数据结构 第6章 树和二叉树 下载本文

指向其前驱;rflag=0,right 指向其右孩子,rflag=1,right 指向其后继。

prior(node,x)

{ if (node !=null)

if ((1)_____ ) *x=node->right; else *x=node->left; }

next(bt, node, x) /*bt是二叉树的树根*/ {(2)_____;

if (node!=bt && node!=null)

if (node->rflag) (3)_______ ;

else {do t=*x; (4)_______;while (*x==node); *x=t; } } 【南京航空航天大学 1996 十、 (8分)】

四、应用题

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(n>0)个结点的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分)】

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. 已知A[1..N]是一棵顺序存储的完全二叉树,如何求出A[i]和A[j]的最近的共同祖先?

【中国人民大学 2001 二、5 (4分)】

15.给定K(K>=1),对一棵含有N个结点的K叉树(N>0)、请讨论其可能的最大高度和最小高度。

【大连海事大学 2001 五、 (8分)】 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)试证明

?2i?1n?(li?1)=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 九、 (8分)】 类似本题的另外叙述有: