下载文档原格式
7.3补充练习题及参考答案7.3.1单项选择题1.对于一棵具有n 个结点、度为4的树来说,_____________.A.树的高度最多是n-3B.树的高度最多是是n-4C.第i 层上最多有4(i-1)个结点D.至少在某一层上正好有4个结点答:这样的树中至少有一个结点的度为4,也就是说,至少有一层中有4个或以上的结点,因此树的高度最多是n-3。
本题的答案为A 。
2.度为4、高度为h 的树_____________.A.至少有h+3个结点B.最多有4h -1个结点C.最多有4h 个结点D.至少有h+4个结点答:与上小题分析相同,本题的答案为A 。
3.对于一棵具有n 个结点、度为4的树来说,树的高度至少是_____________.A.)]2([log 4nB.)]13([log 4-nC.)]13([log 4+nD.)]12([log 4+n答:由树的性质4可知,具有n 个结点的m 次树的最小高度为)]1)1(([log +-m n m 。
这里m=4,因此最小高度为)]13([log 4+n 。
本题的答案为C 。
4.在一棵3次树中度为3的结点数为两个,度为2的结点数为一个,度为1的结点数为两个,则度为0的结点数为_____________个。
A.4B.5C.6D.7答：3n =2，2n =1，1n =2，001235n n n n n n +=+++=，n=度之和+1=33n +22n +1n +1=11， 所以65110=-=n 。
本题的答案为C 。
5.若一棵有n 个结点的树,其中所有分支结点的度均为k,该树中的叶子结点个数 是_____________。
A.n(k 一1)/kB.n-kC.(n+1)/kD.(nk 一n+1)/k答:m=k,有k n n n +=0,度之和=n-1=k kn ,k n n k /)1(-=,所以0n =n-k n =n-(n-1)/k=(nk-n+1)/k.本题的答案为D 。
⼆叉树的优点和缺点
⼆叉排序树是⼀种⽐较有⽤的折衷⽅案。
数组的搜索⽐较⽅便，可以直接⽤下标，但删除或者插⼊某些元素就⽐较⿇烦。
链表与之相反，删除和插⼊元素很快，但查找很慢。
⼆叉排序树就既有链表的好处，也有数组的好处。
在处理⼤批量的动态的数据是⽐较有⽤。
⽂件系统和数据库系统⼀般都采⽤树（特别是B树）的数据结构数据，主要为排序和检索的效率。
⼆叉树是⼀种最基本最典型的排序树，⽤于教学和研究树的特性，本⾝很少在实际中进⾏应⽤，因为缺点太明显了（看看教科书怎么说的）。
就像冒泡排序⼀样，虽然因为效率问题并不实⽤，单不失⼀种教学例⼦的好⼿段。
平衡⼆叉树都有哪些应⽤场景
⼆叉树⽀持动态的插⼊和查找，保证操作在O(height)时间，这就是完成了哈希表不便完成的⼯作，动态性。
但是⼆叉树有可能出现worst-case，如果输⼊序列已经排序，则时间复杂度为O(N)
平衡⼆叉树/红⿊树就是为了将查找的时间复杂度保证在O(logN)范围内。
所以如果输⼊结合确定，所需要的就是查询，则可以考虑使⽤哈希表，如果输⼊集合不确定，则考虑使⽤平衡⼆叉树/红⿊树，保证达到最⼤效率
平衡⼆叉树主要优点集中在快速查找。
如果你知道SGI/STL的set/map底层都是⽤红⿊树（平衡⼆叉树的⼀种）实现的，相信你会对这些树⼤有兴趣。
缺点：
顺序存储可能会浪费空间(在⾮完全⼆叉树的时候)，但是读取某个指定的节点的时候效率⽐较⾼O(0)
链式存储相对⼆叉树⽐较⼤的时候浪费空间较少，但是读取某个指定节点的时候效率偏低O(nlogn)。
第6章 树和二叉树内容概要：本章主要介绍树，二叉树，最优二叉树的相关概念和操作，存储结构和相应的操作，并在综合应用设计中，给出了对应算法的C 语言实现。
教学目标1．理解各种树和森林与二叉树的相应操作。
2．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其他操作。
3．熟练掌握二叉树和树的各种存储结构及其建立的算法。
4．掌握哈夫曼编码的方法。
5．通过综合应用设计，掌握各种算法的C 语言实现过程。
基本知识点：树和二叉树的定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码重点：二叉树的性质、二叉树的遍历及其应用，构造哈夫曼树。
难点：编写实现二叉树和树的各种操作的递归算法。
本章知识体系结构：课时安排：6个课时树的定义 树树的性质 树的逻辑表示法 树形表示法 树的存储结构 双亲存储结构 文氏表示法凹入表示法 括号表示法 孩子存储结构 孩子双亲存储结构二叉树二叉树的定义 二叉树的性质二叉树的逻辑表示法（采用树的逻辑表示法）二叉树的存储结构二叉树的顺序存储结构先序遍历 中序遍历 后序遍历二叉树的遍历 二叉树的链式存储结构（二叉链） 由先序序列和中序序列构造二叉树 由中序序列和后序序列构造二叉树二叉树的构造 二叉树的线索化 哈夫曼树二叉树和树之间的差别 二叉树与树、森林之间的转换二叉树和树课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标掌握树、二叉树的基本概念和术语，二叉树的性质教学重点二叉树的定义、二叉树的性质、链式存储结构教学难点二叉树的性质、链式存储二叉树的基本操作组织教学一、树的定义二、树的基本概念三、二叉树的定义、性质四、二叉树的顺序存储结构和链式存储结构五、小结作业复习本讲内容并预习下一讲内容课堂情况及课后分析课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标掌握二叉树遍历的三种方法及二叉树的基本操作教学重点二叉树的遍历算法教学难点中序与后序遍历的非递归算法组织教学一、复习二叉树的定义二、遍历二叉树的三种方法三、递归法遍历二叉树四、二叉树的基本操作五、总结作业复习本讲内容并预习下一讲内容课堂情况及课后分析课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标理解树与森林的转换，掌握哈夫曼树教学重点哈夫曼树教学难点树与森林的转换组织教学一、导入二、树与森林三、哈夫曼树四、小结作业习题6课堂情况及课后分析前面几章讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，可用于描述客观世界中具有单一前驱和后继的数据关系。
数据结构考试题库含答案数据结构习题集含答案目录目录1选择题2第一章绪论2第二章线性表4第三章栈和队列5第四章串6第五章数组和广义表7第六章树和二叉树7第七章图9第八章查找11第九章排序12简答题15第一章绪论15第二章线性表20第三章栈和队列22第四章串24第五章数组和广义表24第六章树和二叉树26第七章图31第八章查找33第九章排序34编程题36第一章绪论36第二章线性表36第三章栈和队列46第四章串46第五章数组和广义表46第六章树和二叉树46第七章图46第八章查找46第九章排序51选择题第一章绪论1.数据结构这门学科是针对什么问题而产生的？（A）A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下面选项最准确的是（D）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C）A、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素4.某数据结构是指（A）。
A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C）。
A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的目的是（C）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7.算法分析的主要方法（A）。
A、空间复杂度和时间复杂度B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性8.计算机内部处理的基本单元是（B）A、数据B、数据元素C、数据项D、数据库9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（B）。
数据结构树和二叉树习题及答案集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#习题六树和二叉树一、单项选择题1．以下说法错误的是 ( )A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继C．树形结构可以表达(组织)更复杂的数据D．树(及一切树形结构)是一种"分支层次"结构E．任何只含一个结点的集合是一棵树2．下列说法中正确的是 ( )A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的度肯定等于2D．任何一棵二叉树中的度可以小于23．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储C．将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义4．树最适合用来表示 ( )A．有序数据元素 B．无序数据元素C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是（）。
A．M1 B．M1+M2 C．M3 D．M2+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-19．二叉树的第I层上最多含有结点数为（）A．2I B． 2I-1-1 C． 2I-1 D．2I -110．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+111. 利用二叉链表存储树，则根结点的右指针是（）。
