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

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

1. AMảng không được có quá 1000 phần tử
2. BMảng chỉ được chứa số dương
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

Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. ABậc hai
2. BHằng số
3. CLogarit
4. DTuyến tính

Công thức truy hồi T(n) = 2T(n/2) + O(n) có nghiệm là:

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

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp vun đống
2. BSắp xếp trộn
3. CQuicksort (phiên bản tại chỗ điển hình)
4. DSắp xếp chọn (phiên bản điển hình)

Chi phí khấu hao của việc tăng một bộ đếm nhị phân là bao nhiêu, biết rằng một lần tăng có thể lật nhiều bit?

1. AO(n) mỗi lần tăng
2. BO(log n) mỗi lần tăng
3. CO(1) mỗi lần tăng
4. DO(n log n) mỗi lần tăng

Phát biểu nào về P và NP là đúng?

1. AĐã được chứng minh rằng P ≠ NP
2. BNP có nghĩa là "không đa thức"
3. CCác bài toán NP không thể được kiểm chứng nhanh
4. DMọi bài toán trong P cũng thuộc NP