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

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian tối đa nó mất trên mọi đầu vào kích thước n
2. BThời gian nó mất trên một máy tính chậm
3. CThời gian nó mất trên đầu vào nhỏ nhất
4. DThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. ANó xử lý đúng một phần tử mỗi giây thời gian chạy
2. BNó chỉ có thể chạy một lần
3. CThời gian chạy của nó không tăng theo kích thước đầu vào
4. DNó luôn mất đúng một giây

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

1. AO(n)
2. BO(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(2^m+n)
2. BO(mn log n)
3. CO(mn)
4. DO(m + n)

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 + k)
3. CO(n log n + k log n)
4. DO(nk)

Định lý Cook–Levin đã thiết lập điều gì?

1. ABài toán dừng là bất khả quyết định
2. BMọi bài toán NP đều giải được trong thời gian hàm mũ
3. CBài toán thỏa mãn Boole (SAT) là NP-đầy đủ
4. DP không bằng NP

Với biến thể bài toán cái túi nào thì quy tắc tham lam "lấy các món theo thứ tự giá trị trên cân nặng" luôn cho đáp án tối ưu?

1. ACái túi phân số, trong đó các món có thể bị chia nhỏ
2. BBài toán cái túi 0/1, trong đó các món luôn phải được lấy nguyên
3. CCả hai biến thể
4. DKhông biến thể nào