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 của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

log₂ 1024 bằng bao nhiêu?

1. A12
2. B10
3. C512
4. D32

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig O
2. BBig Omega
3. CBig Theta
4. DLittle omega

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AMột cây khung nhỏ nhất trong O(E log V)
2. BĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)
3. CĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
4. DMột thứ tự tô-pô trong O(V²)

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 1,000
2. BKhoảng 500,000
3. CKhoảng 20
4. DKhoảng 100

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. ABài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó
2. BMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con
3. CMọi bài toán con đều có cùng kích thước
4. DBài toán có thể giải trong thời gian hằng số

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. ATìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ
2. BĐế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
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

Sắp xếp chèn chạy trong O(n) trên đầu vào đã sắp xếp. Điều này có mâu thuẫn với cận dưới Ω(n log n) cho sắp xếp dựa trên so sánh không?

1. ACó, nên cận dưới là sai
2. BCó, nhưng chỉ với mảng ngắn hơn 100
3. CKhông, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh
4. DKhông, cận dưới áp dụng cho trường hợp xấu nhất trên mọi đầu vào, không phải cho từng đầu vào