暨南大学830数据结构2016年考研专业课真题试卷
- 格式：pdf
- 大小：307.11 KB
- 文档页数：7
文档推荐
-
暨南大学2018考研真题之830数据结构页数:10
-
2016年暨南大学830数据结构真题.页数:5
-
2011年暨南大学830数据结构考研试题页数:5
下载文档原格式
合集下载
暨南大学软件工程830数据结构2016年真题
(1)构造赫夫曼树(Huffman)的算法。（8分）
(2)求各字符赫夫曼编码的算法。（7分）
考试科目：数据结构共5页，第5页
1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，求解下列问题：
(1)画出此二叉树。（4分）
(2)将该二叉树转换成森林。（4分）
2.设有一组关键字（71,23,73,14,55,89,33,43,48）,采用哈希函数：H(key)=key %10，采
用开放地址的二次探测再散列方法解决冲突，试在散列地址空间中对该关键字序列(按从左
else
return Find((10), item );
}
}
六．编写算法（25分）
1.设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。（10分）
2.设有一整型数组w保存n个字符的权值（均大于0），请写出
7.向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度h。（）
8.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树高度为原树的高度加1。（）
9.无向图的邻接矩阵一定是对称阵。( )
10.对小根堆进行层次遍历可以得到一个有序序列。（）
考试科目：数据结构共5页，第2页
四.简答题（45分）
{
BiThrNode *p;
p=(3)
while(p!=T){ //空树或遍历结束时p==T
while(p->LTag==Link)(4)
if(!Visit(p->data)) return ERROR;
(2)求各字符赫夫曼编码的算法。（7分）
考试科目：数据结构共5页，第5页
1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，求解下列问题：
(1)画出此二叉树。（4分）
(2)将该二叉树转换成森林。（4分）
2.设有一组关键字（71,23,73,14,55,89,33,43,48）,采用哈希函数：H(key)=key %10，采
用开放地址的二次探测再散列方法解决冲突，试在散列地址空间中对该关键字序列(按从左
else
return Find((10), item );
}
}
六．编写算法（25分）
1.设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。（10分）
2.设有一整型数组w保存n个字符的权值（均大于0），请写出
7.向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度h。（）
8.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树高度为原树的高度加1。（）
9.无向图的邻接矩阵一定是对称阵。( )
10.对小根堆进行层次遍历可以得到一个有序序列。（）
考试科目：数据结构共5页，第2页
四.简答题（45分）
{
BiThrNode *p;
p=(3)
while(p!=T){ //空树或遍历结束时p==T
while(p->LTag==Link)(4)
if(!Visit(p->data)) return ERROR;
暨南大学830数据结构2010,2012--2020年考研真题
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、 单项选择题(每题 2 分，共 30 分)
1. 下述关于顺序存储结构优点的说法，哪个是正确的（ ）
A. 插入运算方便
B. 可方便地用于各种逻辑结构的存储表示
C. 存储密度大
D. 删除运算方便
2. 假设根结点为第 1 层，深度为 h 层的二叉树至少有( ) 个结点(h>1)；
A．3
B．4
C．5
D．6
13. 有一个 100*90 的整数稀疏矩阵，其中非 0 元素个数为 10；设每个整数占用 3 个字节，则
用三元组表示该矩阵时，总共需要的存储空间为( )字节。
A．30
B．33
C．90
D．99
14. 在一个双向链表中，当删除结点 p 时，错误的操作序列为 ( )。
A. p=p->prev; p->next->prev=p; p->next=p->next->next;
2020 年全国硕士研究生统一入学考试自命题试题 B 卷
********************************************************************************************
学科、专业名称：网络空间安全 研究方向：网络空间安全 083900 考试科目名称及代码：数据结构 830
4. 以下关于递归算法的论述，不正确的是( )
A. 递归算法的代码可读性好
B. 递归算法可以提高程序运行效率
C. 递归调用层次太深有可能造成堆栈溢出 D. 递归调用层次太深会占用大量内存
5. 设有字符集合{4,6,3,W,S}，将字符序列 6W43S 中的字符按顺序进入堆栈，出栈可发生在任
2016年全国硕士研究生入学统一考试《计算机学科专业基础综合》真题及标准答案
2016年全国硕士研究生入学统一考试《计算机学科专业基础综合》真题(总分：150.00，做题时间：180分钟)一、单项选择题(总题数：40，分数：80.00)1.已知表头元素为c的单链表在内存中的存储状态如下表所示现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a,e,f的“链接地址”依次是（）。
（分数：2.00）A.1010H，1014H，1004HB.1010H，1004H，1014HC.1014H，1010H，1004HD.1014H，1004H，1010H√prev data next结点，正确的语句序列是（）。
（分数：2.00）A.p->next->prev=p->prev;p->prev->next=p->prev;free(p);B.p->next->prev=p->next;p->prey->next=p->next;free(p);C.p->next->prev=p->next;p->prev->next=p->prev;free(p);D.p->next->prey=p->prey;p->prev->next=p->next;fr ee(p);√3.设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。
现有编号为1～9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7。
若期望驶出的次序依次为1～9，则n至少是（）。
2.00）A.2B.3C.4√D.54.有一个100阶的三对角矩阵M，其元素mi,j(1≤i≤100，1≤j≤100)按行优先次序压缩存入下标从0开始的一维数组Ⅳ中。
元素m30,30在N中的下标是（）。
（分数：2.00）A.86B.87√C.88D.895.若森林F有15条边、25个结点，则F包含树的个数是（）。
数据结构暨南大学期末试卷试题
数据结构暨南大学期末试卷试题一、判断题(共10分)1. 当静态链表采用数组实现时，插入与删除操作仍需移动元素。
2. 栈也是一种线性表，也同样有顺序存储结构和链式存储结构。
3. 二叉树的三种遍历算法区别仅在于对树根、左右子树访问先后顺序的不同。
4. 邻接表是图的一种顺序存储结构。
5. 二叉树就是度数为2的树。
6. 在哈希表中勿需比较就可找到记录在表中的位置。
7. 线性表的链式存储结构既方便其存取操作，也方便其插入与删除操作。
8. 顺序存储结构既适合于完全二叉树，也同样适合于一般的二叉树。
9.一个算法是正确的、高效率的，还不能说它就是一个“好”的算法。
10. 快速排序与堆排序的平均时间复杂度相同。
二、概念填空(共20分，每题2分)1.对顺序存储结构的线性表，设表长为La;在各元素插入为等概率条件下，插入一个数据元素需平均移动表中元素_______ 个;在最坏情况下需移动表中元素_______ 个。
2.从逻辑角度看，四种基本的数据结构可分为__________、___________、____________和____________;两种存储结构为_____________和_________________。
3.一个深度为,的满k(k>2)叉树，其第i层(若存在)有________个结点;编号为p(p>1)的结点其父结点(父结点为非根结点)编号是___________________。
4.具有n个结点的完全二叉树的深度为____________;编号为p(<n)的结点其右孩子(若存在)结点编号是___________。
5.堆栈被称为一个_____________的线性表;队列被称为一个_____________的线性表。
6.静态查找表的查找方法主要有:有序表查找及________________________;在n个记录中进行折半查找，当查找不成功时，与关键字比较次数最多为_____________________。
暨南大学2020年《830数据结构》考研专业课真题试卷
D. p=p->prev; p->next=p->next->next; p->next->prev=p;
15. 在一个具有 V 个顶点的有向连通图中，若所有顶点的入度数之和为 N，所有顶点的出度
之和为 M，则以下说法正确的是（ ）。
A．V=(M+N)/2
B．M>V
C．M=N
D．N>V
二、填空题(每空 2 分，共 20 分)
A. 64WS3
B. 4W36S
C. 6W34S
D. WS436
6. 在管理城市道路交通网络据时，最适合采用（ ）数据结构来对其进行存储。
A．有向图
B．无向图
C．树
D．矩阵
7. 具有 k 个顶点的完全有向图的边数为( )。
A. k(k-1)
B. k(k-1)/2
C. k2-1
D. k2+1
8. 若线性表最常用的操作是增加或者删除某个元素, 则采用( )存储方式节省时间.
D. 采用更好的地址冲突解决方法
11. 以下数据结构中哪一个是非线性结构？( )
A. 队列
B. 栈
C. 线性表
D. 二叉树
12. 对于一个整数集合{11，37，29，55，80，46，73，17}进行散列存储时，若选用函数
H（K）= K %9 作为散列(哈希)函数，则散列地址为 1 的元素有（ ）个。
A. 2h
B. 2h-1
C. 2h+1
D. 2h-1
3. 用单向链表来实现容量为 n 的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆
栈底部元素，则以下说法错误的是( )
A. 入栈操作的复杂度为 O(1)
2023年暨南大学全国硕士真题830 数据结构
2023 年招收攻读硕士学位研究生入学考试试题A 卷******************************************************************************************** 招生专业与代码：网络空间安全考试科目名称及代码：数据结构 830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、单项选择题(每题 2 分，共 20 分)1.以下数据结构中, ( )是非线性数据结构A.字符串B．树C．队列D．栈2.请选择下面程序段的时间复杂度( )i = 1;while (i <= n)i = i * 3;A.O（n）B. O（log3 n）C. O（n2）D. O（i * n）3.顺序表中第一个元素的存储地址为120，每个元素的长度为5，则第4 个元素的地址为 ( )A. 135B. 140C. 130D. 1454.在单链表中，要将L所指节点插入到M所指节点之后，其语句应为( )A.L->next = M+1; M->next = L;B.(*M).next = L; (*L).next = (*M).next;C.L->next = M->next; M->next = L->next;D.L->next = M->next; M->next = L;5.若让元素1，2，3，4，7 依次进栈，则出栈顺序不可能为( )A. 7, 4, 3, 2, 1B. 4, 3, 1, 2, 7C. 2, 1, 7, 4, 3D. 2, 3, 7, 4, 16.假设栈 S 与队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次进入栈 S，一个元素出栈后即进入 Q，若 6 个元素出队的序列是 e2、e4、e3、e6、e5 和e1，则栈S 的容量至少为( )A．2 B. 4 C. 3. D.67.假设以行序列为主序存储二维数组 A = array[1..100,1..100]，设每个数据元素占 2 个存储单元，基地址为 10，则 LOC[5, 5] = ( )A．808 B．1010 C．818 D．10208.由3个不同结点可计算出多少种不同的二叉树？( )A. 3B. 4C. 5D. 69.广度优先遍历类似于二叉树的( )A.先序遍历B. 中序遍历C. 层次遍历D.后序遍历10.设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84 共四个，现要将关键字为49 的元素加到表中，用二次探测法解决冲突，则放入的位置是( )A．8 B．3 C．5 D．9考试科目：数据结构共 3 页，第 1 页。
《暨南大学823电子技术基础历年2010-2018年考研真题及答案解析》
目录Ⅰ历年真题试卷 (2)暨南大学2010年招收攻读硕士学位研究生入学考试试题 (2)暨南大学2011年招收攻读硕士学位研究生入学考试试题 (8)暨南大学2012年招收攻读硕士学位研究生入学考试试题 (12)暨南大学2013年招收攻读硕士学位研究生入学考试试题 (17)暨南大学2014年招收攻读硕士学位研究生入学考试试题 (22)暨南大学2015年招收攻读硕士学位研究生入学考试试题 (26)暨南大学2016年招收攻读硕士学位研究生入学考试试题 (31)暨南大学2017年招收攻读硕士学位研究生入学考试试题 (35)暨南大学2018年招收攻读硕士学位研究生入学考试试题 (40)Ⅱ历年真题试卷答案解析 (45)暨南大学2010年招收攻读硕士学位研究生入学考试试题答案解析 (45)暨南大学2011年招收攻读硕士学位研究生入学考试试题答案解析 (57)暨南大学2012年招收攻读硕士学位研究生入学考试试题答案解析 (66)暨南大学2013年招收攻读硕士学位研究生入学考试试题答案解析 (79)暨南大学2014年招收攻读硕士学位研究生入学考试试题答案解析 (93)暨南大学2015年招收攻读硕士学位研究生入学考试试题答案解析 (104)Ⅰ历年真题试卷暨南大学2010年招收攻读硕士学位研究生入学考试试题学科、专业名称：信息科学技术学院电路与系统、微电子学与固体电子学、电磁场与微波技术、通信与信息系统、信号与信息处理、电子与通信工程（专业学位）专业；理工学院物理电子学考试科目名称：823电子技术基础考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、判断下列说法是否正确，凡对者打“√”，错者打“×”，（答案必须写在答题纸上）。
（共10小题，每小题2分，共20分）1、一个理想对称的差分放大电路，既能放大差模输入信号，也有可能放大共模输入信号。
2、场效应管依靠电场控制漏极电流，故不能称为电压控制器件。
2016年暨南大学管理学院833管理学[专业硕士]考研真题【圣才出品】
2016年暨南大学管理学院833管理学[专业硕士]考研真题科目代码：833科目名称：管理学A卷一、单项选择题（请选择唯一的正确答案，每小题2分，共20分）1．控制工作中，分析和评估偏差信息首要是（）。
A．找出产生偏差信息的主要原因B．判断偏差信息的差距程度C．找出产生偏差信息的确的位置D．找出产生偏差信息的人2．“士为知己者死”这一古训反映了有效的领导始于（）。
A．上下级之间的友情B．为下属设定崇高的目标C．舍己为人D．了解下属的欲望和要求3．某公司领导比较看好某位青年员工，并经常指点和培养他，引起一般员工的不满，认为这样做很不公平。
你认为下面哪一种选择比较正确。
（）A．该领导委派重任给该青年，以树立该青年员工的工作业绩B．疏远该青年员工，以表示公平C．重新评估该青年员工的能力，根据评估结果作出处理D．不理睬那些反对声4．某企业生产同种产品有三种方案可供选择，已知各方案的固定成本和单位变动成本分别为：甲方案5000和100；乙方案15000和60；丙方案25000和40，目前企业的产量可以达到610，那么企业应该选择（）才能实现成本最低。
A．甲方案B．乙方案C．丙方案D．无法确定5．第一个采用霍桑实验，从而创立人际关系管理学的是（）。
A．罗伯·特欧文B．亨利·法约尔C．特罗D．梅克6．面对动态变化、竞争加剧的世界经济，管理者必须注意考虑环境因素的作用，以便充分理解与熟悉环境，从而能够做到有效地适应环境并（）。
A．进行组织变革B．保持组织稳定C．减少环境变化D．推动环境变革7．关于领导者必须具备的素质，不正确的是（）。
A．有部下或追随者B．拥有影响追随者的能力或力量C．具有明确的目的D．没有上级8．根据波士顿矩阵，相对市场占有率高、销售增长率低的产品，属于（）。
A．金牛产品B．瘦狗产品C．明星产品D．问题产品9．王强是销售高手并且又乐此不疲，根据领导生命周期理论，对王强应采取哪种领导风格会有更好的效果（）。
暨南大学网络空间安全专业研究生统一入学考试自命题试题A卷
4.试写出一种算法在带头结点的单链表结构上实现线性表操作 Length(L)。（8 分）
5.请用顺序存储的方式，用 C 语言写出实现把串 S1 复制到串 S2 的串复制函数 strcpy（S1，S2）。
（8 分）
6.试着描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。（6 分）
五、算法填空（共 2 小题，每空 2 分，共 20 分）
址冲突的整数有（）个
A. 1 B. 2
C. 3
D. 4
二、填空题 (每空 2 分，共 20 分)
1. 有一个 10 阶对称矩阵 A，采用压缩存储方式（以行序为主，且 A[0][0]=1）,则 A[8][5]的地 址是（ ） 2. 含有 100 个结点的树有（ ）条边。 3. 已知二叉树的前序序列为 ABDEGCFHIJ，中序序列为 DBGEAHFIJC，请写出后序列（ ） 4. 数据结构的三要素是指（ ）（ ）（ ）。
1/4
5. 在顺序表中插入或删除一个元素，需要平均移动（ ），具体移动的元素个数与（ ）有关。 6. 设栈 S 与队列 Q 的初始状态皆为空，元素 a1,a2,a3,a4,a5 和 a6 依次通过一个栈，一个元素出 栈后即进入队列 Q，若 6 个元素出队列的顺序是 a3,a5,a4,a6,a2,a1,则栈 S 至少应该容纳（ ）个 元素。 7. 在一个无向图的邻接表中，若表结点数目为 m，则图中边的条数为（ ）。
A. a 在 B 的左边 B. a 在 b 的右边 C. a 是 b 的祖先 D. a 是 b 的子孙
7. 用单向链表来实现容量为 n 的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈
底部元素，则以下说法错误的是（ ）
பைடு நூலகம்
5.请用顺序存储的方式，用 C 语言写出实现把串 S1 复制到串 S2 的串复制函数 strcpy（S1，S2）。
（8 分）
6.试着描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。（6 分）
五、算法填空（共 2 小题，每空 2 分，共 20 分）
址冲突的整数有（）个
A. 1 B. 2
C. 3
D. 4
二、填空题 (每空 2 分，共 20 分)
1. 有一个 10 阶对称矩阵 A，采用压缩存储方式（以行序为主，且 A[0][0]=1）,则 A[8][5]的地 址是（ ） 2. 含有 100 个结点的树有（ ）条边。 3. 已知二叉树的前序序列为 ABDEGCFHIJ，中序序列为 DBGEAHFIJC，请写出后序列（ ） 4. 数据结构的三要素是指（ ）（ ）（ ）。
1/4
5. 在顺序表中插入或删除一个元素，需要平均移动（ ），具体移动的元素个数与（ ）有关。 6. 设栈 S 与队列 Q 的初始状态皆为空，元素 a1,a2,a3,a4,a5 和 a6 依次通过一个栈，一个元素出 栈后即进入队列 Q，若 6 个元素出队列的顺序是 a3,a5,a4,a6,a2,a1,则栈 S 至少应该容纳（ ）个 元素。 7. 在一个无向图的邻接表中，若表结点数目为 m，则图中边的条数为（ ）。
A. a 在 B 的左边 B. a 在 b 的右边 C. a 是 b 的祖先 D. a 是 b 的子孙
7. 用单向链表来实现容量为 n 的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈
底部元素，则以下说法错误的是（ ）
பைடு நூலகம்
2016年真题823数据结构+操作系统(2015-B)
拟采用带头结点的单链表来存储线性表中的数据元素，但要求单链表中数据元素的存储顺序与线性表中数据元素的顺序逆序。即若线性表中的数据元素序列是a1,a2,……,an-1,an,则实现的单链表的数据元素的序列是an,an-1,……，a2,a1（请见图2）。
图2逆序建单链表示意图
PART II操作系统部分
一、选择题（每题2分，共20分）
优先数
进入内存时间
开始时间
完成时间
周转时间（分钟）
A
10:00
40
3
B
10:20
30
1
C
10:30
50
2
D
10:50
20
4
平均周转时间（分钟）
四、程序设计题（共13分）
某工厂有2个生产配件的车间A、B和一个装配车间C，A、B两个车间分别生产两种配件，C的任务是取一个A车间的配件和一个B车间的配件组装成一个产品。A、B车间各有一个存放配件的仓库，每个仓库最多只能存放50个配件；C车间从A、B仓库各取一个配件，装配好的产品及时运到测试车间测试，无需考虑容量问题。请用信号量和PV操作正确编写A、B、C三个车间的同步关系的程序。
3.有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，在表1所示的作业序列中作业优先数即为进程优先数，优先数越小优先级越高。列出所有作业进入内存时间、开始时间、结束时间、周转时间，计算平均周转时间。
表1作业序列及调度
作业号
到达输入井时间
运行时间(分钟)
first=first->link;
}
}
2.设哈希函数H（k）=（3 * k）mod 11，散列地址空间为0～10。给定关键字序列（35，13，49，24，62，21，14，81，12）。
图2逆序建单链表示意图
PART II操作系统部分
一、选择题（每题2分，共20分）
优先数
进入内存时间
开始时间
完成时间
周转时间（分钟）
A
10:00
40
3
B
10:20
30
1
C
10:30
50
2
D
10:50
20
4
平均周转时间（分钟）
四、程序设计题（共13分）
某工厂有2个生产配件的车间A、B和一个装配车间C，A、B两个车间分别生产两种配件，C的任务是取一个A车间的配件和一个B车间的配件组装成一个产品。A、B车间各有一个存放配件的仓库，每个仓库最多只能存放50个配件；C车间从A、B仓库各取一个配件，装配好的产品及时运到测试车间测试，无需考虑容量问题。请用信号量和PV操作正确编写A、B、C三个车间的同步关系的程序。
3.有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，在表1所示的作业序列中作业优先数即为进程优先数，优先数越小优先级越高。列出所有作业进入内存时间、开始时间、结束时间、周转时间，计算平均周转时间。
表1作业序列及调度
作业号
到达输入井时间
运行时间(分钟)
first=first->link;
}
}
2.设哈希函数H（k）=（3 * k）mod 11，散列地址空间为0～10。给定关键字序列（35，13，49，24，62，21，14，81，12）。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
精都教育——全国 100000 考生的选择
我们的梦想，为成就更多人的梦想
暨 南 大 学 大 学
更多考研真题、笔记、模拟、题库、讲义资料就上精都考研网 /
暨南大学2016年考研专业课真题试卷（原版）
三．判断题（每题 1 分，共 10 分，正确的选 t，错误的选 f）
1. 2. 3. 4. 5. 6. （ 7. 8. 在 n 个顶点的无向图中，若边数>n-1，则该图必是连通图。 （ ） 具有 n 个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的（ ） 使用散列法存储时，哈希表的大小可随意选取，通常取 10 的倍数。 （ ） 向一个二叉排序树插入新的结点时，新插入的结点总是叶子结点（ ） 数据元素是数据的最小单位。 （ ） 普里姆(Prim)算法相对于克鲁斯卡尔(Kruskal)算法更适合求一个稀疏图 G 的最小生成树。 ） 向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度 h。 （ ） 向一棵 B_树插入元素的过程中，若最终引起树根结点的分裂，则新树高度为原树的高度 加 1。 （ ） 9. 无向图的邻接矩阵一定是对称阵。 ( ) 10. 对小根堆进行层次遍历可以得到一个有序序列。 （ ）
B. head->next == NULL D. head != NULL B. 不必预估所需存储空间大小 D. 所需空间与线性表长度成正比 ） 。 插入排序 D. 快速排序
5.设有 n 个待排序的记录关键字，则在堆排序中需要（ ）辅助记录空间。 A．O(1) B. O(n) C. O(nlog2n) D. O(n2) 6. 数组 A［５］ ［６］的每个元素占 5 个字节，将其按行优先次序存储。假设 A[1][1]元素的 存储地址为 1000，则元素 A［５，５］的存储地址为( )。 A. 1140 B. 1145 C. 1120 D. 1125 7. 高度为 n 的完全二叉树的结点数至少为（ ） 。 A. 2n-1 B. 2n-1+1 C. 2n D. 2n+1 8. 设有一个无向图 G=（V，E）和 G’=（V’ ，E’ ） ，如果 G’为 G 的生成树，则下面不正确 的说法是（ ） 。 A．G’为 G 的子图 B．G’为 G 的连通分量 C．G’为 G 的极小连通子图且 V’=V D．G’为 G 的一个无环子图 9. 在有向图的邻接表存储结构中，顶点 V 在表结点中出现的次数是（ ） 。 A. 顶点 V 的度 B. 顶点 V 的出度 C. 顶点 V 的入度 D. 依附于顶点 V 的边数 10. 关键路径是事件结点网络中( )。 A．最短的回路 B．从源点到汇点的最短路径 C．最长的回路 D．从源点到汇点的最长路径
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、 单项选择题(每题 2 分，共 30 分)
1. 在线索化二叉树中，T 所指结点没有左子树的充要条件是（ A. T-> lchild=NULL B. T->ltag=1 C. t->ltag=1 且 t-> lchild =Null D. 以上都不对 2. 一个带有头结点的单链表为空的判定条件是 ( )。 A. head == NULL C. head->next == head 3. 线性链表不具有的特点是（ ） 。 A. 随机访问 C. 插入与删除时不必移动元素 4. 在下面的排序方法中，稳定的是（ A. 希尔排序 B. 堆排序 C. ） 。
2016 年全国硕士研究生统一入学考试自命题试题（A 卷）
********************************************************************************************
学科、专业名称：计算机科学与技术、软件工程 研究方向：计算机系统结构 081201，计算机软件与理论 081202，计算机应用技术 081203，软件工程 083500，计算机技术(专业学位) 085211，软件工程(专业学位) 085212 考试科目名称及代码：数据结构 830
二．填空题(每空 2 分，共 20 分)
1. 在一个长度为 n 的顺序表中删除第 i 个元素时，需向前移动 个元素。 2. 设数组 Data[0..m]作为循环队列 SQ 的存储空间，front 为队头指针，rear 为队尾指针 则执行出队操作时 front 指针的值应更新为 front= 。 3. 在单链表中，若要删除指针 p 所指结点的后一结点，则需要执行下列语句：（设 q 为指 针 变量）q=p->next; ； 。 4. 在有 n 个结点的二叉链表中，值为 NULL 的链域的个数为 。 5. 二叉树中度为 0 的结点数为 30，度为 1 的结点数为 30，总结点数为 。 6. 在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为 ，整个 堆排序过程的时间复杂度为 。 7. 对于 n 个记录（假设每个记录含 d 个关键字）进行链式基数排序，总共需要进行 趟分配和收集。 8. 设有向图 G 中有向边的集合 E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图 的一种拓扑序列为 。
考试科目：
数据结构
共 5 页，第 1
页
暨南大学2016年考研专业课真题试卷（原版）
11. 一个有 n 个结点的无向图最多有（ ）条边。 A. n B. n-1 C. n(n-1) D. n(n-1)/2 12. 对某个无向图的邻接矩阵来说，( )。 A．第 i 行上的非零元素个数和第 i 列的非零元素个数一定相等 B．矩阵中的非零元素个数等于图中的边数 C．第 i 行上，第 i 列上非零元素总数等于顶点 vi 的度数 D．矩阵中非全零行的行数等于图中的顶点数 13. 平衡二叉树的平均查找长度是 ( )。 2 A. O(n ） B. O(nlog2n） C. O(n） D. O(log2n） 14. 下列哪种排序需要的附加存储开销最大( )。 A. 快速排序 B. 堆排序 C. 归并排序 D. 插入 排序 15. 设一数列的顺序为 1,2,3,4,5,6, 通过栈操作可以得到（ ）的输出序列。 A. 3,2,5,6,4,1 B. 1,5,4,6,2,3 C. 6,4,3,2,5,1 D. 3,5,6,2,4,1
我们的梦想，为成就更多人的梦想
暨 南 大 学 大 学
更多考研真题、笔记、模拟、题库、讲义资料就上精都考研网 /
暨南大学2016年考研专业课真题试卷（原版）
三．判断题（每题 1 分，共 10 分，正确的选 t，错误的选 f）
1. 2. 3. 4. 5. 6. （ 7. 8. 在 n 个顶点的无向图中，若边数>n-1，则该图必是连通图。 （ ） 具有 n 个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的（ ） 使用散列法存储时，哈希表的大小可随意选取，通常取 10 的倍数。 （ ） 向一个二叉排序树插入新的结点时，新插入的结点总是叶子结点（ ） 数据元素是数据的最小单位。 （ ） 普里姆(Prim)算法相对于克鲁斯卡尔(Kruskal)算法更适合求一个稀疏图 G 的最小生成树。 ） 向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度 h。 （ ） 向一棵 B_树插入元素的过程中，若最终引起树根结点的分裂，则新树高度为原树的高度 加 1。 （ ） 9. 无向图的邻接矩阵一定是对称阵。 ( ) 10. 对小根堆进行层次遍历可以得到一个有序序列。 （ ）
B. head->next == NULL D. head != NULL B. 不必预估所需存储空间大小 D. 所需空间与线性表长度成正比 ） 。 插入排序 D. 快速排序
5.设有 n 个待排序的记录关键字，则在堆排序中需要（ ）辅助记录空间。 A．O(1) B. O(n) C. O(nlog2n) D. O(n2) 6. 数组 A［５］ ［６］的每个元素占 5 个字节，将其按行优先次序存储。假设 A[1][1]元素的 存储地址为 1000，则元素 A［５，５］的存储地址为( )。 A. 1140 B. 1145 C. 1120 D. 1125 7. 高度为 n 的完全二叉树的结点数至少为（ ） 。 A. 2n-1 B. 2n-1+1 C. 2n D. 2n+1 8. 设有一个无向图 G=（V，E）和 G’=（V’ ，E’ ） ，如果 G’为 G 的生成树，则下面不正确 的说法是（ ） 。 A．G’为 G 的子图 B．G’为 G 的连通分量 C．G’为 G 的极小连通子图且 V’=V D．G’为 G 的一个无环子图 9. 在有向图的邻接表存储结构中，顶点 V 在表结点中出现的次数是（ ） 。 A. 顶点 V 的度 B. 顶点 V 的出度 C. 顶点 V 的入度 D. 依附于顶点 V 的边数 10. 关键路径是事件结点网络中( )。 A．最短的回路 B．从源点到汇点的最短路径 C．最长的回路 D．从源点到汇点的最长路径
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、 单项选择题(每题 2 分，共 30 分)
1. 在线索化二叉树中，T 所指结点没有左子树的充要条件是（ A. T-> lchild=NULL B. T->ltag=1 C. t->ltag=1 且 t-> lchild =Null D. 以上都不对 2. 一个带有头结点的单链表为空的判定条件是 ( )。 A. head == NULL C. head->next == head 3. 线性链表不具有的特点是（ ） 。 A. 随机访问 C. 插入与删除时不必移动元素 4. 在下面的排序方法中，稳定的是（ A. 希尔排序 B. 堆排序 C. ） 。
2016 年全国硕士研究生统一入学考试自命题试题（A 卷）
********************************************************************************************
学科、专业名称：计算机科学与技术、软件工程 研究方向：计算机系统结构 081201，计算机软件与理论 081202，计算机应用技术 081203，软件工程 083500，计算机技术(专业学位) 085211，软件工程(专业学位) 085212 考试科目名称及代码：数据结构 830
二．填空题(每空 2 分，共 20 分)
1. 在一个长度为 n 的顺序表中删除第 i 个元素时，需向前移动 个元素。 2. 设数组 Data[0..m]作为循环队列 SQ 的存储空间，front 为队头指针，rear 为队尾指针 则执行出队操作时 front 指针的值应更新为 front= 。 3. 在单链表中，若要删除指针 p 所指结点的后一结点，则需要执行下列语句：（设 q 为指 针 变量）q=p->next; ； 。 4. 在有 n 个结点的二叉链表中，值为 NULL 的链域的个数为 。 5. 二叉树中度为 0 的结点数为 30，度为 1 的结点数为 30，总结点数为 。 6. 在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为 ，整个 堆排序过程的时间复杂度为 。 7. 对于 n 个记录（假设每个记录含 d 个关键字）进行链式基数排序，总共需要进行 趟分配和收集。 8. 设有向图 G 中有向边的集合 E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图 的一种拓扑序列为 。
考试科目：
数据结构
共 5 页，第 1
页
暨南大学2016年考研专业课真题试卷（原版）
11. 一个有 n 个结点的无向图最多有（ ）条边。 A. n B. n-1 C. n(n-1) D. n(n-1)/2 12. 对某个无向图的邻接矩阵来说，( )。 A．第 i 行上的非零元素个数和第 i 列的非零元素个数一定相等 B．矩阵中的非零元素个数等于图中的边数 C．第 i 行上，第 i 列上非零元素总数等于顶点 vi 的度数 D．矩阵中非全零行的行数等于图中的顶点数 13. 平衡二叉树的平均查找长度是 ( )。 2 A. O(n ） B. O(nlog2n） C. O(n） D. O(log2n） 14. 下列哪种排序需要的附加存储开销最大( )。 A. 快速排序 B. 堆排序 C. 归并排序 D. 插入 排序 15. 设一数列的顺序为 1,2,3,4,5,6, 通过栈操作可以得到（ ）的输出序列。 A. 3,2,5,6,4,1 B. 1,5,4,6,2,3 C. 6,4,3,2,5,1 D. 3,5,6,2,4,1