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

Trường hợp cơ sở của một hàm đệ quy là gì?

1. ATrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy
2. BLời gọi dùng nhiều bộ nhớ nhất
3. CDòng đầu tiên của hàm
4. DTrường hợp được trả lời trực tiếp mà không thực hiện thêm lời gọi đệ quy nà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 cho một đầu vào có độ dài trung bình
3. CThời gian trên loại máy tính phổ biến nhất
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

Tốc độ tăng O(2ⁿ) được gọi là gì?

1. ATuyến tính
2. BĐa thức
3. CHàm mũ
4. DLogarit

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. AThuật toán Dijkstra
2. BTìm kiếm theo chiều sâu
3. CThuật toán Kruskal
4. DBắt buộc phải dùng Bellman–Ford trong mọi trường hợp

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

Một thuật toán tham lam:

1. AThử mọi lời giải có thể
2. BĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước
3. CChỉ dùng đệ quy
4. DLuôn cho lời giải tối ưu

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

1. AΘ(n²)
2. BΘ(n^{log₂ 7}), khoảng n^2,81
3. CΘ(n² log n)
4. DΘ(n³)

Với biến thể bài toán cái túi nào thì quy tắc tham lam "lấy các món theo thứ tự giá trị trên cân nặng" luôn cho đáp án tối ưu?

1. ACái túi phân số, trong đó các món có thể bị chia nhỏ
2. BCả hai biến thể
3. CKhông biến thể nào
4. DBài toán cái túi 0/1, trong đó các món luôn phải được lấy nguyên