}
2．将折半查找的算法改写为递归算法。
【提示】对于每次查找的思想是相同的，只是查找区间发生了变化，因此折折半查找算法改写为递归算法时要将查找区间的上下限作为参数，递归调甩时查找区间的上下限是变化的。
int BinSearch(datatype R[]，int low, int hig, keytype K) {int mid;
if (low < hig) retum(0); else {mid =(low＋hig)/2；
if(K==R[mid].key)return(mid);
else if(K＞R[mid].key)return(Bitiseareh(R,mid+1,hig,K))； else return(Binsrch(R,low,mid-1); } }
3.编写算法，利用折半查找算法在一个有序表中插入一个元素x，并保持表的有序性。 【提示】先在有序表R中利用折半查找法查找关键字值小于或等于x的结点，mid指向关键字正好等于x的结点或low指向关键字正好大于x的结点，然后采用移动法插入x结点即可。
void Binlnsert(datatype R[]，KeyType x) {int low =1,hig＝n,mid,inplace,i,find＝0; while(low<=hig&&!find) {mid=(low+hig)/2);
if(x.key＜R[mid].key)hig=mid-1;
else if(x.key>R[mid].key) low＝mid+1； else { i = mid; find=1； } }
if(find)inspace=mid; else inspace＝low;
for(i=n;i >=inspace；i--)R[i+l]=R[i]; R[inspac]=x; }
4.假设二叉排序树T的各个元素值均不相同，设计一个算法按递减次序打印各元素的值。
【提示】调整中序递归遍历算法，先遍历右子树，然后输出根结点的值，再遗历左子树。
viod PrintNode(BiSTree T) {if(T)
{PrintNode(T->rchild); printf（T->data）； PrintNode(T->lchild); }
5.已知一棵二叉排序树上所有关键字中的最小值为-max，最大值为max，又知-max 【提示】解决本题的关键是递归函数的参数设置，采用逐渐缩小查找区间的方法来实现。 void fun(BiSTree T,int x,int *a,int *b) {if(T) if(x fun(T=>lchild, x,a,b); } else if（x>T->data) /*当x大于根结点时，修改a,在右子树上继续查找*/ {*a=T->data.key; fun(T=>rchild, x,a,b); } else /*当x等于根结点时，a是其左子树的最右下结点，b是其右子树的最左下结点*／ {if(T->lchild) {p=T->lchild; while(p-> rchilt) p = p - > rchiid; *a = p -> data.key; } if(T->rchild） {P＝T->rchild； while(P->lchild）P＝P->lchild； *b=p->data.key; } } } 6.在平衡二叉排序树的每个结点中增设一个lsize域，其值为它的左子树中的结点数加1。试写时间复杂度为O(log2n)的算法，确定树中第k小的结点的位置。 【提示】由二叉排序树的性质和lsize域的定义可知，第k小的结点即lsize域的值为k的结点。因此，可以采用递归算法在二叉排序树中查找这样的结点。 typedef struct BiTNode ｛datatype data； int lsize； struct BiTNode *lehild，*rchild； ｝BiTNode，*BiTree；／*增设lsize 域的二叉树的类型定义*／ Biffree Index(BiTree T, int k) {if(T==NULL) return(NULL)；／*若根结点t为空则查找失败*／ if(T->lsize==k) return（T）；／*找到第k小结点，返回其地址*／ else if(T->lsize > k) Index(T->lchild;k)；／*若k小于根结点，在左子树继续查找*/ else Index(T->rchild;k)；/*若k大于根结点，在右子树继续查找*／ } 7.假设一棵平衡二叉树的每个结点都标明了平衡因子bf，设计算法求平衡二叉树的高度。 ［提示］因为二叉树各结点已标明了平衡因子bf，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子bf为0时，任选左右一分支向下查找，若bf不为0，则沿左（当bf=1时）或右（当bf=-1时）向下查找。 typedef struct bsnode { datatyte data； struct bsnode *lchild,*rchild； int bf; ／*结点的平衡因子*／ ｝BBiST Node，BBiSTree；／*带平衡因子域的平衡二叉树的类型定义*／ int Height(BBiSTree T) ／*求平衡二叉树T的高度*／ {int level＝0； BBiSTree p=T; while(p) {level++； ／*树的高度增1．／ if(p->bf<0) p=p->rehild； ／*bf＝-1，沿右分支向下*／ else p=p-＞lchild; /*hf >=0，沿左分支向下*／ } return（level）； } 8.设计在有序顺序表上进行斐波那契查找的算法，并画出长度为20的有序表进行斐波那契查找的判定树，求出在等概率下查找成功的平均查找长度。 【提示】采用类似折半查找的算法，按照斐波那契数列分割查找表，实现查找。 int Fibo_Search(SSTable L，keytype x，int fibo[]) /*向量fibo中为斐波那契分割序列*/ {int low＝1； int high=L.length； /*设L.length=fibo[K]-1*/ while(low<=high) { mid = low+fibo[K-1]； if(x＜L.elem[mid])high=mid-1; else if ( x > L. elemR[mid])low＝mid + 1； else return(mid)； } retum(0)； } 9.试编写一个判定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。 【提示】 判断一棵二叉树是二叉排序树，可以采用递归算法。对于树中所有结点，检查其左子树上所有结点的关键字是否都小于它的关键字，检查其右子树上所有结点的关键字是否都大于它的关键字。 int BinsortTree(BisTree T) /*判别由二叉链表存储的二叉树是否为二叉排序树，是则返回1，否则返回0*/ { int l,r: if(!T) return 1; /*空树是二叉排序树*/ else if (T->lchild ==NUUL&T -> rchild==NULL) return 1; /*只有一个根结点是二叉排序树*/ else{l=BinSortTree(T->lchild)； r=BinSortTree(T->rchild)； if(T->lchild&&T->rchild） if(T->key＞T->lchild->key&&T->key if(T->lchild ==NUUL) /*只有一个根结点是二叉排序树，／ return(T->key＜T->rchild->key && r) else return(T->key＞T->lchild->key&&l)／*只有一个根结点是二叉排序树*／ } } 10:假设散列表表长为m，散列函数为H(key)，用链地址法处理冲突。试编写输入一组关键字并建立散列表的算法。 【提示】输入关键字后，应先确定其散列地址，再将其插人到相应的单链表中去。 typedef struct HNode {datatype data; struct HNode *next; }HNode,*Hlistt; /*链地址法处理冲突的散列表类型定义。／ void CreateHlist(Hlist L[ ],int m) {int i; HNode *s; for(i=0;i L[i]=NULL; /*表头指针初始化*/ scanf( x)； while(x!=’＃’） {h=Hash(x); /*计算x的散列地址。*/ s=(HNode *)malloc(sizeof(HNode)); s->data. key=x;／*申请、填装结点。／ s->next=L[h]； L[h]=s; ／*插人到散列表中去*／ scanf(x)； } }