Cấu trúc dữ liệu và giải thuật: gói ôn nước rút

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

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

Độ phức tạp thời gian của việc xây dựng một đống nhị phân từ n phần tử chưa sắp xếp bằng phương pháp từ dưới lên là gì?

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

Trong bảng băm dùng địa chỉ mở, hệ số tải tối đa có thể là bao nhiêu?

1. A0,5
2. B2
3. CKhông có mức tối đa
4. D1

Bạn phải giữ k giá trị nhỏ nhất từ một luồng n số bằng bộ nhớ O(k). Cách nào chạy trong thời gian O(n log k)?

1. AMột hàng đợi FIFO gồm k giá trị cuối
2. BMột đống min chứa tất cả n giá trị, từ đó k giá trị nhỏ nhất được lấy ra ở cuối
3. CMột mảng đã sắp xếp chứa tất cả n giá trị
4. DMột đống max kích thước k, thay gốc của nó khi có giá trị nhỏ hơn đến

Một cây có 4 đỉnh bậc 3, 4 đỉnh bậc 4, 4 đỉnh bậc 5, 3 đỉnh bậc 2, và mọi đỉnh khác của nó đều là lá (bậc 1). Nó có bao nhiêu lá L?

Thuật toán Kruskal xây dựng một cây khung nhỏ nhất. Hãy nhấp vào cạnh mà nó thêm vào là cạnh số 2; các cạnh bị bỏ qua không được tính.

1. 1cạnh AB
2. 2cạnh AC
3. 3cạnh BC
4. 4cạnh BD
5. 5cạnh DE
6. 6cạnh EF
7. 7cạnh GB
8. 8cạnh GD
9. 9cạnh GE