当前位置：首页 > 数据结构第六章考试题库（含答案）
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=S1∪S2∪S3。若对于任意的a∈Sl,b∈S2，c∈S3是否总有a≤b≤c?为什么?【清华大学 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分)】
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，3??n）/输出序列对应一种二叉树形态的方法，并以入栈序列1，2，3（即n=3）为例加以说明。【浙江大学 1998年 五、1 (7分)】
38. 如果给出了一个二叉树结点的前序序列和对称序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。【北京大学 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分)】 （3）找出所有的二叉树，其结点在下列两种遍历下，恰好都是以同样的顺序出现：
1）前序遍历和中序遍历。 2）前序遍历和后序遍历。【南京航空航天大学 1995 六(5分)】 （4）试找出分别满足下列条件的所有二叉树。
1）先序序列和中序序列相同 2）中序序列和后序序列相同 3）先序序列和后序序列相同 【南京航空航天大学 2001 二、（10分)】 （5）找出所有满足下列条件的二叉树：
1）它们在先序遍历和中序遍历时，得到的结点访问序列相同； 2）它们在后序遍历和中序遍历时，得到的结点访问序列相同； 3）它们在先序遍历和后序遍历时，得到的结点访问序列相同；【东南大学2000一、4(6分）】 44．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）
A B C D E F K H L G I J M N O
P 【南京航空航天大学 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) （2分)给出这棵二叉树： (2) （2分)转换为对应的森林：
(3) （4分)画出该森林的带右链的先根次序表示法：
Itag=
(4) (4分) 画出该森林带度数的后根次序表示法：
(5) (4分)在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。写出以结点x为根的子树在后根次序序列中的前驱的求法。（用语言叙述，不用写算法）【山东大学 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分)】
本文作者：...共分享92篇相关文档
