第7章 查 找
1．选择题
BBCDB CDBBA
2．填空题
（1）(n+1)/2，((n+1)*log2(n+1))/(n-1)，(s2+2s+n)/2s，log2 (n/s+1)+s/2，1+a（a为装填因子）
（2）哈希表查找方法
（3）顺序存储结构，有序的
（4）索引，块
（5）15
（6）素数
（7）1，2，4，8，5，3.7
（8）O(n)，O(log2 n)，O(n1/2)
3．问答题
（1）略。
（2）构造相应的判定树，如图A-14所示（图中节点的值对应元素的关键字），先找中间节点45，再找77、95，最后找到82，经过4次比较。
图A-14 一棵判定树
（3）平均时间为(1+2+3+4+…+n)/n=(n+1)/2。
（4）依次为GA、DA、B、G、L、A2、A3、A4及E。
（a）溢出时，使用线性探测法 （b）溢出时，使用链地址法
4．上机操作题
（1）按中序遍历二叉排序树可得到一个按键值从小到大排列的有序表，利用这个特点来判断二叉树是否为二叉排序树，算法如下：
# define max 999
# define mix 0
int judge(BTnode*bt)
{
BTmode*s[max],*p=bt;
int top=0,preval=min;
do{
while(p)
{
s[top++]=p;
p=p->lchild;
}
if(top>0)
{
p=s[--top];
if(p->data<preval)
return(0);
preval=p->data;
p=p->rchild;
}
}while(p||top>0);
Return(1);
}
（2）算法如下：
#define max 1000
void order(BTnode *t,int x)
{
int top=0;
do{
while(p)
{
s[top++]=p;
p=p->rchild;
}
if(top>0)
{
p=s[--top]
if(p->data<x)
return;
printf("%d,",p->data);
p=p->lchild;
}
}while(top>0||p);
}
（3）表中节点类型定义如下：
typedef struct node{int data;
struct node*next;}Lnode;
算法描述如下：
void Searchlen(Lnode*HT[ ],int m)
{
Lnode*p;
int j=0,i,n;
fliat ss=0.0,su=0.0;
for(i=0;i<m;i++)
{
p=HT[i];
n=0;
while(p)
{
n+ +;
j++;
ss+=n;
p=p->next;
}
su+=n;
}
ss=ss/j;
su=su/m;
printf("ASL =%f",ss);
printf("ASL =%f",su);
}