|
设散列表长度为散列函数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 RKeyType 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 RKeyType Kint lowint high) { //在有序表R[lowhigh]中进行二分查找成功时返回结点的位置失败时返回零 int mid //置当前查找区间上下界的初值 if (low<=high){ //当前查找区间R[lowhigh]非空 mid=(low+high)/ if(R[mid]key==K) return mid //查找成功返回 if(R[mid]kdy>K) return BinSearch( RKlowmid)//在R[lowmid]中查找 else return BinSearch( RKmid+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(&QT); while(!QueueEmpty(&Q)) { p=DeQueue(&Q); if (p>lchild) if (p>data<p>lchild>data) return ;//不是二叉排序树 else EnQueue(&Qp>lchild); if (p>rchild) if (p>data>p>rchild>data) return ;//不是二叉排序树 else EnQueue(&Qp>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 TKeyType x) {//从大到小输出二叉排序树中所有其值不小于x的关键字 if (T) { OUTPUTNODE( T>rchildx); if (T>key>=x) printf(%dT>key); OUTPUTNODE( T>Lchildx); } } 写一个遍历B树的算法使输出的关键字序列递增有序算法中的读盘操作可假定为DiskRead 答 #define Max l //结点中关键字的最大数目Max=mm是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(%dT>key[i+]; } } 上一篇：二叉树的操作
下一篇：第10章文件习题练习
|
