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

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

Ghi nhớ (memoisation) là gì?

1. AViết chú thích bên cạnh từng dòng mã
2. BTự động chuyển đệ quy thành vòng lặp tương đương để không cần ngăn xếp lời gọi
3. CLưu kết quả của các lời gọi hàm để các lời gọi lặp lại được trả lời từ bộ nhớ
4. DGiải phóng bộ nhớ sau khi một hàm trả về

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 2 đồng; tối ưu là 2
3. CTham lam dùng 3 đồng; tối ưu là 3
4. DTham lam dùng 4 đồng; tối ưu là 3

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 100
2. BKhoảng 1,000
3. CKhoảng 500,000
4. DKhoảng 20

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. ASắ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
2. BSắ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
3. CSắp xếp chèn là O(n log n) trong trường hợp xấu nhất
4. DCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử

Bài toán thỏa mãn nào sau đây được biết là giải được trong thời gian đa thức?

1. AThỏa mãn mạch
2. B3-SAT, trong đó mỗi mệnh đề có đúng ba literal
3. C2-SAT, trong đó mỗi mệnh đề có tối đa hai literal
4. DSAT tổng quát trên các công thức dạng chuẩn tắc hội

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 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
2. BX không có thuật toán đa thức, và X quyết định đượ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