中国铁道出版社数据结构(第二版)单元7练习参考答案

1、中国铁道出版社数据结构(第二版)单元7练习参考答案单元练习7一判断题（下列各题，正确的请在前面的括号内打；错误的打）（）（1）树结构中每个结点最多只有一个直接前驱。（）（2）完全二叉树一定是满二查树。（）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。（）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。（）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。（）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。（）（8）在哈夫曼编码中，当两个字符出现的

2、频率相同，其编码也相同，对于这种情况应该做特殊处理。（）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。（）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。二填空题（1）在树中，一个结点所拥有的子树数称为该结点的度。（2）度为零的结点称为叶（或叶子，或终端）结点。（3）树中结点的最大层次称为树的深度（或高度）。（4）对于二叉树来说，第i层上至多有2i-1个结点。（5）深度为h的二叉树至多有2h-1 个结点。（6）由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。（7）有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。（8）哈夫曼树是带权路径长度最小的二叉树

3、。（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（17）三个结点可

4、以组成 2 种不同形态的树。（18）将一棵完全二叉树按层次编号，对于任意一个编号为i 的结点，其左孩子结点的编号为： 2*i 。 （19）给定如下图所示的二叉树，其前序遍历序列为： ABEFHCG 。 （20）给定如下图所示的二叉树，其层次遍历序列为： ABCEFGH 。 三选择题（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）在一棵具

5、有五层的满二叉树中，结点的总数为（ B ）A 16B 31C 32D 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 （9）如右图所示的二叉树，后序遍历的序列是（ D ） A A 、B 、C

6、 、D 、E 、F 、G 、H 、IB A 、B 、D 、H 、I 、E 、C 、F 、GC H 、D 、I 、B 、E 、A 、F 、C 、GD H 、I 、D 、E 、B 、F 、G 、C 、A（10）对于下边的二叉树，其中序序列为 （ A ）A DBEHAFCGB DBHEAFCGC ABDEHCFGD ABCDEFGH （11）某二叉树的后序遍历序列为：DABEC ，中序遍历序列为: DEBAC ，则前序遍历序列为（ D ）。 A ACBEDB DECABC DEABCD CEDBA （12）具有n （n1）个结点的完全二叉树中，结点i （2in ）的左孩子结点是（ D ）。A 2i

7、B 2i+1 C 2i-1 D 不存在（若2i（13）把一棵树转换为二叉树后，这棵二叉树的形态是（ A ）。A 唯一的B 有多种C 有多种，但根结点都没有左孩子D 有多种，但根结点都没有右孩子（14）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（ B ）。 A 46 B 47 C 90 D 91（15）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（ B ）。A98 B99 C50 D100（16）二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的

8、线索，这种说法（ 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 ）。A3 B4 C5 D6（20）二叉树的叶结点个数比度为2的结点的个数（ C ）。A无关B相等 C多一个 D少一个四.

9、 简答题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，

10、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）森林中有几棵树？ 2）每一棵树的根结点分别是什么？ 3）第一棵树有几个结点？ 4）第二棵树有几个结点？ 5）森林中有几个叶结点？ （2） A ，C，G ，K （3） 6（4） 2 （5） 7 3二叉树按中序遍历的结果为：ABC ，试问有几种不同形态的二叉树可以得到这一遍历结果？并画出这些二叉树。答：（1） 5种。 （2

11、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 A D C F H G I2已知一棵二叉树的前序遍历和中序遍历的序列分别为：A ，B ，D ，G ，H ，C ，E ，F ，I 和G，D ，H ，B ，A ，E ，C ，I ，F 。 请画出此二叉树，并写出它的后序

12、遍历的序列。 其后序遍历的序列为：G H D B E I F C A3 已知一棵树的层次遍历的序列为：ABCDEFGHIJ，中序遍历的序列为：DBGEHJACIF ，请画出该二叉树，并写出它的后序遍历的序列。 解： 后序遍历的序列：D G J H E B I F C A4. 把下列一般树转换为二叉树 解：（1）（2） 5. 把下列森林转换为二叉树 解：6把下列二叉树还原为森林 解：还原后的二叉树为： 7 某二叉树的结点数据采用顺序存储，其结构如下：（1）画出该二叉树（3分）（2）写出按层次遍历的结点序列（2分） 解： （1） （2）层次遍历的结点序列：E A F D H C G I B8 某二

13、叉树的存储如下：data其中根结点的指针为6，lchild 、rchild 分别为结点的左、右孩子的指针域，data 为数据域。 （1）画出该二叉树（3分）（2）写出该树的前序遍历的结点序列（2分） 解：（1）（2）前序遍历的结点序列：A B C E D F H G I J 9 给定如图所示二叉树T ，请画出与其对应的中序线索二叉树。解： （1） 中序遍历序列：55 40 25 60 28 08 33 54（2） 中序线索二叉树： 10. 画出表达式：-A+B-C+D 的标识符树，并求它们的后缀表达式。解：后缀表达式：0 A B + C D +11画出表达式：（A+B/C-D）*（E*（F+G

14、）的标识符树，并求它们的后缀表达式。解：后缀表达式：A B C / + D E F G + * *12对于算术表达式（A+B*C/D）*E+F*G，画出标识符树，并求它们的后缀表达式。解：后缀表达式：A B C D / * + E * F G * +13 给定一个权集W=4，5，7，8，6，12，18，试画出相应的哈夫曼树，并计算其带权路径长度WPL 。解：4 5 6 7 8 12 18 9 13 17253560WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=15914 给定一个权集W=3，15，17，14，6，16，9，2，试画出相应的哈夫曼树，并计算其带权路径长度WPL

15、。 解2 3 6 9 14 15 16 17 5 29 33 11 20 49 82WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=22915 假设用于通信的电文仅由A 、B 、C 、D 、E 、F 、G 8个字母组成，字母在电文中出现的频率分别为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;1求二叉树中的度数为2的结

16、点。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-datamax)max=t-data;max=maxnode(t-lchild,ma

17、x);max=maxnode(t-rchild,max);3将二叉树各结点存储到一维数组中。void create(BT t,int a ,int i) if (t) ai=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-rc

18、hild, 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+;qrear=T;flag=1;p=rear;while (front front+;T=qfront;if (T-lchild!=NULL) rear+;qrear=T-lchild;cou

19、nt+;if (T-rchild!=NULL) rear+;qrear=T-rchild;count+;if (front=p) / 当前层已遍历完毕 if (flagflag=count;count=0;p=rear; / p指向下一层最右边的结点 / endwhilereturn(flag);6解：借助栈来进行对换。Swap(BinTree*T) BinTree *stack100, *temp;int top=-1;root=T;if (T!=NULL)top+;stacktop=T;while(top-1) T=stacktop;top-;if (T-child!=NULL|T-rch

20、ild!=NULL) / 交换结点的左右指针 temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;if (T-lchild!=NULL) top+;stacktop=T-lchild;if (T-rchild!=NULL) top+;stacktop=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(“n

21、The Node s Number:%d”,i);printf(“nThe Leafss 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;elseif (T-data=x) h=lh; count=h;e

22、lse 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”,co unt);模拟考题一 读程序，写出运行结果1二叉树的结构如图所示，试写出执行下列算法后的输出结果： 。（用大写的英文字母表示，字母之间不要任何间隔符号，最后一个字母后面也不要间隔符号）typedef struct BT datatype data;

23、 BT *lchild; BT *rchild; BT; void Preorder(BT *T) i f (T!=NULL) coutPreorder(T-lchild); Preorder(T-rchild); 解：ABCEDFG 先序遍历2二叉树的结构如图所示，试写出执行下列算法后的输出结果： 。typedef struct BT datatype data; / 定义结点 BT *lchild; BT *rchild; BT;int BTD(BT *T) i nt ldep,rdep; if (T=NULL) return 0; else ldep= BTD (T-lchild); r

24、dep= BTD (T-rchild); if (ldeprdep) return ldep+1; elsereturn rdep+1;解：4 （求二叉树深度）3二叉树的结构如图所示，试写出执行下列算法后，count 的值为多少？typedef struct BT datatype data; / 定义结点BT *lchild;BT *rchild;BT;int count=0;void Leafnum(BT *T)if (T!=NULL) if(T-lchild=NULL & T-rchild=NULL)count+;Leafnum(T-lchild);Leafnum(T-rchild);解

25、：3 （求叶结点数） (2，3，4改为程序填空)二程序填空1填空完成二叉树按层次遍历的程序typedef struct BT datatype data; / 定义结点BT *lchild;BT *rchild;BT;void Levelorder(BT *T) / 层次遍历 int i,j;BT *q100,*p;p=T;if ( p!=NULL ) i=1;qi=p;j=2; while (i!=j) p=qi;coutif ( p-lchild!=NULL ) qj= p-lchild ;j+;if (p-rchild!=NULL) qj= p-rchild ;j+; i+;三 应用题1 将下列二叉树转换为森林。 解：2 画出和下列二叉树相应的森林。 解： （根右边的子树肯定是森林，而孩子结点的右子树均为兄弟）3 某二叉树的结点数据采用顺序存储，其结构如下：（1）画出该二叉树（2分）（2）写出结点值为D 的父结点及左、右子树（3分） 解： （1） （2） D 的父结点为AD 的左子树为C D 的右子树为空4 某二叉树的存储如下：Lchild Data（1）画出该二叉树（3分）（2）写出该树的中序遍历的结点序列（2分） 解：（1） （2）中序遍历的结点序列：E C B H