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

Đến với Đề thi HK môn Toán rời rạc năm 2016 trường CĐ Kỹ Thuật Cao Thắng Đề 2 các bạn sẽ được tìm hiểu và tham khảo 3 câu hỏi tự luận với thời gian làm bài 75 phút. Cùng tìm hiểu để nắm bắt nội dung thông tin 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 - Đề 2TRƯỜNG CĐ KỸ THUẬT CAO THẮNGKHOA ĐIỆN TỬ - TIN HỌCĐỀ 2ĐỀ 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 s, t, u là các biến mệnh đề. Dùng luật logic, CMR:(1.5 điểm)((s̅ Ù t Ù u)  t̅)  (s  u)  (s  t  u)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 ≥ 0; x2 ≥ 0; x3 ≥ 3 và x4 ≤ 4.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.0 điểm)1.Hãy cho biết ma trận kề (trọng số) của đồ thị?2.Hãy tìm cây khung ngắn nhất của đồ thị bằng thuật toán Kruskal? (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ĐỀ 2ĐÁ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 s, t, u là các biến mệnh đề. Dùng luật logic, chứng minh rằng:1.((s̅ Ù t Ùu) t̅)  (s  u)  s  t  uVT  ((s̅ Ù t Ù u)  t)  (s  u)(1.5 điểm)//kéo theo (s̅ Ù t Ù u) Ù t  (s  u) (s̅ Ù t Ù u)  (s  u)//kết hợp (s̅  s  u) Ù (t  s  u)Ù(u  s  u)//phân phối T Ù (t  s  u) Ù T//phần tử bù s  t  u (đ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 ≥ 0; x2 ≥ 0; x3 ≥ 3 và x4 ≤ 4.Gọi x1 + x2 + x3 + x4 = 40, với : x1 ≥ 0; x2 ≥ 0; x3 ≥ 3 và x4 ≤ 4 là (1)Gọi x1 + x2 + x3 + x4 = 37, với : x1 ≥ 0; x2 ≥ 0; x3 ≥ 0 và x4 ≤ 4 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 ≥ 0; x3 ≥ 0 và x4 ≥ 5 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