Đề thi tham khảo CTDL & GT của khóa trước trước đây.

Đề thi tham khảo CTDL & GT của khóa trước trước đây. Các bạn tham khảo nha.
Trong nội dung này mình thấy gần giống với phần ôn tập của thầy. Nhưng thiếu phần Biểu diễn quá trình thực hiện của giải thuật.

ĐỀ THI
Môn : Thuật Giải
Giảng viên : Nguyễn Hòa
Thời gian : 120 phút
Sinh viên không được sử dụng tài liệu

1. Câu 1 :
a) Dựa trên thủ tục MAX_HEAPIFY(A, i) hãy viết mã giả cho thủ tục MIN_HEAPIFY(A, i) để thực hiện thao tác duy trì tính chất min-heap trên cây con định gốc tại i. (2.5 điểm)
b) Sử dụng thủ tục MIN_HEAPIFY(A, i) đã viết ở câu a, viết giải thuật Heapsort để sắp xếp một mảng các số theo thứ tự giảm dần. (2.5 điểm)
2. Câu 2 :
a) Mặc dù Bucketsort là giải thuật sắp xếp thời gian tuyến tính, O(n), nhưng nó có hạn chế là chỉ sắp xếp được các số trong khoảng [0, 1). Tuy nhiên, có thể ứng dụng giải thuật Bucketsort để viết một giải thuật sắp xếp các số bất kỳ cũng có thời gian chạy là O(n).
Hãy ứng dụng Bucketsort để viết giải thuật sắp xếp thời gian O(n) vừa nêu ở trên. (2.0 điểm)
b) Hãy chứng tỏ rằng thời gian chạy của giải thuật đã viết là O(n). (1.0 điểm)
3. Câu 3 : Hãy nêu ưu điểm và hạn chế của thuật toán Countingsort khi so sánh với thuật toán Quicksort. (2.0 điểm)

De thi cung ko may hoc bua nhi. On bai Ki la co the wa dc.