Đề thi cơ sở dữ liệu và giải thuật

Tham khảo tài liệu đề thi cơ sở dữ liệu và giải thuật, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Đề thi cơ sở dữ liệu và giải thuật Câu 1 : (3 điểm) Giả sử tồn tại cây nhị phân tìm kiếm (CNPTK) T trên bộ nhớ, có dữliệu của mỗi phần tử là 1 điểm trên mặt phẳng như sau:CODEstruct point { int x,y; };struct BSTree { Node Root; };struct tagNode { point data; tagNode *Left, *Right; };typedef tagNode *Node;Anh (chị) hãy :a) Nhập vào một số thực a, tìm phần tử b của cây T mà b có x gần a nhất (dùng fasbđể lấy giá trị tuyệt đối của số thực).b) Cho biết cặp điểm gần nhau nhất của cây T.Câu 2 : (4 điểm)Trên mặt phẳng Oxy có một hình vuông C, ta chia hình vuông C này thành 04 hìnhvuông C1, C2, C3, C4. Trong mỗi hình vuông Ci (i = 1, 2, 3, 4) ta lại chia thành 04 hìnhvuông nhỏ hơn mỗi hình vuông được tô màu xanh, đỏ, tím, vàng (theo thứ tự như hìnhvẽ). Quá tình chia nhỏ kết thúc khi diện tích nhỏ hơn a (cho trước). Anh (chị) hãy xâydựng cấu trúc dữ liệu động để lưu trữ các hình vuông và thuật toán để xây dựng cáchình vuông này.CODE ___________________________ | | | | | | Đỏ | Xanh | | | | | | | | |____________|_____________| | | | | | | | Tím | Vàng | | | | | | | |____________|_____________|a) Hãy cho biết có bao nhiêu số lần phải chia.b) Hãy cho biết có bao nhiêu hình vuông có diện tích nhỏ hơn b (cho trước).Hết. 1. Cài đặt các giải thuật sắp xếp : nhị phân, Bubble sort, Select sort, Insert sort, Heap sort, Quick sort. 2. Cài đặt thuật toán tìm kiếm nhị phân - Binary Search 3. Chương trình đổi cơ số, cài đặt bằng stack 4. Bài toán Josephus : có N người đã quyết định tự sát tập thể bằng cách đứng trong vòng tròn và giết người thứ M quanh vòng tròn, thu hẹp hàng ngũ lại khitừng người lần lượt ngã khỏi vòng tròn. Vấn đề là tìm ra thứ tự từng người bịgiếtVí dụ : N = 9, M = 5 thì thứ tự là 5, 1, 7, 4, 3, 6, 9, 2, 8Hãy viết chương trình giải quyết bài toán Josephus5. Chọn cấu trúc thích hợp để lưu trữ một đa thức với các hệ số khác 0, khôngcần nhập theo thứ tự bậc. Viết chương trình tính tổng, tích của 2 đa thức, tìmthương và phần dư trong phép chia 2 đa thức, tính đạo hàm của một đa thức.(Có thể cho phép các hệ số là phân số)6. Một danh sách sinh viên được tổ chức lưu trữ bằng cấu trúc danh sách liênkết,một phần tử bao gồm các thành phần như sauint MASOchar *HOTENfloat DIEMTOAN, DIEMVAN, DIEMLYViết các hàm thực hiện các chức năng sau:Nhập xuất, ghi dữ liệu vào file, đọc dữ liệu từ fileThêm, xoá một sinh viên.Tìm kiếm sinh viên theo mã số, theo điểm trung bìnhSắp xếp sv theo mã sốSắp xếp sv theo điểm từ cao xuống thấp, xếp loại, xếp hạng, loại giỏi ởtrên cùng rồi đến khá trung bình yếuđiểm trung bình< 5.0 : Yếu< =6.5 : Nếu có môn dưới 4 : Yếu, ngược lại Trung Bình< 8.0 : Nếu có môn =8.0 : Nếu có môn (xét cách cài đặt đệ quy và không đệ quy) a. Số nút lá b. Số nút có đúng 1 cây con c. Số nút có đúng 2 cây con d. Số nút có khóa nhỏ hơn x (giả sử T là CNPTK) e. Số nút có khóa lớn hơn x (giả sử T là CNPTK) f. Số nút có khóa lớn hơn x và nhỏ hơn y (T là CNPTK) g. Chiều cao của cây h. In ra tất cả các nút ở tầng (mức) thứ k của cây T i. In ra tất cả các nút theo thứ tự từ tầng 0 đến tầng thứ h-1 của cây T (h là chiều cao của T). j. Kiểm tra xem T có phải là cây cân bằng hoàn toàn không k. Tìm mức có nhiều nút lá nhất l. Sao chép cây m. Kiểm tra cây T1 có phải là con cây T không CNPTK: cây nhị phân tìm kiếm. ---------------------------------------------------------Đề thi môn Cấu trúc dữ liệuThời gian 90 phútSinh viên được sử dụng tài liệuCâu 1 (5 điểm)Giả sử tồn tại cây nhị phân tìm kiếm T trong bộ nhớ, với data của 01 node là 01 sốnguyên có cấu trúc như sau:CODE struct Node{ int data; Node *Left, *Right; };typedef Node *BSNode; 2. Anh chị hãy viết chương trình: 1. Đếm số node lá trong cây T (1 điểm) 2. Tạo 01 mảng a (các phần tử là các số nguyên) có số phần tử là số node lá của cây T, mỗi phần tử mang giá trị là giá trị của các node là (2 điểm) 3. Tính trung bình tổng chiều dài đường đi từ gốc đến tất cả các node lá (2 điểm) Câu 2 (5 điểm) Anh chị hãy đề nghị xây dựng 01 cấu trúc dữ liệu (động) và các thủ tục để quản lý các phần tử được mô tả như sau: 1. MỖi phần tử là một tam giác đều, được thể hiện qua toạ độ 03 đỉnh của tam giác. 2.Từ 01 tam giác ta lấy toạ độ tâm của tam giác ta sẽ tạo được 03 tam giác mới có quan hệ với ta ...