Câu hỏi: Cho ma trận kề A[n,n] biểu diễn đồ thị G vô hướng, n đỉnh, giá trị A[i,j] của ma trận kề xác định:

A. Có cạnh giữa đinh i và đỉnh j

B. Có cạnh giữa đinh j và đỉnh i

C. Không có cạnh giữa đinh i và đỉnh j

D. Không có cạnh giữa đinh i và đỉnh j

Câu 1: Số cạnh của cây với 1000 đỉnh là:

A. 9900

B. 9999

C. 10000

D. 1001

Câu 2: Với đồ thị n đỉnh, độ phức tạp tính toán của thuật toán Dijkstra là:

A. O(n3 log2n)

B. O(n3)

C. O(n2) 

D. O(n2 log2n) 

Câu 3: Sự khác nhau giữa thuật toán Prim và thuật toán Kruskal:

A. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, liên thuộc trong khi thuật toán Kruskal chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc.

B. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, liên thuộc với một đỉnh thuộc cây khung và không tạo thành chu trình. Thuật toán Kruskal chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc với các đỉnh đã thuộc cây khung và không tạo thành chu trình.

C. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc với các đỉnh đã thuộc cây và không tạo thành chu trình. Thuật toán Kruskal chọn các cạnh có trọng số tối thiểu, liên thuộc với các đỉnh đã thuộc cây và không tạo thành chu trình.

D. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, không liên thuộc với một đỉnh thuộc cây khung và không tạo thành chu trình. Thuật toán Kruskal chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc với các đỉnh đã thuộc cây khung và không tạo thành chu trình.

Câu 4: Hãy cho biết đồ thị nào dưới đây là một cây?

A.

B.

C.

D.

Câu 5: Trong biểu diễn đồ thị bởi danh sách kề, mỗi đỉnh của đồ thị có một danh sách:

A. Các cạnh kề với đỉnh đó

B. Các bậc của đỉnh kề với đỉnh đó

C. Các đỉnh kề với đỉnh đó

D. Các cạnh kề với cạnh đó

Câu 6: Nếu G = (V,E) là một đơn đồ thị vô hướng thì: (Chọn phương án đúng)

A. Ma trận kề gồm các phần tử đối xứng nhau qua đường chéo chính

B. Ma trận kề gồm các phần tử không đối xứng nhau qua đường chéo chính

C. Các phần tử trên đướng chéo chính bằng 1

D. Các phần tử trên đường chéo phụ bằng 1