《树和二叉树13》由会员分享，可在线阅读，更多相关《树和二叉树13（2页珍藏版）》请在金锄头文库上搜索。
1、第六章树和二叉树(1-3)一、选择题1.设森林 F 对应的二叉树为B，它有 m个结点， B 的根为 p,p 的右子树结点个数为n, 森林中第一棵树的结点个数是（）A m-nB m-n-1C n+1D 条件不足，无法确定2设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和 M3。与森林对应的二叉树根结点的右子树上的结点个数是（）。A M1B M1+M2CM3D M2+M3FF3. 设给定权值总数有 n 个，其哈夫曼树的结点总数为 ( )A不确定B 2nC2n+1D2n-14.有 n 个叶子的哈夫曼树的结点总数为（）。A不确定B 2nC 2n+1D 2n-15在下列存储形式中
2、，哪一个不是树的存储形式？（）A双亲表示法B 孩子链表表示法C 孩子兄弟表示法D 顺序存储表示法6.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )A不确定B. 0C. 1D. 27.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。A. 0B. 1C. 2D.不确定8.若 X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则 x 的前驱为 ()A.X 的双亲 B.X 的右子树中最左的结点C.X的左子树中最右结点D.X 的左子树中最右叶结点9.引入二叉线索树的目的是（）A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C为了能方
3、便的找到双亲D 使二叉树的遍历结果唯一10.线索二叉树是一种（）结构。A逻辑 B 逻辑和存储C物理D线性11 n 个结点的线索二叉树上含有的线索数为（）A 2nB n lC n lD n12（）的遍历仍需要栈的支持 .A前序线索树B中序线索树C后序线索树13.由 3个结点可以构造出多少种不同的有向树？（）A 2B 3C 4D514下述编码中哪一个不是前缀码（）。A（ 00， 01， 10， 11） B （ 0，1， 00， 11） C （0， 10， 110， 111） D （1， 01，000， 001）15下面几个符号串编码集合中，不是前缀编码的是（）。A 0,10,110,1111B 1
4、1,10,001,101,0001C 00,010,0110,1000D b,c,aa,ac,aba,abb,abc二、填空题1设 F 是由 T1,T2,T3 三棵树组成的森林, 与 F 对应的二叉树为B, 已知T1,T2,T3的结点数分别为 n1,n2 和 n3 则二叉树B 的左子树中有_(1)_ 个结点，右子树中有2一棵树T 中，包括一个度为1 的结点，两个度为2 的结点，三个度为为 4 的结点和若干叶子结点，则T 的叶结点数为 _。_(2)_ 个结点。3 的结点，四个度3 每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，对称序列是FEBGCHD，则它
5、的后序序列是_(1)_ 。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是_(2)_ 。4利用树的孩子兄弟表示法存储，可以将一棵树转换为_。5一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：_。6设 y 指向二叉线索树的一叶子，x 指向一待插入结点，现x 作为 y 的左孩子插入，树中标志域为ltag和 rtag ，并规定标志为1 是线索，则下面的一段算法将x 插入并修改相应的线索，试补充完整：(lchild,rchild分别代表左，右孩子)x.ltag:= (1)_; x.lchild:= (2)_; y.ltag:= (3)_;y.lchild:= (4)_; x.rtag
6、:= (5)_; x.rchild:= (6)_;IF (x.lchildNIL)AND(xlchild.rtag=1) THEN x.lchild.rchild:=(7)_;7哈夫曼树是_。8若以 4 ， 5， 6， 7， 8 作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_。9有数据 WG=7， 19， 2，6， 32， 3， 21， 10 ，则所建 Huffman 树的树高是 _(1)_ ，带权路径长度 WPL为 _(2)_ 。10有一份电文中共使用6 个字符 :a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为 _(1)_ ，字符 c 的编码是 _(2)_ 。11设 n0 为哈夫曼树的叶子结点数目，则该哈夫曼树共有_个结点。
