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

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

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

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. ABậc hai
2. BHằng số
3. CLogarit
4. DTuyến tính

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

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

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ó chạy trong thời gian O(1)
2. BTrì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
3. CNó tự động trả về 0
4. DNó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó xóa cạnh đắt nhất cho đến khi không còn chu trình
2. BNó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây
3. CNó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
4. DNó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng

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

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

Bài toán thỏa mãn nào sau đây được biết là giải được trong thời gian đa thức?

1. A2-SAT, trong đó mỗi mệnh đề có tối đa hai literal
2. BThỏa mãn mạch
3. CSAT tổng quát trên các công thức dạng chuẩn tắc hội
4. D3-SAT, trong đó mỗi mệnh đề có đúng ba literal

Dùng định lý chủ, T(n) = 8T(n/2) + O(n²) có nghiệm là:

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