《数据结构单元练习7.》由会员分享，可在线阅读，更多相关《数据结构单元练习7.（32页珍藏版）》请在金锄头文库上搜索。
1、(11)(12)(13)(14)(15)(16)前序为A，B，CDEBAFCHG，则二单元练习7一判断题(下列各题，正确的请在前面的括号内打V;错误的打X )(V) (1)树结构中每 个结点最 多只有一个直 接前驱。(X) (2)完全二叉树 一定是满 二查树。(X) ( 3)在中序线索二叉树中，右线索若不为空，则一定指向其双亲。(V) (4) 一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。(V) ( 5)二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。(V) (6)由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。(V) ( 7)在完全二叉树
2、中，若一个结点没有左孩子，则它必然是叶子结点。(X) ( 8)在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特 殊处理。(X) ( 9)含多于两棵树的森林转换的二叉树，其根结点一 定无右 孩子。(V) (10)具有n个叶子结点的 哈夫曼 树共有2n-1个结点。二填空题(1) 在树中，一个结点所拥有的子树数称为该结点的度 。(2) 度为零的结点称为叶(或叶子，或终端)结点。(3) 树中结点的最大层次称为树的深度(或高度)。(4) 对于二叉树来说，第i层上至多有 2i-1个结点。(5) 深度为h的二叉树至多有2h-1个结点。(6) 由一棵二叉树的前序序列和中序序列可唯一
3、确定这棵二叉树。(7) 有20个结点的完全二叉树，编号为10的结点的父结点的编号是5 。(8) 哈夫曼树是带权路径长度最小 的二叉树。(9) 由二叉树的后序和中序 遍历序列，可以唯一确定一棵二叉树。(10) 某二叉树的中序遍历序列为：DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为:DABEC 。设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为:叉树中叶结点是：E、F、H 。已知完全二叉树的第 8层有8个结点，则其叶结点数是68。由树转换成二叉树时，其根结点无右子树 。采用二叉链表存储的 n个结点的二叉树，一共有 2n个指针域。采用二叉链表存储的 n个结点的二叉树，共
4、有空指针n+1个。(17)三个结点可以组成2种不同形态的树。2*i。(18) 将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为ABEFHCG给定如下图所示的二叉树，其前序遍历序列为:(17)三个结点可以组成2种不同形态的树。(17)三个结点可以组成2种不同形态的树。(19) 给定如下图所示的二叉树，其层次遍历序列为：ABCEFGHACBEFGH三选择题(1) 树最适合用来表示( D )。A 有序数据元素C 元素之间无联系的数据B 无序数据元素D元素之间有分支的层次关系(2) 前序为A , B, C的二叉树共有( D )种。A 2B 3C 4(3) 根据二叉树的定义，
5、具有3个结点的二叉树有( C )种树型。A 3B 4C 5(4 )在一棵具有五层的满二叉树中，结点的总数为(B )A 16B 31C 32(5)具有64个结点的完全二叉树的深度为( C )A 5B 6C 7D 5D 6D 33D 8(6)任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序(A.不发生改变B 发生改变C 不能确定A )。D 以上都不对(7) A , B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是( C )。B . A是B祖先C . A在B左方D. A是B子孙(8) 下列4棵树中,B )不是完全二叉树。(9) 如右图所示的二叉树，后序遍历的序列是(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、AD )(10) 对于下边的二叉树，其中序序列为(A )A. DBEHAFCG.ABCDEFGH(11) 某二叉树的后序遍历序列为：DABEC，中序遍历序列为：DEBAC，则前序遍历序列为(D )。A . ACBEDB . DECABC . DEABCD . CEDBA(12) 具有n (n1)个结点的完全二叉树中，结点i ( 2in)的左孩子结点是(D )。A . 2iB . 2i+1C . 2i-1D .不存在(若2i=n，则答案为A)(13) 把
7、一棵树转换为二叉树后，这棵二叉树的形态是(A )。A .唯一的B.有多种C .有多种，但根结点都没有左孩子D .有多种，但根结点都没有右孩子(14 )将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1,则编号为45的结点的左孩子编号为(B )。A . 46B . 47C . 90D . 91(15)将一棵有 100 个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为 49 的结点的右孩子编号为( B )。A 98B 99C. 50D. 10016)二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法(BA正确B.错误
8、C .不确定D .都有可能17)下列陈述正确的是(D )。A二叉树是度为 2 的有序树B .二叉树中结点只有一个孩子时无左右之分C二叉树中必有度为2 的结点D .一叉树中最多只有两棵子树，且有左右子树之分18)用 5 个权值 3, 2, 4, 5, 1 构造的哈夫曼树的带权路径长度是(B )。A 32B. 33C. 34D.15先构造哈夫曼树，WPL=( 1+2) *3+( 3+4+5) *2=33 )19)在树结构中，若结点B有4个兄弟，A是B的父亲结点，贝UA的度为为(C )。A 3B. 4C. 5D.620)二叉树的叶结点个数比度为 2的结点的个数( C )。A 无关B.相等C .多一个
9、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
10、，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.设下列二叉树是与某森林对应的二叉树，试回答下列问题。ACBDFGEHJKL解4(2)G,K(3)6(4)2(5)7答种5(2)AAACBCBBACABCCB答o(2)O(i)(i)(i)A , C4.分别画出具有3个结点的树和三个结点的二叉树的
11、所有不同形态。(5 )森林中有几个叶结点?ABC试问有几种不同形态的二叉树可以得到这一遍历结果？并画三个结点的树(1)森林中有几棵树?(2)每一棵树的根结点分别是什么?(3 )第一棵树有几个结点?(4 )第二棵树有几个结点?3.二叉树按中序遍历的结果为:出这些二叉树。三个结点的二叉树树五.应用题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 I 2 .已知一棵二叉树的前序遍历
12、和中序遍历的序列分别为：A , B, D, G H, C, E, F, I 和 G D, H, B, A, E, C, I , F。 请画出此二叉树，并写出它的后序遍历的序列。答：恢复的二叉树为：AB：C1DE : FGH ：l I其后序遍历的序列为：G H D B E I F C AABCDEFGHIJ，中序遍历的序列为:DBGEHJACIF，请画3.已知一棵树的层次遍历的序列为：出该二叉树，并写出它的后序遍历的序列。解:后序遍历的序列：D G J H E B I F C A解:4.(1(2) A解:5.把下列森林转换为二叉树KABGCHE其中根结点的指针为6, Ichild 、rchild分别为结点的左、右孩子的指针域,data为数据域。6.把下列二叉树还原为森林解:其中根结点的指针为6, Ichild 、rchild分别为结点的左、右孩子的指针域,data为数据域。其中根结点的指针为6, Ichild 、rchild分别为结点的左、右孩子的指针域,data为数据域。7.某二叉树的结点数据采用顺序存储，其结构如下:1234567891011121314151617181920EAFDHCGIB(1)画出该二叉树(3分)(2)写出按层次遍历的结点序列(2分)解:(1)(2)002
