发布时间 : 星期日 文章计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编8更新完毕开始阅读
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编
8
(总分：66.00，做题时间：90分钟)
一、 填空题(总题数：22，分数：44.00)
1.设一棵完全二叉树叶子结点数为k，最后一层结点数>2，则该二叉树的高度为__________。【北京科技大学1998一、3】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：[log 2 k]+1) 解析：
2.已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是__________。【东南大学2005数据结构部分二、7(1分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：235。参见上面一、2的分析。) 解析：
3.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点编号为0，则编号为50的结点的右孩子编号为__________。【中南大学2005二、l(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：102。假定编号为i的结点的左右孩子存在，左孩子的编号是2*i+1，右孩子的编号是2*i+2。) 解析：
4.高度为i(i≥1)的完全二叉树最多有__________个结点；最少有__________个结点；若按自上而下，从左到右的次序给结点编号(从1开始)，则编号最小的叶子结点的编号为__________。【大连理工大学2005一、2(3分)】【江苏大学2006二、3(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)2 -1 (2)2 (3)[n／2]+1(设n是完全二叉树的结点数)) 解析：
5.对于一个具有n个结点的二叉树，当它为一棵(1)二叉树时具有最小高度，当它为一棵(2)时，具有最大高度。【哈尔滨工业大学2001一、3(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)完全 (2)只有一个叶子结点的二叉树) 解析：
6.n(n大于1)个结点的各棵树中，其深度最小的那棵树的深度是(1)。它共有(2)个叶子结点和(39)个非叶子结点，其中深度最大的那棵树的深度是(4) ，它共有(5)个叶子结点和(6)个非叶子结点。【山东大学2001三、7(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)2 (2)n一1 (3)1 (4)n (5)1 (6)n一1) 解析：
t
i-1
7.在树的孩子兄弟表示法中，二叉链表的左指针指向__________，右指针指向__________。【北京理工大学2006十、3(1分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)结点的第一个孩子 (2)结点的右兄弟) 解析：
8.设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B，已知T1、T2、T3的结点数分别为n1、n2和，n3，则二叉树B的左子树中有 (1)个结点，右子树中有 (2)个结点。【南京理工大学2000二、9(3分)】
（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)n1－1 (2)n2+n3) 解析：
9.先序遍历森林时，首先访问森林中第一棵树的__________。【中山大学2005】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：根结点) 解析：
10.设森林F对应的二元树为B，它有m个结点，B的根为P，P的右子树结点个数为n，则森林，中第一棵树的结点个数是__________。【哈尔滨工业大学2005一、8(1分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：m一n) 解析：
11.一个深度为七的，具有最少结点数的完全二叉树按层次，(同层次从左到右)用自然数依此对结点编号，则编号最小的叶子的序号是(1)；编号是f的结点所在的层次号是(2)(根所在的层次号规定为1层)。【南京理工大学2001二、2(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)2 +1(第k层1个结点，总结点个数是2 ，其双亲是2 ／2=2 )(2)[log
2
k－2
k-1
k-1
k-2
i]／+1本题(1)也可以这样分析：深度为k且具有最少结点数的完全二叉树，第k层只有一个结点，第
k-2
k-2
k-1层是满的，最左边的结点度为1，其右兄弟就是编号最小的叶子结点。而第k-2层最右边结点的编号是2 －1。所以，最小叶子结点的编号是(2 一1)) 解析：
12.将一棵结点编号(从上到下，从左至右)为1到7的满二叉树转变成森林，则中序遍历该森林得到的序列为__________。【北京工业大学2005二、5(3分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：4，2，5，1，6，3，7。说明：题中“中序遍历该森林”多数教材使用“后序遍历该森林”。) 解析：
13.每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，对称序列是FEBGCHD，则它的后序序列是(1)。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是(2)。【山东工业大学1997二(6分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)FEGHDCB (2)BEF(该二叉树转换成森林，含三棵树，其第一棵树的先根次序是BEF)) 解析：
14.前序遍历树林正好等同于按(1)遍历对应的二叉树，后序遍历树林正好等同于按(2)遍历对应的二又树。【山东工业大学1999二、1(4分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)前序 (2)中序) 解析：
15.二叉树的先序序列和中序序列相同的条件是__________。【合肥工业大学2000三、7(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：任何结点至多只有右子女的二叉树) 解析：
16.已知一棵二叉树的前序序列为abdecfhg，中序序列为dbeahfcg，则该二叉树的根为(1)，左子树中有(2)，右子树中有(3)。【南京理工大学1996二、1(6分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)a (2)dbe (3)hfcg) 解析：
17.设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用“．”表示，现前序遍历二叉树，访问的结点的序列为ABDG…CE．H．F．，则中序遍历二叉树时，访问的结点序列为(1)；后序遍历二叉树时，访问的结点序列为(2)。【南京理工大学1999二、3(4分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1).D.G.B.A.E.H.C.F (2)…GD.B…HE..FCA) 解析：
18.设某二叉树的先序遍历序列为abcdefgh，中序遍历序列为dgbaechf,，则其后序遍历序列为__________。【北京交通大学2006二、5(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：gdbehfca) 解析：
19.某二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是__________。【中科院研究生院2005二、6(1分)】【东南大学2005数据结构部分二、6(1分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：cedba) 解析：
20.在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是__________。【中国人民大学2001一、4(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：双亲的右子树中最左下的叶子结点) 解析：
21.一棵左子树为空的二又树在先序线索化后，其中的空链域的个数为__________。【厦门大学2002六、1(4分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：2) 解析：
22.设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y，y的右子树高度是3l，x是y的左孩子。则确定x的后继最多需经过__________中间结点(不含后继及x本身)。【南京理工大学2000二、8(1．5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：31(x的后继是经x的双亲y的右子树中最左下的叶结点)) 解析：
二、 综合题(总题数：8，分数：22.00)
23.从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。【西安电子科技大学2001软件二、1(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：树的孩子兄弟链表表示法和二叉树二叉链表表示法本质上是一样的，只是解释不同，也就是说，树(树是森林的特例，即森林中只有一棵树的特殊情况)可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林的问题。树和二又树均属于树形结构，其区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空(一些教材上考虑到与二叉树的转换，允许树为空)。二叉树不是树的特例。) 解析：
24.请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。【大连海事大学2001三(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲(根无双亲)，从这个意义上说，存在一(双亲)对多(子女)的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为线性结构：度为1的树，以及广义表中的元素都是原子时。另外，广义表中同层(最高层是用逗号分隔的)元素之间的关系可看成前驱和后继，也符合线性表中元素间的逻辑关系，但这时元素有原子，也有子表，即元素并不属于同一数据对象。) 解析：
25.设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值?【中国人民大学2001二、3(4分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：方法有二。一是对该算术表达式(二叉树)进行后序遍历，得到表达式的后序遍历序列，即后缀表达式，可对其求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(+、一、*、／等)进行最后求值。) 解析：
26.将算术表达式((a+b)+c (d+e)+f) (g+h)转化为二叉树。【天津大学2003一、3(8分)】【东南大学2003二(7分)】【东北大学2000三、1(4分)】≠ （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：该算术表达式转化的二叉树如右图所示。解析：
27.试分别画出表示下列两个表达式的二叉树。【华中科技大学2006三、1(6分)】(1)a一b+c (2)a+(b一c)／d—e*f （分数：2.00）
) *
*