1、（12） n个顶点的完全无向图有 n（n-1）/2_ 条边。（13） 有向图的邻接表表示适于求顶点的 出度 。（14） 有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点Vi的 入度 。（15） 对于具有n个顶点的图，其生成树有且仅有 n-1 条边。（16） 对n个顶点，e条弧的有向图，其邻接表表示中，需要 n+e 个结点。（17） 从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的 遍历 。（18） 无向图的邻接矩阵一定是 对称 矩阵。（19） 一个连通网的最小生成树是该图所有生成树中 权 最小的生成树。（20） 若要求一个稠密图G的最小生成树，最好用 Pri
2、m 算法来求解。三选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（ C ）倍。 A1/2 B. 1 C. 2 D. 4（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。 A1/2 B. 1 C. 2 D. 4（3）对于一个具有n个顶点的有向图的边数最多有（ B ）。 An Bn（n-1） Cn（n-1）/2 D2n（4）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。 An Bn+1 C n-1 Dn/2（5）有8个结点的有向完全图有（ C ）条边。 A14 B. 28 C. 56 D. 112（6）深度优先遍历类似于二叉树的（ A ）
3、。 A先序遍历 B中序遍历 C后序遍历 D层次遍历（7）广度优先遍历类似于二叉树的（ D ）。（8）任何一个无向连通图的最小生成树（ A ）。 A只有一棵 B一棵或多棵 C一定有多棵 D可能不存在（9）无向图顶点v的度是关联于该顶点（ B ）的数目。 A顶点 B边 C序号 D下标（10）有n个顶点的无向图的邻接矩阵是用（ B ）数组存储。 A一维 Bn行n列 C任意行n列 Dn行任意列（11）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（ C ）。 An-1 Bn+1 Cn Dn+e（12）在图的表示法中，表示形式唯一的是（ A ）。 A邻接矩阵表示法 B邻接表表示法
4、 C逆邻接表表示法 D邻接表和逆邻接表表示法（13）在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（ C ）。 An Be C 2n D2e（14）下列图中，度为3的结点是（ B ）。 AV1 B. V2 C. V3 D. V4（15）下列图是（ A ）。 A连通图 B. 强连通图 C. 生成树 D. 无环图（16）如下图所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（ D ）。A a，b，e，c，d，fB a，c，f，e，b，dC. a，e，b，c，f，dD. a，e，d，f，c，b（17）如下图所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（
5、 A ）。A. a，b，e，c，d，fB. a，b，e，c，f，d（18）最小生成树的构造可使用（ A ）算法。 Aprim算法 B卡尔算法 C哈夫曼算法 D迪杰斯特拉算法（19）下面关于图的存储结构的叙述中正确的是（ A ）。A 用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关B 用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关 C 用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关 D 用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关（20）连通分量是（ C ）的极大连通子图。 A树 B图 C无向图 D有向图四应用题（30分）1有向图如下图
6、所示，画出邻接矩阵和邻接表解：（1）邻接矩阵 1 2 3 4 5（2）邻接表123542 已知一个无向图有6个结点，9条边，这9条边依次为（0，1）,（0，2）,（0，4）,（0，5），（1，2），（2，3），（2，4），（3，4），（4，5）。试画出该无向图，并从顶点0出发，分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。（5分）从顶点0出发的深度优先搜索遍历的结点序列：0 1 2 3 4 5（答案不唯一）从顶点0出发的广度优先搜索遍历的结点序列：0 1 2 4 5 3（答案不唯一）3 已知一个无向图的顶点集为：a，b，c，d，e，其邻接矩阵如下，画出草图，写出顶点a出发按深度优先
7、搜索进行遍历的结点序列。（1） （2）深度优先搜索：a b d c e （答案不唯一） 广度优先搜索： a b e d c （答案不唯一） 4网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。 最小生成树： 8 11 10 8 3 4 13 7 3 4 75. 已知某图G的邻接矩阵如图，（1）画出相应的图；（2）要使此图为完全图需要增加几条边。（1）（2） 完全无向图应具有的边数为：n*（n-1）1/2=4*（4-1）/2=6，所以还要增加2条边（如右图）。6已知如图所示的有向图，请给出该图的:（1） 每个顶点的入/出度；（2） 邻接表；（3） 邻接矩阵。（1） （2）顶点6入度出度（
8、3）7如图，请完成以下操作：（2） 写出无向带权图的邻接矩阵；（3） 设起点为a，求其最小生成树。 （1）邻接矩阵为： （2）起点为a，可以直接由原始图画出最小生成树8给定下列网G:（1） 画出网G的邻接矩阵；（2） 画出网G的最小生成树。（1）邻接矩阵 （2）最小生成树五程序题填空题图G为有向无权图，试在邻接矩阵存储结构上实现删除一条边（v,w）的操作：DeleteArc（G,v,w）。若无顶点v或w，返回“ERROR”；若成功删除，则边数减1，并返回“OK”。（提示：删除一条边的操作，可以将邻接矩阵的第i行全部置0 ）Status DeleteArc（MGraph &G,char v,ch
9、ar w） dj） ij.adj= 0 ; - ; （或 = ） return OK ; 六算法题1 编写一个无向图的邻接矩阵转换成邻接表的算法。2 以知有n个顶点的有向图邻接表，设计算法分别实现以下功能：（1）求出图G中每个顶点的出度、入度。（2）求出G中出度最大的一个顶点，输出其顶点序号。（3）计算图中度为0的顶点数。1 解：本题思想是逐个扫描邻接矩阵的各个元素，若第i行第j列的元素为1，则相应的邻接表的第i个单链表上增加一个j结点。void trans（int edgesnn,Adjlist adj） int i,j; edgenode *p; for （i=0;in;i+） adji.
10、data=i; adji.link=NULL; for （j=0;jadjvex=j;next=adji.link; adji.link=p; 2（1）求出度的思想：计算出邻接表中第i个单链表的结点数即可。int outdegree（adjlist adj,int v） int degree=0; p=adjv.link; while （p!=NULL） degree+; p=p-next; return degree;void printout（adjlist adj,int n） int i,degree; printf（The Outdegree are:n）; for（i=0; deg
11、ree=outdegree（adj,i）; printf（%d,%d）,i,degree）; 求入度的思想：计算出邻接表中结点i的结点数即可。int indegree（adjlist adj,int n,int v） int i,j,degree=0; p=adji.link; while （p! if （p-adjvex=v） degree+; p=p-void printin（adjlist adj,int n）The Indegree are: degree=Indegree（adj,n,i）;（2）求最大度的算法void maxoutdegree（adjlist adj,int n）
12、int maxdegree=0,maxv=0,degree,i; degree=outdegree（adj,i）; if （degreemaxdegree） maxdegree=degree; maxv=i;maxoutdegree %d,maxvertex=%d,maxdegree,maxv）;（3）求度为0的顶点数的算法int outzero（adjlist adj,int n） int num=0,i; if （outdegree（adj,i）=0） num+; return num;模拟考题1 已知如图所示的有向图，请给出该图的:（1） 每个顶点的入度和出度；（2） 逆邻接表。2 给定
13、下列网G:（1） 写出网G以B为顶点的广度优先遍历的序列；（1）以B为顶点的广度优先遍历的序列： （2）最小生成树 B A E F C G D3 无向图G如图所示，（1）试画出邻接矩阵；（2）写出从A出发的深度优先遍历的序列。（1） 邻接矩阵 （2）从A出发的深度优先遍历的序列： A B D C E G F（不唯一）3 已知图G的邻接表如下，以顶点1为出发点，完成下列问题：（1）写出以顶点1为出发点的广度优先遍历序列；（2）画出以顶点1为出发点的深度优先搜索得到的一棵二叉树。（1）广度优先遍历序列：1，2，5，4，3 （2）深度优先搜索得到的一棵二叉树：5 试填空完成深度优先搜索的递归函数。#
14、define MAXVEX 100 / 定义图的最大顶点数struct vertex int num; / 顶点编号 char data; / 顶点的信息;typedef struct graph struct vertex vexsMAXVEX; / 顶点集合 int edgesMAXVEX MAXVEX; / 边的集合sdjmax;int visitedMAXVEX;void dfs（adjlist adj,int v） / 深度优先搜索的递归函数 int i; struct edgenode *p; for （i=1;=n;i+） visitedi=0; / 给visited数组赋初值0visitedv=1; cin v; / 取v的边的表头指针 p= adjv-link ; while （ p!=NULL ） if （visitedp-adjvex= 0 ） / 从v的未访问过的邻接点出发进行深度优先搜索 dfs（adjlist, p-adjvex ）; p= p-next ; / 找v的下一个邻接点
