




已阅读5页,还剩4页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
习题五参考答案备注: 红色字体标明的是与书本内容有改动的内容 一、选择题1对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行( B )遍历操作相同。A 先根 B. 中根 C. 后根 D. 层次2在哈夫曼树中,任何一个结点它的度都是( C )。B 0或1 B. 1或2 C. 0或2 D. 0或1或23对一棵深度为h的二叉树,其结点的个数最多为( D )。A 2h B. 2h-1 C. 2h-1 D. 2h-14一棵非空二叉树的先根遍历与中根遍历正好相同,则该二叉树满足( A )A 所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树5一棵非空二叉树的先根遍历与中根遍历正好相反,则该二叉树满足( B )B 所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树6假设一棵二叉树中度为1的结点个数为5,度为2的结点个数为3,则这棵二叉树的叶结点的个数是( C )A2 B. 3 C. 4 D. 57若某棵二叉树的先根遍历序列为ABCDEF,中根遍历序列为CBDAEF,则这棵二叉树的后根遍历序列为( B )。AFEDCBA B. CDBFEA C. CDBEFA D. DCBEFA8若某棵二叉树的后根遍历序列为DBEFCA,中根遍历序列为DBAECF,则这棵二叉树的先根遍历序列为( B )。AABCDEF B. ABDCEF C. ABCDFE D. ABDECF9根据以权值为2,5,7,9,12构造的哈夫曼树所构造的哈夫曼编码中最大的长度为( B )A2 B. 3 C. 4 D. 510在有n个结点的二叉树的二叉链表存储结构中有( C )个空的指针域。An-1 B. n C. n+1 D. 0二、填空题1. 在一棵度为m的树中,若度为1的结点有n1个,度为2的结点有n2个,度为m的结点有nm个,则这棵树中的叶结点的个数为 1+n2+2n3+3n4+(m-1)nm 。2. 一棵具有n个结点的二叉树,其深度最多为 n ,最少为 log2n+1 。3. 一棵具有100个结点的完全二叉树,其叶结点的个数为 50 。4. 以5,9,12,13,20,30为叶结点的权值所构造的哈夫曼树的带权路径长度是 217 。5. 有m个叶结点的哈夫曼树中,结点的总数是 2m-1 。6. 若一棵完全二叉树的第4层(根结点在第0层)有7个结点,则这棵完全二叉树的结点总数是 11 。7. 在深度为k的完全二叉树中至少有 k个结点,至多有 2k-1 个结点。8. 对一棵树转换成的二叉树进行先根遍历所得的遍历序列为ABCDEFGH,则对这棵树进行先根遍历所得的遍历序列为 ABCDEFGH 。9. 二叉树常用的存储结构是 二叉链式存储结构 ,树常用的存储结构是 孩子兄弟链表存储结构 。10. 对森林进行后根遍历操作等同于从左到右对森林中的每一棵树进行 后根 遍历操作,并且对森林的后根遍历序列与对森林所对应的二叉树的 中根 遍历序列相同。四、算法设计题1. 编写一个基于二叉树类的统计叶结点数目的成员函数。参考答案:public int countLeafNode(BiTreeNode T) / 统计叶结点数目int count = 0;if (T != null) if (T.getLchild() = null & T.getRchild() = null) +count;/ 叶结点数增1 else count += countLeafNode(T.getLchild(); / 加上左子树上叶结点数count += countLeafNode(T.getRchild();/ 加上右子树上的叶结点数return count;2. 编写一个基于二叉树类的查找二叉树结点的成员函数。参考答案: public BiTreeNode searchNode(BiTreeNode T,Object x) / 在以T为根结点的二叉树中查找值为x的结点,若找到,则返回该结点,否则返回空值 if (T != null) if (T.getData().equals(x)return T;else BiTreeNode lresult= searchNode(T.getLchild(),x); / 在左子树上查找return (lresult!=null?lresult:searchNode(T.getRchild(),x) ;/ 若左子树上没找到,则到右子树上找 return null;3. 编写算法求一棵二叉树的根结点root到一个指定结点p之间的路径并输出。参考答案:/ 求根结点到指定结点的路径过程中,采用了后跟遍历的思想,最终求得的路径保存在一个链栈中,其中根结点处于栈顶位置,指定结点处于栈底位置。/下面用到的二叉树结点类BiTreeNode在书中第5章中已给出public LinkStack getPath(BiTreeNode root, BiTreeNode p) BiTreeNode T = root;LinkStack S = new LinkStack();/ 构造链栈if (T != null) S.push(T); / 根结点进栈Boolean flag;/ 访问标记BiTreeNode q = null;/ q指向刚被访问的结点while (!S.isEmpty() while (S.peek() != null)/ 将栈顶结点的所有左孩子结点入栈S.push(BiTreeNode) S.peek().getLchild();S.pop(); / 空结点退栈while (!S.isEmpty() T = (BiTreeNode) S.peek();/ 查看栈顶元素if (T.getRchild() = null | T.getRchild() = q) if (T.equals(p) / 对栈S进行倒置,以保证根结点处于栈顶位置LinkStack S2 = new LinkStack();while (!S.isEmpty()S2.push(S.pop();return S2;S.pop();/ 移除栈顶元素q = T;/ q指向刚被访问的结点flag = true;/ 设置访问标记 else S.push(T.getRchild();/ 右孩子结点入栈flag = false;/ 设置未被访问标记if (!flag)break;return null;4. 编写算法统计树(基于孩子兄弟链表存储结构)的叶子数目。参考答案:/下面用到的孩子兄弟链表结构中的结点类CSTreeNode在书中第5章中已给出public int countLeafNode(CSTreeNode T) int count = 0;if (T != null) if (T.getFirstchild() = null) +count;/ 叶结点数增1else count += countLeafNode(T.getFirstchild(); / 加上孩子上叶结点数 count += countLeafNode(T.getNextsibling();/ 加上兄弟上叶结点数return count;5. 编写算法计算树(基于孩子兄弟链表存储结构)的深度。参考答案:public int treeDepth(CSTreeNode T) if (T != null) int h1= treeDepth(T.getFirstchild();int h2= treeDepth(T.getNextsibling(); return h1+1h2?h1+1:h2;return 0;四、上机实践题1. 编写一个程序实现:先建立两棵以二叉链表存储结构表示的二叉树,然后判断这两棵二叉树是否相等并输出测试结果。参考答案:package ch05Exercise;import ch05.BiTreeNode;/教材第5章中有此类的描述public class Exercise5_4_1 public boolean isEqual(BiTreeNode T1, BiTreeNode T2) /判断两棵树是否相等,若相等则返回true,否则返回falseif (T1 = null & T2 = null)/ 同时为空return true;if (T1 != null & T2 != null) / 同时非空进行比较if (T1.getData().equals(T2.getData()/ 根结点数据元素是否相等if (isEqual(T1.getLchild(), T2.getLchild() / 左子树是否相等 if (isEqual(T1.getRchild(), T2.getRchild()/ 右子树是否相等return true;return false; /测试主方法public static void main(String args) / 创建根结点为T1的二叉树BiTreeNode D1 = new BiTreeNode(D);BiTreeNode G1 = new BiTreeNode(G);BiTreeNode H1 = new BiTreeNode(H);BiTreeNode E1 = new BiTreeNode(E, G1, null);BiTreeNode B1 = new BiTreeNode(B, D1, E1);BiTreeNode F1 = new BiTreeNode(F, null, H1);BiTreeNode C1 = new BiTreeNode(C, F1, null);BiTreeNode T1 = new BiTreeNode(A, B1, C1);/ 创建根结点为T2的二叉树BiTreeNode D2 = new BiTreeNode(D);BiTreeNode G2 = new BiTreeNode(G);BiTreeNode H2= new BiTreeNode(H);BiTreeNode E2 = new BiTreeNode(E, G2, null);BiTreeNode B2 = new BiTreeNode(B, D2, E2);BiTreeNode F2 = new BiTreeNode(F, null, H2);BiTreeNode C2 = new BiTreeNode(C, F2, null);BiTreeNode T2 = new BiTreeNode(A, B2, C2); / 创建根结点为T3的二叉树BiTreeNode E3= new BiTreeNode(E);BiTreeNode F3 = new BiTreeNode(F);BiTreeNode D3= new BiTreeNode(D,F3,null);BiTreeNode B3 = new BiTreeNode(B, null, D3);BiTreeNode C3 = new BiTreeNode(C, null, E3);BiTreeNode T3 = new BiTreeNode(A, B3, C3); Exercise5_4_1 e = new Exercise5_4_1();if (e.isEqual(T1, T2)System.out.println(T1、T2两棵二叉树相等!);elseSystem.out.println(T1、T2两棵二叉树不相等!); if (e.isEqual(T1, T3)System.out.println(T1、T3两棵二叉树相等!);elseSystem.out.println(T1、T3两棵二叉树不相等!);运行结果:2编写一个程序实现:先建立一棵以孩子兄弟链表存储结构表示的树,然后输出这棵树的先根遍历序列和后根遍历序列。参考答案:package ch05Exercise;import ch05.CSTreeNode; /教材第5章中有此类的描述public class Exercise5_4_2 /创建一棵树 public CSTreeNode createBiTree() CSTreeNode D = new CSTreeNode(D);CSTreeNode E = new CSTreeNode(E);CSTreeNode C = new CSTreeNode(C, D, E);CSTreeNode B = new CSTreeNode(B, null, C);CSTreeNode A = new CSTreeNode(A, B, null);return A;/ 先根遍历树的递归算法public void preRootTraverse(CSTreeNode T) if (T != null) System.out.print(T.getData(); / 访问根结点preRootTraverse(T.getFirstchild();/ 访问孩子结点preRootTraverse(T.getNextsibling();/ 访问兄弟结点/ 后根遍历树的递归算法public void postRootTraverse(CSTreeNode T) if (T != null) postRootTraverse(T.getFirstchild();/ 访问孩子结点System.out.print(T.getData(); / 访问根结点postRootTraverse(T.getNextsibling();/ 访问兄弟结点public static void main(String args) Exercise5_4_2 e = new Exercise5_4_2();CSTreeNode root=e.createBiTree(); / 调试先根遍历System.out.println(该树的先根遍历为:);e.preRootTraverse(root);/ 调试后根遍历System.out.println(n该树的后根遍历为:);e.postRootTraverse(root);运行结果:3编写一个基于构造哈夫曼树和哈夫曼编码的HuffmanCoding类的测试程序,使其实现先建立一棵哈夫曼树,然后再根据这棵哈夫曼树来构造并输出其哈夫曼编码。参考答案:package ch05Exercise;import ch05.HuffmanNode; /教材第5章中有此类的描述/构造哈夫曼树和哈夫曼编码的HuffmanCoding类class HuffmanTree / 求赫夫曼编码的算法,W存放n个字符的权值(均0)public int huffmanCoding(int W) int n = W.length;/ 字符个数int m = 2 * n - 1;/ 赫夫曼树的结点数HuffmanNode HN = new HuffmanNodem;int i;for (i = 0; i n; i+)HNi = new HuffmanNode(Wi);/ 构造n个具有权值的结点for (i = n; i m; i+) / 建赫夫曼树/ 在HN0.i - 1选择不在赫夫曼树中且weight最小的两个结点min1和min2HuffmanNode min1 = selectMin(HN, i - 1);min1.setFlag(1);HuffmanNode min2 = selectMin(HN, i - 1);min2.setFlag(1);/ 构造min1和min2的父结点,并修改且父结点的权值HNi = new HuffmanNode();min1.setParent(HNi);min2.setParent(HNi);HNi.setLchild(min1);HNi.setRchild(min2);HNi.setWeight(min1.getWeight() + min2.getWeight();/ 从叶子到根逆向求每个字符的赫夫曼编码int HuffCode = new intnn;/ 分配n个字符编码存储空间for (int j = 0; j n; j+) int start = n - 1;/ 编码的开始位置,初始化为数组的结尾for (HuffmanNode c = HNj, p = c.getParent(); p != null; c = p, p = p.getParent()/ 从叶子到根逆向求编码if (p.getLchild().equals(c)/ 左孩子编码为0HuffCodejstart- = 0;else/ 右孩子编码为1HuffCodejsta
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- T/CNSS 004-2020加速康复外科(ERAS)围手术期营养诊疗规范
- 2025重庆綦江区三江街道公开招聘公益性岗位2人备考考试题库附答案解析
- 2025年宿州灵璧师范学校秋季学期公开招聘教师备考考试题库附答案解析
- 2025下半年浙江金华市兰溪市市属国企人才引进招聘19人备考考试题库附答案解析
- 2025年安徽建筑大学管理及教学助理招聘11名备考考试题库附答案解析
- 2025江西天然气管道设备安装工程有限公司面向江投集团内部招聘2人备考考试题库附答案解析
- 2025上海市崇明区交通运输事业发展中心 公开招聘非在编人员备考考试题库附答案解析
- 2025年泉州发展集团有限公司(第二批)人才引进招聘29人备考考试题库附答案解析
- 有机农业赢销之道
- 阅读的魅力与价值
- 2025年“学宪法、讲宪法”主题活动知识竞赛题库及答案
- 2024年毕节威宁自治县招聘城市社区工作者真题
- GB/T 15234-2025塑料平托盘
- 山东省汽车维修工时定额(T-SDAMTIA 0001-2023)
- GB/T 4170-2006塑料注射模零件技术条件
- GB/T 12363-2021锻件功能分类
- 水调歌头-公开课教学设计 省赛一等奖
- 《番茄工作法图解》课件
- 报价单模板及范文(通用十二篇)
- 蒂森克虏伯电梯MC2-C调试介绍
- 苏教版三年级数学上册《间隔排列》作业纸(大组教研)
评论
0/150
提交评论