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

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A8 giây
2. B4 giây
3. C1 giây
4. D2 giây

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

1. AO(n log n)
2. BO(n)
3. CO(1)
4. DO(log 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 sắp xếp
2. BMột mảng có độ dài 2
3. CMột mảng mà các phần tử đều khác nhau
4. DMột mảng có thứ tự ngẫu nhiên

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 500,000
2. BKhoảng 100
3. CKhoảng 20
4. DKhoảng 1,000

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

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. ALuôn chọn phần tử đầu tiên
2. BChỉ dùng đệ quy ở phía bên trái
3. CChọn pivot đồng đều ngẫu nhiên
4. DSắp xếp đầu vào trước khi chạy quicksort

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. CCác khóa phải được sắp xếp trước
4. DHàm băm chậm