第六章作业及答案

第六章作业

一、选择题

1.若不考虑结点的数据信息的组合情况，具有3个结点的树共有种（ ）形态，而二叉树共有( )种形态。

A.2 B.3 C.4 D.5

2.对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0= ( ) A.n1+1 B.n1+n2 C.n2+1 D.2n1+1

3.已知某非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即

ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为 ( ) A. G,D,B,A,F,H,C,E B. G,B,D,A,F,H,C,E C. B,D,G,A,F,H,C,E D. B,G,D,A,F,H,C,E 4、具有65个结点的完全二叉树的高度为（ ）。（根的层次号为1）

A．8 B．7 C．6 D．5 5、在有N个叶子结点的哈夫曼树中，其结点总数为（ ）。 A 不确定 B 2N C 2N+1 D 2N-1

6、以二叉链表作为二叉树存储结构，在有N个结点的二叉链表中，值为非空的链域的个数为（ ）。

A N-1 B 2N-1 C N+1 D 2N+1 7、树的后根遍历序列等同于该树对应的二叉树的( ).

A. 先序序列 B. 中序序列 C. 后序序列

8、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是 （ ）

A．39 B.52 C.111 D.119

9、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是（ ） A．41 B.82 C.113 D.122 二、填空题。

1、对于一个具有N个结点的二叉树，当它为一颗 _____ 二叉树时，具有最小高度。

2、对于一颗具有N个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为 _____ 个， 其中_____个用于链接孩子结点， _____ 个空闲着。

3、一颗深度为K的满二叉树的结点总数为 _____ ，一颗深度为K的完全二叉树的结点总数的最小值为 _____ ，最大值为 _____ 。

4、已知一棵二叉树的前序序列为ABDFCE，中序序列为DFBACE，后序序列为 三、应用题。

1、已知一棵树二叉如下，请分别写出按前序、中序、后序遍历时得到的结点序列，并将该二叉树还原成森林。 A

B

E

G

C

D

F

H

I

2 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。

五、算法设计题

1. 已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目和二叉树的深度。

2. 编写算法将每个节点的左右子树进行交换。

*3. 已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。

4. 已知二叉树按照二叉链表方式存储，写出按层遍历的算法（提示：利用队列）。

参考答案：

一 1 D 2 C 3 D 4 B 5 D 6 A 7 B 8.c 9B

二 1 完全二叉树 2 2N N-1 N+1 3 2k-1 2k-1 2k-1 4 FDBECA 三

1 void search(BiTree &T){

if(T){ cou++;

if(T->lchild!=NULL&&T->rchild!=NULL) count++; search(T->lchild); search(T->rchild);

} }

int Depth (BiTree T ) { // 返回二叉树的深度

if ( !T ) depthval = 0; else {

depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild );

depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight); }

return depthval; }

2

void exch_pre(BTNode* b)//基于前序的交换 {

BTNode* tmp;

if(b) {

tmp = b->lchild;

b->lchild = b->rchild; b->rchild = tmp; exch_pre(b->lchild); exch_pre(b->rchild); } }

void exch_in(BTNode* b) //基于中序的交换 {

BTNode* tmp; if(b) {

exch_pre(b->lchild); tmp = b->lchild;

b->lchild = b->rchild; b->rchild = tmp;

exch_pre(b->lchild); //!!!!!!! } }

void exch_post(BTNode* b) //基于后序的交换 {

BTNode* tmp; if(b) {

exch_pre(b->lchild); exch_pre(b->rchild); tmp = b->lchild;

b->lchild = b->rchild; b->rchild = tmp; } }

3 void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法 {

InitStack(S);

Push(S,T); //根指针进栈 while(!StackEmpty(S)) {

while(Gettop(S,p)&&p) {

visit(p->data);

push(S,p->lchild); } //向左走到尽头 pop(S,p);

if(!StackEmpty(S)) {

pop(S,p);

push(S,p->rchild); //向右一步 }

}//while

}//PreOrder_Nonrecursive

4. void LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType)) { // 初始条件：二叉树T存在,Visit是对结点操作的应用函数

// 操作结果：层序递归遍历T(利用队列),对每个结点调用函数Visit一次且仅一次 LinkQueue q; QElemType a; if(T) {

InitQueue(q); EnQueue(q,T);

while(!QueueEmpty(q)) {

DeQueue(q,a); Visit(a->data);

if(a->lchild!=NULL) EnQueue(q,a->lchild); if(a->rchild!=NULL) EnQueue(q,a->rchild); }

printf(\ } }

本文来源：https://www.bwwdw.com/article/v54t.html