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(xdata)p=p->lchild; else p=p->rchild;

}

if(xdata)q->lchild=s;

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(xdata)p=p->lchild; else p=p->rchild;

}

if(xdata)q->lchild=s;

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(xdata)p=p->lchild; else p=p->rchild;

}

if(xdata)q->lchild=s;

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

结论:哈夫曼编码优于等长二进制编码


本文标签: 结点 二叉树 算法 遍历 排序