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

Độ 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(n²)
2. BO(1)
3. CO(n log n)
4. DO(n)

Một bài toán thường được gọi là khả thi (tractable) nếu:

1. ANó chỉ có thể được giải bằng cách thử mọi khả năng
2. BNó có thể được giải trong thời gian đa thức
3. CNó có thể được giải trong thời gian hằng số
4. DNó không có lời giải

Thời gian chạy nào sau đây là đa thức?

1. AO(2ⁿ)
2. BO(n³)
3. CO(n!)
4. DO(nⁿ)

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AĐúng, nhưng chỉ khi n nhỏ hơn 100
2. BĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
3. CKhông, vì n³ nhỏ hơn n² khi n lớn
4. DKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

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

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

Vì sao tìm kiếm nhị phân không cho thời gian O(log n) trên một danh sách liên kết đơn?

1. AĐến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp
2. BDanh sách liên kết không thể được sắp xếp
3. CCác phép so sánh trên nút danh sách liên kết chậm hơn
4. DTìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ

Định lý Cook–Levin đã thiết lập điều gì?

1. ABài toán thỏa mãn Boole (SAT) là NP-đầy đủ
2. BP không bằng NP
3. CBài toán dừng là bất khả quyết định
4. DMọi bài toán NP đều giải được trong thời gian hàm mũ