Free Printable Chương 6+ 7

1.

Cây là một đồ thị như thế nào?

a)

Đơn, liên thông và có chu trình

b)

Có chu trình

c)

Không liên thông

d)

Đơn, liên thông và không có chu trình

2.

Cho T là một cây có n đỉnh (n ≥ 2). Khẳng định nào sau đây đúng?

a)

T liên thông và có n cạnh

b)

T không có chu trình và có n cạnh

c)

T liên thông và có (n-1) cạnh

d)

T có chu trình và có (n-1) cạnh

3.

Cho T là một cây có gốc. Khẳng định nào sau đây đúng?

a)

Gốc có bậc vào bằng 1

b)

Lá có bậc ra khác 0

c)

Gốc có bậc vào bằng 0

d)

Lá có bậc ra bằng 1

4.

Cho T là một cây có gốc. Khẳng định nào sau đây đúng?

a)

Lá có bậc ra khác 0

b)

Lá có bậc ra bằng 0

c)

Gốc có bậc vào bằng 1

d)

Lá có bậc ra bằng 1

5.

Cây bao trùm ngắn nhất là gì?

a)

Cây bao trùm có trọng số lớn nhất

b)

Cây bao trùm có trọng số bé nhất

c)

Cây bao trùm của đồ thị

d)

Không có đáp án đúng

6.

Cho graph vô hướng G(V,E) với V = {a,b,c,d,e}; E = {ab,ac,ae, ad,bc,cd,de}. Trong đồ thị G, phương án nào sau đây đúng?

a)

Xóa cạnh bc,cd,de của G thì được cây bao trùm của G.

b)

Xóa cạnh bc,ab,ae của G thì được cây bao trùm của G.

c)

Xóa cạnh bc,ab,ac của G thì được cây bao trùm của G.

d)

Xóa cạnh ac,ad của G thì được cây bao trùm của G.

7.

Cho graph vô hướng G(V,E) với V = {a,b,c,d,e}; E = {ab,ac,ae, ad,bc,cd,de}. Trong đồ thị G, phương án nào sau đây đúng?

a)

Xóa cạnh bc,ab,ae của G thì được cây bao trùm của G.

b)

Xóa cạnh bc,ac,ad của G thì được cây bao trùm của G.

c)

Xóa cạnh bc,ab,ac của G thì được cây bao trùm của G.

d)

Xóa cạnh ac,ad của G thì được cây bao trùm của G.

8.

Cho graph vô hướng G(V,E) với V = {a,b,c,d,e}; E = {ab,ac,ae,ad,bc,cd,de}. Trong đồ thị G phương án nào sau đây là đúng?

a)

Xóa cạnh bc,ab,ae của G thì được cây bao trùm của G.

b)

Xóa cạnh bc,ab,ac của G thì được cây bao trùm của G.

c)

Xóa cạnh ac,ad của G thì được cây bao trùm của G.

d)

Xóa cạnh ab,ac,ad của G thì được cây bao trùm của G.

9.

Cho graph vô hướng G(V,E) với V = {a,b,c,d,e}; E = {ab,ac,ae,ad,bc,cd,de}. Trong đồ thị G phương án nào sau đây là đúng?

a)

Xóa cạnh bc,ad,ae của G thì được cây bao trùm của G.

b)

Xóa cạnh bc,ab,ae của G thì được cây bao trùm của G.

c)

Xóa cạnh bc,ab,ac của G thì được cây bao trùm của G.

d)

Xóa cạnh ac,ad của G thì được cây bao trùm của G.

10.

Cho graph vô hướng G(V,E) với V = {a,b,c,d,e}; E = {ab,ac,ae,ad,bc,cd,de}. Trong đồ thị G phương án nào sau đây là đúng?

a)

Xóa cạnh bc,ac,ae của G thì được cây bao trùm của G

b)

Xóa cạnh bc,ab,ae của G thì được cây bao trùm của G

c)

Xóa cạnh bc,ab,ac của G thì được cây bao trùm của G

d)

Xóa cạnh ac,ad của G thì được cây bao trùm của G

11.

Cho graph vô hướng G(V,E) với V = {a,b,c,d,e}; E = {ab,ac,ae,ad,bc,cd,de}. Trong đồ thị G phương án nào sau đây là đúng?

a)

Xóa cạnh bc,ab,ae của G thì được cây bao trùm của G.

b)

Xóa cạnh bc,ab,ac của G thì được cây bao trùm của G.

c)

Xóa cạnh cd,ac,ad của G thì được cây bao trùm của G.

d)

Xóa cạnh ac,ad của G thì được cây bao trùm của G.

12.

Cho graph vô hướng G(V,E) với V = {a,b,c,d,e}; E = {ab,ac,ae,ad,bc,cd,de}. Trong đồ thị G phương án nào sau đây là đúng?

a)

Xóa cạnh bc,ab,ae của G thì được cây bao trùm của G.

b)

Xóa cạnh bc,ab,ac của G thì được cây bao trùm của G.

c)

Xóa cạnh ac,ad của G thì được cây bao trùm của G.

d)

Xóa cạnh de,ac,ad của G thì được cây bao trùm của G.

13.

Ma trận kề là ma trận biểu diễn mối liên quan giữa:

a)

Đỉnh - Cạnh

b)

Đỉnh - Đỉnh

c)

Cạnh - Cạnh

d)

Không có đáp án đúng

14.

Số phần tử trên ma trận kề biểu diễn Graph G(V,E) bằng: (Qui ước: $|V|$ là số đỉnh của đồ thị, $|E|$ là số cạnh của đồ thị)

a)

$|V|\cdot|V|$

b)

$|E|\cdot|E|$

c)

$|V|\cdot|E|$

d)

$|V|+|E|$

15.

Số phần tử trên ma trận liên thuộc đỉnh cạnh biểu diễn Graph có hướng G(V,E) bằng: (Qui ước: $|V|$ là số đỉnh của đồ thị, $|E|$ là số cung của đồ thị)

a)

$|V|\cdot|V|$

b)

$|V|\cdot|E|$

c)

$|E|\cdot|E|$

d)

$|V|+|E|$

16.

Ma trận liên thuộc đỉnh cạnh chỉ sử dụng cho đồ thị:

a)

Vô hướng

b)

Có trọng số

c)

Có hướng

d)

Có hướng và có trọng số

17.

Với đồ thị vô hướng G(V,E), nếu sử dụng phương pháp danh sách kề để lưu giữ đồ thị thì số ô nhớ máy tính cần sử dụng là: (Qui ước: $|V|$ là số đỉnh của đồ thị, $|E|$ là số cạnh của đồ thị)

a)

$|E|$

b)

$|V|$

c)

$|V|\cdot|E|$

d)

$2|E|$

18.

Với đồ thị có hướng G(V,E), nếu sử dụng phương pháp danh sách kề để lưu giữ đồ thị thì số ô nhớ máy tính cần sử dụng là: (Qui ước: $|V|$ là số đỉnh của đồ thị, $|E|$ là số cung của đồ thị)

a)

$|V|$

b)

$|E|$

c)

$|V|+|E|$

d)

$2|E|$

19.

Với đồ thị có hướng G(V,E), nếu sử dụng phương pháp danh sách cạnh để lưu giữ đồ thị thì số ô nhớ máy tính cần sử dụng là: (Qui ước: $|V|$ là số đỉnh của đồ thị, $|E|$ là số cung của đồ thị)

a)

$|V|$

b)

$|E|$

c)

$|V|+|E|$

20.

Với đồ thị có hướng G(V,E), nếu biểu diễn bằng ma trận kề thì số phần tử khác không bằng: (Qui ước: $|V|$ là số đỉnh của đồ thị, $|E|$ là số cung của đồ thị)

a)

$|E|$

b)

$|V|$

c)

$|V|+|E|$

d)

$2|E|$

21.

Với đồ thị đơn vô hướng, nếu biểu diễn bằng ma trận kề thì số phần tử bằng 1 bằng: (Qui ước: $|V|$ là số đỉnh của đồ thị, $|E|$ là số cạnh của đồ thị)

a)

$2|V|$

b)

$|E|$

c)

$|V|+|E|$

d)

$2|E|$

22.

Trong ma trận liên thuộc đỉnh–cạnh, mỗi phần tử trên ma trận có thể nhận mấy giá trị?

a)

2

b)

1

c)

4

d)

3

23.

Trong ma trận kề biểu diễn đồ thị vô hướng, bậc của một đỉnh bằng:

a)

Tổng số phần tử khác 0 trên hàng hoặc trên cột tương ứng

b)

Tổng số phần tử bằng 0 trên hàng và trên cột tương ứng

c)

Tổng số phần tử bằng 0 trên hàng tương ứng

d)

Tổng số phần tử bằng 0 trên cột tương ứng

24.

Cho $V=\{2,3,4,5,6\}$ ; $E=\{(u,v)\mid u,v$ thuộc $V$ ; $u<v$ và nguyên tố cùng nhau\}. Ma trận kề biểu diễn graph có hướng $G(V,E)$ có bao nhiêu phần tử?

a)

24

b)

20

c)

25

d)

15

25.

Cho $V=\{2,3,4,5,6\}$ ; $E=\{(u,v)\mid u,v$ thuộc $V$ ; $u<v$ và nguyên tố cùng nhau\}. Ma trận kề biểu diễn graph có hướng $G(V,E)$ có bao nhiêu phần tử bằng 0?

a)

19

b)

18

c)

20

d)

15

26.

Cho $V=\{2,3,4,5,6\}$ ; $E=\{(u,v)\mid u,v$ thuộc $V$ ; $u<v$ và nguyên tố cùng nhau\}. Ma trận kề biểu diễn graph có hướng $G(V,E)$ có bao nhiêu phần tử khác 0?

a)

8

b)

6

c)

0

d)

5

27.

Cho V={2,3,4,5,6}; E={(u,v) / u,v thuộc V; u < v và nguyên tố cùng nhau}. Ma trận liên thuộc đỉnh-cạnh biểu diễn Graph có hướng G(V,E) có bao nhiêu phần tử khác 0?

a)

10

b)

5

c)

9

d)

12

28.

Cho V={2,3,4,5,6}; E={(u,v) / u,v thuộc V; u < v và nguyên tố cùng nhau}. Ma trận liên thuộc đỉnh-cạnh biểu diễn Graph có hướng G(V,E) có bao nhiêu phần tử bằng 0?

a)

10

b)

18

c)

16

d)

12

29.

Cho V={2,3,4,5,6}; E={(u,v) | u,v V; u< v và nguyên tố cùng nhau}. Trên đường chéo chính của ma trận kề biểu diễn Graph có hướng G(V,E) có bao nhiêu phần tử bằng 0?

a)

12

b)

6

c)

5

d)

9

Chương 6+ 7

Total questions: 29

Worksheet time: 15mins

Similar Resources on Wayground