火箭军工程大学
2018年硕士研究生入学考试专业课试题
科目：数据结构 时间：180分钟 满分：150分
注意：答案写在答题纸上，答在试卷上无效！答题时不用抄题，只需写清题号。

一、填空题（1~10题，每空1.5分，共15分）
1．AOE 网中关键路径是指（ ）。

2．在一棵Huffman 树中，度为2的结点个数为n 2，则总结点有（ ）个。

3．对于采用邻接矩阵A 表示的n 个顶点的图，顶点vi 的入度可以表示成（ ）。

4．假定一组记录的排序码为（49,38,65,97,76,13,27,50），对其进行2-路插入升序排序的过程中，第3 趟排序的结果为（ ）。

5．如果一个完全二叉树共有n 个节点，那么叶子节点有（ ）个。

6．相较于顺序表，线性链表的优点是（ ）。

7. 深度为k 的二叉树，至多有（ ）个节点。

8. 最优二叉树的特点是（ ）。

9． 栈结构对于数据操作的原则是（ ）。

10．相较于归并排序、选择排序、快速排序，基数排序最显著的思想差异是（ ）。

二、单项选择题（11~32题，每题2分，共44分）
11．在一个单链表L 中，若要在指针p 指向节点之后插入一个由指针q 所指向结点，则执行（ ）。

A ．q = p->next ; p->next = q;
B ．p->next = q ; q = p->next;
C ．q->next= p; p = q;
D ．q->next = p->next; p->next = q;
12．一个算法的执行时间为T(10n 3+200n 2log 2n+4n-7)/(100n)，其时间复杂度为（ ）。

A ．O(n 2)
B ．O(2nlog 2n)
C ．O(nlog 2n)
D ．O(n)
13．若要以O(nlog 2n)的时间复杂度和O(1)的空间复杂度进行排序，需要用（ ）。

A ．插入排序
B ．堆排序
C ．快速排序
D ．基数排序
14．在数据结构中，与所使用的计算机无关的是数据的（ ）结构。

A ．逻辑
B ．存储
C ．逻辑和存储
D ．物理
15．图的深度优先遍历借助于（ ）结构来实现。

A ．线性表
B ．栈
C ．邻接矩阵
D ．邻接表
16．节点数为n 的完全二叉树，则其深度至少为____。

A ． -1
B ．+1
C ．
D ．⎣⎦n 2log ⎣⎦n 2log ⎣⎦)1(log 2+n ⎣⎦
)1(log 2-n 17．在一个具有n 个节点的有序单链表中插入一个新节点并仍然保持有序的时间复杂度是（ ）。

A ．O(n 2)
B ．O(n)
C ．O(1)
D ．O(nlog 2n)
18．堆排序是一种（ ）排序。

A ．插入
B ．选择
C ．交换
D ．归并
19．对有序表{1,3,9,12,32,41,45,62,75,77,82,95,100}中的82进行折半查找，需（）次才成功。

A ．3
B ．5
C ．4
D ．6
20．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构是（ ）。