21.设散列表长度为11，散列函数h(x)=x%11,给定的关键字序列为：1，13，13，34，38，33，27，试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么? 

22.假定有k个关键字互为同义词，若用线性探查法把这些同义词存入散列表中，至少要进行多少次探查?

23.为什么说当装填因子非常接近1时，线性探查类似于顺序查找?为什么说当装填因子比较小(比如α=0.7左右)时，散列查找的平均查找时间为O(1)?

24.设顺序表中关键字是递增有序的，试写一顺序查找算法，将哨兵设在表的高下标端。然后求出等概率情况下查找成功与失败时的ASL.

25.试写出二分查找的递归算法。

26.试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同。

27.试写一递归算法，从大到小输出二叉排序树中所有其值不小于x的关键字。要求算法的时间为O(lgn+m)，n为树中结点数，m为输出关键字个数(提示：先遍历右子树，后遍历左子树)。

28.写一个遍历B-树的算法，使输出的关键字序列递增有序。算法中的读盘操作可假定为DiskRead。

29.若采用除余法作为散列函数，线性探查解决冲突，则9.4.4节中通用的散列表查找算法可改写为对线性探查专用的查找算法：
  int HashSearch(HashTable T,KeyType K,int *pos){
  　　　int i=0;//记录探查次数
  　　　*pos=K%m; //散列函数值作为第一个散列地址
 　　　 while(i++<m) //最多探查m次
    　　　　{
      　　　　　if(T[*pos].key==K) return 1;//查找成功返回
      　　　　　if(T[*pos].key==NIL) return 0;//查找失败返回
      　　　　　*pos=(*pos+1)%m;//用线性探查法求下一个探查地址
    　　　　}
  　　　return -1;//查找失败，且表满
　　}//HashSearch
　　假设散列表上的删除操作已将结点的关键字标记为DELETED(例如，不妨设DELETED为-2)。请修改上述散列表上的查找算法及插入算法HashInsert，使之能正确地查找和插入。

30.用拉链法解决冲突，有关的类型说明和插入算法如下，请据此写出散列表的建表、查找及删除算法。
　typedef struct node{
　　　KeyType key;//关键字
　　　InfoType Otherinfo;//以下不处理此域
　　　struct node *next;//链域
　　}CNodeType;
　typedef CNodeType *CHashTable[m];//散列表类型是一个指针数组
　void ChainHashInsert(CHashTable T,KeyType K){
　　　//将关键字K插入表T中，设散列函数为h(K)=K%m
　　　CNodeType *p;
　　　int addr;
　　　p=ChainHashSearch(T,K);//在T中查找有无关键字为K的结点
　　　if (p) printf("duplicate key!");//关键字已存在
　　　else {//申请一个新结点，将其关键字置为K，并插入相应链表的头上
　　　　　　　addr=K%m;//求散列函数值作为散列地址
　　　　　　　p=(CNodeType *)malloc(sizeof(CNodeType));
　　　　　　　p->key=K;p->next=T[addr];T[addr]=p;//将*p插入链表T[addr]的头部 
　　　　　　}//endif
　　}//ChainHashInsert