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 trung bình mô tả điều gì?

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

Sắp xếp chọn hoạt động như thế nào?

1. ANó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyển
2. BNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
3. CNó chia mảng làm đôi rồi trộn lại
4. DNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu

Độ phức tạp không gian đo lường:

1. ASố dòng mã
2. BDung lượng đĩa của tệp chương trình sau khi được biên dịch
3. CKích thước vật lý của máy tính
4. DLượng bộ nhớ một thuật toán cần khi đầu vào tăng

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AĐúng, nhưng chỉ khi n nhỏ hơn 100
2. BĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
3. CKhông, vì n³ nhỏ hơn n² khi n lớn
4. DKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. AMọi bài toán con đều có cùng kích thước
2. BBài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó
3. CBài toán có thể giải trong thời gian hằng số
4. DMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Phép nhân Karatsuba thỏa mãn T(n) = 3T(n/2) + O(n). Nghiệm của nó là gì?

1. AΘ(n^{log₂ 3}), khoảng n^1,585
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n log n)

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

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