[考研类试卷]计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编5.doc
[考研类试卷]计算机专业基础综合数据结构（树和二叉树）历年真题试
卷汇编5
一、单项选择题
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
（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）二叉排序树
6 二叉树的第I层上最多含有的结点数为( )。【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】
（A）2I
（B）2I-1一12018年广东省考职位表
（D）2I一1
7 从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h层的从左到右第k个结点的编号为( )。【电子科技大学2005一、6(1分)】
（A）2h+h-1
（B）2h一k+1
（C）2h+k+1
国企有哪些单位（D）2h一k-1
8 下列判断中，( )是正确的。【华南理工大学2006一、2(2分)】
（A）深度为k的二叉树最多有2k-1个结点(k≥1)，最少有k个结点
（B）二叉树中不存在度大于2的结点
（C）对二叉树遍历是指先序、中序或后序遍历中的一种
（D）构造线索二叉树是为能方便到每个结点的双亲2022年高考分数排名
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）n2+n1+n0
（B）n2+n1+2n0
（C）2n2+n1
（D）n1+2n0
12 一棵具有n个结点的完全二叉树的树高(深度)是( )。【南京理工大学1996
一、8(2分)】
（A）[logn]+1
（B）logn+1
（C）[logn]
（D）logn-1
13 有n(n>0)个结点的二叉树的深度的最小值是( )。【华中科技大学2006一、6(2分)】
（A）[log2(n)]
（B）[log2(n+1)]
（C）[log2(n+1)]
（D）[log2(n)]
14 有n个结点，并且高度为n的二叉树的数目为( )。【华中科技大学2007一、10(2分)】
（A）log2n
（B）n／2
（C）n
（D）2n-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）n2一1
（B）log2(n+1)+1
（C）log2(n+1)
（D）log2(n一1)
17 一棵树高为k的完全二叉树至少有( )个结点。【南京理工大学1998一、3(2分)】
（A）2k-1
（B）2k-1一1
（C）2k-1
（D）2k
18 一棵深度为4的完全二叉树，最少有( )个结点。【华南理工大学2005一、1(2分)】