数据结构单元练习7

单元练习7

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ） （√）（1）树结构中每个结点最多只有一个直接前驱。 （ㄨ）（2）完全二叉树一定是满二查树。 （ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。 （√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。 （√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。 （√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。 （√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。 （ㄨ）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。 （ㄨ）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。 （√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。

二．填空题 （1） 在树中，一个结点所拥有的子树数称为该结点的 度 。 （2） 度为零的结点称为 叶（或叶子，或终端） 结点。 （3） 树中结点的最大层次称为树的 深度（或高度） 。 （4） 对于二叉树来说，第i层上至多有 2i-1 个结点。 （5） 深度为h的二叉树至多有 2h-1 个结点。 （6） 由一棵二叉树的前序序列和 中序 序列可唯一确定这棵

二叉树。 （7） 有20个结点的完全二叉树，编号为10的结点的父结点的编号

是 5 。 （8） 哈夫曼树是带权路径长度 最小 的二叉树。 （9） 由二叉树的后序和 中序 遍历序列，可以唯一确定一棵二

叉树。

（10） 某二叉树的中序遍历序列为: DEBAC，后序遍历序列为：

EBCAD。则前序遍历序列为：DABEC 。

（11） 设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍

历序历为：DEBAFCHG，则二叉树中叶结点是： E、F、H 。

（12） 已知完全二叉树的第8层有8个结点，则其叶结点数是

68 。

（13） 由树转换成二叉树时，其根结点无 右子树 。

（14） 采用二叉链表存储的n个结点的二叉树，一共有 2n 个

指针域。

（15） 采用二叉链表存储的n个结点的二叉树，共有空指针 n+1

个。

（16） 前序为A，B，C且后序为C，B，A的二叉树共有 4 种。 A A A A

B B B B

C C C （17）三个结点可以组成 2 种不同形态的树。 C

（18）将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为： 2*i 。 （19）给定如下图所示的二叉树，其前序遍历序列为： ABEFHCG 。

A C B E F G

H

（20）给定如下图所示的二叉树，其层次遍历序列为： ABCEFGH 。

A C B E F G

H

三．选择题

（1）树最适合用来表示（ D ）。

A．有序数据元素 B．无序数据元素 C．元素之间无联系的数据 D．元素之间有分支的层次关系

（2）前序为A，B，C的二叉树共有（ D ）种。 A．2 B．3 C．4 D．5

（3）根据二叉树的定义，具有3个结点的二叉树有（ C ）种树型。 A．3 B．4 C．5 D．6 （4）在一棵具有五层的满二叉树中，结点的总数为（ B ）

A．16 B．31 C．32 D．33

（5）具有64个结点的完全二叉树的深度为（ C ）

A．5 B．6 C．7 D．8

（6）任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（ A ）。

A．不发生改变 B．发生改变 C．不能确定 D．以上都不对

（7）A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（ C ）。

A．A在B右方 B．A是B祖先 C．A在B左方 D．A是B子孙

（8）下列4棵树中，（ B ）不是完全二叉树。

A． B． C． D． A A A A

C C C C B B B B

D E F D D E D E FG （9）如右图所示的二叉树，后序遍历的序列是（ D ） A． A、B、C、D、E、F、G 、H、I A

C BB． A、B、D、H、I、E、C、F、G F G D E C． H、D、I、B、E、A、F、C、G H I D． H、I、D、E、B、F、G、C、A

（10）对于下边的二叉树，其中序序列为 （ A ）

A．DBEHAFCG B．DBHEAFCG C．ABDEHCFG D．ABCDEFGH

A B C D E F G H

（11）某二叉树的后序遍历序列为：DABEC，中序遍历序列为: DEBAC，则前序遍历序列为（ D ）。

A． ACBED B．DECAB C．DEABC D．CEDBA

（12）具有n（n>1）个结点的完全二叉树中，结点i（2i>n）的左孩子结点是（ D ）。

A．2i B．2i+1 C．2i-1 D．不存在 （若2i<=n，则答案为A）

（13）把一棵树转换为二叉树后，这棵二叉树的形态是（ A ）。

A．唯一的 B．有多种

C．有多种，但根结点都没有左孩子 D．有多种，但根结点都没有右孩子

（14）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（ B ）。

A．46 B．47 C．90 D．91 （15）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（ B ）。

A．98 B．99 C．50 D．100 （16）二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法（ B ）。

A．正确 B．错误 C．不确定 D．都有可能

（17）下列陈述正确的是（ D ）。

A．二叉树是度为2的有序树 B．二叉树中结点只有一个孩子时无左右之分

C．二叉树中必有度为2的结点 D．二叉树中最多只有两棵子树，且有左右子树之分

（18）用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是（ B ）。

Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15

（ 先构造哈夫曼树，WPL=（1+2）*3+（3+4+5）*2=33 ）

（19）在树结构中，若结点B有4个兄弟，A是B的父亲结点，则A的度为为（ C ）。

A．3 B．4 C．5 D．6

（20）二叉树的叶结点个数比度为2的结点的个数（ C ）。 A．无关 B．相等 C．多一个 D．少一个

四. 简答题

1． 已知一棵树边的集合如下，请画出此树，并回答问题。 {(L,M),(L,N),(E,L),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(H,I),(C,H),(A,C)}

（1）哪个是根结点？ （2）哪些是叶结点？ （3）哪个是G的双亲？ （4）哪些是G的祖先？ （5）哪些是G的孩子？ （6）哪些是E的子孙？

（7）哪些是E的兄弟？哪些是F的兄弟？ （8）结点B和N的层次各是多少？

（9）树的深度是多少？

（10）以结点C为根的子树的深度是多少？ （11）树的度数是多少？ 答：

（1）A是根结点。

（2）叶结点：M，N，D，J，K，F，I。 （3）G的双亲：C。 （4）G的祖先：A，C。 （5）G的孩子：J，K。 （6）E的子孙：L，M，N。

（7）E的兄弟：D；F的兄弟：G，H。 （8）结点B的层次为2；结点N的层次是5。 （9）树的深度是5。

（10）以结点C为根的子树的深度是3。 （11）树的度数是3。

2． 设下列二叉树是与某森林对应的二叉树，试回答下列问题。 （1）森林中有几棵树？

A （2）每一棵树的根结点分别是什么？ B C （3）第一棵树有几个结点？ （4）第二棵树有几个结点？ D E F G （5）森林中有几个叶结点？ J I H K

L 解： （1） 4 （2） A，C，G，K （3） 6

（4） 2 （5） 7

3．二叉树按中序遍历的结果为：ABC，试问有几种不同形态的二叉树可以得到这一遍历结果？并画出这些二叉树。 答： （1） 5种。 （2）

C B A A B C A B C AB C B A C

4. 分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。 答：

（1） 三个结点的树

（2） 三个结点的二叉树树

五. 应用题

1．已知一棵二叉树的后序遍历和中序遍历的序列分别为：

A，C，D，B，G，I，H，F，E和A，B，C，D，E，F，G，H，I。 请画出该二叉树，并写出它的前序遍历的序列。 答：恢复的二叉树为： E B F A DH C G I

其前序遍历的序列为：E B A D C F H G I

2．已知一棵二叉树的前序遍历和中序遍历的序列分别为：

A，B，D，G，H，C，E，F，I和G，D，H，B，A，E，C， 请画出此二叉树，并写出它的后序遍历的序列。。 答：恢复的二叉树为： A B C D E F G H I

其后序遍历的序列为：G H D B E I F C A

I，F。

3． 已知一棵树的层次遍历的序列为：ABCDEFGHIJ，中序遍历的序列为：DBGEHJACIF，请画出该二叉树，并写出它的后序遍历的序列。 解：

后序遍历的序列：D G J H E B I F C A

4. 把下列一般树转换为二叉树

1 (1) (2) DG B E H I J A C F

3 2 4 6 5 7 E B F J G H A C I D 解：

1 A 8 （1） 2 B （2）

3 4 E F C H D

5. 把下列森林转换为二叉树

E K B A C D F G I H J

解：

A B C F G DK C F H I E J G

6．把下列二叉树还原为森林

E A

B D H I 解：还原后的二叉树为：

7． 某二叉树的结点数据采用顺序存储，其结构如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F D H C G I B B A C DE F H G I

5 29 33 11 20 49

82

WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229

15． 假设用于通信的电文仅由A、B、C、D、E、F、G 、H8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。

解：以权值：2、3、6、7、10、19、21、32构造哈夫曼树：

六．算法设计题

以二叉链表为存储结构，设二叉树BT结构为： typedef struct BT { char data; BT *lchild; BT *rchild; }BT;

0 0 0 1001 401 0 0 601 字母编号 A B C D 1 E F G H 对应编码 1010 00 10000 1001 11 10001 01 1011 出现频率 7 19 2 6 32 3 21 10 19 21 11 5 1 2 328 1 17 7 32 0 1 0 6 101． 求二叉树中的度数为2的结点。 2． 求二叉树中值为最大的元素。 3． 将二叉树各结点存储到一维数组中。

4． 前序输出二叉树中各结点及其结点所在的层号。 5． 求二叉树的宽度

6． 交换二叉树各结点的左右子树。

7． 写出在二叉树中查找值为x的结点在树中层数的算法。 解： 1．

求二叉树中的度数为2的结点。 void count(BT t) { if (t)

{ if (t->lchild && t->rchild)

k++;

count(t->lchild); count(t->rchild); } }

2. 求二叉树中值为最大的元素。

int maxnode(BT t, int max) { if (t)

{ if (t->data>max)

max=t->data;

max=maxnode(t->lchild,max); max=maxnode(t->rchild,max); } }

3．将二叉树各结点存储到一维数组中。

void create(BT t,int a[ ],int i) { if (t)

{ a[i]=t->data;

create (t->lchild, a, 2*i); create (t->rchild, a, 2*i+1);

} }

4．前序输出二叉树中各结点及其结点所在的层号。void preorderlevel (BT t,int h) // t的层数为h { if (t!=NULL)

{ printf (“%d,%d”,t->data, h); preorderlevel (t->lchild, h+1); preorderlevel (t->rchild, h+1);

} }

5. 求二叉树的宽度

思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。

int Width(BT *T)

{ int front=-1,rear=-1; // 队列初始化 int flag=0,count=0,p;

// p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值 if (T!=NULL) { rear++; q[rear]=T; flag=1; p=rear; }

while (front

{ front++; T=q[front];

if (T->lchild!=NULL) { rear++;

q[rear]=T->lchild;

count++;

}

if (T->rchild!=NULL) { rear++;

q[rear]=T->rchild; count++; }

if (front==p) 完毕

{ if (flag

flag=count;

count=0;

p=rear; 层最右边的结点 }

} return(flag); }

6．解：借助栈来进行对换。

Swap(BinTree*T)

{ BinTree *stack[100], *temp; int top=-1; root=T;

// 当前层已遍历指向下一 // endwhile // p

if (T!=NULL)

{ top++; stack[top]=T; while(top>-1) { T=stack[top]; top--;

if (T->child!=NULL||T->rchild!=NULL)

{ // 交换结点的左右指针

temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; }

if (T->lchild!=NULL) { top++;

stack[top]=T->lchild; }

if (T->rchild!=NULL) { top++;

stack[top]=T->rchild;

}

}

} } main()

{ int I,j,k,l; printf(“\\n”); root=CreateBinTree(); Inorder (root); i=CountNode (root); j=CountLeafs (root); k=Depth (root); l=Width (root);

printf(“\\nThe Node ’s Number:%d”,i); printf(“\\nThe Leafs’s Number:%d”,j); printf(“\\nThe Depth is:%d”,k); printf(“\\nThe width is:%d”,l); Swap(root);

Printf(“\\nThe swapTree is:”); Inorder(root); }

7．解：

int h=-1,lh=1,count=0;charx=’c’; // 赋初值 Level (BinTree T,int h,int lh) // 求X结点在树只的层树 { if (T==Null)

h=0; else

if (T->data==x) { h=lh; count=h;} else { h++;

Level(T->lchild,h,lh); if (h==-1)

Level(T->rchild,h,lh);

} } main()

{ BinTree *(*newroot); Printf(“\\n”); Root=CreateBinTree(); Inorder(root);

Printf(“\\n”); Level(root,h,lh); Printf(“%d”,count); }

模拟考题

一． 读程序，写出运行结果

1．二叉树的结构如图所示，试写出执行下列算法后的输出结果： 。

（用大写的英文字母表示，字母之间不要任何间隔符号，最后一个字母后面也不要间隔符号）

typedef struct BT { datatype data; BT *lchild; BT *rchild; }BT;

void Preorder(BT *T) { if (T!=NULL) { cout<< T->data; Preorder(T->lchild); Preorder(T->rchild); } }

解：ABCEDFG 先序遍历

2．二叉树的结构如图所示，试写出执行下列算法后的输出结果： 。

C E BF A D G

typedef struct BT

{ datatype data; // 定义结点 BT *lchild; BT *rchild; C BF A D G }BT;

E int BTD(BT *T) { int ldep,rdep; if (T==NULL) return 0; else

{ ldep= BTD (T->lchild); rdep= BTD (T->rchild); if (ldep>rdep) return ldep+1; else

return rdep+1;

} }

解：4 （求二叉树深度）

3．二叉树的结构如图所示，试写出执行下列算法后，少？

count的值为多typedef struct BT

{ datatype data; // 定义结点B BT *lchild; BT *rchild; }BT;

int count=0; void Leafnum(BT *T) {

if (T!=NULL)

C E A D F G { if(T->lchild==NULL && T->rchild==NULL) count++;

Leafnum(T->lchild); Leafnum(T->rchild); } }

解：3 （求叶结点数） (2，3，4改为程序填空)

二． 程序填空

1．填空完成二叉树按层次遍历的程序

typedef struct BT

{ datatype data; // 定义结点 BT *lchild;

BT *rchild; }BT;

void Levelorder(BT *T) // 层次遍历 { int i,j; BT *q[100],*p; p=T;

if ( p!=NULL ) { i=1;q[i]=p;j=2; } while (i!=j)

{ p=q[i];

cout<< p->data ;

if ( p->lchild!=NULL ) { q[j]= p->lchild ;j++;} if (p->rchild!=NULL)

{ q[j]= p->rchild ;j++; } i++; }

}

}

三． 应用题

1． 将下列二叉树转换为森林。 A B C D E F G H I J K 解： A B E D I H

C G F J K 2． 画 解：

D G B H J K A E C F 出和下列二叉树相应的森林。

I M （根右边的子树肯定是森林，而孩子结点的右子树均为兄弟）

3． 某二叉树的结点数据采用顺序存储，其结构如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

10． 对于算术表达式（A+B*C/D）*E+F*G，画出标识符树，并求它们的后缀表达式。 解： + * * + E FG A * B / C D

后缀表达式：A B C D / * + E * F G * +

11． 给定一个权集W={4，5，7，8，20，12，2}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。 解： 58 2335 11 12 15 20 5 67 8 2 4

WPL=(12+20)*2+(5+7+8)*3+(2+4)*4=148

12． 给定一个权集W={7，19，2，6，32，3，的哈夫曼树，并计算其带权路径长度WPL。 解： 100（1）

40 60 19 21 28 32 11 17 5 6 7 10 2 3

21，10}，试画出相应

（2） WPL＝(19+21+32)* 2+ (6+7+10) 4+ (2+3) *5=144+92+25=261

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