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

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