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

Ba bước của một thuật toán chia để trị là gì?

1. AChia, trị, kết hợp
2. BĐoán, kiểm tra, lặp lại
3. CĐọc, tính toán, ghi
4. DSắp xếp, tìm kiếm, trả về

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

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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AChia để trị
2. BVét cạn
3. CQuy hoạch động
4. DLựa chọn tham lam

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

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

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

1. AKhoảng √n
2. BKhoảng n / 2
3. CKhoảng log₂ n
4. DKhoảng n

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. AChỉ dùng đệ quy ở phía bên trái
2. BChọn pivot đồng đều ngẫu nhiên
3. CSắp xếp đầu vào trước khi chạy quicksort
4. DLuôn chọn phần tử đầu tiên

Thuật toán quy hoạch động Held–Karp giải chính xác bài toán người bán hàng rong. Thời gian chạy của nó cho n thành phố là bao nhiêu?

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