Đề thi hết học phần môn cấu trúc dữ liệu

Đề thi cấu trúc dữ liệu cùa hệ đại học ngân hàng, mời các bạn tham khảo và giải đề
Nội dung trích xuất từ tài liệu:
Đề thi hết học phần môn cấu trúc dữ liệu B n quy n tài li u thu c v di n àn http://sinhviennganhang.com THI 1 MÔN C U TRÚC D LI U VÀ GI I THU T Th i gian: 120 phútCâu 1. Cho danh sách sinh viên. M i sinh viên ư c mô t b i các thu c tính h tên, tu i, gi itính. 1. Hãy cài t danh sách sinh viên b i danh sách liên k t. 2. Hãy vi t th t c lo i kh i danh sách t t c các sinh viên n .Câu 2. Cho danh sách các s nguyên ư c s p x p theo th t không gi m v i danh sách ư ccài t b i m ng: 1. Hãy khai báo CTDL bi u di n dánh sách ó. 2. Hãy vi t th t c xem vào sanh sách m t s nguyên m i n sao cho danh sách nh n ư c v n còn ư c s p theo th t không gi m.Câu 3. M t m ng r ng g m 11 ô ư c ánh s t 0 ên 10 dùng lưu tr các s nguyên. Các snguyên k ư c ưa vào m ng b i hàm băm: h(k) = (k – 3*i)%11 (i = 0,1,…) Hãy ưa các dãy s nguyên 15, 20, 6, 9, 17 vào m ng. Gi i thích t i sao chúng l i ư c ưa vào nh ng v trí ó trong m ng.Câu 4. Cho th nh hư ng sau: 1 2 6 7 3 5 4 i qua th xu t phát t nh 1. 1. Hãy ưa ra r ng các cây t o thành khi i qua th theo b r ng và danh sách các nh theo th t ã i qua. 2. Hãy ưa ra r ng các cây t o thành khi i qua th theo b sâu và danh sách các nh theo th t ã i qua. B n quy n tài li u thu c v di n àn http://sinhviennganhang.com THI 2 MÔN C U TRÚC D LI U VÀ GI I THU T Th i gian: 120 phútCâu 1. (2 i m) Khoa Công ngh ư c bi u di n b i danh sách các l p. M i l p ư c bi u di nb i tên l p và danh sách sinh viên c a l p. M i sinh viên ư c bi u di n b i tên, năm sinh, gi itính. Danh sách các l p ư c cài t b i danh sách liên k t. Hãy khai báo CTDL bi u di n Khoa Công ngh , Cho bi u di n hình h c CTDL này.Câu 2. ( 2,5 i m) Cho 2 danh sách các s nguyên ư c cài t b i danh sách liên k t. Ta c n k th p 2 danh sách thành m t danh sách b ng cách nôi uôi danh sách th nh t t i u danh sáchthw hai. Ví d , t 2 danh sách L1 và L 2, sau khi n i ta ư c L như sau: L1 L2 7 5 9 4 3 L 7 5 9 4 3a) Khai báo CTDL bi u di n danh sách liên k tb) T 2 danh sách liên k t ( có th r ng), hãy vi t hàm k t n i 2 danh sách thành m t danh sách.Câu 3. (2,5 i m) Các giá tr khóa c a cây tìm ki m nh phân là s nguyên. Cho dãy các s nguyên: 5, 1, 6, 8, 4, 9, 7 a) Áp d ng th t c xen vào cây b t u t cây r ng, hãy xây d ng cây tìm ki m nh phân, b ng cách xem vào các nh m i có khóa l n lư t là 5, 1, 6, 8, 4, 9, 7 b) T cây ã xây d ng, hãy dưa ra dãy các khóa theo các th t : trư c, trung và sau.Câu 4. (2 i m) M i ngư i có giá tr ưu tiên là s nguyên. M i ngư i ư c bi u di n b i tên, và gi tr ưutiên. Hàng ưu tiên ư c lưu trong m ng theo th t gi m d n c a giá tr ưu tiên. Ch ng h n, Ancó GTƯT là 5, Ba và Lan có GTƯT là 2 và 4 ư c lưu trong m ng sau: An Lan Ba 5 4 2 0 1 2 Max-1 a) Khai báo CTDL cài a t hàng ưu tiên b i m ng như trên b) Vi t hàm lo i ngư i có giá tr ưu tiên nh nh t.Câu 5. (1 i m) Áp d ng thu t toán s p x p n i b t cho m ng sau 9 4 7 1 3Yêu c u: ưa ra k t qu c a t ng bư c B n quy n tài li u thu c v di n àn http://sinhviennganhang.com THI 3 MÔN C U TRÚC D LI U VÀ GI I THU T Th i gian: 120 phútCâu 1. Cho danh sách tên c a m i l p. M i sinh viên ư c bi u di n b i 2 trư ng: ten, diem.Danh sách ư c cài t b i danh sách liên k t. 1. Hãy khai báo CTDL cài t danh sách ó. 2. Vi t th t c tính i m trung bình c a l p ó. 3. Vi t th t c lo i kh i danh sách t t c sinh viên có i m b ng p cho trư c.Câu 2. Cho m t cây, m i nh có t i a K nh con. Thông tin ch a trong m i nh là s th c.Cây ư c cài t cách ch ra danh sách các con c a m i nh và s d ng con tr . 1. Khai báo CTDL cài t cây b ng cách trên. 2. Vi t th t c i qua cây theo sâu ( quy ho c không quy) tính t ng các s th c lưu trong các nh c a cây.Câu 3. Cho b ng băm óng g m 11 thành ph n. Các giá tr khóa là các s nguyên và ư c ưavào b ng b i hàm băm: h(x) = x%11. Va ch m ư c gi i quy t b ng cách băm l i bình phương.T b ng băm r ng, s d ng t i a 3 l n bă l i, hãy ưa ra b ng băm k t qu khi th c hi n cáchành ng sau: 1. Xen vào 5099, 23,, 213, ,36, 300, 19, 28 ...