发布时间 : 星期三 文章计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1更新完毕开始阅读
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编
1
(总分：86.00，做题时间：90分钟)
一、 单项选择题(总题数：27，分数：54.00)
1.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。【西安交通大学1996三、2(3分)】 A.250 B.500 C.254 D.505
E.以上答案都不对 √
2.一棵124个叶结点的完全二叉树，最多有( )个结点。【中国科学技术大学1995十四、3(2分)】 A.247 B.248 √ C.249 D.250 E.251
3.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。【上海交通大学2005四、6(2分)】 A.3 11 B.3 12 C.3 13 √ D.3 14 E.其他
4.具有300个结点的二叉树，其高度至少应为( )。【北京理工大学2006五、8(1分)】 A.6 B.7 C.8 D.9 √
5.当结点数目一定时，具有最小深度的二叉树是( )。【北京航空航天大学2005】 A.满二叉树 B.完全二叉树 √ C.线索二叉树 D.二叉排序树
设结点数目是n，n个结点未必是满二叉树，A错。C和D明显错误。
6.二叉树的第I层上最多含有的结点数为( )。【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】 A.2 B.2 一1 C.2 √ D.2 一1
7.从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h层的从左到右第k个结点的编号为( )。【电子科技大学2005一、6(1分)】 A.2 +h-1 √ B.2 一k+1 C.2 +k+1 D.2 一k-1
hhhhII-1I-1I
8.下列判断中，( )是正确的。【华南理工大学2006一、2(2分)】 A.深度为k的二叉树最多有2 -1个结点(k≥1)，最少有k个结点 √ B.二叉树中不存在度大于2的结点 √
C.对二叉树遍历是指先序、中序或后序遍历中的一种 D.构造线索二叉树是为能方便找到每个结点的双亲
9.一个具有1025个结点的二叉树的高h为( )。【南京理工大学1999一、19(2分)】 A.1 1 B.10
C.11至1025之间 √ D.10至1024之间
10.一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有( )个结点。【南京理工大学2001一、11(1．5分)】【华中科技大学2007一、4(2分)】【江苏大学2004一、6(2分)】 A.2h B.2h-1 √ C.2h+1 D.h+1
11.设二叉树中有n2个度为2的结点，有，11个度为1的结点，有n0个度为0的结点，则该二叉树中空指针个数为( )。【重庆大学2005】 A.n 2 +n 1 +n 0 B.n 2 +n 1 +2n 0 C.2n 2 +n 1 D.n 1 +2n 0 √
度为2的结点没空指针，度为1的结点有一个空指针，度为0的结点(叶子)有两个空指针。 12.一棵具有n个结点的完全二叉树的树高(深度)是( )。【南京理工大学1996一、8(2分)】 A.[logn]+1 √ B.logn+1 C.[logn] D.logn-1
13.有n(n>0)个结点的二叉树的深度的最小值是( )。【华中科技大学2006一、6(2分)】 A.[log 2 (n)] B.[log 2 (n+1)] C.[log 2 (n+1)] √ D.[log 2 (n)]
14.有n个结点，并且高度为n的二叉树的数目为( )。【华中科技大学2007一、10(2分)】 A.log 2 n B.n／2 C.n D.2 √
本题相当于二叉树的第n层上至多有多少个结点。结点数、高度和层次均为n的二叉树的叶子结点有2 个不同位置，形成2 棵不同的二叉树。
15.深度为h的满m叉树的第k层有( )个结点。(1≤k≤h)【北京航空航天大学2000一、4(2分)】 A.m √ B.m -1 C.m D.m -1
16.有n(n>0)个分支结点的满二叉树的深度是( )。【华中科技大学2004一、6(1分)】 A.n 一1
B.log 2 (n+1)+1 √ C.log 2 (n+1)
2kk-1kk-1
n-1
n-1
n-1
k
D.log 2 (n一1)
17.一棵树高为k的完全二叉树至少有( )个结点。【南京理工大学1998一、3(2分)】 A.2 -1 B.2 一1 C.2 √ D.2
第k-1层以上是满二叉树，第k层只有最左边的一个叶子结点。
18.一棵深度为4的完全二叉树，最少有( )个结点。【华南理工大学2005一、1(2分)】 A.4 B.8 √ C.15 D.6
19.若某完全二叉树的结点个数为100，则第60个结点的度为( )。【西南交通大学2005】 A.0 √ B.1 C.2 D.不确定
20.若用一维数组表示一个深度为5、结点个数为10的二叉树，数组的长度至少为( )。【北京理工大学2006九、9(1分)】 A.10 B.16 C.31 √ D.64
用一维数组存储二叉树要按完全二叉树的格式存储，一般二叉树要加“虚结点”，使之成为完全二叉树的形状。深度为5的完全二叉树至多有2 一1=3 1个结点，所以数组长度要31，和题中给的结点个数为10关系不大，只要结点个数在5至31之间，分配的数组长度都一样。
21.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为( )。【南京理工大学2000一、5(1．5分)】【烟台大学2007一、13(2分)】 A.4 B.5 C.6 √ D.7
深度为h的满三叉树的结点数为N b =3 +3 +3 +…+3 =(3 一1)／2。
22.任何一棵二叉树的叶子结点在其先序、中序、后序遍历序列中的相对位置( )。【北京交通大学2006一、3(2分)】 A.肯定发生变化 B.有时发生变化 C.肯定不发生变化 √ D.无法确定
23.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序( )。【北方交通大学2001一、25(2分)】 A.都不相同 B.完全相同 √
C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同
24.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。【北京理工大学2000一、4(2分)】【南开大学2005】 A.先序
0
1
3
h-1
h
5
kk-1k-1k
B.中序 C.后序 √
D.从根开始按层次遍历
25.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。【北京航空航天大学1999一、4(2分)】 A.前序 √ B.中序 C.后序 √ D.按层次
本题A和C均可。采用递归遍历：A是若二叉树非空，则交换左右子树，再先序递归交换左子树，先序递归交换右子树。C是若二叉树非空，后序递归交换左子树，后序递归交换右子树，最后交换根结点的左右子树。
26.下面不能唯一确定一棵二叉树的两个遍历序列是( )。【北京理工大学2006九、10(1分)】 A.先序序列和中序序列 B.先序序列和后序序列 √ C.后序序列和中序序列 D.都不能
27.根据( )可以唯一地确定一棵二叉树。【北京理工大学2005一、8(1分)】 A.先序遍历和后序遍历 B.先序遍历和层次遍历 C.中序遍历和层次遍历 √ D.中序遍历和后序遍历 √
由二叉树的中序和先序，以及中序和后序都可以唯一确定一棵二叉树。此外，由二叉树的中序序列和层次序列，也可以唯一确定一棵二叉树。请参见下面四、63和五、52。
二、 判断题(总题数：16，分数：32.00)
28.对一棵二叉树进行层次遍历时，应借助于一个栈。( )【南京航空航天大学1995五、3(1分)】 A.正确 B.错误 √
29.在含有n个结点的树中，边数只能是n一1条。( )【中国海洋大学2003一、8(2分)】 A.正确 √ B.错误
30.采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。 ( )【北京邮电大学2000一、2(1分)】 A.正确 √ B.错误
31.树的数组表示法(单链或父链表示法)中兄弟结点的编号不一定是连续的。( )【哈尔滨工业大学2002三、3(1分)】 A.正确 √ B.错误
树的数组表示法中，每个数组元素有两个分量：data表示结点数据，parent表示该结点的双亲在数组中的下标。对兄弟结点的编号是否连续没要求，哪个结点放在哪个位置没要求。一般将根结点放数组最前面，子女结点接在双亲后面，这是为了形式好看，并非必须。
32.不用递归就不能实现二叉树的前序遍历。( )【北京邮电大学2006二、6(1分)】 A.正确 B.错误 √
33.任何二叉树的后序线索树进行后序遍历时都必须用栈。( )【西安交通大学1996二、2(3分)】 A.正确 B.错误 √
任何结点至多只有左子树的后序线索树的遍历就不需要栈。
34.任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。( )【西安交通大学1996二、1(3分)】 A.正确 √ B.错误
35.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索。( )【北京交通大学2005三、2(2分)】【中南大学2005三、3(2分)】 A.正确 B.错误 √
只有空指针的地方才能加指向前驱或后继的线索，有左／右子女的结点，其左／右指针指向左／右子女。 36.在中序线索二叉树中，每一非空的线索均指向其祖先结点。( )【合肥工业大学2000二、5(1分)】 A.正确 √ B.错误
在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点(该结点的后继指针指向祖先)，中序后继是其右子树上按中序遍历的最左边的结点(该结点的前驱指针指向祖先)。 37.二又树按照某种顺序线索化之后，任一个结点均有指向其前驱结点或者后继结点的线索。( )【哈尔滨工业大学2003二、5(1分)】 A.正确 B.错误 √
38.树的父链表示法其实就是用数组表示树的存储结构。( )【哈尔滨工业大学2004三、5(1分)】 A.正确 √ B.错误
39.一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么从根结点到第k-1层具有最多的结点数为2 一1，余下的，n一2 +1个结点在第七层的任一位置上。( )【北京师范大学2005三、2(5分)】 A.正确 √ B.错误
该二叉树的1到k-1层可看做满二叉树，第k层有n一2 +1个结点，任意存放。
40.用六叉链表表示30个结点的六又树，则树中共有151个空指针。( )【北京邮电大学2005二、5(1分)】 A.正确 √ B.错误
41.必须把一般树转换成二叉树后才能进行存储。( )【南京航空航天大学1997一、4(1分)】 A.正确 B.错误 √
42.树有先根遍历和后根遍历，树可以转化为对应的二叉树，树的后根遍历与其对应的二叉树的后根遍历相同。( )【北京交通大学2005三、4(2分)】 A.正确 B.错误 √
43.用树的前序遍历和中序遍历可以导出树的后序的遍历。( )【中国海洋大学2006二、7(1分)】【中国海洋大学2007二、7(1分)】 A.正确 B.错误 √ 该结论只适合二又树。
k-1
k-1
k-1