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

2014 年全国硕士研究生入学考试招生单位自命题科目 A 卷
861（A 卷）第 1 页，共 3 页
安徽工业大学 2014 年硕士研究生招生专业基础课试卷（A 卷）
科目名称： 数据结构 科目代码： 861 满分： 150 分
考生请注意：所有答案必须写在答题纸上，做在试题纸或者草稿纸上的一律无效！
一、在下面每小题选择一个最佳答案(每小题 2 分，共 40 分)
1、下列序列中，_________是堆。
A）(100,80,55,60,50,40,58,35,20) B） (100,80,55,60,50,40,35,58,20)
C）(100,80,55,58,50,40,60,35,20) D） (100,70,55,60,50,40,58,35,20)
2、最短路径的 Floyd 算法的时间复杂度为______。
A) Ｏ(n) B) Ｏ(n+e) C) Ｏ(n
2
) D)Ｏ(n
3
)
3、线性表若采用链表存储结构时，要求内存中可用存储单元的地址 。
A）必须是不连续的 B）必须是连续的
C）连续与否都可以 D）部分地址必须是连续的
4、设 F 是一个森林，B 是由 F 转换得到的二叉树，F 中有 n 个非终端结点，B 中右指针
域为空的结点有 个。
A） n-1 B） n C） n+1 D） n+2
5、一个图中包含 k 个连通分量，若按深度优先（DFS）搜索方法访问所有结点，则必
须用 次深度优先遍历算法。
A）k B）1 C）k-1 D）k+1
6、表达式 a*(b+c)-d 的后缀表达式是 。
A）abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd
7、采用邻接表存储的图的深度优先遍历算法类似于二叉树的 算法。
A）先序遍历 B）中序遍历 C）后序遍历 D）按层遍历
8、初始序列已经有序，用直接插入排序算法进行排序，需要比较的次数为 。
A）n
2
B）3(n-1) C）n-1 D）n
9、二叉树在线索化后，下列问题中相对较难解决的是 。
A）先序线索二叉树中求先序后继 B）中序线索二叉树中求中序后继
C）中序线索二叉树中求中序前趋 D）后序线索二叉树中求后序后继
10、已知表 A 中每个元素距其最终位置不远，采用 方法最节省时间。
A． 堆排序 B．插入排序 C．快速排序 D．简单选择排序
11、设有—顺序栈 S，元素 s1,s2,s3,s4,s5,s6 依次进栈，如果 6 个元素出栈的顺序是
s2,s4,s3,s6,s5,s1，则栈的容量至少应该是_________。
A）3 B）4 C）5 D）6
12、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，
主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该
缓冲区应该是一个__________结构。
A）堆栈 B）队列 C）数组 D）线性表
13、若已知一个栈的入栈序列是 l,2,3,„,30，其输出序列是 p1,p2,p3,„,pn，若 p1
＝30，则 p10 为________。