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

TRƯỜNG CĐ KỸ THUẬT CAO THẮNG
KHOA ĐIỆN TỬ - TIN HỌC

ĐỀ 2

ĐỀ THI KẾT THÚC MÔN TOÁN RR&LTĐT
LỚP: CĐTH 15AB
NGÀY THI: 03/03/16
THỜI GIAN: 75 phút

Câ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ành
từ 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ọc

Giáo viên ra đề

TRƯỜNG CĐ KỸ THUẬT CAO THẮNG
KHOA ĐIỆN TỬ - TIN HỌC

ĐỀ 2

ĐÁP ÁN ĐỀ THI MÔN TOÁN RR&LTĐT
LỚP: CĐTH 15AB
NGÀY THI: 03/03/16
THỜI GIAN: 75 phút

Câ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  u

VT  ((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 đẳng

Dù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ành
từ 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à: 310

Gọ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| = 210
B: tập các số 10 chữ số với các chữ số là 1,3 (không có 2)  |B| = 210
C: tập các số 10 chữ số với các chữ số là 1,2 (không có 3)  |C| = 210
X 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) = K
Kế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 đệ quy
int Cal(int n){
if (n == 0 || n == 1)
return 1;
else
return Cal(n-1) + Cal(n-2);
}

Cách 2: Không dùng đệ quy
int Cal(int n){
int a0 = 1, an = 1, tam;
for (int i = 3, i