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. AVét cạn
2. BQuy hoạch động
3. CChia để trị
4. DLựa chọn tham lam

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)

Thời gian chạy trong trường hợp trung bình mô tả điều gì?

1. AThời gian cho một đầu vào có độ dài trung bình
2. BThời gian kỳ vọng trên một phân phối cho trước của các đầu vào kích thước n
3. CThời gian trên loại máy tính phổ biến nhất
4. DGiá trị ở giữa thời gian chạy trường hợp tốt nhất và trường hợp xấu nhất

Đệ 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 log₂ n
3. CKhoảng n
4. DKhoảng n / 2

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

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

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm
2. BCây khung nhỏ nhất
3. CThứ tự tô-pô trong mọi đồ thị
4. DĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(2ⁿ) và không gian O(1)
2. BThời gian O(n) và không gian O(1)
3. CThời gian O(n) và không gian O(n)
4. DThời gian O(log n) và không gian O(n)

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. ANhiều khóa có thể va chạm vào cùng một ngăn
2. BMảng có truy cập O(n)
3. CHàm băm chậm
4. DCác khóa phải được sắp xếp trước