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

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. A9 giây
2. B3 giây
3. C12 giây
4. D6 giây

Trường hợp cơ sở của một hàm đệ quy là gì?

1. ALời gọi dùng nhiều bộ nhớ nhất
2. BDòng đầu tiên của hàm
3. CTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy
4. DTrường hợp được trả lời trực tiếp mà không thực hiện thêm lời gọi đệ quy nào

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. AQuicksort
2. BSắp xếp trộn
3. CSắp xếp nổi bọt
4. DSắp xếp vun đống

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng có thứ tự ngẫu nhiên
2. BMột mảng có độ dài 2
3. CMột mảng đã được sắp xếp
4. DMột mảng mà các phần tử đều khác nhau

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

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

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 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
3. CQuickselect 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
4. DViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp

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