本章习题解答只给出算法描述,1~8题略。 1画出对长度为18的有序的顺序表进行折半查找时的判定树,并指出在等概率时查找成功的平均查 找长度,以及查找失败时所需的最多的关键字比较次数。 2已知如下所示长度为12的关键字有序的表 0)试表中元的次到一棵切始为空的2支排+,由5完成后的三排树,并求 其在等概率的情况下查找成功的平均查找长度 (2)若对表中元素先进行排序构成有序表,求在等概率的情况下查找成功的平均查找长度 (3)按表中元素的顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。 3.试推导含有12个结点的平衡二叉树的最大深度,并画出一棵这样的树。 4含有9个叶子结点的3阶B-树中至少有多少个非叶子结点?含有10个叶子结点的3阶B-树中 至少有多少个非叶子结点? 5试从空树开始,画出按以下次序向3阶B-树中插入关键码的建树过程:20,30,50,52,60, 68,70。如果此后删除50和68,画出每一步执行后3阶B-树的状态 6在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表 [Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec] (1)用线性探测开放地址法处理冲突 (2)用链地址法处理冲突。 并分别求这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。设哈希函数为H(key i/2,其中i为关键字中第一个字母在字母表中的序号。 7哈希函数H(key)=(3*key)号11。用开放定址法处理冲突,d=i((7*key)号10+1) i=1,2,3,.试在0~10的散列地址空间中对关键字序列(22,41,53,46,30,13,01,67)构 造哈希表,并求等概率情况下查找成功时的平均查找长度 8画出依次插入z,v,o,q,w,y到下图所示的5阶B-树的过程 g h k I s t u x 9将监测哨设在高下标端,改写教科书上给出的顺序查找算法。并分别求出等概率情况下查找成功和 查找失败的平均查找长度 typedef struct( KelTy yElemType typedef struct( Elem Type*elem;∥elem[中存储第一个元素 nt length s table
本章习题解答只给出算法描述，1~8 题略。 ⒈画出对长度为 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–树的状态。 ⒍在地址空间为 0～16 的散列区中，对以下关键字序列构造两个哈希表： {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,…。试在 0～10 的散列地址空间中对关键字序列（22，41，53，46，30， 13，01，67）构 造哈希表，并求等概率情况下查找成功时的平均查找长度。 ⒏画出依次插入 z，v，o，q，w，y 到下图所示的 5 阶 B–树的过程。 ⒐将监测哨设在高下标端，改写教科书上给出的顺序查找算法。并分别求出等概率情况下查找成功和 查找失败的平均查找长度。 typedef struct{ KeyType key ; … }ElemType; typedef struct{ ElemType *elem； // elem[1]中存储第一个元素 int length; }S_table ; j c f m r a b g h i k l n p s t u x
int search(s table L, Key Type K) Lelem[L length+]=K while(K! elem 1+ return( 1%(L length+1)) 0.将折半查找的算法改写为递归算法 int BiSearch(s table L, int low, int high, Key Type x) if (low>high) return(o) mid=(low+high )/2 if(X==Lelem(mid. key) return(mid) else if(X<L elem[mid]. key) BiSearch(L,low, mid-1, x) Else BiSearch(L, mid+l, high, x) I在平衡二叉排序树的每个结点中增设一个1size域,其值为它的左子树中的结点数加1。试写以时 间复杂度为o(1og2n)的算法,确定树中第k小的结点的位置。 typedef struct BTNode Elemtype data int lsize struct BTNode *lchild *rchild BTNode *BiTree BiTree index(bitree t, int k) if(t-NULL return ( NULL) if(t->lsize==K) return(t else if(t->lsize>k)
int search(S_table L , KeyType K) { L.elem[L.length+1] = K ; i=1; while (K! =L.elem[i]) i++ ; return ( i%(L.length+1)) ; } ⒑将折半查找的算法改写为递归算法。 int BiSearch(S_table L, int low, int high,KeyType x) { if (low>high) return(0); mid=(low+high)/2; if (x= =L.elem[mid].key) return(mid); else if (x<L.elem[mid].key) BiSearch(L,low,mid-1,x); Else BiSearch(L,mid+1,high,x); } ⒒在平衡二叉排序树的每个结点中增设一个 lsize 域，其值为它的左子树中的结点数加 1。试写以时 间复杂度为 O(log2n)的算法，确定树中第 k 小的结点的位置。 typedef struct BTNode{ Elemtype data; int lsize; struct BTNode *lchild , *rchild; }BTNode ,*BiTree; BiTree index(BiTree t, int k) { if (t==NULL) return(NULL); if (t->lsize= =K) return(t); else if (t->lsize>K)
return(t->lchild, K); else return(t->rchild, K) 12假设哈希表长为皿,哈希函数为H(key),用链地址法处理冲突。试编写输入一组关键字并建立哈 希表的算法。 typedef struct( Key type ke JElemType typedef struct NOde ElemType data; struct NOde nex 3 Anode, List; void CreateHList(List LmD for(1=0; 1<m; 1++) LI-NULL cin>>X while(x!=#) snew node S->data key=x s->next=LIh cin>>X return: 13已知一棵二叉排序树上所有关键字中的最小值为一max,最大值为max,又知-max<x<max。编写 递归算法,求该二叉排序树上的小于x且最靠近x的值a和大于x且最靠近x的值b。 typedef struct BTNode struct int key data
return(t->lchild,K); else return(t->rchild,K); } ⒓假设哈希表长为 m，哈希函数为 H(key)，用链地址法处理冲突。试编写输入一组关键字并建立哈 希表的算法。 typedef struct{ KeyType key; … }ElemType; typedef struct HNode{ ElemType data; struct HNode *next; }Hnode ,*Hlist; void CreateHList (Hlist L[m]) { for ( i=0; i<m; i++ ) L[i]=NULL; cin>>x; while (x!=’#’) { h=H(x); s=new Hnode; s->data.key=x; s->next=L[h]; L[h] = s; cin>>x; } return; } ⒔已知一棵二叉排序树上所有关键字中的最小值为－max，最大值为 max，又知-max<x<max。编写 递归算法，求该二叉排序树上的小于 x 且最靠近 x 的值 a 和大于 x 且最靠近 x 的值 b。 typedef struct BTNode{ struct{ int key; … }data;
struct BTNode *lchild *rchild 3 BTNode Bitree void fun (BiTree t, int x, int *a, int *b) if (T) if(x<t->data. key) bb=t->data. key fun (t->lchild, x, a, b); eIse if(x>t->data. key fun(t->rchild, x, a, b); p=t->lchild while(p->rchild) data. ke p=t->rchild while(p->lchild p=p->lchild p-data. key return:
struct BTNode *lchild , *rchild; }BTNode ,*BiTree ; void fun(BiTree t, int x, int *a, int *b) { if (T) { if (x<t->data.key) { *b = t->data.key; fun(t->lchild, x,a,b); } else if (x>t->data.key) { *a = t->data.key ; fun(t->rchild,x,a,b); } else { if (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;
14编写一个算法,利用折半查找算法在一个有序表中插入一个元素x,并保持表的有序性 void Insert(s table L, ElemType x) low=1 high=. length while (low<=high mI if(X<L elem midD) high=mid-1 else if(x>L elem midD low-mid+1 return for(i=Llength; i>=low; i L elem[i+1]=Lelem[] Lelem low=X return: 15假设二叉排序树t的各个元素值均不相同,设计一个算法按递减次序打印各元素的值。 void printnode bitree t) if(t) printnode(t->rchild) cout<<t->data<<endl printnode(t->le return: 16设计在有序顺序表上进行斐波那契查找的算法,并画出长度为20的有序表进行斐波那契查找的判 定树,求出在等概率下查找成功的平均查找长度。 int fibo search(s table L, Key Type x, int*fibo)
} ⒕编写一个算法，利用折半查找算法在一个有序表中插入一个元素 x，并保持表的有序性。 void Insert(S_table L, ElemType x) { low=1; high=L.length; while (low<=high; { mid = (low+high)/2; if (x<L.elem[mid]) high=mid-1; else if (x>L.elem[mid]) low=mid+1; else return; } for (i=L.length ; i>=low ;i--) L.elem[i+1] = L.elem[i] ; L.elem[low] =x; return; } ⒖假设二叉排序树 t 的各个元素值均不相同，设计一个算法按递减次序打印各元素的值。 void printnode(BiTree t) { if (t) { printnode(t->rchild); cout<<t->data<<endl; printnode(t->lchild); } return; } ⒗设计在有序顺序表上进行斐波那契查找的算法，并画出长度为 20 的有序表进行斐波那契查找的判 定树，求出在等概率下查找成功的平均查找长度。 int fibo_search(S_table L, KeyType x, int *fibo) {