树和二叉树习题.doc

《树和二叉树习题.doc》由会员分享，可在线阅读，更多相关《树和二叉树习题.doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除第6章 树和二叉树一、选择题1算术表达式a+b*（c+d/e）转为后缀表达式后为（ B ）Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+2. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ C ）A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ D ）A5 B6 C7 D84. 在下述结

2、论中，正确的是（ D ）只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D5. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ A ）Am-n Bm-n-1 Cn+1 D条件不足，无法确定 6若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）A9 B11 C15 D不确定 7设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（

3、D ）。AM1 BM1+M2 CM3 DM2+M38一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E ）A 250 B 500 C254 D505 E以上答案都不对(501) 9. 有关二叉树下列说法正确的是（ B ）A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为210二叉树的第I层上最多含有结点数为（ c ）A2I B 2I-1-1 C 2I-1 D2I -111. 一个具有1025个结点的二叉树的高h为（ C ）A11 B10 C11至1025之间 D10至1024之间12一棵二叉树高度为h,所有结点的度或为0，或

4、为2，则这棵二叉树最少有( B )结点A2h B2h-1 C2h+1 Dh+1 13. 一棵树高为K的完全二叉树至少有（ C ）个结点A2k 1 B. 2k-1 1 C. 2k-1 D. 2k14对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历15一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B ）ACABDEFG BABCDEFG CDACEFBG DADCFEG 16已知一棵二叉树的前序遍历结

5、果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。ACBEFDA B FEDCBA C CBEDFA D不定 17对于前序遍历与中序遍历结果相同的二叉树为（F）;对于前序遍历和后序遍历结果相同的二叉树为（B）。A一般二叉树 B只有根结点的二叉树 C根结点无左孩子的二叉树 D根结点无右孩子的二叉树 E所有结点只有左子数的二叉树 F所有结点只有右子树的二叉树18在下列情况中，可称为二叉树的是（ B ） A每个结点至多有两棵子树的树 B. 哈夫曼树 C每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E以上答案都不对 19n个结点的线索二叉树上含有的线索数为（

6、C ）A2n Bnl Cnl Dn 20由3 个结点可以构造出多少种不同的二叉树？（ D ）A2 B3 C4 D5 21. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 Al.n中时，数组中第i个结点的左孩子为（ A ）AA2i(2i=n) B. A2i+1(2i+1= n) CAi/2 D无法确定二、填空题1二叉树由_ 根节点_，_左子树_，_右子树_三个基本单元组成。2中缀式a+b*3+4*（c-d）对应的前缀式为_+a*b3*4-cd_，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_18_。3具有256个结点的完全二叉树的深度

7、为_9_。4已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_12_个叶子结点。5深度为k的完全二叉树至少有_2(k-1)_个结点，至多有_(2k)-1_个结点。6设有N个结点的完全二叉树顺序存放在向量A1:N中，其下标值最大的分支结点为_N/2_。7一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是_ 2(k-2)+1 _；编号是i的结点所在的层次号是_log2 i|+1 _（log2 i|表示向上取整（根所在的层次号规定为1层）。8具有N个结点的二叉树，采用二叉链表存储，共有_N+1_个空链

8、域。三、应用题1将算术表达式（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。前序序列：*+ab*c+def+gh二叉树如下图所示：2已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？ 答案：结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。3将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）答案：4设某二叉树的前序遍历序列为:ABCDEFGHI，中序遍历序列为:BCAEDGHFI：试画出该二叉树；答案：后序：CBEHGIFDA 5一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G后序序列 ：_ E F D B _ J I H _ A 6给定集合15,3,14,2,6,9,16,17(1)（3分）构造相应的huffman树：(2) (2分)计算它的带权路径长度：(3)（3分)写出它的huffman编码：(4)（3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。【精品文档】第 3 页