全国硕士研究生统一入学考试自命题试题A卷网络空间安全
以下为《全国硕士研究生统一入学考试自命题试题A卷网络空间安全》的无排版文字预览，完整格式请下载
下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。
/
2021年全国硕士研究生统一入学考试自命题试题A卷
********************************************************************************************
学科、专业名称：网络空间安全
研究方向：网络空间安全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.XX组和散列 C. XX组和十字链表 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, 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 针left和右孩子指针right，指针p指向该二叉树的根结点。现要查找键值为x的结点，如果该二叉树中存在键值为x的结点，则返回指向该结点的指针；如果不存在，则返回空指针NULL。请填写下面C代码中空白的部分，使其成为完整的算法以完成对二叉树的查找。
SearchBinaryTree(p, x)
{
if (p == NULL || （1） )
return p;
if (2)
return (3)_______;
else
return (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） ;
} else {
while (（3） ){
node *tmp = q->next;
delete q;
（4） ;
if (q == NULL) break;
}
if (q != NULL){
（5） ;
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分）
[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。
- 3.2-2 段落编号的应用
- 顺序表、链表、栈的编程题(2)
- 数据结构基本知识点
- 数据结构实验报告1
- 公共基础复习资料
- 第一部分 线性表练习题（1-4章）
- 公共基础知识点精简版
- 数据结构_32学时教学大纲
- --2数据结构复习大纲
- 预习1-1-什么是数据结构
- 3.2-2 段落编号的应用
- 实验一 顺序表、单链表的基本操作(答案）
以上为《全国硕士研究生统一入学考试自命题试题A卷网络空间安全》的无排版文字预览，完整格式请下载
下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。