当前位置：启航官网 > 考研真题 > 专业课真题 > 工学真题

暨南大学2021年网络空间安全专业考研真题

2022-02-16 11:45:05

988

考研择校 25考研报考指南

全科400+冲刺备考指导大咖领学>>

点击咨询

考研备考过程中，刷题是重要的一个环节，尤其是在最后的备考阶段，真题的模拟训练是了解考试内容，模拟考试环境非常有效的学习方式，所以学姐给大家整理了“暨南大学2021年830数据结构”的考研真题，希望可以助大家一臂之力哦。

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.三元组和散列 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的完全二叉树可能的最大结点个数为2^h个。（）
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） ;
         } 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分）

如果想要了解更多的院校真题，请点击启航教育考研真题栏目，我们会第一时间帮助大家上传最新真题!

【26考研辅导课程推荐】：26考研集训课程,VIP领学计划,26考研VIP全科定制套餐（公共课VIP＋专业课1对1） , 这些课程中都会配有内部讲义以及辅导书和资料，同时会有教研教辅双师模式对大家进行教学以及督学，并配有24小时答疑和模拟测试等，可直接咨询在线客服老师领取大额优惠券。

免责声明：本平台部分帖子来源于网络整理，不对事件的真实性负责，具体考研相关内容请以各院校的官网通知为准。如果本站文章侵犯到您的权利，请联系我们（400-108-7500）进行删帖处理。

报考

备考

真题

互动

工具

暨南大学2021年网络空间安全专业考研真题

院校 、专业 还没搞定？启航考研为你提供解决方案，专业背景分析、未来的职业规划、个人的实力情况。

精选课程

资讯

备考

院校、专业还没搞定？启航考研为你提供解决方案，专业背景分析、未来的职业规划、个人的实力情况。