2021 年广东暨南大学数据结构考研真题学科、专业名称：网络空间安全研究方向：网络空间安全 083900考试科目名称及代码：数据结构 830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一、 单项选择题 (每题 2 分，共 20 分)1. 以下数据结构中哪一个是非线性结构？ () A. 二叉树 B. 栈 C. 线性表 D. 队列2. 当要对线性表进行折半查找时，线性表必须满足以下条件（ ）。A. 以顺序方式存储 B. 以链表方式存储C. 以顺序方式存储且按关键字有序排列 D. 以链表方式存储且按关键字有序排列3. 为了提高哈希表的查找效率，以下方法说法不正确的是( )。A. 设计好的哈希函数 B. 增加哈希函数的个数C. 增大存储空间 D. 采用更好的地址冲突解决方法4. 用单向链表来实现容量为 n 的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是（ ）A. 入栈操作的复杂度为 O(1) B.出栈操作的复杂度为 O(1) C. 插入一个新的堆栈底部元素复杂度为 O(1) D. 删除底部元素的复杂度为 O(1)5. 设一个顺序有序的一维数组 A[1:14]中有 14 个元素，采用二分查找算法查找到 A[4]中的元素过程中需要比较的元素的顺序是（）A. A[1], A[2], A[3], A[4] B. A[7], A[3], A[5], A[4] C. A[1], A[14], A[7], A[4] D. A[7], A[5], A[3], A[4]6. 稀疏矩阵一般采用的压缩存储方法有两种，即（） A. 二维数组和三维数组 B.三元组和散列 C. 三元组和十字链表 D. 十字链表和散列7. 设 a, b 为一棵二叉树上的两个结点，在中序遍历时先访问 a 后访问 b 的条件是（） A. a 在 B 的左边 B. a 在 b 的右边 C. a 是 b 的祖先 D. a 是 b 的子孙8. 某二叉树的中序序列为 ABCDEFG，后序序列为 BDCAFGE，则其左子树结点数为（ ） A. 5 B. 4 C. 3 D. 29. 判断一个有向图中是否存在环（回路），可采用以下方法（） A. 广度优先遍历 B. 求关键路径 C. 求最短路径 D. 拓扑排序10. 用哈希表存储 7 个整数 18,25,63,50,42,32,9, 如果哈希函数为 H(x)=x mod 9，则与18 发生地址冲突的整数有（）个 A. 1 B. 2 C. 3 D. 4二、填空题 (每空 2 分，共 20 分)1. 数据结构的三要素是指（ ）（ ）（ ）。2. 在顺序表中插入或删除一个元素，需要平均移动（ ），具体移动的元素个数与（ ）有关。3. 设栈 S 与队列 Q 的初始状态皆为空，元素 a1,a2,a3,a4,a5 和 a6 依次通过一个栈，一个元素出栈后即进入队列 Q，若 6 个元素出队列的顺序是 a3,a5,a4,a6,a2,a1,则栈 S 至少应该容纳（ ）个元素。4. 有一个 10 阶对称矩阵 A，采用压缩存储方式（以行序为主，且 A[0][0]=1）,则 A[8][5]的地址是（ ）5. 含有 100 个结点的树有（ ）条边。 6. 已知二叉树的前序序列为 ABDEGCFHIJ，中序序列为 DBGEAHFIJC，请写出后序列（ ）。7. 在一个无向图的邻接表中，若表结点数目为 m，则图中边的条数为（ ）。三．判断题（每题 2 分，共 20 分，正确的选 T，错误的选 F）1. 通过使用线性链表来实现堆栈，可以使得每次入栈/出栈操作的时间复杂度为 O(1)。（ ）2. 深度优先搜索的核心数据结构是队列。（）3. 将包含 n 个元素的升序线性链表改成降序线性链表所需要的时间复杂度为 O(n)。（）4. 选择排序算法是稳定的。（）5. 一棵高度为 h 的完全二叉树的结点数量比同样高度的一棵满二叉树的结点要多。（ ）6. 平衡二叉树（AVL）的优点是能够保证在最坏情况下的查找时间复杂度为 O(logN)。（ ）7. 无向图的邻接矩阵是对称的，因此只需要存储矩阵的下三角阵以节省存储空间。 ( )8. 一棵高度为 h 的完全二叉树可能的最大结点个数为 2h个。（）9. 在快速排序、冒泡排序、希尔排序、堆排序中，空间复杂度最高的是快速排序。（）10. 将一棵树转化成一棵二叉树，则该二叉树的右子树不一定为空。（）四、简答题（共 40 分）1.描述以下三个概念的区别：头指针，头结点，首元结点（第一个...
