Đề 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 - Đề 1

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 /> ABCDEF<br /> ----------Hết---------<br /> <br />