2015北理数据结构889

北京理工大学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-树查找。定义结点类型，返回查找成功与查找失败应该插入的位置。