Đề thi cuối kỳ Toán rời rạc | Đại học Sư phạm kỹ thuật - Đại học Đà Nẵng

lOMoAR cPSD| 46342576
TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA: CÔNG NGHỆ THÔNG TIN
BỘ MÔN: CÔNG NGHỆ PHẦN MỀM ĐỀ THI CUỐI KỲ
Tên học phần: TOÁN RỜI RẠC
Mã học phần: …………………… Số tín chỉ: 3
Phương pháp đánh giá (*): tự luận có giám sát Thời gian làm bài: 90 phút Đề số: Đ0001
☐ Sinh viên được sử dụng tài liệu khi làm bài (tuy nhiên không được phép sử dụng ChatGPT)
—------------------------------------------------------------------------------------------------------------------------------- Họ tên:
……………………… Lớp:………………MSSV:……………………...
Sinh viên làm bài trực tiếp trên tệp này, lưu tệp với định dạng MSSV_HọTên.pdf và nộp bài thông qua MSTeam:
Câu 1 (2,5 điểm) Cho tập X={ 1, 2, 3, 4, 5, 6, 7, 8 A, B, C, D }, với xâu S có độ dài n, S = 𝑠1𝑠2
… 𝑠𝑛, 𝑠𝑖 ∈ 𝑋:
a) (1,0 đ) Hãy đếm số xâu S với độ dài n sao cho có ít nhất 1 chữ số.
# Trả lời: Trình bày và viết kết quả vào bên dưới:
Số xâu có độ dài n là: 12^n
Số xâu có độ dài n mà không có chữ số nào là: 8^n
=>Số xâu S có độ dài n sao cho có ít nhất 1 chữ số là: 12^n – 8^n lOMoAR cPSD| 46342576
# Trả lời: Trình bày và viết kết quả vào bên dưới:
Gọi Fn là tổng số xâu hợp lệ, An là số xâu kết thúc bằng một chữ cái, Bn là số xâu kết thúc bằng một chữ số.  Fn = An + Bn
+An là số xâu kết thúc bằng một chữ cái=> trước đó là chữ cái hoặc chữ số
=>có 4 cách chọn chữ cái cuối cùng và F(n-1) cách tạo phần còn lại =>có 4*F(n-1) xâu
+Bn là số xâu kết thúc bằng một chữ số=> trước đó phải là chữ cái
Có 8 cách chọn chữ số cuối cùng và A(n-1)=4*F(n-2) cách tạo phần còn lại. =>có 8*4*F(n-2)=32*F(n-2) xâu =>Fn=4*F(n-1)+ 32*F(n-2)
Phương trình đặc trưng: x^2=4x+32
=>x^2-4x-32=0 có 2 nghiệm phân biệt là x=8 và x=-4 =>Fn=b*8^n + d*(-4)^n Ta có F0=1, F1=12
=>ta có hệ phương trình: b+d=1, 8b-4d=12=>b=4/3, d=-1/3 =>Fn= ×8n + - 1 ×(-4)n 3 Vậy số xâu S hợp lệ là ×8n + - 1 ×(-4)n 3
b) (1,0 đ) Hãy đếm số xâu S với độ dài n sao cho không có hai chữ số kề nhau.
c) (0,5 đ) Viết hàm để đếm xâu ký tự S với độ dài n không có hai chữ số kề nhau.
# Trả lời: Giải thích và trình bày và viết hàm vào bên dưới:
Câu 2 (3,0 điểm). Cho đồ thị G liên thông, có trọng số như sau:
a) (1,0 đ) Dùng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh a đến đỉnh h. lOMoAR cPSD| 46342576
# Trả lời: Trình bày cách giải bằng bảng vào bên dưới: Vi a b c d e g h k m n - 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ a * 1 ∞ ∞ 3 ∞ ∞ ∞ 3 2 b - * 5 ∞ 2 ∞ ∞ ∞ 3 2 n - - 5 ∞ 2 ∞ ∞ ∞ 3 * e - - 4 ∞ * 6 ∞ ∞ 3 - m - - 4 ∞ - 6 ∞ 6 * - c - - * 10 - 6 ∞ 6 - - g - - - 8 - * 9 6 - - k - - - 8 - - 7 * - - h - - - 8 - - * - - - d - - - * - - - - - -
# Trả lời: Trình bày đường đi và khoảng cách tìm được:
Đường đi ngắn nhất từ đỉnh a đến đỉnh h là: a-m-k-h với khoảng cách là 7
b) (1,0 đ) Dùng thuật toán Prim để tìm cây khung nhỏ nhất của đồ thị G, mà bắt buộc chứa cạnh (e, g).
# Trả lời: Trình bày cách giải vào bên dưới:
# Trả lời: Trình bày kết quả vào bên dưới:
c) (1,0 đ) Viết hàm cài đặt thuật toán Prim
# Trả lời: Giải thích và trình bày hàm vào bên dưới:
Câu 3 (2,5 điểm) Giả sử các hoán vị của tập X={1, 2, 3, 4, 5} được sắp xếp theo thứ tự tăng dần. a)
(0,5 đ) Cho biết hoán vị nhỏ nhất.
# Trả lời: Giải thích và dán kết quả vào bên dưới:
Hoán vị nhỏ nhất là: 12345
b) (1,0 đ) Trình bày các bước tìm hoán vị tiếp theo của hoán vị S = 32541.
# Trả lời: Giải thích và trình bày kết quả vào bên dưới:
Vì 541 là lớn nhất nên phần tử tăng được là 2. Phần tử nhỏ nhất lớn hơn 2 nằm ở bên phải
là 4. Đổi chỗ 2 với 4 ta được 34521.
Hoán vị tiếp theo của S=32541 là 34125. lOMoAR cPSD| 46342576
c) (1,0 đ) Sử dụng kết quả câu b) viết chương trình liệt kê tất cả các hoán vị của X.
# Trả lời: Giải thích và trình bày chương trình vào bên dưới:
Câu 4 ( 2,0 điểm) Cho biểu thức Boole:
𝑬(𝒙, 𝒚, 𝒛) = 𝒙𝒚𝒛 + 𝒙𝒚 𝒛 + + 𝒙 𝒚𝒛 + 𝒙𝒚𝒛 + 𝒙 𝒚 𝒛
a) (1,0 đ) Lập bảng chân trị của biểu thức 𝑬(𝒙, 𝒚, 𝒛).
# Trả lời: Trình bày kết quả bảng chân trị vào bên dưới: x y z E(x,y,z) 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1 1 1
b) (1,0 đ) Dùng bản đồ Karnaugh để tìm biểu thức tối thiểu của 𝑬(𝒙, 𝒚, 𝒛).
# Trả lời: Trình bày cách giải và kết quả vào bên dưới: 𝒚𝒛 𝒚𝒛 𝒚 𝒛 𝒚 𝒛 1 1 𝒙 1 1 1 1 𝒙
Biểu thức tối thiểu E(x,y,z) = 𝒙 𝒛+
Tổng cộng có: 4 câu
Đà Nẵng, ngày 02 tháng 06 năm 2025 lOMoAR cPSD| 46342576
GIẢNG VIÊN BIÊN SOẠN ĐỀ THI TRƯỞNG BỘ MÔN (đã ký)