第4课 树和二叉树
更新时间:2024-03-24 19:53:01 阅读量: 综合文库 文档下载
- 第4课日本明治维新教案推荐度:
- 相关推荐
第四课 树和二叉树
一、选择题
1.已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为( )。
A.-A+B*C/DE B.-A+B*CD/E C.-+*ABC/DE D.-+A*BC/DE 参考答案:D
2.一棵完全二叉树上有1001个结点,其中叶子结点的个数是( )。
A.250 B.500 C.254 D.505 E.以上答案都不对 参考答案:E
3.设树T的度为4,其中度为1、2、3和4的结点个数分别为4、2、1、1,则T中的叶子数为( )。
A.5 B.6 C.7 D.8 参考答案:D
4.在下述结论中,正确的是( )。
①只有一个结点的二叉树的度为0; ②二叉树的度为2;
③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.②③④ C.②④ D.①④ 参考答案:D
5.设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是( )。
A.m-n B.m-n-1 C.n+1 D.条件不足,无法确定 参考答案:A
6.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是( )。
A.9 B.11 C.15 D.不确定 参考答案:B
7.具有10个叶结点的二叉树中有( )个度为2的结点。
A.8 B.9 C.10 D.11 参考答案:B
8.下述编码中不是前缀码的是( )。
A.(00,01,10,11) B.(0,1,00,11) C.(0,10,110,111) D.(1,01,000,001) 参考答案:B
9.设给定权值总数有n个,其哈夫曼二叉树的结点总数为( )。
A.不确定 B.2n C.2n+1 D.2n-1 参考答案:D
10.有关二叉树下列说法正确的是( )。
A.二叉树的度为2 B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2 参考答案:B
11.二叉树的第i层上最多含有结点数为( )。
A.2i B.2i-1-1 C.2i-1 D.2i -1 参考答案:C
12.一个具有1025个结点的二叉树的高h为( )。
A.11 B.10 C.11至1025之间 D.10至1024之间 参考答案:C
13.对于有n个结点的二叉树,其高度为( )。
A.nlog2n B.log2n C.?log2n?+1 D.不确定 参考答案:D
14.一棵具有n个结点的完全二叉树的树高度(深度)是( )。
A.?logn?+1 B.logn+1 C.?logn? D.logn-1 参考答案:A
15.在一棵高度为k的满二叉树中,结点总数为( )。
A.2k-1 B.2k C.2k-1 D.?log2k?+1 参考答案:C
16.高度为k的二叉树最大的结点数为( )。
A.2k B.2k-1 C.2k-1 D.2k-1-1 参考答案:C
17.一棵树高为k的完全二叉树至少有( )个结点。
A.2k–1 B.2k-1–1 C.2k-1 D.2k 参考答案:C
18.将有关二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高度()。
A.4 B.5 C.6 D.7 参考答案:C
19.利用二叉链表存储树,则根结点的右指针是( )。
A.指向最左孩子 B.指向最右孩子 C.空 D.非空 参考答案:C
20.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用( )次序的遍历实现编号。
A.先序 B.中序 C.后序 D.从根开始按层次遍历 参考答案:C
21.树的后根遍历序列等同于该树对应的二叉树的( )。
A.先序序列 B.中序序列 C.后序序列
参考答案:B
22.下述二叉树中,( )满足从任一结点出发到根的路径上所经过的结点序列按其关键字有序。
A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆 参考答案:D
23.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是( )。
A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCFEG 参考答案:B 24.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为( )。
A.CBEFDA B.FEDCBA C.CBEDFA D.不定 参考答案:A
25.如果T2是由有序树T转换而来的二叉树,那么T中结点的后序就是T2中结点的( )。
A.先序 B.中序 C.后序 D.层序 参考答案:B
26.若二叉树的先序遍历为EFHIGJK,中序遍历为HFIEJKG,则该二叉树根的右子树的根是( )。
A.E B.F C.G D.H 参考答案:C
27.将一棵树T转换为孩子兄弟链表表示的二叉树H,则T的后序遍历序列与H的( )序列相同。
A.前序遍历 B.中序遍历 C.后序遍历 参考答案:B
28.下面的说法中正确的是( )。
(1)任何一棵二叉树的叶子结点在三种遍历中的相对次序不变; (2)按二叉树定义,具有三个结点的二叉树共有6种。
A.(1)(2) B.(1) C.(2) D.(1)、(2)都错 参考答案:B
29.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足( )。
A.所有的结点均无左孩子 B.所有的结点均无右孩子 C.只有一个叶子结点 D.是任意一棵二叉树 参考答案:C
30.在二叉树结点的先序序列,中序序列和后序序列中,所有叶子结点的先后顺序( )
A.都不相同 B.完全相同 C.先序和中序相同,而与后序不同 D.中序和后序相同,而与先序不同 参考答案:B
31.某二叉树的前序序列和后序序列正好相反,则该二叉树一定是( )的二叉树。
A.空或只有一个结点 B.任一结点无左子树 C.高度等于其结点数 D.任一结点无右子树 参考答案:C
32.由3个结点可以构造出( )种不同的二叉树。
A.2 B.3 C.4 D.5 参考答案:D
33.一棵左子树为空的二叉树在先序线索化后,其中空的链域的个数是:( )。
A.不确定 B.0 C.1 D.2 参考答案:D
34.一棵左右子树均不空的二叉树在先序线索化后,其中空的链域的个数是:( )。
A.0 B.1 C.2 D.不确定 参考答案:C
35.若X是二叉中序线索树中一个有左孩子的结点,且X不为根,则X的前驱为( )。
A.X的双亲 B.X的右子树中最左的结点
C.X的左子树中最右结点 D.X的左子树中最右叶结点 参考答案:C
36.引入二叉线索树的目的是( )。
A.加快查找结点的前驱或后继的速度 B.为了能在二叉树中方便的进行插入与删除 C.为了能方便的找到双亲 D.使二叉树的遍历结果唯一 参考答案:A
37.线索二叉树是一种( )结构。
A.逻辑 B.逻辑和存储 C.物理 D.线性 参考答案:C
38.n个结点的线索二叉树上含有的线索数为( )。
A.2n B.n-1 C.n+1 D.n 参考答案:C
39.( )的遍历仍需要栈的支持。
A.前序线索树 B.中序线索树 C.后序线索树 参考答案:C
40.二叉树在线索后,仍不能有效求解的问题是( )。
A.先序线索二叉树中求先序后继 B.中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D.后序线索二叉树中求后序后继 参考答案:D
41.由3个结点可以构造出( )种不同的有序树。
A.2 B.3 C.4 D.5 参考答案:A
二、应用题
1.设有一棵算术表达式树,用什么方法可以对该树所表示的表达式求值?
参考答案:
方法有二。一是对该算术表达式(二叉树)进行后序遍历,得到表达式的后序遍历序列,再按后缀表达式求值;二是递归求出左子树表达式的值,再递归求出右子树表达式的值,最后按根结点运算符(+、-、*、/ 等)进行最后求值。
2.将算术表达式((a+b)+c*(d+e)+f)*(g+h)转化为二叉树。 参考答案:
*
++ +fgh +*
a+bc
de
3.一棵有n(n>0)个结点的d度树,若用多重链表表示,树中每个结点都有d个链域,则在表示该树的多重链表中有多少个空链域?为什么? 参考答案:
n(n>0)个结点的d度树共有nd个链域,除根结点外,每个结点均有一个指针所指,故该树的空链域有nd-(n-1)=n(d-1)+1个。
4.试证明一棵二叉树中的结点的度或为0或为2,则二叉树的枝数为2(n0-1),其中n0是度为0的结点的个数。 参考答案:
设二叉树度为0和2的结点数及总的结点数分别为n0,n2和n,则n=n0+n2 (1)
再设二叉树的分支数为B,除根结点外,每个结点都有一个分支所指,则n=B+1 (2)
度为零的结点是叶子,没有分支,而度为2的结点有两个分支,因此(2)式可写为n=2*n2+1 (3) 由(1)、(3)得n2=n0-1,代入(1),并由(1)和(2)得B=2*(n0-1)。
5.证明任一结点个数为n的二叉树的高度至少为O(log2n)。 参考答案:
最低高度二叉树的特点是,除最下层结点个数不满外,其余各层的结点数都应达到各层的最大值。设n个结点的二叉树的最低高度是h,则n应满足2h-1 6.有n个结点并且其高度为n的二叉树的数目是多少? 参考答案:2n-1 7.已知完全二叉树的第七层有10个叶子结点,则整个二叉树的结点数最多是多少? 参考答案:235。 8.高度为10的二叉树,其结点最多可能为多少? 参考答案:1023。
正在阅读:
第4课 树和二叉树03-24
护士试用期个人工作总结范文三篇09-04
3-1金属的化学性质(第一课时))08-19
2019年黑龙江省绥化市中考数学试卷11-18
正构烷烃管道施工方案06-26
我的自传作文500字02-04
人教版三年级上册数学期末命题试卷05-06
抗击疫情先进个人事迹材料 抗击疫情先进典型事迹材料05-04
义务教育入学新政02-21
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 四川省建筑工程施工许可管理办法实施细则
- 2011秋太平小学教研工作计划
- 农村中学生体育运动兴趣的激发和培养
- 三级综合医院评审标准实施细则(2012年版)中涉及到的标准、制度
- 实验小学兴趣小组活动方案
- 餐饮部工作总结XX工作计划
- 实习 01-05
- 小区调研报告 - 图文
- 百胜FIS2.0-OMD子系统-工程师审核接口设计v1.0
- 输气工题集
- 奉节县兴隆镇总体规划说明书
- 理科数学总复习(三)
- 齐鲁书社小学五年级下学期传统文化教案
- 《义务教育语文课程标准》修订组的12名成员
- 学前游戏简答题
- Solaris新手必读-121个问题解答
- 五谷杂粮小百科和性保健
- 2018-2019年注册会计师税法真题练习含答案考点及解析
- 论科学发展观及其价值的合理性
- 藻类在环境污染治理中的应用及其作用原理