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 nhị phân trên một mảng đã sắp xếp là gì?

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

Hàm nào sau đây tăng chậm nhất khi n lớn dần?

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

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AMột cây khung nhỏ nhất trong O(E log V)
2. BĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)
3. CĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
4. DMột thứ tự tô-pô trong O(V²)

Với các đồng xu 1, 3 và 4 và số tiền 6, phương pháp tham lam "đồng lớn nhất trước" dùng bao nhiêu đồng, so với tối ưu?

1. ATham lam dùng 4 đồng; tối ưu là 3
2. BTham lam dùng 2 đồng; tối ưu là 2
3. CTham lam dùng 3 đồng; tối ưu là 3
4. DTham lam dùng 3 đồng; tối ưu là 2

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
2. BKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
3. CKhông, vì n³ nhỏ hơn n² khi n lớn
4. DĐúng, nhưng chỉ khi n nhỏ hơn 100

Vì sao tìm kiếm nhị phân không cho thời gian O(log n) trên một danh sách liên kết đơn?

1. AĐến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp
2. BCác phép so sánh trên nút danh sách liên kết chậm hơn
3. CTìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ
4. DDanh sách liên kết không thể được sắp xếp

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AThuật toán Prim bắt đầu từ một nút
2. BThuật toán Dijkstra
3. CThuật toán Kruskal
4. DFloyd–Warshall