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

Sắp xếp chọn hoạt động như thế nào?

1. ANó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyển
2. BNó chia mảng làm đôi rồi trộn lại
3. CNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu
4. DNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự

Thuật toán là gì?

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

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

1. AO(log n)
2. BO(n²)
3. CO(2n)
4. DO(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 log n)
2. BΩ(log n)
3. CΩ(n)
4. DΩ(n²)

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

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

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. ABắt buộc phải dùng Bellman–Ford trong mọi trường hợp
2. BThuật toán Dijkstra
3. CTìm kiếm theo chiều sâu
4. DThuật toán Kruskal

Với biến thể bài toán cái túi nào thì quy tắc tham lam "lấy các món theo thứ tự giá trị trên cân nặng" luôn cho đáp án tối ưu?

1. ABài toán cái túi 0/1, trong đó các món luôn phải được lấy nguyên
2. BCả hai biến thể
3. CCái túi phân số, trong đó các món có thể bị chia nhỏ
4. DKhông biến thể nào

Cận nào là đúng cho log(n!)?

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