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

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

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

Độ 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(E log V)
2. BO(V²)
3. CO(V + E)
4. DO(V × E)

Độ phức tạp thời gian của tìm kiếm tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

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

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

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

Độ 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(log n)
4. DO(1)

Định nghĩa nào của lớp NP là đúng?

1. ACác bài toán quyết định có câu trả lời "có" kiểm chứng được trong thời gian đa thức khi cho một chứng chỉ
2. BCác bài toán mà không thuật toán nào giải được
3. CCác bài toán không thể giải trong thời gian đa thức
4. DCác bài toán không phải đa thức

Vì sao tra cứu trung bình trong bảng băm là O(1) nhưng trường hợp xấu nhất là O(n)?

1. AHàm băm chậm
2. BMảng có truy cập O(n)
3. CCác khóa phải được sắp xếp trước
4. DNhiều khóa có thể va chạm vào cùng một ngăn