Đề thi kết thúc môn 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<br /> KHOA ĐIỆN TỬ - TIN HỌC<br /> <br /> ĐỀ 2<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 /> Câu 1. Cho s, t, u là các biến mệnh đề. Chứng minh rằng:<br /> 1.<br /> <br /> ((s  t) Ù (t  u))  (s  u) 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ó 10 bạn nam và 15 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 /> EVERGREEN, 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 đồ thị có hướng như sau:<br /> <br /> 1.<br /> <br /> Hãy cho biết ma trận kề của đồ 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 rộng (BFS).<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 /> ĐỀ 2<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 s, t, u là các biến mệnh đề. Chứng minh rằng:<br /> 1.<br /> <br /> ((s  t) Ù (t  u))  (s  u) là một hằng đúng.<br /> Û((s̅ Út)Ù(t̅Úu))Ú(s̅ Úu)<br /> <br /> //kéo theo<br /> <br /> Û((s̅ Út)Ú(t̅Úu)Ú(s̅ Úu))<br /> <br /> //De Morgan<br /> <br /> Û((sÙt̅)Ú(tÙu))Ú(s̅ Úu)<br /> <br /> //De Morgan<br /> <br /> Û((sÚt)Ù(sÚu)Ù(t̅Út)Ù(t̅Úu))Ú(s̅ Úu)<br /> <br /> (1.0 điểm)<br /> <br /> //phân phối<br /> <br /> Û ((sÚtÚs̅ Úu)Ù(sÚuÚs̅ Úu)Ù(t̅ÚuÚs̅ Úu)) //phân phối<br /> Û TÙTÙTÛ T(đpcm)<br /> 3.<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 /> //tiền đề<br /> <br /> 5. s̅ Ù t̅<br /> <br /> //tiền đề<br /> <br /> 6. s Ú t<br /> <br /> //De Morgan<br /> <br /> 7. r → (s Ú 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 /> EVERGREEN, 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 đồ thị có hướng như sau:<br /> <br /> 1.<br /> <br /> A<br /> B<br /> C<br /> D<br /> E<br /> F<br /> 2.<br /> <br /> (1.0 điểm)<br /> <br /> Hãy cho biết ma trận kề của đồ thị trên?<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 /> Duyệt đồ thị (bắt đầu từ đỉnh A) theo chiều rộng (BFS).<br /> <br /> ABCDEF<br /> ----------Hết---------<br /> <br /> (1.0 điểm)<br /> <br />