Câu hỏi: Cho đồ thị vô hướng G = (V,E), khẳng định nào dưới đây là đúng?

A. Thuật toán BFS(u) duyệt tất cả các thành phần liên thông của đồ thị

B. Thuật toán BFS(u) luôn tìm ra được đường đi giữa hai đỉnh bất kì của đồ thị

C. Thuật toán BFS(u) duyệt tất cả các đỉnh của đồ thị trong cùng thành phần liên thông với đỉnh u

D. Thuật toán BFS(u) duyệt tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần

Câu 1: Đồ thị có đường đi vô hướng Euler khi và chỉ khi:

A. Liên thông và có hai đỉnh bậc lẻ.

B. Không liên thông và có hai đỉnh bậc lẻ.

C. Liên thông và có một đỉnh bậc lẻ.

D. Không liên thông và không có đỉnh bậc lẻ.

Câu 2: Trong biểu diễn đồ thị bằng danh sách kề, mỗi danh sách kề chứa:

A. Các cạnh kề với một đỉnh.

B. Các đỉnh kề với một đỉnh.

C. Tất cả các đỉnh kề và cạnh kề với nó.

D. Các bậc của đỉnh kề với một đỉnh.

Câu 3: Tổng tất cả các bậc trong một đồ thị vô hướng bằng:

A. Hai lần số cạnh.

B. Hai lần số đỉnh.

C. Trung bình  cộng của số đỉnh và số cạnh. 

D. Tổng của số đỉnh và số cạnh.

Câu 4: Độ phức tạp của thật toán Floyd là:

A. O(n3 log2n)

B. O(n2)

C. O(n3)

D. O(n2 log2n) 

Câu 5: Có 12 học viên trong một lớp. Có bao nhiêu cách để 12 học viên có 3 bài kiểm tra khác nhau nếu 4 học viên có chung mỗi bài kiểm tra?

A. 34650

B. 220

C. 3465

D. 650

Câu 6: Đồ thị dưới dạng ma trận kề:

A. Euler

B. Hamilton  và Euler 

C. Hamilton 

D. Không  liên  thông