《第章习题及解答》由会员分享，可在线阅读，更多相关《第章习题及解答（7页珍藏版）》请在金锄头文库上搜索。
1、本章习题解答只给出算法描述，18题略。画出对长度为18的有序的顺序表进行折半查找时的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。已知如下所示长度为12的关键字有序的表：Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec试按表中元素的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。若对表中元素先进行排序构成有序表，求在等概率的情况下查找成功的平均查找长度。按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下
2、查找成功的平均查找长度。试推导含有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用线性探测开放地址法处理冲突；用链地址法处理冲突。并分别求这两个
3、哈希表在等概率情况下查找成功和不成功的平均查找长度。设哈希函数为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 将监测哨设在高下标端，改写教科书上给出的顺序查找算法。并分别求出等概
4、率情况下查找成功和查找失败的平均查找长度。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) i
5、f (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;
6、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
7、 ;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;
8、编写一个算法，利用折半查找算法在一个有序表中插入一个元素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 (
9、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);试编写一个判定二
10、叉树是否二叉排序树的算法，设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。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);
