JAV数据库考题适用于大连东软信息学院

1、5.8 习题5.8.1 知识点：图的基本概念一、选择题1n个顶点的连通图至少有（A ）条边。A n-1B nC n+1D02 在无向图中定义顶点 vi与vj之间的路径为从 vi到达vj的一个（B ）。A .顶点序列B .边序列C.权值总和D .边的条数3 具有n个顶点的有向图最多可包含（ D ）条有向边。A. n-1B. nC. n（n-1） /2D. n（n-1）4在无向图中定义顶点的度为与它相关联的（ B ）的数目。A .顶点B .边C.权D .权值5一个有N个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。A. NB. N1C.N 1D.N/26 含N个顶点的连通图中的任意一条简单

2、路径，其长度不可能超过（C ）。A. 1B.N/2C.N 1D.N7 设无向图的顶点个数为n,则该图最多有（B ）条边。【清华大学1998】【西安电子科技大 1998】【北京航空航天大学1999】A. n-1B. n（n-1） /2C. n（n+1） /2D. n（n-1）8 在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。【哈尔滨工业大学 2001】A. 1/2B. 2C. 1D. 4二、填空题1n （n 0）个顶点的无向图中顶点的度的最大值为_n-1。2n （n 0）个顶点的无向图最少有 _0条边。3n （n

3、0）个顶点的连通无向图各顶点的度之和最少为_2（n-1）。4 具有n个顶点的无向完全图，边的总数为_n（n-1）/2条；而具有n个顶点的有向完全图边的总数为 _n（n-1）条。5 在有n个顶点的有向图中，每个顶点的度最大可达_2（n-1）。6 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_n_条弧。【合肥工业大学 2000】7n个顶点的连通无向图，其边的条数至少为_n-1。【哈尔滨工业大学2000】8N个顶点的连通图的生成树含有 _n-1条边。【中山大学1998】9一个连通图的生成树是一个极小连通子图。【重庆大学 2000】三、判断题(T)1 如果无向图中各个顶点的度都大于

4、2，则该图中必有回路。(F )2一个图的子图可以是空图，顶点个数为0。(T ) 3有n (nl)个顶点的有向强连通图最少有n条边。(T) 4 树中的结点和图中的顶点就是指数据结构中的数据元素。【青岛大学2001 】(F ) 5在n个结点的无向图中，若边数大于n-1,则该图必是连通图。【中科院软件所1997】( T) 6 强连通图的各顶点间均可达。【北京邮电大学 2000】( F) 7 强连通分量是无向图的极大强连通子图。【北京邮电大学 2002】(F) 8 连通分量指的是有向图中的极大连通子图。【燕山大学1998】四、简答题1设连通图G如图所示。(1) 如果有关结点，请找出所有关结点。(2)

5、如果想把该连通图变成重连通图，至少在图中加几条边？如何加？582知识点：图的存储一、选择题1 在n个顶点的有向无环图的邻接矩阵中至少有( C )个零元素。A . nB. n (n-1) /2C. n (n+1) /2D. n ( n-1)2 若采用邻接矩阵法存储一个 n个顶点的无向图，则该邻接矩阵是一个(D )。A.上三角矩阵B.稀疏矩阵C.对角矩阵D .对称矩阵3 对于一个有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是(D )。A. NB . ( N 1) * ( N 1)D. N*NC. N 14设一个有n个顶点和e条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是

6、(A )。A. O (n)B . O( e)C. O ( n+e)D . O( )5 对于具有e条边的无向图，它的邻接表中有( D )个边结点。A. e-1B. eC. 2 (e-1)D. 2e6 下面结构中最适于表示稀疏无向图的是( E ),适于表示稀疏有向图的是( D )。 【北京工业大学 2001】A .邻接矩阵 B.逆邻接表 C .邻接多重表 D .十字链表 E.邻接表二、填空题1 用邻接矩阵存储图，占用存储空间数与图中顶点个数n有关，与边数_无关。2 邻接表和十字链表适合于存储 有向图，邻接多重表适合于存储 无向图。3在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是_第i列非零元

7、素个数。【青岛大学 2002】4在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于 该顶点的度;对于有向图来说等于该顶点的出度。【燕山大学 2001】5 对于一个具有 n个顶点e条边的无向图的邻接表的表示，则表头向量大小为 _n，邻接表的边结点个数为 _2e。【青岛大学2002】三、判断题(T) 1 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间 大小只与图中的顶点个数有关，而与图的边数无关。(T ) 2存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下(上)三 角部分就可以了。(T ) 3邻接矩阵只适用于稠密图(边数接近于顶点数的平方)，邻接表适用

8、于稀疏图(边数远小于顶点数的平方)。(F )4 邻接多重表是无向图和有向图的链式存储结构。【南京航空航天大学1995】(F ) 5 十字链表是无向图的一种存储结构。【青岛大学 2001】(T ) 6 无向图的邻接矩阵可用一维数组存储。【青岛大学2000】(T ) 7有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。【北京邮电大学 1998】(F ) 8 有向图的邻接矩阵是对称的。【青岛大学2001】(F )9 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。【东南大学2001】【哈尔滨工业大学1999】（F ） 10 邻接矩阵适用于有向图和无向

9、图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。【上海海运学院1998】（F ）11一个有向图的邻接表和逆邻接表中结点的个数可能不等。【上海交通大学1998 】四、简答题1在下图所示的有向图中，试给出:（1）每一个顶点的入度和出度；（2）邻接矩阵；（3）邻接表、逆邻接表；（4）强连通分量。图5.601题图2在下图所示的无向图中，试给出:（1）该图的邻接矩阵（2）该图的邻接表（3）该图的多重邻接表（4）给出每个顶点的度图5.61 2题图3 已知无向图 G，V（ G） =1，2, 3, 4，E（ G） =（ 1，2），（ 1, 3 ），（ 2, 3），（ 2,4），（3

10、, 4） 试画出G的邻接多重链表，并说明，若已知点i，如何根据邻接多重链表找到与i相邻的点j?【东南大学1998】五、算法题1设有向图用邻接表表示， 图有n个顶点，表示为1至n,试写一个算法求顶点 k的入度(1kn )。【南京理工大学 1997】2一个无向连通图的存储结构以邻接表的形式给定，设计算法删除该图中的一条边(i，j)。【北京工业大学 1996】583知识点：图的遍历-、选择题1为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是( B )。A .栈B .队列 C .二叉树D .树2一个连通图的生成树是包含图中所有顶点的一个(C )子图。A 极小B 连通C 极小连通D 无环3

11、采用邻接表存储的图的深度优先遍历算法类似于二叉树的(C )。A 前序遍历B 中序遍历C.后序遍历D 层次遍历4 对于有向图，其邻接矩阵表示比邻接表表示更易于( A )。A .求一个顶点的度B .求一个顶点的邻接点C.进行图的深度优先遍历D 进行图的广度优先遍历5 下列说法不正确的是( C )。【青岛大学2002】A 图的遍历是从给定的源点出发每一个顶点仅被访问一次B. 遍历的基本算法有两种：深度遍历和广度遍历C. 图的深度遍历不适用于有向图D. 图的深度遍历是一个递归过程6无向图 G= (V, E),其中：V=a , b, c, d, e, f , E= (a, b), (a, e), (a,

12、 c),(b, e), (c, f), (f, d), (e, d) ，对该图进行深度优先遍历，得到的顶点序列正确的是(D )。【南京理工大学 2001】A. a, b, e, c, d, f B. a, c, f, e, b, dC. a, e, b, c, f, d D. a,e, d, f, c, b7下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是(1) C ),而进行广度优先遍历得到的顶点序列是(2) C )。【中科院软件所1999】(1) :A . 1354267B. 1347652C. 1534276D.1247653E.以上答案均不正确(2) :

13、A. 1534267B. 1726453C. l354276D.1247653E.以上答案均不正确图5.627题图、填空题1 深度优先生成树的高度比广度优先生成树的高度高。2 遍历图的基本方法有 深度优先搜索和广度优先搜索两种。3 已知一无向图 G=（ V，E），其中 V=a，b，c, d，e ，E=（ a, b），（ a, d），（ a,c）, （d，c），（b，e） 。现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是深度遍历方法。【南京理工大学 1996】4 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列存放被访问的结点以实现遍历。【

14、南京理工大学 1999】三、判断题（T）1 图的深度优先搜索（depth first search）是一种典型的回溯搜索的例子，可以通过递归算法求解。（T ）2 图的广度优先搜索（breadth first search）算法不是递归算法。（T ）3 对一个连通图进行一次深度优先搜索（depth first search）可以遍访图中的所有顶点。四、简答题1 设连通图G如图所示。试画出该图及其对应的邻接表表示，并给出对它执行从v0开始的深度优先搜索的结果。2首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出从顶点v1出发，对图分别进行深度和广度优先遍历的结果。图5.642题图3 对

15、下图所示的有向图，从顶点v1出发，分别画出其深度和广度生成树。五、算法题1 使用邻接矩阵，实现图的深度优先遍历算法。2使用邻接表，实现图的广度优先遍历算法。3 假设图采用邻接表存储，分别写出基于 DFS和BPS遍历的算法来判别定点i和定 点j （i M）j之间是否有路径。584知识点：最小生成树一、选择题1在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（D ）辅助结构，判断一条边的两个端点是否在同一个连通分量上。A .位向量B .堆C.并查集D .生成树顶点集合2 任何一个带权的无向连通图的最小生成树（ B ）。A 只有一棵B 有一棵或多棵C 一定有多棵D 可能不存在

16、3 一个无向连通图的生成树是含有该连通图的全部顶点的（A ）。A. 极小连通子图B .极小子图C.极大连通子图D .极大子图4 对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个（C ）。A 由n-1条权值最小的边构成的子图B. 由n-1条权值之和最小的边构成的子图C. 由n-1条权值之和最小的边构成的连通子图D. 由n顶点构成的边的权值之和最小的连通子图5 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（B ）。【合肥工业大学 2001】a. o（0）b. O（ln +eI） c. O（0）d. o （同）二、填空题1101个顶点的连通网络 N有100条边，其中权值

17、为1, 2, 3, 4, 5, 6, 7, 8, 9, 10的边各10条，则网络N的最小生成树各边的权值之和为_550。2在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点 不在同一个 边上，才有可能加入到生成树中。3构造连通网络最小生成树的两个典型算法是 prim和_kruskal。4Prim （普里姆）算法适用于求 稠密的网的最小生成树；kruskal （克鲁斯卡尔）算法适用于求 稀疏的网的最小生成树。【厦门大学1999】5对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为_0（n2）_，利用Kruskal算法生成最小代价生成树其

18、时间复杂度为 _O（eloge）。【长沙铁道学院 1998】三、判断题（F ） 1最小生成树是指边数最少的生成树。（F ） 2 从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树。（F ）3 只要无向网中没有权值相同的边，其最小生成树就是唯一的。（F）4 只要无向网中有权值相同的边，其最小生成树就不可能是唯一的。（F ）5需要借助于一个队列来实现DFS算法。【南京航空航天大学1996】（F ） 6广度遍历生成树描述了从起点到各顶点的最短路径。【合肥工业大学2001 】（F ）7 任何无向图都存在生成树。【北京邮电大学 2000】（F ）8 不同的求最小生成树的方法最后得到的生成树

19、是相同的。【南京理工大学1998 】（F ）9 带权无向图的最小生成树必是唯一的。【南京航空航天大学1996】（T ）10最小生成树的 KRUSKAL 算法是一种贪心法（GREEDY ）。【华南理工 大学2002】（T ） 11 求最小生成树的普里姆（Prim ）算法中边上的权可正可负。【南京理工大学1998】（T ）12最小生成树问题是构造连通网的最小代价生成树。【青岛大学2001】（T ）13在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。【合肥工业大学 2000】四、简答题1对下图所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。图5.66 1题图2 已

20、知世界六大城市为：北京（Pe）、纽约（N）、巴黎（Pa）、伦敦（L）、东京（T ）、 墨西哥（M ），下表给出了这六大城市之间的交通里程（单位：百公里），试作下面的题目：(1) 画出这六大城市的交通网络图 ；(2) 画出该图的邻接表表示法 ；(3) 画出该图按权值递增的顺序来构造的最小(代价)生成树。表5.12题表penpaLTMPe109828121124N109585510832PA825839792L815539589T211089795113M1243292891133 已知无向图如下所示：(1) 给出从V1开始的广度优先搜索序列；(2) 画出它的邻接表；(3) 画出从V1开始深度优先

21、搜索生成树。【燕山大学2000】图5.673题图五、算法题1 如下图是一个城市连接图，图中的权值表示两个城市之间的里程(单位：100km)现要设计一条铁路贯穿所有城市(即从一个任一城市可以到达其他城市)，设计一个算法， 求出最小代价。假设每 1km的铁路的造价为100万元。icpCJ图5.68 1题图585知识点：图的应用、选择题1 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（B ）。A. O （ nlog2e）b. o （|n +e|）c. O （画D. O （吋）2图中有关路径的定义是（A ）A 由顶点和相邻顶点序偶构成的边所形成的序列B 由不同

22、顶点所形成的序列C.由不同边所形成的序列D .上述定义都不是3以下说法正确的是（A ）。A .连通图的生成树是该连通图的一个极小连通子图B .无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的C.任何一个有向图，其全部顶点可以排成一个拓扑序列D 有回路的图不能进行拓扑排序4关键路径是事件顶点网络中（ A ）。A 从源点到汇点的最长路径B 从源点到汇点的最短路径C.最长的回路D .最短的回路5 下面哪一方法可以判断出一个有向图是否有环（回路）（B ）。A.深度优先遍历B .拓扑排序 C.求最短路径D .求关键路径6一个有向无环图的拓扑排序序列（ B ）是唯一的。【北京邮电大学 2001】A

23、 .一定B .不一定7在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的 是（D ）。【南京理工大学 2000】A. G中有弧 B . G中有一条从 Vi到Vj的路径C. G中没有弧 D . G中有一条从 Vj到Vi的路径8在用邻接表表示图时，拓扑排序算法时间复杂度为（B ）。【合肥工业大学 2000】【南京理工大学 2001】【青岛大学2002】a. O（0） b. O （丨n +e|） c. O（罔）d.o（罔）9 下面关于求关键路径的说法不正确的是（ A ）。【南京理工大学 1998】A .求关键路径是以拓扑排序为基础的B .一个事件的最早开始时间同以该事件为尾的弧

24、的活动最早开始时间相同C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续 时间的差D. 关键活动一定位于关键路径上10 下列关于AOE网的叙述中，不正确的是（D）。【北方交通大学 1999】【北京工业大学 1999】A 关键活动不按期完成就会影响整个工程的完成时间B. 任何一个关键活动提前完成，那么整个工程将会提前完成C. 所有的关键活动提前完成，那么整个工程将会提前完成D. 某些关键活动提前完成，那么整个工程将会提前完成11 下列哪一种图的邻接矩阵是对称矩阵？ ( B)【北方交通大学 2001】A.有向图 B.无向图C AOV网 D AOE网二、填空题1在AOE网

25、中，从源点到汇点路径上各活动时间总和最长的路径称为关键路径2 若对一个有向无环图进行拓扑排序，再对排在拓扑有序序列中的所有顶点按其先后次序重新编号，则在相应的邻接矩阵中所有_非零 元素将集中到对角线以上。3 有向图G可拓扑排序的判别条件是 AOV网 有向无环图_。【长沙铁道学院 1998 】4AOV网中，结点表示 活动，边表示优先级关系 。AOE网中，结点表示 _事件，边表示 活动。【北京理工大学 2001】5 在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为 关键路径。【重庆大学 2000】三、判断题( F ) 1 对任何用顶点表示活动的网络( AOV 网)进行拓扑排序的结果都是

26、唯一的。(T ) 2有回路的有向图不能完成拓扑排序。(F ) 3在AOE网络中一定只有一条关键路径。(F ) 4对一个有向图进行拓扑排序(topological sorting ), 一定可以将图的所有 顶点按其关键码大小排列到一个拓扑有序的序列中。(T ) 5对于一个边上权值任意的带权有向图，使用Dijkstra算法可以求一个顶点到其它各个顶点的最短路径。(F ) 6 拓扑排序算法把一个无向图中的顶点排成一个有序序列。【南京航空航天大学 1995】(T ) 7拓扑排序算法仅能适用于有向无环图。【南京航空航天大学 1997】(F ) 8 拓扑排序的有向图中，最多存在一条环路。 【大连海事大学 2001】(F ) 9任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。【上海交通大学 1998】(F ) 10 即使有向无环图的拓扑序列唯一，也不能唯一确定该图。【合肥工业大学 2001 】(T ) 11 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。【中科院软件所 1997】(F ) 12AOV网的含义是以边表示活动的网。【南京航空航天大学 1995】(F ) 13对一个AOV网，