第9章习题及解答.doc

本章习题解答只给出算法描述，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–树的过程。
j

m r
c f

s t u x

n p
k l
a b
g h i

⒐将监测哨设在高下标端，改写教科书上给出的顺序查找算法。并分别求出等概率情况下查找成功和查找失败的平均查找长度。
typedef struct{
KeyType key ;
…
}ElemType;
typedef struct{
ElemType *elem； // elem[1]中存储第一个元素
int length;
}S_table ;
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);
}
⒓假设哈希表长为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;
}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;
}
⒕编写一个算法，利用折半查找算法在一个有序表中插入一个元素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)
{
low = 1;
high = L.length ; //设L.length=fibo[K]-1
while (low<=high)
{
mid =low +fibo[K-1] ;
if ( x<L.elem[mid] )
high=mid-1;
else
if (x>L.elem[mid])
low=mid+1;
else
return(mid) ;
}
return(0);
}
⒘试编写一个判定二叉树是否二叉排序树的算法，设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。
typedef struct{
KeyType key;
…
}ElemType;
typedef struct BTNode{
ElemType 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);
else
pre=t;
flagR=process(T->rchild,pre)
if ( flagL && flagR)
return(1) ;
else
return(0);
}
}