Toán rời rạc · Đại Học
Thi thử trắc nghiệm ôn tập Toán rời rạc - Đề #12
30 câu30 phútSưu tầm4.500 lượt làm
- Không cần đăng nhập
- In PDF đề
Không cần tài khoản. Bài làm dở được giữ trên máy này.
Cấu trúc đề
I
30 câu trắc nghiệm một lựa chọn
30 câu · 0,33 điểm/câu
Nội dung đề
Đúng thứ tự câu và đáp án như đề gốc. Làm bài online để được chấm điểm.
I
Câu 1. (0,33 điểm)
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
Câu 2. (0,33 điểm)
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 3. (0,33 điểm)
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ẻ
Câu 4. (0,33 điểm)
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.
Câu 5. (0,33 điểm)
Đơ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.
Câu 6. (0,33 điểm)
Đồ 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
Câu 7. (0,33 điểm)
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.
Câu 8. (0,33 điểm)
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 9. (0,33 điểm)
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 10. (0,33 điểm)
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
Câu 11. (0,33 điểm)
Đồ 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
Câu 12. (0,33 điểm)
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
Câu 13. (0,33 điểm)
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 14. (0,33 điểm)
Đồ 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
Câu 15. (0,33 điểm)
Phát biểu nào sau đây là sai khi nói đến đồ thị phân đôi đầy đủ K.
- 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.
Câu 16. (0,33 điểm)
Đồ 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 17. (0,33 điểm)
Đồ thị phân đôi đầy đủ K có số màu bằng:
- A.3
- B.4
- C.2
- D.-2
Câu 18. (0,33 điểm)
Đườ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ẻ
Câu 19. (0,33 điểm)
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
Câu 20. (0,33 điểm)
Số màu của đồ thị Cₙ (với n chẵn) là:
- A.1
- B.2
- C.3
- D.4
Câu 21. (0,33 điểm)
Số màu của đồ thị Cₙ (với n lẻ) là:
- A.1
- B.2
- C.3
- D.4
Câu 22. (0,33 điểm)
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
Câu 23. (0,33 điểm)
Đồ 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
Câu 24. (0,33 điểm)
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 đó.
Câu 25. (0,33 điểm)
Số màu trong đồ thị hình bánh xe Wₙ (với n chẵn) là:
- A.1
- B.2
- C.3
- D.4
Câu 26. (0,33 điểm)
Số màu trong đồ thị hình bánh xe Wₙ (với n lẻ) là:
- A.1
- B.2
- C.3
- D.4
Câu 27. (0,33 điểm)
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
Câu 28. (0,33 điểm)
Đồ 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
Câu 29. (0,33 điểm)
Độ 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 30. (0,33 điểm)
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
Nộp bài để xem đáp án, kèm điểm và các câu làm sai. Không cần đăng nhập.
Về đề này
Thi thử trắc nghiệm ôn tập Toán rời rạc - Đề #12 gồm 30 câu, thời gian làm bài 30 phút. Nguồn đề: Sưu tầm. Làm online miễn phí, không cần đăng nhập; nộp bài là có điểm theo đúng cách chấm của Bộ.
Nguồn: Sưu tầm · Cập nhật 21/10/2026
Câu hỏi thường gặp
- Đề này có đáp án không?
- Có. Nộp bài xong là xem được đáp án.
- Làm bài có cần đăng nhập không?
- Không. Bấm Bắt đầu làm bài là làm được ngay; kết quả có đường dẫn riêng để xem lại hoặc chia sẻ.
- Làm bài trong bao lâu?
- 30 phút, hết giờ bài được nộp tự động. Có thể chọn chế độ luyện tập để làm không giới hạn thời gian.
- Có in đề ra giấy được không?
- Có. Bấm In PDF để tải đề giữ nguyên thứ tự câu và phương án như đề gốc.