Câu hỏi: 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 1: Để xây dựng cây khung nhỏ nhất của đồ thị, ta dùng: (Chọn phương án đúng)
A. Thuật toán Dijsktra.
B. Tìm kiếm theo chiều rộng (BFS).
C. Tìm kiếm theo chiều sâu (DFS).
D. Thuật toán Prim.
30/08/2021 1 Lượt xem
30/08/2021 2 Lượt xem
Câu 3: Đồ thị vô hướng G = (V,E) được gọi là liên thông nếu.
A. Giữa hai đỉnh bất kỳ \(u,v \in V\) luôn tồn tại đường đi từ u đến v.
B. Nếu \(u,v \in V\) , thì tồn tại v khác u sao cho v liên thông với u.
C. Nếu \(u,v \in V\) , thì với mọi v khác u đều kề với u.
D. Nếu \(u,v \in V\) , thì tồn tại đỉnh v khác u kề với u.
30/08/2021 2 Lượt xem
Câu 4: 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
30/08/2021 1 Lượt xem
Câu 5: Sự giống nhau giữa thuật toán Prim và thuật toán Kruskal là:
A. Dừng khi kết nạp được tất cả các cạnh vào cây khung.
B. Dừng khi kết nạp được n đỉnh và n cạnh vào cây khung
C. Thuật toán 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 khung và không tạo ra chu trình.
D. Thuật toán xây dựng cây khung ngắn nhất.
30/08/2021 1 Lượt xem
Câu 6: 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
30/08/2021 1 Lượt xem
Câu hỏi trong đề: Bộ câu hỏi trắc nghiệm môn Toán rời rạc - Phần 14
- 38 Lượt thi
- 60 Phút
- 30 Câu hỏi
- Sinh viên
Cùng chủ đề Bộ câu hỏi trắc nghiệm môn Toán rời rạc có đáp án
- 2.6K
- 206
- 30
-
50 người đang thi
- 967
- 72
- 30
-
15 người đang thi
- 1.0K
- 47
- 30
-
48 người đang thi
- 666
- 33
- 30
-
69 người đang thi
Chia sẻ:
Đăng Nhập để viết bình luận