2014年安徽工业大学861数据结构考研试题研究生入学考试试题考研真题
● 摘要
2014年全国硕士研究生入学考试招生单位自命题科目 A 卷
安徽工业大学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) Ｏ(n2) D)Ｏ(n3)
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、初始序列已经有序，用直接插入排序算法进行排序，需要比较的次数为 。
2A ）n 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为________。
861（A 卷）第 1 页，共 3 页