数据结构(C++版)课后作业章附答案.doc

第 6 章图
课后习题讲解
1、 填空题
⑴ 设无向图G中顶点数为n,则图G至少有( )条边,至多有( )条边;若G为有向图,则至少有( )条边,至多有( )条边。
【解答】0,n(n-1)/2,0,n(n-1) 【分析】图得顶点集合就是有穷非空得,而边集可以就是空集;边数达到最多得图称为完全图,在完全图中,任意两个顶点之间都存在边。
⑵ 任何连通图得连通分量只有一个,即就是( )。【解答】其自身
⑶ 图得存储结构主要有两种,分别就是( )与( )。【解答】邻接矩阵,邻接表
⑸ 已知一个有向图得邻接矩阵表示,计算第j个顶点得入度得方法就是( )。【解答】求第j列得所有元素之与
⑹ 有向图G用邻接矩阵A[n][n]存储,其第i行得所有元素之与等于顶点i得( )。【解答】出度
⑺ 图得深度优先遍历类似于树得( )遍历,它所用到得数据结构就是( );图得广度优先遍历类似于树得( )遍历,它所用到得数据结构就是( )。
【解答】前序,栈,层序,队列
(8) 如果一个有向图不存在( ),则该图得全部顶点可以排列成一个拓扑序列。
【解答】回路
2、 选择题
⑵ n个顶点得强连通图至少有( )条边,其形状就是( )。 A n B n+1 C n-1 D n×(n-1) E 无回路 F 有回路 G 环状 H 树状 【解答】A,G
⑶ 含n 个顶点得连通图中得任意一条简单路径,其长度不可能超过( )。 A 1 B n/2 C n-1 D n
【解答】C 【分析】若超过n-1,则路径中必存在重复得顶点。
(4)最小生成树指得就是( ) 。 A 由连通网所得到得边数最少得生成树 B 由连通网所得到得顶点数相对较少得生成树 C 连通网中所有生成树中权值之与为最小得生成树 D 连通网得极小连通子图
【解答】C
(5)下面关于工程计划得AOE网得叙述中,不正确得就是( )
A 关键活动不按期完成就会影响整个工程得完成时间 B 任何一个关键活动提前完成,那么整个工程将会提前完成 C 所有得关键活动都提前完成,那么整个工程将会提前完成 D 某些关键活动若提前完成,那么整个工程将会提前完
【解答】B 【分析】AOE网中得关键路径可能不止一条,如果某一个关键活动提前完成,还不能提前整个工程,而必须同时提高在几条关键路径上得关键活动。
3、 判断题
(1)用邻接矩阵存储图,所占用得存储空间大小只与图中顶点个数有关,而与图得边数无关。【解答】对。邻接矩阵得空间复杂度为Ｏ(n2),与边得个数无关。
(2) 图G得生成树就是该图得一个极小连通子图 【解答】错。必须包含全部顶点。
(3)在一个有向图得拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧。
【解答】错。只能说明从顶点a到顶点b有一条路径。
7.已知一个连通图如图所示,试给出图得邻接矩阵与邻接表存储示意图,若从顶点v1出发对该图进行遍历,分别给出一个按深度优先遍历与广度优先遍历得顶点序列。

8.图所示就是一个无向带权图,请分别按Prim算法与Kruskal算法求最小生成树。

自己做。
第 7 章 查找技术
(3) 在各种查找方法中,平均查找长度与结点个数无关得查找方法就是( )。
【解答】散列查找 【分析】散列表得平均查找长度就是装填因子得函数,而不就是记录个数n得函数。
2、 选择题
(1) 设散列表表长m=14,散列函数H(k)=k mod 11。表中已有15、38、61、84四个元素,如果用线性探侧法处理冲突,则元素49得存储地址就是( )。【解答】A 【分析】元素15、38、61、84分别存储在4、5、6、7单元,而元素49得散列地址为5,发生冲突,向后探测3个单元,其存储地址为8。
3、 判断题
⑴ 二叉排序树得充要条件就是任一结点得值均大于其左孩子得值,小于其右孩子得值。
【解答】错。 分析二叉排序树得定义,就是左子树上得所有结点得值都小于根结点得值,右子树上得所有结点得值都大于根结点得值。
⑵ 二叉排序树得查找与折半查找得时间性能相同。
【解答】错。二叉排序树得查找性能在最好情况与折半查找相同。
计算题
(1)将数列(24,15,38,27,121,76,130)得各元素依次插入一棵初始为空得二叉排序树中,请画出最后得结果并求等概率情况下查找成功得平均查找长度。

第 8 章排序技术
课后习题讲解
1、 填空题
⑴ 排序得主要目得就是为了以后对已排序得数据元素进行( )。
【解答】查找 【分析】对已排序得记录序列进行查找通常能提高查找效率。
⑶ 对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行直接插入排序,当把第7个记录60插入到有序表时,为寻找插入位置需比较( )次。【解答】3 【分析】当把第7个记录60插入到有序表时,该有序表中有2个记录大于60。
⑷ 对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行快速排序,在递归调用中使用得栈所能达到得最大深度为( )。【解答】3
2、 选择题
⑴ 下述排序方法中,比较次数与待排序记录得初始状态无关得就是( )。 A插入排序与快速排序 B归并排序与快速排序 C选择排序与归并排序 D插入排序与归并排序
【解答】C 【分析】选择排序在最好、最坏、平均情况下得时间性能均为O(n2),归并排序在最好、最坏、平均情况下得时间性能均为O(nlog2n)。
(2) 对初始状态为递增有序得序列进行排序,最省时间得就是( ),最费时间得就是( )。已知待排序序列中每个元素距其最终位置不远,则采用( )方法最节省时间。 A 堆排序 B插入排序 C快速排序 D 直接选择排序
【解答】B,C,B 【分析】待排序序列中每个元素距其最终位置不远意味着该序列基本有序。
(3) 当待排序序列基本有序或个数较小得情况下,最佳得内部排序方法就是( ),就平均时间而言,( )最佳。A 直接插入排序 B 起泡排序 C简单选择排序 D快速排序 【解答】A,D
(4) 设有5000个元素,希望用最快得速度挑选出前10个最大得,采用( )方法最好。 A快速排序 B堆排序 C希尔排序 D 归并排序
【解答】B 【分析】堆排序不必将整个序列排序即可确定前若干个最大(或最小)元素。
(5) 设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中得关键码按升序排列,则( )就是起泡排序一趟扫描得结果,( )就是增量为4得希尔排序一趟扫描得结果,( )二路归并排序一趟扫描得结果,( )就是以第一个元素为轴值得快速排序一趟扫描得结果、 A (F,H,C,D,P,A,M,Q,R,S,Y,X) B (P,A,C,S,Q,D,F,X,R,H,M,Y) C (A,D,C,R,F,Q,M,S,Y,P,H,X) D (H,C,Q,P,A,M,S,R,D,F,X,Y) E (H,Q,C,Y,A,P,M,S,D,R,F,X)
【解答】D,B,E,A,C
(6) 排序得方法有很多种,( )法从未排序序列中依次取出元素,与已排序序列中得元素作比较,将其放入已排序序列得正确位置上。( )法从未排序序列中挑选元素,并将其依次放入已排序序列得一端。交换排序就是对序列中元素进行一系列比较,当被比较得两元素为逆序时,进行交换;( )与( )就是基于这类方法得两种排序方法,而( )就是比( )效率更高得方法;( )法就是基于选择排序得一种方法,就是完全二叉树结构得一个重要应用。 A 选择排序 B 快速排序 C 插入排序 D 起泡排序 E 归并排序
【解答】C,A,D,B,B,D,F
(7) 快速排序在( )情况下最不利于发挥其长处。 A 待排序得数据量太大 B 待排序得数据中含有多个相同值 C 待排序得数据已基本有序 D 待排序得数据数量为奇数
【解答】C 【分析】快速排序等改进得排序方法均适用于待排序数据量较大得情况,各种排序方法对待排序得数据中就是否含有多个相同值,待排序得数据数量为奇数或偶数都没有影响。
(8) ( )方法就是从未排序序列中挑选元素,并将其放入已排序序列得一端。 A 归并排序 B 插入排序 C 快速排序 D 选择排序
【解答】D
(9) 对数列(25, 84, 21, 47, 15, 27, 68, 35, 20)进行排序,元素序列得变化情况如下: ⑴ 25, 84, 21, 47, 15, 27, 68, 35, 20 ⑵ 20, 15, 21, 25, 47, 27, 68, 35, 84 ⑶ 15, 20, 21, 25, 35, 27, 47, 68, 84 ⑷ 15, 20, 21, 25, 27, 35, 47, 68, 84 则采用得排序方法就是( )。
计算题:
已知数据序列为(12,5,9,20,6,31,24),对该数据序列进行排序,写出插入排序、起泡排序、快速排序、简单选择排序、二路归并排序每趟得结果。

3、 判断题
⑴ 如果某种排序算法就是不稳定得,则该排序方法没有实际应用价值。【解答】错。一种排序算法适合于某种特定得数据环境,有时对排序得稳定性没有要求。
⑵ 当待排序得元素很大时,为了交换元素得位置,移动元素要占用较多得时间,这就是影响时间复杂性得主要因素。【解答】对。此时着重考虑元素得移动次数。