当前位置：首页 > 计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编7
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编
7
(总分：60.00，做题时间：90分钟)
一、 综合题(总题数：30，分数：60.00)
1.若某非空二叉树采用顺序存储结构，结点的数据信息依次存放于一个一维数组中(假设数组的第一个元素的下标为1)，下标分别为i和j的两个结点处在树中同一层的条件是__________。(i≠j≠1)【北京航空航天大学2006一、6(1分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：[logi]=[logj]。编号为i的结点的高度是[logi]+1。) 解析：
2.给定K(K≥1)，对一棵含有Ⅳ个结点的K叉树(N>0)，请讨论其可能的最大高度和最小高度。【大连海事大学2001五(8分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：N个结点的K叉树，最大高度N(只有一个叶结点的任意K叉树)。设最小高度为H，第i(1≤i≤H)层的结点数为F ，则(K +1)／(K-1) H一1)／(K-1)，由此得H=[logk(N(K-1))]+1。) 解析：
3.已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个?【东北大学1999一、1(3分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：结点个数在20到40的满二叉树且结点数是素数的数是31，该二叉树的叶子数是16。) 解析：
4.一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。【东北大学2000一、3(4分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：设分支结点和叶子结点数分别是为n k 和n 0 ，因此有 n=P／n 0 +n k (1) 另外从树的分支数B与结点的关系有 n=B+1=K*nk+1 (2) 由(1)和(2)，有n 0 =n—n k =(n(K+1)+1)／K。) 解析：
5.已知在一棵含有n个结点的树中，只有度七的分支结点和度为0的叶子结点，求该树含有的叶子结点数。【大连理工大学2005二、2(20／4分)】【江苏大学2004三、5(6分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：设分支结点和叶子结点数分别是为n k 和n 0 ，因此有 n=P／n 0 +n k (1) 另外从树的分支数B与结点的关系有 n=B+1=K*nk+1 (2) 由(1)和(2)，有n 0 =n—n k =(n(K+1)+1)／K。) 解析：
6.证明：一棵满k叉树上的叶子结点数加和非叶子结点数，m之间满足关系n0=(k-1)m+1。【北京交通大学2006四、1(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：因为n=n0+m和n=B+1=km+1，其中B为分支数。故n0+m=km+1，所以n0=(k-1)m+1。) 解析：
k+1
I+1
7.如在内存中存放一个完全二叉树，在树上只进行下面两个操作：(1)寻找某个结点双亲；(2)寻找某个结点的儿子。请问应该用何种结构来存储该二叉树?【东北大学200l一、3(3分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：用顺序存储结构存储n个结点的完全二叉树。编号为i的结点，其双亲编号是[i／2](i=时为根结点，无双亲)，其左子女是2i(若2i≤n，否则i无左子女)，右子女是2i+1(若2i+≤n，否则无右子女)。) 解析：
8.试求有n个叶结点的非满的完全二叉树的高度。【中科院计算所2000五(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：设完全二叉树中叶子结点数为n，则根据完全二叉树的性质，度为2的结点数是n一1，而完全二叉树中，度为1的结点数至多为1，所以具有n个叶子结点的完全二叉树结点数是
n+(n—1)+1=2n或2n—1(有或无度为1的结点)。由于具有2n(或2n一1)个结点的完全二叉树的深度是[log
2
(2n)]+1(或[log (2n一1)]+1)，即[log n]+1，故n个叶结点的非满的完全二叉树的高度是[log n]+1(最2 2 2
下层结点数>=2)，或log 2 n+2(最下层只一个叶结点)。) 解析：
9.已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少?【西安电子科技大学2000计算机应用一、4(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：235。由于本题求二叉树的结点数最多是多少，第7层共有2 =64个结点，已知有10个叶子，其余54个结点均为分支结点。它在第8层上有1 08个叶子结点。所以该二叉树的结点数最多可达2 一1+108=235。(注意；本题并未明说完全二叉树的高度，但根据题意，只能8层。)) 解析：
10.已知一棵完全二叉树有892个结点，试求：(1)树的高度(2)叶结点个数(3)单支结点数(4)最后一个非终端结点的序号【中国海洋大学2006五(15分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)根据公式：[log 892]+1，所以树的高度是10。 (2)根据公式：n=n0+n1+n2=2n02 一1+n1，所以叶结点数为446。 (3)根据(2)，单支结点数为1。 (4)最后一个非终端结点，即完全二叉树最后结点的双亲，序号是[892／2]=446。) 解析：
11.求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。【北京工业大学2000二、3(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：根据完全二叉树的性质，最后一个结点(编号为n)的双亲结点的编号是[n／2]，这是最后一个分支结点，在它之后是第一个叶子结点，故序号最小的叶子结点的下标是[n／2]+1。) 解析：
12.设二叉树T中有n个顶点，其编号为1，2，3，…，n，若编号满足如下性质：(1)T中任一顶点1，的编号等于左子树中最小编号减1；(2)对T中任一顶点v，其右子树中最小编号等于其左子树中的最大编号加1。试说明对二叉树中顶点编号的规则(按何种顺序编号)。【山东大学1992一、1(3分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：按前序遍历对顶点编号，即根结点从1开始，对前序遍历序列的结点从小到大编号。) 解析：
7
7-1
13.已知一棵度为M的树中有n1个度为1的结点，n2个度为2结点，…，nm个度为m的结点，证明其叶结点个数为【中国海洋大学2004五(15分)】【山东大学1993一、2(4分)】【西安交通大学1996四、
1(5分)】【东南大学1999一、4(8分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：设树的结点数为n，分支数为B，则下面二式成立： n=n +n +n +…+n (1) n=B+1=n 0 1 2 m +2n 2 +…-mn m (2) 由(1)和(2)得，叶子结点数 ) 1
解析：
14.若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，则该树一共有__________个结点。【北京航空航天大学2006一、5(1分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：78。) 解析：
15.有一非空树，其度为4，已知度为f的结点数有i个，其中1≤i<5，试问其叶结点个数是多少?【天津大学2005一、1(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：21) 解析：
16.已知二叉树有50个叶子结点，则二叉树的总结点数至少应为多少个?请给出计算过程。【中科院研究生院2004五(7分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：99。由公式n=n0+n1+n2=n0+n1+n0一1=2n0+n1-1，当n1=0时，二又树的结点数最少。) 解析：
17.下图给出了一个二叉树的顺序存储结构，其中空白表示结点不存在。请回答下列问题： (1)画出该二叉树。(2)给出该二叉树的中序序列和后序序列。（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：二叉树按完全二叉树存储，加了虚结点。二叉树略。中序序列：BADCFE，后序序列：BDFECA。) 解析：
18.下列完全二叉树共有d层及n个结点，试在下图涂黑的结点(叶结点)上标上相应的序号 (用d或n表示)。【浙江大学2004三(5分)】（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：第一个结点是编号最小的叶子结点，编号为[n／2]+1；第二个结点是d-1层最后一个，编号为2 一1；第三个结点是d层第一个结点，编号为2 ；第一个结点是d层最后一个结点，编号为n。) 解析：
d-1
d-1
【北京理工大学2007三、3(6分)】
19.一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点?有多少个度为1的结点?有多少个度为2的结点?如果完全二叉树有501个结点，结果如何?请写出推导过程。【东南大学2004一、1(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：二叉树度为2的结点n2和度为0的结点n0间有关系式n2=n0-1，且完全二叉树中度为1的结点n1至多为1，由上述关系得知完全二叉树结点间的公式n=2n0+n1-1。故当n=500时，n0=250，n1=1，n2=249;n=501时，n0=251，n1=0，n2=250。) 解析：
20.对于具有n个叶子结点，且所有非叶子结点都有左、右孩子的二叉树，(1)试问这种二叉树的结点总数是多少? (5分) (2)试证明 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)根据二叉树度为2结点个数等于叶子结点个数减1的性质，故具有n个叶子结点且非叶子结点均有左右子树的二叉树的结点数是2n-1。(2)证明：当i=1时，2
-（k-1）
。其中：l t 表示第i个叶子结点所在的层号(设根结点所在层号为1)。
(10分)【北方交通大学1995三(15分)】
=2 =1，公式成立。
0
设当i=n-1时公式成立，证明当i=n时公式仍成立。设某叶子结点的层号为t，当将该结点变为内部结点，从而再增加两个叶子结点时，这两个叶子结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶子结点，增加了两个新叶子结点，反映到公式中，因为2 明当i=n时公式仍成立。证毕。) 解析：
21.假设高度为H的二叉树上只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少?【北京邮电大学1996一、1(4分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：结点数的最大值2 －1(满二叉树)；最小值2h-1(第一层根结点，其余每层均两个结点)。) 解析：
22.一棵满k叉树，按层次遍历存储在一维数组中，试计算结点下标为“的结点的第f个孩子的下标以及结点下标为1，的结点的父母结点的下标。【北京邮电大学2001四、4(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)k(u一1)+1+i (2)[(v－2)／k+1) 解析：
23.二叉树有n个顶点，编号为1，2，3，…，n，设：T中任一顶点V的编号等于左子树中最小编号减1；T中任一顶点V的右子树中最小编号等于其左子树中的最大编号加1。试描绘该二叉树。【东南大学1999一、2(7分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：该二叉树是按前序遍历顺序编号，以根结点为编号1，前序遍历的顺序是“根一左一右”。) 解析：
24.设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分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)设n=1，则e+2*1=2(只有一个根结点时，有两个外部结点)，公式成立。 设有n个结点时，公式成立，即 E n =I n +2n (1) 现在要证明，当有n+1个结点时公式成立。 增加一个内部
h
-(t-1)
=2
-(t+1-1)
+2
-(t+1-1)
，所以结果不变，这就证
本文作者：...共分享92篇相关文档
