数据结构习题与答案图

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构习题与答案图第7章图

一、单选题

01、在一个图中，全部顶点的度数之和等于图的边数的倍。A．1/2B．1C．2D．4

02、在一个有向图中，全部顶点的入度之和等于全部顶点的出度之和的倍。

A．1/2B．1C．2D．4

03、有8个结点的无向图最多有条边。

A．14B．28C．56D．112

04、有8个结点的无向连通图最少有条边。

A．5B．6C．7D．8

05、有8个结点的有向彻低图有条边。

A．14B．28C．56D．112

06、用邻接表表示图举行广度优先遍历时，通常是采纳来实现算法的。

A．栈B．队列C．树D．图

07、用邻接表表示图举行深度优先遍历时，通常是采纳来实现算法的。

A．栈B．队列C．树D．图

08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时光复杂度为。A．O(n)B．O(e)C．O(n+e)D．O(n2)

09、已知图的邻接矩阵，按照算法思想，则从顶点0动身按深度优先遍历的结点序列是。

A．0243156B．0136542

C．0134256D．0361542

10、已知图的邻接矩阵同上题，按照算法，则从顶点0动身，按广度优先遍历的结点序列是。

A．0243651B．0123456

C．0423156D．0134256

11、已知图的邻接表如下所示，按照算法，则从顶点0动身按深度优先遍历的结点序列是。

A．0132B．0231C．0321D．012312、已知图的邻接表如下所示，按照算法，则从顶点0动身按广度优先遍历的结点序列是。

A．0321B．0123C．0132D．031213、图的深度优先遍历类似于二叉树的。

A．先序遍历B．中序遍历C．后序遍历D．层次遍历14、图的广度优先遍历类似于二叉树的。

A．先序遍历B．中序遍历C．后序遍历D．层次遍历15、任何一个无向连通图的最小生成树。

A．惟独一棵B．一棵或多棵

C．一定有多棵D．可能不存在

()16、对于一个具有n个结点和e条边的无向图，若采纳邻接表表示，则顶点表的大小为，全部边链表中边结点的总数为。

A．n、2eB．n、eC．n、n+eD．2n、2e

17、推断有向图是否存在回路，可以利用算法。

A．关键路径B．最短路径的DijkstraC．拓扑排序D．广度优先遍历

18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。

A．图中每个顶点的入度B．图中每个顶点的出度

C．图中弧的条数D．图中连通重量的数目

19、求最短路径的Dijkstra算法的时光复杂度是___。A．O(n)B．O(n+e)C．O(n2)D．O(n*e)

20、设图G采纳邻接表存储，则拓扑排序算法的时光复杂度为。

A．O(n)B．O(n+e)C．O(n2)D．O(n*e)

21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。

A．第i行非∞的元素之和

B．第i列非∞的元素之和

C．第i行非∞且非0的元素个数

D．第i列非∞且非0的元素个数

22、一个有n个顶点的无向图最多有条边。

A．nB．n(n-1)C．n(n-1)/2D．2n

23、对于一个具有n个顶点的无向图，若采纳邻接矩阵表示，则该矩阵的大小是。

A．nB．(n-1)2C．n-1D．n2

24、对某个无向图的邻接矩阵来说，。

A．第i行上的非零元素个数和第i列的非零元素个数一定相等

B．矩阵中的非零元素个数等于图中的边数

C．第i行上，第i列上非零元素总数等于顶点vi的度数D．矩阵中非全零行的行数等于图中的顶点数

25、已知图的表示如下，若从顶点a动身按深度搜寻法举行遍历，则可能得到的一种顶点序列为。

A．abecdfB．acfebdC．aebcfdD．aedfcb26、已知图的表示如上题，若从顶点a动身按广度搜寻法举行遍历，则可能得到的一种顶点序列为。

A．abcedfB．abcefdC．aebcfdD．acfdeb

27、有向图的邻接表存储结构如下图所示，则按照有向图的

深度遍历算法，从顶点v1动身得到的顶点序列是。

A．v1,v2,v3,v5,v4B．v1,v2,v3,v4,v5C．v1,v3,v4,v5,v2D．v1,v4,v3,v5,v2

28、有向图的邻接表存储结构如上题所示，则按照有向图的

广度遍历算法，从顶点v1动身得到的顶点序列是。

A．v1,v2,v3,v4,v5B．v1,v3,v2,v4,v5

C．v1,v2,v3,v5,v4D．v1,v4,v3,v5,v2

29、一个图中有n个顶点且包含k个连通重量，若按深度优

先搜寻办法拜访全部结点，则必需调用次深度优先遍历算法。A．kB．1C．n-kD．n

30、以下不正确的说法是。

A．无向图中的极大连通子图称为连通重量

B．连通图的广度优先搜寻中普通要采纳队列来暂存刚拜访过

的顶点

C．图的深度优先搜寻中普通要采纳栈来暂存刚拜访过的顶点D．有向图的遍历不行采纳广度优先搜寻办法

二、填空题

01、在有向图中，以顶点v为尽头的边的数目称为v的。

02、含n个顶点的无向连通图中至少含有条边。

03、图的存储结构表示有、、十字链表、邻接多重表等多种存

储结构。

04、遍历图的2种常见办法是优先遍历和优先遍历。

04、有向图G用邻接表矩阵存储，其第i行的全部元素之和

等于顶点i的。

05、假如n个顶点的图是一个环，则它有棵生成树。

06、n个顶点e条边的图，若采纳邻接矩阵存储，则空间复

杂度为。若采纳邻接表存储，则空间复杂度为。

07、图的逆邻接表存储结构只适用于图。

08、已知一个图的邻接矩阵表示，删除全部从第i个顶点出

发的办法是。

09、图采纳邻接矩阵表示，则计算第i个顶点入度的办法是求。

10、用邻接矩阵表示图时，则推断随意两个顶点vi和vj之

间是否有路径相连，只需要检查即可。

11、用普里姆(Prim)算法求具有n个顶点e条边的图的最小

生成树的时光复杂度为；用克鲁斯卡尔(Kruskal)算法的时光

复杂度是。

12、对稀疏图最好用算法求最小生成树，对稠密图最好用算

法来求解最小生成树。

13、用Dijkstra算法求某一顶点到其余各顶点间的最短路径

是按路径长度的次序来得到最短路径的。

14、拓扑排序算法是通过重复挑选具有个前驱顶点的过程来

完成的。

15、有向图G用邻接矩阵存储，则第i行的全部元素之和等

于顶点i的。

16、有n个顶点的强连通有向图G至少有条弧。17、设有向图G的邻接矩阵为A，假如图中不存在弧，则A[i,j]的值为。

18、在n个顶点的无向图中，若边数>n-1，则该图必是连通图，此断言是的。(正确/错误)

19、在有n个顶点的有向图中，每个顶点的度最大可达。

20、若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑排序序列必然。(存在/不存在)

三、简答题

01、写出下面有向图的全部强连通重量。

02、已知图的邻接表如下，画出图G的全部连通重量。

03、如下图，分离用普里姆算法和克鲁斯卡尔算法从顶点1开头求最小生成树，写出按次序产生边的序列。说明：边用(i,j)方式表示。

04、如下图，写出全部的拓扑序列，并求在添加什么边之后仅可能有惟一的拓扑序列。

05、已知如图所示的有向图，请给出该图的:

(1)每个顶点的入/出度；(2)邻接矩阵；(3)邻接表；(4)逆

邻接表。

06、写出无向带树图的邻接矩阵，并按普里姆算法填写表格中的内容，最后画出最小生成树；

VbcDeFghUV-U

Vexlowcosta

4

a

3

A

∞

a

∞

a

∞

a

∞

a

∞

{a}{bcdefgh}

Vex

lowcost

Vex

lowcost

Vex

lowcost

Vex

lowcost

Vex

lowcost

Vex

Lowcost

Vex

lowcost

07、写出无向带树图的邻接表，并按克鲁斯卡尔算法写出求最小生成树产生的边序列。

08、已知二维数组表示的图的邻接矩阵如下图所示。试分离画出自顶点1动身举行遍历所得的深度优先生成树和广度优先生成树。

09、利用Dijkstra算法填写表格求图中从顶点a到其他各顶点间的最短路径，并写出终于结果。

尽头

Dist

bcDefg

S(尽头

集)

k=1

k=2

k=3

k=4

k=5

k=6

求利用表格给出求解过程。

11、设图G=(V，E)，V={1，2，3，4，5，6}，E={，，，，，，}。画出图G，并写出图G中顶点的全部拓扑序列。

12、已知图的邻接表表示的形式说明如下：

#defineMaxNum80

typedefstructnode

{intadjvex;//邻接点域

structnode*next;//链指针域

}EdgeNode;//边表结点结构描述

typedefstruct

{charvertex;//顶点域

EdgeNode*firstedge;//边表头指针

}VertexNode;//顶点表结点结构描述

typedefstruct

{VertexNodeadjlist[MaxNum];//邻接表

intn,e;

}AlGraph;//邻接表结构描述

下列算法输出图G的深度优先生成树(或森林)的边，阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。

typedefenum{FALSE,TRUE}Boolean;

Booleanvisited[MaxNum];

voidDFSForest(AlGraph*G)

{for(i=0;in;i++)visited[i]=___;

for(i=0;in;i++)

if(!visited[i])DFSTree(G,i);}

voidDFSTree(AlGraph*G,inti)

{visited[i]=TRUE;

p=G->adjlist[i].firstedge;

while(p!=NULL)

{if(!visited[p->adjves])

{printf(G->adjlist[i].vertex,G->adjlist[p->adjvex].vertex);

___;}

___;}

}

四、算法设计题

01、编写编历算法，完成对图的深度优先搜寻和广度优先搜寻。

02、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

03、试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。

提醒：要删除全部从第i个顶点动身的边，即将邻接矩阵的第i行所有置0。

04、有n个顶点的有向图的邻接表定义如下：

#defineMaxNum80

typedefstructArcNode

{intadjvex;//邻接点域

structArcNode*nextarc;//链指针域

}ArcNode;//边表结点结构描述typedefstructVNode

{VertexTypedata;//顶点域

ArcNode*firstedge;//边表头指针

}VNode,AdjList[MaxNum];//顶点向量结点结构描述typedefstruct

{AdjListvertices;//邻接表

intvexnum,arcnum;

}AlGraph;//邻接表结构描述

设计算法分离实现以下要求

(1)求出图G中每个顶点的出度；

(2)求出图G中出度最大的一个顶点，输出该顶点号及其信息；

(3)计算图G中出度为0的顶点数；

(4)推断图G中是否存在弧。

05、试基于图的深度优先搜寻策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注重：算法中涉及的图的基本操作必需在此存储结构上实现。

第7章图

一、单选题01-10CBBCCBAACB11-20DAADBACACB21-30DCDADBCBAD

二、填空题

01、入度02、n-103、邻接矩阵、邻接表

04、深度、广度04、出度05、n

06、O(n2)、O(n+e)07、有向08、将邻接矩阵的第i行所有置009、矩阵第i列非0元素之和10、第i行第j列的元素是否为011、O(n2)、O(elog2e)12、克鲁斯卡尔(Kruskal)、普里姆(Prim)

13、递增14、015、出度

16、n17、018、错误

19、2(n-1)20、存在

三、简答题

01、3个，分离是：a,bce,dfg

02、

03、普里姆算法产生边的序列：(1,3),(3,4),(4,6),(6,5),(5,2)

克鲁斯卡尔算法产生边的序列：(4,6),(1,3),(4,3),(6,5),(2,5)

04、v1,v2,v3,v4

v1,v3,v2,v4

v2,v1,v3,v4

05、(1)每个顶点的入/出度(2)邻接矩阵

(3)邻接表(4)逆邻接表

06、(1)邻接矩阵为：

VbcdefghUV-U

Vexlowcosta

4

a

3

a

∞

a

∞

a

∞

a

∞

a

∞

{a}{b,c,d,e,f,g,h}

Vexlowcosta

4

0c

5

a

∞

a

∞

a

∞

c

5

{a,c}{b,d,e,f,g,h}

Vexlowcost00c

5

b

9

a

∞

a

∞

c

5

{a,c,b}{d,e,f,g,h}

Vexlowcost000d

7

d

6

d

5

d

4

{a,c,b,d}{e,f,g,h}

Vexlowcost000d

7

d

6

d

5

0{a,c,b,d,h}{e,f,g}

Vexlowcost000d

7

g

2

00{a,c,b,d,h,g}{f,e}

Vexlowcost000f

3

000{a,c,b,d,h,g,f}{e}

Vex

lowcost

0000000{a,c,b,d,h,g,f,e}{}

07、邻接表为：

fg(2)→ac(3)→fe(3)→ab(4)→dh(4)→bd(5)→dg(5)08、

09、

a→c：2(a,c)

a→f：6(a,c,f)

a→e：10(a,c,e)

a→d：11(a,c,f,d)

a→g：14(a,c,f,d,g)

a→b：15(a,b)

10、和上题类似，求解过程略。

11、

1，2，3，6，5，4

1，3，2，6，5，4

1，3，6，2，5，4

12、

FALSE//初始化为未拜访

DSFTree(G,p->adjvex)//从相邻结点往下继续深度搜寻

p=p->next//下一个未拜访的相邻结点

四、算法设计题

01、编写编历算法，完成对图的深度优先搜寻和广度优先搜寻。

深度优先搜寻：课本P169算法7.4和算法7.5

广度优先搜寻：课本P170算法7.6

02、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

解：StatusBuild_AdjList(ALGraph

scanf("%d",

if(vnextarc;q=q->nextarc);

q->nextarc=p;

}

p->adjvex=j;p->nextarc=NULL;

}//while

returnOK;

}//Build_AdjList

03、试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。(假如要删除全部从第i个顶点动身的边呢？提醒：将邻接矩阵的第i行所有置0)

解：//本题中的图G均为有向无权图。

StatusDelete_Arc(MGraph

if((j=LocateVex(G,w))。

05、试基于图的深度优先搜寻策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注