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 chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. AQuicksort
2. BSắp xếp nổi bọt
3. CSắp xếp trộn
4. DSắp xếp chèn

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AĐộ dài mảng phải là lũy thừa của hai
2. BMảng chỉ được chứa số dương
3. CMảng không được có quá 1000 phần tử
4. DMảng phải được sắp xếp

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

1. AThời gian trên loại máy tính phổ biến nhất
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 cho một đầu vào có độ dài trung bình
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

Độ phức tạp thời gian của Fibonacci đệ quy ngây thơ (fib(n) = fib(n−1) + fib(n−2)) là:

1. AHàm mũ
2. BLogarit
3. CTuyến tính
4. DHằng số

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

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

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(mn log n)
2. BO(mn)
3. CO(2^m+n)
4. DO(m + n)

Phát biểu nào về ký hiệu little-o là đúng?

1. An = o(n²), nhưng n không phải o(n)
2. Bn = o(n), vì mọi hàm đều là little-o của chính nó
3. Cn² = o(n)
4. D2n = o(n), vì 2n tăng chậm

Bài toán dừng cho thấy rằng:

1. AMột số chương trình chạy nhanh hơn trên máy tính nhanh hơn, nên việc dừng phụ thuộc vào phần cứng
2. BKhông thuật toán nào có thể quyết định, với mọi chương trình và đầu vào, liệu nó có dừng hay không
3. CMọi chương trình cuối cùng đều dừng
4. DNên tránh các vòng lặp