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

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. ASắp xếp trộn
2. BSắp xếp vun đống
3. CQuicksort
4. DSắp xếp nổi bọt

Một thuật toán O(n) mất 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A12 giây
2. B9 giây
3. C6 giây
4. D3 giây

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

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

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

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

1. AO(n)
2. BO(log n)
3. CO(n²)
4. DO(n 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 tính theo số cạnh từ nút xuất phát
2. BThứ tự tô-pô trong mọi đồ thị
3. CCây khung nhỏ nhất
4. DĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm

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

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

Phát biểu nào về việc chọn phần tử nhỏ thứ k của một mảng chưa sắp xếp là đúng?

1. AViệc chọn chỉ có thể thực hiện trong O(n²)
2. BQuickselect chạy trong O(log n) ở trường hợp xấu nhất, vì nó chỉ đệ quy một phía của phần tử chốt
3. CQuickselect chạy trong thời gian kỳ vọng O(n), và trung vị của các trung vị đảm bảo O(n) trong trường hợp xấu nhất
4. DViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp