Đ 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:ồ ị ị ướ
Đ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.ứ ự
Đ THI 2Ề
MÔN C U TRÚC D LI U VÀ GI I THU TẤ Ữ Ệ Ả Ậ
2
3
45
6 7
1
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:ụ ừ ố ượ ư
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:ạ Ư Ư ượ ư ả
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ụ ậ ắ ế ổ ọ ả
Yêu c u: Đ a ra k t qu c a t ng b cầ ư ế ả ủ ừ ướ
Đ THI 3Ề
MÔN C U TRÚC D LI U VÀ GI I THU TẤ Ữ Ệ Ả Ậ
7
5
9
4
3
7
5
9
4
3
L1 L2
L
An Lan Ba
542
94713
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ậ ể ắ ấ ủ ồ ị
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.ầ ầ ả ế ả ủ ỗ ướ ả
A
6
A
D
B
6
C
6
E
6
F
6
B
6
7 2
2
9
36
44
6
1
Đ 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.ỉ
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 Aế ế ế ộ ạ nBn (n>=0) hay không?
A
6
C
6
E
6
B
6
D
6
H
6
G
6
F
6