ĐỀ THI HẾT MÔN TRR & LTDT - LẦN 1 (Đề 1) LỚP: C10 – năm học 2011

Tham khảo đề thi - kiểm tra đề thi hết môn trr & ltdt - lần 1 (đề 1) lớp: c10 – năm học 2011, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
ĐỀ THI HẾT MÔN TRR & LTDT - LẦN 1 (Đề 1) LỚP: C10 – năm học 2011 ĐỀ THI HẾT MÔN TRR & LTDT - LẦN 1 (Đề 1)TRƯỜNG CĐ CNTT TP.HCM LỚP: C10 – năm học 2011. Khoa CNTT *** (TG 90 phút – Không được xem tài liệu)Bài 1(1đ):Chứng minh biểu thức mệnh đề sau là hằng sai ((a ∨b) → c) ∧((a ∨b) ∧┐c)Bài 2(3đ):Một mật khẩu phải có độ dài từ 6 đến 8 ký tự (không phân biệt ký tự hoa, thường), mỗi kýtự được lấy từ bảng 26 chữ cái. Tính số mật khẩu có thể tạo ra trong mỗi trường hợp sau: a) Không có điều kiện gì thêm. b) Trong mật khẩu phải có ít nhất một ký tự X. c) Trong mật khẩu phải có ít nhất một ký tự X và có ít nhất một ký tự Y.Bài 3(2đ):Tìm các công thức đa thức tối tiểu của hàm Bool sau, bằng ph ương pháp bi ểu đ ồKarnaugh. F(x,y,z,t) = xyt + xyz t + x z t + x y t + x y z t + x y zBài 4(1đ):Một đơn đồ thị phẳng liên thông có 9 miền, có 2 đỉnh bậc 4, các đỉnh còn lại bậc 3. Tìm sốđỉnh, số cạnh và vẽ đồ thị.Bài 5(3đ):Cho đơn đồ thị có hướng G=(V,E) có ma trận trọng s ố như sau (d ấu - là gi ữa 2 đ ỉnhkhông có cung): A B C DE F G 0 3 1 - - 5 - A - 0 - - 2 1 - B - 1 0 5 1 - - C 3 - - 0 - - 8 D - - 4 - 0 - 1 E 4 - - - 7 0 2 F 1 2 - - - 3 0 G 5Vẽ đồ thị. Thể hiện sự hoạt động của thuật toán Dijkstra với đồ thị trên, đ ể tìm đườngđi ngắn nhất từ đỉnh D đến các đỉnh còn lại. Liệt kê các lộ trình này. Hết.