[单项选择]无向图的邻接矩阵一定是（）。
A. 对角矩阵
B. 稀疏矩阵
C. 三角矩阵
D. 对称矩阵

[单项选择]无向图的邻接矩阵一定是 (40) 。
A. 稀疏矩阵
B. 对称矩阵
C. 对角矩阵
D. 三角矩阵

[单项选择]无向图中一个顶点的度是指图中______。
A. 通过该顶点的简单路径数
B. 通过该顶点的回路数
C. 与该顶点相邻的顶点数
D. 与该顶点连通的顶点数

[单项选择]无向图的邻接矩阵是
A. 对角矩阵
B. 稀疏矩阵
C. 上三角矩阵
D. 对称矩阵

[单项选择]具有6个顶点的无向图至少应有 (39) 条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8

[单项选择]若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个( )。
A. 上三解矩阵
B. 稀疏矩阵
C. 对角矩阵
D. 对称矩阵

[单项选择]在一个无向图中，所有顶点的度数之和等于所有边数的多少倍
A. 3
B. 2
C. 1
D. 1/2

[单项选择]在一个无向图中，所有顶点的度数之和等于所有边敷的多少倍
A. 3
B. 2
C. 1
D. 1/2

[填空题][说明]
所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。
应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。
函数中使用的预定义符号如下：
#define M 100
typedef struct/为两端点p1、p2之间的距离, p1、p2所组成边的长度*/
float x;
int p1, p2;
tdr;
typedef struct/*p1、p2为和端点相联系的两个端点, n为端点的度*/
int n, p1, p2;
tr;
typedef struct /*给出两点坐标*/
float x, y;
tpd;
typedef int t1[M];
int n = 10;
[函数]
float distance(tpd a, tpd b);/*计算端点a、b之间的距离*/
void sortArr(tdr a[M], int m);
/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表, m为边的条数*/
int isCircuit(tr r[M], int i, int j);
/*判断边(i, J)选入端点关系表r[M]后，是否形成回路, 若形成回路返回0*/
void selected(tr r[M], int i, int j);/*边(i，J)选入端点关系表r*/
void course(tr r[M], t1 1 [W]);/*从端点关系表r中得出回路轨迹表*/
void exchange(tdr a[M], int m, int b);
/*调整表排序表, b表示是否可调, 即是否有长度相同的边存在*/
void travling(tpd pd[M], int n, float dist, t1 locus[M])
/*dist记录总路程

[单项选择]如下所示是一个带权连通无向图，其最小生成树各边权的总和为
A. 24
B. 25
C. 26
D. 27

[简答题]编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。

[单项选择]若G是一个具有36条边的非连通无向图（不含自回路和多重边），则图G至少有（）个顶点。
A. 11
B. 10
C. 9
D. 8

[填空题]在图的邻接表表示中，每个顶点邻接表中的顶点数，对于有向图来说是______，对于无向图来说是______。

[单项选择]在无向图G中，节点间的连通关系是一个二元关系，该关系是 (43) 关系。
A. 偏序
B. 反对称
C. 等价
D. 反传递

[单项选择]具有10个顶点的无向图最多有（）条边。
A. 0
B. 9
C. 10
D. 45

[简答题][说明]
Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图，令T是由G的顶点构成的于图，Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树：初始时，T中的点互相不连通；考察G的边集E中的每条边，若它的两个顶点在T中不连通，则将此边添加到T中，同时合并其两顶点所在的连通分量，如此下去，当添加了n-1条边时，T的连通分量个数为1，T便是G的一棵最小生成树。
下面的函数void Kruskal(EdgeType edges[],int n)利用Kruskal算法，构造了有n个顶点的图 edges的最小生成树。其中数组father[]用于记录T中顶点的连通性质：其初值为father[i]=-1 (i=0,1,…,n-1)，表示各个顶点在不同的连通分量上；若有father[i]=j，j＞-1，则顶点i，j连通；函数int Find(int father[],int v)用于返回顶点v所在树形连通分支的根结点。
[函数]
#define MAXEDGE 1000
typedef struct
int v1;
int v2;
EdgeType;
void Kruskal(EdgeType edges[],int n)
int father[MAXEDGE];
int i,j,vf1,vt2;
for(i=0;i＜n;i+ +) father[i]=-1;
i=0;
j=0;
while(i＜MAXEDGE && j＜ (1) )
vf1=Find(father,edges[i].v1);
vf2=Find(father,edges[i].v2);
if( (2) )
(3) =vf1;
(4) ;
printf("%3d%3d/n",edges[i].v1,edges[i].v2);

(5) ;
int Find(int father[],int v)
int t;
t=v;
while

[单项选择]若一个具有n个结点、k条边的非连通无向图是一个森林（n＞k），则该森林中必有（）棵树。
A. k
B. n
C. n-k
D. n+k

[多项选择]箭条图是一张有向无环图，由（）组成。
A. 节点
B. 事件
C. 作业活动
D. 方案