[提示]：可利用任何递归、非递归遍历算法。

20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。 [提示]： [方法一]：

（1）利用队列，初值为根

（2 ）出队访问，并将左、右子入队，直到队空 （3）记录每一层中最后一个结点在队中的位置

（4 ）第i 层最后一个结点的右子，必是第i+1 层的最后一个结点 （5）第1 层最后一个结点在队中的位置为0 [方法二]：利用层号和全局数组，任意遍历、统计 21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。 22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树； 给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树； 23. 二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。 第七章 7.1 已知如图所示的有向图，请给出该图的： （1） 每个顶点的入度、出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 十字链表； （6） 强连通分量。

7.2 已知如图所示的无向图，请给出该图的： （1） 邻接多重表；（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。） （2） 从顶点1 开始，深度优先遍历该图所得顶点序列和边的序列；（给出深度优先搜索树）

（3） 从顶点1 开始，广度优先遍历该图所得顶点序列和边的序列。（给出广度优先搜索树）

7.3已知如图7.31 所示的AOE-网，试求：

（1） 每个事件的最早发生时间和最晚发生时间； （2） 每个活动的最早开始时间和最晚开始时间； （3） 给出关键路径。

7.4 已知如图7.30 所示的有向网，试利用 Dijkstra 算法求顶点 1 到其余顶点的最短路径，并给出算法执行过程中各步的状态。

7.5编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。 [参例题]

7.6试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v); InsertArc(G, v, w); DeleteVertex(G,v)和 DeleteArc(G, v, w)。 7.7 试对邻接表存储结构重做题 6。

7.8 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点v 到顶点v 的路径（i≠j ）。注意：算法中涉及的图的基本操作必须在此存储

结构上实现。

7.9 同上题要求。试基于图的广度优先搜索策略写一算法。

7.10 试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法。算法中不规定具体的存储结构，而将图 Graph 看成是一种抽象数据类型。

7.11 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为 k 的简单路径（指顶点序列中不含有重现的顶点）的算法。

[提示]：利用深度搜索，增设一个深度参数，深度超过k 则停止对该结点的搜索。

7.12 下图是带权的有向图 G 的邻接表表示法。从结点V1 出发，深度遍历图G 所得结点序列为（A），广度遍历图G 所得结点序列为（B）；G 的一个拓扑序列是（C）；从结点 V1 到结点 V8 的最短路径为（D）；从结点V1 到结点 V8 的关键路径为（ E ）。 其中A、B、C 的选择有：

① V1,V2,V3,V4,V5,V6,V7,V8 ② V1,V2,V4,V6,V5,V3,V7,V8 ③ V1,V2,V4,V6,V3,V5,V7,V8 ④ V1,V2,V4,V6,V7,V3,V5,V8 ⑤ V1,V2,V3,V8,V4,V5,V6,V7 ⑥ V1,V2,V3,V8,V4,V5,V7,V6 ⑦ V1,V2,V3,V8,V5,V7,V4,V6 D、E 的选择有：

① V1,V2,V4,V5,V3,V8 ② V1,V6,V5,V3,V8 ③ V1,V6,V7,V8 ④ V1,V2,V5,V7,V8

第八章

8.1 若对大小均为 n 的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？

（1） 查找不成功，即表中没有关键字等于给定值K 的记录。 （2） 查找成功，且表中只有一个关键字等于给定值K 的记录。

（3） 查找成功，且表中有若干个关键字等于给定值 K 的记录，一次查找要求找出所有记录。

[提示]：均用顺序查找法。

8.2 画出对长度为 10 的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

[提示]：根据P.191 ASL 定义计算平均查找长度。

8.3 试推导含 12 个结点的平衡二叉树的最大深度并画出一棵这样的树。

[提示]：沿最左分支生长，前提是：其任一祖先的右分支与左分支等深，如不等深，则先生 长右分支，而生长右分支的前提是：其任一祖先的左分支与右分支等深，如不等深，则先生 长左分支，如此交互考虑，逐步生长，直到 12 个结点。 8.4 试从空树开始，画出按以下次序向 2-3 树，即 3 阶B-树中插入关键码的建树过程：20， 30，50，52，60，68，70。如果此后删除50 和68，画出每一步执行后2-3 树的状态。

8.5 选取哈希函数 H(k)=(3k)，用线性探测再散列法处理冲突。试在0～10 的散列地址 空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。 [提示]：平均查找长度参考P.225。

0 1 2 3 4 5 6 7 8 9 10 22 41 30 01 53 46 13 67 1 1 2 2 1 1 2 6 ASLsucc = (1×4 + 2×3 + 6) / 8 = 2

ASLunsucc = ( 2 + 1 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 ) / 11 = 40 / 11

8.6 试为下列关键字建立一个装载因子不小于 0.75 的哈希表，并计算你所构造的哈希表的 平均查找长度。

（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG， JIN） [提示]：（1）由装填因子求出表长，（2）可利用字母序号设计哈希函数， （3）确定解决冲突的方法。

8.7 试编写利用折半查找确定记录所在块的分块查找算法。

8.8 试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结 构，且树中结点的关键字均不同。

[提示]：检验中序遍历序列是否递增有序？

[方法 1]：用非递归中序遍历算法，设双指针pre, p 一旦 pre->data > p->data 则返回假

[方法2]：用递归中序遍历算法，设全局指针pre，（参中序线索化算法） 一旦 pre->data > p->data 则返回假 [方法3]：用递归（中序或后序）算法

（1）空树是（2）单根树是（3）左递归真（4）右递归真 （5）左子树的右端小于根（6）右子树的左端大于根

8.9 编写算法，求出指定结点在给定的二叉排序树中所在的层数。

8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结 点A、B 中，A 是 B 的祖先，则认为A 是A、B 的最近公共祖先）。 [提示]：

（1） 假设A<=B，

（2） 从根开始，左走或右走，直到A 在左（或根），B 在右（或根）。

8.11 编写一个函数，利用二分查找算法在一个有序表中插入一个元素 x，并保持表的有序 性。 [提示]：（1）表中已经有x，（2）表中没有x 参 P. 231

8.12 已知长度为12 的表：

（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。 （1） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。 （2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 （3） 按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功的平均查找长度。

[提示]：画出判定树或排序树，根据P.191ASL 定义计算平均查找长度。

8.13 含有 9 个叶子结点的 3 阶 B-树中至少有多少个非叶子结点？含有 10 个叶子结点的 3阶B-树中至少有多少个非叶子结点？ [提示]：叶子结点对应空指针。

8.14 写一时间复杂度为O(log2n + m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。 [提示]：

（1） p=root

（2） 如果p->key 大于、等于x，则删除p->rchild 和 p， （3） 左走一步，转（2）

（4） 如果p->key 小于x，则反复右走， （5） 转（2）

（6） 直到p==NULL

8.15 在平衡二叉排序树的每个结点中增加一个lsize 域，其值为它的左子树中的结点数加1。编写一时间复杂度为 O(log n)的算法，确定树中第k 个结点的位置。 [提示]：先画图手工求。 （1）sum=0,

（2）从当前根开始沿左链找sum + lsize<=k 的最大结点a，

（3）沿a 的右链求sum=sum + lsize，直到结点b，sum + lsize(b)>=k 重复（2）、（3），直到sum=k

第九章

9.1 以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手 工执行以下排序算法，写出（前三趟）每一趟排序结束时的关键码状态： （1）直接插入排序； （2）希尔排序（增量d[1]=5）； （3）快速排序； （4）堆排序； （5）归并排序； （6）基数排序。

9.2 一组关键字码，40，27，28，12，15，50，7，采用快速排序或堆排序，写出每趟 排序结果。9.3 不难看出，对长度为 n 的记录序列进行快速排序时，所需进行的比较次数依赖于这 n个元素的初始排列。n=7 时在最好情况下需进行多少次比较？请说明理由。 对 n=7 给出一个最好情况的初始排列实例。（保证每个基准记录都是中间记录） 9.4 假设序列由 n 个关键字不同的记录构成，要求不经排序而从中选出关键字从大到小顺序的前k(k<

9.5 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后 的插入排序算法。

9.6 编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。 [提示]：（1）参快速排序（2）“水底”、“水面”相遇时结束。

9.7 编写算法，对 n 个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：

采取顺序存储结构，至多使用一个记录的辅助存储空间； 算法的时间复杂度 O(n)；

讨论算法中记录的最大移动次数。

[提示]：r[0]=r[1]，以0 为分界值，参快速排序划分过程，但不要求对元素排序。 9.8 试以单链表为存储结构实现简单选择排序的算法 9.9 假设含 n 个记录的序列中，其所有关键字为值介于 v 和 w 之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组 number[v...w]且令 number[i]为统计关键字取整数 I 的记录数，之后按 number 重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。

9.10 已知两个有序序列(a , a ,..., a )和(a , a ,..., a ),并且其中一个序列的记录个数少于s,且s= floor ( sqrt (n) ). 试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。 9.11 偶交换排序如下所述：第一趟对所有奇数 i,将 a[i]和 a[i+1]进行比较；第二趟对所有偶数 i,将 a[i]和 a[i+1]进行比较，若 a[i]>a[i+1],则将两者交换；第一趟对所有奇数 i, 第二趟对所有偶数 i，?,依次类推直至整个序列有序为止。 （1） 这种排序方法的结束条件是什么？ （2） 分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。

（3） 写出奇偶交换排序的算法。 9.12 设计一个用链表表示的直接选择排序算法。（与9.8 重）

9.13 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后 的插入排序算法。（与9.5 重复）

9.14 一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。（与9.7 类似）

9.15 为什么通常使用一维数组作为堆的存放形式？

9.16 已知（k ,k ,?，k ）是堆，写一个算法将（k ,k ,?，k ，k）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。

9.17 试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基 数排序的时空性能、稳定性和适用情况。

9.18 在供选择的答案中填入正确答案： 1 ）、排序（分类）的方法有许多种：__A_③_法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；__B①__法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。__C_④__和__D②__是基于这类方法的两种排序方法，而__D__是比__C__效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是__E_⑦_ 。 供选择答案

① 选择排序 ② 快速排序 ③ 插入排序 ④ 冒泡排序 ⑤ 归并排序 ⑥ 二分排序 ⑦ 哈希排序 ⑧ 基数排序 2）、一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个 记录为基准得到的一次划分结果为 C 。 A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，79 3）、下列排序算法中，C算法可能会出现下面情况：初始数据有序时，花费时间反而最多。 A、堆排序 B、冒泡排序 C、快速排序 D、SHELL 排序 9.19 判断正误：

（ ）在一个大堆中，最小元素不一定在最后。

（ X ）对n个记录采用快速排序方法进行排序，最坏情况下所需时间是o （nlog2n）。 （ X ）在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。

第 1 章 绪论

1．4 试编写算法，求一元多项式P (x)=a +a x+a x +a x +?a x 的值P (x )，并确定算法中