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