2022年树和二叉树笔试题文件 .pdf

树和二叉树笔试题GSM 全球移动通信系统概述树和二叉树学习2009-12-10 17:34:37 阅读 1252 评论 0 字号：大中小订阅四、应用题1从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么， 并指出树和二叉树的主要区别。【西安电子科技大学2001 软件二、1 （ 5 分） 】2树和二叉树之间有什么样的区别与联系？【西北工业大学1998 一、 3(4 分)】 【厦门大学2000 五、 2(14%/3 分)】 【燕山大学2001 三、1(5 分)】3请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。【大连海事大学2001 三(10 分)】4. 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？【中国人民大学2001 二、 3(4 分） 】5将算术表达式（ （a+b）+c*(d+e)+f ）*(g+h) 转化为二叉树。 【东北大学2000 三、 1 （4分） 】6. 一棵有 n(n0)个结点的d 度树, 若用多重链表表示, 树中每个结点都有d 个链域 , 则在表示该树的多重链表中有多少个空链域? 为什么 ? 【长沙铁道学院1998 四、 1 (6 分)】7. 一棵二叉树中的结点的度或为0 或为 2，则二叉树的枝数为2(n0-1)，其中 n0 是度为 0 的结点的个数。【南京理工大学1998 六、(3 分)】类似本题的另外叙述有：（1）若二叉树中度为1 的结点数为0，则该二叉树的总分支数为2（ n0-1） ，其中 n0 为叶结点数。【西北工业大学1998 三、 1（5 分） 】8一个深度为L 的满 K 叉树有以下性质：第 L 层上的结点都是叶子结点，其余各层上每个结点都有K 棵非空子树，如果按层次顺序从1 开始对全部结点进行编号，求：1）各层的结点的数目是多少？2）编号为 n 的结点的双亲结点（若存在）的编号是多少？3）编号为n 的结点的第i 个孩子结点（若存在）的编号是多少？4）编号为n 的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？请给出计算和推导过程。【西北工业大学1999 五(10 分)】 【中科院自动化所1996 二、 1(10分)】类似本题的另外叙述有：（1）一棵高度为h 的满 k 叉树有如下性质：根据结点所在层次为0；第 h 层上的结点都是叶子结点； 其余各层上每个结点都有k 棵非空子树， 如果按层次自顶向下，同一层自左向右,顺序从 1 开始对全部结点进行编号，试问：1)各层的结点个数是多少?(3 分) 2)编号为 i 的结点的双亲结点（若存在）的编号是多少?(3分) 3)编号为 i 的结点的第m 个孩子结点（若存在）的编号是多少？（3 分）4)编号为 i 的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？（3 分) 【清华大学1999 八 (12 分)】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 21 页 - - - - - - - - - 9证明任一结点个数为n 的二叉树的高度至少为O(logn). 【浙江大学2000 四、(5 分)】10有 n 个结点并且其高度为n 的二叉树的数目是多少? 【西安电子科技大学2000 计应用一、 3(5 分)】11已知完全二叉树的第七层有10 个叶子结点，则整个二叉树的结点数最多是多少？【西安电子科技大学2000 计应用一、 4 （ 5 分） 】12高度为10 的二叉树，其结点最多可能为多少？【首都经贸大学1998 一、 1 （4 分） 】13任意一个有n 个结点的二叉树，已知它有m 个叶子结点，试证明非叶子结点有（m-1）个度为 2，其余度为1。 【西安电子科技大学2001 计应用二、 3 （5 分） 】14. 已知 A1.N 是一棵顺序存储的完全二叉树，如何求出Ai 和 Aj 的最近的共同祖先？【中国人民大学2001 二、 5 （4 分） 】15给定 K(K=1), 对一棵含有N 个结点的K 叉树（N） 、请讨论其可能的最大高度和最小高度。【大连海事大学2001 五、(分 )】16已知一棵满二叉树的结点个数为20 到 40 之间的素数， 此二叉树的叶子结点有多少个？【东北大学1999 一、 1 （3 分） 】17一棵共有n 个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。【东北大学2000 一、 3 （4 分） 】18如在内存中存放一个完全二叉树，在树上只进行下面两个操作：（1）寻找某个结点双亲（2）寻找某个结点的儿子；请问应该用何种结构来存储该二叉树？【东北大学2001 一、 3 （3 分） 】19求含有 n 个结点、 采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。 【北京工业大学2000 二、 3 （ 5 分） 】20设二叉树T 中有 n 个顶点，其编号为1，2，3， ,n,若编号满足如下性质：（1）T 中任一顶点v 的编号等于左子树中最小编号减1；（2）对 T 中任一顶点v,其右子树中最小编号等于其左子树中的最大编号加1。试说明对二叉树中顶点编号的规则（按何种顺序编号）。 【山东大学1992 一、 1 （3 分） 】21 若一棵树中有度数为1 至 m 的各种结点数为n1,n2, ,nm(nm 表示度数为m 的结点个数 )请推导出该树中共有多少个叶子结点n0 的公式。【北京邮电大学1993 二 1(6 分)】 【西安交通大学 1996 四、1(5 分)】 【南京航空航天大学1998 五(10 分)】 【东南大学1999 一 4（8 分)】【山东大学1993 一 2(4 分)】【山东师范大学2001 二 3(12 分 ) 2001 二 2(15 分 )】22若一棵完全二叉树中叶子结点的个数为n,且最底层结点数2，则此二叉树的深度H=？【北京科技大学2001 一、 6 （2 分） 】23已知完全二叉树有30 个结点，则整个二叉树有多少个度为0 的结点？【山东师范大学1996 五、 3(2 分 )】24在一棵表示有序集S 的二叉搜索树 (binary search tree)中,任意一条从根到叶结点的路径将 S 分为 3 部分：在该路径左边结点中的元素组成的集合Sl；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S=S1S2S3。若对于任意的 aSl,bS2， cS3 是否总有abc?为什么 ? 【清华大学2000 四(10 分 )】【武汉大学2000 三、 3】25试证明 ,在具有 n(n=1) 个结点的 m 次树中 ,有 n(m-1)+1 个指针是空的。 【复旦大学1998四(8 分)】26对于任何一棵非空的二叉树,假设叶子结点的个数为n0,而次数为2 的结点个数为n2,请给出 n0 和 n2 之间所满足的关系式n0=f(n2). 要求给出推导过程。【复旦大学1998 五 (8 分)】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 21 页 - - - - - - - - - 27对于任意一棵非空的二叉树T，我们用n0 表示 T 中叶子结点的个数，用n2 表示 T 中有两棵非空子树的结点的个数。（1）给出 n0 和 n2 所满足的关系式。 （2）证明你在（ 1）中给出的关系式成立。【复旦大学1997 三 (10 分)】28试求有n 个叶结点的非满的完全二叉树的高度;【中科院计算所2000 五、(5 分)】29对于具有n 个叶子结点，且所有非叶子结点都有左右孩子的二叉树，(1)试问这种二叉树的结点总数是多少？（5 分）(2)试证明=1。其中 :li 表示第 i 个叶子结点所在的层号(设根结点所在层号为1)。(10 分) 【北方交通大学1995 三、(15 分)】30假设高度为H 的二叉树上只有度为0 和度为2 的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少？【北京邮电大学1996 一、 1 （4 分） 】31一棵满k 叉树，按层次遍历存储在一维数组中，试计算结点下标的u 的结点的第i 个孩子的下标以及结点下标为v 的结点的父母结点的下标。【北京邮电大学2001 四、 4(5 分） 】32二叉树有n 个顶点，编号为1， 2，3， ，n，设：* T 中任一顶点V 的编号等于左子树中最小编号减1；* T 中任一顶点V 的右子树中的最小编号等于其左子树中的最大编号加1；试描绘该二叉树。 【东南大学1999 一、 2 （7 分） 】33设 T 是具有 n 个内结点的扩充二叉树，I 是它的内路径长度，E 是它的外路径长度。（1）试利用归纳法证明E=I+2n, n=0.（5 分 ) （2）利用（ 1）的结果试说明：成功查找的平均比较次数s 与不成功查找的平均比较次数u 之间的关系可用公式表示s=(1+1/n)u-1,n=1 。 【清华大学1998 四、(10 分)】34一棵非空的有向树中恰有一个顶点入度为0, 其它顶点入度为1,但一个恰有一个顶点入度为 0,其它顶点入度为1 的有向图却不一定是一棵有向树,请举例说明。 【中科院计算所1999 三、 1 （5 分） 】35试给出下列有关并查集（mfsets）的操作序列的运算结果：union(1,2),union(3,4),union(3,5),union(1,7),union(3,6),union(8,9), union(1,8),union(3,10),union(3,11),union(3,12),union(3,13), union(14,15),union(16,0),union(14,16),union(1,3),union(1,14). (union 是合并运算，在以前的书中命名为merge) 要求（1）对于 union(i,j), 以 i 作为 j 的双亲；（5 分) （2）按 i 和 j 为根的树的高度实现union(i,j), 高度大者为高度小者的双亲；（5 分) （3）按 i 和 j 为根的树的结点个数实现union(i,j), 结点个数大者为结点个数小者的双亲。（5分) 【清华大学2001 一、 (15 分)】36证明：在任何一棵非空二叉树中有下面的等式成立：叶结点的个数=二度结点的个数+1 【天津大学1999 四】37. 对于一个堆栈，若其入栈序列为1，2，3，n，不同的出入栈操作将产生不同的出栈序列。 其出栈序列的个数正好等于结点个数为n 的二叉树的个数， 且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入（固定为1，2，3n ） /输出序列对应一种二叉树形态的方法，并以入栈序列1，2，3（即 n=3）为例加以说明。 【浙江大学1998 年 五、 1 (7分)】38. 如果给出了一个二叉树结点的前序序列和对称序序列，能否构造出此二叉树?若能，请名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 21 页 - - - - - - - - - 证明之。 若不能， 请给出反例。 如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树 ?若能，请证明之。若不能，请给出反例。【北京大学1998 二、 2 （5 分)】类似本题的另外叙述有：（1） 二叉树的中序与后序序列能唯一地定义一棵二叉树吗? 这里所指序列中的符号代表树结点中的标识符吗？二叉树的前序与后序序列能唯一地定义一棵二叉树吗?为什么 ? 【东南大学 1993 一、 4（8 分） 】39试证明 :同一棵二叉树的所有叶子结点，在前序序列。对称序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如前序abc,后序 bca 对称序 bac。 【山东工业大学 1997 七、(10 分)】40. 由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是否也能唯一的建立二叉树，不能则说明理由， 若能对中序序列DBEAFGC 和后序序列DEBGFCA构造二叉树。【南京理工大学1998 四、(3 分)】41. 证明，由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH ，中序序列为： DGBEAFHC 。试画出该二叉树。 【浙江大学1996 六、(8 分)】类似本题的另外叙述有：(1) 证明：由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。【长沙铁道学院1997 五、 2(10 分)】（2）证明：由二叉树的中序遍历序列和后序遍历序列可唯一地确定出该二叉树。【华南理工大学2001 一、 3 （4 分)】（3）二叉树已知其中序扫描序列和后序扫描序列如何确定这一棵二叉树,并举例说明 . 【山东大学2001 软件与理论二、1 （4 分） 】42试证明： 仅仅已知一棵二叉树的后序遍历序列和先序遍历序列，不能唯一地确定这棵二叉树。【大连海事大学2001 九、 (分 )】类似本题的另外叙述有：(1) 由二叉树的前序遍历和后序遍历结果能否唯一确定一棵二叉树？解释你的论断。【西安电子科技大学2001 计应用二、4 （5 分） 】(2) 假定某二叉树的前序遍历序列为ABCDEFGHIJ, 后序遍历序列为CEFDBJIHGA, 据此两个序列能否唯一确定此二叉树? 若不能 ,试画出两样具有同样上述遍历序列的二叉树.【武汉交通科技大学1996 二 8（3 分） 】43. 试找出满足下列条件的二叉树1）先序序列与后序序列相同2）中序序列与后序序列相同3）先序序列与中序序列相同4）中序序列与层次遍历序列相同 已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和 DEBHIFGCA ，画出这棵二叉树。【东北大学1999 六、 (4 分)】类似本题的另外叙述有：（1）试画出在先根次序和中根次序下结点排列顺序皆相同的所有类型的二叉树形。试画出在先根次序和后根次序下结点排列顺序皆相同的所有类型的二叉树形。【吉林大学1995 四、 1,2 （每题 7 分)】（2）找出所有的二叉树，其结点在下列两种遍历下恰好都有同样的遍历序列。1）先序遍历和中序遍历2）先序遍历和后序遍历【北京理工大学1999 三(6 分 )】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 21 页 - - - - - - - - - （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 中，每个数组元素存放树中一个结点，每个结点的形式为（值，左指针，右指针），分别用 treei.v ，treei.l ，treei.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 分)画出该森林的带右链的先根次序表示法： Itag=(4) (4 分) 画出该森林带度数的后根次序表示法：(5) (4 分)在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。写出以结点 x 为根的子树在后根次序序列中的前驱的求法。（用语言叙述，不用写算法）【山东大学名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 21 页 - - - - - - - - - 1998 八、 （16 分） 】48设某二叉树的前序遍历序列为:ABCDEFGGI ，中序遍历序列为:BCAEDGHFI ：（1）试画出该二叉树；（2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。（3）设具有四个结点的二叉树的前序遍历序列为；为长度等于四的由，排列构成的字符序列，若任取作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。【浙江大学1997 六、 (15 分)】类似本题的另外叙述有：（1）已知二叉树的先序序列: CBHEGAF, 中序序列 : 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 分） 】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 21 页 - - - - - - - - - 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 F I C E H G 中序序列： D K F I A E J C 后序序列： K F B H J G A【西安电子科技大学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. 下表中 MN 分别是一棵二叉树中的两个结点，表中行号i=1，2，3，4 分别表示四种MN 的相对关系，列号j=1，2，3 分别表示在前序、中序、后序遍历中M,N 之间的先后次序关系。 要求在 i，j 所表示的关系能够发生的方格内打上对号。例如：如果你认为n 是 m的祖先，并且在中序遍历中n 能比 m 先被访问，则在（3，2）格内打上对号先根遍历时n 先被访问 中根遍历时n 先被访问 后根遍历时n 先被访问名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 21 页 - - - - - - - - - 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 分 ) LINK 0 0 2 3 7 5 8 0 10 1 INFO J H F D B AC E G I RLINK 0 0 0 9 4 0 0 0 0 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对下图所示二叉树分别按前序中序后序遍历，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 21 页 - - - - - - - - - 给出相应的结点序列，同时给二叉树加上中序线索。【青岛海洋大学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 的存储结构如下: 1 2 3 4 5 6 7 8 9 10 Lchild 0 0 2 3 7 5 8 0 10 1 Data J H F D B A C E G I Rchild 0 0 0 9 4 0 0 0 0 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 B C D E F G H I J K Ltag 0 0 0 0 0 0 0 0 0 0 0 Fch 2 0 5 7 8 0 11 0 0 0 0 Rtag 0 0 0 0 0 0 0 0 0 0 0 Nsib 0 3 4 0 6 0 0 9 10 0 0 77. 已知一棵二叉树的前序遍历为ABECDFGHIJ ，中序遍历为EBCDAFHIGJ 。试画出这棵树和它的中序线索树。假定用于通讯的电文仅有8 个字母 C1，C2，C8 组成，各个字母在电文中出现的频率分别为5，25， 3，6，10，11，36，4，试为这8 个字母设计哈夫曼编码树。【上海海运学院1998 四(10 分)】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 21 页 - - - - - - - - - 78设有正文AADBAACACCDACACAAD,字符集为A,B,C,D, 设计一套二进制编码，使得上述正文的编码最短。 【首都经贸大学1997 一、 5 （4 分)】类似本题的另外叙述有：（1）设有正文MNOPPPOPMMPOPOPPOPNP ，字符集为M，N，O，P，设计一套二进制编码，使得上述正文的编码最短。【首都经贸大学1998 一、 5 （4 分） 】79给定集合 15,3,14,2,6,9,16,17 (1)（3 分）用 表示外部结点，用 表示内部结点，构造相应的huffman 树：(2) (2 分)计算它的带权路径长度：(3)（3 分)写出它的huffman 编码：(4)（3 分)huffman 编码常用来译码，请用语言叙述写出其译码的过程。【山东大学1998 七、 】 【山东工业大学2000 七、(11 分)】类似本题的另外叙述有：（1）如果通信字符a,b,c,d 出现频度分别为：7，5，2，4 请画出哈夫曼树并给出相应的哈夫曼编码。【青岛大学2001 七、 1 （5 分)】（2）给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。【青岛大学2000 七、 (10 分)】（3）设通信中出现5 中字符A、 B、C、D、 E 对应的频率为0.2,0.1,0.5,0.15,0.25 构造哈夫曼树，并给出对应字符的编码。【青岛大学2002 四、 2 （10 分） 】（4） 设 A、B、C、D、E、F 六个字母出现的概率分别为7,19,2,6,32,3 。试写出为这六个字母设计的HUFFMAN编码 , 并画出对应的HUFFMAN 树.【山东工业大学1995 四(10 分)】（ 5 ） 设 用 于 通 信 的 电 文 由8 个 字 母 组 成 , 字 母 在 电 文 中 出 现 的 频 率 分 别为:7,19,2,6,32,3,21,10 。试为这8 个字母设计哈夫曼编码.使用 0-7 的二进制表示形式是另一种编码方案 ,试比较这两种方案的优缺点。【南京航空航天大学1999 四、 (10 分)】（6）假设用于通讯的电文由8 个字符组成，其出现的频率为5,29,7,8,14,23,3,11。试为这8个字符设计哈夫曼编码。【燕山大学1999 五、 (5 分)】（7）假设用于通信的电文由字符集a,b,c,d,e,f,g 中的字母构成。它们在电文中出现的频度分别为 0.31,0.16,0.10,0.08,0.11,0.20,0.04, 1) 为这 7 个字母设计哈夫曼编码；2）对这 7 个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？【北京邮电大学2001 四、 2 （5 分)】（8）试构造一棵二叉树,包含权为1,4,9,16,25,36,49,64,81,100 等 10 个终端结点 ,且具有最小的加权路径长度WPL。 【北方交通大学1993 年 五（ 12 分 )】（9）带权结点为5,6,7,8,9 ，构造 Huffman 树，计算带权路径长度。【西北大学2001 年三、3】（10）以数据集 2,5,7,9,13 为权值构造一棵哈夫曼树，并计算其带权路径长度。【西安电子科技大学1999 计应用一、 4 （ 5 分） 】（ 11） 假 设 用于 通 讯的 电 文仅 由8 个字 母 组成 ， 字母 在 电文 中 出 现的 频 率分 别 为7,19,2,6,32,3，21,10。试为这 8 个字母设计哈夫曼编码。使用 07 的二进制表示形式是另一种编码方案。 对于上述实例， 比较两种方案的优缺点。 【大连海事大学1996 五、2 (8 分)】 。（12）设用于通讯的电文仅由8 个字母组成，他们在电文中出现的频率分别为0.30，0.07，0.10， 0.03，0.20，0.06,0.22，0.02，试设计哈夫曼树及其编码。使用0-7 的二进制表示形式是另一种编码方案。给出两种编码的对照表、带权路径长度WPL 值并比较两种方案的优缺点。 【厦门大学1999 三、 3】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 21 页 - - - - - - - - - (13) 给定一组权值2,3,5,7,11,13,17,19,23,29 ，31， 37，41，试画出用Huffman算法建造的Huffman 树。 【吉林大学2000 一、 2 （4 分)】(14) 以数据集 3,4,5,8,12,18,20,30 为叶结点， 构造一棵哈夫曼树，并求其带权路径长度。 【山东师范大学1996 五 5(2 分)】80给定权 W1,W2, ，Wm 。说明怎样来构造一个具有最小的加权路径长度的k 叉树。试对于权1,4,9,16,25, 36,49,64,81,100 来构造最优的三叉树， 并给出其最小加权路径长度。 【北方交通大学1994 年 四(12 分） 】81已知下列字符