数据结构课堂练习3data(答案)

《数据结构课堂练习3data(答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法课堂练习(3)(答案)1.一个n个顶点的连通图，它的生成树有条边。A．nB．n-1C．n+1D．2*n2.Dijkstra算法是用来求。A．从一个顶点到其余顶点的最短路径B．每对顶点之间的最短路径C．拓扑序列D．最小生成树3.拓扑排序能够进行的前提条件（即能输出一个拓扑序列）是该AOV网。A.顶点数多于边数B.边数多于顶点数C.不存在回路D.有回路4.拓扑排序能够进行的前提条件（即能输出一个拓扑序列）是该AOV网。A.不存在回路B.有回路C.顶点数多于边数D.边数多于顶点数选择题5.最小生成树是

2、指连通网（设每条边上的权值均大于0）的各生成树中的生成树。A.边数最少B.生成树的权最小C.不存在回路D.路径最短6.当AOV网满足条件时，它代表的工程才是可行的。A.是无向无环图B.是无向带环图C.是有向无环图D.是有向带环图7.求从一个顶点到其余顶点的最短路径需用。A.Prim算法B.Floyd算法C.Dijkstra算法D.Kruskal算法8.判断一个有向图是否存在回路，除了可以利用深度优先遍历算法外，还可以用。A.求最短路径的算法B.拓扑排序算法C.求最小生成树的算法D.广度优先遍历算法1.已知一个

3、有向图的邻接矩阵存储结构如图，画出该图形，并写出从顶点V1出发的深度优先和广度优先的顶点序列。解：图形：深度优先的顶点序列为：V1,V3,V5,V2,V4广度优先的顶点序列为：V1,V2,V3,V4,V50101000000110000000001110解答题V4V5V1V2V3V4V5V1V2V3V4V5V1V2V311122.无向带权图G如下:①从结点A出发，画出根据普里姆算法产生图G的最小生成树的过程（即需要写出得到各条边的次序）。AFEGDBC1058119276146103解答题AFEGDBC105

4、8119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC582143②从结点A出发，画出根据克鲁斯卡尔算法产生图G的最小生成树的过程（即需要写出得到各条边的次序）。AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC105811927614610

5、3AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC582143解：图结点按邻接矩阵下标由小到大排列v0,v1,v2,v3,v4,v5,v6,v7,v9,v83．在下面有向网中，求出顶点V0点到其它顶点的最短路径（写出经过的顶点和长度）。12V3V0V1V2V4830532541020解：V0->V13V0->V1->V311V0->V1->V3->V215V0->V1->V3->V423解答题4.一个AOV

6、网的二元组表示为：V={0,1,2,3,4,5,6,7,8,9}E={<1,2>,<1,3>,<0,3>,<0,4>,<2,3>,<2,5>,<3,5>,<3,6>,<4,6>,<3,9>,<5,7>,<5,9>,<6,9>,<7,8>,<9,8>}①画出该AOV网的示意图。②若该AOV网采用邻接矩阵存储结构，写出按拓扑排序算法得到的拓扑序列。V0V1V2V3V4V5V6V7V8V95.一个AOV网的二元组表示为：V={0,1,2,3,4,5,6,7,8}E={<0,1>,<0,3>,<0,4>,<1,2>,

7、<1,3>,<2,3>,<2,5>,<3,5>,<3,6>,<3,8>,<4,6>,<5,7>,<5,8>,<6,8>,<8,7>}①画出该AOV网的邻接矩阵存储结构。②写出按邻接矩阵存储结构存储时由拓扑排序算法得到的拓扑序列。解：000000000001000011001101000000000000000000000011000000100000000000001001010001100432105678432105678000000000001000011001101000000000000000000

8、000011000000100000000000001001010001100432105678432105678全0，无入度，输出v0把1全改为0V0,V1,V2,V3,V4,V5,V6,V8,V7解答题6.一个AOV网的二元组表示为：V={0,1,2,3,4,5,6,7,8,9}E={<0,2>,<0,3>,<1,3>,<1,4>,<2,3>,<2,5>,<3,5>,<3,6>,<4,6>,<3