Bài Quiz không có tiêu đề

Trong tìm kiếm theo chiều rộng (BFS), cấu trúc dữ liệu nào được sử dụng để lưu trữ các đỉnh cần khám phá?

• Stack

• Queue

• Priority Queue

• List

Đâu là đặc điểm chính của thuật toán DFS?

• Luôn tìm đường đi ngắn nhất

• Khám phá tất cả các đỉnh cùng mức trước

• Dễ dẫn đến đi vào chu trình nếu không đánh dấu

• Sử dụng hàng đợi

Giả sử đồ thị có nn đỉnh và mm cạnh. Độ phức tạp thời gian của DFS/BFS là bao nhiêu?

• O(n^2)

• O(n+m)

• O(n.m)

• O(log n)

Với một đồ thị vô hướng liên thông, nếu thực hiện BFS từ một đỉnh, điều gì xảy ra?

• Chỉ thăm được một phần đồ thị

• Có thể bỏ sót chu trình

• Tất cả các đỉnh được thăm

• Không có kết quả chính xác

Một đồ thị vô hướng liên thông có chu trình Euler khi nào?

• Tất cả các đỉnh đều có bậc lẻ

• Có đúng 2 đỉnh bậc lẻ

• Tất cả các đỉnh có bậc chẵn

• Đồ thị có hướng

Trong đồ thị có hướng, điều kiện để tồn tại chu trình Euler là gì?

• Bậc vào = bậc ra với mọi đỉnh

• Có đúng 2 đỉnh có bậc vào ≠ bậc ra

• Có ít nhất một đỉnh cô lập

• Tồn tại ít nhất một chu trình

Thuật toán nào dùng để tìm chu trình Euler hiệu quả nhất?

• Prim

• Dijkstra

• Hierholzer

• Kruskal

Đồ thị Hamilton là gì?

• Đồ thị có chu trình đi qua tất cả các đỉnh đúng một lần và quay về đỉnh xuất phát

• Đồ thị có cạnh nối tất cả các cặp đỉnh

• Đồ thị có ít nhất một chu trình

• Đồ thị có chu trình đi qua mỗi cạnh đúng một lần

Phát biểu nào sau đây là đúng về bài toán Hamilton?

• Luôn có lời giải với mọi đồ thị đầy đủ

• Là bài toán P

• Là bài toán NP-complete

• Có thể giải bằng BFS

Điều nào là không đúng về đồ thị Hamilton?

• Không phải mọi đồ thị liên thông đều là Hamilton

• Đồ thị có chu trình Euler thì luôn có chu trình Hamilton

• Đồ thị đầy đủ với ≥3 đỉnh luôn là Hamilton

• Việc tìm chu trình Hamilton là khó về tính toán