TR NG CĐ CNTT TP.HCMƯỜ Đ THI H T MÔN TRR & LTDT - L N 2 (Đ 2)Ề Ế Ầ ề
Khoa CNTT L P: Cao đ ng khóa 9 – năm h c 2009-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(3đ):
M t m t kh u ph i có đ dài 6 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 và 10 ch s . 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 s .ậ ẩ ả ấ ộ ự ố
c) Trong m t kh u không có ký t A nh ng có ít nh t m t ký t B.ậ ẩ ự ư ấ ộ ự
Bài 3(2đ):
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ó h ng G=(V,E) có ma tr n tr ng s nh sau (d u - là gi a 2 đ nhơ ồ ị ướ ậ ọ ố ư ấ ữ ỉ
không có cung):
A B C D E F G
A
0
3
1 - -
5
-
B- 0 - -
3
1 -
C
- 1 0 5 1 -
-
D
3
-
- 0 - -
18
E- - 14 - 0 - 1
F4 - - - 7 0 2
G
2 - - - 3 1
50
V đ 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 G đ n các đ nh còn l i. Li t kê các l trình này.ắ ấ ừ ỉ ế ỉ ạ ệ ộ
H t.ế
