├──┤ 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 等概率情况下查找成功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 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(\ 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棵子树