Ôn tập TOÁN RỜI RẠC – MTH254
Áp dụng cho các lớp: MTH254 (V, X, B, BX, BV)
Nguyen Minh Nhat, 05/04/2023 A. TRẮC NGHIỆM
PHẦN 1: LOGIC VÀ TẬP HỢP
Câu 1: Tập nào dưới đây là tập con của {1, 2, 3, 4}? A. {1, 2} B. {1, 2, 3} C. {1} D. Tất cả đều đúng
Câu 2: Nếu tập A = {1, 2} và tập B = {a, b} thì tích Cartesian của hai tập A và B là:
A. {(1, a), (1, b), (2, a), (b, b)}
B. {(1, 1), (2, 2), (a, a), (b, b)}
C. {(1, a), (2, a), (1, b), (2, b)}
D. {(1, 1), (a, a), (2, a), (1, b)}
Câu 3: Cho tập S = {a, b, c}. Số tập con của tập S là: A. 3 B. 9 C. 6 D. 8
Câu 4: Số số nguyên dương không lớn hơn 1000 chia hết cho 7 hoặc 11 là: A. 232 B. 230 C. 220 D. Tất cả đều sai PHẦN 2: BÀI TOÁN ĐẾM
Câu 5. Một bình đựng 5 viên bi xanh và 4 viên bi đỏ. Lần thứ nhất lấy ngẫu nhiên một viên
bi và không bỏ vào lại bình, lần thứ hai lấy ngẫu nhiên một viên bi. Xác suất để lần đầu lấy
1 bi xanh và lần hai lấy 1 bi đỏ là: A. 0.2996 B. 0.3124 C. 0.2778 D. 0.3112
Câu 6: Phương trình sau có bao nhiêu nghiệm nguyên không âm?x + y + z = 11 A. 33 B. 78 C. 190 D. A, B, C đều sai
Câu 7: Số xâu nhị phân độ dài 10 bắt đầu bằng 3 bit 0 hoặc kết thúc bằng 2 bit 0 là: 1 | 8 A. 352 B. 1024 C. 512 D. A, B, C đều sai
Câu 9: Phương trình x + y + z = 15 có số nghiệm nguyên không âm và x>=1 là: A. 100 B. 136 C. 120 D. 45
Câu 10: Mỗi thành viên trong câu lạc bộ thể thao có quê ở 1 trong 20 tỉnh thành. Hỏi cần
phải tuyển bao nhiêu thành viên để đảm bảo có ít nhất 4 người cùng quê? A. 81 B. 80 C. 101 D. A, B sai
Câu 11: Số xâu gồm ba chữ số thập phân, bắt đầu chữ số lẻ là: A. 1000 B. 550 C. 500 D. A, B, C đều sai
Câu 13: Một hộp đựng 4 bi xanh và 5 bi đỏ. Xác suất lấy ngẫu nhiên 1 viên bi xanh từ hộp là: A. 4/5 B. 5/9 C. 4/9 D. Tất cả đều sai
Câu 14: Sắc số (số màu tối thiểu để tô các đỉnh) của đồ thị dưới đây là: A. 2 B. 3 C. 4 D. 6
Câu 15: Số hàm đơn ánh từ tập có 5 phần tử đến tập có 7 phần tử là: A. 35 B. 78125 C. 16807 D. 2520
Câu 16: Phải chọn ít nhất bao nhiêu quân bài trong bộ bài để luôn có được 3 quân bài cùng
nước (cơ, rô, chuồn, bích)? A. 3 B. 9 C. 7 D. 13
PHẦN 3: NGUYÊN LÝ BÙ TRỪ - HỆ THỨC TRUY HỒI
Câu 17: Công thức nào sau đây có thể tạo ra chuỗi 5, 9, 13, 17, 21, . . . A. an = 2n + 1. 2 | 8 B. an = 4n + 1. C. an = 4n + 3. D. an = 4n - 1.
Câu 18: Phương trình sau có bao nhiêu nghiệm nguyên không âm?x + y + z = 11 A. 33 B. 78 C. 190 D. A, B, C đều sai
PHẦN 4: BÀI TOÁN TỒN TẠI – BÀI TOÁN LIỆT KÊ
Câu 19: Chuỗi nhị phân liền sau chuỗi 11011111 là: A. 11011110 B. 10111111 C. 11111111 D. 11100000
Câu 20: Hoán vị kế tiếp của dãy 5 4 6 3 2 1 là: A. 4 5 6 3 2 1 B. 5 6 4 3 2 1 C. 5 6 1 2 3 4 D. 6 5 1 2 3 4
PHẦN 5: LÝ THUYẾT ĐỒ THỊ
Câu 21: Đồ thị G liên thông, gồm n đỉnh thì số thành phần liên thông của đồ thị là: A. n B. 0 C. 1 D. Tất cả đều sai
Câu 22: Dùng thuật toán Prim, chúng ta có thể:
A. Tìm cây khung nhỏ nhất của đồ thị
B. Tìm được đường đi ngắn nhất giữa các đỉnh trong đồ thị
C. Kiểm tra tính liên thông của đồ thị D. Câu A và câu C đúng
Câu 23: Số đỉnh bậc lẻ trong đồ thị luôn là: A. 2 B. 4 C. Số chẵn D. Tất cả đều sai
Câu 24: Giả sử các đỉnh được duyệt ưu tiên theo thứ tự đỉnh từ 1 đến n. Kết quả duyệt đồ
thị dưới đây theo chiều rộng, xuất phát từ đỉnh 1 là: A. 1 2 3 4 5 6 B. 1 2 3 4 6 5 C. 1 2 3 5 4 6 D. 1 2 5 3 4 6 3 | 8 B. CÂU HỎI NGẮN
Câu 1: Có bao nhiêu cách chia 8 bánh cho 3 em nhỏ
Vậy có 8!/(3!5!) = 56 cách đáp ứng yêu cầu.
Câu 2: Có bao nhiêu bộ nghiệm thỏa mãn phương trình X1+X2 + X3 + X = 6. 4
Mỗi bộ nghiệm của phương trình là một tổ hợp lặp chập 6 của 4 phần tử thuộc loại X1, X2, X , X 3 Và = 4 9!/(4!.5!) = 126.
Câu 3: Tìm số nghiệm nguyên không âm của phương trình x + y + z = 20, trong trường hợp: x 0, y 2, z 3.
Câu 4: Chứng minh: AB+ A C+BC=AB+ A C
Câu 5: Khử phép kéo theo cho biểu thức logic α = (P --> Q) -->R C. TỰ LUẬN
Câu 1: Chứng minh các mệnh đề sau tương đương logic a. Ø (p ↔ q) và Øp ↔ q b. Øp ↔ q và p ↔ Øq Hướng dẫn a. Ø (p ↔ q) và Øp ↔ q Ø (p ↔ q) Ø (p q) Ø (q p) Ø(Ø p q) Ø( Ø q p) (p ˄ Ø q) (q ˄ Ø p) Ø p↔ q (Ø p q) (q ˄ Ø p) (p q) ( ˄ Ø q Ø p) (1) [(p q) ˄ Ø q] [(p q) ˄ Ø p] (p ˄ Ø q) (q ˄ Ø p) Vậy Ø (p ↔ q) Øp ↔ q
b. Øp ↔ q và p ↔ Øq p ↔ Øq (p Ø q) ( ˄ Ø q p) (Ø p Ø q) (q ˄ p) (p q) ( ˄ Ø p Ø q) (2)
Từ (1) và (2) suy ra Øp ↔ q p ↔ Øq Câu 2:
a. Giải hệ thức truy hồi sau: ao = 5, a1 = 8... an=3an-1 - 2an-2
b. Giải hệ thức truy hồi sau: an = 4an-1 – 4an-2, với a0 = 4, a1 = 2 và n > 1.
c. Tìm nghiệm của hệ thức truy hồi sau: an = 2an-1 – an-2 n³ 2 với các điều kiện ³
đầu là a0 = 2, a1 = 3. 4 | 8 Hướng dẫn Đặt a = rn n
, thay vào hệ thức truy hồi đã cho, ta có được phương trình đặc trưng như sau:
r2 – 2r + 1 = 0 (r – 1) = 0 2 r = 1 (
Do đó nghiệm của hệ thức truy hồi có dạng a n
n = b1. 1 + b2.n.1n. Từ điều kiện đầu ta có được 2 phương trình:
Từ đó ta suy ra được b = 2 và b 1
= 1. Do đó nghiệm của hệ thức truy hồi đã cho 2 là: a n n = 2. 2n +n.2 .
d. Giải hệ thức truy hồi sau: an = 2an-1 +1, với a1 = 1. Tính a7 an= 2.a(n – 1) + 1 = 2.(2.a(n – 2) + 1) + 1 = 2 a(n – 2) + 2 2. 1 + 20
= 23. a(n – 3) + 22 + 21+ 20 = …
= 2n-1.a(1) + 2n-2 + … + 2 + 2 1 0 = 2 – 1. n 1.0 Với a = 1, a 1 7 = 127
Câu 3: Tại thành phố Đà Nẵng, các biển số xe theo quy định mới có dạng 43- XN - 1
NNN.NN, trong đó X là một chữ cái từ A → Z, N1 là một chữ số từ 1 → 9, N là một
chữ số từ 0 → 9 ( ngoại trừ các biển số dạng 43 – XN1 - 000.00). Hỏi có thể đăng ký
cho tối đa là bao nhiêu xe trên toàn địa bàn thành phố? Hướng dẫn -
Có 26 cách chọn 1 chữ cái cho vị trí X -
Có 9 cách chọn 1 chữ số cho vị trí N1 -
Có 10 cách chọn 1 chữ số cho vị trí N
Vậy có tổng cộng là 26 x 9 x 105 = 23400000 biển số xe theo quy định, tuy
nhiên loại trừ những biển số dạng XN -
1 000.00 (có 234 biển số dạng như vậy).
Vậy kết quả có 234000000-234 = 23399766 biển số có thể đăng ký được trên toàn địa bàn thành phố.
Câu 4: Chỉ ra rằng 7 số chọn từ 10 số nguyên dương đầu tiên nhất thiết có ít nhất 2
cặp số có tổng bằng 11. Hướng dẫn
Với 10 số nguyên dương đầu tiên 1, 2, 3, …, 10 thì có thể chia thành 5 cặp số mà có tổng
là 11, gọi 5 cặp số đó lần lượt là G1, G2, G3, G4, G5. Để chọn 7 số từ 10 số này thì cũng
là chọn 7 số từ 5 cặp số G1 …G5, theo nguyên lý Dirichlet phải có ít nhất 2 cặp số được
chọn thuộc cùng 1 nhóm tức là có tổng là 11. 5 | 8
Câu 5: Có 3 hộp đựng bi xanh, đỏ, trắng. Mỗi hộp chỉ chứa các viên bi cùng màu và
mỗi hộp có ít nhất là 8 bi. Có bao nhiêu cách chọn ra 8 viên bi trong đó có ít nhất
mỗi loại một viên bi?
Câu 6: Cho đồ thị như hình vẽ:
a) Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh D T A B C D E F L 0 X 3 4 7 X 4 7 X 10 7 10 10 X X F A A // // A A A // // A A A C // A A A C F A
Vậy đường đi từ A đến D là A->C->D với độ dài là 10
b) Tìm cây khung nhỏ nhất A B C D E F [0,0] [0, ] [0, ] [0, ] [0, ] [0, ] * [A,3] [A,4] [0, ] [0, ] [A,7] * [A,4] [0, ] [0, ] [A,7] * [C,6] [0, ] [C,5] [C,6] [F,3] * [E,4] * * 6 | 8
Vậy cây khung nhỏ nhất của đồ thị là: {AB, AC, FC, EF, ED} tổng trọng số cây khung là 19
Câu 7: Cho đồ thị G= (V, E) như hình vẽ sau đây: a b 12 4 10 14 3 a) Biểu
diễn đồ thị trên dưới dạng ma 3 11 c d e trận trọng số.
b) Chỉ ra 2 đường đi bất kỳ từ đỉnh a đến đỉnh e của đồ thị trên.
c) Dùng thuật toán Dijkstra, tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh
khác của đồ thị. Hướng dẫn Đồ thị đã cho: a b 12 a. Biểu 4 diễn 10 14 3
đồ thị dưới dạng ma trận trọng số. 3 11 b. c d e
Chỉ ra 2 đường đi bất kỳ từ a đến e:
(a,b),(b,e) : chiều dài đường đi là 15
(a,c), (c,d), (d,e): chiều dài đường đi là 18.
c. Dùng thuật toán Dijkstra, tìm đường đi ngắn nhất từ đỉnh
a đến các đỉnh khác của đồ thị trên. T a b c d e 0 x 12 4 10 x 12 x 7 L x 12 x x 18 x x x x 15 x x x x x Trươc a a a // a a c // 7 | 8 a a c d a a c b
Kết luận: đường đi ngắn nhất từ đỉnh a đến các đỉnh: B: a b độ dài: 12 C:a c độ dài: 4 D:a c d độ dài: 7 E: a b e độ dài: 15
Câu 8: Tìm dạng cực tiểu của hàm Boole sau: F(x,y,z)= Hướng dẫn x
Cực tiểu của biểu thức là
Câu 9: Rút gọn hàm bool sau bằng 2 cách -
Phép biến đổi tương đương -
Bìa Karnaugh, và vẽ mạch kết quả.
http://hfs2.duytan.edu.vn/ndJK184IUkdfn23df675/TestBank/210407_DAI_SO_BOOL_TU
_LUAN_DE_1_4653_E02DE_071203.png 8 | 8