TR NG CĐDL CNTT TP.HCMƯỜ Đ THI MÔN H T MÔN TRR & LTDT - L N 1 (Đ 2)Ề Ế Ầ ề
Khoa CNTT L P: Cao đ ng khóa 8 – năm h c 2008-2009.Ớ ẳ ọ
* * * (TG 90 phút – Không đ c xem tài li u)ượ ệ
Bài 1(1.5đ):
Cho bi t chân tr có gi i thích, và vi t m nh đ ph đ nh c a m nh đ sau (x,y là các bi nế ị ả ế ệ ề ủ ị ủ ệ ề ế
s th c)ố ự
∃x ∃y : (x-y=2) ∧ (x+2y=5)
Bài 2(2đ):
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 ch cái.ậ ẩ ả ấ ộ ữ
c) Trong m t kh u ph i có c ch và s .ậ ẩ ả ả ữ ố
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) = xy
z
+
x
y
z
t
+ xyzt + xy
t
+
x
y
t
+ x
y
t
Bài 4(1.5đ):
M t gi i thi đ u bóng đá, v i s đ i tham gia và th th c thi đ u tùy ý. Ch ng minh r ngộ ả ấ ớ ố ộ ể ứ ấ ứ ằ
luôn có m t s ch n đ i, có s tr n thi đ u là m t s l .ộ ố ẵ ộ ố ậ ấ ộ ố ẻ
Bài 5(3đ):
Cho đ n đ th có tr ng s G=(V,E) nh sau:ơ ồ ị ọ ố ư
Vi t ma tr n tr ng s c a nó. 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 A đ n các đ nh còn l i. Li t kê các l trình này.ể ườ ắ ấ ừ ế ỉ ạ ệ ộ
H t.ế
4
5
2
3
2
6
1
7 5
1
B
D
E
A
C
F