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

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. CΘ (Big Theta)
4. DO (Big O)

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

1. AThờ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
2. BThời gian trên loại máy tính phổ biến nhất
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

log₂ 1024 bằng bao nhiêu?

1. A10
2. B12
3. C32
4. D512

Độ 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)

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

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

1. ANó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
2. BNó 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
3. CNó xóa cạnh đắt nhất cho đến khi không còn chu trình
4. DNó 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

Định nghĩa nào của lớp NP là đúng?

1. ACác bài toán mà không thuật toán nào giải được
2. BCác bài toán quyết định có câu trả lời "có" kiểm chứng được trong thời gian đa thức khi cho một chứng chỉ
3. CCác bài toán không phải đa thức
4. DCác bài toán không thể giải trong thời gian đa thức

Cận nào là đúng cho log(n!)?

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