数据结构第七章习题(1)

7.1 选择题1. 对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为()A) O(n)B)O(n+e)C) O(n*n)D)O(n*n*n)【答案】B2. 设无向图的顶点个数为n,则该图最多有()条边。

A) n-1B)n(n-1)/2C)n(n+1)/2【答案】B3. 连通分量指的是()A) 无向图中的极小连通子图B) 无向图中的极大连通子图C) 有向图中的极小连通子图D) 有向图中的极大连通子图【答案】B4. n 个结点的完全有向图含有边的数目()A) n*n B) n(n+1) C) n/2【答案】D5. 关键路径是()A) AOE网中从源点到汇点的最长路径B) AOE网中从源点到汇点的最短路径C) AOV网中从源点到汇点的最长路径D) n2D) n* (n-1)D) AOV网中从源点到汇点的最短路径【答案】 A 6．有向图中一个顶点的度是该顶点的()A)入度B)出度C)入度与出度之和D)(入度+出度)12【答案】C7．有e 条边的无向图，若用邻接表存储，表中有()边结点。

A) e B) 2eC) e-1D) 2(e-1)【答案】B8．实现图的广度优先搜索算法需使用的辅助数据结构为()A)栈B)队列C)二叉树D)树【答案】B9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为()A)栈B)队列C)二叉树D)树【答案】 A 10．存储无向图的邻接矩阵一定是一个()A)上三角矩阵B)稀疏矩阵C)对称矩阵D)对角矩阵【答案】C11．在一个有向图中所有顶点的入度之和等于出度之和的()倍A) B) 1C) 2D) 4答案】B12．在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为(A) O(n)B) O(n+e)C 0(n2)D) 0(n3))【答案】B13 .下列关于AOE网的叙述中，不正确的是()A) 关键活动不按期完成就会影响整个工程的完成时间B) 任何一个关键活动提前完成，那么整个工程将会提前完成C) 所有的关键活动提前完成，那么整个工程将会提前完成D) 某些关键活动提前完成，那么整个工程将会提前完成【答案】B14. 具有10 个顶点的无向图至少有多少条边才能保证连通()A ) 9B) 10C) 11D) 12【答案】A15. 在含n 个顶点和e 条边的无向图的邻接矩阵中，零元素的个数为()A)e B)2eC)n2-e D)n2-2e【答案】D7.2 填空题1 .无向图中所有顶点的度数之和等于所有边数的________________ 倍。

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;第2章线性表算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表。

要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。

表中不允许有重复的数据。

（2）将两个非递减的有序链表合并为一个非递增的有序链表。

要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。

表中允许有重复的数据。

（3）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

（4）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

（5）设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink 和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。

第3章栈和队列（1）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。

7.1选择题1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（）A）O(n)B）O(n+e)C）O(n*n)D）O(n*n*n)【答案】B2．设无向图的顶点个数为n，则该图最多有（）条边。

A）n-1B）n(n-1)/2C）n(n+1)/2【答案】B3．连通分量指的是（）A）无向图中的极小连通子图B）无向图中的极大连通子图C）有向图中的极小连通子图D）有向图中的极大连通子图【答案】B4．n个结点的完全有向图含有边的数目（）A）n*n B）n（n+1）C）n/2【答案】D5．关键路径是（）A）AOE网中从源点到汇点的最长路径B）AOE网中从源点到汇点的最短路径C）AOV网中从源点到汇点的最长路径D）n2D）n*（n-1）D）AOV网中从源点到汇点的最短路径【答案】A6．有向图中一个顶点的度是该顶点的（）A）入度B）出度C）入度与出度之和D）（入度+出度）/2【答案】C7．有e条边的无向图，若用邻接表存储，表中有（）边结点。

A）e B）2eC）e-1D）2(e-1)【答案】B8．实现图的广度优先搜索算法需使用的辅助数据结构为（）A）栈B）队列C）二叉树D）树【答案】B9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（）A）栈B）队列C）二叉树D）树【答案】A10．存储无向图的邻接矩阵一定是一个（）A）上三角矩阵B）稀疏矩阵C）对称矩阵D）对角矩阵【答案】C11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍A）B）1C）2D）4【答案】B12．在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为（A）O(n)B）O(n+e)C）O(n2)D）O(n3)）【答案】B13．下列关于AOE网的叙述中，不正确的是（）A）关键活动不按期完成就会影响整个工程的完成时间B）任何一个关键活动提前完成，那么整个工程将会提前完成C）所有的关键活动提前完成，那么整个工程将会提前完成D）某些关键活动提前完成，那么整个工程将会提前完成【答案】B14．具有10个顶点的无向图至少有多少条边才能保证连通（）A）9B）10C）11D）12【答案】A15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A）e B）2eC）n2-e D）n2-2e【答案】D7.2填空题1．无向图中所有顶点的度数之和等于所有边数的_____________倍。

数据结构习题（7,8,9章）第七章图⼀．选择题1．n个顶点，e条边的有向图的邻接矩阵中⾮零元素有个。

A.nB.2eC.eD.n+e2．⽤邻接表存储图所⽤的空间⼤⼩（）A．与图的顶点数和边数都有关B．只与图的边数有关C．只与图的顶点数有关D．与边数的平⽅有关3．有n 条边的⽆向图的邻接表存储法中，链边中结点的个数是（）个。

A．n B．2n C．n/2 D．n*n4．⼀个带权⽆向连通图的最⼩⽣成树（）。

A．有⼀棵或多棵. B．只有⼀棵C．⼀定有多棵D．可能不存在5．若⼀个图中包含有k个连通分量，若要按照深度优先搜索的⽅法访问所有顶点，则必须调⽤( )次深度优先搜索遍历的算法。

A．k B．1 C．k-1 D．k+1⼆．如下所⽰有向图：1．请给出每个顶点的度，⼊度和出度。

2．请画出其邻接矩阵、邻接表、逆邻接表、⼗字链表。

三．试对下图所⽰的AOE⽹络，解答下列问题。

1．求每个事件的最早发⽣时间ve [i]和最迟发⽣时间vl[i]。

2．求每个活动的最早开始时间ee(s)和最迟开始时间el(s)。

3．指出哪些活动加速可使整个⼯程提前完成。

四．写出下图所⽰的AOV⽹的所有拓扑有序序列。

第⼋章查找⼀．填空题1．采⽤⼆分法进⾏查找的查找表，应选择____________________⽅式的存储结构2．设在有序表A[0……9]中进⾏⼆分查找，⽐较⼀次查找成功的结点数为_____，⽐较⼆次查找成功的结点数为______，⽐较三次查找成功的结点数为_____，⽐较四次查找成功的结点数为_____，⽐较五次查找成功的结点数为_____，平均查找长度为______。

⼆．选择题1．对线性表进⾏⼆分查找时，要求线性表必须（）A．键值有序的链接表B．键值有序的顺序表C．链接表但键值不⼀定有序D．顺序但键值不⼀定有序2．有⼀个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},当⽤⼆分查找法查找键值为84的结点时，经（）⽐较后查找成功。