[考研类试卷]计算机专业基础综合数据结构(集合)历年真题试卷汇编1.doc

[考研类试卷]计算机专业基础综合数据结构（集合）历年真题试卷汇编

1

一、单项选择题

1 下列二叉排序树中，满足平衡二叉树定义的是( )。【2009年全国试题4(2分)】 （A）

（B）

（C）

（D）

2 下列叙述中，不符合m阶B树定义要求的是( )。【

（A）根结点最多有m棵子树

（B）所有叶结点都在同一层上

（C）各结点内关键字均升序或降序排列

（D）叶结点之间通过指针链接

答案见麦多课文库

2009年全国试题8(2分)】 3 在下图所示的平衡二叉树中，插入关键字48．舌得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是( )。

【2010年全国试题4(2分)】

（A）13、48

（B）24、48

（C）24、53

（D）24、90

4 已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多是( )。 [2010年全国试题9(2分)】

（A）4

（B）5

（C）6

（D）7

5 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是( )。【2011年全国试题7(2分)】

（A）95，22，91，24，94，71

（B）92，20，91，34，88，35

（C）21，89，77，29，36，38

答案见麦多课文库

（D）12，25，71，68，33，24

6 为提高散列(Hash)表的查找效率，可以采取的正确措施是( )。 【2011年全国试题9(2分)】 I．增大装填(载)因子

Ⅱ．设计冲突(碰撞)少的散列函数

Ⅲ．处理冲突(碰撞)时避免产生聚集(堆积)现象

（A）仅I

（B）仅Ⅱ

（C）仅I、Ⅱ

（D）仅Ⅱ、Ⅲ

7 若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为( )。【2012年全国试题4(2分)】

（A）12

（B）20

（C）32

（D）33

8 设有一棵3阶B树，如下图所示。删除关键字78得到一棵新B树，其最右叶结点所含的关键字是( )。[2012年全国试题9(2分)】

（A）60

答案见麦多课文库

（B）60，62

（C）62，65

（D）65

9 若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是( )。[2013年全国试题3(2分)】

（A）0

（B）1

（C）2

（D）3

10 在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是( )。【2013年全国试题6(2分)】 I．若v是T1的叶结点，则T1与T3不同 Ⅱ．若1，是T1的叶结点，则T1与T3相同 Ⅲ．若v不是T1的叶结点，则T1与T3不同 Ⅳ．若v不是T1的叶结点，则T1与T3相同

（A）仅I、Ⅲ

（B）仅I、Ⅳ

（C）仅Ⅱ、Ⅲ

（D）仅Ⅱ、Ⅳ

11 在一棵高度为2的5阶B树中，所含关键字的个数最少是( )。[2013年全国试题10(2分)】

（A）5

答案见麦多课文库