绪论
1.1复习笔记
一.什么是数据结构
数据结构是研究非数值计算编程问题中计算机的操作对象及其关系和操作等的学科。
二.基本概念和术语
1数据
数据是表示客观事物的符号，是计算机科学中可以输入计算机，可以用计算机程序处理的符号的总称。
2数据元素
数据元素是数据的基本单位。
3数据对象
数据对象是具有相同性质的数据元素的集合，也是数据的子集。
4数据结构
数据结构是相互具有一个或多个特定关系的数据元素的集合。
)1)数据结构的基本结构
根据数据元素之间关系的特性，通常有四种基本结构：
聚会。 数据元素属于“同一集合”，没有其他复杂关系。
线性结构。 数据要素之间有一对一的关系。
树形结构。 数据元素之间有多种关系。
图形结构或网状结构。 数据元素之间有多对关系。
【注意】区分这四种基本结构取决于元素之间的对应关系。
图1-1所示为上述4种基本结构的关系图。
图1 -一类基本结构关系图
)2)数据结构的格式定义
数据结构的格式定义如下：
Data_Structure=(D，s )
其中d表示数据元素的有限集合，s表示d上的关系的有限集合。
)3)在计算机上显示数据结构
数据结构包括数据元素的表示和关系，在计算机中称为数据的物理结构(也称为存储结构)。
这里，关系有顺序映射和非顺序映射两种表现方法。 这两种表示方法对应于两种存储结构：顺序存储结构和链式存储结构。
a .顺序映射：用相对位置表示数据要素之间的逻辑关系。
b .非顺序图像：用指针表示数据元素之间的逻辑关系。
5数据类型
数据类型是值集合和在该值集合中定义的一组操作的总称。
6抽象数据类型
抽象数据类型(ADT )由一个值域和在该值域中定义的一系列操作组成。
【注意】抽象数据类型是数据类型体系结构的全局表示，可以更清楚地看到某些数据类型。
7多形数据类型
多形数据类型是指其值成分不确定的数据类型。
8数据操作的类型
基本操作如下
(1)插入
(2)删除
(3)更新
)4)搜索
)5)排序
从操作的特性来看，所有操作可以归纳为两种。
加工型操作：改变了“操作前”结构的值；
引用操作：也就是说，在不改变结构值的情况下，只需检查和计算结构值即可。
在上述5个操作中，“检索”除了是引用型操作以外，其他都是加工型操作。
名校研究生入学考试问题
说明：我们从指定闪闪导师《数据库系统概论》 (第5版)为考研参考文献的名牌大学历年考研试题及相关补习习题中选取代表性真题，并对其进行详细解答。 通过这部分的练习，可以帮助学生巩固基础知识，巩固专业基础，做好全方位的应试准备。
一、选题
1根据数据库APP应用系统的生命周期模型，在开发某数据库APP应用系统时，合理评估系统采用的软硬件、技术方案等，并提出选择建议的工作包括()。
a .规划和分析阶段的系统规划和定义
b .规划和分析阶段的可行性分析
c .需求分析阶段的业务规则需求分析
d .系统设计阶段的总体设计
【答案】b看答案
【解析】技术可行性分析是指对系统采用的软硬件、技术方案等进行合理评价，提出选择建议，是根据用户提出的系统功能、性能以及实现系统的各项约束条件进行分析，是在规划和分析阶段
2对于数据库APP应用系统的需求分析工作，以下表述是正确的()。
a .需要通过需求分析流程，确定整个应用系统的目标、任务和系统范围说明
b .在需求分析阶段，系统需求分析师必须与用户充分沟通，建立各类用户视图
c .数据需求分析的主要工作是识别数据处理中的数据处理流程
d .数据操作的响应时间、系统吞吐量、**并发用户数都是性能需求分析的重要指标
【答案】d看答案
【解析】数据库APP应用系统的需求分析工作主要包括数据和数据处理需求分析业务需求分析性能、存储、安全性、备份、恢复等需求。 其中，性能需求分析指标主要有：数据操作响应时间； 系统吞吐量**并发用户数。
3数据库的概念设计有以下几种方法。
A.DFD法和IDEFIX法
B.E-R法和IDEF0法
C.E-R法和IDEFIX法
D.DFD法和IDEF0法
【答案】查看c答案
【解析】概念设计是指将需求分析得到的用户需求抽象为信息结构的过程。 平时
见的用户数据库概念设计方法包括E-R方法和IDEFIX方法等。4关于数据库概念设计阶段的工作目标，下列说法错误的是( )。
A．定义和描述应用系统设计的信息结构和范围
B．定义和描述应用系统中数据的属性特征和数据之间的联系
C．描述应用系统的数据需求
D．描述需要存储的记录及其数量
【答案】D查看答案
【解析】数据库概念设计阶段的工作内容为：①定义和描述应用领域涉及的数据范围，获取应用领域或问题域的信息模型；②准确描述数据的属性特征、数据之间的关系、数据约束、数据的安全性要求以及支持用户的各种处理需求；③保证信息模型正确便捷的转换成数据库的逻辑结构(数据库模式)，便于用户理解。但不需要描述需要存储的记录及其数量。
5下列不属于非平凡函数依赖的是( )。
A．(CustomerID，ProviderID，BuyDate)→GoodsName
B．(CustomerID，ProviderID，BuyDate)→GoodsName，ProviderID
C．(CustomerID，ProviderID，BuyDate)→GoodsClassID
D．(CustomerID，ProviderID，BuyDate)→ProviderID
【答案】D查看答案
【解析】若X→Y，但Y∈X，则称X→Y是平凡函数依赖，否则称为非平凡函数依赖。D项为平凡函数依赖，所以不属于非平凡函数依赖。
6有某数据库系统在运行过程中发生了系统故障，发生故障时正在运行事务t1和t2。进行故障恢复时，在日志文件中发现有t1事务的开始记录而没有结束记录，有t2的开始记录和结束记录，但t2对数据库的修改还没有写到数据库中，从检查点开始正向扫描日志文件( )。
A．扫描到t1时，直接重做t1，扫描到t2时，将t2直接撤销
B．扫描到t1时，将t1加入重做队列，扫描到t2时，将t2加入撤销队列
C．扫描到t1时，直接撤销t1，扫描到t2时，将t2直接重做
D．扫描到t1时，将t1加入撤销队列，扫描到t2时，将t2加入重做队列
【答案】D查看答案
【解析】事务的原子性定义为：一个事务对数据库的所有操作是一个不可分割的工作单元，要么全部执行，要么全部不执行。本题中由于t1事务没有结束记录，可能对数据库做了部分修改，所以应该加入回滚队列。而t2有开始和结束记录却将数据存储在缓冲区中，没有写入数据库，所以应该加入重做队列。