2015年安徽工业大学861数据结构考研真题硕士研究生入学考试试题

2015年全国硕士研究生入学考试招生单位自命题试卷 A卷
861（A 卷）第 1 页，共 3 页
安徽工业大学 2015 年硕士研究生招生专业基础课试卷（A 卷）
科目名称： 数据结构 科目代码： 861 满分： 150 分
考生请注意：所有答案必须写在答题纸上，做在试题纸或者草稿纸上的一律无效！
一、 单项选择题（每题 2 分，共 40 分）
1. 哈希查找中 k 个关键字具有同一哈希值，若用线性探测法将这 k 个关键字对应的记
录存入哈希表中，至少要进行( )次探测。
A． k B. k+1 C. k(k+1)/2 D.1+k(k+1)/2
2. 要连通具有 n 个顶点的有向图，至少需要（ ）条边。
A．n-l B．n C．n+l D．2n
3. 有六个元素 6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？
（ ）
A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6
4. 具有 12 个关键字的有序表，折半查找的平均查找长度（ ）
A. 3.1 B. 4 C. 2.5 D. 5
5. 二叉查找树的查找效率与二叉树的树型有关, 在 ( )时其查找效率最低。
A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
6. G 是一个非连通的无向图，共有 28 条边，则该图至少有( )个顶点。
A.6 B.7 C.8 D.9
7. 一棵三叉树中，已知度为 3 的结点数等于度为 2 的结点数，且树中叶结点的数目为
13，则度为 2 的结点数目为( )。
A．4 B．2 C．3 D．5
8. 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点
数至少为( )个。
A． 2h B．2h-1 C． 2h+1 D． h+1
9.下述编码中哪一个不是前缀码（ ）。
A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，
000，001）
10. 下列关于 AOE 网的叙述中，不正确的是( )。
A. 关键活动不按期完成就会影响整个工程的完成时间
B. 任何一个关键活动提前完成，整个工程将会提前完成
C. 所有的关键活动提前完成，整个工程将会提前完成
D. 某些关键活动提前完成，整个工程将会提前完成
11. 对于含有 n 个顶点 e 条边的无向连通图，利用 Kruskal 算法生成最小生成树，其
时间复杂度为( )。
A. O(elog2e) B. O(e*n) C. O(elog2n) D. O(nlog2n)
12. 下列排序算法中，时间复杂度不受数据初始状态影响，恒为 O（nlog2n）的是