Kiểm tra phần đồ thị môn Kinh tế vĩ mô | Trường Đại học Kinh doanh và Công nghệ Hà Nội

lOMoAR cPSD| 47270246
Câu 1: Bậc của một đỉnh trong đồ thị vô hướng là: a.
Số cạnh đi qua đỉnh đó
b. Số cung đi vào đỉnh đó
c. Số cung đi ra đỉnh đó
d. Tổng của bậc ra và bậc vào
Câu 2: Bậc của một đỉnh trong đồ thị có hướng là: a.
Tổng của bậc ra và bậc vào tại đỉnh đó
b. Số cạnh đi qua đỉnh đó
c. Số cung đi ra từ đỉnh đó
d. Số cung đi vào đỉnh đó Câu 3: Khuyên là gì?
a. Là đường đi từ một đỉnh đến chính nó
b. Là đường đi từ một đỉnh đến một đỉnh khác
c. Là một đường đi qua tối thiểu 3 cạnh
d. Là một đường đi qua tối thiểu 3 đỉnh Câu 4: Đường đi sơ cấp là:
a. Là đường đi không lặp lại đỉnh
b. Là đường đi lặp lại đỉnh
c. Là đường đi lặp lại đỉnh và lặp lại cạnh
d. Là đường đi lặp lại đỉnh và không lặp lại cạnh Câu 5: Đường đi đơn giản là:
a. Là đường đi không lặp lại cạnh
b. Là đường đi lặp lại cạnh
c. Là đường đi qua tất cả các cạnh
d. Là đường đi lặp lại cạnh và lặp lại đỉnh Câu 6: Chu trình là gì?
a. Là một đường đi xuất phát từ một đỉnh kết thúc tại chính đỉnh đó và đi qua tối thiểu 3 cạnh
b. Là một đường đi từ một đỉnh và kết thúc tại đỉnh đó
c. Là một đường đi xuất phát từ một đỉnh kết thúc tại một đỉnh khác và đi qua tối thiểu 3 cạnh
d. Là một đường qua tối thiểu 3 cạnh Câu 7: Chu trình sơ cấp là gì?
a. Là một chu trình không lặp lại đỉnh
b. Là một chu trình lặp lại đỉnh
c. Là một chu trình lặp lại đỉnh và lặp lại cạnh
d. Là một chu trình lặp lại cạnh Câu 8: Chu trình đơn giản là gì? lOMoAR cPSD| 47270246
a. Là một chu trình không lặp lại cạnh
b. Là một chu trình lặp lại cạnh
c. Là một chu trình lặp lại cạnh và lặp lại đỉnh
c. Là một chu trình lặp lại cạnh và không lặp lại đỉnh
Câu 9: Đỉnh cô lập là: a. Đỉnh có bậc bằng 0 b. Đỉnh có bậc bằng 1 c. Đỉnh có bậc khác 0
d. Đỉnh có bậc bằng 2 Câu 10: Đỉnh treo là: a. Đỉnh có bậc bằng 1 b. Đỉnh có bậc bằng 0 c. Đỉnh có bậc khác 0
d. Đỉnh có bậc bằng 2 Câu 11: Nếu đỉnh u có bậc bằng 0 thì: a. Tất cả các đáp án sau đều đúng
b. u là đỉnh không tồn tại đường đi đến bất kì đỉnh nào c. u là đỉnh cô lập
d. Không có đỉnh nào kề với u Câu 12: Đồ thị đều là gì?
a. Là đồ thị mà mọi đỉnh đều cùng bậc
b. Là đồ thị mà mọi đỉnh đều kề nhau
c. Là đồ thị liên thông
d. Là đồ thị có khuyên Câu 13: Đồ thị đầy đủ là gì?
a. Là đồ thị mà mọi đỉnh đều kề nhau
b. Là đồ thị mà mọi đỉnh đều cùng bậc
c. Là đồ thị có khuyên
d. Là đồ thị liên thông
Câu 14: Đơn đồ thị vô hướng là:
a. Đồ thị không có khuyên và giữa hai đỉnh kề nhau chỉ tồn tại duy nhất một đường đi trực tiếp b. Đồ thị có khuyên
c. Đồ thị không có khuyên
d. Đồ thị có khuyên và giữa hai đỉnh kề nhau chỉ tồn tại duy nhất một đường đi trực tiếp
Câu 15: Cầu của đồ thị là gì?
a. Là cạnh mà khi bỏ cạnh đó đi đồ thị đang liên thông trở nên không liên thông
b. Là cạnh mà khi thêm cạnh đó vào đồ thị đang không liên thông trở nên liên thông lOMoAR cPSD| 47270246
c. Là cạnh mà khi bỏ cạnh đó đi đồ thị vẫn liên thông
d. Là cạnh bất kì của đồ thị Câu 16: Khớp của đồ thị là gì?
a. Là đỉnh mà khi bỏ đỉnh đó đi đồ thị đang liên thông trở nên không liên thông
b. Là đỉnh mà khi thêm đỉnh đó vào đồ thị đang không liên thông trở nên liên thông
c. Là đỉnh mà khi bỏ đỉnh đó đi đồ thị vẫn liên thông
d. Là đỉnh bất kì của đồ thị Câu 17: Đường đi Euler là:
a. Đường đi qua tất cả các cạnh mỗi cạnh chỉ qua duy nhất một lần
b. Đường đi lặp lại cạnh
c. Đường đi lặp lại cạnh và không lặp lại đỉnh
d. Đường đi lặp lại cạnh và lặp lại đỉnh Câu 18: Chu trình Euler là:
a. Chu trình đi qua tất cả các cạnh mỗi cạnh chỉ qua duy nhất một lần
b. Chu trình lặp lại cạnh
c. Chu trình đi qua tất cả các cạnh
d. Chu trình lặp lại cạnh và không lặp lại đỉnh
Câu 19: Điều kiện để một đồ thị vô hướng có chu trình Euler là: a.
Đồ thị liên thông và mọi đỉnh đều có bậc chẵn
b. Đồ thị mà mọi đỉnh đều có bậc chẵn
c. Đồ thị liên thông và mọi đỉnh đều có bậc lẻ d. Đồ thị liên thông
Câu 20: Điều kiện để đồ thị vô hướng có đường đi Euler là:
a. Đồ thị liên thông và có hai đỉnh bậc lẻ, các đỉnh còn lại có bậc chẵn b. Đồ thị liên thông
c. Đồ thị có đúng hai đỉnh bậc lẻ
d. Đồ thị mà mọi đỉnh đều có bậc chẵn
Câu 21: Ma trận kề là ma trận biểu diễn mối liên quan giữa: a. Đỉnh - Đỉnh b. Đỉnh - Cạnh c. Cạnh - Cạnh
d. Không có đáp án đúng
Câu 22: Dựa vào ma trận kề để tính bậc của một đỉnh trong đồ thị đơn vô hướng: a.
Tính tổng phần tử bằng 1 trên hàng hoặc cột tương ứng lOMoAR cPSD| 47270246
b. Tính tổng phần tử bằng 0 trên hàng hoặc cột tương ứng c. Không tính được
d. Không có đáp án đúng
Câu 23: Nếu sử dụng ma trận kề để lưu giữ đồ thị thì số phần tử trên ma trận kề bằng: a. |V|.|V| b. |E|.|E| c. |V|.|E| d. |V|+|E|
Câu 24: Ma trận liên thuộc đỉnh cạnh chỉ sử dụng cho đồ thị: a. Có hướng b. Vô hướng c. Có trọng số
d. Có hướng và có trọng số
Câu 25: Ma trận liên thuộc đỉnh cạnh biểu diễn mối quan hệ giữa: a. Đỉnh - Cạnh b. Đỉnh - Đỉnh c. Cạnh - Cạnh
d. Không có đáp án đúng
Câu 26: 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. 3 b. 2 c. 1 d. 4
Câu 27: Nếu sử dụng ma trận liên thuộc đỉnh cạnh để lưu giữ đồ thị thì số phần tử trên ma
trận liên thuộc đỉnh cạnh bằng: a. |V|.|E| c. |V|.|V| c. |E|.|E| d. |V|+|E|
Câu 28: 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à: a. 2|E| lOMoAR cPSD| 47270246 b. |E| c. |V| d. |V|.E|
Câu 29: Với đồ thị vô hướng, 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à: a. 2|E| b. |E| c. |V| d. |V|.|E|
Câu 30: Với đồ thị có hướng, 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à: a. |E| b. |V| c. |V|+|E| d. 2|E|
Câu 31: Trên ma trận liên thuộc đỉnh cạnh biểu diễn đồ thị có hướng số phần tử bằng 1 bằng: a. |E| b. |V| c. |V|+|E| d. 2|E|
Câu 32: Trên ma trận liên thuộc đỉnh cạnh biểu diễn đồ thị có hướng số phần tử bằng -1 bằng: a. |E| b. |V| c. |V|+|E| d. 2|E|
Câu 33: Với đồ thị có hướng, nếu biểu diễn bằng ma trận kề thì số phần tử khác không bằng: a. |E| b. |V| c. |V|+|E| lOMoAR cPSD| 47270246 d. 2|V|
Câu 34: 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: a. 2|E| b. 2|V| c. |E| d. |V|+|E|
Câu 35: Trên 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ử khác 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
Câu 36: Graph G(V,E) với V={a,b,c,d,e}, E={ab,ac,bc,bd,ad}. Bậc của các đỉnh tương ứng
trong G(V,E) là: a. 3-3-2-2-0 b. 1-2-3-4-0 c. 3-2-3-2-0 d. 2-3-1-2-0
Câu 37: Graph G(V,E) với V={a,b,c,d,e}, E={ab,ac,bc,bd,ad}. Đồ thị G(V,E) có mấy đỉnh cô lập? a. 1 b. 2 c. 3 d. 0
Câu 38: Graph G(V,E) với V={a,b,c,d,e}, E={ab,ac,bc,bd,ad}. Đồ thị G(V,E) có mấy khuyên? a. 0 b. 1 c. 2 d. 3
Câu 39: Graph G(V,E) với V={a,b,c,d,e}, E={ab,ac,bc,bd,ad}. Đồ thị G(V,E) có mấy đỉnh treo? a. 0 b. 2 lOMoAR cPSD| 47270246 c. 3 d. 1
Câu 40: Graph G(V,E) với V={a,b,c,d,e}, E={ab,ac,bc,bd,ad}. Đồ thị G(V,E) có mấy đỉnh bậc lẻ? a. 2 b. 3 c. 1 d. 4
Câu 41: Graph G(V,E) với V={a,b,c,d,e}, E={ab,ac,bc,bd,ad}. Đồ thị G(V,E) có mấy đỉnh bậc chẵn? a. 3 b. 2 c. 1 d. 4
Câu 42: Graph G(V,E) với V={a,b,c,d,e}, E={ab,ac,bc,bd,ad}. Bậc của đồ thị G(V,E) bằng: a. 10 b. 5 c. 8 d. 6
Câu 43: Graph G(V,E) với V={a,b,c,d,e}, E={ab,ac,bc,bd,ad}. Đồ thị G(V,E) có mấy khớp? a. 0 b. 3 c. 1 d. 2
Câu 44: Graph G(V,E) với V={a,b,c,d,e}, E={ab,ac,bc,bd,ad}. Khẳng định nào sau đây sai?
a. Đồ thị có đường đi Eurle
b. Đồ thị không có đường đi Eurle
c. Đồ thị không có chu trình Eurle
d. Đồ thị không liên thông
Câu 45: Graph G(V,E) với V={a,b,c,d,e}, E={ab,ac,bc,bd,ad}. Khẳng định nào sau đây đúng?
a. Đồ thị không có chu trình Euler lOMoAR cPSD| 47270246
b. Đồ thị có chu trình Euler
c. Đồ thị có đường Euler d. Đồ thị liên thông
Câu 46: Graph G(V,E) được cho theo danh sách kề như sau: a (b,d), b (a,c,d,e), c (b,e) , d (
a,b,e), e (b,c,d). Trong G(V,E) có bao nhiêu đường đi sơ cấp từ a đến e? a. 6 b. 4 c. 5 d. 8
Câu 47: Graph G(V,E) được cho theo danh sách kề như sau: a(b,d), b(a,c,d,e), c(b,e),
d(a,b,e), e(b,c,d). Graph G(V,E) có bao nhiêu cạnh ? a. 7 b. 10 c. 8 d. 6
Câu 48: Graph G(V,E) được cho theo danh sách kề như sau: a(b,d), b(a,c,d,e), c(b,e),
d(a,b,e), e(b,c,d). Trong G(V,E) có bao nhiêu đường đi sơ cấp từ c đến d? a. 6 b. 9 c. 5 d. 7
Câu 49: Graph G được cho theo danh sách kề như sau: a(b,d), b(a,c,d,e), c(b,e), d(a,b,e),
e(b,c,d). Trong G(V,E) đường đi sơ cấp dài nhất từ c đến d không đi qua các đỉnh nào? a. Đỉnh nào cũng qua b. a và e c. e d. b
Câu 50: Graph G(V,E) được cho theo danh sách kề như sau: a(b,d) , b(a, c, d, e), c(b,e),
d(a, b, e), e(b,c,d). Ma trận biểu diễn G(V,E) có bao nhiêu phần tử khác không? a. 14 b. 15 c. 8 lOMoAR cPSD| 47270246 d. 11
Câu 51:Graph G(V,E) với V={-1,0,1,2,4,5,25}; E = {(u,v)/ u,v thuộc V; v=u^2}. Ma trận kề
biểu diễn Graph có hướng G(V,E) có bao nhiêu phần tử? a. 49 b. 35 c. 20 d. 28
Câu 52: Graph G(V,E) với V={-1,0,1,2,4,5,25}; E = {(u,v)/ u,v thuộc V; v=u^2}. 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. 44 b. 49 c. 21 d. 14
Câu 53: Graph G(V,E) với V={-1,0,1,2,4,5,25}; E = {(u,v)/ u,v thuộc V; v=u^2}. 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. 5 b. 49 c. 7 d. 14
Câu 54: Graph G(V,E) với V={-1,0,1,2,4,5,25}; E = {(u,v)/ u,v thuộc V; v=u^2}. 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ử? a. 35 b. 20 c. 14 d. 49
Câu 55: Graph G(V,E) với V={-1,0,1,2,4,5,25}; E = {(u,v)/ u,v thuộc V; v=u^2}. 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 1? a. 5 b. 8 c. 7 d. 10
Câu 56: Graph G(V,E) với V={-1,0,1,2,4,5,25}; E = {(u,v)/ u,v thuộc V; v=u^2}. 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 -1? a. 5 b. 7 c. 3 lOMoAR cPSD| 47270246 d. 10
Câu 57: Graph G(V,E) với V={-1,0,1,2,4,5,25}; E = {(u,v)/ u,v thuộc V; v=u^2}. 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. 25 b. 24 c. 30 d. 27
Câu 58:Graph G(V,E) với V={-1,0,1,2,4,5,25}; E = {(u,v)/ u,v thuộc V; v=u^2}. Graph có
hướng G(V,E) có mấy khuyên? a. 2 b. 1 c. 3 d. 0
Câu 59:Graph G(V,E) với V={-1,0,1,2,4,5,25}; E = {(u,v)/ u,v thuộc V; v=u^2}. Bậc của
Graph có hướng G(V,E) bằng: a. 10 b. 14 c. 8 d. 12
Câu 60: Graph G(V,E) với V={-1,0,1,2,4,5,25}; E = {(u,v)/ u,v thuộc V; v=u^2}. Graph có
hướng G(V,E) có mấy đỉnh treo? a. 5 b. 4 b. 0