}//else
}//exist_path_DFS
7.9
同上题要求。试基于图的广度优先搜索策略写一算法。
int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 {
int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i);
while(!QueueEmpty(Q)) {
DeQueue(Q,u); visited[u]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc) {
k=p->adjvex; if(k==j) return 1;
if(!visited[k]) EnQueue(Q,k); }//for }//while return 0;
}//exist_path_BFS
7.10
试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。
void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G {
int visited[MAXSIZE]; InitStack(S);
Push(S,GetVex(S,1)); //将第一个顶点入栈 visit(1); visited=1;
while(!StackEmpty(S)) {
while(Gettop(S,i)&&i) {
j=FirstAdjVex(G,i); if(j&&!visited[j]) {
visit(j);
visited[j]=1;
Push(S,j); //向左走到尽头 }
}//while
if(!StackEmpty(S)) {
Pop(S,j); Gettop(S,i);
k=NextAdjVex(G,i,j); //向右走一步 if(k&&!visited[k]) {
visit(k); visited[k]=1; Push(S,k); } }//if }//while
}//Straverse_Nonrecursive
分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.
7.11
采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。
[提示]：利用深度搜索，增设一个深度参数，深度超过k 则停止对该结点的搜索。
int visited[MAXSIZE];
int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 {
if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) {
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc) {
l=p->adjvex; if(!visited[l])
if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for
visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else
return 0; //没找到 }//exist_path_len
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 1 6 0 v1 ④ 3 1 4 6 5 50 ∧ 3 11 ∧
1 2 v2 v3 v4 v5 v6 v7 v8 ∧ 2 43 7 8 ∧ 4 12 ∧ 2 38 7 20 ∧ 题12图 4 1 3 4 5 6 24 ∧ 6 12 ∧ 6 7 7.13
已知一棵以二叉链表作存储结构的二叉树，试编写按层次顺序（同一层自左至右）遍历二叉树的算法。
void LayerOrder(Bitree T)//层序遍历二叉树 {
InitQueue(Q); //建立工作队列 EnQueue(Q,T);
while(!QueueEmpty(Q)) {
DeQueue(Q,p); visit(p);
if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }
}//LayerOrder
第八章 查找
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）右子树的左端大于根
int last=0,flag=1;
int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0 {
if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->data
if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree
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定义计算平均查找长度。
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
void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间 {
if(T->rchild) Delete_NLT(T->rchild,x);