发布时间 : 星期六 文章[考研类试卷]计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编5.doc更新完毕开始阅读3e9dd9f367ce0508763231126edb6f1afe007178
[考研类试卷]计算机专业基础综合数据结构（树和二叉树）历年真题试
卷汇编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
答案见麦多课文库
（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）二叉排序树
6 二叉树的第I层上最多含有的结点数为( )。【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】
（A）2I
（B）2I-1一1
答案见麦多课文库
（C）2I-1
（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）构造线索二叉树是为能方便找到每个结点的双亲
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
答案见麦多课文库