TRƯỜNG ĐẠI HỌC ĐÔNG Á

KHOA CÔNG NGHỆ THÔNG TIN

ĐỀ THI KẾT THÚC HỌC PHẦN – ĐỀ THI SỐ: 01

Tên học phần: TOÁN RỜI RẠC Số tín chỉ: 03

Ngành học: Công nghệ thông tin Bậc đào tạo: Đại học - năm 2013

Thời gian làm bài: 90 phút Hình thức thi: Trắc nghiệm

Được sử dụng tài liệu: Không được sử dụng tài liệu: X

Họ và tên giáo viên ra đề: Nguyễn Thị Hồng Nhung Chữ ký: ……………………

(Cán bộ coi thi không giải thích gì thêm)

NỘI DUNG CỦA ĐỀ THI

1. Chọn câu sai trong các câu sau:

x y xy

A 0 0 0

B 0 1 1

C 1 1 0

D 1 0 1

2. Chọn câu đúng trong các câu sau:

x y xy

A 0 1 0

B 0 1 1

C 1 1 0

1

D 1 1 1

3. Chọn câu sai trong các câu sau:

x y xy

A 0 0 1

B 0 1 1

C 1 0 1

D 1 1 1

4. Chọn ý sai trong các ý sau:

A. Để xy = x x thì y = 1. C. Để xy = 1 y thì x = 0.

B. Để xy = x x thì y = 0. D. 0 = 0

5. Chọn câu sai trong các câu sau:

x y z xy̅

A 0 0 0 1

B 0 1 0 1

C 1 0 1 1

D 1 1 1 1

6. Xét hàm Bool 4 biến như sau: = + ̅ + ̅ + + ̅

6.1. Số lượng tế bào lớn 8 ô là:

A. 0 C. 2

B. 1 D. 3

6.2. Số lượng tế bào lớn 4 ô là:

A. 0 C. 2

2

B. 1 D. 3

6.3. Số lượng tế bào lớn 2 ô là:

A. 1 C. 3

B. 2 D. 4

6.4. Số lượng tế bào lớn 1 ô là:

A. 0 C. 2

B. 1 D. 3

!

6.5. Có bao nhiêu cách chọn ra 3 người từ 5 người:

=

!

=

A. 3*5 = 15 C. ()!

B. ()!! D. = 5!

6.6. Số hoán vị của 5 phần từ là:

A. 5! C. 5

B. 5*4 D. 5*5

7. Có 56 sinh viên đăng ký học môn Toán rời rạc, 42 sinh viên đăng ký học môn

Toán cao cấp, trong đó có 11 sinh viên vừa đăng ký học Toán rời rạc và Toán cao cấp.

Hỏi có bao nhiêu sinh viên đăng ký học ít nhất một trong hai môn trên?

A. 56 + 42 C. 56 + 42 – 11

B. 56 – 42 D. 56 + 42 + 11

8. Trong một lớp học gồm 20 sinh viên nam, 30 sinh viên nữ. Nhà trường muốn

chọn ra 3 sinh viên để lập ban cán sự lớp. Hỏi:

!

8.1. Có bao nhiêu cách chọn ban cán sự lớp không phân biệt nam nữ?

=

!

=

A. 50 C. ()!!

3

B. D. 50 + 20 ()!!

!

!

8.2. Có bao nhiêu cách chọn ban cán sự lớp gồm 1 nam và 2 nữ?

=

∗

()!

!

!

=

A. 50 ∗ C. ()!

∗

()!!

∗ B. D. 50 + 30 + 20 ()!!

8.3. Cho các số 1, 2, 3, 4, 5. Hỏi có thể thành lập được bao nhiếu số gồm 3 chữ số

!

khác nhau từ các số trên?

=

!

=

A. 3*5 = 15 C. ()!

B. ()!! D. = 5!

8.4. Một lớp học phải có tối thiểu bao nhiêu sinh viên để đảm bảo luôn tồn tại ít nhất

hai sinh viên có cùng tháng sinh?

C. 12 A. 10

D. 13 B. 11

8.5. Một lớp học chia thành 5 tổ. Hỏi lớp học phải có tối thiểu bao nhiêu sinh viên để

đảm bảo rằng dù phân chia bằng cách nào cũng luôn tồn tại ít nhất một tổ có số thành viên

tối thiểu là 5?

C. 22 A. 20

D. 23 B. 21

9. Cho đồ thị đơn vô hướng sau:

E

A

D

F

B

C

4

9.1. Số đỉnh của đồ thị là:

A. 5 C. 7

B. 6 D. 8

9.2. Số cạnh của đồ thị là:

A. 4 C. 6

B. 5 D. 7

9.3. Bậc cao nhất của các đỉnh ở đồ thị trên là:

A. 1 C. 3

B. 2 D. 4

9.4. Bậc thấp nhất của các đỉnh ở đồ thị trên là:

A. 0 C. 2

B. 1 D. Tất cả đều sai

9.5. Ma trận kề của đồ thị là:

A. B 1 0 1 1 0 0

A B C D E F C 0 1 0 1 0 0

A 0 1 0 1 1 0 D 1 1 1 0 0 0

B 1 0 1 1 0 0 E 1 0 0 0 0 0

C 0 1 0 1 0 0 F 0 0 0 0 0 0

D 1 1 1 0 0 0 C.

E 1 0 0 0 0 0 A B C D E F

F 0 0 0 0 0 0 A 0 1 0 1 1 0

B 1 0 1 1 0 0

B. C 0 1 0 1 0 0

A B C D E F D 1 0 1 0 0 0

5

A 0 1 0 1 0 0 E 1 0 0 0 0 0

F 0 0 0 0 0 0 C 0 1 1 1 0 0

D. D 1 1 1 1 0 0

A B C D E F E 1 0 0 0 1 0

A 1 1 0 1 1 0 F 0 0 0 0 0 1

B 1 1 1 1 0 0

9.6. Bậc của các đỉnh lần lượt là:

C. A.

Đỉnh A B C D E F Đỉnh A B C D E F

Bậc 2 3 2 3 1 0 Bậc 2 3 4 3 0 0

D. B.

Đỉnh A B C D E F Đỉnh A B C D E F

Bậc 2 3 2 3 1 0 Bậc 3 3 2 3 1 0

9.7. Chọn câu sai trong các câu sau:

A. Có đường đi từ A đến D C. Đường đi ngắn nhất từ A đến C là 2

B. Không có đường đi từ B đến F D. Đường đi ngắn nhất từ A đến C là 3

9.8. Số cạnh tối đa của đồ thị đơn vô hướng n đỉnh là:

A. n(n – 1) C. n(n – 1)/2

B. n(n + 1) D. n*n

10. Cho đồ thị đơn vô hướng sau:

E

A

D

F

6

B

C

10.1. Số đỉnh và số cạnh của đồ thị là:

A. 6 và 6 C. 5 và 7

B. 6 và 7 D. 6 và 12

10.2. Đỉnh có bậc ra lớn nhất là:

A. Đỉnh A C. Đỉnh C

B. Đỉnh B D. Đỉnh D

10.3. Chọn câu đúng:

A. Có đường đi từ B đến A C. Có đường đi từ E đến C

B. Có đường đi từ A đến F D. Có đường đi từ D đến A

10.4. Bậc vào của các đỉnh lần lượt là:

C. A.

Đỉnh A B C D E F Đỉnh A B C D E F

Bậc 2 3 2 3 1 0 Bậc 1 0 1 2 2 0

D. B.

Đỉnh A B C D E F Đỉnh A B C D E F

Bậc 2 3 2 3 1 0 Bậc 3 3 2 3 1 0

10.5. Bậc ra của các đỉnh lần lượt là:

C. A.

Đỉnh A B C D E F Đỉnh A B C D E F

Bậc 2 3 2 3 1 0 Bậc 1 0 1 2 2 0

D. B.

Đỉnh A B C D E F Đỉnh A B C D E F

Bậc 2 3 2 3 1 0 Bậc 3 0 2 1 0 0

7

(Cán bộ coi thi không giải thích gì thêm)