TRƯỜNG CĐ KỸ THUẬT CAO THẮNG<br />
KHOA ĐIỆN TỬ - TIN HỌC<br />
<br />
ĐỀ 2<br />
<br />
ĐỀ THI KẾT THÚC MÔN TOÁN RR<Đ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 s, t, u là các biến mệnh đề. Dùng luật logic, CMR:<br />
<br />
(1.5 điểm)<br />
<br />
((s̅ Ù t Ù u) t̅) (s u) (s t u)<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 ≥ 0; x2 ≥ 0; x3 ≥ 3 và x4 ≤ 4.<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.0 điểm)<br />
<br />
1.<br />
<br />
Hãy cho biết ma trận kề (trọng số) của đồ thị?<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 Kruskal? (1.0 điểm)<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 />
ĐỀ 2<br />
<br />
ĐÁP ÁN ĐỀ THI MÔN TOÁN RR<Đ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 s, t, u là các biến mệnh đề. Dùng luật logic, chứng minh rằng:<br />
1.<br />
<br />
((s̅ Ù t Ùu) t̅) (s u) s t u<br />
<br />
VT ((s̅ Ù t Ù u) t) (s u)<br />
<br />
(1.5 điểm)<br />
//kéo theo<br />
<br />
(s̅ Ù t Ù u) Ù t (s u)<br />
(s̅ Ù t Ù u) (s u)<br />
<br />
//kết hợp<br />
<br />
(s̅ s u) Ù (t s u)Ù(u s u)<br />
<br />
//phân phối<br />
<br />
T Ù (t s u) Ù T<br />
<br />
//phần tử bù<br />
<br />
s t u (đ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 ≥ 0; x2 ≥ 0; x3 ≥ 3 và x4 ≤ 4.<br />
Gọi x1 + x2 + x3 + x4 = 40, với : x1 ≥ 0; x2 ≥ 0; x3 ≥ 3 và x4 ≤ 4 là (1)<br />
Gọi x1 + x2 + x3 + x4 = 37, với : x1 ≥ 0; x2 ≥ 0; x3 ≥ 0 và x4 ≤ 4 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 ≥ 0; x3 ≥ 0 và x4 ≥ 5 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
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
