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

log₂ 1024 bằng bao nhiêu?

1. A10
2. B512
3. C12
4. D32

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

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

1. ANó chia mảng làm đôi rồi trộn lại
2. BNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
3. CNó 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
4. DNó 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

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
2. BNó xóa cạnh đắt nhất cho đến khi không còn chu trình
3. CNó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng
4. DNó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây

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

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

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

Để chứng minh một bài toán mới X là NP-khó, bạn phải làm gì?

1. AChứng minh X kiểm chứng được trong thời gian đa thức
2. BChứng minh X không có thuật toán đa thức cho đầu vào nhỏ
3. CQuy dẫn một bài toán NP-khó đã biết về X trong thời gian đa thức
4. DQuy dẫn X về một bài toán NP-khó đã biết trong thời gian đa thức

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

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