Câu hỏi: Cho đồ thị trọng số G=(V,E) như hình vẽ. Cây khung nhỏ nhất H = (V,T) theo thuật toán Prim có tập cạnh:

A. T ={(2,5)(2,6)(2,3)(6,2)(4,1)(5,4)}

B. T ={(5,3)(3,7)(2,3)(6,2)(4,1)(7,4)}

C. T ={(5,1)(3,5)(2,3)(6,2)(4,1)(7,4)}

D. T ={(4,7)(3,5)(2,3)(6,2)(4,1)(3,6)}

Câu 1: Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(2):

A. 2, 1, 3, 4, 5, 10, 6, 9, 7, 8

B. 2, 1, 7, 4, 3, 6, 8, 5, 9, 10

C. 2, 1, 3, 5, 4, 10, 6, 9, 7, 8

D. 2, 1, 7, 3, 6, 9, 4, 5, 8, 10 

Câu 2: Biểu thức \((P \wedge Q) \to (P \vee Q)\) tương đương logic với biểu thức nào sau đây?

A. \((P \wedge Q) \vee (P \vee Q)\)

B. \((P \wedge Q) \vee (\overline {P \vee Q} )\)

C. \((\overline {P \wedge Q} ) \vee (P \vee Q)\)

D. \((\overline {P \wedge Q} ) \wedge (P \vee Q)\)

Câu 3: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(I) là:

A. I, A, C, E, G, B, F, H, D, K, N

B.  I, C, E, F, G, K, H, N, B, D, A

C. I, G, B, F, N, K, E, C, D, H, A

D. I, G, H, N, K, B, A, C, E, F, D

Câu 4: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(I) là:

A. I, A, E, G, K, B, C, F, H, D

B.  I, A, E, G, C, K, B, F, H, D 

C. I, A, B, C, D, E, G, H, F, K

D.  I, A, B, D, E, G, C, F, H, K

Câu 5: Giả sử p1, p2, … , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, … , pn được gọi là một biểu thức hội cơ bản nếu nó có dạng?

A. \(F = {q_1} \vee {q_2} \vee ... \vee {q_n}\)  với  qj = pj hoặc \({q_j} = \overline {{p_j}} (j = 1,...,n)\)

B. \(F = {q_1} \vee {q_2} \vee ... \vee {q_n}\)

C. \(F = {q_1} \wedge {q_2} \wedge ... \wedge {q_n}\)

Câu 6: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(C) là:

A. C, A, B, E, F, D, G, H, K, C, N

B. C, A, B, K, N, I, D, E, F, H, G

C. C, A, E, G, B, D, F, H, K, I, N 

D. C, A, E, G, F, H, N, B, D, I, K