Bài toán cây khung cực tiểu Quizz

Multiple Choice

Cây khung cực tiểu của một đồ thị liên thông có trọng số là gì?

• Cây có số cạnh lớn nhất

• Cây có số đỉnh bằng số cạnh

• Cây bao trùm tất cả các đỉnh và có tổng trọng số cạnh nhỏ nhất

• Chu trình có trọng số nhỏ nhất

Multiple Select

Khi áp dụng thuật toán Kruskal, những yếu tố nào sau đây là bắt buộc phải kiểm tra ở mỗi bước?

• Trọng số của cạnh

• Cạnh có tạo chu trình hay không

• Tổng bậc của đồ thị

• Cạnh có nối 2 đỉnh trong cùng thành phần hay không

Multiple Choice

Trong thuật toán Prim, ta chọn cạnh nào để thêm vào cây khung?

• Cạnh bất kỳ

• Cạnh có trọng số nhỏ nhất nối từ cây hiện tại đến đỉnh chưa xét

• Cạnh có trọng số lớn nhất

• Cạnh tạo chu trình

Multiple Choice

Số cạnh của cây khung cực tiểu trong đồ thị có n đỉnh là:

• n

• n−1

• Phụ thuộc số cạnh ban đầu

• n+1

Multiple Choice

Thuật toán Kruskal thường dùng cấu trúc dữ liệu nào để tránh tạo chu trình?

• Cây tìm kiếm nhị phân

• Union-Find (Disjoint Set Union - DSU)

• Danh sách kề

• Danh sách liên kết

Multiple Choice

Trong thuật toán Prim, nếu có 2 cạnh có trọng số bằng nhau cùng nối tới đỉnh chưa duyệt, ta nên chọn cạnh nào?

• Cạnh xuất phát từ đỉnh có tên đứng trước trong bảng chữ cái

• Cạnh bất kỳ vì kết quả không thay đổi

• Cạnh nối tới đỉnh có bậc cao hơn

• Cạnh nối tới đỉnh nằm gần gốc cây hơn

Multiple Choice

Trong cây khung cực tiểu, nếu loại bỏ 1 cạnh thì:

• Đồ thị không còn liên thông

• Vẫn là cây khung

• Tạo thêm chu trình

• Tăng số cạnh lên

Multiple Choice

Thuật toán nào xử lý tốt hơn với đồ thị thưa?

• DFS

• Prim

• BFS

• Kruskal

Multiple Choice

Thuật toán Prim bắt đầu từ đâu?

• Đỉnh có trọng số nhỏ nhất

• Cạnh có trọng số nhỏ nhất

• Đỉnh bất kỳ

• Đỉnh xa nhất trong đồ thị

Multiple Choice

Đồ thị có 8 đỉnh và 12 cạnh, liên thông. Số cạnh của cây khung cực tiểu là:

• 6

• 7

• 5

• 9

Multiple Choice

Khi áp dụng Kruskal, nếu hai đỉnh của cạnh đang xét thuộc cùng một tập hợp, ta sẽ:

• Không thêm cạnh đó vào cây

• Gộp hai tập lại

• Gán lại trọng số

• Đánh dấu là "chu trình chính"

Multiple Select

Chọn tất cả phát biểu đúng.

• Kruskal có thể áp dụng cho đồ thị không liên thông, thu được kết quả một rừng khung cực tiểu

• Nếu đồ thị có nhiều cạnh trọng số bằng nhau, cây khung cực tiểu có thể không duy nhất

• Prim không tạo được cây khung nếu đồ thị có chu trình

• Cây khung không bao giờ có chu trình

Multiple Choice

Bạn đang thiết kế hệ thống mạng LAN tiết kiệm chi phí. Mỗi dây nối có chi phí. Hãy chọn giải pháp phù hợp để nối tất cả các máy tính với chi phí thấp nhất:

• Tìm chu trình Hamilton

• Dùng thuật toán Dijkstra

• Dùng BFS

• Dùng cây khung cực tiểu

Multiple Select

Phát biểu nào sau đây đúng về sự khác nhau giữa Kruskal và Prim?

• Prim dùng hàng đợi ưu tiên, Kruskal dùng sắp xếp cạnh

• Kruskal có thể áp dụng cho đồ thị không liên thông để tìm rừng khung

• Prim không bao giờ tạo chu trình nếu dùng đúng

• Kruskal cần khởi tạo điểm gốc

Multiple Choice

Quan sát hình bên. Đâu là tập cạnh tạo thành cây khung cực tiểu?

• {AB, BD, DC, DE}

• {AB, AC, CE, DE}

• {AB, BC, CD, CE}

• {AB, BC, CD, CE, DE}