第9章习题及解答.doc

本章习题解答只给出算法描述，18题略。画出对长度为18的有序的顺序表进行折半查找时的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。已知如下所示长度为12的关键字有序的表：Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec试按表中元素的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。若对表中元素先进行排序构成有序表，求在等概率的情况下查找成功的平均查找长度。按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。含有9个叶子结点的3阶B树中至少有多少个非叶子结点？含有10个叶子结点的3阶B树中至少有多少个非叶子结点？试从空树开始，画出按以下次序向3阶B树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后3阶B树的状态。在地址空间为016的散列区中，对以下关键字序列构造两个哈希表：Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec用线性探测开放地址法处理冲突；用链地址法处理冲突。并分别求这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。设哈希函数为H(key) =i/2,其中i为关键字中第一个字母在字母表中的序号。哈希函数H(key)=(3*key) % 11。用开放定址法处理冲突，di=i (7*key) % 10+1)， i=1,2,3,。试在010的散列地址空间中对关键字序列（22，41，53，46，30， 13，01，67）构造哈希表，并求等概率情况下查找成功时的平均查找长度。画出依次插入z，v，o，q，w，y到下图所示的5阶B树的过程。j m rc f s t u xn pk la bg h i 将监测哨设在高下标端，改写教科书上给出的顺序查找算法。并分别求出等概率情况下查找成功和查找失败的平均查找长度。typedef structKeyType key ;ElemType;typedef structElemType *elem； / elem1中存储第一个元素 int length;S_table ;int search(S_table L , KeyType K)L.elemL.length+1 = K ;i=1;while (K! =L.elemi)i+ ;return ( i%(L.length+1) ;将折半查找的算法改写为递归算法。int BiSearch(S_table L, int low, int high,KeyType x) if (lowhigh)return(0);mid=(low+high)/2;if (x= =L.elemmid.key)return(mid); elseif (xlsize= =K)return(t);elseif (t-lsizeK)return(t-lchild,K);elsereturn(t-rchild,K);假设哈希表长为m，哈希函数为H(key)，用链地址法处理冲突。试编写输入一组关键字并建立哈希表的算法。typedef structKeyType key;ElemType;typedef struct HNodeElemType data;struct HNode *next;Hnode ,*Hlist;void CreateHList (Hlist Lm)for ( i=0; ix; while (x!=#)h=H(x);s=new Hnode;s-data.key=x;s-next=Lh;Lh = s;cinx;return;已知一棵二叉排序树上所有关键字中的最小值为max，最大值为max，又知-maxxmax。编写递归算法，求该二叉排序树上的小于x且最靠近x的值a和大于x且最靠近x的值b。typedef struct BTNodestructint key;data;struct BTNode *lchild , *rchild;BTNode ,*BiTree ;void fun(BiTree t, int x, int *a, int *b)if (T)if (xdata.key)*b = t-data.key;fun(t-lchild, x,a,b);elseif (xt-data.key)*a = t-data.key ;fun(t-rchild,x,a,b);elseif (t-lchild)p=t-lchild;while (p-rchild)p=p-rchild;*a=p-data.key;if (t-rchild)p=t-rchild;while (p-lchild )p=p-lchild;*b=p-data.key; return;编写一个算法，利用折半查找算法在一个有序表中插入一个元素x，并保持表的有序性。void Insert(S_table L, ElemType x)low=1; high=L.length;while (low=high;mid = (low+high)/2;if (xL.elemmid)low=mid+1;elsereturn;for (i=L.length ; i=low ;i-)L.elemi+1 = L.elemi ;L.elemlow =x;return;假设二叉排序树t的各个元素值均不相同，设计一个算法按递减次序打印各元素的值。void printnode(BiTree t)if (t)printnode(t-rchild); coutdatalchild);return;设计在有序顺序表上进行斐波那契查找的算法，并画出长度为20的有序表进行斐波那契查找的判定树，求出在等概率下查找成功的平均查找长度。int fibo_search(S_table L, KeyType x, int *fibo)low = 1; high = L.length ; /设L.length=fiboK-1while (low=high)mid =low +fiboK-1 ;if ( xL.elemmid)low=mid+1;elsereturn(mid) ;return(0);试编写一个判定二叉树是否二叉排序树的算法，设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。typedef structKeyType key;ElemType;typedef struct BTNodeElemType data ;struct BTNode *lchild, *rchild ;BTNode ,*BiTree;int process(BiTree T ,BTNode *pre)if (T)flagL=process(T-lchild,pre)if ( pre & (pre-data.key=t-data.key)return (0);elsepre=t;flagR=process(T-rchild,pre)if ( flagL & flagR)return(1) ;elsereturn(0);