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

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(E log V)
2. BO(V + E)
3. CO(V²)
4. DO(V × E)

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng n
2. BKhoảng n / 2
3. CKhoảng n²
4. DKhoảng log₂ n

Thuật toán sắp xếp nào chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp nổi bọt
2. BSắp xếp chèn
3. CQuicksort
4. DSắp xếp trộ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(m + n)
2. BO(mn)
3. CO(2^m+n)
4. DO(mn log n)

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. ASắp xếp trộn không có cấu trúc đệ quy
2. BQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
3. CSắp xếp trộn đã là O(n)
4. DCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

1. AO(n²)
2. BO(n log n)
3. CO(dn log k)
4. DO(d(n + k))

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

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

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

1. ACác bài toán không thể giải trong thời gian đa thức
2. BCác bài toán không phải đa thức
3. CCác bài toán mà không thuật toán nào giải được
4. DCá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ỉ