TR NG CĐ CNTT TP.HCMƯỜ Đ THI H T MÔN TRR & LTDT - L N 1 (Đ 2)Ề Ế Ầ ề
Khoa CNTT L P: H c l i – năm 2010.Ớ ọ ạ
* * * (TG 90 phút – Không đ c xem tài li u)ượ ệ
Bài 1(2đ):
Ch ng minh bi u th c m nh đ sau là h ng đúngứ ể ứ ệ ề ằ
((p → q) ∧ p) → q
Bài 2(2đ):
Có 50 vé s , đ c đánh s t 1 đ n 50, đ c bán cho 50 ng i khác nhau. Ng iố ượ ố ừ ế ượ ườ ườ
ta s trao 4 gi i th ng nh t, nhì, ba, t . H iẽ ả ưở ấ ư ỏ
a) Có bao nhiêu cách trao gi i?ả
b) Có bao nhiêu cách trao gi i, n u ng i có vé 50 trúng gi i nh t?ả ế ườ ả ấ
c) Có bao nhiêu cách trao gi i, n u ng i có vé 50 trúng gi i nh t và ng i cóả ế ườ ả ấ ườ
vé 60 trúng m t gi i trong các gi i còn l i?ộ ả ả ạ
Bài 3(3đ):
Tìm các công th c đa th c t i ti u c a hàm Bool có bi u đ Karnaugh sau:ứ ứ ố ể ủ ể ồ
1 1 1
1 1
1 1
1 1
Bài 4(3đ):
Cho đ n đ th có tr ng s G=(V,E) có ma tr n tr ng s nh sau (d u - là gi a 2 đ nhơ ồ ị ọ ố ậ ọ ố ư ấ ữ ỉ
không có c nh):ạ
1 2 3 4 5 6
1 0 - 2 7 1 -
2 - 0 1 4 - 2
3 2 1 0 - 6 5
4 7 4 - 0 3 5
5 1 - 6 3 0 -
6 - 2 5 5 - 0
V đ thi. 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 5 đ n các đ nh còn l i. Li t kê các l trình này.ắ ấ ừ ỉ ế ỉ ạ ệ ộ
H t.ế