安徽工业大学861数据结构考研真题

2016年全国硕士研究生入学考试招生单位自命题试卷 A卷
861（A 卷）第 1 页，共 7 页
安徽工业大学 2016 年硕士研究生招生专业基础课试卷（A 卷）
科目名称： 数据结构 科目代码： 861 满分： 150 分
考生请注意：所有答案必须写在答题纸上，做在试题纸或者草稿纸上的一律无效！
一、单项选择题（2 分*15=30 分）
1、在循环双链表的 p 所指结点之后插入 s 所指结点的操作是_____。
A. p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B. p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
C. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
D. s->prior=p; s->next=p->next; p->next->prior=s; p->next =s;
2、假设以数组 A[m]存放循环队列的元素,其头尾指针分别为 front 和
rear，则当前队列中的元素个数为_____。
A．(rear-front+m)%m B．rear-front+1
C．(front-rear+m)%m D．(rear-front)%m
3、一个 100*90 的稀疏矩阵，非 0 元素有 10 个整型数，设每个整型数占 2
字节，则用三元组表示该矩阵时，所需的字节数是_______。
A. 60 B. 66 C. 18000 D. 33
4、表达式 a*(b+c)-d 的后缀表达式是______ 。
A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd
5、已知广义表 LS＝((a,b,c),(d,e,f)),运用 Head 和 Tail 函数取出 LS 中
原子 e 的运算是______。
2016年全国硕士研究生入学考试招生单位自命题试卷 A卷
861（A 卷）第 2 页，共 7 页
A. Head (Tail (LS)) B. Head (Tail (Head (Tail (LS))))
C. Tail (Head (LS)) D. Head (Tail (Tail (Head (LS))))
6、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删
除第一个元素，则采用____存储方式最节省运算时间。
A. 单链表 B. 仅有头指针的单循环链表
C. 双链表 D. 仅有尾指针的单循环链表
7、一棵三叉树中，已知度为 3 的结点数等于度为 2 的结点数，且树中叶
结点的数目为 13，则度为 2 的结点数目为_______
A．4 B．2 C．3 D．5
8、设森林中有 3 棵树，其中第 1、第 2 和第 3 棵树的结点个数分别为 n1、
n2、n3，则与森林对应的二叉树中根结点的右子树上的结点个数是
_________。
A．n1 B．n1+ n2 C． n3 D．n2+n3
9、二叉树在线索化后，下列问题中相对较难解决的是 。
A．先序线索二叉树中求先序后继 B．中序线索二叉树中求中序后继
C．中序线索二叉树中求中序前趋 D．后序线索二叉树中求后序后继
10、若 n 个顶点的连通图是一个环，则它有 棵生成树
A．n B．n-1 C．2n D．n+2
11、有 n 个顶点有向图，至少需要 条弧才能保证是连通的。
A．n B．n-1 C．2n D．n+2
2016年全国硕士研究生入学考试招生单位自命题试卷 A卷
861（A 卷）第 3 页，共 7 页
12、用 DFS 遍历一个有向无环图，并在 DFS 算法退栈返回时打印出相应顶
点，则输出的顶点序列是___________。
A． 逆拓扑有序 B. 拓扑有序 C. 无序 D. DFS 遍历序列
13、一组记录的键值为（46，74，18，53，14，20，40，38，86，65），
利用堆排序的方法建立的初始堆为 。
A．（14，18，38，46，65，40，20，53，86，74）
B．（14，38，18，46，65，20，40，53，86，74）
C．（14，18，20，38，40，46，53，65，74，86）
D．（14，86，20，38，40，46，53，65，74，18）
14、初始序列已经有序，用直接插入排序算法进行排序，需要比较次数
为 。
A．n2
B．3(n-1) C．n-1 D．n
15、一个图中包含 k 个连通分量，若按深度优先（DFS）搜索方法访问所
有结点，则必须用 次深度优先遍历算法。
A）k B）1 C）k-1 D）k+1
二、填空题（2*10=20 分）
1、已知 n 个结点的二叉树具有最小路径长度时，其深度为 k，那么第 k 层
上的结点数为___
2、已知完全二叉树的第 8 层有 10 个结点，则该二叉树有_ __个度为 2 的
结点。
2016年全国硕士研究生入学考试招生单位自命题试卷 A卷
861（A 卷）第 4 页，共 7 页
3、分别采用堆排序、快速排序、插入排序和归并排序对初始状态为递增
序列的表按递增顺序排序，最省时间的是 算法，最费时是 算法。
4、 法构造的哈希函数肯定不会发生冲突
5、最短路径的 Floyd 算法的时间复杂度为
6、快速排序的递归算法在平均情况下的空间复杂度为
7、已知某二叉树的后序遍历序列是 DACBE，中序序列是 DEBAC，则它
的前序遍历序列是
8、n 个顶点连通图用邻接矩阵表示时，该矩阵至少有 个非零元素
9、由带权为 9，27，18，6，15 的 5 个叶子结点构成一棵哈夫曼树，则带
权路径长度为_____
三、判断题（对打√ ，错打× 1 分*10 =10 分）
1、非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没
有右孩子（ ）
2、一个树的叶结点，在先序遍历和后序遍历下，皆以相同的相对位置
出现。（）
3、在由 n 个元素组成的有序表上进行折半查找时，对任一个元素进行
查找的长度都不会大于 log2n+1 （ ）
4、哈希函数越复杂，随机性越好，冲突的概率越小。（ ）
5、在 n 个顶点的无向图中，若边数大于 n-1，则该图必是连通图。（ ）
6、快速排序算法在数据表为有序时所花费的时间最少。（ ）
2016年全国硕士研究生入学考试招生单位自命题试卷 A卷
861（A 卷）第 5 页，共 7 页
7、有向图 G 的拓扑序列惟一，则其弧数必为 n-1（其中 n 为 G 的顶点
数）。（ ）
8、对于一个堆，无论按二叉树的层次遍历还是先序遍历，都不一定能
得到有序序列。（ ）
9、Hash 表的平均查找长度与处理冲突的方法无关。（ ）
10、线性表的链接存储结构优于顺序存储结构。（ ）
四、应用题（30 分，每小题 5 分）
1、假定一组数据 (30，25，40，18，27，36，50)，按此顺序生成一棵二
叉排序树，并求出在该二叉排序树上查找成功时的平均查找长度 ASL
2、对于下图所示的无向连通图，请用 Prim 算法构造其最小生成树，设算
法从图中顶点 1 开始处理。
3、画出广义表 L=((x,a),(x,a,(b,e)))存储结构图，并利用求表头 head
和求表尾 tail 给出求解元素 b 过程
4、试图的邻接矩阵如下：利用 Dijkstra 算法求源点 1 到
其他各顶点的最短路径，要求给出相应的求解步骤
V0 V1 V2 V3 V4 V5
0 5
61 4
2 3
6 8
15
13
124
12 9
12
5
20
10
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
2016年全国硕士研究生入学考试招生单位自命题试卷 A卷
861（A 卷）第 6 页，共 7 页
5、对于序列{ 57,40,38,11,13,34,48,75,6,19,9,7}，从中选出最小的四
个元素：6,7,9,11。若采用堆排序共需要进行多少次比较？为什么？
6、请写出下列递归算法的结果： 若 m=2,n=6,则其返回结果为（ ）
int Ackerman(int m,int n)
{ if (m==0) return(n+1);
else if (m!=0 && n==0) return(Ackerman(m-1,1));
else return(Ackerman(m-1,Ackerman(m,n-1)));}
五、算法设计题（60 分，每小题 12 分）
1、一个带头结点的单链表 A，其数据元素是字符字母字符、数字字符、其
他字符，设计算法将 A 表分成三个带头结点的循环单链表 A、B 和 C，分别
含有字母、数字和其它符号的同一类字符，利用原表空间。
2、设具有 n 个结点的完全二叉树采用顺序结构存储在顺序表 BT[1..n]中，
试编写非递归先序遍历算法。(设 bt 类型为 datatype)
3、编写算法实现带头结点的单链表作为存储结构的两个递增有序表 La ，
Lb 进行如下操作：将所有在 Lb 表中存在而 La 表中不存在的结点插入到
La 中，其中 La 和 Lb 分别为两个链表的头指针。
4、设计一个算法，从具有 n 个顶点的无向图中删除一条边(u,v)。已知无
2016年全国硕士研究生入学考试招生单位自命题试卷 A卷
861（A 卷）第 7 页，共 7 页
向图采用邻接表方法存储,u 和 v 分别是一条边对应的两个顶点的序号。
5、设计算法在二叉链表结构下二叉排序树 bst 中，求关键字 K 所在结点
的层次。 （试题完）