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