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

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n
2. BThời gian nó mất trên một máy tính chậm
3. CThời gian nó mất trên đầu vào nhỏ nhất
4. DThời gian tối đa nó mất trên mọi đầu vào kích thước 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. ALogarit
2. BTuyến tính
3. CBậc hai
4. DHằng số

Ký hiệu nào mô tả cận dưới của tốc độ tăng?

1. Ao (little o)
2. BΘ (Big Theta)
3. CO (Big O)
4. DΩ (Big Omega)

Phát biểu nào về một hàm đệ quy không có trường hợp cơ sở nào đạt tới được là đúng?

1. ANó chạy trong thời gian O(1)
2. BTrình biên dịch luôn biến nó thành một vòng lặp kết thúc an toàn
3. CNó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
4. DNó tự động trả về 0

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ACác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
2. BSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
3. CSắp xếp chèn là O(n log n) trong trường hợp xấu nhất
4. DSắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

Phải chứng minh hai điều nào để chứng tỏ một bài toán quyết định X là NP-đầy đủ?

1. AX không có thuật toán đa thức, và X quyết định được
2. BX thuộc NP, và một bài toán NP-đầy đủ đã biết quy dẫn về X trong thời gian đa thức
3. CX thuộc P, và X quy dẫn về SAT
4. DX quy dẫn về một bài toán trong P, và X thuộc NP

Bài toán dừng cho thấy rằng:

1. ANên tránh các vòng lặp
2. BKhông thuật toán nào có thể quyết định, với mọi chương trình và đầu vào, liệu nó có dừng hay không
3. CMọi chương trình cuối cùng đều dừng
4. DMột số chương trình chạy nhanh hơn trên máy tính nhanh hơn, nên việc dừng phụ thuộc vào phần cứng