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

第 6 章图课后习题讲解1、 填空题 设无向图G中顶点数为n,则图G至少有( )条边,至多有( )条边;若G为有向图,则至少有( )条边,至多有( )条边。 【解答】0,n(n-1)/2,0,n(n-1) 【分析】图得顶点集合就是有穷非空得,而边集可以就是空集;边数达到最多得图称为完全图,在完全图中,任意两个顶点之间都存在边。 任何连通图得连通分量只有一个,即就是( )。【解答】其自身 图得存储结构主要有两种,分别就是( )与( )。【解答】邻接矩阵,邻接表 已知一个有向图得邻接矩阵表示,计算第j个顶点得入度得方法就是( )。【解答】求第j列得所有元素之与 有向图G用邻接矩阵Ann存储,其第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)进行快速排序,在递归调用中使用得栈所能达到得最大深度为( )。【解答】32、 选择题 下述排序方法中,比较次数与待排序记录得初始状态无关得就是( )。 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、 判断题 如果某种排序算法就是不稳定得,则该排序方法没有实际应用价值。【解答】错。一种排序算法适合于某种特定得数据环境,有时对排序得稳定性没有要求。 当待排序得元素很大时,为了交换元素得位置,移动元素要占用较多得时间,这就是影响时间复杂性得主要因素。【解答】对。此时着重考虑元素得移动次数。