TR
NG CĐ CNTT TP.HCM
ƯỜ
Ề
Ầ
Ế
ề
Đ THI H T MÔN TRR & LTDT - L N 2 (Đ 1) L P: Khóa 10.
Ớ (TG 90 phút – đ
c xem tài li u riêng)
ượ
ệ
Khoa CNTT * * *
ứ ứ ể ệ ề ằ Bài 1(1đ): Ch ng minh bi u th c m nh đ sau là h ng sai ((a (cid:218) b) → c) (cid:217) ((a (cid:218) b) (cid:217) ┐c)
(không phân bi t ký t ộ ự ừ ệ ế ỗ ộ đ hoa, th ự b ng 26 ch cái. Tính s m t kh u có th t o ra trong m i tr Bài 2(3đ): M t m t kh u ph i có đ dài t ậ ẩ ả c l y t t ự ượ ấ ừ ả ữ 6 đ n 8 ký t ố ậ ườ ỗ ườ ể ạ ẩ ng), m i ký ng h p sau: ợ
X. X và có ít nh t m t ký t Y. ấ ấ ậ ậ ẩ ẩ ả ả ộ ộ ự ự ấ ộ ự 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 c) Trong m t kh u ph i có ít nh t m t ký t
i ti u c a hàm Bool sau, b ng ph ng pháp bi u đ ứ ứ ố ủ ể ằ ươ ể ồ Bài 3(2đ): Tìm các công th c đa th c t Karnaugh.
F(x,y,z,t) = xyt + xyz t + x z t + x y t + x y z t + x y z
ướ ng G=(V,E) có ma tr n tr ng s nh sau (d u - là gi a 2 đ nh ố ư ữ ậ ấ ọ ỉ Bài 4(4 đ): Cho đ n đ th có h ồ ị ơ không có cung):
1 2 3 4 5 6
0 8 5 6 - - 1
- 0 - - - 9 2
- - 0 15 3 - 3
- 1 - 0 - - 4
4 - - - 0 4 5
- 7 - 2 - 0 6
ng đi ớ ồ ị ể ườ trình này. t kê các l V đ th . Th hi n s ho t đ ng c a thu t toán Dijkstra v i đ th trên, đ tìm đ ậ ẽ ồ ị i. Li ng n nh t t ệ ắ ể ệ ự ủ đ nh 1 đ n các đ nh còn l ế ạ ộ ỉ ấ ừ ỉ ạ ộ
H t.ế
TR
NG CĐ CNTT TP.HCM
ƯỜ
Ề
Ầ
Ế
ề
Đ THI H T MÔN TRR & LTDT - L N 2 (Đ 2) L P: Khóa 10.
Ớ (TG 90 phút – đ
c xem tài li u riêng)
ượ
ệ
Khoa CNTT * * *
Bài 1(1đ): Ch ng minh bi u th c m nh đ sau là h ng đúng ệ ứ ằ ể ề ứ ((p (cid:218) q) → r) (cid:218) ((p (cid:218) q) (cid:217) ┐r)
(không phân bi t ký t ộ ự ừ ệ ế ỗ ộ đ hoa, th ự b ng 26 ch cái. Tính s m t kh u có th t o ra trong m i tr Bài 2(3đ): M t m t kh u ph i có đ dài t ẩ ậ ả c l y t t ự ượ ấ ừ ả ữ 5 đ n 7 ký t ố ậ ườ ỗ ườ ể ạ ẩ ng), m i ký ng h p sau: ợ
a) Không có đi u ki n gì thêm. ệ ề b) Trong m t kh u ph i có đúng m t ký t c) Trong m t kh u ph i có đúng m t ký t A. A và có đúng m t ký t B. ậ ậ ẩ ẩ ả ả ộ ộ ự ự ộ ự
i ti u c a hàm Bool sau, b ng ph ng pháp bi u đ ứ ứ ố ủ ể ằ ươ ể ồ Bài 3(2đ): Tìm các công th c đa th c t Karnaugh.
F(x,y,z,t) = x y t + x y z t + x y z + xyt + xyz t + x z t
ướ ng G=(V,E) có ma tr n tr ng s nh sau (d u - là gi a 2 đ nh ố ư ữ ậ ấ ọ ỉ Bài 4(4 đ): Cho đ n đ th có h ồ ị ơ không có cung):
1 2 3 4 5 6
0 8 5 6 - - 1
- 0 - - - 9 2
- - 0 15 3 - 3
- 1 - 0 - - 4
4 - - - 0 4 5
- 7 - 2 - 0 6
ng đi ớ ồ ị ể ườ trình này. t kê các l V đ th . Th hi n s ho t đ ng c a thu t toán Dijkstra v i đ th trên, đ tìm đ ậ ẽ ồ ị i. Li ng n nh t t ệ ắ ể ệ ự ủ đ nh 5 đ n các đ nh còn l ế ạ ộ ỉ ấ ừ ỉ ạ ộ
H t.ế
