学科、专业名称:网络空间安全
研究方向:网络空间安全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);
}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的结点的双亲与所有孩子。(10分)
暨南大学新祥旭考研辅导班
手机+微信咨询:**(新祥旭吴老师)
暨南大学考研2021年暨南大学830数据结构专业课考研真题
本站小编 Free考研考试/2023-08-19
相关话题/暨南大学 考研真题
暨南大学考研2021年暨南大学829社会研究方法专业课考研真题
招生专业与代码:公共管理各专业考试科目名称及代码:829社会研究方法考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。一、单项选择题(10小题,每题2分,共20分)1.某高中三个年级共1200名学生,欲从其中抽取100名学生进行调查,研究者根据性别占比等比例随机抽取男学生40人和女学 ...专业课考研资料 本站小编 Free考研考试 2023-08-19暨南大学考研2021年暨南大学828管理学及微观经济学专业课考研真题
招生专业与代码:工商管理考试科目名称及代码:管理学与微观经济学828考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。第一部分:管理学一、单项选择题(5题3分/题,共15分)[1]()主要指教育水平、文化传统、风俗习惯、价值观念、道德伦理、宗教信仰、商业习惯等。A.经济 ...专业课考研资料 本站小编 Free考研考试 2023-08-19暨南大学考研2021年暨南大学827管理运筹学专业课考研真题
学科与专业名称:管理科学与工程考试科目代码与名称:827,管理运筹学(A卷)考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。第一部分:管理学部分一、单项选择题(5题3分,共15分)[1]以下哪种现象不能在需要层次理论中得到合理的解释()。A.一个饥饿的人会冒着生命危险 ...专业课考研资料 本站小编 Free考研考试 2023-08-19暨南大学考研2021年暨南大学826食品化学专业课考研真题
招生专业与代码:食品科学、粮食油脂及蛋白质工程、食品工程考试科目名称及代码:食品化学(826)考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。一、名词解释(每题2.5分,共10分)1、同质多晶2、蛋白质变性作用3、胶凝作用4、酶二、单选题(每题2分,共30分)1.某食品的水分活度为 ...专业课考研资料 本站小编 Free考研考试 2023-08-19暨南大学考研2021年暨南大学824环境保护概论专业课考研真题
招生专业与代码:环境科学(工学)083001、环境工程083002、资源与环境(专业学位)085700考试科目名称及代码:环境保护概论824考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。一、名词解释(共5题,每小题6分,共30分)1.生态平衡;2.大气湍流;3.水体的生化自净;4 ...专业课考研资料 本站小编 Free考研考试 2023-08-19暨南大学考研2021年暨南大学823 电子技术基础专业课考研真题
招生专业与代码:080902电路与系统、080903微电子学与固体电子学、081001通信与信息系统、081002信号与信息处理、085400电子与通信工程(专业学位)考试科目名称及代码:823电子技术基础(A)考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。一、填空题(每空1分, ...专业课考研资料 本站小编 Free考研考试 2023-08-19暨南大学考研2021年暨南大学822工程力学专业课考研真题
招生专业与代码:土木与水利(085900)考试科目名称及代码:工程力学(822)考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。一、填空题(共5小题,每小题2分,共10分)1.如图1-1所示系统只受力F作用而平衡.欲使A支座约束力的作用线与杆AB成30角,则斜面的倾角?? ...专业课考研资料 本站小编 Free考研考试 2023-08-19暨南大学考研2021年暨南大学821材料综合专业课考研真题
招生专业及代码:080501材料物理与化学、080502材料学、080503材料加工工程、0805Z1生物材料、085600材料与化工(专业学位)考试科目级代码:821材料综合考生请注意:《材料综合》满分150分,考卷包括A《基础化学》、B《材料科学基础》两项内容。请根据自己的专业背景和未来拟从事的 ...专业课考研资料 本站小编 Free考研考试 2023-08-19暨南大学考研2021年暨南大学820数字电子技术专业课考研真题
招生专业与代码:光学工程(080300)考试科目名称及代码:数字电子技术(820)考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。一、单项选择题(共10小题,每小题3分,共30分)1.八位D/A转换器的最小电压增量为0.01V,当输入代码为**时,输出电压为()V。A.1.28B. ...专业课考研资料 本站小编 Free考研考试 2023-08-19暨南大学考研2021年暨南大学816高分子化学与物理专业课考研真题
招生专业与代码:生物医学工程083100考试科目名称及代码:高分子化学与物理816考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。一、单项选择题(共20题,每题2分,共40分;将正确选项的字母填入括号内)1、自由基本体聚合至一定转化率时会出现自动加速现象,这时体系的自由基浓度[M& ...专业课考研资料 本站小编 Free考研考试 2023-08-19