tramhieu892005
18-04-2012, 18:36
MÌnh Sắp Thi rùi có bạn nào có thể giúp mình không?
mình thật sự kông biết cách giải bài này, bạn nào giải được thì giúp mình nhé! thanks
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. 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
b) Hãy chứng tỏ rằng thời gian chạy của giải thuật đã viết là O(n).
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.
mình thật sự kông biết cách giải bài này, bạn nào giải được thì giúp mình nhé! thanks
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. 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
b) Hãy chứng tỏ rằng thời gian chạy của giải thuật đã viết là O(n).
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.