admin 管理员组文章数量: 1086019
2024年9月13日发(作者:shell批量注释)
《数据结构与算法》第二部分 习题精选
一、下面是有关二叉树的叙述,请判断正误
( )1. 若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n—1个非空
指针域。
( )2.二叉树中每个结点的两棵子树的高度差等于1。
( )3.二叉树中每个结点的两棵子树是有序的。
( )4.二叉树中每个结点有两棵非空子树或有两棵空子树。
( )5.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字
值,且小于其右非空子树(若存在的话)所有结点的关键字值。
( )6.二叉树中所有结点个数是2
k-1
-1,其中k是树的深度。
( )7.二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。
( )8.对于一棵非空二叉树,它的根结点作为第一层,则它的第i层上最多能有2
i
—1个
结点。
( )9.用二叉链表法(link-rlink)存储包含n个结点的二叉树,结点的2n个指针区域中有
n+1个为空指针。
( √ )10. 具有12个结点的完全二叉树有5个度为2的结点。
二、填空
1. 由3个结点所构成的二叉树有 种形态。
2. 一棵深度为6的满二叉树有 个分支结点和 个叶子。
3. 一棵具有257个结点的完全二叉树,它的深度为 。
4.设一棵完全二叉树有700个结点,则共有 个叶子结点。
5. 设一棵完全二叉树具有1000个结点,则此完全二叉树有 个叶子结点,有 个
度为2的结点,有 个结点只有非空左子树,有 个结点只有非空右子树。
6.一棵含有n个结点的k叉树,可能达到的最大深度为 ,最小深度为 。
7. 二叉树的基本组成部分是:根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次
序有六种。最常用的是三种:前序法(即按N L R次序),后序法(即按 次序)和
中序法(也称对称序法,即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉
树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必
是 。
8.中序遍历的递归算法平均空间复杂度为 。
9.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是 。
三、单项选择题
( )1. 不含任何结点的空树 。
(A)是一棵树; (B)是一棵二叉树;
(C)是一棵树也是一棵二叉树; (D)既不是树也不是二叉树
( )2.二叉树是非线性数据结构,所以 。
(A)它不能用顺序存储结构存储; (B)它不能用链式存储结构存储;
(C)顺序存储结构和链式存储结构都能存储;
(D)顺序存储结构和链式存储结构都不能使用
( )3. 具有n(n>0)个结点的完全二叉树的深度为 。
(A) log
2
(n) (B) log
2
(n) (C) log
2
(n) +1 (D) log
2
(n)+1
( )4.把一棵树转换为二叉树后,这棵二叉树的形态是 。
(A)唯一的 (B)有多种
(C)有多种,但根结点都没有左孩子 (D)有多种,但根结点都没有右孩子
四、算法设计题
1.编写递归算法,计算二叉树中叶子结点的数目。
2.写出求二叉树深度的算法,先定义二叉树的抽象数据类型。
或编写递归算法,求二叉树中以元素值为x的结点为根的子树的深度。
3.编写按层次顺序(同一层自左至右)遍历二叉树的算法。
或:按层次输出二叉树中所有结点;
4. 已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中,试编写一个算法打印
出编号为i的结点的双亲和所有的孩子。
5.编写算法判别给定二叉树是否为完全二叉树。
6、假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07,0.19,
0.02,0.06,0.32,0.03,0.21,0.10。试为这8个字母设计哈夫曼编码。使用0~7的二进制
表示形式是另一种编码方案。对于上述实例,比较两种方案的优缺点。
习题精选答案
一、
1.(√)2.(×) 3.(√) 4.(×) 5.(×)
6.(×) 7.(×) 8.(×)9.( √ )。10.( √ )
二
1.5 2. 31 32 3.9 4. 350 5. 500 499 1 0
6. n 2 7. L R N F E G H D C B 8. O(n) 9. 33
三、单项选择题
1.(C)2.(C) 3.(C)4.(A)
四、1. 解:思路:输出叶子结点比较简单,用任何一种遍历递归算法,凡是左右指针均空
者,则为叶子,将其打印出来。
法一:核心部分为:
DLR(liuyu *root) /*中序遍历 递归函数*/
{if(root!=NULL)
{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%dn",root->data);}
DLR(root->lchild);
DLR(root->rchild); }
return(0);
}
法二:
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目
{
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1; //叶子结点
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加
上右子树的叶子数
}//LeafCount_BiTree
① 打印叶子结点值(并求总数)
思路:先建树,再从遍历过程中打印结点值并统计。
步骤1 键盘输入序列12,8,17,11,16,2,13,9,21,4,构成一棵二叉排序树。叶子
结点值应该是4,9, 13, 21, 总数应该是4.
12
7 17
2 11 16 21
4 9 13
编程: 生成二叉树排序树之后,再中序遍历排序查找结点的完整程序如下:
说明部分为:
#include
#include
typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test;
liuyu *root;
int sum=0;int m=sizeof(test);
void insert_data(int x) /*如何生成二叉排序树?参见教材P43C程序*/
{ liuyu *p,*q,*s;
s=(test*)malloc(m);
s->data=x;
s->lchild=NULL;
s->rchild=NULL;
if(!root){root=s; return;}
p=root;
while(p) /*如何接入二叉排序树的适当位置*/
{q=p;
if(p->data==x){printf("data already exist! n");return;}
else if(x
}
if(x
else q->rchild=s;
}
DLR(liuyu *root) /*中序遍历 递归函数*/
{if(root!=NULL)
{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%dn",root->data);}
DLR(root->lchild);
DLR(root->rchild); }
return(0);
}
main() /*先生成二叉排序树,再调用中序遍历递归函数进行排序输出*/
{int i,x;
i=1;
root=NULL; /*千万别忘了赋初值给root!*/
do{printf("please input data%d:",i);
i++;
scanf("%d",&x); /*从键盘采集数据,以-9999表示输入结束*/
if(x==-9999){
DLR(root);
printf("nNow output count value:%dn",sum);
return(0); }
else insert_data(x);} /*调用插入数据元素的函数*/
while(x!=-9999);
return(0);}
2. 答;设计思路:只查后继链表指针,若左或右孩子的左或右指针非空,则层次数加1;否
则函数返回。
但注意,递归时应当从叶子开始向上计数,否则不易确定层数。
int depth(liuyu*root) /*统计层数*/
{int d,p; /*注意每一层的局部变量d,p都是各自独立的*/
p=0;
if(root==NULL)return(p); /*找到叶子之后才开始统计*/
else{
d=depth(root->lchild);
if(d>p) p=d; /*向上回朔时,要挑出左右子树中的相对大的那个深度值*/
d=depth(root->rchild);
if(d>p)p=d;
}
p=p+1;
return(p);
}
法二:
int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度
{
if(T->data==x)
{
printf("%dn",Get_Depth(T)); //找到了值为x的结点,求其深度
exit 1;
}
}
else
{
if(T->lchild) Get_Sub_Depth(T->lchild,x);
if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找
}
}//Get_Sub_Depth
int Get_Depth(Bitree T)//求子树深度的递归算法
{
if(!T) return 0;
else
{
m=Get_Depth(T->lchild);
n=Get_Depth(T->rchild);
return (m>n?m:n)+1;
}
}//Get_Depth
步骤2: 执行求深度的函数,并打印统计出来的深度值。
完整程序如下:
#include
#include
typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test;
liuyu *root;
int sum=0;int m=sizeof(test);
void insert_data(int x) /*如何生成二叉排序树?参见教材P43C程序*/
{ liuyu *p,*q,*s;
s=(test*)malloc(m);
s->data=x;
s->lchild=NULL;
s->rchild=NULL;
if(!root){root=s; return;}
p=root;
while(p) /*如何接入二叉排序树的适当位置*/
{q=p;
if(p->data==x){printf("data already exist! n");return;}
else if(x
}
if(x
else q->rchild=s;
}
int depth(liuyu*root) /*统计层数*/
{int d,p; /*注意每一层的局部变量d,p都是各自独立的*/
p=0;
if(root==NULL)return(p); /*找到叶子之后才开始统计*/
else{
d=depth(root->lchild);
if(d>p) p=d; /*向上回朔时,要挑出左右子树中的相对大的那个深度值*/
d=depth(root->rchild);
if(d>p)p=d;
}
p=p+1;
return(p);
}
void main() /*先生成二叉排序树,再调用深度遍历递归函数进行统计并输出
*/
{int i,x;
i=1;
root=NULL; /*千万别忘了赋初值给root!*/
do{printf("please input data%d:",i);
i++;
scanf("%d",&x); /*从键盘采集数据,以-9999表示输入结束*/
if(x==-9999){
printf("nNow output depth value=%dn", depth (root)); return; }
else insert_data(x);} /*调用插入数据元素的函数*/
while(x!=-9999);
return;}
3. 解:思路:既然要求从上到下,从左到右,则利用队列存放各子树结点的指针是个好办
法。
这是一个循环算法,用while语句不断循环,直到队空之后自然退出该函数。
技巧之处:当根结点入队后,会自然使得左、右孩子结点入队,而左孩子出队时又会立即使
得它的左右孩子结点入队,……以此产生了按层次输出的效果。
level(liuyu*T)
/* liuyu *T,*p,*q[100]; 假设max已知*/
{int f,r;
f=0; r=0; /*置空队*/
r=(r+1)%max;
q[r]=T; /*根结点进队*/
while(f!=r) /*队列不空*/
{f=(f+1%max);
p=q[f]; /*出队*/
printf("%d",p->data); /*打印根结点*/
if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空,则左子树进队*/
if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空,则右子树进队*/
}
return(0);
}
法二:
void LayerOrder(Bitree T)//层序遍历二叉树
{
InitQueue(Q); //建立工作队列
EnQueue(Q,T);
while(!QueueEmpty(Q))
{
DeQueue(Q,p);
visit(p);
if(p->lchild) EnQueue(Q,p->lchild);
if(p->rchild) EnQueue(Q,p->rchild);
}
}//LayerOrder
可以用前面的函数建树,然后调用这个函数来输出。
完整程序如下(已上机通过)
#include
#include
#define max 50
typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test;
liuyu *root,*p,*q[max];
int sum=0;int m=sizeof(test);
void insert_data(int x) /*如何生成二叉排序树?参见教材P43C程序*/
{ liuyu *p,*q,*s;
s=(test*)malloc(m);
s->data=x;
s->lchild=NULL;
s->rchild=NULL;
if(!root){root=s; return;}
p=root;
while(p) /*如何接入二叉排序树的适当位置*/
{q=p;
if(p->data==x){printf("data already exist! n");return;}
else if(x
}
if(x
else q->rchild=s;
}
level(liuyu*T)
/* liuyu *T,*p,*q[100]; 假设max已知*/
{int f,r;
f=0; r=0; /*置空队*/
r=(r+1)%max;
q[r]=T; /*根结点进队*/
while(f!=r) /*队列不空*/
{f=(f+1%max);
p=q[f]; /*出队*/
printf("%d",p->data); /*打印根结点*/
if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空,则左子树进队*/
if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空,则右子树进队*/
}
return(0);
}
void main() /*先生成二叉排序树,再调用深度遍历递归函数进行统计并输出
*/
{int i,x;
i=1;
root=NULL; /*千万别忘了赋初值给root!*/
do{printf("please input data%d:",i);
i++;
scanf("%d",&x); /*从键盘采集数据,以-9999表示输入结束*/
if(x==-9999){
printf("nNow output data value:n", level(root)); return; }
else insert_data(x);} /*调用插入数据元素的函数*/
while(x!=-9999);
return;}
4. 答:首先,由于是完全二叉树,不必担心中途会出现孩子为null的情况。
其次分析:结点i的左孩子为2i,右孩子为2i+1;直接打印即可。
Printf(“Left_child=”, %d, v[2*i].data; “Right_child=”, %d, v[2*i+1].data;);
但其双亲是i/2,需先判断i为奇数还是偶数。若i为奇数,则应当先i-- ,然后再除以
2。
If(i/2!=0)i--;
Printf(“Parents=”, %d, v[i/2].data;);
5. 答:int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0
{
InitQueue(Q);
flag=0;
EnQueue(Q,T); //建立工作队列
while(!QueueEmpty(Q))
{
{
DeQueue(Q,p);
if(!p) flag=1;
else if(flag) return 0;
else
{
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列
}
}//while
return 1;
}//IsFull_Bitree
分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点
是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空
指针的序列.反之,则序列中会含有空指针.
6、解:方案1;哈夫曼编码
先将概率放大100倍,以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10},按哈夫曼规则:【[(2,3),6], (7,10)】, ……19, 21, 32
(100)
0 1
(40) (60)
0 1 0 1
19 21 32 (28)
19 21 32
(17) (11)
0 1
7 10 6 (5)
0 1 0 1
2 3
7 10 6
0 1
2 3
方案比较:
字母编号 对应编码 出现频率 字母编号 对应编码 出现频率
1 1100 0.07 1 000 0.07
2 00 0.19 2 001 0.19
3 11110 0.02 3 010 0.02
4 1110 0.06 4 011 0.06
10 0.32 5 100 0.32
5
11111 0.03 6 101 0.03
6
7 110 0.21
方案1的WPL=2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61
方案2的WPL=3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3
结论:哈夫曼编码优于等长二进制编码
版权声明:本文标题:《数据结构与算法》第六章-树与二叉树习题 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.roclinux.cn/p/1726231302a929718.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论