elsereturnOK;
}
求得561234
7.11试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径,写出执行算法过程中各步的状态。
7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。
注意：
算法中涉及的图的基本操作必须在此存储结构上实现。
解：
intvisited[MAXSIZE];//指示顶点是否在当前路径上
intexist_path_DFS（ALGraphG,inti,intj）//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
if（i==j）return1;//i就是j
else
{
visited[i]=1;
for（p=G.vertices[i].firstarc;p;p=p->nextarc）
{
k=p->adjvex;
if（!
visited[k]&&exist_path（k,j））return1;//i下游的顶点到j有路径
}//for
}//else
}//exist_path_DFS
7.23③同7.22题要求。
试基于图的广度优先搜索策略写一算法。
解：
intexist_path_BFS（ALGraphG,inti,intj）//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
intvisited[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）return1;
if（!
visited[k]）EnQueue（Q,k）;
}//for
}//while
return0;
}//exist_path_BFS
第9章查找
9.2试分别画出在线性表（a,b,c,d,e,f,g）中进行折半查找，以查关键字等于e,f和g的过程。
解：
1）查找e的过程如下：
2）查找f的过程
3）查找g的过程
9.3画出对长度为10的有续表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
解：
9.9已知如下所示长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）
（1）试按表中元素的顺序依次插入一查初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
（2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
（3）按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
解：
（1）求得的二叉排序树如下图所示：
在等概率情况下查找成功的平均查找长度为：
ASL成功=（1+2*2+3*3+4*3+5*2+6*1）/12=42/12=3.5
（2）分析：
对表中元素进行排序后，其实就变成了对长度为12的有序表进行折半查找了，那么在等概率的情况下的平均查找长度只要根据折半查找的判定树就很容易求出。
所以可求出：
ASL成功=（1+2*2+4*3+5*4）/12=37/12
（3）平衡二叉树的构造过程
平衡二叉树为
9.21在地址空间为0~16的散列区中，对以下关键字序列构造两哈希表：
（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）
（1）用线性探测开放定址法处理冲突；
（2）用链地址法处理。
并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。
设哈希函数为H（x）=i/2取整,其中i为关键字中第一个字母在字母表中的序号。
解：
（1）因为：
H（Jan）=5;
H（Feb）=3;
H（Mar）=6;
H（Apr）=0;
H（May）=6;H1（May）=7;
H（June）=5;H1（June）=6;H2（June）=7;H3（June）=8
H（July）=5;H1（July）=6;H2（July）=7;H3（July）=8;H4（July）=9;
H（Aug）=0;H1（Aug）=1
H（Sep）=9;H1（Sep）=10
H（Oct）=7;H1（Oct）=8;H2（Oct）=9;H3（Oct）=10;H4（Oct）=11;
H（Nov）=7;H1（Nov）=8;H2（Nov）=9;H3（Nov）=10;H4（Nov）=11;H5（Nov）=12;
H（Dec）=2
所以，用线性探测开放定址法处理冲突构造的哈希表如下图所示：
012345678910111213141516
Apr
Aug
Dec
Feb
Jan
Mar
May
June
July
Sep
Oct
Nov
Ci:
121111245256
并求得：
ASL成功=（1*5+2*3+4+5*2+6）/12=31/12
ASL不成功=（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14=60/14
（2）用链地址法处理冲突构造的哈希表如下图所示：
^
^
^
^
^
^
^
^
^
^
并求得：
ASL成功=（1*7+2*4+3）/12=18/12
ASL不成功=（1*3+2*3+3）/14=12/14
9.25假设顺序表按关键字自大至小有序，试改写教科书9.1.1节中的顺序查找算法，将监视哨设在高下标端。
然后画出描述此查找过程的判定树，分别求出等概率下查找成功和不成功的平均查找长度。
解：
（1）顺序表的存储结构描述：
Typedefstruct{
Keytypekey;
}Elemtype;//记录类型；
typedefstruct{
Elemtype*elem;
intlength;
}SSTable;//顺序表类型；
按要求所得算法如下：
intSearch（SSTableST,Keytypekey）
{ST.elem[ST.length].key=key;
for（i=0;keyif（i==ST.length）return0;
elseif（key==ST.elem[i].key）returni;
elsereturn0;
}
（2）按此查找过程的判定树如下图所示：
（3）等概率下的查找成功与查找不成功的平均查找长度分别为：
、
ASL成功=（1+2+3+….+n）/n=（n+1）/2
ALS不成功=（2+3+…+n+（n+1））/n=（n+2）/2
9.26试将折半查找的算法改成递归算法。
intSearch_Bin_Recursive（SSTableST,intkey,intlow,inthigh）//折半查找的递归算法
{
if（low>high）return0;//查找不到时返回0
mid=（low+high）/2;
if（ST.elem[mid].key==key）returnmid;
elseif（ST.elem[mid].key>key）
returnSearch_Bin_Recursive（ST,key,low,mid-1）;
elsereturnSearch_Bin_Recursive（ST,key,mid+1,high）;
}
}//Search_Bin_Recursive
9.32已知一棵二叉排序树上所有关键字中的最小值为-max，最大值为max，又-max编写具有如下功能的函数：
求该二叉树上小于x且最靠近x的值a和大于x且最靠近x的b。
intlast=0;
voidMaxLT_MinGT（BiTreeT,intx）//找到二叉排序树T中小于x的最大元素和大于x的最小元素
{
if（T->lchild）MaxLT_MinGT（T->lchild,x）;//本算法仍是借助中序遍历来实现
if（lastdata>=x）//找到了小于x的最大元素
printf（"a=%d\n",last）;
if（last<=x&&T->data>x）//找到了大于x的最小元素
printf（"b=%d\n",T->data）;
last=T->data;
if（T->rchild）MaxLT_MinGT（T->rchild,x）;
}//MaxLT_MinGT
升级会员 