Trắc nghiệm toán rời rạc-chuơng 3

Chia sẻ: Anh Hoàng | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

528
lượt xem 70
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'trắc nghiệm toán rời rạc-chuơng 3', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Trắc nghiệm toán rời rạc-chuơng 3

Chương 3. Chương 3: Hiểu. Câu 1 Nếu G = (V,E) là một đồ thị vô hướng thì A) Số đỉnh bậc lẻ và số đỉnh bậc chẵn là một số chẵn B) Số đỉnh bậc chẵn là một số chẵn C) Số đỉnh bậc lẻ là một số chẵn D) Số đỉnh bậc lẻ là một số lẻ Đáp án C Câu 2 Những đơn đồ thị vô hướng nào dưới đây tồn tại nếu bậc của các đỉnh lần lượt là A) 1, 4, 3, 2, 5, 6. B) 2, 1, 5, 2, 3, 3. C) 2, 4, 3, 4, 3, 2. D) 1, 4, 3, 2, 2, 3. Đáp án C Câu 3 Đơn đồ thị vô hướng nào dưới đây tồn tại nếu bậc của các đỉnh lần lượt là A) 1, 2, 3, 4, 5. B) 0, 1, 2, 2, 3. C) 3, 4, 3, 4, 3. D) 1, 2, 3, 4, 7. Đáp án B Câu 4 Đồ thị liên thông nào trong các đồ thị dưới đây là đồ thị Euler nếu số bậc của các đỉnh lần lượt là A) 4, 2, 1, 4, 4 B) 2, 4, 2, 4, 2 C) 4, 2, 1, 3, 4 D) 5, 2, 4, 4, 4 Đáp án B Câu 5 Đồ thị liên thông nào trong các đồ thị dưới đây là đồ thị nửa Euler nếu số bậc của các đỉnh lần lượt là A) 2, 4, 1, 2, 6 B) 3, 4, 4, 2, 4 C) 1, 4, 2, 5, 2 D) 4, 4, 6, 5, 3 Đáp án C Câu 6 Trong cách biểu diễn đồ thị bằng danh sách cạnh chúng ta lưu trữ A) Danh sách tất cả các cạnh. B) Danh sách tất cả các đỉnh. C) Danh sách tất cả các cạnh và các đỉnh. D) Không lưu trữ danh sách cạnh và đỉnh nào. Đáp án A Câu 7 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ản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
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. Đáp án B Câu 8 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. Đáp án A Câu 9 Nếu bậc của mỗi đỉnh trong đồ thị đều chẵn thì A) Đồ thị là liên thông. B) Đồ thị không liên thông. C) Tính liên thông của đồ thị không xác định. D) Đồ thị là liên thông mạnh Đáp án C Câu 10 Đồ thị dưới dạng ma trận kề:  0 1 1 0 0  1 0 0 1 1    1 0 0 1 0   0  1 1 0 1  0  1 0 1 0  Là đồ thị A) Euler B) Hamilton và Euler C) Hamilton D) không liên thông Đáp án C Câu 11 Đồ thị dưới dạng ma trận kề:  0 1 1 1 0  1 0 0 1 1    1 0 0 1 0   1  1 1 0 1  0  1 0 1 0  Là đồ thị A) nửa Euler B) Euler C) không liên thông D) Hamilton và Euler Đáp án A Câu 12 Cho đồ thị được biểu diễn bởi ma trận kề sau đây Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
 0 0 0 1 1  0 0 1 1 1    0 1 0 0 1   1  1 0 0 0  1  1 1 0 0  Danh sách các đỉnh nào dưới đây tạo nên đường đi trong đồ thị A) 1, 3, 5, 2, 4 B) 1, 5, 3, 2, 4 C) 3, 4, 2, 5, 1 D) 3, 1, 5, 2, 4 Đáp án B Câu 13 Cho đồ thị được biểu diễn bởi ma trận kề sau đây  0 0 0 1 1  0 0 1 1 1    0 1 0 0 1   1  1 0 0 0  1  1 1 0 0  Danh sách các đỉnh nào dưới đây tạo nên chu trình trong đồ thị A) 1, 4, 5, 3, 2, 1 B) 1, 5, 4, 2, 3, 1 C) 1, 4, 2, 3, 5, 1 D) 1, 3, 5, 2, 4, 1 Đáp án C Câu 14 Cho đồ thị vô hướng G = (V,E), khẳng định nào sau đây là đúng? A) Thuật toán DFS(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 B) Thuật toán DFS(u) luôn tìm ra được đường đi giữa hai đỉnh bất kì của đồ thị C) Thuật toán DFS(u) duyệt tất cả các thành phần liên thông của đồ thị D) Thuật toán DFS(u) duyệt tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần Đáp án A Câu 15 Cho đồ thị vô hướng G = (V,E), khẳng định nào sau đâ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 Đáp án C Câu 16 Đồ thị K4 có số đỉnh và số cạnh tương ứng là A) 4,6 B) 4,8 C) 5,8 Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
D) 4,4 Đáp án A Câu 17 Phát biểu nào sau đây là sai khi nói đến đồ thị phân đôi đầy đủ K m,n A) có tập đỉnh được phân thành hai tập con tương ứng có m đỉnh và n đỉnh. B) có một cạnh giữa hai đỉnh nếu và chỉ nếu một đỉnh thuộc tập con này và đỉnh thứ hai thuộc tập con kia. C) có một cạnh giữa hai đỉnh nếu và chỉ nếu mỗi đỉnh đều thuộc vào hai tập đỉnh con. D) có m+n đỉnh, mn cạnh. Đáp án C Câu 18 Đồ 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ẻ. Đáp án A Câu 19 Đồ thị phân đôi đầy đủ Kn,m có số màu bằng: A) 3 B) 4 C) 2 D)  2 Đáp án C Câu 20 Đường đi Euler vô hướng trên một đồ thị có đỉnh đầu và đỉnh cuối A) trùng nhau B) khác nhau C) có cùng bậc chẵn D) Đỉnh đầu bậc chẵn đỉnh cuối bậc lẻ Đáp án B Câu 21 Nếu G là đồ thị Euler thì A) không có đỉnh bậc chẵn B) không có đường đi Euler. C) không có chu trình Euler D) có chu trình Euler Đáp án D Câu 22 Số màu của đồ thị Cn (với n chẵn) là A) 1 B) 2 C) 3 D) 4 Đáp án B Câu 23 Số màu của đồ thị Cn (với n lẻ) là A) 1 B) 2 C) 3 D) 4 Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
Đáp án C Câu 24 Chu trình Hamilton là A) Chu trình đi qua tất cả các đỉnh mỗi đỉnh đúng một lần trừ đỉnh bậc lẻ B) chu trình đi qua tất cả các đỉnh mỗi đỉnh đúng một lần trừ đỉnh bậc chẵn C) chu trình đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần D) chu trình đi qua tất cả các đỉnh của đồ thị mỗi đỉnh hơn một lần Đáp án C Câu 25 Đồ thị liên thông G có một đỉnh có bậc bằng một thì A) G có chu trình Hamilton B) G có chu trình Euler C) G không có chu trình Hamilton D) G không có chu trình Đáp án C Câu 26 Khi xây dựng chu trình Hamilton, nếu lấy hai cạnh liên thuộc với một đỉnh đặt vào chu trình thì A) có thể xóa tất cả các cạnh còn lại không liên thuộc với đỉnh đó. B) có thể xóa tất cả các cạnh còn lại liên thuộc với đỉnh đó. C) có thể xóa tất cả các cạnh còn lại của đồ thị. D) có thể lấy thêm các cạnh liên thuộc với đỉnh đó. Đáp án B Câu 27 Số màu trong đồ thị hình bánh xe Wn (với n chẵn) là A) 1 B) 2 C) 3 D) 4 Đáp án C Câu 28 Số màu trong đồ thị hình bánh xe Wn (với n lẻ) là A) 1 B) 2 C) 3 D) 4 Đáp án D Câu 29 Cho đồ thị như hình vẽ hỏi đồ thị đó có phải là đồ thị phẳng hay không? A) Là đồ thị phẳng Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
B) Không là đồ thị phẳng C) Vừa là đồ thị phẳng, không phẳng D) Không xác định Đáp án A Câu 30 Cho đơn đồ thị phẳng liên thông có số đỉnh bằng 6 và mỗi đỉnh đều bậc 4. Số miền trong biểu diễn phẳng của đồ thị là A) 5 miền B) 6 miền C) 7 miền D) 8 miền Đáp án D Câu 31 Đồ thị như hình vẽ sau có phải là đồ thị phẳng hay không? A) là đồ thị phẳng B) không là đồ thị phẳng C) vừa là đồ thị phẳng, không phẳng D) Không xác định Đáp án A Câu 32 Đồ thị nào trong các đồ thị không phẳng sau đây có tính chất : bỏ đi một đỉnh bất kỳ và các cạnh liên thuộc với nó tạo ra một đồ thị phẳng A) K5 B) K6 C) K2 D) K7 Đáp án A Câu 33 Số màu của đồ thị G bằng bao nhiêu? A) 4 Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
B) 3 C) 2 D) 1 Đáp án B Câu 34 Số màu của đồ thị G’ bằng bao nhiêu? A) 4 B) 3 C) 2 D) 1 Đáp án A Câu 35 Độ phức tạp của thật toán Floyd là A) O(n3log2n) B) O(n2) C) O(n3) D) O(n2log2n) Đáp án C Câu 36 Thuật toán Dijkstra được áp dụng cho A) đồ thị vô hướng hoặc có hướng có trọng số không âm. B) đồ thị liên thông có trọng số không âm C) đồ thị có hướng có trọng số không âm. D) đồ thị vô hướng hoặc có hướng không có chu trình âm. Đáp án B Câu 37 Thuật toán Dijkstra được dùng để A) tìm đường đi ngắn nhất giữa các cặp đỉnh bất kì của đồ thị. B) tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại của đồ thị C) tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị. D) tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích. Đáp án D Câu 38 Với đồ thị n đỉnh, độ phức tạp tính toán của thuật toán Dijkstra là A) O(n3 log2 n) B) O(n3 ) C) O(n2 ) D) O(n2 log2 n) Đáp án C Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
Câu 39 Thuật toán Floy được dùng để A) tìm đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị. B) tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại của đồ thị. C) tìm đường đi ngắn nhất giữa hai cặp đỉnh của đồ thị. D) tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích Đáp án A Câu 40 Số cạnh của cây với 1000 đỉnh là A) 9900 B) 9999 C) 10000 D) 1001 Đáp án B Câu 41 Để xây dựng cây khung nhỏ nhất của đồ thị, ta dùng A) tìm kiếm theo chiều sâu (DFS). B) thuật toán Floyd. C) thuật toán Prim. D) thuật toán Dijsktra. Đáp án B Câu 42 Để xây dựng cây khung nhỏ nhất của đồ thị, ta dù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. Đáp án D Câu 43 Thuật toán Kruskal áp dụng cho đồ thì G, n đỉnh sẽ dừng khi A) kết nạp được n-1 cạnh vào cây khung. B) kết nạp được n cạnh vào cây khung. C) kết nạp được n – 2 cạnh vào cây khung. D) kết nạp được n - 3 cạnh vào cây khung. Đáp án A Câu 44 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. Đáp án D Câu 45 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. Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
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. Đáp án B Câu 46 Hãy cho biết đồ thị nào dưới đây là một cây A) A. B) B C) C D) D Đáp án C Trong thuật toán Ford – Fullkerson giải bài toán luồng cực đại, bước tăng Câu 47 luồng thực hiện trên A) các cạnh nằm ngoài đường đi đánh dấu. B) các cạnh nằm trên đường đi đánh dấu C) trên cạnh nối đỉnh phát với đỉnh thu. D) trên đỉnh phát và đỉnh thu. Đáp án B Câu 48 Trong thuật toán Ford – Fullkerson tìm luồng cực đại, thực hiện lặp đi lặp lại thao tác A) đánh dấu các đỉnh và cải tiến luồng. B) nâng giá trị luồng. C) giảm giá trị luồng. D) giảm khả năng thông qua của các cạnh. Đáp án A Câu 49 Giá trị của luồng cực đại trong mạng A) lớn hơn khả năng thông qua của mọi lát cắt B) bằng khả năng thông qua của một lát cắt. C) không vượt quá khả năng thông qua của lát cắt hẹp nhất trong mạng. D) không vượt quá khả năng thông qua của lát cắt lớn nhất trong mạng. Đáp án C Câu 50 G là một đơn đồ thị phẳng liên thông n đỉnh, m cạnh, gọi r là số miền trong biểu diễn phẳng của G khi đó A) r ≠ m – n +2 Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
B) r = m – n +2 C) r ≥ m – n +2 D) r ≤ m – n +2 Đáp án B Câu 51 Nếu một đơn đồ thị phẳng liên thông có n đỉnh, m cạnh (n≥ 3) thì A) m ≠ 2n - 4 B) m = 2n - 4 C) m ≤ 2n - 4 D) m ≥ 2n - 4 Đáp án C Câu 52 Theo định lý Ford – Fulkerson giá trị luồng cực đại từ điểm phát s đến điểm thu t A) bằng khả năng thông qua của lát cắt hẹp nhất tách điểm s và t. B) bằng khả năng thông qua của lát cắt lớn nhất tách điểm s và t. C) không vượt quá khả năng thông qua của lát cắt lớn nhất tách điểm s và t. D) tất cả các đáp án đều sai Đáp án A Chương 3: Biết. Câu 1 Đồ thị G = (V,E) được gọi là đơn đồ thị nếu A) giữa hai đỉnh bất kỳ i,j V, có nhiều nhất một cạnh, có kể đến thứ tự các đỉnh. B) giữa hai đỉnh bất kỳ i,j V, có nhiều nhất một cạnh. C) giữa hai đỉnh bất kỳ i,j V, có thể có nhiều hơn một cạnh, có kể đến thứ tự các đỉnh. D) giữa hai đỉnh bất kỳ i,j V, có thể có nhiều hơn một cạnh, không kể đến thứ tự các đỉnh. Đáp án B Câu 2 Nếu G = (V,E) là một đơn đồ thị vô hướng thì A) G không có khuyên, không có cạnh bội. B) G không có khuyên, có thể có cạnh bội. C) G có khuyên, không có cạnh bội. D) G có khuyên, có thể có cạnh bội. Đáp án A Câu 3 Đồ thị G = (V,E) được gọi là đồ thị vô hướng nếu A) tồn tại một cạnh của G là cạnh vô hướng B) mọi cạnh của G là cạnh vô hướng C) có hai cạnh của G là cạnh vô hướng D) mọi cạnh của G là cạnh có hướng Đáp án B Câu 4 Nếu G = (V,E) là một đơn đồ thị vô hướng thì 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 Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
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 Đáp án A Câu 5 Nếu G = (V,E) là một đa đồ thị vô hướng thì A) G không có khuyên B) G chứa cạnh bội C) G không có cạnh bội. D) G có thể có cạnh có hướng Đáp án B Câu 6 Ta gọi đỉnh v là đỉnh treo trong đồ thị vô hướng G = (V,E) A) nếu bậc của đỉnh v là 0. B) nếu bậc của đỉnh v là một số lẻ. C) nếu bậc của đỉnh v là một số chẵn. D) nếu bậc của đỉnh v là 1. Đáp án D Câu 7 Đồ 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 V luôn tồn tại đường đi từ u đến v. B) nếu u,v 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 V, thì với mọi v khác u đều kề với u. D) nếu u ,v V, thì tồn tại đỉnh v khác u kề với u. Đáp án A Câu 8 Đồ thị có hướng G =(V,E) được gọi là liên thông mạnh nếu A) giữa hai đỉnh bất kỳ u,v V luôn tìm được đường đi từ u đến v và đường đi từ v đến u. B) giữa hai đỉnh bất kỳ u,v V luôn tìm được đường đi từ u đến v C) giữa hai đỉnh bất kỳ u,v V luôn tìm được đường đi từ v đến u D) giữa hai đỉnh bất kỳ u,v V không tồn tại đường đi từ u đến v Đáp án A Câu 9 Ta nói cặp hai đỉnh (u,v) là cạnh vô hướng của đồ thị G = (V,E) nếu A) u, v  V và u, v có thứ tự B) u, v  V và u, v có thứ tự C) u, v  V và u, v không có thứ tự D) u, v  V và u, v không có thứ tự Đáp án C Câu 10 Ma trận kề của đồ thị vô hướng G = (V,E) có tính chất A) là ma trận đơn vị. B) là ma trận đối xứng. C) là ma trận không đối xứng. D) là ma trận đường chéo trên. Đáp án B Câu 11 Ma trận kề của đồ thị có hướng không phải là A) ma trận đối xứng. B) ma trận đướng chéo trên. C) ma trận không đối xứng. D) ma trận đường chéo dưới. Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
Đáp án A Câu 12 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 đó Đáp án C Câu 13 Ma trận kề của một đơn đồ thị vô hướng đầy đủ là A) ma trận tam giác trên. B) ma trận tam giác dưới C) ma trận có các phần tử trên đường chéo chính bằng 0, các phần tử khác bằng 1. D) ma trận có các phần tử trên đường chéo chính bằng 1, các phần tử khác bằng 0. Đáp án C Câu 14 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 Đáp án A Câu 15 Đường đi trong đồ thị G vô hướng từ đỉnh s đến đỉnh t là một dãy A) các cạnh e1,e2,…,en kề nhau. B) các đỉnh v0=s, v1, v2, …,vn = t kề nhau, các cạnh e i=(vi-1,vi) đôi một khác nhau, i=0..n. C) các cạnh e1,e2,…,en không kề nhau. D) các đỉnh v0=s, v1, v2, …,vn = t không kề nhau Đáp án B Câu 16 Cho đồ thị G vô hướng, đỉnh v G có bậc bằng 1 khi A) có một cạnh xuất phát từ v B) có hơn một cạnh xuất phát từ v C) có đúng một cạnh đi vào và có hơn một đỉnh đi ra khỏi đỉnh này. D) tồn tại khuyên ở đỉnh đó. Đáp án A Câu 17 Đồ thị G là không liên thông nếu nó chứa A) cạnh có hướng B) đỉnh cô lập. C) đỉnh treo. D) cạnh vô hướng Đáp án B Câu 18 Đồ thị G vô hướng được gọi là liên thông nếu giữa mọi cặp đỉnh u,v bất kỳ đều có A) một cạnh nối giữa u và v Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
B) một đường đi có hướng nối u đến v C) một đường đi vô hướng nối u đến v D) hai cạnh nối u đến v Đáp án C Câu 19 Chu trình trên đồ thị G là A) đường đi có hướng với đỉnh đầu và đỉnh cuối trùng nhau. B) đường đi có đỉnh đầu và đỉnh cuối trùng nhau. C) đường đi có đỉnh đầu và đỉnh cuối kề nhau. D) đường đi có đỉnh đầu và đỉnh cuối không kề nhau. Đáp án B Câu 20 Số đỉnh bậc lẻ trong đồ thị G vô hướng A) phụ thuộc vào số đỉnh của đồ thị. B) là một số lẻ. C) là một số chẵn. D) phụ thuộc vào số cạnh của đồ thị. Đáp án C Câu 21 Chu trình đơn trên đồ thị G là A) đường đi đơn có đỉnh đầu và đỉnh cuối trùng nhau. B) đường đi có hướng với đỉnh đầu và đỉnh cuối trùng nhau. C) đường đi đơn có đỉnh đầu và đỉnh cuối kề nhau. D) đường đi có đỉnh đầu và đỉnh cuối khác nhau Đáp án A Câu 22 Bậc của đỉnh trong đồ thị có hướng G là A) số cạnh đi vào đỉnh đó. B) số cạnh đi ra khỏi đỉnh đó. C) tổng của cạnh đi vào và số cạnh đi ra khỏi đỉnh đó. D) hiệu của cạnh đi vào và cạnh đi ra khỏi đỉnh đó Đáp án C Câu 23 Độ dài của một chu trình trên đồ thị G là A) số cạnh tạo thành chu trình. B) số đỉnh tạo thành chu trình +1. C) số cạnh tạo chu trình + 1. D) số đỉnh trên tạo chu trình – 1. Đáp án B Câu 24 Đỉnh cô lập trên đồ thị G là A) đỉnh có 2 đỉnh kề với nó. B) đỉnh có bậc bằng 1 C) đỉnh có bậc bằng 0 D) đỉnh có bậc  1 Đáp án C Câu 25 Đường đi đơn trong đồ thị G là đường đi A) các đỉnh trên nó đối xứng từng đôi một. B) các đỉnh chỉ xuất hiện một lần trừ đỉnh đầu và đỉnh cuối. C) đỉnh đầu và đỉnh cuối khác nhau. D) mỗi đỉnh chỉ kề với hai đỉnh. Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
Đáp án B Câu 26 Đồ thị đầy đủ Kn có số đỉnh và số cạnh tương ứng là A) n, 2n. B) n, n(2n-1)/2. C) n+1, 2n. D) n, n(n-1)/2. Đáp án D Câu 27 Đồ thị Cn có số đỉnh và số cạnh tương ứng là A) n, n+1 B) n, n C) n, n-1 D) n, 2n Đáp án B Câu 28 Đồ thị lập phương Qn là đồ thị A) 2n đỉnh, mỗi đỉnh kề nhau chỉ khác nhau một bit. B) 2n đỉnh, mỗi đỉnh kề nhau chỉ khác nhau nhiều nhất 2 bit. C) 2n đỉnh, mỗi đỉnh được biểu diễn bởi một xâu bit độ dài n sao cho hai đỉnh kề nhau chỉ khác nhau một bit. D) n đỉnh, mỗi đỉnh được biểu diễn bởi một xâu bit độ dài n sao cho hai đỉnh kề nhau chỉ khác nhau một bit. Đáp án C Câu 29 Chu trình Euler của đồ thị là chu trình đi qua tất cả các đỉnh A) mỗi đỉnh đúng một lần. B) mỗi cạnh đúng một lần. C) mỗi cạnh không quá một lần D) đi qua đỉnh đầu và đỉnh cuối hai lần. Đáp án B Câu 30 Chu trình Euler đi qua mỗi đỉnh của đồ thị A) không quá một lần. B) đúng một lần. C) không xác định D) nhiều hơn một lần Đáp án C Câu 31 Đường đi Euler đi qua mỗi cạnh của đồ thị A) không quá một lần. B) đúng một lần. C) không xác định D) có thể nhiều hơn một lần. Đáp án B Câu 32 Chu trình Hamilton là chu trình đi qua tất cả các đỉnh của đồ thị mỗi đỉnh A) không quá một lần. B) đúng một lần. C) luôn nhiều hơn một lần. D) không xác định. Đáp án B Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
Câu 33 Đường đi Hamilton là đường đi đi qua tất cả các đỉnh của đồ thị mỗi đỉnh A) đúng một lần B) luôn nhiều hơn một lần. C) không quá một lần. D) không xác định. Đáp án A Câu 34 Đồ thị G được gọi là nửa Hamilton nếu tồn tại đường đi đi qua tất cả các đỉnh của đồ thị A) mỗi cạnh một lần. B) mỗi cạnh không quá một lần. C) mỗi đỉnh một lần. D) một đỉnh không quá một lần. Đáp án C Câu 35 Đa đồ thị liên thông G có chu trình Hamilton nếu A) bậc của các đỉnh trong đồ thị 2 B) bậc của các đỉnh trong đồ thị n C) bậc của các đỉnh trong đồ thị n/2 D) bậc của các đỉnh trong đồ thị n/4 Đáp án C Câu 36 Một đồ thị được gọi là phẳng nếu A) có thể vẽ được trên một mặt phẳng mà có các cạnh cắt nhau ở đỉnh ngoài B) có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau C) có thể vẽ được trên một mặt phẳng mà có hai cạnh bất kỳ cắt nhau D) có thể vẽ được trên một mặt phẳng mà không có quá hai cạnh cắt nhau Đáp án B Câu 37 Nếu G là một đơn đồ thị phẳng liên thông n đỉnh (n  m cạnh khi đó 3), A) m = 3n - 6 B) m 3n - 6 C) m - 6 3n D) m  3n - 6 Đáp án D Câu 38 Số màu của một đồ thị là A) Số trung bình các màu cần thiết để tô màu đồ thị này B) Số tối thiểu các màu cần thiết để tô màu đồ thị này C) Số tối đa các màu cần thiết để tô màu đồ thị này D) Số theo yêu cầu các màu cần thiết để tô màu đồ thị này Đáp án B Câu 39 Số màu của một đồ thị phẳng là : A) bằng 5. B) lớn hơn 4. C) lớn hơn hoặc bằng 5. D) không lớn hơn 4. Đáp án D Câu 40 Đồ thị đầy đủ Kn có số màu bằng: A) (n- 2) Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
B) n C) (n-1) D) n(n-1)/2 Đáp án B Câu 41 Đồ thị G vô hướng n đỉnh là một cây nếu A) nếu liên thông và có n-1 cạnh B) nếu không liên thông và có n-1 cạnh C) nếu liên thông và có n cạnh D) nếu không liên thông và có n cạnh Đáp án A Câu 42 Cây là một đồ thị vô hướng A) liên thông và số đỉnh nhỏ hơn số cạnh là 1. B) liên thông và số đỉnh bằng số cạnh C) liên thông và không chứa chu trình D) không liên thông và có số đỉnh bằng số cạnh là 1. Đáp án C Câu 43 Bài toàn xây dựng cây khung nhỏ nhất của đồ thị được phát biểu trên: A) đồ thị có hướng có trọng số B) đồ thị vô hướng có trọng số bất kỳ C) đồ thị vô hướng D) đồ thị vô hướng có trọng số dương Đáp án D Cho G =(V,E) là đồ thị vô hướng liên thông n đỉnh. Cây T =(V T , ET ) được Câu 44 gọi là cây khung của đồ thị G nếu A) T liên thông và mỗi cạnh của nó đều là cầu. B) nếu thêm vào T một cạnh thì ta có ít nhất một chu trình C) VT =V , ET  E D) T liên thông, có đúng n cạnh và ET  E. Đáp án C Cho G =(V,E) là đồ thị vô hướng liên thông n đỉnh. T = (V , E ) được gọi là T T Câu 45 cây khung của đồ thị G nếu: A) T liên thông và chứa n đỉnh của G. B) T không liên thông, không chứa chu trình và chứa n cạnh của G. C) T liên thông, không chứa chu trình và chứa n đỉnh của G. D) T không chứa chu trình và chứa n cạnh của G. Đáp án C Câu 46 Cây là đồ thị vô hướng liên thông A) không có chu trình. B) không có đỉnh cô lập C) không có cạnh cầu D) không có đỉnh treo Đáp án A Câu 47 Mạng là một đồ thị có hướng, A) trong đó có một đỉnh cô lập. Mỗi cung e=(vi,vj) E được gán một giá trị không âm qij gọi là khả năng thông qua của cung e. Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
B) trong đó có duy nhất một đỉnh s không có cung đi vào gọi là điểm phát, có duy nhất một đỉnh t không có cung đi ra gọi là điểm thu. Mỗi cung e=(vi,vj) E được gán một giá trị không âm qij gọi là khả năng thông qua của cung C) trong đó có duy nhất một đỉnh s có cung đi vào gọi là điểm phát, có duy nhất một đỉnh t có cung đi ra gọi là điểm thu. Mỗi cung e=(vi,vj) E được gán một giá trị không âm qij gọi là khả năng thông qua của cung D) trong đó có duy nhất một đỉnh s có cung đi vào gọi là điểm phát, có duy nhất một đỉnh t không có cung đi ra gọi là điểm thu. Mỗi cung e=(vi,vj) E được gán một giá trị không âm qij gọi là khả năng thông qua của cung Đáp án B Câu 48 Cho mạng G=(V,E), giá trị của luồng f trên mạng G là số A) val(f) =  f ( s, u ) =  f (u, t ) u (s) u (t ) B) val(f) =  f ( s, u ) =  f (u, t ) u (s) u (t ) C) val(f) =  f ( s, u ) =  f (u, t ) u (s) u (t ) D) val(f) =  f ( s, u ) =  f (u, t ) u (s) u (t ) Đáp án C Câu 49 Cho mạng G, điểm phát s điểm thu t, u,v G. Điều kiện cân bằng luồng trên mỗi đỉnh của mạng: A) tổng luồng trên các cung đi ra đỉnh v bằng tổng luồng trên các cung đi ra khỏi đỉnh u nếu u,v s,t. B) tổng luồng trên các cung đi vào đỉnh v bằng tổng luồng trên các cung đi ra khỏi đỉnh u nếu u,v s,t. C) tổng luồng trên các cung đi ra đỉnh v bằng tổng luồng trên các cung đi vào đỉnh u nếu u,v s,t. D) tổng luồng trên các cung đi vào đỉnh v bằng tổng luồng trên các cung đi ra khỏi đỉnh v nếu v s,t. Đáp án D Câu 50 Cho mạng G, điểm phát s điểm thu t, v G, v s,t khi đó tổng luồng trên các cạnh đi vào đỉnh v bằng A) tổng luồng trên các cạnh đi ra khỏi đỉnh v B) tổng khả năng thông qua trên các cạnh đi ra khỏi đỉnh v C) tổng khả năng thông qua trên các cạnh đi vào đỉnh v D) tổng khả năng thông qua trên các cạnh đi vào và các cạnh đi ra khỏi đỉnh v Đáp án A Câu 51 Cho mạng G, điểm phát s điểm thu t. Tính cân bằng của luồng f trên mạng G phải thỏa mãn cho A) tất cả các đỉnh của G. B) tất cả các đỉnh của G trừ đỉnh phát s. C) tất cả các đỉnh của G rừ đỉnh thu t. D) tất cả các đỉnh của G trừ đỉnh phát s và đỉnh thu t. Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
Đáp án D Câu 52 Cho mạng G, điểm phát s điểm thu t. Lát cắt (X, Y) trong đó X V, Y= V - X là A) Tập hợp tất cả các cung (vi, vj) sao cho hoặc vi X, vj Y và vj X, vi Y B) Tập hợp tất cả các cung (vi, vj) sao cho hoặc vi X, vj Y hoặc vj X, vi Y C) Tập hợp tất cả các cung (vi, vj) sao cho hoặc vi X, vj X hoặc vj X, vi Y D) Tập hợp tất cả các cung (vi, vj) sao cho hoặc vi X, vj Y hoặc vj Y, vi Y Đáp án B Câu 53 Cho mạng G, điểm phát s điểm thu t. Khả năng thông qua của lát cắt (X, Y) là một số A) c(X,Y) =  c(v j , v j )  q jj v j X ,v j Y B) c(X,Y) =  vi X ,vi Y c(vi , vi )  qii C) c(X,Y) =  vi X ,v j Y c(vi , v j )  qij D) c(X,Y) =  vi X ,v j Y c(vi , v j )  q ji Đáp án C Câu 54 Cho mạng G, điểm phát s điểm thu t. Lát cắt (X, Y) được gọi là lát cắt hẹp nhất nếu A) khả năng thông qua của lát cắt (X,Y) bằng tổng khả năng thông qua của các cung đi ra khỏi đỉnh s B) khả năng thông qua của lát cắt (X,Y) bằng tổng khả năng thông qua của các cung đi vào đỉnh t C) khả năng thông qua của lát cắt (X,Y) lớn nhất. D) khả năng thông qua của lát cắt (X,Y) bé nhất. Đáp án D Chương 3: Áp dụng. Cho đồ thị G = (V,E) vô hướng. Bậc của các đỉnh 1, 2, 3, 4, 5 tương ứng Câu 1 là Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
A) 3, 3, 4, 6, 4 B) 3, 4, 6, 4, 4 C) 3, 4, 6, 4, 5 D) 3, 4, 5, 4, 4 Đáp án B Cho đồ thị G = (V, E) dưới dạng ma trận trọng số. Cây khung nhỏ nhất theo H = (V,T) theo thuật toán Kruskal là 0 7  2   7 0 4 3 5 4   Câu 2   4 0   3 C   2 3  0 2    5  2 0 1     4 3  1 0 A) T = {(5,6), (1,4), (4,5), (4,2), (3,6)} B) T = {(5,6), (2,3), (4,5), (4,2), (3,6)} C) T = {(5,6), (1,4), (4,5), (4,2), (3,6), (2,3)} D) T = {(5,6), (2,3), (1,2), (1,4), (3,6),(2,5)} Đáp án A Câu 3 Có bao nhiêu cạnh trong đồ thị có 10 đỉnh, mỗi đỉnh có bậc bằng 6? A) 60 B) 45 C) 30 D) 20 Đáp án C Câu 4 Đồ thị G vô hướng nào trong các đồ thị sau là tồn tại nếu các đỉnh có số bậc lần lượt là A) 2, 4, 3, 1, 4, 2, 5 B) 3, 4, 2, 1, 4, 2, 6 C) 5, 2, 2, 1, 3, 2, 4 D) 2, 1, 4, 3, 4, 2, 7 Đáp án B Câu 5 Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(I) là Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com
A) I, A, E, G, K, B, C, F, H, D B) I, A, E, G, C, K, B, F, H, D C) I, A, B, C, D, E, G, H, F, K D) I, A, B, D, E, G, C, F, H, K Đáp án A Câu 6 Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(K) là A) K, A, B, C, D, E, F, G, H, I B) K, A, C, E, G, B, D, F, H, I C) K, I, E, G, F, H, A, B, C, D D) K, I, A, E, G, B, C, F, H, D Đáp án D Câu 7 Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(I) là A) I, A, C, H, E, G, B, D, F, K B) I, A, B, C, D, E, G, F, H, K C) I, A, C, K, E, G, B, D, F, H D) I, E, F, G, H, A, B, C, D, K Đáp án C Bản quyền windows 8, windows 7, Antivirus giá rẻ http://buykeysoft.blogspot.com