TRƯỜNG CĐ KỸ THUẬT CAO THẮNG<br />
KHOA ĐIỆN TỬ - TIN HỌC<br />
<br />
ĐỀ THI KẾT THÚC MÔN TOÁN RỜI RẠC<br />
LỚP: CĐN QTM, SCMT 15<br />
NGÀY THI: 04/3/16<br />
THỜI GIAN: 75 phút<br />
<br />
ĐỀ 1<br />
<br />
Câu 1. Cho p, q, r là các biến mệnh đề. Chứng minh rằng:<br />
1.<br />
<br />
((p q) Ù (q r)) (p r) là một hằng đúng.<br />
<br />
(1.5 điểm)<br />
<br />
2.<br />
<br />
Kiểm tra suy luận sau:<br />
<br />
(1.5 điểm)<br />
<br />
Câu 2.<br />
1.<br />
<br />
Lớp học có 15 bạn nam và 10 bạn nữ. Hãy cho biết có bao nhiêu cách chọn<br />
đội văn nghệ của lớp gồm 8 thành viên trong các trường hợp sau:<br />
a.<br />
<br />
Không có điều kiện gì thêm.<br />
<br />
(1.0 điểm)<br />
<br />
b.<br />
<br />
Số bạn nam bằng số bạn nữ.<br />
<br />
(1.0 điểm)<br />
<br />
c.<br />
<br />
Nhóm có cả nam và nữ.<br />
<br />
(1.0 điểm)<br />
<br />
2.<br />
<br />
Hãy cho biết, có bao nhiêu Byte (8 bit) với các bit chỉ là 0, 1 mà trong đó<br />
mỗi bit 0, 1 có mặt ít nhất 1 lần?<br />
(1.0 điểm)<br />
<br />
3.<br />
<br />
Có bao nhiêu chuỗi kí khác nhau lập được từ các chữ cái của từ<br />
MISSISSIPPI, yêu cầu dùng lại tất cả các chữ cái?<br />
(1.0 điểm)<br />
<br />
Câu 3. Cho ma trận kề của đồ thị có hướng như sau:<br />
A<br />
B<br />
C<br />
D<br />
E<br />
F<br />
<br />
A<br />
0<br />
0<br />
0<br />
1<br />
0<br />
0<br />
<br />
B<br />
1<br />
0<br />
0<br />
0<br />
0<br />
0<br />
<br />
C<br />
1<br />
1<br />
0<br />
0<br />
0<br />
1<br />
<br />
D<br />
0<br />
0<br />
1<br />
0<br />
0<br />
0<br />
<br />
E<br />
0<br />
0<br />
1<br />
1<br />
0<br />
0<br />
<br />
F<br />
0<br />
0<br />
0<br />
0<br />
1<br />
0<br />
<br />
1.<br />
<br />
Hãy vẽ đồ thị trên?<br />
<br />
(1.0 điểm)<br />
<br />
2.<br />
<br />
Duyệt đồ thị (bắt đầu từ đỉnh A) theo chiều sâu (DFS).<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 đề. Chứng minh rằng:<br />
1.<br />
<br />
((p q) Ù (q r)) (p r) là một hằng đúng.<br />
Û((pÚq)Ù(qÚr))Ú(pÚr)<br />
<br />
//kéo theo<br />
<br />
Û((pÚq)Ú(qÚr)Ú(pÚr))<br />
<br />
//De Morgan<br />
<br />
Û((pÙq)Ú(qÙr̅))Ú(pÚr)<br />
<br />
(1.0 điểm)<br />
<br />
//De Morgan<br />
<br />
Û((pÚq)Ù(pÚr̅ )Ù(qÚq)Ù(qÚr̅))Ú(pÚr) //phân phối<br />
Û ((pÚqÚpÚr)Ù(pÚr̅ ÚpÚr)Ù(qÚr̅ ÚpÚr)) //phân phối<br />
Û TÙTÙTÛ T(đpcm)<br />
2.<br />
<br />
//phần tử bù<br />
(1.5 điểm)<br />
<br />
Kiểm tra suy luận sau:<br />
1. u<br />
<br />
//tiền đề<br />
<br />
2. u → t̅<br />
<br />
//tiền đề<br />
<br />
3. t̅<br />
<br />
//khẳng định<br />
<br />
4. s<br />
̅<br />
<br />
//tiền đề<br />
<br />
5. s t̅<br />
̅Ù<br />
<br />
//tiền đề<br />
<br />
6. s<br />
Ú t<br />
<br />
//De Morgan<br />
<br />
7. r → (s<br />
Ú t)<br />
<br />
//tiền đề<br />
<br />
8. r̅<br />
<br />
//phủ định<br />
<br />
9. ( p Ú q) → r<br />
<br />
//tiền đề<br />
<br />
10. p Ú q<br />
<br />
//phủ định<br />
<br />
11. p Ù q <br />
<br />
//De Morgan<br />
<br />
12. p<br />
<br />
đpcm<br />
<br />
Câu 2.<br />
1.<br />
<br />
Lớp học có 15 bạn nam và 10 bạn nữ. Hãy cho biết có bao nhiêu cách chọn<br />
đội văn nghệ của lớp gồm 8 thành viên trong các trường hợp sau:<br />
a. Không có điều kiện gì thêm = C<br />
b. Số bạn nam bằng số bạn nữ = C<br />
c. Nhóm có cả nam và nữ = C<br />
<br />
2.<br />
<br />
− C<br />
<br />
(1.0 điểm)<br />
xC<br />
− C<br />
<br />
(1.0 điểm)<br />
(1.0 điểm)<br />
<br />
Hãy cho biết, có bao nhiêu Byte (8 bit) với các bit chỉ là 0, 1 mà trong đó<br />
mỗi bit 0, 1 có mặt ít nhất 1 lần?<br />
(1.0 điểm)<br />
Ta có số số Byte (8 bit), với các bit là 0, 1 là: 28<br />
<br />
Gọi:<br />
A: tập các Byte với các bit 0 (không có 1). |A| = 18<br />
B: tập các Byte với các bit 1 (không có 0). |A| = 18<br />
X là tập các số thỏa yêu cầu = 28 - 18 - 18<br />
3.<br />
<br />
Có bao nhiêu chuỗi kí khác nhau lập được từ các chữ cái của từ<br />
MISSISSIPPI, yêu cầu dùng lại tất cả các chữ cái?<br />
(1.0 điểm)<br />
=<br />
<br />
!<br />
! ! ! !<br />
<br />
Câu 4. Cho ma trận kề của đồ thị có hướng như sau:<br />
A<br />
B<br />
C<br />
D<br />
E<br />
F<br />
<br />
A<br />
0<br />
0<br />
0<br />
1<br />
0<br />
0<br />
<br />
B<br />
1<br />
0<br />
0<br />
0<br />
0<br />
0<br />
<br />
C<br />
1<br />
1<br />
0<br />
0<br />
0<br />
1<br />
<br />
D<br />
0<br />
0<br />
1<br />
0<br />
0<br />
0<br />
<br />
E<br />
0<br />
0<br />
1<br />
1<br />
0<br />
0<br />
<br />
F<br />
0<br />
0<br />
0<br />
0<br />
1<br />
0<br />
<br />
1.<br />
<br />
Hãy vẽ đồ thị trên?<br />
<br />
(1.0 điểm)<br />
<br />
2.<br />
<br />
Duyệt đồ thị (bắt đầu từ đỉnh A) theo chiều sâu (DFS).<br />
<br />
(1.0 điểm)<br />
<br />
ABCDEF<br />
----------Hết---------<br />
<br />