Trắc nghiệm toán rời rạc HUST

Trắc nghiệm Toán rời rạc HUST là một trong những đề thi môn Toán rời rạc được tổng hợp từ trường Đại học Bách Khoa Hà Nội (HUST). Môn học này đóng vai trò nền tảng trong việc phát triển tư duy logic và toán học, bao gồm các chủ đề như lý thuyết đồ thị, tổ hợp, và logic toán học, rất cần thiết cho sinh viên các ngành Công nghệ thông tin và Khoa học máy tính. Đề thi này thường được xây dựng bởi các giảng viên giàu kinh nghiệm như PGS.TS. Trần Mạnh Hùng, người có nhiều năm giảng dạy và nghiên cứu trong lĩnh vực Toán học tại HUST. Đề thi trắc nghiệm Toán rời rạc 2023 này đặc biệt hướng đến sinh viên năm thứ hai, giúp kiểm tra và củng cố những kiến thức đã học trong suốt học kỳ. Hãy cùng dethitracnghiem.vn khám phá đề thi này và tham gia kiểm tra ngay lập tức!

Câu hỏi trắc nghiệm toán rời rạc HUST (có đáp án) 

Câu 1: Có bao nhiêu xâu nhị phân độ dài 5?
A. 3
B. 20
C. 25
D. 32

Câu 2: Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E = {(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Hỏi G có phải là đồ thị đầy đủ không?
A. KHÔNG
B. CÓ

Câu 3: Cho đồ thị vô hướng G. Hỏi kết luận “duyệt theo chiều sâu trên G từ đỉnh s luôn cho ta đường đi ngắn nhất theo số cạnh từ s đến tất cả các đỉnh cùng thành phần liên thông với s” là đúng hay sai?
A. SAI
B. ĐÚNG

Câu 4: Có bao nhiêu xâu nhị phân độ dài 7 bít hoặc được bắt đầu bằng bít 10 hoặc được kết thúc bằng bít 00?
A. 56
B. 64
C. 32
D. 57

Câu 5: Cho đồ thị vô hướng G = (V,E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8} và tập cạnh E = {(1,2),(1,3),(1,6),(2,3),(2,5)}. Hỏi số cạnh (nối giữa các đỉnh trong V) ít nhất cần bổ sung thêm vào G là bao nhiêu để G trở thành đồ thị Euler?
A. 2
B. 3
C. 4
D. 1

Câu 6: Cho đồ thị vô hướng trọng số trên cạnh G = (V,E) trong đó V = {1,2,3,4,5,6} và E = {(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Trọng số trên cạnh w(1,2) = 1, w(1,3) = 1, w(1,6) = 4, w(2,3) = 1, w(2,5) = 2, w(2,6) = 2, w(4,5) = 3, w(4,6) = 5, w(5,6) = 2. Hỏi cây khung nhỏ nhất của G có trọng số bằng bao nhiêu?
A. 8
B. 9
C. 10
D. 7

Câu 7: Hãy cho biết hoán vị tiếp theo của hoán vị 4, 5, 8, 2, 7, 6, 3, 1 theo thứ tự từ điển là hoán vị nào sau đây:
A. 4, 5, 8, 2, 7, 6, 1, 3
B. 4, 5, 8, 7, 2, 6, 3, 1
C. 4, 5, 8, 3, 1, 2, 6, 7
D. 5, 4, 8, 2, 7, 6, 3, 1

Câu 8: Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E = {(1,4),(1,6),(2,5),(2,6),(3,4),(3,5),(3,6)}. Hỏi G có phải là đồ thị hai phía hay không?
A. CÓ
B. KHÔNG

Câu 9: Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Hỏi G có phải là đồ thị Euler hay không?
A. CÓ
B. KHÔNG

Câu 10: Cho đồ thị vô hướng trọng số trên cạnh G = (V,E) trong đó V = {1,2,3,4,5,6} và E = {(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Trọng số trên cạnh w(1,2) = 1, w(1,3) = 1, w(1,6) = 4, w(2,3) = 1, w(2,5) = 2, w(2,6) = 2, w(4,5) = 3, w(4,6) = 5, w(5,6) = 2. Hỏi cây khung nhỏ nhất của G có bao nhiêu cạnh?
A. 3
B. 4
C. 6
D. 5

Câu 11: Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6),(1,5)}. Hỏi chu trình nào dưới đây là chu trình Euler?
A. 1 – 3 – 2 – 5 – 4 – 6 – 1
B. 6 – 4 – 5 – 2 – 3 – 1 – 6
C. 3 – 2 – 1 – 5 – 2 – 6 – 5 – 4 – 6 – 1

Câu 12: Một cây có n cạnh thì sẽ có bao nhiêu đỉnh?
A. n-1
B. n
C. n+1
D. 2n

Câu 13: Cho đồ thị vô hướng trọng số trên cạnh G = (V,E) trong đó V = {1,2,3,4,5,6} và E = {(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Trọng số trên cạnh w(1,2) = 1, w(1,3) = 1, w(1,6) = 4, w(2,3) = 1, w(2,5) = 2, w(2,6) = 2, w(4,5) = 3, w(4,6) = 5, w(5,6) = 2. Hỏi có tồn tại cây khung nhỏ nhất của G chứa cạnh (4,6) hay không?
A. CÓ
B. KHÔNG

Câu 14: Trong lớp có 15 bạn nam và 15 bạn nữ. Hỏi có bao nhiêu cách bầu ra ban cán bộ lớp bao gồm 1 bạn nam và 2 bạn nữ?
A. 1575
B. 3150
C. 30
D. 225

Câu 15: Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Thực hiện phép duyệt đồ thị G theo chiều sâu (khi xét các đỉnh thì xét theo thứ tự từ điển). Hỏi thứ tự các đỉnh được thăm trong phép duyệt theo chiều sâu là thứ tự nào dưới đây?
A. 1, 2, 3, 5, 4, 6
B. 1, 2, 3, 4, 5, 6
C. 6, 5, 4, 3, 2, 1
D. 1, 2, 3, 6, 4, 5

Câu 16: Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Thực hiện phép duyệt đồ thị G theo chiều sâu (khi xét các đỉnh thì xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 6 tìm được bằng phép duyệt theo chiều sâu là đường đi nào dưới đây?
A. 1 – 6
B. 1 – 2 – 5 – 4 – 6
C. 1 – 2 – 5 – 6
D. 1 – 2 – 6

Câu 17: Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6),(1,5)}. Hỏi chu trình nào dưới đây là chu trình Hamilton?
A. 1 – 3 – 2 – 5 – 4 – 6 – 1
B. 1 – 2 – 3 – 1 – 5 – 4 – 6 – 1
C. 3 – 2 – 1 – 5 – 2 – 6 – 5 – 4 – 6 – 1

Câu 18: Cho đồ thị có hướng G = (V,E) trong đó tập đỉnh V = {1,2,3,4,5,6} và tập cung E = {(1,6),(2,1),(2,5),(2,6),(3,1),(3,2),(5,4),(5,6),(6,4)}. Hỏi có thể tiến hành sắp xếp TOPO các đỉnh trên G hay không?
A. CÓ
B. KHÔNG

Câu 19: Có 5 công việc đánh số 1, 2, 3, 4, 5 và 5 người thợ được đánh số 1, 2, 3, 4, 5. Tùy thuộc tay nghề chuyên môn, mỗi thợ chỉ có thể thực hiện 1 số công việc nào đó: Người thợ 1 chỉ có thể thực hiện công việc 4, thợ 2 chỉ có thể thực hiện công việc 1 hoặc 5, thợ 3 chỉ có thể thực hiện công việc 4, thợ 4 chỉ có thể thực hiện công việc 2 hoặc 3, thợ 5 chỉ có thể thực hiện công việc 1 hoặc 5. Hỏi có thể chọn ra nhiều nhất bao nhiêu công việc để phân công cho thợ sao cho mỗi công việc chỉ được thực hiện bởi duy nhất 1 người thợ (phù hợp tay nghề chuyên môn) và mỗi thợ không được thực hiện quá 1 công việc?
A. 2
B. 3
C. 4
D. 5