第四章_图.doc

数据结构与算法上机作业第四章 图一、选择题1、在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。A. 1/2B. 1C. 2D. 42、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的 B 倍。A. 1/2B. 1C. 2D. 43、G是一个非连通无向图，共有28条边，则该图至少有 C 个顶点。A. 6B. 7C. 8D. 94、有n个顶点的图的邻接矩阵使用 B 数组存储的。A. 一维B. n行n列C. 任意行n列D. n行任意列5、对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头数组大小至少为（假设下标为0的数组参与使用） A 。A. n-1B. n+1C. nD. n+e6、下列说法正确的是 C 。A. 有向图的邻接矩阵一定是不对称的B. 有向图的邻接矩阵一定是对称的C. 无向图的邻接矩阵一定是对称的D. 无向图的邻接矩阵可以不对称7、深度优先遍历类似与二叉树的 A ：A. 先根遍历B. 中根遍历C. 后根遍历D. 层次遍历8、广度优先遍历类似与二叉树的 D ：A. 先根遍历B. 中根遍历C. 后根遍历D. 层次遍历9、下列关于开放树(Free Tree)的说法错误的是 C ： A. 具有n个结点的开放树包含n-1条边 B. 开放树没有回路 C. 开放树可以是非连通图 D. 在开放树中任意加一条边，一定会产生回路10、在如下图所示的图中，从顶点a出发，按深度优先遍历，则可能得到的一种顶点的序列为 D 。 A. a, b, e, c, d, fB. a, c, f, e, b, d C. a, e, b, c, f, dD. a, e, d, f, c, b11、在如上图所示的图中，从顶点a出发，按广度优先遍历，则可能得到的一种顶点的序列为 A 。A. a, b, e, c, d, fB. a, b, e, c, f, dC. a, e, b, c, f, dD. a, e, d, f, c, b12、设网(带权的图)有n个顶点和e条边，则采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为 C 。A. O(n)B. O(n+e)C. O(n2)D. O(n3)13、设图有n个顶点和e条边，求解最短路径的Floyd算法的时间复杂度为 B 。A. O(n)B. O(n+e)C. O(n2)D. O(n3)14、最小生成树是指 C 。A. 由连通网所得到的边数最少的生成树。B. 由连通网所得到的顶点数相对较少的生成树。C. 连通网中所有生成树中权值之和为最小的生成树。D. 连通网的极小连通子图。15、下面关于工程计划的AOE网的叙述中，不正确的是 B 。A. 关键活动不按期完成就会影响整个工程的完成时间。B. 任何一个关键活动提前完成，那么整个工程将会提前完成。C. 所有关键活动都提前完成，那么整个工程将会提前完成。D. 某些关键工程若提前完成，那么整个工程将会提前完成。16、在AOE网中，始点和汇点的个数为 D 。A. 1个始点，若干个汇点B. 若干个始点，若干个汇点C. 若干个始点，1个汇点C. 1个始点，1个汇点17、在下图所示的无向图中，从顶点v1开始采用Prim算法生成最小生成树，算法过程中产生的顶点次序为 A 。A. v1, v3, v4, v2, v5, v6B. v1, v3, v6, v2, v5, v4C. v1, v2, v3, v4, v5, v6D. v1, v3, v6, v4, v2, v518、在上图所示的途中，采用Cruskal算法生成最小生成树，过程中产生的边的次序是 。A. (v1, v2), (v2, v3), (v5, v6), (v1, v5)B. (v1, v3), (v2, v6), (v2, v5), (v1, v4)C. (v1, v3), (v2, v5), (v3, v6), (v4, v5)D. (v2, v5), (v1, v3), (v5, v6), (v4, v5)19、如下图所示的图中，其中一个拓扑排序的结果是 。A. v1v2v3v6v4v5v7v8B. v1v2v3v4v5v6v7v8C. v1v6v4v5v2v3v7v8D. v1v6v2v3v7v8v4v520、在下图所示的AOE网中，活动a9的最早开始时间为 B 。A. 13B. 14C. 15D. 1621、在上图所示的AOE网中，活动a4的最迟开始时间为 C A. 2B. 3C. 4D. 522、设图有n个顶点和e条边，当用邻接表表示该图时，则求解最短路径的Dijkstra算法的时间复杂度为 。A. O(n)B. O(n+e)C. O(e)D. O(n2)二、填空题1、若无向图G中顶点数为n，则图G至多有 n(n-1)/2 条边；若G为有向图，则图G至多有 n(n-1) 条边。2、图的存储结构主要有两种，分别是 邻接矩阵 和 邻接表 。3、若G 是有向图，则把邻接到顶点v 的顶点数目或边数目称为顶点v 的 入度 ；把邻接于顶点v 的顶点数目或边数目称为顶点v 的 度 。4、已知一个图的邻接矩阵表示，计算第j个顶点的入度的方法是 listofnode Pre(G,j) ，计算第j个顶点的出度的方法是 listofnode Succ(G,j) 。5、若将图中的每条边都赋予一个权，则称这种带权的图为 带权图 。6、无论是有向图还是无向图，顶点数n 、边数e 和各顶点的度D(vi)之间的关系为： e=12i=1nD(vi) 。7、 若路径上第一个顶点v1 与最后一个顶点vm 重合, 则称这样的简单路径为 环路 。8、 如果图中任意一对顶点都是连通的, 则称此图是 连通图 ；非连通图的极大连通子图叫做 连通分量 。9、创建一个邻接矩阵图的复杂度是 ；创建一个链接表图的复杂度是 。10、图的遍历有 深度优先遍历 和广度优先遍历等方法。11、在深度优先搜索和广度优先搜索中，都采用visitedi= new 的方式设置第i个顶点为new，而采用visitedi= old 的方式标识第i个结点为old。12、由于深度优先算法的特点，深度优先往往采用 的方式实现。13、由于广度优先算法的特点，在广度优先实现过程中，往往要借助于另一种数据结构 实现。14、在深度优先搜索和广度优先搜索中，在搜索过程中所经过的边都称为 回退边 。15、连通而且无环路的无向图称为 开放树 。16、对于含有n个顶点e条边的连通图，利用Prim算法求其最小生成树的时间复杂度为 O（n2） ，利用Kruscal算法求最小生成树的时间复杂度是 O(n) 。3、顶点表示活动的网简称为 AOV ；边表示活动的网简称为 AOE 。17、一个含有n个顶点的无向连通图，其每条边的权重都是a(a0)，则其最小生成树的权重等于 。18、具有n个顶点的有向图，如果采用邻接矩阵表示该图，则求某顶点到其他各顶点的最短路径的Dijkstra算法的时间复杂度是 ；如果采用邻接表表示该图，则时间复杂度为 。19、在用Dijkstra算法求单源最短路径的过程中，将顶点集合V划分为两个集合S和V-S，其中S中的点为 最短路径已经确定的点 ，V-S中的点为 最短路径尚未确定的点 。20、求每一对顶点之间的最短路径，可以用两种方法，一种是分别对每个顶点采用 算法，另一种方法是 。21、假设有向图的邻接矩阵C的传递闭包为A，则Aij=1表示 。22、有向图的中心点是指 具有最小偏心度的点 。三、已知一个无向图如下图所示，试给出该图的邻接矩阵和邻接表存储示意图（画图，分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。四、已知一个有向图如下图所示，试给出图的邻接矩阵和邻接表存储示意图（画图，分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。五、已知一个图的顶点集为a, b, c, d, e，其邻接矩阵如下图，考虑图为无向图和有向图两种情况，分别画出该图。六、已知一个连通图如下图所示，分别给出一个按深度优先遍历和广度优先遍历的顶点序列（假设从顶点v1出发）。并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写相关基本操作，并在主函数中求出深度优先序列和广度优先序列。七、基于深度优先搜索算法，写出求无向图所有连通子图的算法，并求连通分量。提示：对于无向图，从任一个顶点出发进行DFS遍历，当本次遍历完成后，其所访问的结点构成一个连通子图；如果还存在没有访问过的结点，则从中任一个结点出发进行DFS遍历，直到所有结点都被访问。每一次调用DFS后都得到此非连通图的一个连通子图，调用DFS的次数就是连通子图的个数。八、网络G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。九、下图是一个无向带权图，请给出该图的邻接矩阵，并分别按Prim算法和Kruskal算法求最小生成树（包括算法代码和画图）。十、已知如下图所示的AOE网，顶点表示事件，弧及权重表示活动的时间(单位为天)。找出关键路径，并求出事件v3的最早开始时间，然后编程实现。十一、已知一个图的顶点集V和边集G分别为V=0, 1, 2, 3, 4, 5, 6, 7, 8，E=, , , , , , , , , , , , ，若采用邻接表存储，并且每个顶点邻接表中的边结点都是按照终点序号从大到小的次序连接的，则按照拓扑排序算法，写出得到的拓扑序列，并编程实现。十二、如下图所示的有向网络，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径(要求写出如教材P155表4-2所示的Dijkstra算法的执行过程)，并编程验证。十三、应用Floyd算法，编程求下图所示有向图的每对顶点之间的最短路径(写出相应的矩阵)，并求该图的中心点。并利用Warshall算法，编程求该图的传递闭包(矩阵)。思考题1：跳马周游棋盘问题：在nn（n15）的国际象棋上的某一位置（键盘输入）上放置一个马，然后采用象棋中“马走日字”的规则，要求这个马能不重复地走完 nn个格子，试用计算机求马能够走的一条路径。 提示：用深度优先搜索法思考题2：nn(n15)国际象棋棋盘上有一个马，要从起点（键盘输入）跳到指定目标（键盘输入），最少跳几步，试用计算机实现。 提示：用广度优先搜索法。 a b c d e f g h12345678h8a1思考题3：POJ1789 要求用Prim算法实现Truck HistoryTime Limit: 2000MSMemory Limit: 65536KDescriptionAdvanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are used for vegetable delivery, other for furniture, or for bricks. The company has its own code describing each type of a truck. The code is simply a string of exactly seven lowercase letters (each letter on each position has a very special meaning but that is unimportant for this task). At the beginning of companys history, just a single truck type was used but later other types were derived from it, then from the new types another types were derived, and so on. Today, ACM is rich enough to pay historians to study its history. One thing historians tried to find out is so called derivation plan - i.e. how the truck types were derived. They defined the distance of truck types as the number of positions with different letters in truck type codes. They also assumed that each truck type was derived from exactly one other truck type (except for the first truck type which was not derived from any other type). The quality of a derivation plan was then defined as 1/(to,td)d(to,td)where the sum goes over all pairs of types in the derivation plan such that to is the original type and td the type derived from it and d(to,td) is the distance of the types. Since historians failed, you are to write a program to help them. Given the codes of truck types, your program should find the highest possible quality of a derivation plan. InputThe input consists of several test cases. Each test case begins with a line containing the number of truck types, N, 2 = N = 2 000. Each of the following N lines of input contains one truck type code (a string of seven lowercase letters). You may assume that the codes uniquely describe the trucks, i.e., no two of these N lines are the same. The input is terminated with zero at the place of number of truck types. OutputFor each test case, your program should output the text The highest possible quality is 1/Q., where 1/Q is the quality of the best derivation plan. Sample Input4aaaaaaabaaaaaaabaaaaaaabaaaa0Sample OutputThe highest possible quality is 1/3.思考题4 POJ2485 要求用Kruskal算法实现HighwaysTime Limit: 1000MSMemory Limit: 65536KTotal Submissions: 18145Accepted: 8433DescriptionThe island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. Theyre planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system. Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways. The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.InputThe first line of input is an integer T, which tells how many test cases followed. The first line of each case is an integer N (3 = N = 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within 1, 65536) between village i and village j. There is an empty line after each test case.OutputFor each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.Sample Input130 990 692990 0 179692 179 0Sample Output692思考题5POJ1094 拓扑排序Sorting It All OutTime Limit: 1000MSMemory Limit: 10000KDescriptionAn ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A B, B C and C D. in this problem, we will give you a set of relations of the form A B and ask you to determine whether a sorted order has been specified or not. InputInput consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 = n = 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A B which will be given in this problem