第9章查找(二)习题练习答案

第9章查找(二)习题练习答案  

设散列表长度为 散列函数h(x)=x% 给定的关键字序列为 试画出分别用拉链法和线性探查法解决冲突时所构造的散列表 并求出在等概率情况下 这两种方法查找成功和失败时的平均查找长度 请问装填因子的值是什么? 答 　( )拉链法如下图   T[ ]    ┌──┐   │    │→ → →∧    ├──┤   │    │→ → → → ∧    ├──┤   │    │→ →∧    ├──┤   │ ∧ │    ├──┤   │ ∧ │    ├──┤   │    │→ → →∧　　├──┤　 │ ∧ │    ├──┤   │ ∧ │    ├──┤   │ ∧ │    ├──┤   │ ∧ │     ├──┤  │ ∧ │    └──┘  ( )线性探查法如下图       下标                                           ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐  T[ ]│ │ │ │ │ │ │ │ │  │  │  │          └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘  探查次数                          用拉链法的查找成功平均查找长度为     ASLsucc=( * + * + * )/ =   查找失败时平均查找长度为     ASLunsucc=( + + + + + + + + + + )/ =   用线性探查法查找成功时平均查找长度为     ASLsucc=( + + + + + + + )/ =   查找失败时平均查找长度为     ASLunsucc=( + + + + + + + + + + )/ =   装填因子α拉链= / = α线性探查= / =

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

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

设顺序表中关键字是递增有序的 试写一顺序查找算法 将哨兵设在表的高下标端 然后求出等概率情况下查找成功与失败时的ASL 答:  typedef struct{　　　KeyType key 　　　InfoType otherinfo //此类型依赖于应用　　}NodeType 　typedef NodeType SeqList[n+ ] //n号单元用作哨兵　int SeqSearch(Seqlist R KeyType K)　　　{ //在关键字递增有序的顺序表R[ n ]中顺序查找关键字为K的结点 　　　　//成功时返回找到的结点位置 失败时返回 　　　　int i 　　　　R[n] key=K //设置哨兵　　　　for(i= R[i] key<=K;i ) //从表前往后找　　　　if (i<n&&R[i] key==K) return i; //R[i]是要找的结点　　　　else return  　　　} //SeqSearch　　等概率情况下查找成功ASL=( + + +…+n)/n　　等概率情况下查找失败时的ASL=( + + +…+n+n+ )/(n+ )

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

试写一算法判别给定的二叉树是否为二叉排序树 设此二叉树以二叉链表为存储结构 且树中结点的关键字均不相同 解 　　由二叉排序树的定义可得 二叉排序树中左子树的所有结点的值都小于根结点的值 所有右子树中结点的值都大于根结点的值 那么只要对待判定的二叉树中的结点按层遍历并判断即可 在该算法中要用到队列保存已遍历的结点指针 　typedef BinTNode *DataType;//循环队列中元素为二叉树结点指针 　int BinSortStree(BinTree T)　　{ 　　　CirQueue Q;　　　BinTNode *p;　　　if (!T) return ;//空树为二叉排序树　　　InitQueue(&Q);　　　EnQueue(&Q T);　　　while(!QueueEmpty(&Q))　　　　{　　　　　p=DeQueue(&Q);　　　　　if (p >lchild)　　　　　　if (p >data<p >lchild >data) return ;//不是二叉排序树　　　　　　else EnQueue(&Q p >lchild);　　　　　if (p >rchild)　　　　　　if (p >data>p >rchild >data) return ;//不是二叉排序树　　　　　　else EnQueue(&Q p >rchild);　　　　}　　　return ;//是二叉排序树　　　}

试写一递归算法 从大到小输出二叉排序树中所有其值不小于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);　　　　}　　}

写一个遍历B 树的算法 使输出的关键字序列递增有序 算法中的读盘操作可假定为DiskRead 答 　#define Max l //结点中关键字的最大数目 Max=m m是B 树的阶　#define Min //非根结点中关键字的最小数目 Min=「m/ ( 　typedef int KeyType //KeyType应由用户定义　typedef struct node{ //结点定义中省略了指向关键字代表的记录的指针　　　int keynum //结点中当前拥有的关键字的个数 keynum<=Max　　　KeyType key[Max+ ] //关键字向量为key[ keynum] key[ ]不用 　　　struct node *parent //指向双亲结点　　　struct node *son[Max+ ] //孩子指针向量为son[ keynum]　　}BTreeNode 　typedef BTreeNode *BTree 　void travelBtree(BTree T){　　//按关键字递增序输出B 树序列　　int i;　　if (T){　　　　for(i= ;i<=T >keynum;i++)//T >keynum个关键字的结点有T >keynum+ 棵子树　　　　　{　　　　　　　if (T >son[i]){　　　　　　　　　DiskRead(T >son[i]);//读入根结点的第i棵子树　　　　　　　　　travelBtree(T >son[i]);//遍历第i棵子树　　　　　　　　}　　　　　　　if (i<T >keynmu)//若刚遍历的子树不是最后一棵子树　　　　　　　　　printf( %d T >key[i+ ];　　　　　　} 　　}