-
本章习题解答只给出算法描述，
1~8
题略。<
/p>
⒈画出对长度为
18
< br>的有序的顺序表进行折半查找时的判定树，并指出在等概率时查找成功的平均查
找
长度，以及查找失败时所需的最多的关键字比较次数。
⒉已知
如下所示长度为
12
的关键字有序的表：
{Jan, Feb, Mar, Apr, May, June, July,
Aug, Sep, Oct, Nov, Dec}
⑴试按表中元素的顺序依次插入
到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求
其在等概率的情况下
查找成功的平均查找长度。
⑵若对表中元素先进行排序构成有
序表，求在等概率的情况下查找成功的平均查找长度。
⑶按表
中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
⒊试推导含有
12
个结点的平衡
二叉树的最大深度，并画出一棵这样的树。
⒋含有
9
个叶子结点的
3
阶
B
–树中至少有多少个非叶子结点？含有
1
0
个叶子结点的
3
阶
< br>B
–树中
至少有多少个非叶子结点？
⒌试从空树开始，画出按以下次序向
3
< br>阶
B
–树中插入关键码的建树过程：
20
，
30
，
50
，
52
，
60
，
68
，
70
。如果此后删除
50
和
68
，画出每一步执行后
3
< br>阶
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
。用开放定址法处理冲突，
d
i
=i ((7*key) % 10+1)
，
i=1,2,3
,…
。试在
< br>0
～
10
的散列地址空间中对关
键字序列（
22
，
41
，
53
，
46
，
30
，
13
，
01
，
67
）构
造哈希表，并求等概率情况下查找成功时的平均查找长度。
⒏画出依次插入
z
，
v
，
o
，
q
，
w
，
y
到下图所示的
5
阶
B
–树的过程。
j
c
f
a
b
g
h
i
k
l
m
r
n
p
s
t
u
x
⒐将监测哨设在高下标端，改写教科书上给出的顺序查找算
法。并分别求出等概率情况下查找成功和
查找失败的平均查找长度。
typedef
struct{
KeyType
key
…
}ElemType;
typedef
struct{
ElemType
*elem
；
/
/
elem[1]
中存储第一个元素
int
length;
}S_table
int
search(S_table
L , KeyType
K)
{
[+1] = K
i=1;
while (K! =[i])
i++
return ( i%(+1))
}
⒑将折半查找的算法改写为递归算法。
int BiSearch(S_table L, int low, int
high,KeyType x)
{
if (low>high)
return(0);
mid=(low+high)/2;
if (x=
=[mid].key)
return(mid);
else
if
(x<[mid].key)
BiSearch(L,low,mid-1,x);
Else
BiSearch(L,mid+1,high,x);
}
⒒在平衡二叉排序树的每个结点中
增设一个
lsize
域，
其值为它的左
子树中的结点数加
1
。
试写以时
间复杂度为
O(log
2
n)
的算法，确定树中第
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
L[i]=NULL;
cin>>x;
while (x!=’#’)
{
h=H(x);
s=new Hnode;
s->=x;
s->next=L[h];
L[h] = s;
cin>>x;
}
return;
}
⒔已知一棵二叉排序树上所有关键字中的最小值为－
max
，最大值为
max
，又知
。
-m
ax
。编写
递归算法，求该二叉排序树上的小于<
/p>
x
且最靠近
x
的
值
a
和大于
x
且最靠近
x
的值
b
typedef
struct
BTNode{
struct{
int
key;
…
}data;
-
-
-
-
-
-
-
-
-
上一篇：通知老外春节放假事宜(英文)
下一篇：对比语言学的定义-起源和发展(精)