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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AVét cạn
2. BChia để trị
3. CQuy hoạch động
4. DLựa chọn tham lam

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 đầu vào nhỏ nhất
3. CThời gian nó mất trên một máy tính chậm
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

Ký hiệu nào mô tả cận dưới của tốc độ tăng?

1. AΘ (Big Theta)
2. BΩ (Big Omega)
3. CO (Big O)
4. Do (little o)

Độ phức tạp thời gian của: for i = 1 to n: for j = 1 to i: thực hiện công việc O(1) là gì?

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

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

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

Phát biểu nào về một hàm đệ quy không có trường hợp cơ sở nào đạt tới được là đúng?

1. ANó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
2. BNó tự động trả về 0
3. CTrình biên dịch luôn biến nó thành một vòng lặp kết thúc an toàn
4. DNó chạy trong thời gian O(1)

Một bài toán là NP-đầy đủ nếu nó:

1. AKhông thể giải được
2. BGiải được trong thời gian đa thức
3. CThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức
4. DNằm ngoài NP nhưng khó hơn mọi bài toán NP, chẳng hạn bài toán dừng

Thuật toán quy hoạch động Held–Karp giải chính xác bài toán người bán hàng rong. Thời gian chạy của nó cho n thành phố là bao nhiêu?

1. AO(2^n²)
2. BO(n² 2ⁿ)
3. CO(n³)
4. DO(n!)