济南铁道职业技术学院 专升本辅导教材 数据结构
／x利用s和dist在尚未找到最短路径的顶点中确定一个与v最近的顶点u。／ s[u]=1； ／‘置u的标记为1●／
path[u)C++pos[u]]=u； ／x将u添加到v到u的最短路径中。／ count++； ／，计数器累力n1 x／
while(1){ ／。根据u更新v到所有尚未确定最短路径的顶点的路径长度。／ if((w=SEARCH_VER(s，dist，u))==-1)
／，找到通过u可以直接到达、且尚未确定最短路径的一个顶点。／ break； ／x未找到，路径长度更新过程结束。／ else{
if(dist[u]+cost[u][w] dist[N]=dist[u]+cost[u][w]； ／x更新路径长度●／ for[i=0；i ／。用源点v到顶点u的路径替换源点v到w的路径。／ } } } ． 习 题 6．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)没有顶点的图称为空图。 ( ) (2)图的度是图中所有顶点的度的最大值。 ( ) (3)边上带权值的图称为网(络)。 ( ) (4)图中一个顶点的度应该是它的出度与人度之和。 ( ) (5)n个顶点的无向图最多有n(n-1)条边。 ( ) (6)在有向图中，所有顶点的人度之和等于所有顶点的出度之和。 ( ) (7)在无向图中，若顶点i到顶点j有路径，则这两个顶点之间是连通的。 ( ) (8)在有向图中，若顶点i到顶点j有路径，则这两个顶点之间是连通的。 ( ) (9)连通图的最小生成树是惟一的。 ( ) (10)邻接矩阵主要用来表示顶点之间的关系。 ( ) (u)若表示某图的邻接矩阵不是对称矩阵，则该图一定是有向图。 ( ) (12)若表示某图的邻接矩阵中出现了全零行或者全零列，则该图一定是非连通图或者非强连通图。 ( ) (13)对于同一个有向图，邻接表中的边结点数目与逆邻接表中边结点数目相等。 ( ) (14)无向图的邻接表中边结点数目一定为偶数。 ( ) (15)邻接表中边结点数目为奇数的图一定是有向图。 ( ) (16)邻接表中边结点数目为偶数的图一定是无向图。 ( ) (17)对图进行广度优先搜索的过程中要用到队列。 ( ) (18)对图进行深度优先搜索的过程中要用到堆栈。 ( ) (19)带权连通图的最小生成树是惟一的。 ( ) (20)最短路径一定是简单路径。 ( ) (21)求源点到各点的最短路径的迪杰斯特拉算法不适用于存在回路的有向网络。 ( ) (22)不能对强连通图进行拓扑排序。 ( ) (23)若AOV网中存在拓扑序列，则一般情况下，拓扑序列不是惟一的。 ( ) 第 41 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 (24)关键路径是由权值最大的边构成的。 ( ) (25)给定的AOE网的关键路径一定是惟一的。 ( ) 6．2单项选择题。 (1)在一个图中，所有顶点的度数之和等于所有边数的——倍。 A．1／2 B．1 C．2 D．4 (2)一个具有n个顶点的无向图最多有——条边。 A．n(n-1)／2 B．n(n-1) C．n(n+1)/2 D．n(2) (3)一个具有n个顶点的有向图最多有——条边。 A．n(n-1)/2 B．n(n-1) C．n(n+1)/2 D．n(2) (4)在一个具有n个顶点的无向图中，要连通全部顶点至少需要——条边。 A．n B．n+1 C．n-1 D．2n (5)具有n个顶点的连通图的生成树一定有——条边。 A．n B．n+1 C．n-1 D．2n (6)若一个非连通的无向图最多有28条边，则该无向图至少有——个顶点。 ， A．6 B．7 C．8 D．9 (7)在带权图中，两个顶点之间的路径长度是——。 A．路径上的顶点数目 B．路径上的边的数目 C．路径上顶点和边的数目 D．路径上所有边上的权值之和 (8)若具有n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵一定为一个——。 A．一般矩阵 B．对称矩阵 C．对角矩阵 D．稀疏矩阵 (9)若图的邻接矩阵中主对角线上的元素均为0，其余元素全为1，则可以断定该图一定 _____. A．是无向图 B．是有向图 C．是完全图 D．不是带权图 (10)有向图的邻接表的第i个链表中的边结点数目是第i个顶点的——。 A．度数 B．出度 C．人数 D．边数 (11)若某图的邻接表中的边结点数目为奇数，则该图——。 A．一定有奇数个顶点 B．一定有偶数个顶点 C．一定是有向图 D。可能是无向图 (12)若某图的邻接表中的边结点数目为偶数，则该图——。 A．一定是无向图 B。可能是有向图 C．可能是无向图，也可能是有向图 D．一定有偶数个顶点 (13)若无向图有k条边，则相应的邻接表中就有——个边结点。 A．k-1 B．k C．2k D．K(2) (14)若有向图有k条边，则相应的邻接表中就有——个边结点。 A．k-1 B．k C．2k D．K(2) (15)对于一个不带权的无向图的邻接矩阵而言，——。 A．矩阵中非零元素的数目等于图中边的数目 B．矩阵中非全零的行的数目等于图中顶点的数目 巴第i行的非零元素的数目与第i列的非零元素的数目相等 D。第i行与第i列的非零元素的总数等于第i个顶点的度数 (16)导致图的遍历序列不惟一的因素有——。 A．出发点不同、遍历方法不同 B，出发点不同、存储结构不同 C，遍历方法不同、存储结构不同 第 42 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 D．出发点不同、存储结构不同、遍历方法不同 (17)若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问该图的所有顶点，则 该图一定是一个——图。 A．非连通 B．连通 C．强连通 D．完全 (18)可以进行拓扑排序的图一定是——。 A．连通图 B．带权连通图 C．无回路的图 D．无回路的有向图 (19)已知某有向图G=(V，E)，其中V={v1，v2，v3，v4，v5，v6}，E={{v1，v2)，(v1，v4)，{v2，v6)， (v3，v1)，(v3，v4)，(v4，v5)，{v5，v2)，{v5，v6)}，G的拓扑序列是—— A．v3，v1，v4，v5，v2，v6 B．v3，v4，v1，v5，v2，v6 C．v1，v3，v4，v5，v2，v6 D．v1，v4，v3，v5，v2，v6 (20)下面关于AOE网的叙述中，不正确的是———。 A．若所有关键活动都提前完成，则整个工程一定能够提前完成 B．即使所有非关键活动都未按时完成，整个工程仍有可能按时完成 C．任何一个关键活动的延期完成，都会导致整个工程的延期完成 D.任何一个关键活动的提前完成，都会导致整个工程的提前完成 6.3 设一有向图为G=(V，E)，其中，V={vl，v2，v3，v4}，E={ 6.5 已知给定无向图如图6.27所示。 (1)画出相应邻接矩阵； (2)画出相应邻接表。 6.6 证明n个顶点的无向图的边数达到的最大值为n(n—1)／2。 6.7 具有n个顶点的强连通图至少有多少条边?这样的图的形状有何特点? 6.8 已知一无向图如图6.28所示，请写出其邻接表表示，然后根据该邻接表分别写出从顶v1出发进行深度优先搜索与广度优先搜索时得到的顶点序列。 6.9 已知某带权连通无向图采用邻接矩阵存储方法，邻接矩阵以三元组表形式给出，不包括主对角线元素在内的下三角形部分元素对应的各三元组分别为(2，1，7)，(3，1，6)，(3，2，8)，(4，1， 9)，(4，2，4)，(4，3，6)，(5，1，oo)，(5，2，4)，(5，3，oo)，(5，4，2)。该连通图的最小生成树的权值之和是多少? 6.10 试编写一构造无向图邻接表结构的算法，设该无向图G=(V，E)以V={v1，v2，?，vn}与E={(Vi，Vj)|Vi,Vj属于V,i≤n，j≤n}作为输入。 8.11 设计一个算法，将一个已知图的邻接矩阵存储形式转换为邻接表的存储形式。 第 43 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 8.12 已知一个具有n个顶点的无向图采用邻接表存储方法。试设计一个算法，删除图中一条边(u，v)。 8.13 一个带权连通图的最小生成树是否一定惟一?什么情况下有可能不惟一? 8.14 已知一带权连通图如图6.29所示。请首先写出其邻接矩阵，然后再按Prim算法求出其所有可能的最小生成树。 8.15 根据SHORTEST PATH算法，求出给定有向图(如图6.30所示)从顶点v1到其他各顶点长度递增的最短路径，并分别写出执行算法过程中各个数组的变化状态。 6.16 源点到图中其他各顶点的所有最短路径构成一棵生成树，该生成树是否为最小生成树?为什么? 6.17 某航空公司在六个城市设有分公司v1，v2，v3,v4,v5，v6；矩阵A中元素A[i][j]表示vi到vj的飞机票价(A[i][j]=+oo表示vi与vj之间不直接通航)。请为该航空公司制作一张由vl到各分公司去的最便宜的通航线路图。 6.18 已知一AOE网采用邻接矩阵存储方式，其邻接矩阵为一稀疏矩阵，并采用三元组表形式给出(见图6.31)。 (1)画出该AOE网； (2)分别说明各顶点、有向边表示什么，边上权值代表什么。 6.19 设计出一种求AOE网关键路径的算法。 6.20 对给定AOE网(如图8．32所示)。 (1)分别求出各活动的最早开始时间与最晚开始时间； (2)求出所有关键路径； (3)该工程完成的最短时间是多少? 第 44 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 第六章 图 历年考试题 1．若 A．vi邻接于vj B．vj邻接于vi C．vi和vj相互邻接 D．vi与vj不相邻接 2．在一个带权连通图G中，权值最小的边一定包含在G的（ ） A．最小生成树中 B．深度优先生成树中 C．广度优先生成树中 D．深度优先生成森林中 3．下列数据组织形式中，（ ）的各个结点可以任意邻接。 A．集合 B．树形结构 C．线性结构 D．图状结构 4．邻接表是图的一种（ ） A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构 5．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（ A．G肯定不是完全图 B．G一定不是连通图 C．G中一定有回路 D．G有2个连通分量 6．一个带权的无向连通图的最小生成树（ ） A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在 7．下列有关图遍历的说法中不正确的是（ ） A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 8.n个顶点的有向完全图中含有向边的数目最多为( ) A.n-1 B.n C.n(n-1)/2 D.n(n-1) 9.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为( ) A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f c b 第 45 页 共 63 页 ）