[Đề 114] - Đề tổng hợp - Toán rời rạc
Phần I. Trắc nghiệm 4 phương án(20 câu)
Thí sinh trả lời từ câu 1 đến câu 20. Mỗi câu hỏi thí sinh chỉ chọn một phương án.
Câu 1.Một cây (tree) có $n = 46$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 2.Đồ thị đầy đủ $K_{23}$ (n = $23$) có chu trình Hamilton hay không?
Câu 3.Biểu thức Boole $(P \lor Q) \land \neg P$ trên $(P, Q) \in \{0,1\}^2$ TRUE ở bao nhiêu trong $4$ tổ hợp giá trị?
Câu 4.Hỏi đồ thị $K_{18}$ với $n = 18$ có chu trình Hamilton (đi qua mỗi đỉnh đúng 1 lần) không?
Câu 5.Giá trị của $F_{21}$ trong dãy Fibonacci ($F_1 = F_2 = 1$) là bao nhiêu?
Câu 6.Tính tổng $S = 1 + 2 + 3 + \dots + 87$.
Câu 7.Dãy số xác định bởi $a_1 = a_2 = 1$, $a_n = a_{n-1} + a_{n-2}$. Hỏi $a_{20}$?
Câu 8.Có $31$ con thỏ được sắp vào $10$ chuồng. Theo nguyên lý Dirichlet, ít nhất phải có 1 chuồng chứa bao nhiêu con thỏ?
Câu 9.Một cây (tree) có $n = 22$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 10.Cho biểu thức Boole hai biến $P \land \neg Q$. Hỏi trong $2^2 = 4$ trường hợp gán giá trị, có bao nhiêu trường hợp biểu thức nhận giá trị TRUE?
Câu 11.Số cạnh trong đồ thị vô hướng đầy đủ $21$ đỉnh là bao nhiêu?
Câu 12.Trong $K_{42}$ (đồ thị đầy đủ $42$ đỉnh), có tồn tại chu trình Hamilton hay không?
Câu 13.Có $8$ học sinh, chọn $5$ học sinh và xếp thành 1 hàng. Số cách chọn là:
Câu 14.Đếm số dòng có giá trị $1$ trong bảng chân trị 2 biến của $P \leftrightarrow Q$.
Câu 15.Dãy Fibonacci định nghĩa $F_1 = F_2 = 1$, $F_n = F_{n-1} + F_{n-2}$. Tính $F_{25}$.
Câu 16.Trong nhóm sinh viên, có $17$ bạn học Toán, $28$ bạn học Lý, trong đó $5$ bạn học cả hai. Hỏi có bao nhiêu sinh viên học ít nhất một trong hai môn?
Câu 17.Có $22$ học sinh, chọn ngẫu nhiên $4$ học sinh không kể thứ tự. Số cách chọn là:
Câu 18.Cho biểu thức Boole hai biến $(P \oplus Q) \lor P$. Hỏi trong $2^2 = 4$ trường hợp gán giá trị, có bao nhiêu trường hợp biểu thức nhận giá trị TRUE?
Câu 19.Đồ thị đầy đủ $K_{82}$ (n = $82$) có chu trình Euler hay không?
Câu 20.Tìm hệ số của $x^{1}$ trong khai triển $(1 + 2x)^3$.
Phần III. Tự luận(8 câu)
Thí sinh trả lời từ câu 21 đến câu 28. Thí sinh điền đáp án (số) vào ô trống.
Câu 21.Tổng các bình phương từ $1^2$ đến $20^2$ bằng bao nhiêu?
Câu 22.Một đồ thị vô hướng có $|V| = 19$ đỉnh và $|E| = 154$ cạnh. Tính bậc trung bình $\bar d$ của đồ thị (giữ dạng phân số tối giản nếu cần).
Câu 23.Đồ thị vô hướng (đơn) có số cạnh $|E| = 70$. Theo bổ đề bắt tay, tổng bậc các đỉnh bằng bao nhiêu?
Câu 24.Đếm số hàm Boole $f: \{0,1\}^{3} \to \{0,1\}$ khác nhau với $n = 3$ biến đầu vào.
Câu 25.Áp dụng định lý De Morgan để rút gọn biểu thức $\neg \neg (P \lor Q)$, sau đó cho biết biểu thức nhận giá trị TRUE ở bao nhiêu dòng trong bảng chân trị 2 biến $(P, Q)$.
Câu 26.Hãy xác định Dạng chuẩn tuyển (DNF) của biểu thức $P \oplus Q$ trên 2 biến $(P, Q)$, và cho biết số minterm trong dạng chuẩn đó.
Câu 27.Đồ thị liên thông $12$ đỉnh, $49$ cạnh. Cần xóa ít nhất bao nhiêu cạnh (giữ tính liên thông) để được cây?
Câu 28.Đếm số minterm trong dạng chuẩn tuyển (DNF) của biểu thức 3 biến $P \oplus Q \oplus R$ (số dòng TRUE của bảng chân trị 8 dòng).