9. 对长度为10的排好序的表用二分法检索，若检索不成功，至少需比较10 次。
10. 对5个不同的数排序至少需要比较4次。 四、综合应用题(第1小题15分，第2，3，4小题各10分，共45分)
1. 分别给出在先序线索二叉树、中序线索二叉树和后序线索二叉树中结
点p的直接后继结点所在位置。
线索二叉树中结点的结构包括数据域data、左孩子域left、右孩子域
2. 已知单链表A长度为m，单链表B长度为n，若将B连接在A的末尾，在没有 链尾指针的情形下，算法的时间复杂度应为（ ）。
3. 从一个具有n个结点的有序单链表中查找其值等于x的结点时，在查找 成功的情况下，需要平均比较（ ）个结点。
4. 对于一个有N个结点、K条边的森林，共有（ ）棵树。
5. 若以｛4，5，6，3，8｝作为叶子节点的权值构造哈夫曼树，则带权路径长 度是（ ）。
B）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
A）奇数
B）偶数
C）素数 D）充分大的数
10.用二分插入排序法进行排序，被排序的表应采用的数据结构是（ ）。
A）数组 B）单链表
C）双向链表 D）散列表
二、填空题(共10小题，每小题2分，共20分)
1. 一个栈的入栈序列为1,2,3,…,n，其出栈序列是p1,p2,p3,…,pn 。若p2 = 3，则p3可能取值的个数是（ ）。
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的左兄弟 C）x是y的祖先
注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无
效；考完后试题随答题纸交回。
一、选择题(共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；
right、左标志域ltag和右标志域rtag，标志域为0表示没有孩子，孩 子域为线索。
2. 已知一棵树的先序序列（ABEFIGCDHJKLNOM）和后序序列（EIFGBCJKNOLM
HDA）。 （1）请画出该树的逻辑结构
（2）写出该树的层次遍历序列
第2页共4页
5. 对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点 的权值一定不小于下一层任一结点的权值。
6. Prim 算法通过每步添加一条边及相连顶点到一棵树，从而生成最小生成树。
7. 用邻接矩阵存储图，占用的存储空间只与图中结点数有关，而与边数无 关。
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 mod3，49，24，38，21，4，1 2）按线性探测法解决冲突的方法构造哈希表，则该哈希表等概率下查 找成功的平均查找长度为（ ）。
）。图G的关键路径为（ ）。
A）<1,2><2,4><4,6> C）<1,3><3,5><5,6>
B）<1,3><3,2><2,5><5,6> D）<1,2><2,5><5.6>
7. 在一个有权无向图中，如果顶点b到顶点a的最短路径长度是10，顶点c
与顶点b之间存在一条长度为3的边。那么下列说法中有几句是正确的
9. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为（ ）。
10. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空） 中的元素进行比较，将其放入已排序序列的正确位置上的方法称为（ ）。
三、判断题(对的答√错的答×，共10小题，每小题2分，共20分)
1. 不论是入队列还是入栈，在顺序存储结构上都需要考虑“溢出”情况。 2. 在顺序表中取出第i个元素所花费的时间与i成正比。 3. 线性表的插入、删除总是伴随着大量数据的移动。 4. 二叉树通常有顺序存储结构和链式存储结构。
？
（1）c与a的最短路径长度是13 （2）c与a的最短路径长度是7
（3）c与a的最短路径长度不超过13 （4）c与a的最短路径不小于7
第1页共4页
A）1句 B）2句 C）3句 D）4句
8. 二分查找法所需的平均比较次数为（ ）。
A）O(n2)
B）O(nlog2n)
C）O(n)
D）O(log2n)
9. 在Hash函数H(k)=k MOD m中，一般来讲m应取（ ）。
姓名： 报考专业： 准考证号码： 密封线内不要写题
2018年全国硕士研究生招生考试初试自命题试题
科目名称：数据结构（C语言版）（■A卷□B卷）科目代码：856 考试时间：3小时 满分 150 分
可使用的常用工具：√无 □计算器 □直尺 □圆规（请在使用工具前打√）