Đề thi HK môn Toán rời rạc năm 2016 - CĐ Kỹ Thuật Cao Thắng - Đề 1

Gửi đến các bạn tài liệu tham khảo Đề thi HK môn Toán rời rạc năm 2016 trường CĐ Kỹ Thuật Cao Thắng - Đề 1. Hi vọng tài liệu sẽ cung cấp đến các bạn những kiến thức bổ ích trong quá trình học tập. Để nắm vững hơn nội dung chi tiết đề thi mời các bạn cùng tham khảo tài liệu.
Nội dung trích xuất từ tài liệu:
Đề thi HK môn Toán rời rạc năm 2016 - CĐ Kỹ Thuật Cao Thắng - Đề 1TRƯỜNG CĐ KỸ THUẬT CAO THẮNGKHOA ĐIỆN TỬ - TIN HỌCĐỀ 1ĐỀ THI KẾT THÚC MÔN TOÁN RR<ĐTLỚP: CĐTH 15ABNGÀY THI: 03/03/16THỜI GIAN: 75 phútCâu 1.1.Cho p, q, r là các biến mệnh đề. Dùng luật logic, CMR:(1.5 điểm)((p Ù q Ù r̅)  q)  (p  r)  (p  q  r)2.Dùng phương pháp quy nạp, CMR (Bất đẳng thức Bernoulli):(1.5 điểm)(1+a)n ≥ 1 + na, ∀n ∈ N∗Câu 2.1.Cho 3 chữ số {1,2,3}. Hãy cho biết, có bao nhiêu số có 10 chữ số tạo thànhtừ 3 chữ số đã cho, mà trong đó mỗi chữ số có mặt ít nhất 1 lần? (1.5 điểm)2.Hãy cho biết số nghiệm nguyên không âm của phương trình:(1.5 điểm)x1 + x2 + x3 + x4 = 40. Biết rằng: x1 ≥ 3; x2 ≤ 4; x3 ≥ 0 và x4 ≥ 0.Câu 3. Hãy mô tả thuật toán tìm số hạng thứ n của dãy được xác định như sau:(2.0 điểm)a0 = a1 = 1 và an= an-1 + an-2 với n = 2,3,4,...Câu 4. Cho đồ thị có trọng số sau:1.Hãy cho biết ma trận kề của đồ thị?(1.0 điểm)2.Hãy tìm cây khung ngắn nhất của đồ thị bằng thuật toán Prim?(1.0 điểm)----------Hết--------Bộ môn Tin họcGiáo viên ra đềTRƯỜNG CĐ KỸ THUẬT CAO THẮNGKHOA ĐIỆN TỬ - TIN HỌCĐỀ 1ĐÁP ÁN ĐỀ THI MÔN TOÁN RR<ĐTLỚP: CĐTH 15ABNGÀY THI: 03/03/16THỜI GIAN: 75 phútCâu 1. Cho p, q, r là các biến mệnh đề. Dùng luật logic, chứng minh rằng:1.((pÙ q Ùr̅ ) q)  (p  r)  p  q  rVT  ((p Ù q Ù r̅ )  q)  (p  r)(1.5 điểm)//kéo theo (p Ù q Ù r̅ ) Ù q  (p  r) (p Ù q Ù r̅ )  (p  r)//kết hợp (p  p  r) Ù (q  p  r)Ù(r̅  p  r)//phân phối T Ù (q  p  r) Ù T//phần tử bù p  q  r (đpcm)2.//De Morgan//lũy đẳngDùng phương pháp chứng minh quy nạp, chứng minh rằng:(1.5 điểm)(1+a)n ≥ 1+na, ∀n ∈ N∗Bước 1: Xét n =1. Ta có VT =1+a  VP = 1+a. Sang bước 2.(0.5 điểm)Bước 2: Giả sử: (1+a)n ≥ 1+na, ∀n ∈ N∗ là đúng.(0.5 điểm)Ta cần chứng minh: (1+a)n+1 ≥ 1+(n+1)a, ∀n ∈ N∗đúng.Thật vậy: (1+a)n+1 = (1+a)n(1+a)(0.5 điểm)≥ (1+na)(1+a) ≥ (1 + na+a+na2) ≥ (1 + (n+1)a + na2)≥ (1 + (n+1)a), vì na2 ≥ 0 (đpcm)Câu 2.1.Cho 3 chữ số {1,2,3}. Hãy cho biết, có bao nhiêu số có 10 chữ số tạo thànhtừ 3 chữ số đã cho, mà trong đó mỗi chữ số có mặt ít nhất 1 lần? (1.5 điểm)Ta có số số có 10 chữ số với các chữ số là 1,2,3 là: 310Gọi:(0.5 điểm)(0.5 điểm)A: tập các số 10 chữ số với các chữ số là 2,3 (không có 1)  |A| = 210B: tập các số 10 chữ số với các chữ số là 1,3 (không có 2)  |B| = 210C: tập các số 10 chữ số với các chữ số là 1,2 (không có 3)  |C| = 210X là tập các số thỏa yêu cầu đề bài:Khi đó: |X| = 310 - |A| - |B| - |C|2.(0.5 điểm)Tìm số nghiệm nguyên không âm của phương trình:(1.5 điểm)x1 + x2 + x3 + x4 = 40. Biết rằng: x1 ≥ 3; x2 ≤ 4; x3 ≥ 0 và x4 ≥ 0.Gọi x1 + x2 + x3 + x4 = 40, với : x1 ≥ 3; x2 ≤ 4; x3 ≥ 0 và x4 ≥ 0 là (1)Gọi x1 + x2 + x3 + x4 = 37, với : x1 ≥ 0; x2 ≤ 4; x3 ≥ 0 và x4 ≥ 0 là (2)Khi đó số nghiệm của (2) = K(0.5 điểm)Gọi x1 + x2 + x3 + x4 = 40, với : x1 ≥ 0; x2 ≥ 5; x3 ≥ 0 và x4 ≥ 0 là (3)Khi đó số nghiệm của (3) = KKết luận: Số nghiệm của (1): K−K(0.5 điểm)(0.5 điểm)Câu 3. Hãy mô tả thuật toán đệ quy tìm số hạng thứ n của dãy được xác định như sau:a0 = a1 = 1 và an= an-1 + an-2 với n = 2,3,4,...Cách 1: Dùng đệ quyint Cal(int n){if (n == 0 || n == 1)return 1;elsereturn Cal(n-1) + Cal(n-2);}Cách 2: Không dùng đệ quyint Cal(int n){int a0 = 1, an = 1, tam;for (int i = 3, i