问答题

下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：
由顶点V1到顶点V3的最短路径。【中山大学1994四(12分)】

答案：正确答案：V1到V3最短路径(V1一V4一V3)为67。

你可能感兴趣的试题

下面的邻接表表示一个给定的无向图。
(1)给出从顶点v1开始，对图G用深度优先搜索法进行遍历时的顶点序列；(2)给出从顶v1，1开始，对图G用广度优先搜索法进行遍历时的顶点序列。【复旦大学1998六(10分)】

答案：正确答案：(1)v ₁ v ₂ v ₄ v ₃ v ₅ v ₆ (2) v ₁ v ₂ v ₃ v ₄ v ₅ v ₆

解答下面的问题：
【西安电子科技大学2000计算机应用六(10分)】如果每个指针需要4字节，每个顶点的标号占2字节，每条边的权值占2字节。下图采用哪种表示法所需的空间较多为什么

答案：正确答案：邻接矩阵：(6*6个元素)*2字节／元素=72字节邻接表：表头向量6*(4+2)+边结点9*(2+2+4)*...

多项选择题

已知一个有向图如图所示，则从顶点a出发进行深度优先遍历，写出所有可能得到的DFS序列。
【北京交通大学2006四、4(5分)】

如下所示的连通图，请画出：(1)以顶点①为根的深度优先生成树；(5分)(2)如果有关节顶点，请找出所有的关节顶点。(5分)【清华大学l 998七(10分)】

答案：正确答案：(1)未确定存储结构，其DFS树不唯一，其中之一(按邻接点逆序排列)是：

(2)关节顶点有3，1，8，7，2。

给出图G：
画出G的邻接表表示图；

答案：正确答案：

某田径赛中各选手的参赛项目表如下：
设项目A，B，…，F各表示一数据元素，若两项目不能同时举行，则将其连线(约束条件)。根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构；

答案：正确答案：

解答下面的问题：
【西安电子科技大学2000计算机应用六(10分)】写出下图从顶点1开始的：DFS树。

答案：正确答案：因未确定存储结构，从顶点1开始的DFS树不唯一，现列出两个：

某田径赛中各选手的参赛项目表如下：
设项目A，B，…，F各表示一数据元素，若两项目不能同时举行，则将其连线(约束条件)。写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列。【北京科技大学1999五2000五(12分)】

答案：正确答案：AFEDBC

给出图G：
根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。【南开大学1997五(14分)】【烟台大学2007四、3(15分)】

答案：正确答案：广度优先生成树，深度优先生成树，为节省篇幅，生成树横画，下同。

考虑下图：
(1)从顶点A出发，求它的深度优先生成树。(2)从顶点E出发，求它的广度优先生成树。(3)根据普利姆(Prim)算法，求它的最小生成树。【上海交通大学1999六(12分)】

答案：正确答案：设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列。(1)ABGFDEC (2)EACFBDG (3)

在什么情况下，Prim算法与Kruskual算法生成不同的MST【西安电子科技大学2000计算机应用一、11(5分)】

答案：正确答案：在边有相等权值(特别是边的权值较小且相等)时可能会生成不同的MST。

已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小生成树(假设以①为起点，试画出构造过程)。
【哈尔滨工业大学2000九(8分)】

答案：正确答案：设连通网N=(V,{E})，设V是N的顶点的集合，E是N上边的集合。Prim算法从U={u₀

一带权无向图的邻接矩阵如下，试画出它的一棵最小生成树。
【浙江大学1994五(8分)】

答案：正确答案：设顶点集合为{1，2，3，4，5，6}，由下边的逻辑图可以看出，在{1，2，3}和{4，5，6}回路中，各任选...

已知顶点1～6和输入边与权值的序列(如右图所示)：每行三个数表示一条边的两个端点和其权值，共11行。请你：
(1)采用邻接多重表表示该无向网，用类Pascal语言描述该数据结构，画出存储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。(2)分别写出从顶点1出发的深度优先和广度优先遍历顶点序列，以及相应的生成树。(3)按Prim算法列表计算，从顶点1始求最小生成树，并图示该树。【北京工业大学1999四(20分)】

答案：正确答案：(1)
(2)深度优先遍历序列：1，4，6，5，3，2；深度优先生成树的边集合：{(1，4)，(4，...

下图表示一个地区的通信网，边表示城市间的通信线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n一1条线路，画出所有可能的选择。【东北大学2000一、4(4分)】

答案：正确答案：最小生成树的顶点集合：V(G)={1，2，3，4，5，6}，下面两个边的集合都可以。 E1(G)={(1，2，...

【简答题】
试列出下图中全部可能的拓扑排序序列。

答案：

正确答案：7个：561234，516234，512634，512364，156234，152364，152634

试给出有向图的所有拓扑序列。
【北京交通大学2005五、3(5分)】

答案：正确答案：3个：23 1546，213546，123546

对于一个有向图，不用拓扑排序，如何判断图中是否存在环【厦门大学2006三、3(25／3分)】

答案：正确答案：图的深度优先遍历可用于拓扑排序，使用dfs遍历所得顶点序列是逆拓扑序列。

对于一个有向图，除了进行拓扑排序，还可以采用什么办法判断图中是否存在回路请简述判断原则。【北京航空航天大学2007一、2(3分)】

答案：正确答案：图的深度优先遍历可用于判断图中是否存在回路。若从有向图某顶点V出发进行遍历，在dfs(v)结束之前出现从顶点W...

下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：
该带权有向图的图形；

答案：正确答案：

【论述题】已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其他各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处给出解题过程。

答案：正确答案：下面用Floyd算法求出任意两顶点的最短路径(如图A^(b)所示)。题目要求娱乐中心“距其...

有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列A ¹ ，A ² ，A ³ ，A ⁴ 。
【北京邮电大学2001四、5(5分)】

答案：正确答案：

下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：
从顶点V1为起点的广度优先周游的顶点序列及对应的生成树(即支撑树)；

答案：正确答案：V1，V2，V4，V6，V3，V5

试利用Dijkstra算法求下图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。【东南大学2000四(10分)】

答案：正确答案：求解过程略。顶点a到顶点b，c，d，e，f，g间的最短路径分别是15，2，11，10，6，13。

下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：
以顶点V1为起点的深度优先周游生成树；

答案：正确答案：顶点集合V(G)={V1，V2，V3，V4，V5，V6}边的集合E(G)={，，，，)

对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源点，并写出生成过程。【吉林大学1999一、2(4分)】

答案：正确答案：顶点A到顶点B，C，D，E的最短路径依次是3，1 8，38，43，按Dijkstra所选顶点过程是B，C，D，...

已知图的邻接矩阵为：
当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列；(2)以顶点V1为出发点的唯一的广度优先遍历序列；(3)该图唯一的拓扑有序序列。【同济大学1998一(12分)】

答案：正确答案：(1)V1，V4，V9，V10，V7，V6，V8，V3，V2，V5深度优先遍历生成树如右面第一图 (2)V1，...

下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：
由顶点V1到顶点V3的最短路径。【中山大学1994四(12分)】

答案：正确答案：V1到V3最短路径(V1一V4一V3)为67。

求出下图中顶点1到其余各顶点的最短路径。
【厦门大学2002八、2(5分)】

答案：正确答案：本表中DIST中各列最下方的数字是顶点1到顶点的最短路径。
顶点1到其他顶点的最短路径依次是20，3...