TR NG CĐDL CNTT TP.HCMƯỜ Đ THI MÔN TÓAN R I R C & LÝ THUY T D THỀ Ờ Ạ Ế Ồ Ị
Khoa CNTT L P: H c l i K4.Ớ ọ ạ
* * * (TG 60 phút – Không đ c xem tài li u)ượ ệ
Bài 1:
Ch ng minh bi u th c m nh đ sau là h ng đúngứ ể ứ ệ ề ằ
(┐(a ∧ b) ∧ a) → ┐b
Bài 2:
T chu i ký t ừ ỗ ự THANHPHOHOCHIMINH t o ra bao nhiêu chu i ký t khác nhau b ngạ ỗ ự ằ
phép hóan v ?ị
Bài 3:
Tìm s đ nh và v đ th G, bi t r ng G là đ n đ th vô h ng liên thông có 15 c nh, có 3ố ỉ ẽ ồ ị ế ằ ơ ồ ị ướ ạ
đ nh b c 4, các đ nh còn l i b c 3.ỉ ậ ỉ ạ ậ
Bài 4:
Cho đ n đ th 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 7
1 0 4 - 5
15
-
-
2 4 0
28
-
-
- -
3 -
28
0
17 30
-
12
4 5 -
17
0 -
10
7
5
15
-
30
- 0 5
15
6 - - -
10
5 0 3
7 - -
12
7
15
3 0
a) V đ th G.ẽ ồ ị
b) Th hi n s ho t đ ng c a thu t toán Kruskal đ tìm cây khung nh nh t c a đ thể ệ ự ạ ộ ủ ậ ể ỏ ấ ủ ồ ị
này. V cây khung nh nh t này.ẽ ỏ ấ
H t.ế