zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

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

Chia sẻ: Ngocbich Bich | Ngày: | Loại File: PDF | Số trang:4

Báo xấu

76
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề 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 đề

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề 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út Câ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 i tí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 ư c cà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 s nguyê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út Câ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 n b 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 i tí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 t h 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ách thw 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 3 a) Khai báo CTDL bi u di n danh sách liên k t b) 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 ưu tiê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, An có 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 3 Yê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út Câ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 ưa và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ác hành ng sau: 1. Xen vào 5099, 23,, 213, ,36, 300, 19, 283. 2. Lo i 300, 36 r i xen vào 146, 360, 480. Yêu c u: c n gi i thích t i sao nh n ư c k t qu như th . Câu 4. Trình bày tư tư ng c a thu t toán PRIM tìm cây bao trùm ng n nh t c a th vô hư ng liên thông có tr ng s . Mô t thu t toán này. Áp dung thu t toán tìm cây bao trùm ng n nh t c th sau A 7 2 2 1 C D B 3 6 4 4 9 F E 6 Yêu c u: C n ph i tìm ra k t qu c a m i bư c và gi i thích.
B n quy n tài li u thu c v di n àn http://sinhviennganhang.com THI 4 CTDL VÀ GI I THU T Cho K46CA, CB,CC (Th i gian: 120 phút) Câu 1. (3 i m) Ki u d li u tr u tư ng ư c xác nh như sau: • Các i tư ng DL là các danh sách s nguyên ư c s p x p theo th t không gi m. • Các phép toán g m: 1. Tìm xem danh sách có ch a s nguyên cho trư c không? 2. Xen m t s nguyên m i vào danh sách sao cho sau khi xen, danh sách v n còn ư c s p 3. K t h p 2 danh sách ư c s p thành m t danh sách ư c s p. Danh sách ư c cài t b ng danh sách liên k t. a) Hãy vi t file u ch a mô t CTDL và các prototype c a các hàm th c hi n các phép toán trên (V i m i hàm c n vi t ra các i u ki n trư c và i u ki n sau) b) Hãy cài t hàm xen vào. Câu 2. (2 i m) Gi s các i tư ng khác nhau có giá tr ưu tiên khác nhau và hàng ưu tiên ư c cài t b i cây tìm ki m nh phân v i khóa tìm ki m là giá tr ưu tiên. a) Hãy mô t CTDL bi u di n hangf ưu tiên trong cáhc cài t trên b) Hãy vi t hàm lo i i t ong có giái tr ưu tiên nh nh t kh i hàng ưu tiên. Câu 3. (2,5 i m) a) Hãy mô t CTDL bi u di n b ng băm dây chuy n và vi t hàm xem vào b ng băm này theo hàm băm ã cho. b) Gi s c c a b ng là 5, các giá tr khóa là các s nguyên không âm. Và hàm băm là hàm chua l y ph n sư. Áp d ng hàm xen vào, t b ng băm day chuy n r ng, hãy â vào các d li u v i khóa 9,12,31,217,5.42,16. Cho bi u di n hình h c b ng băm k t qu . Câu 4. (1,5 i m) a) Hãy trình bày tư tư ng c u thu t toán i qua th theo b r ng và theo sâu. b) Cho th nh hư ng trong hình v sau: c) Hãy ưa ra th t các nh ư c thưm theo b r ng và sâu khi xu t phát t nh A. A C E B D H G F Câu 5. (1 i m) Gi s các xâu ư c t o thành t 2 lý t A vàB. S d ng ccs phép toán ngăn x p, hãy vi t hàm cho bi t m t xâu có d ng AnBn (n>=0) hay không?

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.