Trang: 1/22 --- Mã đề thi: 111

Trường ĐH Công Nghệ Thông Tin
Ngày thi: 08/05/2011
Hội đồng thi: ĐH CNTT
Số báo danh: …………………………
Họ và tên: …………………………………
Đề thi trắc nghiệm môn: CHUYÊN NGÀNH
Kỳ thi: TN TXQM
Mã đề thi: 111
Số lượng câu: 100
Thời gian làm bài: 150 phút
Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không được giải thích gì thêm
PHẦN I: TRÍ TUỆ NHÂN TẠO
Câu 1:
Cho bài toán: Giả thiết: (a e) , (b d)  (d c) , (a b). Kết luận: (c  e)
Theo thuật toán Vương Hạo, chuyển bài toán trên thành dạng chuẩn: Chọn:
A. ae , ab, (bd) (dc )  c  e B. ae , (bd),  (dc ), ab  c  e
C. ae , (bd) ( dc ) , ab, c  e D. ae , ab,  (bd) (dc )  c  e

Bài toán áp dụng cho các câu 2, câu 3, câu 4, câu 5, câu 6:
Áp dụng thuật toán tô màu để giải bài toán xếp lịch thi đấu thể thao: Có 6 đội tham gia: A, B,
C, D, E và F. Các trận đấu diễn ra theo như bảng dưới đây:

A B C D E F
A
AB AC AD AE AF
B
BC BD BE BF
C
CD CE CF

D
DE DF
E
EF
F


Các trận đấu đã xảy ra: AB, BC, CD, DE, EF và AF. Hãy sắp xếp các trận đấu còn lại sao
cho số buổi tổ chức là ít nhất. Lưu ý, mỗi đội không thể tham gia thi đấu cùng một lúc 2 trận;
Mỗi buổi có thể diễn ra nhiều trận đấu.
Câu 2:
Chọn bậc của các đỉnh AC, AD, AE, BD, BE, BF, CE, CF, DF lần lượt theo thứ tự là:
A. 4,4,3,4,4,4,3,3,4 B. 4,4,3,4,4,4,4,4,3
C. 4,4,4,4,4,4,4,3,3 D. 4,4,4,4,4,4,4,4,4

Câu 3:
Chọn bậc thấp nhất trong các đỉnh là:
A. 3 B. 4
C. 2 D. 5

Trang: 2/22 --- Mã đề thi: 111

Câu 4:
Chọn các trận đấu có thể tổ chức đồng thời với trận AD:
A. BE, CF B. BF,AC
C. CE,DF D. BD, CF

Câu 5:
Chọn các trận đấu không thể tổ chức đồng thời với trận AC:
A. BD,BE B. BF, BD

C. BF,DF D. BE,CF

Câu 6:
Chọn số buổi tổ chức các trận đấu ít nhất là:
A. 3 B. 5
C. 4 D. 6

Bài toán áp dụng cho các câu 7,câu 8, câu 9:
Cho {(pq)r, (rs) q, s}. Suy ra: {p r}
Câu 7:
Theo thuật toán Robinson, thực hiện Bước 1: chuyển bài toán trên thành dạng chuẩn, chọn:
A. pq  r, rs  q, s  p r B. pq  r, rs  q, s  p r
C. pq  r, rs  q, s  p r D. pq  r, rs  q, s  p r

Câu 8:
Theo thuật toán Robinson, bài toán trên thực hiện Bước 2: chuyển vế kết luận, chọn:
A. pq  r, rs  q, s , p, r B. pq  r, rs  q, s, p, r
C. pq  r, rs  q, s , p, r D. pq  r, rs  q, s , p,  r

Câu 9:
Theo thuật toán Robinson, chọn mệnh đề còn lại cuối cùng của bài toán trên là:
A. p
B. q
C. s
D.  r

Bài toán áp dụng cho các câu 10, câu 11, câu 12, câu 13:
Cho bảng dữ liệu:

Trang: 3/22 --- Mã đề thi: 111


Tên Vị Màu Vỏ Độc
A Ngọt Đỏ Nhẵn Không
B Cay Đỏ Nhẵn Không
C Chua Vàng Có gai Không
D Cay Vàng Có gai Độc
E Ngọt Tím Có gai Không
F Chua Vàng Nhẵn Không
G Ngọt Tím Nhẵn Không
H Cay Tím Có gai Độc
I Cay Vàng Có gai Không

Dựa vào bảng dữ liệu trên và thuật toán Quinland để xác định một loại quả độc hay không
độc ?
Định nghĩa độ đo vec-tơ đặc trưng V:
V(Thuộc tính=Đặc tính)=(


dactinh
đa ctinh
mau
maudoc
,


dactinh
đa ctinh
mau
maukhong
)

Câu 10:
Chọn giá trị của các Véc-tơ đặc trưng V của thuộc tính dẫn xuất Màu được xác định theo
thứ tự: Đỏ, Vàng, Tím là:
A. (
2
2
,
2
0
) , (
4
3
,
4
1
) , (
3
2
,
3
1
) B. (
2
2
,
2
0
) , (
4
2

,
4
2
) , (
3
2
,
3
1
)
C. (
2
2
,
2
0
) , (
4
3
,
4
1
) , (
3
1
,
3
2
) D. (
2

2
,
2
0
) , (
4
1
,
4
3
) , (
3
2
,
3
1
)

Câu 11:
Chọn các thuộc tính dẫn xuất có ít vec-tơ đơn vị nhất là:
A. Màu, Vị B. Vị, Vỏ
C. Màu, Vỏ D. Vị, Độc

Câu 12:
Chọn thuộc tính dẫn xuất để phân hoạch:
A. Màu B. Vị
C. Vỏ D. Độc






Trang: 4/22 --- Mã đề thi: 111


Câu 13:
Qua phân hoạch lần 1, chọn bảng dữ liệu quan sát còn lại là:
A. B.
Tên Vị Vỏ Độc
B Cay Nhẵn Không
C Chua Có gai Không
H Cay Có gai Độc
I Cay Có gai Không
C.
Tên Màu Vỏ Độc
B Đỏ Nhẵn Không
D Vàng Có gai Độc
H Tím Có gai Không
I Vàng Có gai Độc
D.

Tên Màu Vỏ Độc
B Đỏ Nhẵn Không
D Vàng Có gai Độc
H Tím Có gai Độc
I Vàng Có gai Không

Tên Màu Vị Độc
B Đỏ Cay Không
D Vàng Chua Độc

H Tím Cay Độc
I Vàng Cay Không


Câu 14:
Cho bài toán: {( pq) v  (r vs)}. Chứng minh: (ps).
Theo thuật toán Robinson, thực hiện Bước 1: chuyển bài toán trên thành dạng chuẩn:
A. (p v q v r)  (p v q v s)  p  s B. (p v q v r), (p v q v s)  p  s
C. (p v q v r) v (p v q v s)  p  s D. (p v q v r)  (p v q v s)  p  s

Câu 15:
Thuật toán A
T
được phát biểu như sau:

Chọn dòng lệnh thích hợp để điền vào dòng lệnh 9:
A. g(T
k
) = g(T
max
) B. g(T
k
) = g(T
max
) + c(T
max
)
C. g(T
k
) = g(T

max
) + c(T
max
, T
k
) D. g(T
k
) = g(T
k
) + c(T
max
, T
k
)

Bài toán áp dụng cho các câu 16, câu 17, câu 18, câu 19, câu 20, câu 21, câu 22:
Áp dụng thuật toán QuinLan để giải quyết bài toán sau: Xác định điều kiện như thế nào để
1. OPEN := { (T
0
, g(T
0
)=0) }
2. Quit :=FALSE
3. WHILE Quit = FALSE DO BEGIN
4. Nếu OPEN =  thì <không tìm được lời giải > Quit =TRUE;
5. Chọn T
max
 OPEN sao cho g(T
max
) là tốt nhất.

6. OPEN := OPEN – { ( T
max
, g(T
max
) ) }
7. Nếu T
max
= G <tìm được lời giải> Quit:=TRUE;
8. Ngược lại Với mỗi trạng thái T
k
có thể đi đến từ T
max
9.
-----------------------------------------------------------
10 OPEN := OPEN  {( T
k
, g(T
k
) ) }
11. END;
Trang: 5/22 --- Mã đề thi: 111

có thể đi dã ngoại được hay không ?
Cho bảng quan sát:
STT Quang cảnh Nhiệt độ Gió Dã ngoại
1 Mưa Nóng Nhẹ Không
2 Mưa Nóng Mạnh Không
3 Mây Nóng Nhẹ Đi
4 Mây Ấm Nhẹ Đi
5 Mây Mát Mạnh Đi

6 Nắng Mát Nhẹ Đi
7 Nắng Nóng Nhẹ Không
8 Nắng Nóng Mạnh Không
9 Nắng Ấm Mạnh Không
Định nghĩa độ đo vec-to đặc trưng V:
V(Thuộc tính= đặc tính)=(


dactinh
đa ctinh
mau
maudi
,


dactinh
đa ctinh
mau
maukhong
)
Câu 16:
Chọn các Véc-tơ đặc trưng V của thuộc tính dẫn xuất Quang cảnh được xác định theo thứ
tự: Mây, Mưa,Nắng là:
A. (
2
2
,
2
0
) , (

3
0
,
3
3
) , (
4
3
,
4
1
) B. (
3
0
,
3
3
) , (
2
2
,
2
0
) , (
4
3
,
4
1
)

C. (
3
0
,
3
3
) , (
4
3
,
4
1
) ,(
2
2
,
2
0
) D. (
4
3
,
4
1
) , (
3
3
,
3
0

) , (
2
0
,
2
2
)

Câu 17:
Chọn thuộc tính dẫn xuất có nhiều véc – tơ đơn vị nhất :
A. Quang cảnh B. Nhiệt độ
C. Gió D. Dã ngoại

Câu 18:
Chọn thuộc tính dẫn xuất có ít véc tơ đơn vị nhất:
A. Quang cảnh B. Nhiệt độ
C. Gió D. Dã ngoại

Trang: 6/22 --- Mã đề thi: 111


Câu 19:
Qua phân hoạch lần 1, chọn bảng quan sát còn lại là:
A. B.
STT Nhiệt độ Gió Dã ngoại
1 Mát Nhẹ Đi
2 Nóng Nhẹ Không
3 Nóng Mạnh Không
4 Ấm Mạnh Không


C.
STT Nhiệt độ Gió Dã ngoại
6 Mát Nhẹ Đi
7 Nóng Nhẹ Không
8 Nóng Mạnh Không
9 Ấm Mạnh Không

D.
STT Nhiệt độ Gió Dã ngoại
6 Mát Nhẹ Đi
7 Nóng Nhẹ Đi
8 Nóng Mạnh Không
9 Ấm Mạnh Không

STT Nhiệt độ Gió Dã ngoại
1 Mát Nhẹ Đi
2 Nóng Nhẹ Đi
3 Nóng Mạnh Không
4 Ấm Mạnh Không

Câu 20:
Chọn số luật rút ra được từ cây định danh được xây dựng theo bài toán trên:
A. 3 B. 4
C. 5 D. 6

Câu 21:
Theo các luật được rút ra từ cây định danh trên, chọn điều kiện để đi được dã ngoại:
A. Quang cảnh có mưa B. Quang cảnh có nắng và nhiệt độ ấm
C. Quang cảnh có nắng và nhiệt độ nóng D. Quang cảnh có mây


Câu 22:
Theo các luật được rút ra từ cây định danh trên, chọn điều kiện đi dã ngoại không được:
A. Quang cảnh có nắng và nhiệt độ mát B. Quang cảnh có nắng và nhiệt độ ấm
C. Quang cảnh có mây và nhiệt độ ấm D. Quang cảnh có mây và nhiệt độ nóng

Bài toán áp dụng cho câu 23, câu 24
Trang: 7/22 --- Mã đề thi: 111

Bài toán hành trình người giao hàng qua n đỉnh: Thuật giải GTS1 được cải tiến bằng thuật
giải GTS2 với p đỉnh xuất phát (p<n) và phát biểu như sau:








Câu 23:

Theo thuật giải GTS2 phát biểu trên, chọn các bước thực hiện sai:
A. Bước 1, bước 2

B. Bước 2, bước 3

C. Bước 2, bước 4

D. Bước 3, bước 5



Câu 24:
Theo thuật toán GTS2 được phát biểu trên, chọn độ phức tạp O (ô lớn) của thuật toán này
là:
A. O(n) B. O(n
2
)
C. O(n!) D. O(2n)

Câu 25:
Từ tập sự kiện ban đầu {T, U} và các luật sau:
(R1): M  Q
(R2): N  P
(R3): T  M
(R4): Q  S  O
(R5): Q  U  N
(R6): P  Q  U  O
(R7): S  U  R  M
Áp dụng cơ chế suy luận, tập sự kiện được sinh ra là:
A. {M, N, O, Q, S, T, U} B. {M, N, O, P, S, T, U}
C. {M, N, P, Q, R, T, U} D. {M, N, O, P, Q, T, U}




Bước 1: cost=

;
Best={};
k=0;
Bước 2: Nếu k>p thì qua Bước 3

Ngược lại thì dừng;
Bước 3: Tăng k=k+1;
Gọi GTS1 với thành phố xuất phát là v
k
Tính T
k

Chi phí C
k

Bước 4: Cập nhật lại hành trình với chi phí thấp nhất;
Nếu C
k
>C thì cost=C
k

Best=T
k

Bước 5: Quay lại Bước 2;
Trang: 8/22 --- Mã đề thi: 111


Câu 26:
Cho câu phát biểu:
“Nếu học lực không giỏi và ngoại ngữ không tốt , tôi không xin được việc làm”
Đặt P: Học lực giỏi, Q: ngoại ngữ không tốt, R: xin được việc làm.
Chọn biểu diễn câu trên dưới dạng logic mệnh đề:
A. (P ˅ Q) → R B. P ˅ Q → R
C. (P ˅ Q) → R

D. P  Q → R

Bài toán áp dụng cho câu 27, câu 28, câu 29, câu 30:
Áp dụng thuật toán tô màu, Cho đồ thị sau:






Câu 27:
Chọn bậc của các đỉnh AC,AE,AF,BC,BD,CF,DE,EF lần lượt theo thứ tự là:
A. 4, 4, 4, 3, 2, 4, 3, 4 B. 4, 4, 4, 3, 3, 4, 3, 4
C. 4, 4, 3, 4, 2, 4, 3, 4 D. 4, 4, 4, 3, 2, 3, 4, 4

Câu 28:
Chọn nhóm các đỉnh có thể tô cùng màu là:
A. AC,BD,CF B. AE,CF, DE
C. AF,DE, BC D. AB,EF, CF

Câu 29:
Chọn nhóm các đỉnh cấm tô cùng màu là:
A. AF,DE, BC B. AE,CF, BD
C. AC,BD,EF D. AE,CF, DE



AE
AF
AC

BC
EF BD
DE
CF