计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编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 I
 B.2 I-1 一1
 C.2 I-1 √
 D.2 I 一1
7.从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h层的从左到右第k个结点的编号为( )。【电子科技大学2005一、6(1分)】
 A.2 h +h-1 √
 B.2 h 一k+1
 C.2 h +k+1
 D.2 h 一k-1
8.下列判断中，( )是正确的。【华南理工大学2006一、2(2分)】
 A.深度为k的二叉树最多有2 k -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-1 √
本题相当于二叉树的第n层上至多有多少个结点。结点数、高度和层次均为n的二叉树的叶子结点有2 n-1 个不同位置，形成2 n-1 棵不同的二叉树。
15.深度为h的满m叉树的第k层有( )个结点。(1≤k≤h)【北京航空航天大学2000一、4(2分)】
 A.m k-1 √
 B.m k -1
 C.m k-1
 D.m k -1
16.有n(n>0)个分支结点的满二叉树的深度是( )。【华中科技大学2004一、6(1分)】
 A.n 2 一1
 B.log 2 (n+1)+1 √
 C.log 2 (n+1)
 D.log 2 (n一1)
17.一棵树高为k的完全二叉树至少有( )个结点。【南京理工大学1998一、3(2分)】
 A.2 k -1
 B.2 k-1 一1
 C.2 k-1 √
 D.2 k
第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 5 一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 0 +3 1 +3 3 +…+3 h-1 =(3 h 一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.先序
 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.错误
在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点(该结点的后继指针指向祖先)，中序后继是其右子树上按中序遍历的最左边的结点(该结点的前驱指针指向祖先)。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。