第六章 树
更新时间:2024-04-11 05:07:01 阅读量: 综合文库 文档下载
- 第六章光夜结局是谁推荐度:
- 相关推荐
第六章 树
一、选择题
1.对于一棵具有n个结点的树,该树中所有结点的度数之和为________。 A. n-1 B. n C. n+1 D. (n+1)/2
2.设结点A 有3个兄弟结点且结点B为结点A的双亲结点,则结点B 的度数为________。
A. 3 B. 4 C.5 D. 1 3.根据二叉树的定义可知二叉树共有________种不同的形态。 A. 4 B. 5 C. 6 D. 7 4.在一棵树中,________没有前驱结点。
A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点
5.设某棵二叉树中只有度数为0和度数为2的结点,且度数为0的结点数为 n,则这棵二叉中共有________个结点。
A. 2n B.n+1 C. 2n-1 D.2n+1
6.设某棵二叉树的高度为10,则该二叉树上叶子结点最多有________。 A. 20 B.256 C. 512 D.1024 7. 一棵具有5层满二叉树中结点总数为________。 A. 31 B. 32 C.33 D.16 8. 如下图所示的4 棵二叉树,_______不是完全二叉树。
9.具有65个结点的完全二叉树的高度为________。 (根的层次号为1)
A.8 B.7 C.6 D.5
10.把一棵深度4的左单支二叉树改造成完全二叉树时,要增添 个空结点。
A.10
B.8
C.6
D.4
11.设按照从上到下、从左到右的顺序从 1 开始对完全二叉树进行顺序编号,则编号为 i结点的左孩子结点的编号为________。
A. 2i+1 B. 2i C. i/2 D. 2i-1
12.首先访问结点的左子树,然后访问该结点,最后访问结点的右子树,这种遍历称为________。
A.前序遍历 B.后序遍历 C.中序遍历 D.层次遍历 13.已知一棵二叉树的前序遍历结果为 ABCDEF ,中序遍历结果为 CBAEDF,则后序遍历的结果为________。
A.CBEFDA B. FEDCBA C. CBEDFA D. 不定
14.已知某二叉树的后序遍历序列是 dabec, 中序遍历序列是 debac,它的前序遍历序列是________。
A.acbed B.decab C.deabc D.cedba 15.某二叉树T有n个结点,设按某种遍历顺序对T中的每个结点进行编号,编号值为1,2,…,n且有如下性质:T中任一结点V,其编号等于左子树上的最小编号减1,而V的右子树 的结点中,其最小编号等于V左子树上结点的最大编号加1。这时按 编号。
A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次遍历序列 16.某非空二叉树的前序序列和后序序列正好相反,则二叉树一定是________的二叉树。
A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子 17.由前序序列和中序序列________唯一确定一棵二叉树。 A. 能 B. 不能 C. 不一定
18.树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是________。
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对
19.对于一棵具有n个结点的二叉树,对应二叉链表中指针总数为 2n 个,其中________ 个用于指向孩子结点。
A. n-1 B. n C. n+1 D.n-2
20.设F是由T1、T2和T3 三棵树组成的森林,与F对应的二叉树为B,T1、T2 和T3 的结点数分别为N1、N2和N3,则二叉树B的根结点的左子树的结点数为________。
A. N1-1 B. N2-1 C. N2+N3 D. N1+N3
21. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为 __ ___。
A. 23 B. 37 C. 44 D.46 22.n 个权构成一棵Huffman树,其结点总数为__________。
A.2n-1 B.2n C.2n+1 D. 不确定
二、填空题
1. 在一棵二叉树中,度为0的结点的个数为n0 ,度为2的结点的个数为n2 ,则:n0 = 。
2.结点数为7的二叉树的高度最矮是_______ ,最高是_______ 。 3.给定二叉树的结点数,要使树高为最大,那么该树应该是_______形状。 4.给定二叉树的结点数,要使树高为最矮,那么该树应该是_______形状。 5.如果一棵满二叉树的深度为7,那么它共有_______个结点,有 _______个叶结点。
6.深度为5的二叉树,至多有_______个结点。
7.深度为k 的完全二叉树至少有_______个结点,至多有_______个结点。 8.在树形结构中,树根结点没有前驱结点,其余每个结点有且只有_______ 个前驱结点,叶子结点没有后继结点,其余每个结点的后继结点可以有_______个。 9.设二叉树中度数为0 的结点数为50,度数为1 的结点数为30,则该二叉树中总共有_______个结点。
10.设二叉树中结点的两个指针域分别为lchild 和rchild,则判断指针变量p 所指向的结点为叶子结点的条件是___________________________。
11. 在n 个带权叶子结点构造出的所有二叉树中,带权路径长度最小的二叉树称为________。
12.设一棵完全二叉树中有21个结点,如果按照从上到下、从左到右的顺序从1 开始顺序编号,则编号为8 的双亲结点的编号是_____,编号为8 的左孩子结点的编号是_______。
13. 设哈夫曼树中共有n 个结点,则该哈夫曼树中有_____个度数为1 的结点。 14. 以数据集{4,5,6,7,10,12,18}为结点权值所构造的Huffman 树为____,其带权路径长度为_________ 。
15.设一棵Huffman 树有6 个叶结点,权值分别为3、4、7、14、15、20,则根 结点的权值是_______。
16.设用于通信的电文仅由8 个字母组成,字母在电文中出现的频率分别为7、19、2、6、32、3、21、10,根据这些频率作为权值构造哈夫曼树,则这棵哈夫曼树的高度为_________。
三、综合应用题
1. 已知一棵树的边的集合表示为{(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G),(D,H),(D,I),(D,J),(A,B),(A,C),(A,D)}。画出这棵树并回答下面问题:
(1) 树的根节点是哪个,哪些是叶子结点,哪些是非终端结点。 (2) 树的深度是多少,各个结点的层数是多少。
(3) 对于G结点,它的双亲结点、祖先结点、孩子结点、子孙结点、兄弟和堂兄弟分别是哪些结点。
2.设二叉树如下图所示,分别写出它的先序遍历、中序遍历、后序遍历序列。
J D H I B C A E F G 3.设一棵二叉树的先序遍历序列为abcde,中序遍历序列为badce,请画出对应
的二叉树,并写出对应后序遍历序列。
4.某二叉树结点的中序序列为HBCDEFG,后序序列为BDCHFGE,请据此画出该二叉树,再给该树加上中序线索。
5.请按照孩子-兄弟表示法,将下图所示树转化为二叉树。
G E F B C D A 6.若7个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树(请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造),计算出带权路径长度WPL及该树的结点总数。
7.在一段文字中,共出现a、b、c、d、e、f六种字符,每种字符出现的频率分别为7,9,12,22,23,27。请回答下列问题: (1)什么是哈夫曼树?
(2)根据题目所给频率值,画出相应的哈夫曼树。 (3)给出各个字符对应的哈夫曼编码。 (4)该段文字经过哈夫曼编码后,长度是多少。
四、算法设计题
1. 设计一个求结点x在二叉树中的双亲结点的算法。 2. 设计判断两个二叉树是否相同的算法。 3. 设计计算二叉树中所有结点值之和的算法。 4. 设计求二叉树中值为x的结点所在的层号的算法。
正在阅读:
第六章 树04-11
2019年南京林业大学理学院824有机化学考研冲刺五套模拟题05-02
2012考研英语(一)阅读翻译及解析07-28
《针灸学》复习题及答案10-21
三环与四环立交桥监理细则07-03
上市工作会议政办通报04-12
老人健康智能手环可行性分析报告12-29
EPB线束工艺流程图05-10
国际结算论文12-19
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 机械设备操作规程
- 圆柱的体积说课稿教学设计
- 京山温泉新区项目建议书
- 《藏传净土法》考试复习范围100题答案
- 管路流体流动阻力的测定 数据处理
- 2015秋大学计算机期末理论练习题
- 百度快照不更新的原因及百度快照突然或频繁回档原因
- 2018年新版人教版初中生物中考生物总复习提纲
- 2013年全国中考数学(100套)选择填空解答压轴题分类解析汇编 专
- 教育测量与评价试题(终极版本)
- 基坑钢支撑支护总结
- 控制工程(MATLAB)实验
- 康佳彩电通病及维修经验大集合
- 寺院上供仪轨大全
- 36年坚守与被遗忘的国家任务
- 2015年高中英语疑难探究Idontthink的否定转移素材
- 物料搬运系统设计论文 - 图文
- 苏教版高中化学选修四3.2《溶液的酸碱性、pH的简单计算》参考教
- 第七章 线性变换
- 如何以先进典为榜样检查自身不足3篇