数据结构基础练习.doc

判断题： 1. 在n个结点的无向图中，若边数 n-1，则该图必是连通图。（ ） 答：FALSE(该图可能包含多个连通子图，但其本身可以是不连通的。因为图的定义是：如果对于图中任意两个顶点v 、v E，v 和v 都是连通的，则称G是连通图(Connected Graph)。) 2.邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。（ ） 答：FALSE(邻接表也可存储无向图) 3.图的深度优先搜索序列和广度优先搜索序列不一定是唯一的。( )答：TRUE 4.有回路的图不能进行拓扑排序。( )答：TRUE 5.任何AOV网拓扑排序的结果都是唯一的。( ) 答：FALSE(拓扑排序不一定唯一，只要满足偏序关系即可。) 6.在AOV-网中，如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径。( ) 答：TRUE 7.图的邻接矩阵中矩阵元素的行数只与顶点个数有关（ TRUE ） 8.图的邻接矩阵中矩阵中非零元素个数与边数有关（TRUE ） 9.在拓扑排序序列中，任意两个相继结点V i和Vj都存在从V i到Vj的路径（FALSE ） 10.若一个图的邻接矩阵为对称矩阵，则该图必为无向图。（TRUE ） 11.任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条（ TRUE ） 12.在有向图中，入度为0的结点称为叶子结点（或叶子）（ FALSE ）单选题： 13.在一个图中，所有顶点的度数之和等于所有边数的( )倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。 A. 1/2 B. 2 C. 1 D. 4 答： B C 14.具有n个顶点的有向图最多有( )条边。 An B. n(n-1) C. n(n+1) D. 答：B 15.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。 A. n B. n+1 C. n-1 D. n/2 答：C 16.一个有n个顶点的无向连通图，它所包含的连通分量个数为( )。 A0 B. 1 C. n D. n+1 答：B 17. n个顶点的强连通图至少有( )条边。 A. n B. n-1 C. n+1 D. n(n-1) 答：A 18. 在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为( )。 As B. s-1 C. s+1 D. n 答：A 19. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为( )；所有邻接表中的结点总数是( )。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C. 2e D. n+e 答： A C (为什么选C呢？因为在无向图中邻接表表示法中，每条边作一次“第一条”边，再作一次其它边的“相邻接”边. ) 20. 对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点的单链表中的结点数为( )。 Ak1 B. k2 C. k1-k2 D. k1+k2 答：B 21. 在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情况下不可能出现的是( )。 AG中有弧 B. G中有一条从vi到vj的路径 CG中没有弧 D. G中有一条从vj到vi的路径 答：D 22. 在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为( )。 Ak B. k+1 C. k+2 D. 2k 答：B 23. 采用邻接表存储的图的深度优先遍历类似于二叉树的( )。 A中序遍历 B. 先序遍历 C. 后序遍历 D. 按层次遍历 答：B 24.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A逆拓扑有序的 B. 拓扑有序的 C. 无序的 答：A （请参见严蔚敏(c语言版)数据结构P185.算法7.13、算法7.14） 25.关键路径是事件结点网络中的( )。 A从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C 最长的回路 D. 最短的路径 答：A 26.下面不正确的说法是( )。 (1)在AOE-网工程中，减少任一关键活动上的权值后，整个工期也就相应的减小 (2)AOE-网工程工期为关键活动上的权之和 (3)在关键路径上的活动都是关键活动，而关键活动也必在关键路径上 A(1) B. (2) C. (3) D. (1)(3) 答：A (若网中有 n条关键路径时，仅减其中一条关键路径的权值并不能使整个工期减少，故选择A.) 27.下面的叙述中不正确的是( )。 A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，将使整个工程提前完成 C.所有关键活动都提前完成，则整个工程将提前完成 D.某些关键活动若提前完成，将使整个工程提前完成 答：B (理由同26题) 28.采用邻接表存储的图的广度优先遍历类似于二叉树的( )。 A按层次遍历 B. 中序遍历 C. 后序遍历 D. 先序遍历 答：A 29.一个图中包含k个连通分量，若按深度优先(DFS)搜索方法访问所有结点，则必须调用( )次深度优先遍历算法。 Ak B. 1 C. k-1 D. k+1 答：A (一次深度优先搜索只能遍历一个连通分量，故选A.) 30.以下说法正确的是( )。 A.连通分量是无向图中的极小连通子图 B.强连通分量是有向图中的极大强连通子图 C.在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧 D.对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图 答：B (A错，连通分量是无向图中的极大连通子图；C错，拓扑序列中顶点a在顶点b之前，则图中并不一定存在一条弧；D错，如果有向图构成双向有环时，则从任一顶点出发均能访问到每个顶点，但该图却非完全图；因此，选择B.)31.下面关于图的存储的叙述中，哪一个是正确的。 （ ） A用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关,而与边数无关 B用相邻矩阵法存储图，占用的存储空间数只与图中边数有关,而与结点个数无关 C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关 D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 答案：A 32.对于如右下图所示的带权有向图，从顶点1到顶点5的最短路径（ ） A1，4，5 B.1，2，3，5 C1，4，3，5 D.1，2，4，3，5 答案：D E2,则称（ ）V2,E133.设G1=(V1,E1)和G2=(V2,E2)为两个图， V1 AG1是G2的子图 B.G2是G1的子图 CG1是G2的连通分量 D.G2是G1的连通分量 答案：A 34.带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ ） A、第i行非的元素之和 B、第i列非的元素之和 C、第i行非且非0的元素个数 D、第i列非且非0的元素个数 答案：D 35.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（ ） A O(n) BO(e) CO(n+e) DO(n*e) 答案：C填空题： 36.一个无向图有n个顶点和e条边，则所有顶点的度的和即 ( 表示顶点i的度)= 。 答：2e (一条边被两个顶点使用) 37.若无向图G的顶点度数的最小值大于或等于 时，G至少有一条回路。 答：2 38.一个连通图的 是一个极小连通子图。 (重大2000年研究生试题。) 答：生成树 39.设无向图G的顶点数为n，图G最少有 条边，最多有 条边。若G为有向图，有n个顶点，则图G最少有 条边，最多有 条边。具有n个顶点的无向完全图，边的总数为 条；而具有n个顶点的有向完全图中，边的总数有 条。 答：0 n(n-1)/2 0 n(n-1) n(n-1)/2 n(n-1) (注*：设每个结点都有n-1条弧线从自己出发分别射向其它各个结点的话，则n个结点共有n(n-1) 条有向弧线存在；但是，如此一来任两个结点之间都会有两条相向而指的弧线存在，这就是所谓的有向完全图。如果我们限定任意两个结点之间都有且仅有一条无向的连线存在，则整个图的连线总数就会比有向完全图的弧线总数刚好少一半，即共有 n(n-1)条边，也就是 (n-1) 条边。此乃所谓(无向)完全图。若能画图一试，则上述公式对错立判。请参考讲义7.1.) 40.在有n个顶点的有向图中，每个顶点的度最大可达 。 答：2(n-1) (向其它每个顶点发出一条弧，则共发出n-1条，同时从其它每个顶点接收一条弧，共接收n-1条，两者合计为2(n-1)条。) 41.在无向图G的邻接矩阵A中，若AIj等于1，则AjI等于 。 答：1 42.在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的 ；而对于无向图而言等于该顶点的 。 答：出度数 度数 43.对无向图，若它有n个顶点e条边，则其邻接表中需要 个结点。其中， 个结点构成邻接表， 个结点构成顶点表。 答：2e+n 2e n 44.已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是 。 答：求矩阵第i列非0元素的个数。 45.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是 。 答：将矩阵第i行全部置0 46.遍历图的过程实质上是 。Bread