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

2021数据结构考研《数据库系统概论》考研真题大题解析1、设计与应用题1某汽车维修公司需建立一个汽车维修数据库，该数据库中需要存储和管理下列信息：车辆信息：车牌号，车型，发动机号，行驶里程，车辆所有人，联系电话维修项目：项目号，项目名称，维修费汽车备件：备件号，备件名称，备件单价，库存数量以上数据之间存在下列约束：可以对一个车辆进行多个维修项目，每个维修项目可用于多个车辆，维修项目完成后要在数据库中记录维修时间；一种备件可用于多个维修项目，每个维修项目最多只使用一种备件，但每种备件的数量可以是多个。

①根据以上需求构建该数据库的概念模型（画E-R图）。

②假设车辆信息有如下约束：车牌号：标识属性，取值形式为：第1个字符是“京”，第2个字符为“A”到“Z”的字母，第3到第7个字符均是“0”到“9”的数字。

此列采用普通编码定长字符型，非空；车型：普通编码定长字符型，长度为6，默认值为“轿车”；发动机号：普遍编码定长字符型：长度为6，非空；行驶里程：整型，取值大于或等于0；车辆所有人：普通编码定长字符型，长度为8，非空；联系电话：普通编码定长字符型，长度为13，取值唯一。

写出创建满足上述要求的车辆信息表的SQL语句。

（注：表名和列名均用题中给出的中文名，SQL语句中大、小写字母均可。

）答：概念模型如下：②【解析】①根据题意可知，一个车辆可以进行多个项目的维修，一个维修可以用于多个车辆，所以实体车辆信息与维修项目之间是多对多的关系；一种配件可用于多个维修项目，但一个维修项目最多只能用一种配件，所以配件与维修项目是一对多的关系。

②SQL语句中车牌号的取值形式限定可用CHECK约束来表示。

2现有关系模式：教师授课（教师号，姓名，职称，课程号，课程名，学分，教科书名）其函数依赖集为：{教师号→姓名，教师号→职称，课程号→课程名，课程号→学分，课程号→教科书名}①指出这个关系模式的主码。

②这个关系模式是第几范式，为什么？③将其分解为满足3NF要求的关系模式（分解后的关系模式名自定）答：①主码为：（教师号、课程号）②第1范式，因为存在部分依赖。

数据结构暨南大学期末试卷试题一、判断题(共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个记录中进行折半查找，当查找不成功时，与关键字比较次数最多为_____________________。

考研真题：暨南大学2022年[计算机基础综合]考试真题第一部分数据结构一、单项选择题1.含有m个结点的二叉树链式存储结构中空指针的个数为( )。

A．2mB．m-1C．m+1D．m2.下列排序算法中元素的移动次数和关键字的初始排列次序无关的是( )。

A.快速排序B.插入排序C.选择排序D.希尔排序3.一个栈的进栈序列是abcde，则栈的输出序列不可能的是( )。

A．abcdeB．edcbaC．decbaD．dceab4.需要的辅助空间最多的排序算法为( )。

A.归并排序B.快速排序C.基数排序D.堆排序5.哈希表的平均查找长度说法错误的是( )。

A.与处理冲突方法有关而与表的长度无关B.与选用的哈希函数有关C.与哈希表的饱和程度有关D.与表中填入的记录数有关6.有n个顶点、e条边且使用了邻接表存储的有向图进行深度优先遍历，其算法的时间复杂度是( )。

A.O（n+e）B.O（n2）C.O（n+2e）D.O（n*e）7.已知一个长度为11的顺序表，其元素按关键字有序排列，若采用折半查找查找一个其中不存存在的元素，则关键字的比较次数最多是( )。

A．3B．4C．5D．68.一棵完全二叉树上有3001个结点，其中叶子结点的个数是( )。

A.1500B.1501C.1000D.10019.若一棵二叉树度为2的结点有18个，度为1的结点有10个，则度为0的结点个数是( )。

A.46B.28C.19D.1710.m阶B-树是一棵( )。

A.m叉排序树B.m-1叉平衡排序树C.m叉平衡排序树D.m+1叉平衡排序树二、填空题1.已知一棵二叉树的中序遍历序列为GDHBAECIF，后序遍历序列为GHDBEIFCA，那么先序遍历序序列为。

2.若某记录的关键字序列是（491，77，572，16，996，101，863，258，689，325），以第一个关键字为枢轴，写出采用快速排序算法第一趟排序的结果。

3.将对称矩阵A[8][8]的下三角部分逐行存储到起始地址为2000的内存单元中，已知每个元素占4个单元，假设第一个元素是A[0][0]，则A[4][6]的地址是。

2020年全国硕士研究生统一入学考试自命题试题B卷********************************************************************************************学科、专业名称：网络空间安全研究方向：网络空间安全083900考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

一、单项选择题(每题2分，共30分)1. 下述关于顺序存储结构优点的说法，哪个是正确的（）A. 插入运算方便B. 可方便地用于各种逻辑结构的存储表示C. 存储密度大D. 删除运算方便2. 假设根结点为第1层，深度为h层的二叉树至少有( ) 个结点(h>1)；A. 2hB. 2h-1C. 2h+1D. 2h-13. 用单向链表来实现容量为n的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是( )A. 入栈操作的复杂度为O(1)B. 出栈操作的复杂度为O(1)C. 删除底部元素的复杂度为O(1)D. 插入一个新的堆栈底部元素复杂度为O(1)4. 以下关于递归算法的论述，不正确的是( )A. 递归算法的代码可读性好B. 递归算法可以提高程序运行效率C. 递归调用层次太深有可能造成堆栈溢出D. 递归调用层次太深会占用大量内存5. 设有字符集合{4,6,3,W,S}，将字符序列6W43S中的字符按顺序进入堆栈，出栈可发生在任何时刻。

则以下的出栈序列错误的是（）。

A. 64WS3B. 4W36SC. 6W34SD. WS4366. 在管理城市道路交通网络据时，最适合采用（）数据结构来对其进行存储。

A．有向图B．无向图C．树D．矩阵7. 具有k个顶点的完全有向图的边数为( )。

A. k(k-1)B. k(k-1)/2C. k2-1D. k2+18. 若线性表最常用的操作是增加或者删除某个元素, 则采用( )存储方式节省时间.A. 单链表B. 双链表C. 单循环链表D. 顺序表9. 由权为6,3,2,8的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（）。

1
暨南大学硕士研究生入学考试自命题科目
830《数据结构》考试大纲
Ⅰ考试形式
一、试卷满分及考试时间
本试卷满分为150分，考试时间为180分钟
二、答题方式
答题方式为闭卷、笔试
Ⅱ考查目标
1. 理解数据结构的基本概念；掌握数据结构的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

2. 掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。

3. 能够选择合适的数据结构和方法进行问题求解。

一、基本概念和术语
（一）数据元素、数据结构、抽象数据类型等概念
（二）算法设计的基本要求
（三）语句的频度和估算时间复杂度
二、线性表
（一）线性表的定义和基本操作 暨南大学硕士研究生入学考试自命题考试大纲 (含参考书目清单)
第 1／4页。