525 câu trắc nghiệm môn Toán rời rạc
tracnghiem.net chia sẻ 525 câu trắc nghiệm môn Toán rời rạc (có đáp án) dành cho các bạn sinh viên chuyên ngành có thêm tư liệu học tập, ôn tập chuẩn bị cho kì thi kết thúc học phần sắp diễn ra. Nội dung gồm những vấn đề cơ bản nhất của toán học rời rạc lý thuyết tổ hợp, lý thuyết đồ thị, lý thuyết độ phức tạp, đại số Boole.,…Để việc ôn tập trở nên hiệu quả hơn, các bạn có thể ôn theo từng phần trong bộ câu hỏi này bằng cách trả lời lần lượt các câu hỏi cũng như so sánh đáp và lời giải chi tiết được đưa ra. Sau đó các bạn hãy chọn tạo ra đề ngẫu nhiên để kiểm tra lại kiến thức mình đã ôn tập được nhé!
Chọn hình thức trắc nghiệm (30 câu/60 phút)
-
Câu 1:
Kết quả thuật toán đệ quy:
Function Test(st:string):string;
Begin
If length(st) <=1 then Test:=st
Else Test:= st[length(st)] + Test(Copy(st,1,length(st)-1));
End;
A. Xuất mỗi kí tự của st trên một dòng
B. Đảo ngược chuỗi st
C. Đưa ra tất cả các xâu con của xâu kí tự st
D. Đưa ra độ dài của xâu st
-
Câu 2:
Dạng chính tắc tuyển (nối rời chính tắc) của hàm Boole là…?
A. Công thức biểu diễn hàm Boole thành tổng của các tích cơ bản (từ tối tiểu)
B. Công thức biểu diễn hàm Boole thành tích của các tích cơ bản (từ tối tiểu)
C. Công thức biểu diễn hàm Boole thành tổng của các đơn thức
-
Câu 3:
Công thức nào sau đây đúng. Cho x, y là 2 biến và n là một số nguyên dương. Khi đó:
A. \({(x + y)^n} = \sum\nolimits_{i = 0}^n {C(n,i)} {x^{n - i}}{y^i}\)
B. \({(x + y)^n} = \sum\nolimits_{i = 1}^n {C(n,i)} {x^{n - i}}{y^i}\)
C. \({(x + y)^n} = \sum\nolimits_{i = 0}^n {C(n,i)} {x^n}{y^i}\)
D. \({(x + y)^n} = \sum\nolimits_{i = 0}^n {C(n,i)} {x^n}{y^{n - i}}\)
-
Câu 4:
Cho đồ thị G có bậc là 10. Số cạnh của đồ thị G là:
A. 2
B. 3
C. 4
D. 5
-
Câu 5:
Cho các mệnh đề được phát biểu như sau:
- Quang là người khôn khéo
- Quang không gặp may mắn
- Quang gặp may mắn nhưng không không khéo
- Nếu Quang là người khôn khéo thì không gặp may mắn
- Quang là người khôn khéo khi và chi khi Quang gặp may mắn
- Hoặc Quang là người khôn khéo, hoặc gặp may mắn nhưng không đồng thời cả hai.
Hãy cho biết có tối đa bao nhiêu mệnh đề đồng thời đúng trong số các mệnh đề trên?
A. 2
B. 3
C. 4
D. 5
-
Câu 6:
Trong số các quan hệ hai ngôi dưới đây, quan hệ nào có tính phản đối xứng?
A. R = {(a,b)| a ≤ b} trên tập số nguyên
B. {(1,1), (1,2), (2,2), (2,3), (3,2), (3,3)} trên tập {1,2,3}
C. {(a,b), (a,c), (b,b), (b,c), (c,c), (c,a)} trên tập {a,b,c}
D. R = {(a,b)| a≡b(mod 3)} trên tập {-15, -14, …, 14, 15}
-
Câu 7:
Cho quan hệ R = {(a,b)| a ≡ b(mod 4)} trên tập {-8, -7, …,7, 8}. Hãy xác định [1]R?
A. {-8, -4, 1, 4, 8}
B. {-7, -3, 1, 5}
C. {-5, -1, 3, 7}
D. {1}
-
Câu 8:
Cho n, r là các số nguyên không âm sao cho \(r \le n\). Khi đó:
A. C(n,r) = C(n+r-1,r)
B. C(n,r) = C(n, r-1)
C. C(n,r) = C(n,n-r)
D. C(n,r) = C(n-r,r)
-
Câu 9:
Có bao nhiêu chuỗi bít có độ dài nhỏ hơn hoặc bằng 6?
A. 64
B. 124
C. 126
D. 62
-
Câu 10:
Cấu trúc của chương trình con đệ quy gồm:
A. Phần dễ giải quyết và phần khó giải quyết
B. Phần cơ sở và phần đệ quy
C. Phần cơ sở và phần quy nạp
D. Phần hữu hạn và phần quy nạp
-
Câu 11:
Chu trình Hamilton là chu trình đi qua tất cả các đỉnh của đồ thị mỗi đỉnh.
A. Không quá một lần.
B. Đúng một lần.
C. Luôn nhiều hơn một lần.
D. Không xác định
-
Câu 12:
Cho X={1,2,3,4,5,6,7,8,9} A={1,2,3,8}, B={2,4,8,9}, C={6,7,8,9}
Tìm xâu bit biểu diễn tập: \((A \cup B) \cap C\)
A. 000000011
B. 111111100
C. 000011
D. 111100
-
Câu 13:
Một hội nghị bàn tròn của phái đoàn các nước: Việt Nam 3 người; Lào 2 người; Campuchia 1 người; Thái Lan 2 người. Có bao nhiêu cách xếp chỗ ngồi cho mọi thành viên sao cho người cùng quốc tịch ngồi cạnh nhau?
A. 120
B. 476
C. 24
D. 96
-
Câu 14:
Chu trình trên đồ thị G là:
A. Đường đi có hướng với đỉnh đầu và đỉnh cuối trùng nhau.
B. Đường đi có đỉnh đầu và đỉnh cuối trùng nhau.
C. Đường đi có đỉnh đầu và đỉnh cuối kề nhau.
D. Đường đi có đỉnh đầu và đỉnh cuối không kề nhau
-
Câu 15:
Tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại trong đồ thị sau. Đỉnh E được gán trọng số nhỏ nhất là?
A. 3
B. 4
C. 5
D. 6
-
Câu 16:
Cho đồ thị G liên thông có 5 đỉnh. Hỏi cây khung của G có mấy cạnh, mấy đỉnh?
A. 5 cạnh, 5 đỉnh
B. 4 cạnh, 5 đỉnh
C. 5 cạnh, 4 đỉnh
D. 4 cạnh, 4 đỉnh
-
Câu 17:
Cô dâu và chủ rể mời 4 người bạn đứng thành một hàng để chụp ảnh với mình. Có bao nhiêu cách xếp hàng nếu cô dâu đứng ở phía bên trái chú rể?
A. 120
B. 720
C. 360
D. 480
-
Câu 18:
Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(C) là:
A. C, A, B, E, F, D, G, H, K, C, N
B. C, A, B, K, N, I, D, E, F, H, G
C. C, A, E, G, B, D, F, H, K, I, N
D. C, A, E, G, F, H, N, B, D, I, K
-
Câu 19:
Nội dung chính của thuật toán quay lui là:
A. Xây dựng toàn bộ các thành phần của cấu hình bằng cách thử tất cả các khả năng
B. Xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả năng.
C. Xây dựng mỗi thành phần của cấu hình bằng cách thử tất cả các khả năng
D. Xây dựng bất kì thành phần nào của cấu hình bằng cách thử tất cả các khả năng
-
Câu 20:
Cho biết số phần tử của A1 + A2 + A3 nếu mỗi tập có 100 phần tử và các tập hợp là đôi một rời nhau?
A. 200
B. 300
C. 100
D. 0
-
Câu 21:
Cho A={1,2,3,4,5}. Có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau không bắt đầu bởi chữ số 1 được thành lập từ A.
A. 24
B. 120
C. 96
D. 16
-
Câu 22:
Để chứng minh tích của 3 số tự nhiên liên tiếp luôn chia hết cho 6, người ta chứng minh như sau:
- Đặt P(n) = n(n+1)(n+2). P(n) chia hết cho 6 với n>0.
- Ta có, với n = 1; P(1) = 1.2.3 = 6, chia hết cho 6
- Giả sử P(n) đúng , ta đi chứng minh (n+1) (n+2)(n+3) chia hết cho 6.
- Ta có, (n+1) (n+2)(n+3) = n(n+1)(n+2) + 3(n+1)(n+2).
- Ta đã có n(n+1)(n+2) chia hết cho 6. Mặt khác (n+1)(n+2) luôn chia hết cho 2 (kết quả này đã được chứng minh). Do vậy, 3(n+1)(n+2) chia hết cho 6. Như vậy ta được điều phải chứng minh.
Đoạn trên sử dụng phương pháp nào?
A. Chứng minh qui nạp mạnh
B. Chứng minh trực tiếp
C. Chứng minh quy nạp yếu
D. Chứng minh phản chứng.
-
Câu 23:
Lớp toán học rời rạc có 25 sinh viên giỏi tin học, 13 sinh viên giỏi toán và 8 sinh viên giỏi cả toán và tin học. Hỏi lớp có bao nhiêu sinh viên nếu mỗi sinh viên hoặc giỏi toán hoặc học giỏi tin học hoặc giỏi cả hai môn?
A. 12
B. 25
C. 30
D. 13
-
Câu 24:
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 25:
Cho X = {1,2,3,4,5,6,7,8,9}. Xâu bit biểu diễn tập A là: 111001011, xâu bit biểu diễn tập B là 010111001. Tìm xâu bit biểu diễn tập \(A \cap B.\)
A. 010001100
B. 101110010
C. 010001001
D. 010001101
-
Câu 26:
Hai biểu thức boole gọi là tương đương nhau nếu chúng:
A. Có cùng giá trị chân lý trong mọi trường hợp giá trị của các biến Boole.
B. Có cùng số biến và có cùng giá trị chân lý.
C. Cùng biểu diễn một hàm boole, số biến bằng nhau.
D. Có số biến bằng nhau và biểu diễn 2 hàm boole giống hoặc khác nhau.
-
Câu 27:
Nội dung của nguyên lý bù trừ phát biểu trên hai tập hợp hữu hạn A, B:
A. Nếu A và B là hai tập hợp rời nhau thì: N( A+B )= N(A) + N(B)
B. Nếu A và B là hai tập hợp thì: N(A . B ) = N(A).N(B)
C. Nếu A và B là hai tập hợp thì: N(A+B)= N(A) + N(B) – N(A+B)
D. Nếu có N đồ vật được đặt vào K hộp thì sẽ tồn tại một hộp chứa ít nhất đồ vật.
-
Câu 28:
Thuật toán Dijkstra được dùng để:
A. Tìm đường đi ngắn nhất giữa các cặp đỉnh bất kì của đồ thị.
B. Tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại của đồ thị
C. Tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị.
D. Tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích.
-
Câu 29:
Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(K):
A. K, B, D, F, H, A, C, E, G, I
B. K, B, A, C, D, F, E, G, H, I
C. K, B, F, H, A, C, D, E, G, I
D. K, E, F, G, H, A, B, C, D, I
-
Câu 30:
Khi chạy chương trình:
Var S, i, j : Integer;
Begin
S := 0;
for i:= 1 to 3 do
for j:= 1 to 4 do S := S + 1 ;
End.
Giá trị sau cùng của S là:
A. 4
B. 3
C. 12
D. 0