暨南大学-830数据结构【2019】考研真题
2023-06-21
999+
58.37KB
5 页
侵权投诉
2019 年全国硕士研究生统一入学考试自命题试题（A卷）
********************************************************************************************
招生专业与代码：计算机科学与技术、软件工程、网络空间安全、工程硕士
研 究 方 向 ： 计算 机 系 统 结 构 081201 ， 计 算 机软 件 与 理 论 081202 ， 计 算 机应 用 技 术
081203，软件工程 083500，计算机技术(专业学位) 085211，网络空间安全 083900
考试科目名称及代码：数据结构 830
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、 单项选择题(每题 2 分，共 30 分)
1. 在任意一棵二叉树的先序序列和后序序列中，各叶子之间的相对次序关系 ( )。
A．不一定相同 B．互为逆序 C．都不相同 D．都相同
2. 深度为 4的二叉树至多有结点数为（ ）。
A. 18 B. 14 C. 15 D.16
3. 在一个具有 n个顶点的有向图中，若所有顶点的入度数之和为 m，则所有顶点的度数之和为
（ ）。
A．m B．m-1 C．m+1 D．2m
4. 快速排序在( )情况下最不利于发挥其长处。
A. 被排序的数据量太大. B. 被排序数据中含有多个相同的关键字
C. 被排序的数据完全无序 D. 被排序的数据已基本有序
5. 一组记录的关键字为（45,80,55,40,42,85）, 则利用堆排序的方法建立的初始堆为（ ）。
A. （80,45,55,40,42,85) B. (85,80,55,40,42,45)
C. (85,80,55,45,42,40) D. (85,55,80,42,45,40)
6. 对有 18 个元素的有序表（下标为 1~18）作折半查找,则查找 A[3]的比较序列的下标为 ( )。
A. 1,2,3 B. 9,5,2,3 C. 9,5,3 D. 9,4,2,3
7. 具有 n个顶点的完全有向图的边数为( )。
A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1
8. 利用逐点插入法建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树以后，查找元素
35 要进行（ ）。
A. 4 次 B. 5 次 C. 3 次 D. 2 次
9. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（ ）。
A．求最短路径的 Floyd 方法 B．求最短路径的 Dijkstra 方法
C．广度优先遍历算法 D．深度优先遍历算法
10. 对于一个具有 n个顶点的无向连通图，它包含的连通分量的个数为（ ）。
A．0 B．1 C．n D．n+1
11. 在一个单链表中,若p所指的结点不是最后一个结点,在p之后插入 s所指的结点, 则执行(
)。
A. s->next=p; p->next=s B. p->next=s; s->next=p
C. p=s; s->next=p->next D. s->next=p->next; p->next=s
考试科目： 数据结构 共5 页，第 1 页
12. 设F是由 T1、T2 和T3 三棵树组成的森林，与 F对应的二叉树为 B，T1、T2 和T3 的结点
数分别为 N1、N2和N3，则二叉树 B的根结点的左子树的结点数为（ ）。
A. N1-1 B. N2-1 C. N2+N3D. N1+N3
13. 设输入元素 1,2,3,P,A，输入次序为：123PA，元素经过栈后到达输出序列。当所有元素均
达到输出序列，下面（ ）序列可以作为高级语言的变量名。
A. 123PA B. PA321 C. 12AP3 D. PA123
14. 在一个链队列 Q中，删除一个结点需要执行的指令是（ ）。
A. Q.rear=Q.front->next; B. Q.rear->next=Q.rear->next->next;
C. Q.front->next=Q.front->next->next; D. Q.front=Q.rear->next;
15. 如果 T2 是由树 T转换而来的二叉树,那T中结点的后序就是 T2 中结点的 ( )。
A. 先序 B. 中序 C. 后序 D. 层次序
二．填空题(每空 2分，共 20 分)
1. 设根结点在第一层，那么具有n个结点的完全二叉树，其高度为 。
2. 对于一个循环队列Q[0..m-1]，队头、队尾指针分别为f、r，其判空的条件是 ，判满的条
件是 。
3. 在堆排序，希尔排序，快速排序，归并排序算法中，占用辅助空间最多的是 。
4. 已知二维数组 A[m][n]采用行序为主序存储，每个元素占k个存储单元，并且第一个元素
的存储地址是Loc(A[0][0]), 则A[i][j]的地址是 。
5. 若某记录序列的关键字序列是（235，346，021，558，256），用链式基数排序方法排
序，第一次收集的结果是 。
6. 设Hash 表 为 m=11 ，散列函数H(k)=k%11 ，表中已有 4个 结 点 ， 地 址 分 别 为 ：
addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7，其余地址为空。如果用二次探测再散列处理
冲突，关键字为 49 的结点的地址是 。
7. 在一个3阶的B-树上，每个结点包含的子树相同，最多为 个结点，最少为 个结点。
8. 一个连通图的 是一个极小连通子图。
三．判断题（每题 1分，共 10 分，正确的选 t，错误的选 f）
1. 对于 n个记录的集合进行冒泡排序，在最坏情况下的时间复杂度是 O(n2)。 ( )
2. 包含两个结点的所有二叉树都是相同的。（ ）
3. 一个图按广度优先遍历的结果是唯一的。( )
4. 用Prime 算法和 Kruskal 算法求得的图的最小生成树一定相同。（ ）
5. 线性表中的每一个元素都有一个前驱和后继元素。( )
6. 在n个顶点的无向图中，若边数>n-1，则该图必是连通图。（ )
7. 完全二叉树的某结点若无左孩子，则必是叶子结点。 （ )
8. 在B-树,有n棵子树的结点中有 n个关键字。 （ ）
9. 在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为
零。（ )
10. 用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图
中结点的个数有关，而与图的边数无关。（ ）
考试科目： 数据结构 共5 页，第 2 页
四. 简答题（40 分）
摘要：
展开>>
收起<<
2019年全国硕士研究生统一入学考试自命题试题（A卷）********************************************************************************************招生专业与代码：计算机科学与技术、软件工程、网络空间安全、工程硕士研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术(专业学位)085211，网络空间安全083900考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一、单项选择题(每...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
