计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编
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
计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编1
