ĐỀ 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

4
3
7
5
9
4
3
L1 L2
L
An Lan Ba
5 4 2
9 4 7 1 3
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

• 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
n
B