Đề 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
KHOA ĐIỆN TỬ - TIN HỌC

ĐỀ 1

ĐỀ 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 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à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 ≥ 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ọc

Giáo viên ra đề

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

ĐỀ 1

ĐÁ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 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  r

VT  ((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 đẳ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 ≥ 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) = 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