Một số đề thi Thuật Giải cũ (tham khảo thoy)

ĐỀ 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
Ngày thi : 11 – 07 – 2007
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)

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)

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)
-----------------------------

-----------------------------

Bạn lephi chu đáo thiệt scan cả đề thi và úp lên luôn. thanh kìu nhe !;

_ Cám ơn bạn nhiều nhé, mình đang cần mấy cái này để ngâm cứu cho sáng chủ nhật này đây

Bạn nào rảnh thì giải rùi up lên cho mọi người tham khảo lun nha !!!