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

Đệ quy là gì?

1. AMột vòng lặp không bao giờ kết thúc
2. BMột loại cấu trúc dữ liệu
3. CMột hàm gọi chính nó trên các đầu vào nhỏ hơn
4. DMột phương pháp sắp xếp

Truy cập một phần tử theo chỉ số trong một mảng mất:

1. AO(1)
2. BO(log n)
3. CO(n²)
4. DO(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(V²)
2. BO(V + E)
3. CO(E log V)
4. DO(V × E)

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

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

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn là O(n log n) trong trường hợp xấu nhất
2. BSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
3. CCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
4. DSắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động ngắn nhất trước
2. BChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích
3. CChọn hoạt động bắt đầu sớm nhất
4. DChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích

Điều gì sẽ xảy ra nếu ai đó tìm được thuật toán thời gian đa thức cho một bài toán NP-đầy đủ?

1. AMọi thuật toán thời gian hàm mũ sẽ lập tức chạy trong thời gian tuyến tính
2. BBài toán dừng trở nên quyết định được
3. CMọi bài toán trong NP đều giải được trong thời gian đa thức, nên P = NP
4. DChỉ bài toán đó chuyển vào P

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

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