




免费预览已结束,剩余2页可下载查看
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
一、判断题()1. 若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n1个非空指针域。()2.二叉树中每个结点的两棵子树的高度差等于1。 ()3.二叉树中每个结点的两棵子树是有序的。 ()4.二叉树中每个结点有两棵非空子树或有两棵空子树。 ()5.二叉树中所有结点个数是2k-1-1,其中k是树的深度。(应2i-1) ()6.二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。 ()7.对于一棵非空二叉树,它的根结点作为第一层,则它的第i层上最多能有2i1个结点。(应2i-1)()8.用二叉链表法存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。()9.具有12个结点的完全二叉树有5个度为2的结点。 (r ) 10、哈夫曼树中没有度为1的结点,所以必为满二叉树。(r )11、在哈夫曼树中,权值最小的结点离根结点最近。(r )12、线索二叉树是一种逻辑结构。( )13、深度为K的完全二叉树至少有2K-1个结点。 ( )14、具有n个结点的满二叉树,其叶结点的个数为(n+1)/2。 ( )15、前序和中序遍历用线索树方式存储的二叉树,不必使用栈。 ( )16、哈夫曼树是带权路径长度最短的树,路径上权值较大的点离根较远。()17、在二叉树结点的先序序列和后序序列中,所有叶子结点的先后顺序完全相同。()18、二叉树的遍历操作实际上是将非线性结构线性化的过程()19、树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。()20、树的后根遍历序列与其所转化的二叉树的后序遍历序列相同。二、填空1 由个结点所构成的二叉树有 5 种形态。 2. 线索二叉树的左线索指向其_前驱_,右线索指向其_后继_。3 一棵具有257个结点的完全二叉树,它的深度为 9 。4、如某二叉树有20个叶子结点,有30个结点仅有一个孩子,则该二叉树的总结点数为_69_。5. 设一棵完全二叉树具有1000个结点,则此完全二叉树有 500 个叶子结点,有 499 个度为2的结点,有 1 个结点只有非空左子树,有 0 个结点只有非空右子树。答:最快方法:用叶子数n/2500 ,n2=n0-1=499。 另外,最后一结点为2i属于左叶子,右叶子是空的,所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数0.6. 一棵含有n个结点的k叉树,可能达到的最大深度为 n ,最小深度为 2 。7. 若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是 F E G H D C B 。 8. 在二叉树中,指针p所指结点为叶子结点的条件是_ p-lchild=null & p-rchlid=null。三、选择题 1某二叉树结点的中序序列为A、B、C、D、E、F、G,后序序列为B、D、C、A、F、G、E,则其左子树中结点数目为(C)A)3 B)2 C)4 D)52二叉树是非线性数据结构,所以( C )。、它不能用顺序存储结构存储; 、它不能用链式存储结构存储; 、顺序存储结构和链式存储结构都能存储; 、顺序存储结构和链式存储结构都不能使用 3.具有n(n0)个结点的完全二叉树的深度为( C )。() log2(n) () log2(n) () log2(n) +1 () log2(n)+14把一棵树转换为二叉树后,这棵二叉树的形态是( A )。()唯一的 ()有多种()有多种,但根结点都没有左孩子 ()有多种,但根结点都没有右孩子5.线索二叉树是一种(C )结构。A 逻辑 B 逻辑和存储 C 物理 D线性6、将一棵有100个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点编号为1,则编号为49的结点的左孩子的编号为( A) A、98 B、99 C、50 D、487、设森林F中有三棵树,第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是(D)A)M1 B)M1+M2 C)M3 D)M2+M38、将一棵有100个结点的完全二叉树从根开始,每一层从左到右依次对结点进行编号,根结点编号为1,则编号最大的非叶结点的编号为(C) A、48B、49C、50D、519、引入二叉线索树的目的是(A )A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入与删除C、为了能方便的找到双亲 D、使二叉树的遍历结果唯一10若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(B )A9 B11 C15 D不确定 11 一棵树深度为K的完全二叉树至少有(C )个结点A2k 1 B. 2k-1 1 C. 2k-1 D. 2k12一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是(B )ACABDEFG BABCDEFG CDACEFBG DADCFEG13. 有关二叉树下列说法正确的是(B )A二叉树的度为2 B一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为214. 一个具有1025个结点的二叉树的高h为(C )A11 B10 C11至1025之间 D10至1024之间15一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有( B)结点A2h B2h-1 C2h+1 Dh+1 16对于有n 个结点的二叉树, 其高度为(D )Anlog2n Blog2n Clog2n+1 D不确定17. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的先序遍历是(D )。Aacbed Bdecab Cdeabc Dcedba 18若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置,利用(C )遍历方法最合适。A前序 B中序 C后序 D按层次19在下列存储形式中,哪一个不是树的存储形式?(D )A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法20在下列关于二叉树的叙述中,正确的是(D )只有一个结点的二叉树度为0;二叉树的度为2; 二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D21若X是二叉中序线索树中一个有左孩子的结点,且X不为根,则x的前驱为(C ) A.X的双亲 B.X的右子树中最左的结点C.X的左子树中最右结点 D.X的左子树中最右叶结点22.在二叉树结点的先序序列,中序序列和后序序列中,所有叶子结点的先后顺序(B )A都不相同B完全相同 C先序和中序相同,而与后序不同 D中序和后序相同,而与先序不同23.在线索化二叉树中,t所指结点没有右子树的充要条件是(A )。A、t-Rtag=1 B、t-Rchild=NULLC、t-Rtag=1且t-Rchild=NULL D、以上都不对24、设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为(B)。A2hB2h-1C2h+1Dh+125、如右图所示二叉树的中序遍历序列是(B)。AabcdgefBdfebagc CdbaefcgDdefbagc26、设a和b为一棵二叉树上的两个结点,在中序遍历时,a在b前的条件是(D)。Aa是b的左孩子Bb是a的右孩子Ca是b左子树上结点或b是a右子树上结点D以上三项均可27、假定在一棵二叉树中,双分支结点数为15,单分支结点数为30,则叶子结点数为(C)个。A45B15C16D3128、树的基本遍历策略可分为先根遍历和后根遍历;二叉树的遍历策略分为先序、中序和后序遍历。这里把由树转化得到的二叉树叫做这棵树对应的二叉树。以下结论(A)是正确的。A树的先根遍历序列与其对应的二叉树的先序遍历序列相同B树的后根遍历序列与其对应的二叉树的后序遍历序列相同C树的先根遍历序列与其对应的二叉树的中序遍历序列相同D以上都不对29、如下图所示的4棵二叉树,(C)不是完全二叉树。30、设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有(B)个空指针域。A2m-1B2mC2m+1D4m 31、二叉树的第k层的结点数最多为( D )A2k-1B2K+1C2K-1D2K-132、设某棵二叉树中有2000个结点,则该二叉树的最小高度为( C )。A9B10C11D1233、一棵有n个结点的树,在把它转换成对应的二叉树后,该二叉树根结点的左子树上共有( B )个结点。An-2Bn-1Cn+1Dn+234、对于一棵深度为4的三叉树,最多有( C )个结点。A30B36C40D5435、设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为(B )。(A) 3(B) 4(C) 5(D) 1四、简答题 1.给定二叉树的两种遍历序列,分别是:前序遍历序列:D,A,C,E,B,H,F,G,I; 中序遍历序列:D,C,B,E,H,A,G,I,F,试画出二叉树B。解:方法是:由前序先确定root,由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合,可继续确定root的左右孩子。将他们分别作为新的root,不断递归,则所有元素都将被唯一确定,问题得解。2、已知一棵二叉树,其中序序列DBCAFGE,后序序列DCBGFEA,构造该二叉树。解:3、给定权值8,12,4,5,26,16,9,构造一棵带权路径长度最短的二叉树,并计算其带权路径长度。解:或: WPL=83+44+54+162+93+123+262 =207注:哈夫曼树的左右子树可以互换。4. 把如图所示的树转化成二叉树。答:注意全部兄弟之间都要连线(包括度为2的兄弟),并注意原有连线结点一律归入左子树,新添连线结点一律归入右子树。 A B E C K F H D L G I M J5、画出和下列二叉树相应的森林。答:注意根右边的子树肯定是森林,而孩子结点的右子树均为兄弟。6、假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这8个字母设计哈夫曼编码。解:哈夫曼编码先将概率放大100倍,以方便构造哈夫曼树。 w=7
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年咖啡连锁品牌扩张战略:品牌战略规划与区域市场拓展报告
- 2025年结构工程师试题带答案详解(典型题)
- 2025年新能源汽车零部件行业市场增长动力分析报告
- 2025年新能源汽车轻量化车身轻量化碰撞安全性能评估体系构建报告
- 2025年法学硕士真题解析及答案汇编
- 2025年主管护师考试复习全攻略及试题及答案
- 2025年国家公务员考试时事政治题库带解析必背(巩固)
- 2025年商业银行从业资格考试题及答案
- 2025年临床医师定期考核中医知识必考题库及参考答案
- 2025年大学劳动教育专业题库- 劳动技能教育在高校实践教学中的运用
- 2025年北京市家庭居室装修工程施工合同
- 事业法人登记管理办法
- 承装修试许可证管理办法
- 2025楼宇平方效益评价规范
- 术后并发症护理
- 第9课《天上有颗“南仁东星”》课件 2025-2026学年统编版八年级语文上册
- 餐饮服务食品安全常规项目自查记录表
- 粪污清运服务管理制度
- 医疗机构动火管理制度
- 孵化基地制度管理制度
- 中枢整合康复技术课件
评论
0/150
提交评论