1、20212021 年广东暨南大学年广东暨南大学数据结构数据结构考研真题考研真题 学科、专业名称：网络空间安全 研究方向：网络空间安全 083900 考试科目名称及代码：数据结构 830 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一一、 单项单项选择题选择题 ( (每题每题 2 2 分，共分，共 2020 分分) ) 1. 以下数据结构中哪一个是非线性结构？ () A. 二叉树 B. 栈 C. 线性表 D. 队列 2. 当要对线性表进行折半查找时，线性表必须满足以下条件（ ） 。 A. 以顺序方式存储 B. 以链表方式存储 C. 以顺序方式存储且按关键字有序排列 D.
2、以链表方式存储且按关键字有序排列 3. 为了提高哈希表的查找效率，以下方法说法不正确的是( )。 A. 设计好的哈希函数 B. 增加哈希函数的个数 C. 增大存储空间 D. 采用更好的地址冲突解决方法 4. 用单向链表来实现容量为 n 的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向 堆栈底部元素，则以下说法错误的是（ ） A. 入栈操作的复杂度为 O(1) B.出栈操作的复杂度为 O(1) C. 插入一个新的堆栈底部元素复杂度为 O(1) D. 删除底部元素的复杂度为 O(1) 5. 设一个顺序有序的一维数组 A1:14中有 14 个元素， 采用二分查找算法查找到 A4中的 元素过程中需
3、要比较的元素的顺序是（） A. A1, A2, A3, A4 B. A7, A3, A5, A4 C. A1, A14, A7, A4 D. A7, A5, A3, A4 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，则其左子树结点
4、数为（ ） A. 5 B. 4 C. 3 D. 2 9. 判断一个有向图中是否存在环（回路） ，可采用以下方法（） 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 2 分，共分，共 2 20 0 分分) ) 1. 数据结构的三要素是指（ ） （ ） （ ） 。 2. 在顺序表中插入或删除一个元素， 需要平均移动（ ） ，具体移动的元素
5、个数与（ ）有关。 3. 设栈 S 与队列 Q 的初始状态皆为空，元素 a1,a2,a3,a4,a5 和 a6 依次通过一个栈，一个 元素出栈后即进入队列 Q， 若 6 个元素出队列的顺序是 a3,a5,a4,a6,a2,a1,则栈 S 至少应该 容纳（ ）个元素。 4. 有一个 10 阶对称矩阵 A，采用压缩存储方式（以行序为主，且 A00=1）,则 A85 的地址是（ ） 5. 含有 100 个结点的树有（ ）条边。 6. 已知二叉树的前序序列为 ABDEGCFHIJ，中序序列为 DBGEAHFIJC，请写出后序列（ ） 。 7. 在一个无向图的邻接表中，若表结点数目为 m，则图中边的条数
6、为（ ） 。 三判断题（每题三判断题（每题 2 2 分，共分，共 2020 分分，正确的选正确的选 T T，错误的选，错误的选 F F） 1. 通过使用线性链表来实现堆栈， 可以使得每次入栈/出栈操作的时间复杂度为 O(1)。 （ ） 2. 深度优先搜索的核心数据结构是队列。 （） 3. 将包含 n 个元素的升序线性链表改成降序线性链表所需要的时间复杂度为 O(n)。 （） 4. 选择排序算法是稳定的。 （） 5. 一棵高度为 h 的完全二叉树的结点数量比同样高度的一棵满二叉树的结点要多。 （ ） 6. 平衡二叉树（AVL）的优点是能够保证在最坏情况下的查找时间复杂度为 O(logN)。 （
7、） 7. 无向图的邻接矩阵是对称的，因此只需要存储矩阵的下三角阵以节省存储空间。 ( ) 8. 一棵高度为 h 的完全二叉树可能的最大结点个数为 2 h个。 （） 9. 在快速排序、冒泡排序、希尔排序、堆排序中，空间复杂度最高的是快速排序。 （） 10. 将一棵树转化成一棵二叉树，则该二叉树的右子树不一定为空。 （） 四、简答题简答题（共共 4040 分）分） 1.描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点） 。 （6 分） 2.简述线性表、队列和堆栈这三种数据类型的相同点和差异处。 （6 分） 3. 在程序设计中，可采用下列三种方法实现输出和输入: （1）通过 scan
8、f 和 printf 语 句; (2) 通过函数的参数显式传递; (3) 通过全局变量隐式传递。试讨论这三种方法的优缺点。 （6 分） 4.试着描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 （6 分） 5.试写出一种算法在带头结点的单链表结构上实现线性表操作 Length(L)。 （8 分） 6.请用顺序存储的方式，用 C 语言写出实现把串 S1 复制到串 S2 的串复制函数 strcpy（S1， S2） 。 （8 分） 五、算法填空五、算法填空（共共 2 2 小题，每空小题，每空 2 2 分，共分，共 2020 分分） 1. 假设有一棵二叉查找树， 其每个结点包含键值
9、key、 左孩子指针left和右孩子指针right， 指针 p 指向该二叉树的根结点。现要查找键值为 x 的结点，如果该二叉树中存在键值为 x 的结点，则返回指向该结点的指针；如果不存在，则返回空指针 NULL。请填写下面 C 代 码中空白的部分，使其成为完整的算法以完成对二叉树的查找。 SearchBinaryTree(p, x) if (p = NULL | （1） ) return p; if (2) return (3)_; else return (4) ; 请将以上空白处的答案填写在下面对应位置： (1) (2) (3) (4) 2给定一个单向链表 L，链表中的结点按照键值大小升序
10、排列。以下的代码可以将 L 中所 有键值相同的结点从 L 中删除，请将代码中空白处填写完整。 Struct node int key; node *next; int DeleteDuplicate(node *L) node *p, *q; if (L = NULL | L-next =NULL) return -1; p = L; q = p-next; while (p-next != NULL) if (p-key != q-key) （1） ; （2） ; else while (（3） ) node *tmp = q-next; delete q; （4） ; if (q = NU
11、LL) break; if (q != NULL) （5） ; p = p-next; q = p-next; else （6） ; 请将以上代码的空白处答案填写在下方相应位置： (1) (2) (3) (4) (5) (6) 六编写算法（六编写算法（3030 分）分） 1.假设称正读和反读都相同的字符序列为 “回文”，例如， abba和abcba是回文， abcde和ababab 则不是回文。试写一个算法判别读入的一个以 为结束符的字 符序列是否是 “回文”。（10 分） 2. 已知由一个线性链表表示的线性表中含有三类字符的数据元素(如:字母字符、数字字符 和其他字符)， 试编写算法将该线性表分割为三个循环链表， 其中每个循环链表表示的线性 表中均只含一类字符。（10 分） 3. 已知一棵具有 n 个结点的完全二叉树被顺序存储在一维数组 An中，试着编程一个算法 输出 Ai的结点的双亲与所有孩子。（10 分）