数据结构基础练习

《数据结构基础练习》由会员分享，可在线阅读，更多相关《数据结构基础练习（5页珍藏版）》请在金锄头文库上搜索。

1、判断题:1. 在n个结点的无向图中，若边数 -1,则该图必是连通图。( ) 答:FLE(该图也许涉及多种连通子图，但其自身可以是不连通的。由于图的定义是：如果对于图中任意两个顶点 、 E，v 和 都是连通的，则称是连通图(Conneced Graph）。） 2.邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都合用。( )答：FLS（邻接表也可存储无向图).图的深度优先搜索序列和广度优先搜索序列不一定是唯一的。( ）答:RUE 有回路的图不能进行拓扑排序。( )答：TRUE 5.任何AOV网拓扑排序的成果都是唯一的。( ) 答:FAS（拓扑排序不一定唯一，只要满足偏序关系即可

2、。） 6.在AOV-网中,如果得到的拓扑有序序列中顶点个数不不小于网中顶点数n,则阐明网中存在环，不能求核心途径。( ) 答：RE7.图的邻接矩阵中矩阵元素的行数只与顶点个数有关（ TRUE） 8.图的邻接矩阵中矩阵中非零元素个数与边数有关(RUE ）9.在拓扑排序序列中,任意两个相继结点V 和Vj都存在从V i到V的途径（ASE )10若一种图的邻接矩阵为对称矩阵，则该图必为无向图。（TRUE )1.任一AOE网中至少有一条核心途径，且是从源点到汇点的途径中最长的一条( TRUE ） 12.在有向图中,入度为0的结点称为叶子结点(或叶子)（ ALSE）单选题： 13.在一种图中，所有顶点的度

3、数之和等于所有边数的( )倍，在一种有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。 A 1/2 B 2C. 1 D. 答: B C14.具有n个顶点的有向图最多有（ )条边。 A.n B. n(-1） C. n(n+1） D答:B1.在一种具有个顶点的无向图中,要连通所有顶点至少需要()条边。 A. . 1C n-1 D./答: 6.一种有n个顶点的无向连通图,它所涉及的连通分量个数为( )。 0B. 1 C. n D. n+ 答：B 7. n个顶点的强连通图至少有()条边。 B n1C. n+1 D. n(n-1) 答:A 18.在一种具有n个顶点的有向图中,若所有顶点的出度之

4、和为s,则所有顶点的入度之和为( )。 A.B. s-1 .s+1 D. n 答：A 1对于一种具有n个顶点和e条边的无向图,若采用邻接表表达，则表头向量的大小为( );所有邻接表中的结点总数是( )。 A.n B.n+1 . n .+ . e/2 B e . eD.n+ 答:A C (为什么选C呢?由于在无向图中邻接表表达法中,每条边作一次“第一条”边,再作一次其他边的“相邻接”边. )0.对于一种有向图，若一种顶点的入度为1、出度为k,则相应邻接表中该顶点的单链表中的结点数为（ )。 Ak1 B.k2 C. 1-k2 D. k1+2 答：B 1. 在有向图的拓扑序列中，若顶点vi在顶点vj

5、之前，则下列状况下不也许浮现的是( )。 AG中有弧B.G中有一条从v到j的途径C中没有弧i,j D. 中有一条从vj到i的途径 答:D 2在一种无向图中,若两个顶点之间的途径长度为k，则该途径上的顶点数为(）。 A.k B.k+1 C. k+ D 2k 答：B 23 采用邻接表存储的图的深度优先遍历类似于二叉树的(）。 A.中序遍历 先序遍历 C. 后序遍历 D按层次遍历 答:B .用DS遍历一种无环有向图，并在DS算法退栈返回时打印相应的顶点，则输出的顶点序列是()。A.逆拓扑有序的 拓扑有序的 .无序的 答： (请参见严蔚敏(c语言版)数据构造185.算法7.13、算法4）5.核心途径是

6、事件结点网络中的(）。 A.从源点到汇点的最长途径 B. 从源点到汇点的最短途径C. 最长的回路 D 最短的途径 答：A 6.下面不对的的说法是( ）。 (1)在AE网工程中,减少任一核心活动上的权值后,整个工期也就相应的减小 (2)OE-网工程工期为核心活动上的权之和 (3)在核心途径上的活动都是核心活动,而核心活动也必在核心途径上 A(1) B. （) C. () (）（3)答:A (若网中有 条核心途径时,仅减其中一条核心途径的权值并不能使整个工期减少,故选择.) 2.下面的论述中不对的的是( )。 A核心活动不按期完毕就会影响整个工程的完毕时间 .任何一种核心活动提前完毕，将使整个工程

7、提前完毕 C.所有核心活动都提前完毕，则整个工程将提前完毕D.某些核心活动若提前完毕,将使整个工程提前完毕答：B （理由同26题） 2.采用邻接表存储的图的广度优先遍历类似于二叉树的( )。A按层次遍历 B 中序遍历 C. 后序遍历 D. 先序遍历 答: 9一种图中涉及k个连通分量，若按深度优先(FS)搜索措施访问所有结点，则必须调用()次深度优先遍历算法。 A B 1C.k- D. k 答: （一次深度优先搜索只能遍历一种连通分量，故选A)30.如下说法对的的是( )。 A.连通分量是无向图中的极小连通子图 .强连通分量是有向图中的极大强连通子图C.在一种有向图的拓扑序列中若顶点a在顶点b之

8、前,则图中必有一条弧a,b .对有向图G,如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点,则该图一定是完全图答：B (A错,连通分量是无向图中的极大连通子图;错，拓扑序列中顶点在顶点b之前，则图中并不一定存在一条弧；D错,如果有向图构成双向有环时，则从任一顶点出发均能访问到每个顶点，但该图却非完全图;因此,选择.）31.下面有关图的存储的论述中,哪一种是对的的。 ( ） A用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关,而与边数无关B.用相邻矩阵法存储图，占用的存储空间数只与图中边数有关,而与结点个数无关 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与

9、边数无关 D.用邻接表法存储图,占用的存储空间数只与图中边数有关，而与结点个数无关答案:A 32.对于如右下图所示的带权有向图，从顶点1到顶点的最短途径（ ） A.1，4,5 .1,2,3，51，, D.1，2，4，3,5 答案：DE2,则称（ ）2,E13.设G1=(V1,E1)和G2=(V,)为两个图， VA1是2的子图 G2是的子图 C.G是G的连通分量 D.G2是G1的连通分量 答案：A 34.带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中( ） A、第i行非的元素之和 、第i列非的元素之和、第行非且非0的元素个数 D、第i列非且非0的元素个数 答案:D 35.假设一种有个顶点和

10、条弧的有向图用邻接表表达,则删除与某个顶点vi有关的所有弧的时间复杂度是（ ) A. O（n) B.O(e） .O（+e) .O(n*) 答案：C填空题： 6一种无向图有n个顶点和条边,则所有顶点的度的和即( 表达顶点i的度)= 。 答:2e (一条边被两个顶点使用） 37.若无向图G的顶点度数的最小值不小于或等于 时,G至少有一条回路。 答:238.一种连通图的 是一种极小连通子图。 (重大研究生试题。)答:生成树 39.设无向图的顶点数为n，图G至少有条边，最多有 条边。若G为有向图,有个顶点,则图G至少有 条边,最多有条边。具有n个顶点的无向完全图，边的总数为 条;而具有n个顶点的有向完

11、全图中,边的总数有 条。 答：0 （n-)/2 0 n(n-1) (n-1)/2 （-1) (注*:设每个结点均有条弧线从自己出发分别射向其他各个结点的话,则个结点共有n(n-1） 条有向弧线存在;但是，如此一来任两个结点之间都会有两条相向而指的弧线存在,这就是所谓的有向完全图。如果我们限定任意两个结点之间均有且仅有一条无向的连线存在，则整个图的连线总数就会比有向完全图的弧线总数刚好少一半,即共有 n（n-1）条边,也就是 (n-1) 条边。此乃所谓(无向)完全图。若能画图一试,则上述公式对错立判。请参照讲义71）4.在有n个顶点的有向图中,每个顶点的度最大可达 。 答:（n-1) (向其他每

12、个顶点发出一条弧,则共发出n-1条，同步从其他每个顶点接受一条弧，共接受n-1条,两者合计为2(n-)条。） .在无向图的邻接矩阵A中，若A等于1，则Aj等于 。 答： 42在一种图G的邻接表表达中,每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的 ；而对于无向图而言等于该顶点的 。答:出度数度数 43.对无向图，若它有个顶点e条边,则其邻接表中需要 个结点。其中， 个结点构成邻接表， 个结点构成顶点表。 答：2n2e n 44已知一种图的邻接矩阵表达，计算第个结点的入度的措施是 。 答:求矩阵第i列非0元素的个数。 45.已知一种图的邻接矩阵表达，删除所有从第i个结点出发的边的措施是 。答：将矩阵第i行所有置046.遍历图的过程实质上是。Beadt-irst sear遍历图的时间复杂度为 ，dpt-fist seach遍历图的时间复杂度为 ,两者不同之处在于 ，反映在数据构造上的差别是 。答：对每个顶点查找其邻接点的过程O()(e为图中的边数)O（)遍历图的顺序不同DFS采用栈存储访问过的结点,BFS采用队列存储访问过的结点 47.遍历图的基本措施有深度优先搜索和广度优先搜索,其中 是一种递归过程。 答：深度优先搜索