2021年广东暨南大学数据结构考研真题.doc-资料库

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

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. 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 分，共 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.描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。（6 分） 2.简述线性表、队列和堆栈这三种数据类型的相同点和差异处。（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、左孩子指针 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 中删除，请将代码中空白处填写完整。 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） ; （4） ; （5） ; } else { while (（3） ){ node *tmp = q->next; delete q; if (q == NULL) break; } if (q != NULL){ p = p->next;

q = p->next; } else （6） ; } } } 请将以上代码的空白处答案填写在下方相应位置： (1) (2) (3) (4) (5) (6) 六．编写算法（30 分） 1.假设称正读和反读都相同的字符序列为 “回文”，例如， ‘abba’和‘abcba’是回文， ‘abcde’和‘ababab’ 则不是回文。试写一个算法判别读入的一个以 ‘@’为结束符的字符序列是否是 “回文”。（10 分） 2. 已知由一个线性链表表示的线性表中含有三类字符的数据元素(如:字母字符、数字字符和其他字符)，试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。（10 分） 3. 已知一棵具有 n 个结点的完全二叉树被顺序存储在一维数组 A[n]中，试着编程一个算法输出 A[i]的结点的双亲与所有孩子。（10 分）

资料库

2021年广东暨南大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料