第6章 树和二叉树_作业.docx

《第6章 树和二叉树_作业.docx》由会员分享，可在线阅读，更多相关《第6章 树和二叉树_作业.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章 树和二叉树 1一、选择题1. 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )A-A+B*C/DE B-A+B*CD/EC-+*ABC/DE D-+A*BC/DE2. 在下述结论中，正确的是（）只有一个结点的二叉树的度为0; 二叉树的度为2；二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A B C D3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（）A5 B6 C7 D84. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n

2、,森林F中第一棵树的结点个数是（）Am-n Bm-n-1 Cn+1 D条件不足，无法确定5. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A9 B11 C15 D不确定6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。AM1 BM1+M2 CM3 DM2+M37.有关二叉树下列说法正确的是（）A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为28. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。A 250

3、 B 500 C254 D505 E以上答案都不对9. 具有10个叶结点的二叉树中有（）个度为2的结点。A8 B9 C10 Dll10. 深度为h的满m叉树的第k层有（）个结点。(1=k=h)Amk-1 Bmk-1 Cmh-1 Dmh-111. 设二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树满足的条件是（）A、空或只有一个结点 B、完全二叉树C、二叉排序树 D、高度等于其结点数12. 已知一棵有2011个结点的树,其叶结点个数为116，该树对应的二叉树无右孩子的结点个数为（）A115 B116 C1895 Dl896题号123456789101112答案二、判断题1. 二叉树是度为2

4、的有序树。2.完全二叉树一定存在度为1的结点。3.深度为K的二叉树中结点总数2k-1。4. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息。5. 二叉树的遍历结果不是唯一的。6. 若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必定是该子树的前序中历序列中的最后一个结点7. 已知一棵二叉树的后序和前序序列，可以唯一确定这个二叉树题号1234567答案三、填空题1.二叉树由_，_，_三个基本单元组成。2.在二叉树中，指针p所指结点为叶子结点的条件是_。3. 二叉树中某一结点左子树的深度减去右子树的深度称为该结点的_。4. 深度为k的完全二叉树至少有_个结点，至多有_个结点。5.

5、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是_。6. 设高度为h 的二叉树上只有度为0 和度为2 的节点，问该二叉树的节点数可能的最大值为_，最小值为_。7. 一棵共有n个结点的树，其中所有分支结点的度均为K，则该树中叶子结点的个数为_。8. 一棵完全二叉树有200 个结点，则度为1 的结点有_个。度为0 的结点有_个。度为2 的结点有_个。四、应用题1. 任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）个度为2，其余度为1。2. 已知A1.N是一棵顺序存储的完全二叉树，如何求出Ai和Aj的最近的共同祖先？3. 试证明:同一棵二叉树的所有叶子结点

6、，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如前序abc，后序bca，对称序bac。4. 由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是否也能唯一的建立二叉树，不能则说明理由，若能对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。五、算法设计题1. 二叉树采用二叉链表存储：（1）写一个建立二叉树的算法。（2）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。（3）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。（4）写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。2. 在二叉树中查找值为x的结点，试编写算法（用C语言）打印值为x的结点的所有祖先，假设值为x的结点不多于一个，最后试分析该算法的时间复杂度。