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

  T[0..10]
    ┌──┐
   0│    │→ 33 → 22 →∧
    ├──┤
   1│    │→ 1 → 12 →34→ ∧
    ├──┤
   2│    │→ 13 →∧
    ├──┤
   3│ ∧ │
    ├──┤
   4│ ∧ │
    ├──┤
   5│    │→ 38 → 27 →∧
　　├──┤
　 6│ ∧ │
    ├──┤
   7│ ∧ │
    ├──┤
   8│ ∧ │
    ├──┤
   9│ ∧ │ 
    ├──┤
  10│ ∧ │
    └──┘

  (2)线性探查法如下图：

      下标   0   1   2   3   4   5   6   7   8   9  10 
          ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
  T[0..10]│33│1 │13│12│34│38│27│22│  │  │  │
          └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
  探查次数   1   1   1   3   4   1   7   8


  用拉链法的查找成功平均查找长度为：
    ASLsucc=(1*4+2*3+3*1)/8=1.625

  查找失败时平均查找长度为：
    ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.73

  用线性探查法查找成功时平均查找长度为：
    ASLsucc=(1+1+1+3+4+1+7+8)/8=3.25

  查找失败时平均查找长度为：
    ASLunsucc=(9+8+7+6+5+4+3+2+1+1+1)/11=4.3

  装填因子α拉链=4/11=0.36 α线性探查=8/11=0.73

22.假定有k个关键字互为同义词，若用线性探查法把这些同义词存入散列表中，至少要进行多少次探查?
答：
    至少要进行1+2+3...+k-1+k次探查。
    也就是说，在散列表的一连串连续空间内，第一个关键字只需探查一次，第二个就要探查2次，如此这般，第k个关键字就要探查k次才能找到位置存放。所以至少要把它们全加起来才够。

23.为什么说当装填因子非常接近1时，线性探查类似于顺序查找?为什么说当装填因子比较小(比如α=0.7左右)时，散列查找的平均查找时间为O(1)?
答：
    当α非常接近1时，整个散列表几乎被装满。由于线性探查法在关键字同义时解决冲突的办法是线性地向后查找，当整个表几乎装满时，它就很类似于顺序查找了。
    当α比较小时，关键字碰撞的几率比较小，一般情况下只要按照散列函数计算出的结果能够1次性就找到相应结点，因此它的平均查找时间接近于1.

24.设顺序表中关键字是递增有序的，试写一顺序查找算法，将哨兵设在表的高下标端。然后求出等概率情况下查找成功与失败时的ASL.
答:
  typedef struct{
　　　KeyType key；
　　　InfoType otherinfo； //此类型依赖于应用
　　}NodeType；
　typedef NodeType SeqList[n+1]； //n号单元用作哨兵

　int SeqSearch(Seqlist R，KeyType K)
　　　{ //在关键字递增有序的顺序表R[0..n-1]中顺序查找关键字为K的结点，
　　　　//成功时返回找到的结点位置，失败时返回-1
　　　　int i；
　　　　R[n].key=K； //设置哨兵
　　　　for(i=0；R[i].key<=K;i--)； //从表前往后找
　　　　if (i<n&&R[i].key==K) return i; //R[i]是要找的结点
　　　　else return -1 
　　　} //SeqSearch

　　等概率情况下查找成功ASL=(1+2+3+…+n)/n
　　等概率情况下查找失败时的ASL=(1+2+3+…+n+n+1)/(n+1)

25试写出二分查找的递归算法。
解：
  int BinSearch(SeqList R，KeyType K，int low，int high)
　　{ //在有序表R[low..high]中进行二分查找，成功时返回结点的位置，失败时返回零
　　　int mid； //置当前查找区间上、下界的初值
　　　if (low<=high){ //当前查找区间R[low..high]非空
　　　　　mid=(low+high)/2；
　　　　　if(R[mid].key==K) return mid； //查找成功返回
　　　　　if(R[mid].kdy>K)
　　　　　　　return BinSearch( R，K,low，mid-1)//在R[low..mid-1]中查找
　　　　　else
　　　　　　　return BinSearch( R，K,mid+1，high)； //在R[mid+1..high]中查找
　　　　}
　　　return 0； //当low>high时表示查找区间为空，查找失败
　　} //BinSeareh

26试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同。
解：
　　由二叉排序树的定义可得：二叉排序树中左子树的所有结点的值都小于根结点的值，所有右子树中结点的值都大于根结点的值。那么只要对待判定的二叉树中的结点按层遍历并判断即可。在该算法中要用到队列保存已遍历的结点指针。

　typedef BinTNode *DataType;//循环队列中元素为二叉树结点指针 
　int BinSortStree(BinTree T)
　　{ 
　　　CirQueue Q;
　　　BinTNode *p;
　　　if (!T) return 1;//空树为二叉排序树
　　　InitQueue(&Q);
　　　EnQueue(&Q,T);
　　　while(!QueueEmpty(&Q))
　　　　{
　　　　　p=DeQueue(&Q);
　　　　　if (p->lchild)
　　　　　　if (p->data<p->lchild->data) return -1;//不是二叉排序树
　　　　　　else EnQueue(&Q,p->lchild);
　　　　　if (p->rchild)
　　　　　　if (p->data>p->rchild->data) return -1;//不是二叉排序树
　　　　　　else EnQueue(&Q,p->rchild);
　　　　}
　　　return 1;//是二叉排序树　
　　}

27.试写一递归算法，从大到小输出二叉排序树中所有其值不小于x的关键字。要求算法的时间为O(lgn+m)，n为树中结点数，m为输出关键字个数(提示：先遍历右子树，后遍历左子树)。
答：
　typedef int KeyType； //假定关键字类型为整数
　typedef struct node { //结点类型
　　　KeyType key； //关键字项
　　　InfoType otherinfo； //其它数据域，InfoType视应用情况而定，下面不处理它
　　　struct node *lchild，*rchild； //左右孩子指针
　　} BSTNode；
　typedef BSTNode *BSTree；

　void OUTPUTNODE(BSTree T,KeyType x)
　　{//从大到小输出二叉排序树中所有其值不小于x的关键字
　　　if (T)
　　　　{
　　　　　OUTPUTNODE( T->rchild,x);
　　　　　if (T->key>=x) printf("%d",T->key);
　　　　　OUTPUTNODE( T->Lchild,x);
　　　　}
　　}

28.写一个遍历B-树的算法，使输出的关键字序列递增有序。算法中的读盘操作可假定为DiskRead。
答：
　#define Max l000 //结点中关键字的最大数目：Max=m-1，m是B-树的阶
　#define Min 500 //非根结点中关键字的最小数目：Min=「m/2(-1
　typedef int KeyType； //KeyType应由用户定义
　typedef struct node{ //结点定义中省略了指向关键字代表的记录的指针
　　　int keynum； //结点中当前拥有的关键字的个数，keynum<=Max
　　　KeyType key[Max+1]； //关键字向量为key[1..keynum]，key[0]不用。
　　　struct node *parent； //指向双亲结点
　　　struct node *son[Max+1]；//孩子指针向量为son[0..keynum]
　　}BTreeNode；
　typedef BTreeNode *BTree；

　void travelBtree(BTree T){
　　//按关键字递增序输出B-树序列
　　int i;
　　if (T){
　　　　for(i=0;i<=T->keynum;i++)//T->keynum个关键字的结点有T->keynum+1棵子树
　　　　　{
　　　　　　　if (T->son[i]){
　　　　　　　　　DiskRead(T->son[i]);//读入根结点的第i棵子树
　　　　　　　　　travelBtree(T->son[i]);//遍历第i棵子树
　　　　　　　　}
　　　　　　　if (i<T->keynmu)//若刚遍历的子树不是最后一棵子树
　　　　　　　　　printf("%d",T->key[i+1];　
　　　　　}
　　}

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，使之能正确地查找和插入。

解：
　(1)查找算法
　　#define DELETED -2
　　#define NIL -1 //空结点标记依赖于关键字类型，本节假定关键字均为非负整数
　　#define M 997 //表长度依赖于应用，但一般应根据。确定m为一素数
　　typedef struct{ //散列表结点类型
　　　　KeyType key；
　　　　InfoType otherinfo； //此类依赖于应用
　　　}NodeType；
　　typedef NodeType HashTable[m]； //散列表类型

　　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

　(2)插入算法HashInsert
　　　int HashInsert(HashTable T,KeyType K){
　　　　//返回1，表示表中已有k，返回0表示正常插入，返回-1表示插入失败
　　　　int i=0;//记录探查次数
　　　　int j=-1;//记录DELETED的位置
　　　　int pos=K%m; //散列函数值作为第一个散列地址
　　　　while(i++<m) //最多探查m次
　　　　　{
　　　　　　if(T[pos].key==K) return 1;//查找成功返回
　　　　　　if(T[pos].key==NIL)
　　　　　　　{if (j==-1) T[pos].key=K;//查找失败,插入
　　　　　　　　else T[j].key=K;//插入到被删除元素留出的位置
　　　　　　　　return 0;
　　　　　　　}//正常插入
　　　　　　if(T[pos].key==DELETED)
　　　　　　　　if (j==-1) j=pos; 
　　　　　　pos=(pos+1)%m;//用线性探查法求下一个探查地址
　　　　　}
　　　　return -1;//查找失败，且表满
　　　}

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

解：
　(1)建表
　　void ChainHashCreat(CHashTable T){
　　　//设散列函数为h(K)=K%m,建立以拉链法为解决冲突方法的散列表
　　　CNodeType *p;
　　　int addr;
　　　int i;
　　　KeyType K;
　　　for(i=0;i<m;i++)//置空的散列表
　　　　T[i]=NULL;
　　　scanf("%d",&K);
　　　while (K)//设输入的数据以0结束
　　　　{
　　　　　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
　　　　　scanf("%d",&K);
　　　　}//endwhile
　　}//ChainHashCreat

　(2)查找
　　CNodeType ChainHashSearch(CHashTable T,KeyType K)
　　　{//查找关键字值为K的结点，若有返回该结点指针，否则返回NULL
　　　　　CNodeType *p;
　　　　　int addr;
　　　　　addr=K%m;//求散列函数值
　　　　　p=T[addr];
　　　　　while (p)&&(p->key!=K)
　　　　　　p=p->next;
　　　　　return p;
　　　}

　(3)删除
　　　CNodeType ChainHashDelete(CHashTable T,KeyType K)
　　　　{//删除关键字值为K的结点，若有返回该结点指针，否则返回NULL
          　CNodeType *p,*q;
　　　　　　int addr;
　　　　　　addr=K%m;//求散列函数值
　　　　　　p=T[addr];
　　　　　　if (p)&&(p->key==K) T[addr]=p->next;//要删的是 T[addr]表的第一个结点
　　　　　　while (p->next)&&(p->next->key!=K)
　　　　　　　　p=p->next;
　　　　　　if (p->next)
　　　　　　　{q=p;p=p->next;q->next=p->next;//删除p}
　　　　　　return p;
　　　　　}