深度优先搜索树：
（2）广度优先搜索
顶点序列：1-2-3-6-5-4 边的序列：（1，2）（1，3）（1，6）（1，5）（5，4）
深度优先搜索树：
注：本题中所求深度优先序列和广度优先序列有多种，以上为其中一种。 7．3 【解答】
源点 终点 最短路径 路径长度 1 2 1，3，2 19 3 1，3 15 4 1，3，2，4 29 5 1，3，5 29 6 1，3，2，4，6 44 7．12 【解答】
1. 深度遍历：1，2，3，8，4，5，7，6或1，2，3，8，5，7，4， 2. 广度遍历：1，2，4，6，3，5，7，8 3. 拓扑序列：1，2，4，6，5，3，7，8 4. 最短路径：1，2，5，7，8
5. 关键路径：1，6，5，3，8 7．13 【解答】 按层遍历二叉树
LayerOrder(BiTree root) { LinkQueue Q; InitQueue(&Q); if(root==NULL) return; EnterQueue(&Q,root); while(!Empty(&Q)) { DelQueue(&Q,&p); visite(p->data); if(p->LChild!=NULL) EnterQueue(&Q,p->LChild); if(p->RChild!=NULL) EnterQueue(&Q,p->RChild); } }
第八章 实习题
习题
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 22 1
1
2 41 1
3 30 2
4 01 2
5 53 1
6 46 1
7 13 2
8 67 6
9
10
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.191 ASL定义计算平均查找长度。