đây là đề thi k51 mình gửi cả lớp tham khảo chú mọi người thi tốt

Câu 1 : Giải công thức truy hồi xác định độ phức tạp của thuật toán đệ quy sau





T(n) = T(n-1) -n +1 với n>1 ; T(1)=1.





Câu 2 : Thuật toán sắp xếp mảng theo phương pháp sắp xếp nhanh được viết như sau

Quicksort (array a, int n, int l, int r) º

{ //sắp xếp đoạn từ chỉ số 1 đến r của mảng a có n phần tử

X = a[(1+r)/2];
Do {
While (a[i]< x) i++;
While (x< a[j]) j--;
if (i<=j) {swap (a[i],a[j]) i++; j--;}
} while (i<=j);
if (l<j) quicksort (l,j);
if (i<r) quicksort (i,r);
}

Hãy :
- phương pháp được sử dụng để thiết kế thuật toán trên là gì
? giải thích?
- xác định độ phức tạp của thuật toán với mảng kích thước độ
dài n?

Câu 3 : Trình bày
thuật toán Dijkstra tìm đường đi ngắm nhất xuất phát từ 1 đỉnh đến các đỉnh
khacscuar đồ thị có trọng số dương. Tư tưởng của phương pháp tham lam thể hiện
trong thuật toán này như thế nào? Cho ví dụ một đồ thị với 5 đỉnh và 10 cạnh ,
áp dụng tìm đường đi ngắn nhất xuất phát từ đỉnh 1 tới các đỉnh còn lại của đồ
thị

cái này hay đó ! nếu anh có cả đề thi các môn khác nữa thì post luôn cho tụi xem ôn thi luôn ! thanks :)

ngon