Thi thử trắc nghiệm ôn tập Toán rời rạc - Đề #12

Danh sách câu hỏi

1. Câu 1:

   Một học viên phải trả lời 8 trong số 10 câu hỏi cho một kỳ thi. Học viên này có bao nhiêu sự lựa chọn nếu học viên phải trả lời ít nhất 4 trong 5 câu hỏi đầu tiên?

   • A. 75
   • B. 35
   • C. 45
   • D. 30

2. Câu 2:

   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

3. Câu 3:

   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ẻ

4. Câu 4:

   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.

5. Câu 5:

   Đơ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.

6. Câu 6:

   Đồ 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. 2, 4,  1, 2, 6
   • B. 3, 4,  4, 2, 4
   • C. 1, 4,  2, 5, 2
   • D. 4, 4,  6, 5, 3

7. Câu 7:

   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.

8. Câu 8:

   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.

9. Câu 9:

   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.

10. Câu 10:

    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

11. Câu 11:

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

    $\left[ {\begin{array}{*{20}{c}} 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 \end{array}} \right]$

    Là đồ thị:

    • A. Euler
    • B. Hamilton  và Euler
    • C. Hamilton
    • D. Không  liên  thông

12. Câu 12:

    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

13. Câu 13:

    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

14. Câu 14:

    Đồ thị K₄ có số đỉnh và số cạnh tương ứng là?

    • A. 4,6
    • B. 4,8
    • C. 5,8
    • D. 4,4

15. Câu 15:

    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.

16. Câu 16:

    Đồ 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ẻ.

17. Câu 17:

    Đồ thị phân đôi đầy đủ K_n,m có số màu bằng:

    • A. 3
    • B. 4
    • C. 2
    • D. -2

18. Câu 18:

    Đườ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ẻ

19. Câu 19:

    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

20. Câu 20:

    Số màu của đồ thị C_n (với n chẵn) là:

    • A. 1
    • B. 2
    • C. 3
    • D. 4

21. Câu 21:

    Số màu của đồ thị C_n (với n lẻ) là:

    • A. 1
    • B. 2
    • C. 3
    • D. 4

22. Câu 22:

    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

23. Câu 23:

    Đồ 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

24. Câu 24:

    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 đó.

25. Câu 25:

    Số màu trong đồ thị hình bánh xe W_n (với n chẵn) là:

    • A. 1
    • B. 2
    • C. 3
    • D. 4

26. Câu 26:

    Số màu trong đồ thị hình bánh xe W_n (với n lẻ) là:

    • A. 1
    • B. 2
    • C. 3
    • D. 4

27. Câu 27:

    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

28. Câu 28:

    Đồ 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. K2
    • C. K6
    • D. K7

29. Câu 29:

    Độ 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)

30. Câu 30:

    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