《北京理工大学数据结构考研例题解析5》由会员分享，可在线阅读，更多相关《北京理工大学数据结构考研例题解析5（16页珍藏版）》请在金锄头文库上搜索。
1、本资料由理硕教育整理，理硕教育是全国唯一专注于北理工考研辅导的学校， 相对于其它机构理硕教育有得天独厚的优势。丰富的理工内部资料资源与人力 资源确保每个学员都受益匪浅，确保理硕教育的学员初试通过率 89%以上，复 试通过率接近 100%，理硕教育现开设初试专业课 VIP 一对一，初试专业课网络 小班，假期集训营，复试 VIP 一对一辅导，复试网络小班，考前专业课网络小 班，满足学员不同的需求。因为专一所以专业，理硕教育助您圆北理之梦。详 情请查阅理硕教育官网点称为该结点的（），该结第 5 章 树和二叉树课后习题讲解 1.填空题结点分成 树是n （n0）结点的有限集合，在一棵非空树中，有（）个根
2、结点【解答】有且仅有一个，互不相交m （m0）个（）的集合，每个集合都是根结点的子树。点称为其子树根结点的（）。树中某结点的子树的个数称为该结点的（），子树的根【解答】度，孩子，双亲有（）个叶子结点和（）个非终端结点一棵二叉树的第i （il）层最多有（）个结点；一棵有n （n0）个结点的满二叉树共【解答】2i-l, (n+l)/2, (n-l)/2存在度为1的结点，所以n=nO+【分析】设满二叉树中叶子结点的个数为nO,度为2的结点个数为n2,由于满二叉树中不 ；由二叉树的性质 n0=n2+1,得 n0=（n+1）/2, n2=（n-1）/2。【解答】2h【分析】深 设高度为h的二叉树上只有度
3、为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值【分析】在满二叉树中叶子结点的个数达到最多。 其他层上都只有2个结点。）。）。个数的情况是第1层有1个结点, 二叉树中，所含叶子的个数最多为（ 具有 100 个结点的完全二叉树的叶子结点数为（解答】 50分析】 100 个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结 点的编号为 50，也就是说，从编号51 开始均为叶子。 已知一棵度为 3 的树有 2 个度为 1 的结点， 3 个度为 2 的结点， 4 个度为 3 的结点。则该 树中有（ ）个叶子结点。【解答】 12【分析】根据二叉树性质3的证明过程，有n
4、0=n2+2n3+l （nO、n2、n3分别为叶子结点、度 为 2 的结点和度为3 的结点的个数）。 某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE,则其后序遍历序列是（）。 【解答】 CDBGFEA【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。 在具有 n 个结点的二叉链表中，共有（ ）个指针域，其中（ ）个指针域用于指向其左 右孩子，剩下的（ ）个指针域则是空的。【解答】2n， n-1， n+1 在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（） 。【解答】n，n-1【分析】n-1个分支结点是经过n-1次合并后得到的。2.选择题 如果结点A有
5、3个兄弟，B是A的双亲，则结点B的度是（【解答】D 设二叉树有n个结点，则其深度为（A n-1 B n C岀胃+1 D不能确定【解答】D【分析】此题并没有指明是完全二叉树，则其深度最多是n,最少是忸刃国+1。二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或只有一个结点B高度等于其结点数【解答】BC任一结点无左孩子D任一结点无右孩子【分析】此题注线索匚结点R没有左孩子的充要条件是（）。是序列正好相反，则左斜树和右斜树均满足条件。ild=NULL B R.l tag=O C R.l tag=l D R.rchild=NULL【分析】线索二叉树中某结点是否有左孩子，不能通过左
6、指针域是否为空来判断，而要判断 左标志是否为 1。 深度为 k 的完全二叉树至少有（ ）个结点，至多有（ ）个结点，具有 n 个结点的完全 二叉树按层序从 1 开始编号，则编号最小的叶子的序号是（ ）。A 2k-2+1 B 2k-1 C 2k -1 D 2k- 1 -1E 2k+1 F 2k+1 -1 G 2k -1+1 H 2k【解答】 B， C， A【分析】深度为k的完全二叉树最少结点数的情况应是第k层上只有1个结点，最多的情况 是满二叉树，编号最小的叶子应该是在结点数最少的情况下，叶子结点的编号。 一个高度为 h 的满二叉树共有 n 个结点，其中有 m 个叶子结点，则有（ ）成立。A n
7、=h+m B h+m=2n C m=h-1 D n=2m-1解答】 D分析】满二叉树中没有度为 1 的结点，所以有 m 个叶子结点，则度为 2 的结点个数为 m-1。 任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ ）。A肯定不发生改变B肯定发生改变C不能确定D有时发生变化【解答】A【分析】三种遍历次序均是先左子树后右子树。，则把森林转换成二叉树后,（）个结点。如果T是由有序树T转换而来的二叉树，那么T中结点的前序序列!序列，T中结点的后序序列就是T中结点的（ ）序列。A前序B中序C后序D层序【解答】A，B 设森林中有4棵树，树中结点的个数依次为n1、n其根结点的右子树上有（
8、）个结点，根结点的A n1T B n1 C n1+n2+n3 D n2+n3+n4【解答】D，A【分析】由森林转换的二叉树中，根结点、中结点的（）棵树中除了根结点以外其余结为第一棵树的根结点，根结点的左子树是由第一 戈的，根结点的右子树是由森林中除第一棵树外其他树转换来的。讨论树、森林和二叉树的关系,目的是为了（）。借助二叉树上的运算方法去实现对树的一些运算将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题F换成二叉树将树、CD3.判断题支巧，没有什么实际意义 在线索二叉树中，任一结点均有指向其前趋和后继的线索。解答】错。某结点是否有前驱或后继的线索，取决于该结点的标志域是
9、否为1。 在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面。解答】对。由前序遍历的操作定义可知。 二叉树是度为 2 的树。解答】错。二叉树和树是两种不同的树结构，例如，左斜树是一棵二叉树，但它的度为 1。 由树转换成二叉树，其根结点的右子树总是空的。【解答】对。因为根结点无兄弟结点。 用一维数组存储二叉树时，总是以前序遍历存储结点。【解答】错。二叉树的顺序存储结构是按层序存储的，一般适合存储完全二叉树4.证明：对任一满二叉树，其分枝数B = 2(n0-l)。(其中，n0为终端结点数)【解答】因为在满二叉树中没有度为1的结点，所以有： n=n0+n2设B为树中分枝数，则n=B+l所以B=
10、n0 +n2T再由二叉树性质:n0=n2+1代入上式有:B二nO+nOTT=2(nOl)5.证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。 遍历序列为blb2b3bn。【解答】证明采用归纳法。设二叉树的前序遍历序列为ala2a3an,当n=l时，前序遍历序列为al,中序遍历可以唯一确定该二叉树;U为bl,二叉树只有一个根结点，所以，al=bl,假设当n14時夫亘輪码树/结点个数。每个结点的值，而是求出结点的个数。所以可将遍历算法中的“访 乍”，将结点的数目累加到一个全局变量中，每个结点累加一次即完 设计算法按前序次序打印二叉树中的叶子结点。【解答】本算法的要求与前序遍历算法既
11、有相同之处，又有不同之处。相同之处是打印次序均为前序，不同之处是此处不是打印每个结点的值，而是打印出其中的叶子结点，即为有条件打印。为此，将前序遍历算法中的访问操作改为条件打印即可。算法如下：设计算法求二叉树的深度。法如下:【解答】当二叉树为空时，深度为0若二叉树不为空，深度应加1,而其左右子树深度的求解又可通过递归调用本算法来Z编写算法，要求输出二叉树后序遍历序列的逆序。历根结点的【解答】要想得到后序树深度的最大值逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍后遍历根结点的左子树。注意和前序遍历的区别，具体算法如下:以二叉链表为存储结构，编写算法求二叉树中结点X的双亲。【解答】对二叉链表进行遍历，在遍历的过程中查找结点X并记载其双亲。具体算法如下:以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树。的双亲结点中指向结点X的指针置空。具体算法如下:二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历。【解答】对二叉链表进行遍历，在遍历的过程中查找结点X并记载其双亲，然吉点X。一棵具有n个结【解答】按照题目求，设置一个工作栈以完成对该树的非递归算法，思路如下:每访问执行该过点，将此结点压栈，查看此结点是否有左子树，若有，
