6．证明：生成树中最长路径的起点和终点的度均为１。 【解答】用反证法证明。 设v1, v2, …, vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然v1, v2, …, vk , v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。 同理可证起点v1的度不能大于1，只能为1。 7．已知一个连通图如图6-6所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。
【解答】邻接矩阵表示如下： 深度优先遍历序列为：v1 v2 v3 v5 v4 v6 广度优先遍历序列为：v1 v2 v4 v6 v3 v5 邻接表表示如下：
8．图6-7所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。 【解答】按Prim算法求最小生成树的过程如下： 按Kruskal算法求最小生成树的过程如下：
9．对于图6-8所示的带权有向图，求从源点v1到其他各顶点的最短路径。 【解答】从源点v1到其他各顶点的最短路径如下表所示。 源点 终点 最短路径 最短路径长度
v1 v7 v1 v7 7 v1 v5 v1 v5 11 v1 v4 v1 v7 v4 13 v1 v6 v1 v7 v4 v6 16 v1 v2 v1 v7 v2 22 v1 v3 v1 v7 v4 v6 v3 25 10．如图6-9所示的有向网图，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径。 【解答】从源点v1到其他各顶点的最短路径如下表所示。 源点 终点 最短路径 最短路径长度
v1 v3 v1 v3 15 v1 v5 v1 v5 15 v1 v2 v1 v3 v2 25 v1 v6 v1 v3 v2 v6 40 v1 v4 v1 v3 v2 v4 45 11．证明：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。 【解答】
任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2…vn-1，我们来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。 假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓扑序列v0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，导致矛盾。因此命题正确。 12. 算法设计
⑴ 设计算法，将一个无向图的邻接矩阵转换为邻接表。 【解答】先设置一个空的邻接表，然后在邻接矩阵上查找值不为零的元素，找到后在邻接表的对应单链表中插入相应的边表结点。 邻接矩阵存储结构定义如下： const int MaxSize=10; template struct AdjMatrix { T vertex[MaxSize]; 6.2.1 B. 6 C. 9 D .以上答案均不正确 【解答】A
2．无向图的邻接矩阵是一个（ ），有向图的邻接矩阵是一个（ ） A 上三角矩阵 B 下三角矩阵 C 对称矩阵 D 无规律 【解答】C，D
3．下列命题正确的是（ ）。 A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一 D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一 【解答】B
4．十字链表适合存储（ ），邻接多重表适合存储（ ）。 【解答】有向图，无向图 5. 在一个具有n 个顶点的有向完全图中包含有（ ）条边： A n(n-1)/2 B n(n-1) C n(n+1)/2 D n2 【解答】B 6．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（ ）个非零元素。 【解答】2(n-1) 7．表示一个有100个顶点，1000条边的有向图的邻接矩阵有（ ）个非零矩阵元素。 【解答】1000 8．一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（ ）棵树。 A k B n C n - k D 1 【解答】C
9．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（ ）。 A 逆拓扑有序 B 拓扑有序 C 无序 D 深度优先遍历序列 【解答】A 10. 关键路径是AOE网中（ ）。 A 从源点到终点的最长路径 B 从源点到终点的最长路径 C 最长的回路 D 最短
的回路 【解答】A
11. 已知无向图G的邻接表如图6-10所示，分别写出从顶点1出发的深度遍历和广度遍历序列，并画出相应的生成树。
【解答】深度优先遍历序列为：1，2，3，4，5，6 对应的生成树为： 广度优先遍历序列为：1，2，4，3，5，6 对应的生成树为：
12. 已知已个AOV网如图6-11所示，写出所有拓扑序列。 【解答】拓扑序列为：v0 v1 v5 v2 v3 v6 v4、 v0 v1 v5 v2 v6 v3 v4、 v0 v1 v5 v6 v2 v3 v4。
第 7 章查找技术 课后习题讲解 1. 填空题
⑴ 顺序查找技术适合于存储结构为（ ）的线性表，而折半查找技术适用于存储结构为（ ）的线性表，并且表中的元素必须是（ ）。 【解答】顺序存储和链接存储，顺序存储，按关键码有序
⑵ 设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（ ）次，至多需比较（ ）次。 【解答】1，7 【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。
⑶ 对于数列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（ ）。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（ ）。 【解答】8，59/15 【分析】根据数列将二叉排序树画出，将二叉排序树中查找每个结点的比较次数之和除以数列中的元素个数，即为二叉排序树的平均查找长度。 ⑷ 长度为20的有序表采用折半查找，共有（ ）个元素的查找长度为3。【解答】4 【分析】在折半查找判定树中，第3层共有4个结点。
⑸ 假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=k mod 7，则元素48的同义词是（ ）。 【解答】62 【分析】H(48)= H(62)=6
⑹ 在散列技术中，处理冲突的两种主要方法是（ ）和（ ）。 【解答】开放定址法，拉链法
⑺ 在各种查找方法中，平均查找长度与结点个数无关的查找方法是（ ）。 【解答】散列查找 【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。
⑻ 与其他方法相比，散列查找法的特点是（ ）。 【解答】通过关键码计算记录的存储地址，并进行一定的比较 2. 选择题
⑴ 静态查找与动态查找的根本区别在于（ ）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同C 所包含的数据元素的类型不一样 D 存储实现不一样【解答】B 【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。
⑵ 有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（ ）；在查找不成功的情况下，s和b的关系是（ ）。A s=b B s>b C s 【解答】D，D 【分析】此题没有指明是平均性能。例如，在有序表中查找最大元素，则顺序查找比折半查找快，而平均性能折半查找要优于顺序查找，查找不成功的情况也类似。⑶ 长度为 12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（ ），查找失败时的平均查找长度是（ ）。 A 37/12 B 62/13 C 3 9/12 D 49/13 【解答】A，B 【分析】画出长度为
12的折半查找判定树，判定树中有12个内结点和13个外结点。
⑷ 用n个键值构造一棵二叉排序树，其最低高度为（ ）。 A n/2 B n C log2n D log2n+1 【解答】D 【分析】二叉排序树的最低高度与完全二叉树的高度相同。
⑸ 二叉排序树中，最小值结点的（ ）。 A 左指针一定为空 B 右指针一定为空C 左、右指针均为空 D 左、右指针均不为空【解答】A 【分析】在二叉排序树中，值最小的结点一定是中序遍历序列中第一个被访问的结点，即二叉树的最左下结点。
⑹ 散列技术中的冲突指的是（ ）。 A 两个元素具有相同的序号 B 两个元素的键值不同，而其他属性相同C 数据元素过多 D 不同键值的元素对应于相同的存储地址【解答】D
⑺ 设散列表表长m=14，散列函数H(k)=k mod 11。表中已有15、38、61、84四个元素，如果用线性探侧法处理冲突，则元素49的存储地址是（ ）。
A 8 B 3 C 5 D 9 【解答】A 【分析】元素15、38、61、84分别存储在4、5、6、7单元，而元素49的散列地址为5，发生冲突，向后探测3个单元，其存储地址为8。
⑻ 在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查 找成功的情况下，所探测的这些位置的键值（ ）。 A 一定都是同义词 B 一定都不是同义词 C不一定都是同义词 D 都相同【解答】C 【分析】采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。 3. 判断题
⑴ 二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。 【解答】错。 分析二叉排序树的定义，是左子树上的所有结点的值都小于根结点的值，右子树上的所有结点的值都大于根结点的值。例如图7-7所示二叉树满足任一结点的值均大于其左孩子的值，小于其右孩子的值，但不是二叉排序树。
⑵ 二叉排序树的查找和折半查找的时间性能相同。 【解答】错。二叉排序树的查找性能在最好情况和折半查找相同。
⑶ 若二叉排序树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。 【解答】错。在二叉排序树中，最小元素所在结点一定是中序遍历序列中第一个被访问的结点，即是二叉树的最左下结点，但可能有右子树。最大元素所在结点一定是中序遍历序列中最后一个被访问的结点，即是二叉树的最右下结点，但可能有左子树。如图7-8所示，5是最小元素，25是最大元素，但5和25都不是叶子结点。
⑷ 散列技术的查找效率主要取决于散列函数和处理冲突的方法。 【解答】错。更重要的取决于装填因子，散列表的平均查找长度是装填因子的函数。
⑸ 当装填因子小于1时，向散列表中存储元素时不会引起冲突。 【解答】错。装填因子越小，只能说明发生冲突的可能性越小。4．分别画出在线性表（a，b，c，d，e，f，g）中进行折半查找关键码e和g的过程。【解答】查找关键码e的过程如图7-9所示，查找关键码g的过程如图7-10所示。
5．画出长度为10的折半查找判定树，并求等概率时查找成功和不成功的平均查找长度。 【解答】参见7.2.1。
6．将数列（24，15，38，27，121，76，130）的各元素依次插入一棵初始为空的二叉排序树中，请画出最后的结果并求等概率情况下查找成功的平均查找长度。【解答】二叉排序树如图7-11所示，其平均查找长度=1+2×2+3×2+4×2=19/7
7．一棵二叉排序树的结构如图7-12所示，结点的值为1～8，请标出各结点的值。【解答】二叉排序树中各结点的值如图7-13所示。8．已知散列函数H(k)=k mod 12，键值序列为(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82)，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。【解答】H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3, H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10 构造的开散列表如下： 平均查找长度ASL=(8×1+4×2)/12=16/12
9. 算法设计⑴ 设计顺序查找算法，将哨兵设在下标高端。
【解答】将哨兵设置在下标高端，表示从数组的低端开始查找，在查找不成功的情况下，算法自动在哨兵处终止。具体算法如下： ⑵ 编写算法求给定结点在二叉排序树中所在的层数。 【解答】根据题目要求采用递归方法，从根结点开始查找结点p，若待查结点是根结点，则深度为1，否则到左子树（或右子树）上去找，查找深度加1。具体算法如下： ⑶ 编写算法，在二叉排序树上找出任意两个不同结点的最近公共祖先。 【解答】设两个结点分别为A和B，根据题目要求分下面情况讨论： ⑴ 若A为根结点，则A为公共祖先； ⑵ 若A->datadata且root->datadata，root为公共祖先； ⑶ 若A->datadata且B->datadata，则到左子树查找； ⑷ 若A->data>root->data且B->data>root->data，则到右子树查找。具体算法如下： ⑷ 设计算法判定一棵二叉树是否为二叉排序树。 【解答】对二叉排序树来讲，其中序遍历序列为一个递增序列。因此，对给定二叉树进行中序遍历，如果始终能够保证前一个值比后一个值小，则说明该二叉树是二叉排序树。
具体算法如下： 学习自测及答案
1．已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，经过（ ）次比较后查找成功。 A 2 B 3 C 4 D 5 【解答】A 2．已知10个元素（54，28，16，73，62，95，60，26，43），按照依次插入的方法生成一棵二叉排序树，查找值为62的结点所需比较次数为（ ）。 A 2 B 3 C 4 D 5 【解答】B 3．已知数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ）。 A 4 B 5 C 6 D 7 【解答】B 4．按（ ）遍历二叉排序树得到的序列是一个有序序列。 A 前序 B 中序 C 后序 D 层次【解答】B 5．将二叉排序树T按前序遍历序列依次插入初始为空的二叉排序树T '中，则T与T'是相同的，这种说法是否正确 【解答】正确 6. 一棵高度为h的平衡二叉树，最少含有个结点。 A 2h B 2 h -1 C 2 h +1 D 2 h -1 【解答】D 7．在散列函数H(k)= k mod m中，一般来讲，m应取（ ）。 A 奇数 B 偶数 C 素数 D 充分大的数【解答】C
8．已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为0~16，设散列函数为H(x)= ，其中i为关键码中第一个字母在字母表中的序号，采用线性探测法和链地址法处理冲突，试分别构造散列表，并求等概率情况下查找成功的平均查找长度。【解答】H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用线性探测法处理冲突，得到的闭散列表如下：
平均查找长度=(1+1+1+1+2+4+5+2+3+5+6+1)/12=32/12 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1×7+2×4+3×1)/12=18/12 第九题 9. 试推导含有12个结点的平衡二叉树的最大深度，并画出以棵这样的树。【解答】令Fk表示含有最少结点的深度为k的平衡二叉树的结点树目，则： F1=1，F2=2，…，Fn= Fn-2+Fn-1+1。含有12 个结点的平衡二叉树的最大深度为5，_______________例如：