安徽工业大学2016年硕士研究生入学考试861数据结构考研试题考研真题
2023-07-14
999+
60.5KB
4 页
侵权投诉
2016 年全国硕士研究生入学考试招生单位自命题试卷 A 卷
安徽工业大学 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 的运算是______。
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 个顶点的连通图是一个环，则它有 棵生成树
861（A卷）第 1 页，共 4 页
2016 年全国硕士研究生入学考试招生单位自命题试卷 A 卷
A．n B．n-1 C．2n D．n+2
11、有 n 个顶点有向图，至少需要 条弧才能保证是连通的。
A．n B．n-1 C．2n D．n+2
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 的
结点。
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、哈希函数越复杂，随机性越好，冲突的概率越小。（ ）
861（A卷）第 2 页，共 4 页
摘要：
展开>>
收起<<
2016年全国硕士研究生入学考试招生单位自命题试卷A卷安徽工业大学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=...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
