问：程序报错：二叉树的创建和输出递归先序建立二叉树，然后非递归中序遍历输出。在完成creatBiTree的输入后程序报...答：（1）createBiTree建树的过程，你采用的是递归，那么你怎么确定，输入的下一个数据应该是建立在左子树中还是右子树？分析你的过程，如果输入数据不是-1，那么就...
问：二叉树模型在资产定价模型中的应用答：可以第一时间收到“提问有新回答”“回答被采纳”“网友求助”的。您想在自己的上展示“知道”上的问答吗？来获取 码吧！或，请到吧...
问：问几个关于二叉树的问题一、在深度为的满二叉树中，度为的结点个数为什么？二、一颗二叉树有个...答：一，满二叉树中除了叶子节点以外其他节点的度均为，总结点数为^-1=1，叶子节点数为^=，所以度为的节点个数为1-=.二，度为的节点数总是比度为...
问：实物期权的三种定价模型答：二叉树定价模型，蒙地卡罗模拟法，B-S模型。具体看我给你的参考 。
问：这个二叉树遍历的顺序到底应该怎么看啊答：中序遍历二叉树的则是：若二叉树为空，则什么也不做；否则，先中序遍历左子树（左下方的小二叉树），再访问根结点（最上面的结点），最后中序遍历右子树（右...
问：请教二叉树期权模型的有关问题我想建一个研发项目的评价模型，用二叉树模型来做，但不知道各阶段的成功概率...答：本文将实物期权理论引入R&D项目管理领域,以阶段门NPD模型为基础,探讨了应用二叉树期权定价模型评估研发项目价值的具体思路和步骤,并通过比较,证明了由于评估时...
问：一道简单的关于二叉树的选择题。答：你找一本数据结构教材，看一下二叉树部分，里面有二叉树的几条性质，其中就有一条：任何一棵非空二叉树的叶子结点的个数等于度为的结点的个数加1。 中的...
问：请问想看看股权激励计划中的定价模型，如何在国数据库...答：不用看，证监会定的股权激励计划必须采用B-S模型定价。
问：如何进行可转债价值判断答：由于可转债发行条款远比单纯的债券或复杂，因此，普通投资者对这种金融工具的价值判断比较难以把握。估值方法从金融工程学的角度讲，可以用期权工具为可...
问：二叉树期权定价模型中性和动态求公式答：中性：假设基期为S()，每期上涨幅度为U，下跌幅度为D，无收益率为r每年，每期间隔为t，期权行权为K，讨论欧式看涨期权，可以做出如下...
问：什么是完全二叉树？数据结构答：完全二叉树的定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。出于简便起见,完全...
问：给我一个基本二叉树期权定价模型英文例子是对冲资产组合的_...万分感激答：自己去看John C Hull的期货期权以及其他金融衍生品啊，现在谁还在用二叉树对冲资产啊
问：哪里有“放弃期权”和“时机选择期权”的题目可以练练笔吗？爱...答：这里有：学 管理 闫期权股价题[1].doc第十一章期权估价（说明：为增强讲座效果，网校特将讲义中的例题隐藏。您也可进行重新设置：&...
问：CPA期权二叉树定价模型问题（两期模型）答：这个二叉树模型里面数据都是这么假定的，解释如下。上升.%，就是s*1.；然后再下降1.%，就是再乘以（1-1.%）即.1；不难发现，在给出的精确度条件...
09-1707-0609-1508-09
04-1203-3010-2202-27
◇本站云标签二叉树的概念以及性质2、二叉树及其基本性质（1）什么是二叉树二叉树是一种很有用的非线性结构,它具有以下两个特点：1）非空
二叉树的概念以及性质2、二叉树及其基本性质（1）什么是二叉树二叉树是一种很有用的非线性结构,它具有以下两个特点：1）非空二叉树只有一个根结点；2）每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树.*：根据二叉树的概念可知,二叉树的度可以为0（叶结点）、1（只有一棵子树）或2（有2棵子树）.（2）二叉树的基本性质（学吧学吧独家稿件）性质1 在二叉树的第k层上,最多有 个结点.性质2 深度为m的二叉树最多有个 个结点.性质3 在任意一棵二叉树中,度数为0的结点（即叶子结点）总比度为2的结点多一个.性质4 具有n个结点的二叉树,其深度至少为 ,其中 表示取 的整数部分.3、满二叉树与完全二叉树满二叉树：除最后一层外,每一层上的所有结点都有两个子结点.完全二叉树：除最后一层外,每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点.*：根据完全二叉树的定义可得出：度为1的结点的个数为0或1.下图a表示的是满二叉树,下图b表示的是完全二叉树：完全二叉树还具有如下两个特性：性质5 具有n个结点的完全二叉树深度为 .性质6 设完全二叉树共有n个结点,如果从根结点开始,按层序（每一层从左到右）用自然数1,2,…,n给结点进行编号,则对于编号为k（k=1,2,…,n）的结点有以下结论：若k=1,则该结点为根结点,它没有父结点；若k>1,则该结点的父结点的编号为INT(k/2).
已经够详细了.
与《二叉树的概念以及性质2、二叉树及其基本性质（1）什么是二叉树二叉树是一种很有用的非线性结构,它具有以下两个特点：1）非空》相关的作业问题
1.深度为m的满二叉树有2^m-1个结点.因为满二叉树的定义为:一颗深度为k且有2^k-1个结点的二叉树称为满二叉树.2.若要树深为最小,显然要使除最后一层外的每一层都有尽可能多的结点,即要二叉树为完全二叉树.由二叉树的一个重要性质:具有n个结点的完全二叉树的深度为[log2n]+1.(这是在根节点层次为1时,若为0,
假设n0表示度为0的结点(叶子结点),n2表示度为2的结点(左右子树皆非空的结点),由二叉树的性质有：n0 = n2 + 1已知n0 = k,则n2 = n0 -1 = k - 1即左右子树皆非空的结点个数是(k-1).
定义就是概念 再问： 那含有未知数的等式叫做方程是定义吗? 再答： 对再问： 对顶角相等是定义吗？ 再答： 不是。对顶角是定义 定义就是指出这种东西与其他东西不一样的地方。 比如角、线、面、点、线段、直线、射线、三角形、四边形，这些都是定义
全等三角形的定义 两个三角形的形状、大小、都一样时,其中一个可以经过平移、旋转、翻折等运动（或称变换）使之与另一个完全重合,这两个三角形称为全等三角形. 当两个三角形完全重合时,互相重合的顶点叫做对应顶点,互相重合的边叫做对应边,互相重合的角叫做对应角. 由此,可以得出：全等三角形的对应边相等,对应角相等. 三角形全等
商不变的性质： 被除数和除数同时扩大或缩小相同的倍数,它们的商不变!分数的基本性质： 分子分母同时乘以或除以一个不为零的数,分数的值不变!
这是递归算法.前序第一个必定是根,根就是A,从中序中就能分出左、右子树了：B和EDCHGIFJ,这是中序就可据此从前序中分出左、右子树了：B和CDEFGHIJ,这是前序了.这样一个问题变成了两个同样的小问题了,递归下去不就解决了.多动动脑筋就出来了
中秩遍历等于后续的话；说明是一个左子树,就是如“人”的左半边,因此先序就是FEDCBA这个题目毫无意义
a(n+1)+an=k,k为常数,对所有正整数都成立,则称an是等和数列性质a(n+1)+an=k,an+a(n-1)=k两式相减得a(n+1)-a(n-1)=0,即a(n+1)=a(n-1)即奇数项都相等于a1,偶数项都等于a2a1+a2=5,a1=2,则a2=3所以a18=a2=3s21=（a1+a2)+(a3+a
一、单项选择题：（每题1.5分） 1.D 2.B 3.A 4.A 5.B6.D 7.C 8.B 9.C 10.D11.C 12.C 13.B 14.D 15.D 16.B 17.D 18.A 19.C 20.B二、问题求（共2题,每空5分,共计10分）1．702．5三、阅读程序写结果（共4题,每题8分,共计32分）1.
性质是一种数学名词本身的特点,定理是它与别的数学名词或它性质之间相互联系的结果.物理中的性质就是某一具体物质所表现出的一些特点,是存在的,可以用试验获得.而数学的性质是认为定义的,是被创造的,是一种抽象的概念一般是数学概念被定义后,用来解释一些物理特征
1、长方形的周长=（长+宽）×2 C=(a+b)×2 2、正方形的周长=边长×4 C=4a 3、长方形的面积=长×宽 S=ab 4、正方形的面积=边长×边长 S=a.a= a 5、三角形的面积=底×高÷2 S=ah÷2 6、平行四边形的面积=底×高 S=ah 7、梯形的面积=（上底+下底）×高÷2 S=（a＋b）h÷2
1.什么是十进制计数法?每相邻的两个计数单位之间的进率都是十的计数方法,叫做“十进制计数法” 2.怎麽比较两个数的大小?先比最高位,哪个数的最高位大,就哪个大,如果相等就往下比,依此类推.3.分数的基本性质和小数的基本性质有什么关系?分数的基本性质是以分数大小相等这一概念为基础的.因为分数与整数不同,两个分数的大小相等
塑料的广义的概念就是可塑性的材料.比如水泥石膏等也是“塑料”.狭义的的塑料就是指具有可塑性的高分子材料,比如聚乙烯,聚苯乙烯,聚氯乙烯等等.
再答： 谢谢！
1满十就加一位,如1,2,3,4,5.9,102相加减或相乘除
1每相邻两个计数单位之间的进率是十,这叫做十进制计数法.小数的计数单位是：十分之一、百分之一、千分之一、万分之一…………2先看整数部分,谁大谁就大.如果整数部分一样,那就再看小数部分的十分位,谁大谁就大.如果十分位一样,那就再看小数部分的百分位,以此类推……
小数点靠右移动,数值变小;靠左移动,数值变大 因数和倍数是相对于两个数来说的.一定要说成某数是某数的因数,某数是某数的倍数.质数和合数是按照一个数的因数的个数来说的,只有两个因数的话呢,就是质数（也叫素数）,若有三个或三个以上因数的话,那么就是合数了.
2个①错,如M{1,2,3},P{1,5,6,7,8,9}为一反例②对,若其为假,即M中没有不属于P的元素,这与已知矛盾③错,如M{1},P{2,3}为一反例④对,由已知直接得
.什么是十进制计数法?你能说出哪些计数单位?十进制计数法是相对二进制计数法而言的,是我们日常使用最多的计数方法（俗称“逢十进一”）,它的定义是:“每相邻的两个计数单位之间的进率都为十”的计数法则,就叫做“十进制计数法”.个,十,百,千,万2.怎样比较两个数的大小?(1)整数的大小比较：先看位数,位数多的数大；位数相同,您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
数据结构考研试精选及答案第6章
树和二叉树答案.doc 50页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：200 &&
数据结构考研试精选及答案第6章
树和二叉树答案
你可能关注的文档：
··········
··········
树和二叉树一、选择题
1.D 2.B 3.C 4.D 5.D 6.A 7.1C 7.2A 7.3C 7.4A 7.5C 8.B
9.C 10.D 11.B 12.E 13.D 14.D 15.C 16.B 17.C 18.C 19.B 20.D
21.A 22.A 23.C 24.C 25.C 26.C 27.C 28.C 29.B 30.C 31.D 32.B
33.A 34.D 35.B 36.B 37.C 38.B 39.B 40.B 41.1F 41.2B 42.C 43.B
44.C 45.C 46.B 47.D 48.B 49.C 50.A 51.C 52.C 53.C 54.D 55.C
56.B 57.A 58.D 59.D 60.B 61.1B 61.2A 61.3G 62.B 63.B 64.D 65.D
66.1C 66.2D 66.3F 66.4H 66.5I
部分答案解释如下。12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因为n=1001,所以+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B都不全。由本题可解答44题。47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。二、判断题1.× 2.× 3.× 4. √ 5. √ 6. √ 7.√ 8.× 9. √ 10.× 11.× 12.×
13.× 14.√ 15.× 16.× 17.√ 18.√ 19.×
20.√ 21.×
22.√ 23.× 24.×
25.√ 26.× 27.× 28.× 29.√ 30.× 31.× 32.√ 33.× 34.× 35.× 36.√
37.√ 38.× 39.× 40.× 41.(3) 42.√ 43.√ 44.× 45.√ 46.× 47.× 48.×
49.√ 50.√
部分答案解释如下。6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。19．任何结点至多只有左子树的二叉树的遍历就不需要栈。24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i&=n)，右儿子是2i+1（2i+1&=n）37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。38 . 新插入的结点都是叶子结点。42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 三.填空题1.(1)根结点(2)左子树(3)右子树
2.(1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法3．p-&lchild==null && p-&rchlid==null
4.(1) ++a*b3*4-cd
5.平衡因子6. 9
8.(1)2k-1 (2)2k-1
(2)2H-1 (3)H=?log2N?+1
10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条件是?log2s?=?log2t?。11. ?log2i?=?log2j?
(2)(n-1)/2
(3)(n+1)/2
(4) ?log2n? +1
13.n 14. N2+1
15.(1) 2K+1-1 (2) k+1
21.(1) n1-1 (2)n2+n3
22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1
正在加载中，请稍后...导读：（3）找出所有的二叉树，其结点在下列两种遍历下，恰好都是以同样的顺序出现：1）前序遍历和中序遍历。2）前序遍历和后序遍历。【南京航空航天大学1995六(5分)】（4）试找出分别满足下列条件的所有二叉树。1）先序序列和中序序列相同2）中序序列和后序序列相同3）先序序列和后序序列相同【南京航空航天大学2001二、（10分)】（5）找出所有满足下列条件的二叉树：1（3）找出所有的二叉树，其结点在下列两种遍历下，恰好都是以同样的顺序出现：
1）前序遍历和中序遍历。
2）前序遍历和后序遍历。【南京航空航天大学 1995 六(5分)】 （4）试找出分别满足下列条件的所有二叉树。 1）先序序列和中序序列相同
2）中序序列和后序序列相同
3）先序序列和后序序列相同
【南京航空航天大学 2001 二、（10分)】 （5）找出所有满足下列条件的二叉树： 1）它们在先序遍历和中序遍历时，得到的结点访问序列相同； 2）它们在后序遍历和中序遍历时，得到的结点访问序列相同； 3）它们在先序遍历和后序遍历时，得到的结点访问序列相同；【东南大学2000一、4(6分）】 44．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）
【南京航空航天大学 1998 一、 (10分)】 45. 阅读下列说明和流程图，回答问题（1）和问题（2）。 说明：流程图是用来实现中序遍历，二叉树存放在数组tree中，每个数组元素存放树中一个结点，每个
结点的形式为（值，左指针，右指针），分别用tree[i].v，tree[i].l，tree[i].r来表示第i个结点的值，左指针，右指针，其中左，右指针的值为所指结点在数组中的下标，若指针的值为0，表示它指向空树，图中指针root用以指向二叉树的根结点。问题：
（1）填充流程图中的①、②、③，使其按中序遍历二叉树。 （2）把流程图中的（A）框移至哪个位置（图中Ⅰ～Ⅸ）使流程图的算法从中序遍历变成后序遍历。 【上海海运学院 1997年四、（13分）】 46．设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列： A B D F C E G H
中序遍历序列： B F D A G E H C （1）画出这棵二叉树。 （2）画出这棵二叉树的后序线索树。
（3）将这棵二叉树转换成对应的树（或森林）。【南京航空航天大学 1997 二、 (10分)】 47．已知一棵二叉树的对称序和后序序列如下： 对称序：GLDHBEIACJFK
LGHDIEBJKFCA (1)
(1) （2分)给出这棵二叉树： (2)
(2) （2分)转换为对应的森林： (3)
(3) （4分)画出该森林的带右链的先根次序表示法：
(4) (4分) 画出该森林带度数的后根次序表示法： (5) (4分)在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。写出以结点x为根的子树在后根次序序列中的前驱的求法。（用语言叙述，不用写算法）【山东大学 1998 八、（16分）】 48．设某二叉树的前序遍历序列为:ABCDEFGGI，中序遍历序列为:BCAEDGHFI： （1）试画出该二叉树； （2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。 （3）设具有四个结点的二叉树的前序遍历序列为ａｂｃｄ；Ｓ为长度等于四的由ａ，ｂ，ｃ，ｄ排列构成的字符序列，若任取Ｓ作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。
【浙江大学 1997 六、 (15分)】 类似本题的另外叙述有： （1）已知二叉树的先序序列:
中序序列: HBGEACF, 试构造该二叉树 【北京理工大学 2001 八、2 （4分）】 （2）已知二叉树按中序排列为BFDAEGC，按前序排列为ABDFCEG，要求画出该二叉树。 【山东师范大学 1996
五、1 (2分)】 （3）已知一棵二叉树的前序序列 A,B,D,C,E,F，中序序列B,D,A,E,F,C. 画出这棵二叉树。 【燕山大学 1999 四、 (5分)】 （4）已知一棵二叉树的前序遍历结果是：ABCDEFGHIJ,中序遍历的结果是：BCEDAGHJIF,试画出这棵二叉树。【厦门大学 1998 六、1 （7分)】 （5）已知二叉树BT各结点的先序、中序遍历序列分别为ABCDEGF和CBAEDF，试画出该二叉树。 【北京工业大学 1998 二、 (6分)】 49. 假设一棵二叉树的前序序列为ABCD,它的中序序列可能是DABC吗?【石油大学1998一、1(5分)】 类似本题的另外叙述有： （1）一棵前序序列为1，2，3，4，的二叉树，其中序序列可能是4，1，2，3吗？设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树。 【东南大学 1996一、2 （7分)
1998 一、3】 50．一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。 【西安电子科技大学2000软件一、8 （5分）】 51．已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。【重庆大学 2000
二、2】 类似本题的另外叙述有： （1）已知二叉树ＢＴ各结点的中序和后序序列分别为ＤＦＢＡＣＥＧ和ＦＤＢＧＥＣＡ，试构造出该二叉树ＢＴ，并作简要说明。【北方交通大学 1997 二、 (8分)】 （2）已知二叉树的中序遍历序列为G F B E A N H M，后序遍历的结点序列为G E B F H N M A ，画出此二叉树的形态。【青岛海洋大学 1999 一、5（5分)】 （3）已知二叉树的后序序列为ABCDEFG 和中序序列为ACBGEDF，构造出该二叉树。 【福州大学 1998 三、1 (6分)】 （4）已知某二叉树的后序遍历和中序遍历如下，构造出该二叉树。 后序遍历序列： G D B E I H F C A
中序遍历序列：D G B A E C H I F 【厦门大学 2000 七、1 （20%/3分)】 （5）已知一个二分树的中序序列和后序序列如下： 中序：A B C D E F G H I J
后序：A C D B H J I G F E
试画出此二分树的结构。 【首都经贸大学 1998 二、1 （10分）】 52．假设一棵二叉树的层次序列为ABCDEFGHIJ，中序序列DBGEHJACIF。请画出这棵二叉树。 【武汉大学 2000 三、1】【东南大学 2000 一、1 （6分）】 类似本题的另外叙述有： （1）假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。【山东大学 2001 四、 (6分)】 53. 已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK
【合肥工业大学 2000 四、1 （5分）】 54． 画出同时满足下列两条件的两棵不同的二叉树。
(1)按先根序遍历二叉树顺序为ABCDE。
(2)高度为5其对应的树（森林）的高度最大为4。【东北大学 1997 一、3 （5分）】 55．用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。 【西安电子科技大学1999计应用一、6 （5分）】 56．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。 先序序列 ：_ _ C D E _ G H I _ K
中序序列 ：C B _ _ F A _ J K I G 后序序列 ：_ E F D B _ J I H _ A
【厦门大学 2002 七、1 （6分)】 类似本题的另外叙述有： （1）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分为显示出来。试求出空格处的内容，并画出该二叉树。
先序序列: _ B
中序序列：D
后序序列：
【西安电子科技大学2000计应用
五、2 （5分)】 （2）已知一棵二叉树的先序 中序和后序序列如下，其中空缺了部分，请画出该二叉树。 先序：_ B C _ E F G _ I J K _ 中序：C B E D _ G A J _ H _ L 后序：_ E _ F D _ J _ L _ H A
【合肥工业大学 2001 四、1 （5分)】 （3）已知含有8个结点的一棵二叉树，按先序、中序、后序进行遍历后，有些结点序号不清楚如下图示。要求构造出一棵符合条件的二叉树。 先根序遍历
_ 2 3 _ 5 _ 7 8 中根序遍历
3 _ 4 1 _ 7 8 6 后根序遍历
_ 4 2 _ _ 6 5 1
【东北大学 1996 一、3 （5分）】 57．M 叉树的前序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应？ 【中国人民大学 2000 一、2 （4分）】 58．证明：在二叉树的三种遍历序列中，所有叶子结点间的先后关系都是相同的。要求每步论断都指出根据。【北京工业大学 2001 二、3 （5分）】 59. 下表中MpN分别是一棵二叉树中的两个结点，表中行号i=1，2，3，4分别表示四种MpN的相对关系，列号j=1，2，3分别表示在前序、中序、后序遍历中M,N之间的先后次序关系。要求在i，j所表示的关系能够发生的方格内打上对号。例如：如果你认为n是m的祖先，并且在中序遍历中n能比m先被访问，则在（3，2）格内打上对号
先根遍历时n先被访问 中根遍历时n先被访问 后根遍历时n先被访问 N在M的左边
N在M的右边
N是M的祖先
N是M的子孙
【南京理工大学 2001 四、 (10分)】
60．用一维数组存放的一棵完全二叉树如下图所示：
A B C D E F G H I J K L 写出后序遍历该二叉树时访问结点的顺序。 【北京工业大学 1996 一、4 （6分）】 61．设树形T在后根次序下的结点排列和各结点相应的次数如下： 后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡ 次
数：００００３０００２０２４ 请画出Ｔ的树形结构图。 【吉林大学 2001 一、2 （4分）】 62．已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成？请简述原因。【西北大学 2001
6】 63．对于二叉树T的两个结点n1和n2，我们应该选择树T结点的前序、中序和后序中哪两个序列来判断结点n1必定是结点n2的祖先,并给出判断的方法。不需证明判断方法的正确性。 【复旦大学 1999 五 (10分)】 64．设二叉树的存储结构如下(每题5分,共15分)
0 其中,T为树根结点的指针,LLINK、RLINK分别指向结点的左右子女,INFO为其数据域,请完成下列各题: （1）画出二叉树T的逻辑结构. （2）写出按前序、中序和后序周游二叉树T得到的结点序列. （3）画出二叉树T的后序线索树。
【山东工业大学 1995 六、（15分）】 65．在二叉树的前序遍历和中序遍历的递归算法中，最后一个递归调用语句在调用时所保留的参数有什么作用？如何清除最后这个递归语句？【北京邮电大学 1994 三、 (8分)】 66．在二叉树的Ｌlink-Rlink存储表示中，引入“线索”的好处是什么？ 【山东大学 1999 六、１(２分）】 67．按下面要求解下图中二叉树的有关问题：
(1)对此二叉树进行后序后继线索化 ；(2)将此二叉树变换为森林； (3)用后根序遍历该森林，；写出遍历后的结点序列。【北京邮电大学 1996 五、 (10分)】 类似本题的另外叙述有： （1）已知一棵二叉树的先序遍历序列为：AEFBGCDHIKJ，中序遍历序列为：EFAGBCHKIJD。试写出此二叉树的后序遍历序列，并用图画出它的后序线索二叉树。【同济大学 2000 一、 (10分)】 68．对下图所示二叉树分别按前序p中序p后序遍历， 给出相应的结点序列，同时给二叉树加上中序线索。 【青岛海洋大学 1999年一、1 （5分）】
第67题图 69. 假设一个二叉树的两种遍历如下： 前序：ABFGCHDEIJLK
中序：FGBHCDILJKEA （1）画出这棵二叉树以及它的中序线索树； （2）写出在中序线索树的情况下，找到结点N的前驱结点的算法INORDER-PRIOR(N,X) 【上海海运学院 1996 四、 (10分)】 70．已知一棵二叉树的中序（或中根）遍历结点排列为DGBAECHIF，后序（或后根）遍历结点排列为GDBEIHFCA， （1）试画出该二叉树； （2）试画出该二叉树的中序穿线（或线索）树； （3）试画出该二叉树（自然）对应的森林；【吉林大学 2000 一、1 （5分）】 71．设二叉树BT的存储结构如下:
Lchild Data Rchild
0 其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。试完成下列各题: （l）画出二叉树BT的逻辑结构; （2）写出按前序、中序、后序遍历该二叉树所得到的结点序列; （3）画出二叉树的后序线索树。【中国矿业大学 2000 二、 (15分)】 72．请说明是否存在这样的二叉树，即它可以实现后序线索树进行后序遍历时不使用栈；而对前序线索树进行前序遍历时，又有什么样的二叉树可不使用栈。【西安电子科技大学 1996 二、1 (5分）】 73．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？ 【西安电子科技大学 2000计应用 一、2 （5分）】 74．在前序线索树上，要找出结点p的直接后继结点，请写出相关浯句。结点结构为(ltag,lc,data,rtag,rc)。【西北大学 2000 二、6 （5分）】 75．对于后序线索二叉树，怎样查找任意结点的直接后继；对于中序线索二叉树，怎样查找任意结点的直接前驱？【西北工业大学 1998 一、4 （4分）】 76．将下列树的孩子―兄弟链表改为后根遍历全线索链表。【清华大学 1994 二、 (10分)】
Data A Ltag 0 Fch 2 Rtag 0 Nsib 0 B 0 0 0 3 C 0 5 0 4 D 0 7 0 0 E 0 8 0 6 F 0 0 0 0 G 0 11 0 0 H 0 0 0 9 I 0 0 0 10 J 0 0 0 0 K 0 0 0 0 77. 已知一棵二叉树的前序遍历为ABECDFGHIJ，中序遍历为EBCDAFHIGJ。试画出这棵树和它的中序线索树。假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。【上海海运学院1998四(10分)】 包含总结汇报、资格考试、专业文献、IT计算机、文档下载、考试资料、计划方案、教学教材、旅游景点以及树和二叉树笔试题等内容。本文共5页
相关内容搜索