YOMEDIA
Đề 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
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 đề
AMBIENT/
Chủ đề:
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?
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
