Tham khảo Đề thi thuật giải năm trước !

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

1. Counting Sort chỉ dùng được cho số nguyên. Kể cả cho trường hợp số nguyên, nếu giả dụ tôi cho số 1 tỉ chẳng hạn, lập tức Counting Sort hỏng ngay vì chẳng thể nào có được 1 mảng 1 tỉ phần tử (ít nhất là với các ngôn ngữ bây giờ)
2. Bucketsort có hạn chế là chỉ sắp xếp được các số trong khoảng [0, 1)
3. The time for counting sort is O(n + 9) = O(n).
4. Counting sort is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). It uses this range to create an array C of this length. Each index i in array C is then used to count how many elements in A have the value i. The counts stored in C can then be used to put the elements in A into their right position in the resulting sorted array. It is less efficient than pigeonhole sort.



Học kỳ 2: năm học 2007-2008 (Lần 1)
Lớp: HCTH072C & HCTH072D
Câu 1:
a. Dựa trên giải thuật MAX-HEAPIFY(A,i) hãy viết giải thuật MIN-HEAPIFY(A,i) (bằng mã giả) để 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đ)
b. Sử dụng giải thuật 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. Sử dụng cấu trúc dữ liệu MAX-HEAP, hãy viết một giải thuật (bằng mã giả) tính giá trị của phần tử lớn nhất trong một mảng các số thực bất kỳ. (2đ)
b. Tính độ phức tạp của giải thuật đã viết ở câu a. (1đ)
Câu 3:
a. Viết giả thuật COUNTINGSORT để sắp xếp một mảng các số nguyên không âm (nằm trong khoảng từ 0 đến k) theo thứ tự tăng dần. (1.5đ)
b. Biểu diễn quá trình thực hiện giải thuật COUNTINGSORT trên mảng các số nguyên không âm A=<1,0,1,3,6,2,4>. (1.5đ)
--------------------------------------------------------------------------------------------------------------------------------------

Học kỳ 1: năm học 2007-2008 (Lần 1, đề 1)
Lớp: HCTH071C
Câu 1:
a. Viết thuật toán (bằng mã giả) tính bán bậc vào của một đỉnh v trong một đồ thị có hướng G. (2đ)
b. Tính độ phức tạp của thuật toán đã viết ở câu a. (1đ)
Câu 2:
a. Dựa trên thuật toán MAX-HEAPIFY (A,i) hãy viết thuật toán MIN-HEAPIFY (A,i) 9bằng mã giả) để 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đ)
b. Sử dụng thuật toán MIN-HEAPIFY (A,i) đã viết ở câu a, viết thuật toán Heapsort để sắp xếp một mảng các số theo thứ tự giảm dần. (2đ)
Câu 3:
Viết thuật toán Prim để tìm cây bao trùm bé nhất (minimum spanning tree) của một đồ thị vô hướng G. (2.5đ)
---------------------------------------------------------------------------------------------------------------------------------------

Học kỳ 1: năm học 2007-2008 (Lần 2)
Câu 1:
a. Viết thuật toán BUILD-MAX-HEAP (bằng mã giả) để tạo một max-heap từ một mảng A các số cho trước. (2đ)
b. Thực hiện thuật toán BUILD-MAX-HEAP đã viết trong câu a đối với mảng A=<3,7,35,18,6,16,5>. (2đ)
Câu 2:
a. Sử dụng thuật toán tìm kiếm theo chiều rộng, viết một thuật toán (bằng mã giả) cho biết khoảng cách đường đi ngắn nhất giữa 2 đỉnh u và v trong đồ thị vô hướng liên thông G. (2đ)
b. Đánh giá thời gian chạy của thuật toán đã viết trong câu a. (2đ)
Câu 3:
Cho một heap có số nút là n. Chứng minh rằng các nút có chỉ số [n/2]+1, [n/2]+2,....,n là các nút lá của heap này. (2đ)

Thank bạn Nhung !

Thanks ban Nhung nhieu nhieu!!!

mình không hiểu về counting sort bạn nào biết chỉ cho mình với , cách làm ấy mà ? Cám ơn trước nha .

Thanks bạn nhiều.

Cảm ơn bạn Nhung nhiều

CAM ON BAN NHA !!!

thanks ban Nhung nhieu lam

Thank a lot ^_^

cám ơn bạn nhìu nha! . Chúc bạn luôn học tốt!

b. Thực hiện thuật toán BUILD-MAX-HEAP đã viết trong câu a đối với mảng A=<3,7,35,18,6,16,5>. (2đ)

nhờ bạn chỉ giúp mình câu này với. mình không hiểu lắm về thao tác này. tks!