Trong thuật toán Kruskal để tìm cây khung nhỏ nhất, bước quan trọng nhất là gì?

• A. Chọn cạnh có trọng số lớn nhất mà không tạo thành chu trình.
• B. Chọn cạnh có trọng số nhỏ nhất mà không tạo thành chu trình.
• C. Chọn cạnh ngẫu nhiên.
• D. Chọn cạnh đầu tiên trong danh sách.

Sự khác biệt chính giữa thuật toán Prim và Kruskal là gì?

• A. Prim bắt đầu từ một đỉnh, Kruskal bắt đầu từ một cạnh.
• B. Prim bắt đầu từ một cạnh, Kruskal bắt đầu từ một đỉnh.
• C. Prim sử dụng hàng đợi ưu tiên, Kruskal sử dụng ngăn xếp.
• D. Prim luôn tìm ra cây khung nhỏ nhất, Kruskal thì không.

Điều kiện nào sau đây là cần thiết để một đồ thị có đường đi Euler?

• A. Tất cả các đỉnh phải có bậc chẵn.
• B. Có đúng hai đỉnh có bậc lẻ.
• C. Đồ thị phải liên thông.
• D. Cả B và C.

Thuật toán Edmonds-Karp cải thiện thuật toán Ford-Fulkerson như thế nào?

• A. Luôn tìm thấy luồng cực đại nhanh hơn.
• B. Đảm bảo thuật toán luôn kết thúc.
• C. Có thể xử lý đồ thị có trọng số âm.
• D. Đơn giản hóa việc triển khai.

Thuật toán Dijkstra được sử dụng để giải quyết vấn đề nào?

• A. Tìm kiếm tuyến tính trong một mảng.
• B. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong một đồ thị có trọng số không âm.
• C. Sắp xếp một mảng theo thứ tự giảm dần.
• D. Tìm kiếm nhị phân trong một mảng đã được sắp xếp.

Trong thuật toán Bellman-Ford, điều gì xảy ra nếu sau V-1 vòng lặp, khoảng cách đến một đỉnh vẫn còn giảm?

• A. Đồ thị không có đường đi.
• B. Đồ thị chứa chu trình âm.
• C. Thuật toán đã hoàn thành.
• D. Có lỗi trong thuật toán.

Trong thuật toán Ford-Fulkerson, mục tiêu chính là gì?

• A. Tìm đường đi ngắn nhất.
• B. Tìm luồng cực đại trong mạng.
• C. Tìm cây khung nhỏ nhất.
• D. Sắp xếp các đỉnh theo thứ tự tô pô.

Thuật toán Prim bắt đầu từ một đỉnh tùy ý và liên tục thêm các cạnh có trọng số nhỏ nhất để mở rộng cây. Điều này đúng hay sai?

• A. Đúng
• B. Sai
• C. Chỉ đúng với đồ thị có trọng số dương
• D. Chỉ đúng với đồ thị vô hướng

Ứng dụng thực tế của sắp xếp tô pô là gì?

• A. Tìm đường đi ngắn nhất trong bản đồ.
• B. Lập lịch các công việc phụ thuộc.
• C. Tìm cây khung nhỏ nhất cho mạng lưới điện.
• D. Sắp xếp các số theo thứ tự tăng dần.

Trong bài toán ghép cặp cực đại (maximum matching), mục tiêu là gì?

• A. Tìm đường đi ngắn nhất giữa hai tập hợp.
• B. Tìm số lượng cạnh lớn nhất mà không có hai cạnh nào có chung đỉnh.
• C. Tìm cây khung nhỏ nhất.
• D. Sắp xếp các đỉnh theo thứ tự.

Định lý luồng cực đại - lát cắt cực tiểu phát biểu điều gì?

• A. Luồng cực đại bằng trọng số cạnh lớn nhất trong đồ thị.
• B. Luồng cực đại bằng dung lượng của lát cắt cực tiểu.
• C. Luồng cực đại bằng tổng dung lượng của tất cả các cạnh.
• D. Luồng cực đại bằng số lượng đỉnh trong đồ thị.

Trong thuật toán sắp xếp trộn (merge sort), độ phức tạp thời gian tốt nhất là gì?

• A. O(n^2)
• B. O(n log n)
• C. O(log n)
• D. O(n)

Trong một mạng luồng, một 'đường tăng' là gì?

• A. Đường đi ngắn nhất từ nguồn đến đích.
• B. Đường đi từ nguồn đến đích có thể tăng luồng.
• C. Đường đi dài nhất từ nguồn đến đích.
• D. Đường đi từ đích đến nguồn.

Cho một đồ thị có hướng, thuật toán nào được sử dụng để phát hiện chu trình?

• A. Thuật toán Dijkstra
• B. Thuật toán Prim
• C. Tìm kiếm theo chiều sâu (DFS)
• D. Tìm kiếm theo chiều rộng (BFS)

Ứng dụng thực tế của bài toán ghép cặp cực đại là gì?

• A. Tìm đường đi ngắn nhất.
• B. Gán công việc cho nhân viên.
• C. Tìm cây khung nhỏ nhất.
• D. Sắp xếp các số.

Thuật toán Bellman-Ford giải quyết vấn đề đường đi ngắn nhất nào?

• A. Đường đi ngắn nhất giữa tất cả các cặp đỉnh.
• B. Đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác, ngay cả khi có trọng số âm.
• C. Đường đi ngắn nhất trong đồ thị không trọng số.
• D. Đường đi ngắn nhất trong đồ thị có hướng không chu trình.

Ứng dụng nào sau đây KHÔNG phải là ứng dụng của cây khung nhỏ nhất?

• A. Thiết kế mạng lưới điện.
• B. Tìm đường đi ngắn nhất giữa hai thành phố.
• C. Xây dựng mạng lưới đường bộ.
• D. Phân cụm dữ liệu.

Điều gì xảy ra khi thuật toán Ford-Fulkerson không tìm thấy đường tăng nào?

• A. Đã tìm thấy luồng cực tiểu.
• B. Đã tìm thấy luồng cực đại.
• C. Mạng không có luồng.
• D. Có chu trình âm trong mạng.

Trong bài toán luồng cực đại, 'lát cắt' là gì?

• A. Một đường đi từ nguồn đến đích.
• B. Một tập hợp các cạnh chia đồ thị thành hai phần, một chứa nguồn và một chứa đích.
• C. Một tập hợp các đỉnh trong đồ thị.
• D. Một chu trình trong đồ thị.

Thuật toán Hungarian được sử dụng để giải quyết bài toán nào?

• A. Tìm đường đi ngắn nhất.
• B. Tìm ghép cặp cực đại trong đồ thị hai phía.
• C. Tìm cây khung nhỏ nhất.
• D. Sắp xếp các đỉnh theo thứ tự.

Nếu tất cả các cạnh trong đồ thị có trọng số bằng nhau, thuật toán nào sẽ hiệu quả nhất để tìm cây khung nhỏ nhất?

• A. Thuật toán Dijkstra
• B. Thuật toán Prim
• C. Tìm kiếm theo chiều rộng (BFS)
• D. Thuật toán Kruskal

Độ phức tạp thời gian của thuật toán tìm kiếm theo chiều rộng (BFS) trong đồ thị được biểu diễn bằng danh sách kề là bao nhiêu, với V là số đỉnh và E là số cạnh?

• A. O(V)
• B. O(E)
• C. O(V + E)
• D. O(V * E)

Điều kiện nào sau đây phải đúng để thuật toán Dijkstra hoạt động chính xác?

• A. Đồ thị phải có hướng.
• B. Đồ thị phải không có chu trình.
• C. Tất cả các trọng số cạnh phải không âm.
• D. Đồ thị phải là đồ thị đầy đủ.

Trong thuật toán Edmonds-Karp, đường tăng được chọn như thế nào?

• A. Đường tăng có dung lượng lớn nhất.
• B. Đường tăng ngắn nhất (ít cạnh nhất).
• C. Đường tăng được chọn ngẫu nhiên.
• D. Đường tăng dài nhất.

Thuật toán sắp xếp tô pô được sử dụng cho loại đồ thị nào?

• A. Đồ thị vô hướng.
• B. Đồ thị có hướng không chu trình (DAG).
• C. Đồ thị đầy đủ.
• D. Đồ thị có trọng số âm.

Ứng dụng thực tế của bài toán luồng cực đại là gì?

• A. Tìm đường đi ngắn nhất trong bản đồ.
• B. Lập lịch thi đấu thể thao.
• C. Tìm cây khung nhỏ nhất.
• D. Sắp xếp các số theo thứ tự tăng dần.

Độ phức tạp thời gian của thuật toán Floyd-Warshall là bao nhiêu, với V là số đỉnh?

• A. O(V)
• B. O(V^2)
• C. O(V^3)
• D. O(V log V)

Cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị liên thông, vô hướng, có trọng số là gì?

• A. Một cây chứa tất cả các đỉnh của đồ thị với tổng trọng số cạnh là lớn nhất.
• B. Một cây chứa tất cả các đỉnh của đồ thị với tổng trọng số cạnh là nhỏ nhất.
• C. Một đồ thị con không chứa chu trình.
• D. Một đồ thị con chứa tất cả các cạnh của đồ thị gốc.

Cấu trúc dữ liệu nào thường được sử dụng để triển khai thuật toán tìm kiếm theo chiều sâu (DFS)?

• A. Hàng đợi (Queue)
• B. Ngăn xếp (Stack)
• C. Danh sách liên kết (Linked List)
• D. Cây nhị phân tìm kiếm (Binary Search Tree)

Thuật toán Floyd-Warshall được sử dụng để giải quyết vấn đề nào?

• A. Tìm cây khung nhỏ nhất.
• B. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị có trọng số.
• C. Sắp xếp tô pô một đồ thị.
• D. Tìm luồng cực đại trong mạng.