发布时间 : 星期五 文章数据结构(C++版)课后作业6-8章附答案更新完毕开始阅读
第 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的生成树是该图的一个极小连通子图 【解答】错。只能说明从顶点a到顶点b有一条路径。
7．已知一个连通图如图所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。
【解答】错。必须包含全部顶点。
（3）在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。
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。