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

Thuật toán là gì?

1. AMột ngôn ngữ lập trình được thiết kế để viết các công thức toán học
2. BBất kỳ chương trình máy tính nào có giao diện đồ họa
3. CMột dãy hữu hạn các bước được xác định rõ để giải một bài toán
4. DMột cấu trúc dữ liệu lưu trữ các số

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(V²)
2. BO(V + E)
3. CO(V × E)
4. DO(E log V)

Big O của 3n² + 5n + 2 là gì?

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

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

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

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ó thể giải trong thời gian hằng số
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ó đú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 đó

Công thức truy hồi T(n) = 2T(n − 1) + O(1) có nghiệm là gì?

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

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. CCác phép so sánh trên nút danh sách liên kết chậm hơn
4. DDanh sách liên kết không thể được sắp xếp

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. AKhô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
2. BCó, nhưng chỉ với mảng ngắn hơn 100
3. CCó, nên cận dưới là sai
4. DKhông, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh