Bộ đề ôn thi môn Cấu trúc dữ liệu và Giải thuật (Có lời giải)

 Bộ đề ôn thi môn Cấu trúc dữ liệu và Giải thuật (Có lời giải) - De-Thi.com
 ĐÁP ÁN
Phần: Trắc nghiệm
 1. A 2. A 3. A 4. D 5. C 6. C 7. D 8. A
 9. B 10. C 11. C 12. C 13. A 14. C 15. D
Phần: Đọc hiểu
Câu 1:
input: 44,33,88,55,66,22,11,77
output: 11,44,33,88,55,66,22,77
Câu 2:
dec2bin:
input: 150
output: 1,0,0,1,0,1,1,0
Câu 3:
linked_list:
input: 44,66,11,22,33,55
output: 55,33,11,44,66,22
Câu 4:
priority_queue_max:
input: 44,55,11,22,66,33
output: 66,55,33,22,44,11
 De-Thi.com Bộ đề ôn thi môn Cấu trúc dữ liệu và Giải thuật (Có lời giải) - De-Thi.com
 ĐỀ SỐ 6
 TRƯỜNG ĐẠI HỌC KINH TẾ - KỸ ĐỀ THI KẾT THÚC HỌC PHẦN
 THUẬT CÔNG NGHIỆP CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
 KHOA CÔNG NGHỆ THÔNG TIN Hệ đào tạo: ĐẠI HỌC
 Thời gian: 90 phút, không kể thời gian phát đề
 ĐỀ 1
Câu 1 (3 điểm). 
a. Viết giải thuật sắp xếp Bubble Sort để sắp xếp một dãy số nguyên theo thứ tự tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau:
 42, 27, 15, 29, 21, 68, 34, 18
Câu 2 (3 điểm). Cho một danh sách nối đơn lưu trữ các số nguyên, giả sử đầu của danh sách 
được trỏ bởi con trỏ p. Hãy viết thủ tục thực hiện các công việc sau:
a. Tạo nút cho danh sách
b. Bổ sung một nút mới vào giữa danh sách.
c. Tìm phần tử X trong danh sách.
Câu 3 (3 điểm). Cho một dãy A gồm các số nguyên như sau
 6 11 5 10 15 20 2 7
Hãy tìm một dãy con (không nhất thiết phải liên tiếp nhau) dài nhất có tổng các số chia hết 
cho số k = 3 (k nguyên dương).
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án, 
Truy vết).
b. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm). Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự giữa.
 ----------HẾT----------
 De-Thi.com Bộ đề ôn thi môn Cấu trúc dữ liệu và Giải thuật (Có lời giải) - De-Thi.com
 ĐÁP ÁN
Câu 1 (3 điểm). 
a. Viết giải thuật sắp xếp Bubble Sort để sắp xếp một dãy số nguyên theo thứ tự tăng dần.
Giải thuật: 
Void Bubble sort (int a[],int n)
{
 int i, j; 
 for (i=0; i<n; i++)
for (j=n-1; j>I;j--)
if (a[j]<a[j-1])
swap (&a[j],&a[j-1]);
}
b. Minh họa giải thuật trên với dãy số đã cho sau:
42, 27, 15, 29, 21, 68, 34, 18
 Dòng A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
 1 42 27 15 29 21 68 34 18
 2 42 27 15 29 21 34 68 18
 3 42 27 15 21 29 39 68 18
 4 42 15 27 21 29 39 68 18
 5 15* 42 27 21 29 39 68 18
 6 42 27 21 29 39 18 68
 7 42 27 21 29 18 39 68
 8 42 27 21 18 29 39 68
 9 42 27 18 21 29 39 68
 10 42 18 27 21 29 39 68
 11 18 42 27 21 29 39 68
 12 18* 42 27 21 29 39 68
 13 27* 42 21 29 39 68
 14 21* 42 29 39 68
 15 29* 42 39 68
 16 39* 42 68
 17 42* 68
 18 68*
→15; 18; 27; 21; 29; 39; 42; 68
Giải thích:
 De-Thi.com Bộ đề ôn thi môn Cấu trúc dữ liệu và Giải thuật (Có lời giải) - De-Thi.com
a[0]= 42; a[1]= 27; a[2]= 15; a[3]= 29; a[4]= 21; a[5]=68; a[6]= 34; a[7]= 18
Ta có i=0; j = n-1= 8-1=7
Ta duyệt từ cuối dãy về vị trí j về i ta thấy a[6]=34 đổi chỗ a[6] và a[5] 
→ 42; 27; 15; 29; 21; 34; 68; 18
J=j-1 = 6-1=5, thấy a[j]=a[5]=34 > a[j-1]=a[4]=21→ dữ nguyên vị trí
Lập lại các bước
...
 De-Thi.com Bộ đề ôn thi môn Cấu trúc dữ liệu và Giải thuật (Có lời giải) - De-Thi.com
 ĐỀ SỐ 7
 TRƯỜNG ĐẠI HỌC KINH TẾ - KỸ ĐỀ THI KẾT THÚC HỌC PHẦN
 THUẬT CÔNG NGHIỆP CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
 KHOA CÔNG NGHỆ THÔNG TIN Hệ đào tạo: ĐẠI HỌC
 Thời gian: 90 phút, không kể thời gian phát đề
 ĐỀ 2
Câu 1 (3 điểm) 
a. Viết giải thuật sắp xếp Selection Sort để sắp xếp một dãy số nguyên theo thứ tự tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau:
 30, 47, 35, 49, 41, 31, 24, 28
Câu 2 (3 điểm) Cho một danh sách nối đơn lưu trữ các số nguyên, giả sử đầu của danh sách 
được trỏ bởi con trỏ p. Hãy viết thủ tục thực hiện các công việc sau:
a. Tạo nút cho danh sách
b. Bổ sung một nút mới vào đầu danh sách.
c. Xóa nút cuối của danh sách.
Câu 3 (3 điểm) Cho một dãy A gồm các số nguyên như sau
 2 3 5 7 9 6 12 7
Hãy tìm một dãy con (không nhất thiết phải liên tiếp nhau) dài nhất có tổng các số chia hết 
cho số k = 5 (k nguyên dương).
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án, 
Truy vết).
b. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự sau.
 ----------HẾT----------
 De-Thi.com Bộ đề ôn thi môn Cấu trúc dữ liệu và Giải thuật (Có lời giải) - De-Thi.com
 ĐÁP ÁN
Câu 1 (3 điểm) 
a. Viết giải thuật sắp xếp Selection Sort để sắp xếp một dãy số nguyên theo thứ tự tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau:
30, 47, 35, 49, 41, 31, 24, 28
a. Giải thuật
Void Selectionsort(int a[],int n)
{
 int min;
 for (int i=0;i<=n-1;i++)
 {
 min=i;
 for (int j = i+1;j<n;j++)
if (a[j] < a[min] )
min = j;
if (i != min)
swap(&a[min],&a[i]);
}
}
b. Minh họa
 Dòng A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] Doicho(a[min],a[i])
 1 30 47 35 49 41 31 24 28 A[6]=24 là min
 2 24* 47 35 49 41 31 30 28 Đổi chỗ (24,30)
 3 47 35 49 41 31 30 28
 4 28* 35 49 41 31 30 47 Đổi (28,47)
 5 35 49 41 31 30 47
 6 30* 49 41 31 35 47 Đổi (30,35)
 7 49 41 31 35 47
 31* 41 49 35 47 Đổi (31,49)
 41 49 35 47
 35* 49 41 47 Đổi (35,41)
 49 41 47
 41* 49 47 Đổi (41,49)
 49 47
 47* 49 Đổi (47,49)
 49*
→ 24; 28; 30; 31; 35; 41; 47; 49
 De-Thi.com Bộ đề ôn thi môn Cấu trúc dữ liệu và Giải thuật (Có lời giải) - De-Thi.com
 ĐỀ SỐ 8
 ĐH QUỐC GIA HÀ NỘI ĐỂ THI HỌC PHẦN HỌC KÌ I
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ MÔN: CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
 Thời gian: 120 phút (không kể thời gian giao đề)
Câu 1 (2 điểm). Các mệnh đề sau đây là đúng hay sai. Hãy trả lời Đúng hoặc Sai và giải 
thích ngắn gọn.
a) Khi sắp xếp 7 số nguyên, thuật toán Sắp xếp chèn (Insertion sort) thường chạy nhanh hơn 
thuật toán Sắp xếp hoà trộn (Merge sort).
b) Lưu danh sách N các số nguyên được sắp xếp theo thứ tự tăng dần vào một danh sách liên 
kết đơn (single-linked list). Thời gian tìm kiếm trung bình xem một số có nằm trong danh 
sách trên hay không là O(log2 N).
c) Tất cả các thuật toán sau là sắp xếp ổn định (stable sort): Sắp xếp hoà trộn (Merge Sort), 
Sắp xếp chọn (Selection Sort), Sắp xếp vun đống (Heap Sort).
d) Bộ nhớ cần sử dụng để lưu N số thực bằng mảng (array) ít hơn khi lưu bằng danh sách 
liên kết đơn (single-linked list).
e) Thời gian tồi nhất để tìm phần tử nhỏ nhất của một tập hợp khi lưu các phần tử của tập đó 
trong cây thứ tự bộ phận (heap) hay cây tìm kiếm cân bằng (AVL hoặc red-black tree) đều là 
O(log2 N).
Câu 2 (1 điểm). Cho dãy N các số nguyên (ví dụ 6 số: 2,1,1,2,3,2). Bạn hãy:
a) Trình bày thuật toán có thời gian chạy nhanh hơn O(N2) bằng mã giả để tìm được tập các 
phần tử duy nhất từ dãy trên (với ví dụ trên là: 2,1,3).
b) Đánh giá độ phân phức tạp tính toán của thuật toán. Chú ý không cần quan tâm tới thứ tự 
các phần tử trả về.
Câu 3 (1 điểm). Trong một cây nhị phân, mỗi nút (node) trong cây cũng là gốc của một cây 
nhị phân con. Hãy trình bày thuật toán và cấu trúc dữ liệu (nếu cần) bằng mã giả để tìm được 
số nút của từng cây nhị phân con đó. Ví dụ với cây nhị phân gồm: cha và con trái. Cây gốc 
cha có số nút là 2 ; và cây gốc con trái có số nút là 1.
Câu 4 (1 điểm). Sử dụng ý tưởng thiết kế thuật toán Chia để trị để tính giá trị biểu thức
E = kn. Bạn hãy:
a) Trình bày ý tưởng của giải thuật, minh họa với biểu thức 924
b) Trình bày giải thuật bằng mã giả dựa trên ý tưởng Chia để trị để tính biếu thức E = kn
Câu 5 (2 điểm). Cho đồ thị vô hướng G = (V, E) có trọng số được biểu diễn như hình sau. 
Bạn hãy:
 De-Thi.com Bộ đề ôn thi môn Cấu trúc dữ liệu và Giải thuật (Có lời giải) - De-Thi.com
a) (1 điểm) Minh họa các bước thực hiện thuật toán Prim tìm cây khung (cây bao trùm) nhỏ 
nhất đồ thị G và cho biết độ dài của cây khung nhỏ nhất của G.
b) (1 điểm) Hãy cho biết khi nào có thể xảy ra trường hợp một đồ thị G' sẽ có nhiều cây 
khung (cây bao trùm) nhỏ nhất khác nhau (Không cần chứng minh). Hãy thay đổi trọng số 
của đồ thị G ở trên để được đồ thị G' có nhiều cây khung (cây bao trùm) nhỏ nhất.
Câu 6 (1 điểm). Cho dãy số A = 17, 28, 45, 56, 34, 92, 76, 15 và hàm băm h(x) bằng phần 
dư của x khi chia cho 11.
a) Bạn hãy minh hoạ việc sử dụng hàm băm theo phương pháp chia (separate chaining) với 
kích thước bảng bằng 11 và phương pháp thăm dò tuyến tính (linear probing) đề giải quyết 
va chạm.
b) Khi tăng kích thước bảng bằng 23, ta nên sử dụng phương pháp băm nào ?
Câu 7 (1 điểm). Cho đồ thị có hướng G gồm 8 đỉnh và 15 cạnh có trọng số như dưới đây:
Cạnh (0,2) (0,4) (0,7) (1,3) (2,1) (3,7) (6,1) (1,5) (2,3) (4,6) (7,0) (1,7) (3,5) (5,2) (7,2)
Trọng 
 2 5 8 5 2 3 52 4 1 9 3 9 10 10 3
 số
a) Hãy vẽ đồ thị biểu diễn G.
b) Hãy áp dụng thuật toán Dijkstra để tìm cây đường đi ngắn nhất xuất phát từ đỉnh 0 tới tất 
cả các đỉnh khác.
Câu 8 (1 điểm). Cho dãy N số nguyên {a1, ,aN}. Cho M ≤ N. Như vậy có (N ― M + 1) tập 
con M số nguyên liên tiếp của dãy là: {a1,..,aM},{a2,..,aM+1}, .,{aN―M+1,..,aN}. Hãy trình bày 
chương trình tìm ra giá trị nhỏ nhất của các tập con trên (có N ― M + 1 số). Đánh giá độ 
phức tạp thuật toán.
Ví dụ: N=5, dãy số {1,4,3,2,1} và M=3. Kết quả là: 1,2,1.
 ----------HẾT----------
 De-Thi.com Bộ đề ôn thi môn Cấu trúc dữ liệu và Giải thuật (Có lời giải) - De-Thi.com
 ĐÁP ÁN
Câu 1: 
a. Đúng. Với N nhỏ, MergeSort chia đôi không có đáng kể lợi ích (vd: khi N=2), nhưng mất 
nhiều thời gian cho sao chép dữ liệu ra mảng phụ và gọi hàm đệ qui. 
b. Sai. Linked-list không truy nhập trực tiếp được, nên thời gian là O(N). 
c. Sai. Selection sort và Heap sort không phải là sắp xếp ổn định. 
d. Đúng. Linked-list ngoài lưu giá trị như mảng, còn phải lưu thêm con trỏ (là địa chỉ ô nhớ). 
e. Sai. Trong cây min-heap, đọc giá trị nhỏ nhất là O(1) do ở gốc cây. 
Câu 2: 
Cách 1 (sắp xếp): O(N.log(N)) -Sắp theo thứ tự tăng dần (MergeSort, QuickSort. C++, Java: 
hàm có sẵn) -Lấy phần tử đầu tiên -Duyệt các phần tử tiếp sau, và lấy nếu nó khác với phần 
tử ngay trước nó 
Cách 2 (Cây tìm kiếm): O(N.log(N)) 
- S là tập kết quả, lưu bằng cây tìm kiếm nhị phân cân bằng (C++ map, Java TreeSet). 
- Duyệt lần lượt các phần tử. Phần tử được cho vào S nếu trước đó không nằm trong S. 
Cách 3 (Bảng băm): Tương tự cách 2, O(N) 
- S là tập kết quả, lưu bằng bảng băm (hash table) (C++ unordered_map, Java HashSet). 
- Duyệt lần lượt các phần tử. Phần tử được cho vào S nếu trước đó không nằm trong S. 
Chú ý: Cách làm sử dụng mảng đếm các phần tử (tương tự counting sort) không đúng, bởi 
cách làm đó chỉ áp dụng được khi chênh lệch giữa phần tử lớn nhất và nhỏ nhất của dãy 
không lớn. (Còn ở bài này không có giới hạn nào.) 
Câu 3: Mỗi nút có: count (số nút), left (child), right (child) 
- Duyệt cây theo trật tự sau (post order) để tìm số nút. 
int countNodes(Node root) { 
if (root == null) return 0; 
root.count = 1 + countNodes(root.left) + countNodes(root.right); 
return root.count; 
} 
Câu 4: 
long long power(int k, int n) { 
if (n<0) return -1; //Hoặc gửi ra thông báo lỗi 
if (n==0) return 1; 
long long H = power(k, n/2); 
if (n%2 == 0) return H*H; 
else return k*H*H; 
} 
 De-Thi.com Bộ đề ôn thi môn Cấu trúc dữ liệu và Giải thuật (Có lời giải) - De-Thi.com
Chú ý: nếu không dùng biến phụ H thì chạy chậm (=>gần như sai), bởi phải tính lại nhiều 
lần. 
if (n%2 == 0) return power(k, n/2)*power(k, n/2); 
else return k*power(k, n/2)*power(k, n/2); 
Câu 5:
a. Trình bày thuật toán Prim xuất phát từ 1 đỉnh (không phải thuật toán Kruskal). Tổng trọng 
số 
cây bao trùm nhỏ nhất là 17. 
b. Khi tất trọng số bằng nhau. (Hay các trường hợp khác.) 
Câu 6: 
a. Trình bày kết quả với phương pháp chia (seperate chaining). 
Trình bày kết quả với phương pháp thăm dò tuyến tính (linear probing) 
b. Với mảng kích cỡ 23, không có va chạm => nên sử dụng thăm dò tuyến tính. 
(Về lý thuyết, phương pháp chia dùng mảng nhỏ hơn, nên bằng 1/5 số phần tử. Ngược lại với 
thăm dò tuyến tính, dùng mảng lớn hơn, nên gấp 2 số phần từ.) 
Câu 7: 
a. Vẽ đúng 
b. Thứ tự các đỉnh (và khoảng cách nhỏ nhất đi từ 0) tìm được theo Dijkstra là: 0 (0), 2 (2), 
3(3), 1(4), 4(5), 7(6), 5(8), 6(14) 
Câu 8: Phần chương trình chung 
Result = null //Tập lưu kết quả min 
S= null//Lớp lưu tập con M phần tử, tùy cách cài đặt quyết định độ phức tạp 
for i = 1 to M-1: 
S.add(a_i, i) //Khởi tạo S gồm M-1 phần tử đầu dãy 
for i= M to N: 
S.add(a_i, i) //Thêm phần tử phía đầu bên phải 
Result.add(S.getMin()); //Lấy ra giá trị nhỏ nhất của tập M phần tử 
S.remove(a_i-M, i-M); //Xoá đi phần tử bên trái 
return Result 
Cách 1: - Cài đặt S là cây tìm kiếm nhị phân cân bằng (C++ là set, Java là TreeSet), mỗi 
node gồm hai giá trị (a_i, i) 
- add(a_i, i) là thêm vào cây node (a_i, i) 
- getMin(): lấy giá trị nhỏ nhất (trái nhất của cây) 
- remove(a_i-M, i-M): xoá node(a_i-M, i-M) 
Độ phức tạp: O(N*log(M)) 
Chú ý: Cách làm này (hay dùng hàng ưu tiên chỉ số) chính là kỹ thuật được dùng để cài đặt 
thuật toán Dijkstra (và đơn giản hơn cài đặt thuật toán Dijstra). 
 De-Thi.com