- 1、本文档共15页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
《c语言数据结构》第6章 树和二叉树 自测卷解答《c语言数据结构》第6章 树和二叉树 自测卷解答
第6章树和二叉树自测卷解答姓名班级题号一二三四五六总分题分101511202024100得分一、下面是有关二叉树的叙述,请判断正误(每小题1分,共10分)(√)1. 若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n—1个非空指针域。(×)2.二叉树中每个结点的两棵子树的高度差等于1。(√)3.二叉树中每个结点的两棵子树是有序的。(×)4.二叉树中每个结点有两棵非空子树或有两棵空子树。(×)5.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值,且小于其右非空子树(若存在的话)所有结点的关键字值。(应当是二叉排序树的特点)(×)6.二叉树中所有结点个数是2k-1-1,其中k是树的深度。(×)7.二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。(×)8.对于一棵非空二叉树,它的根结点作为第一层,则它的第i层上最多能有2i—1个结点。(应2i-1)(√)9.用二叉链表法(link-rlink)存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。(正确。用二叉链表存储包含n个结点的二叉树,结点共有2n个链域。由于二叉树中,除根结点外,每一个结点有且仅有一个双亲,所以只有n-1个结点的链域存放指向非空子女结点的指针,还有n+1个空指针。)即有后继链接的指针仅n-1个。(√)10.〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。最快方法:用叶子数=[n/2]=6,再求n2=n0-1=5二、填空(每空1分,共15分)1.由3个结点所构成的二叉树有5种形态。2. 【计算机研2000】一棵深度为6的满二叉树有n1=n2=2k-1-1=31个分支结点和26-1=32个叶子。注:满二叉树没有度为1的结点,所以分支结点数就是二度结点数。3.一棵具有257个结点的完全二叉树,它的深度为9。(注:用[log2n]+1(257≤2k-1)【全国专升本统考题】设一棵完全二叉树有700个结点,则共有350个叶子结点。答:最快方法:用叶子数=[n/2]=3505. 设一棵完全二叉树具有1000个结点,则此完全二叉树有500个叶子结点,有499个度为2的结点,有1个结点只有非空左子树,有0个结点只有非空右子树。答:最快方法:用叶子数=[n/2]=500,n2=n0-1=499。另外,最后一结点为2i属于左叶子,右叶子是空的,所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数=0.6.【严题集6.7③】一棵含有n个结点的k叉树,可能达到的最大深度为n,最小深度为2。答:当k=1(单叉树)时应该最深,深度=n(层);当k=n-1(k-1叉树)时应该最浅,深度=2(层).(不可能只1层,那是只有根结点的情况。教材说是“完全k叉树”,指的是k≥n的情况。)7. 【96程试题1】二叉树的基本组成部分是:根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种:前序法(即按N L R次序),后序法(即按L R N次序)和中序法(也称对称序法,即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是F E G H D C B。解:求D之法1:画图(见右图),由前序先确定root,由中序先确定左边的叶子,再慢慢推导),由图知,后序序列为FEGH……。。求D之法2:其实不画图也能快速得出后序序列,只要找到根的位置特征。请看,前序遍历BEFCGDH中,根结点在最前面,是B;则后序遍历中B一定在最后面。小结:方法1:由前序先确定root,由中序先确定左子树方法2:递归计算。如B在前序序列中第一,中序中在中间(可知左右子树上有哪些元素),则在后序中必为最后。如法对B的左右子树同样处理,则问题得解。8.【全国专升本统考题】中序遍历的递归算法平均空间复杂度为 O(树的深度k+1)或O(n)。9.【计算机研2001】用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是 33 。解:先构造哈夫曼树,得到各叶子的路径长度之后便可求出WPL=(4+5+3)×2+(1+2)×3=33 (15)(9) (6) 4 5 3 (3)1 2(注:原题为选择题:A.32 B.33 C.34 D.15)三、单项选择题(每小题1分,共11分)(C)1.不含任何结点的空树。(A)是一棵树;(B)是一棵二叉树; (C)是一棵树也是一棵二叉树;(D)既不是树也不是二叉树(C)2.二叉树是非线性数据结构,所以。(A)它不能用顺序存储结构存储;(B)它不能用链式
您可能关注的文档
- “四风”方面存在的突出问题及主要表现汇总“四风”方面存在的突出问题及主要表现汇总.doc
- SH-T3903--2004监理表格(总包单位修改版)2012.3.28SH-T3903--2004监理表格(总包单位修改版)2012.3.28.doc
- “城市之家”招商手册方案“城市之家”招商手册方案.doc
- “外来务工人员子女良好学习习惯的培养与研究”课题实施方案“外来务工人员子女良好学习习惯的培养与研究”课题实施方案.doc
- “夯实统计信息基础,提升银行业数据质量”竞赛活动总结“夯实统计信息基础,提升银行业数据质量”竞赛活动总结.doc
- “奇正相生”的管理智慧“奇正相生”的管理智慧.doc
- “学习《工作规划》落实两个责任”在线测试题库“学习《工作规划》落实两个责任”在线测试题库.doc
- “学习焦裕禄精神,践行群众路线”应知应会试题“学习焦裕禄精神,践行群众路线”应知应会试题.doc
- “学党章党规、学系列讲话,做合格党员”(安排布置)1“学党章党规、学系列讲话,做合格党员”(安排布置)1.doc
- “学案例、转作风、促廉洁”知识测试题“学案例、转作风、促廉洁”知识测试题.doc
- 2021-2022学年湖南省常德市安乡县四年级上学期期中语文真题及答案.pdf
- 2023-2024学年河南省南阳市社旗县四年级上学期期中数学真题及答案.pdf
- 2022-2023学年云南省曲靖市四年级下学期期末数学真题及答案.pdf
- 2021-2022学年河南省周口市鹿邑县二年级下册月考语文真题及答案.pdf
- 2018年河南焦作解放区教师招聘考试真题及答案.pdf
- 2019年江西公务员行测考试真题及答案-乡镇.pdf
- 2019中国石油报社应届高校毕业生招聘试题及答案解析.pdf
- 光大银行招聘应届毕业生能力素质测试笔试真题及答案.pdf
- 2024年广西百色教师招聘考试模拟题及答案.pdf
- 2021-2022学年浙江绍兴诸暨市五年级上册语文期末试卷及答案.pdf
文档评论(0)