姓名： 报考专业： 准考证号码： 密封线内不要写题
2019年全国硕士研究生招生考试初试自命题试题 科目名称：数据结构（C 语言版） 科目代码：856 考试时间：3小时 满分 150 分 可使用的常用工具：√无 □计算器 □直尺 □圆规（请在使用工具前打√） 注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。

一、选择题(共10小题，每小题2分，共20分) 1. 当顺序栈ST （最多元素为MaxSize ）为空时，其栈顶指针top 的值为-1，那么判断栈ST 栈满的条件是（ ）。

A ）ST.top != -1 B ）ST.top == -1 C ）ST.top != MaxSize – 1 D ）ST.top == MaxSize – 1 2. 已知单链表中结点 q 是结点 p 的直接前趋，若在 q 与 p 之间插入结点*s ，则应执行以下（ ）操作。

A ）s->link=p->link; p->link=s; B ）q->link=s; s->link=p; C ）p->link=s->link; s->link=p; D ）p->link=s; s->link=q ； 3. 非空的循环单链表head 的尾结点（由p 所指向）满足（ ）。

A ）p->next==head B ）p==NULL C ）p->next==NULL D ）p==head 4. 设x 和y 是二叉树中的任意两个结点，若在先序遍历中x 在y 之前，而在后序遍历中x 在y 之后，则x 和y 的关系是（ ）。

A ）x 是y 的左兄弟 B ）x 是y 的右兄弟 C ）x 是y 的祖先 D ）x 是y 的子孙 5. 哈夫曼树是n 个带权叶子结点构成的（ ）最小的二叉树。

A ）权值 B ）高度 C ）带权路径长度 D ）度 6. 有向图G 包含6个顶点（编号从1到6）8条弧（<1,2>,<1,3>,<2,4>, <2,5>,<3,2>,<3,5>,<4,6>,<5,6>，权值依次为2,15,10,19,4,11,6,5）。

图G 的关键路径为（ ）。

A ）<1,2><2,4><4,6> B ）<1,3><3,2><2,5><5,6> C ）<1,3><3,5><5,6> D ）<1,2><2,5><5.6> 7. 在一个有权无向图中，如果顶点b 到顶点a 的最短路径长度是10，顶点c 与顶点b 之间存在一条长度为3的边。

那么下列说法中有几句是正确的？ （1）c 与a 的最短路径长度是13 （2）c 与a 的最短路径长度是7 （3）c 与a 的最短路径长度不超过13 （4）c 与a 的最短路径不小于7 A ）1句 B ）2句 C ）3句 D ）4句
8. 二分查找法所需的平均比较次数为（ ）。

A ）O(n 2)
B ）O(nlog 2n)
C ）O(n)
D ）O(log 2n)
9. 在Hash函数H(k)=k MOD m中，一般来讲m应取（）。

A）奇数 B）偶数 C）素数 D）充分大的数
10.用二分插入排序法进行排序，被排序的表应采用的数据结构是（）。

A）数组 B）单链表 C）双向链表 D）散列表
二、填空题(共10小题，每小题2分，共20分)
1. 一个栈的入栈序列为1,2,3,…,n，其出栈序列是p1,p2,p3,…,pn 。

若p2 = 3，
则p3可能取值的个数是（）。

2. 已知单链表A长度为m，单链表B长度为n，若将B连接在A的末尾，在没有链
尾指针的情形下，算法的时间复杂度应为（）。

3. 从一个具有n个结点的有序单链表中查找其值等于x的结点时，在查找成功的
情况下，需要平均比较（）个结点。

4. 对于一个有N个结点、K条边的森林，共有（）棵树。

5. 若以｛4，5，6，3，8｝作为叶子节点的权值构造哈夫曼树，则带权路径长度是
（）。

6. 有向图包含5个顶点（编号从1到5）6条弧（<1,2>,<1,5>,<1,3>,<2,3>,
<3,4><5,4>）。

该图进行拓扑排序，可以得到（）个拓扑序列。

7. 对于一个有向图，若一个顶点的入度为k1,出度为k2，则对应邻接表中该顶点
邻接点单链表中的结点数为（）。

8. 设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，
13，49，24，38，21，4，12）按线性探测法解决冲突的方法构造哈希表，则该哈希表等概率下查找成功的平均查找长度为（）。

9. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为（）。

10. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元
素进行比较，将其放入已排序序列的正确位置上的方法称为（）。

三、判断题(对的答√错的答×，共10小题，每小题2分，共20分)
1. 不论是入队列还是入栈，在顺序存储结构上都需要考虑“溢出”情况。

2. 在顺序表中取出第i个元素所花费的时间与i成正比。

3. 线性表的插入、删除总是伴随着大量数据的移动。

4. 二叉树通常有顺序存储结构和链式存储结构。

5. 对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一
定不小于下一层任一结点的权值。

6. Prim 算法通过每步添加一条边及相连顶点到一棵树，从而生成最小生成树。

7. 用邻接矩阵存储图，占用的存储空间只与图中结点数有关，而与边数无关。

8. 散列查找主要解决的问题是找一个好的散列函数和有效解决冲突的办法。

9. 对长度为10的排好序的表用二分法检索，若检索不成功，至少需比较10次。

10. 对5个不同的数排序至少需要比较4次。

四、综合应用题(第1小题15分，第2，3，4小题各10分，共45分)
1. 分别给出在先序线索二叉树、中序线索二叉树和后序线索二叉树中结点p的直
接后继结点所在位置。

线索二叉树中结点的结构包括数据域data、左孩子域left、右孩子域right、。