北京理工大学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）
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个节点的有向图，最少有___________条边，最多有___________条边；无向图的极小连通子图最少有___________条边，有向连通图最多有___________条边
有向图n个顶点，最多有（）条边，最少有（）条边；无向图n个顶点，最多有（）条边，最少有（）条边；有向完全图有（）条边；无向完全图（）边。
7.B-树的深度为h，则它的所有叶子节点都在第_______层。 三、应用题（40分。每道10分） 1. 写出快速排序的步骤。
2. 给出结点结构和广义表的存储结构，写出这个广义表。
3. 给出一个B-树，插入一个关键字，写出分裂过程。 4. 给出一个有向图，画出邻接矩阵和邻接表。 四、算法题（30分。每道10分） 1. 验证一个串序列是否为回文。利用栈。 2. 双向链表中在第i个位置前插入一个结点。
链表结构如下
typedef struct LNode{ ElemType data; struct LNode *prior; struct LNode *next; }LNode, *LinkList;
3. B-树查找。定义结点类型，返回查找成功与查找失败应该插入的位置。
3、在m阶B-树中查找关键字。
帮楼主补充两道填空
1.线性表可以在（ ）位置插入删除，栈只能在（ ）位置插入删除，队列只能在（ ）位置插入删除。
2.有向图n个顶点，最多有（）条边，最少有（）条边；无向图n个顶点，最多有（）条边，最少有（）条边；有向完全图有（）条边；无向完全图（）边。
其他记不清楚了，提醒16年准备考889的同学，北理研招网挂出的大纲不准，大纲中没有要求的广义表、数组、串都出了不少题，虽然不难但不要全部放弃，我大学毕业几年了，只按大纲准备的，超纲的题目吃了点亏，还有就是大纲中的题型数量分值分布也是错的，大家引以为戒。
考试结束了，一句话 考的很简单，特别重视基础，复习的时候没必要去研究那么深，我都后悔在专业课上花费太多时间了，基本上的东西知道就够了，总之，北理的889数据结构不会考难的东西。
2015-2014年北理工《889数据结构》真题
