北京理工大学2015年
硕士研究生入学考试数据结构889试题：
一、选择题（40分。20道，每道2分）
1． 算法的可选项是（）
A 确定性 B 有穷性C 输入D输出
2.下列不属于数组的特点是（）
A 不属于线性结构 B C D数据元素的类型可以不同
3.下列属于逻辑结构的是（）
A顺序表B哈希表C单链表D有序表
4.下列属于逻辑结构中的集合的是（）
A线性表 B哈希表 C二叉平衡树D有序表
5.线性表与数组相比较，缺点是（）
A．不能随机存取 B 元素类型可以不同 C插入删除怎么着 D以上都不对
（我选的D）
6.入栈顺序为*******，出栈顺序不可能为（）
ABCD
7．串有n个字符，则它的非奇异子串有（ ）个。
A n-1 B.n(n-1)/2 C n2-1 D.n(n-1)
(这道题也不严密 我认为答案是n(n-1)-1，选项中没有，只能选D了)
8.二叉树是（）
A．度为2 B度可以为1和2 CD明显错误
9.二叉树的先序遍历为a b c d 后序遍历为a b c d 则中序遍历不可能为（）
A B C D
10.二叉树给定下列哪种遍历可以唯一确定一棵树（）
A．先序遍历和中序遍历B．先序遍历和后序遍历C．中序遍历和后序遍历D.A和B （我认为这道题错了，我选了A和C）
11.
17.最小生成树的普利姆算法适合（）
A 连通无向图B连通有向图C连通无向网D非连通无向图
19.下列排序和初始状态无关的是（）
A、直接插入排序B选择排序、C冒泡排序、D快速排序
20.下列哪个排序尽可能高效，且要求稳定。（ ）
A．堆排序B归并排序C快速排序D冒泡排序
二、填空题（40分。每空2分）
1、 线性表可以在____________位置插入元素，栈在__________位置插入元素，队列在
______位置插入元素。
2、单链表n个元素，在某个特定位置插入元素时间复杂度，
3、森林中有三棵树，第一，第二，第三棵树的结点个数分别为n1,n2,n3。则与森林相同存储结构的二叉树的左子树结点个数为__________,右子树结点个数为___________。
4.循环队列的删除算法，填三个空：
5.哈夫曼树叶节点有n个，则哈夫曼树共有__________个结点。
6.有n个节点的图，最少有___________条边，最多有___________条边；无向图的极小连通子图最少有___________条边，有向连通图最多有___________条边
7.B-树的深度为h，则它的所有叶子节点都在第_______层。
三、应用题（40分。每道10分）
1. 写出快速排序的步骤。
2. 给出广义表的存储结构，写出这个广义表。
3. 给出一个B-树，插入一个关键字，写出分裂过程。
4. 给出一个有向图，画出邻接矩阵和邻接表。
四、算法题（30分。每道10分）
1. 验证一个串序列是否为回文。利用栈。
2. 双向链表中在第i个位置前插入一个结点。
3. B-树查找。定义结点类型，返回查找成功与查找失败应该插入的位置。