资源描述：
《数据结构（C++版）课后作业6~8章附答案解析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6章图课后习题讲解1.填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。⑵任何连通图的连通分量只有一个，即是（）。【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。【解答】邻接矩阵，邻接表⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。【解答】求第j列的所有元素之和
2、⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。【解答】前序，栈，层序，队列（8）如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。【解答】回路2.选择题⑵n个顶点的强连通图至少有（）条边，其形状是（）。AnBn+1Cn-1Dn×(n-1)E无回路F有回路G环状H树状【解答】A，G⑶含n个顶点的连通图中的任意一条简单路径，其长度不可能超过
3、（）。A1Bn/2Cn-1Dn【解答】C【分析】若超过n-1，则路径中必存在重复的顶点。（4）最小生成树指的是（）。A由连通网所得到的边数最少的生成树B由连通网所得到的顶点数相对较少的生成树C连通网中所有生成树中权值之和为最小的生成树D连通网的极小连通子图【解答】C（5）下面关于工程计划的AOE网的叙述中，不正确的是（）A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动都提前完成，那么整个工程将会提前完成D某些关键活动若提前完成，那么整个工程将会提前完【解答
4、】B【分析】AOE网中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前整个工程，而必须同时提高在几条关键路径上的关键活动。3.判断题（1）用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。【解答】对。邻接矩阵的空间复杂度为Ｏ(n2)，与边的个数无关。（2）图G的生成树是该图的一个极小连通子图【解答】错。必须包含全部顶点。（3）在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。【解答】错。只能说明从顶点a到顶点b有一条路径。7．已知一个连通图如图所示，试给出图的邻接
5、矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。8．图所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。自己做。第7章查找技术（3）在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。【解答】散列查找【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。2.选择题（1）设散列表表长m=14，散列函数H(k)=kmod11。表中已有15、38、61、84四个元素，如果用线性探侧法处理冲突，则元素49的存储地址是（
6、）。【解答】A【分析】元素15、38、61、84分别存储在4、5、6、7单元，而元素49的散列地址为5，发生冲突，向后探测3个单元，其存储地址为8。3.判断题⑴二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。【解答】错。分析二叉排序树的定义，是左子树上的所有结点的值都小于根结点的值，右子树上的所有结点的值都大于根结点的值。⑵二叉排序树的查找和折半查找的时间性能相同。【解答】错。二叉排序树的查找性能在最好情况和折半查找相同。计算题（1）将数列（24，15，38，27，121，76，130）的各元素依
7、次插入一棵初始为空的二叉排序树中，请画出最后的结果并求等概率情况下查找成功的平均查找长度。第8章排序技术课后习题讲解1.填空题⑴排序的主要目的是为了以后对已排序的数据元素进行（）。【解答】查找【分析】对已排序的记录序列进行查找通常能提高查找效率。⑶对一组记录（54,38,96,23,15,72,60,45,83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。【解答】3【分析】当把第7个记录60插入到有序表时，该有序表中有2个记录大于60。⑷对一组记录（54,38,96,23,15,72,
8、60,45,83）进行快速排序，在递归调用中使用的栈所能达到的最大深度为（）。【解答】32.选择题⑴下述排序方法中，比较次数与待排序记录的初始状态无关的是（）。A插入排序和快速排序B归并排序和快速排序C选择排序和归并排序D插入排序和归并排序【解答】C【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归
