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

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A4 giây
2. B1 giây
3. C2 giây
4. D8 giây

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

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

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. AQuicksort
2. BSắp xếp vun đống
3. CSắp xếp nổi bọt
4. DSắp xếp trộn

Cận dưới của sắp xếp dựa trên so sánh trong trường hợp xấu nhất là:

1. AΩ(n)
2. BΩ(n²)
3. CΩ(log n)
4. DΩ(n log n)

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

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

Phân tích khấu hao đo lường điều gì?

1. AChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
2. BChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
3. CChi phí kỳ vọng trên các đầu vào ngẫu nhiên
4. DChi phí của một thuật toán trên đầu vào tốt nhất

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(log n) mỗi lần tăng
2. BO(1) mỗi lần tăng
3. CO(n) mỗi lần tăng
4. DO(n log n) mỗi lần tăng

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. BTìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ
3. CDanh sách liên kết không thể được sắp xếp
4. DCác phép so sánh trên nút danh sách liên kết chậm hơn