Phiếu bài tập Thuật toán và độ phức tạp có đáp án

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

1. AO(2n)
2. BO(log n)
3. CO(n)
4. DO(n²)

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AMảng chỉ được chứa số dương
2. BMảng không được có quá 1000 phần tử
3. CĐộ dài mảng phải là lũy thừa của hai
4. DMảng phải được sắp xếp

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng log₂ n
2. BKhoảng n
3. CKhoảng n²
4. DKhoảng n / 2

Công thức truy hồi T(n) = T(n − 1) + O(n) có nghiệm là gì?

1. AO(n²)
2. BO(n)
3. CO(2ⁿ)
4. DO(n log n)

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng có thứ tự ngẫu nhiên
2. BMột mảng mà các phần tử đều khác nhau
3. CMột mảng đã được sắp xếp
4. DMột mảng có độ dài 2

Với các đồng xu 1, 3 và 4 và số tiền 6, phương pháp tham lam "đồng lớn nhất trước" dùng bao nhiêu đồng, so với tối ưu?

1. ATham lam dùng 3 đồng; tối ưu là 2
2. BTham lam dùng 4 đồng; tối ưu là 3
3. CTham lam dùng 3 đồng; tối ưu là 3
4. DTham lam dùng 2 đồng; tối ưu là 2

Độ phức tạp thời gian của: for i = 1 to n: for (j = i; j ≤ n; j = j + i) thực hiện công việc O(1) là gì?

1. AO(n)
2. BO(n √n)
3. CO(n²)
4. DO(n log n)

Sự khác biệt giữa một bài toán bất khả quyết định và một bài toán không khả thi (intractable) là gì?

1. ABài toán không khả thi không thể giải bằng bất kỳ thuật toán nào, còn bài toán bất khả quyết định chỉ cần thời gian hàm mũ
2. BBài toán bất khả quyết định thuộc NP, còn bài toán không khả thi thuộc P
3. CCả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán
4. DBài toán bất khả quyết định không có thuật toán nào cho mọi đầu vào; bài toán không khả thi có thuật toán, nhưng quá chậm