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. ASố dòng mã
2. BKích thước vật lý của máy tính
3. CDung lượng đĩa của tệp chương trình sau khi được biên dịch
4. DLượng bộ nhớ một thuật toán cần khi đầu vào tăng

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 chèn
2. BSắp xếp nổi bọt
3. CSắp xếp trộn
4. DQuicksort

Một thuật toán O(n) mất 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A6 giây
2. B9 giây
3. C3 giây
4. D12 giây

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp chọn (phiên bản điển hình)
2. BSắp xếp vun đống
3. CQuicksort (phiên bản tại chỗ điển hình)
4. DSắp xếp trộn

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. ACây khung nhỏ nhất
2. BThứ tự tô-pô trong mọi đồ thị
3. CĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát
4. DĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm

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

1. AO(n)
2. BO(2ⁿ)
3. CO(n²)
4. DO(n log 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ả hai biến thể
2. BCái túi phân số, trong đó các món có thể bị chia nhỏ
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

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³)
4. DΘ(n² log n)