1/3 ex5

Report
数据结构习题课
陈家伟
9.15 试证明:高度为h的2-3树中叶子结点数目在2^(h-1)与3^(h-1)
之间。
• 在2-3树中,每个内部结点(非叶子结点)有两个或三个孩子,而且
所有叶子都在同一层上;
• 一方面,若某棵2-3树只包含2-结点,则就是一颗满二叉树。高度为
h的满二叉树的叶子结点数是2^(h-1);
• 另一方面,若某棵2-3树只包含3-结点,那么第i层的结点数目是
3^(i-1)。高度为h的“3树”的叶子结点数是3^(h-1);
• 高度为h的2-3树中叶子结点数目在2^(h-1)与3^(h-1)之间。
9.16 在含有n个关键码的m阶B-树中进行查找时,最多访问多少
个结点?
• 定义:一棵m 阶的B-树,或者为空树,或为满足下列特性的m 叉树:
⑴ 树中每个结点至多有m 棵子树;
⑵ 若根结点不是叶子结点,则至少有两棵子树;
⑶ 除根结点之外的所有非终端结点至少有[m/2] 棵子树;(向上)
⑷ 所有的非终端结点中包含以下信息数据:
(n,A0,K1,A1,K2,…,Kn,An)
Ki(i=1,2,…,n)为关键码,且Ki<Ki+1;
Ai 为指向子树根结点的指针(i=0,1,…,n),且指针Ai-1 所指子树中
所有结点的关键码均小于Ki (i=1,2,…,n),An 所指子树中所有结点的
关键码均大于Kn;
n为关键码的个数;
⑸ 所有的叶子结点都出现在同一层次上,并且不带信息;
9.16 在含有n个关键码的m阶B-树中进行查找时,最多访问多少
个结点?
• 等价于“含有n 个关键码的m 阶B-树,最大高度是多少”
• 假设该B-树高为h+1,那么第h+1层有n+1个叶子结点
• (1) 第一层为根,至少一个结点,根至少有两个孩子,因此在第二
层至少有两个结点;
• (2) 除根和树叶外,其它结点至少有[m/2]个孩子,因此第三层至少有
2*[m/2]个结点,在第四层至少有2*[m/2]^2个结点;
• (3) 那么在第h+1层至少有2*[m/2]^(h-1)个结点,而h层的结点个数n+1,
有:
n+1 >= 2*[m/2]^(h-1)
h <= log[m/2]{(n+1)/2} + 1
9.39 试写一算法,将一棵二叉排序树分裂成两棵二叉排序树,
使得其中一棵树的所有结点的关键字都小于或等于x,另一棵树
的任一结点的关键字均大于x。
• 递归
• void BiTree_Split(BiTree &T, BiTree &A, BiTree &B, int x){
if(T->lchild) BiTree_Split(T->lchild, A, B, x);
if(T->rchild) BiTree_Split(T->rchild, A, B, x); //分裂左右子树
if(T->data<=x) Insert_Node(A, T);
else Insert_Node(B, T); //将元素结点插入合适的树中
}
9.39 试写一算法,将一棵二叉排序树分裂成两棵二叉排序树,
使得其中一棵树的所有结点的关键字都小于或等于x,另一棵树
的任一结点的关键字均大于x。
• void Insert_Node(Bitree &T, BTNode *S){
if(!T) T=S; //考虑到刚开始分裂时树A和树B为空的情况
else if(S->data > T->data){
if(!T->rchild) T->rchild=S;
else Insert_Node(T->rchild,S);
}
else if(S->data < T->data){
if(!T->lchild) T->lchild=S;
else Insert_Node(T->lchild,S);
}
S->lchild=NULL;
S->rchild=NULL;
}
9.40 在平衡二叉排序树的每个结点中增设一个lsize域,其值为
它的左子树中的结点树加1。试写一时间复杂度为O(logn)的算
法,确定树中第k小的结点的位置。
• lsize即是结点从小到大排列的序号
• 高度为logn,递归
• BiNode* Ranking(BiTree T, int k){
if(!T) return NULL;
if(T->lsize == k){
return T;
else{
if(T->lsize > k)
return Ranking(T->lchild, k);
else
return Ranking(T->rchild, k - T->lsize);
}
}
9.19 选取哈希函数H(k)=(3k) MOD 11。用开放定址法处理冲突,
di=i((7k)MOD10 + 1) (i = 1,2,3,…)。试在0~10的散列地址空间中对
关键字序列(22,41,53,46,30,13,01,67)构造哈希表,并求等概率下
查找成功时的平均查找长度。
• Hi=(H(key) + di) MOD m,i=1,2,…,k(k<=m-1)
• H(22) = 0
• H(41) = 2
• H(53) = 5
• H(46) = 6
• H(30) = 2 —— d1 = 1 ,3
• H(13) = 6 —— d1 = 2,8
• H(01) = 3 —— d5 = 40,10
• H(67)= 3 —— d2 = 20,1
9.19 选取哈希函数H(k)=(3k) MOD 11。用开放定址法处理冲突,
di=i((7k)MOD10 + 1) (i = 1,2,3,…)。试在0~10的散列地址空间中对
关键字序列(22,41,53,46,30,13,01,67)构造哈希表,并求等概率下
查找成功时的平均查找长度。
哈希表如下:
0
1
2
3
22
67
41
1
3
1
4
5
6
7
8
30
53
46
13
01
2
1
1
2
6
查找成功时的平均查找长度(比较次数):
ASL = 1/8(1+1+1+1+2+2+6+3) = 17/8
9
10
10.27 编写一个双向起泡的排序算法。即相邻两遍向相反方向起
泡。
• void Bubble_Sort2(int a[], int n){
low = 0; high = n – 1; change = 1;
while(low < high && change){
for(i = low; i < high; i++){
if(a[i] > a[i+1]){
swap(a[i], a[i+1]);
change=1;
}
}
high--;
for(i = high; i > low; i--){
if(a[i] < a[i-1]){
swap(a[i], a[i-1]);
change = 1;
}
}
low++;
}
}
10.31 编写算法,对n个关键字取整数值的记录序列进行整理,
以使所有关键字为负值的记录排在关键字为非负值的记录之前,
要求:(1)采用顺序存储结构,至多使用一个记录的辅助存储空
间;(2)算法的时间复杂度O(n);(3)讨论算法中记录的最大移动
次数。
• void Divide(int a[], int n){
low = 0; high = n – 1;
pivotkey = a[low];
while(low < high){
while(low < high && a[high] >= 0) high--;
a[low] = a[high];
while(low < high && a[low] < 0) low++;
a[high] = a[low];
}
a[low] = pivotkey;
}
10.31 编写算法,对n个关键字取整数值的记录序列进行整理,
以使所有关键字为负值的记录排在关键字为非负值的记录之前,
要求:(1)采用顺序存储结构,至多使用一个记录的辅助存储空
间;(2)算法的时间复杂度O(n);(3)讨论算法中记录的最大移动
次数。
• 最大移动次数:
数组前一半是非负数,后一半是负数时,共需要n次移动;

similar documents