暨南大学-830数据结构【2018】考研真题
2023-06-21
999+
158.55KB
5 页
侵权投诉
2018 年全国硕士研究生统一入学考试自命题试题（A卷）
********************************************************************************************
学科、专业名称：计算机科学与技术、软件工程
研究方向：计算机系统结构 081201，计算机软件与理论 081202，计算机应用技术 081203，
软件工程 083500，计算机技术(专业学位) 085211
考试科目名称及代码：数据结构 830
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、 单项选择题(每题 2分，共 30 分)
1. 任何一棵二叉树 T, 如果度为 1的结点数为 2，度为 0结点数为 11，其分支数为 ( ) 。
A. 23 B. 22 C. 24 D. 21
2. 深度为 k的二叉树至多有( ) 个结点(k>=1)；
A. 2kB. 2k-1 C. 2k+1 D.2k-1
3. 已知一棵二叉树结点的中序序列为 BDCEAFHG, 后序序列为 DECBHGFA, 则结点的先序序
列为( ) 。
A. ABCDEFGH B. DGBFHCA C. DECBGFAH D. CAFHGDB
4. 在有向图的逆邻接表存储结构中，顶点 v在表结点中出现的次数是（ ）。
A. 顶点 V的度 B. 顶点 V的出度
C. 顶点 V的入度 D. 依附于顶点 V的边数
5. 顺序栈 s的GetTop(s, e)操作是用 e返回 s的栈顶元素，则下列( )是正确的操作。
A. e=*(s.top) B. e=*(s.top-1) C. e=*(--s.top) D. e=s.top-1
6. 若线性表最常用的操作是存取第 i个元素及其前趋的值,则采用( )存储方式节省时间.
A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表
7. 在一棵非空 m阶的 B-树上，除根之外的所有非终端结点 （ ）。
A. 至少有
2/m
棵子树 B. 至多有
2/m
棵子树
C. 至少有
2/m
棵子树 D. 至多有
2/m
棵子树
8. 若用单链表来表示队列，最适合队列操作的是（ ）。
A. 带尾指针的非循环队列 B. 带尾指针的循环链表
C. 带头指针的非循环链表 D. 带头指针的循环链表
9. 下面的序列中, ( )是堆。
A. 12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49
B. 12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49
C. 12, 36, 27, 20, 40, 34, 98, 81, 73, 55, 49
D. 12, 36, 35, 65, 40, 34, 98, 81, 73, 55, 49
10. 设有一个 10 阶的对称矩阵 A, 采用压缩存储方式,以行序为主序存储其下三角,a11 为第一个
元素,其首存储地址为 1, 每个元素占 1个地址空间,则a85 的地址为( ) 。
A. 32 B. 33 C. 34 D. 40
考试科目： 数据结构 共 5页，第 1页
11. 用带头结点的单链表存储队列，其队头指针指向头结点，队尾指针指向队尾结点，则在进
行出队时（ ）。
A. 仅修改队头指针 B. 仅修改队尾指针
C. 对头、尾指针都要修改 D. 对头、尾指针都可能要修改
12. 由权为 7,2,4,5 的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（ ）。
A. 33 B. 36 C. 35 D. 34
13. 现有一"遗传"关系：设 x是y的父亲，则 x可以把它的属性遗传给 y。表示该遗传关系最
适合的数据结构为 ( ) 。
A．向量 B．图 C．树 D．二叉树
14. 线性表是具有 n个( )的有限序列。
A. 表元素 B. 字符 C. 数据元素 D. 数据项
15.在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（ ）。
A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序
二．填空题(每空 2分，共 20 分)
1. 单链表中设置头结点的作用是 。
2. 操作系统中先来先服务是 数据结构应用的典型例子。
3. 对线性表进行折半查找时，要求线性表必须 。
4. 在中序线索二叉树上，若当前访问节点的右标志为 0，根据中序遍历的定义，它的后继结
点是 。
5. 哈夫曼树是带权路径长度 的二叉树,通常权值较大的结点离根 。
6. 在m阶B-树中某结点插入一个关键字后，若该结点的关键字数目已达 时，就要对
该结点进行分裂。
7. 顺序查找一个共有 n个元素的线性表，其时间复杂度为 。
8. 对于含有 n个顶点 e条边的无向连通图,利用广度优先搜索遍历图的时间复杂度为 。
9. Dijkstra 算法是按 次序产生一点到其余各定点最短路径的算法。
三．判断题（每题 1分，共 10 分，正确的选 t，错误的选 f）
1. 将一棵树转换成二叉树后，根结点无右子树。 （ ）
2. 归并排序是不稳定的排序方法。 （ ）
3. 在一个有向图的邻接表中，如果某个顶点的链表为空，则该顶点的出度一定为零。（ ）
4. 在二叉树的第 6层上至多有 31 个结点。（ ）
5. B-树和 B+树都能有效地支持随机检索。( )
6. 图G的最小生成树的代价一定不大于其他生成树的代价。 ( )
7. 一个无序的元素序列可以通过构造一棵二叉排序树而变成一个有序的元素序列。（ ）
8. 图的多重邻接表表示法中，表中结点的数目是图中边的条数。（ ）
9. 对特殊矩阵压缩可以降低运算的时间复杂度。 ( )
10. 无向图的邻接矩阵是对称的，因此可只存储矩阵的下三角阵。 （ ）
四.简答题（45 分）
1. 利用拓扑排序的方法求出图 1 所示有向图的所有拓扑序列。对于有向无环图，还可使用什
么方法获得拓扑序列？（10 分）
考试科目： 数据结构 共 5页，第 2页
摘要：
展开>>
收起<<
2018年全国硕士研究生统一入学考试自命题试题（A卷）********************************************************************************************学科、专业名称：计算机科学与技术、软件工程研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术(专业学位)085211考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一、单项选择题(每题2分，共30分)1.任何一棵二叉树T,如果度为1...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
