版权声明
本书根据历年考研大纲要求并结合历年考研真题按照考研题型进行了整理编写，涵盖了这一考研科目重点试题及高频试题并给出了详细参考答案，针对性强，有的放矢，提高复习效率，是考研复习首选资料。
青岛掌心博阅电子书依法对本书享有专有著作权，同时我们尊重知识产权，对本电子书部分内容参考和引用的市面上已出版或发行图书及来自互联网等资料的文字、图片、表格数据等资料，均要求注明作者和来源。但由于各种原因，如资料引用时未能联系上作者或者无法确认内容来源等，因而有部分未注明作者或来源，在此对原作者或权利人表示感谢。若使用过程中对本书有任何异议请直接联系我们，我们会在第一时间与您沟通处理。
因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生读者批评指正。
特别说明
本书由本机构编写组多位高分在读研究生按照考试大纲、真题、指定参考书等公开信息潜心整理编写，仅供考研复习参考，与目标学校及研究生院官方无关，如有侵权请联系我们立即处理。
一、单项选择题
1．下面关于树和二叉树的叙述中，正确的是__________。
A.若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
B.若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点
C.若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
D.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点
【答案】C
【解析】因为中序遍历和前序遍历都是最后遍历右子树，所以，它们对应的遍历序列的最后一个结点是一样的，且是树空间结构上最右边的一个结点。
2．将递归程序转换成非递归程序，一般都要使用栈，但是消除__________可以不使用栈。
A.直接递归
B.间接递归
C.尾递归
【答案】C
3．己知散列范围为[0..9],散列函数(哈希函数)为，处理冲突的方法为线性探测再散列法，依次插入关键字序列后的哈希表为__________
A.
B.
C.
D.
【答案】B
4．在一棵二叉排序树T中，删去某结点后又将其插入，所得的二叉排序树和T相同,则结点必是__________。
A.根
B.内部结点
C.叶子
D.任意结点
【答案】C
【解析】在二叉排序树中插入新结点，必然会插在叶子上；故若T与T相同，则结点必然在叶子上。
5．利用逐点插入法建立序列对应的二叉排序树以后，查找元素35要进行__________元素间的比较。
A.4次
B.5次
C.7次
D.10次
【答案】A
6．采用简单选择排序，关键字比较次数与元素移动次数分别是__________。
A.
B.
C.
D.
【答案】C
【解析】简单选择排序中，关键字比较次数，而元素移动的最大次数。本题答案为C。
7．设广义表，Head和Tail分别为对广义表的取头和取尾操作，则
的结果是__________。
A.b
B.d
C.(d)
D.(c，d)
【答案】C
8．_________的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。
A.树形存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构
【答案】D
【解析】显然，这是散列存储结构。散列存储结构将结点按其关键字的散列地址存储到散列表中。常用的散列函数有除余法、基数转换法、平方取中法、折叠法、移位法和随机数法等。
9．在下列算法中，的执行次数是__________。
A.
B.
C.
D.
【答案】A
10．在二叉平衡排序树上成功地找到一个结点(设结点个数为n)，在平均情况和最坏情况下的时间复杂度分别是__________。
A.
B.
C.
D.
【答案】D
【解析】在平衡二叉树上进行查找的过程和二叉排序树相同，在查找过程和给定值进行比较的关键字个数不超过树的高度，且因为受平衡因子的限制，不会出现变为单支树的情形。因此，查找平衡二叉树的平均时间复杂度和最坏时间复杂度都是。
11．在含有n个关键字的小根堆中，关键字最大的记录有可能存储在__________位置上。
A.
B.
C.1
D.
【答案】D
【解析】若以一维数组存储一个小根堆，则小根堆对应一颗完全二叉树，且所有非叶结点的值均不大于其子女的值，根结点的值最小，而关键字最大的记录只能在叶子结点上。
由完全二叉树的性质知道，对于具有n个结点的完全二叉树，如果对其按序号编号，则序号为的结点的双亲结点的序号为，所有分支结点的序号为。也就是说，叶子节点的编号从开始。
12．循环队列存储在数组中，则入队时的操作为__________。
A.