习题整理：

一、选择题：

1. 在关系数据库的结构化查询语言中，“DELETE FROM表名”表示（从基表中删除所有属性）；

2.在数据库管理系统中，事务的四个特性包括（原子性，一致性，隔离性，持续性）；

3.在数据库理论中，用二维表结构表示的数据模型称为（关系模型）；

4.在数据库系统结构中，用户使用的数据视图称为（外模式，也称子模式或用户模式）；

5.下列说法正确的是（B）；

  A.数据库避免了一切数据冗余     B.数据库中的数据可以共享  

C.数据库避免了一切数据的重复   D.数据库具有完全的数据独立性

6.在关系数据库中，用于关系代的关系运算包括（选择，投影，连接，除运算）；

7.封锁机制主要用于实现（并发控制）；

8.转储的冗余包括（日志文件、数据库后背副本）

9.在局部视图设计中，分E-R图之间的冲突包含下列哪一个（A）；

  A.属性冲突   B.实体冲突   C.联系冲突   D.关系冲突

10.关系演算是用（谓词）来表达查询要求的方式；

11.并发控制：把关系数据库从错误状态恢复到一致状态；

12.转储方式可分为（海量转储和增量转储）；

13.在关系数据库的结构化查询语言中，实现分组查询的子句是（GROUP BY）；

14.在关系数据库的结构化查询语言中，带有“EXISTS”谓词的子查询返回是（逻辑值真“true”假“false”）；

15.在关系数据库的结构化查询语言中，实现“投影”操作的语句是（SELECT）；

16.SQL语言提供的功能不包括（A）；

   A.修改表结构   B.删除属性列   C.删除元组   D.授权

17.两个函数依赖集F和G等价的充分必要条件是（F*=G*）；

18.下面列出的关于“视图”的条目中，不正确的是（C）

   A.视图是外模式  B.视图是虚表  C.加快查询语句的执行速度  D.简化查询语句的编写

19.事务定义不正确的说法是（C）

   A.用户定义的一个数据库操作序列   B.一个不可分割的工作单位

C.就是程序                           D一条或一组SQL语句、或整个程序

20.关于函数依赖，正确的是（A）

   A.若X→Y，Y→Z，则X→YZ    B.若XY→Z,则X→Z,Y→Z 

C.若X→Y，Y→Z，则Y→X     D.若X→Y，Y→Z，Y’包含Y，则Z→Y’

二、填空题：

1.数据库系统死锁属于（事务故障）；

2.在数据库设计中，（需求分析）表达了数据和处理的关系；

3.在数据库设计中，（数据字典）是系统中各类数据表述的集合，是进行详细的数据收集和数据分析所获得的主要成果；

4.事务是数据库的逻辑工作单位，包括的操作要么都要做，要么都不做，成为事务的（原子性）；

5.在并发操作中，产生数据不一致性的主要原因是并发操作破坏了事务的（一致性）；

6.（一致性）是指数据库中只包含成功事务提交的结果；

7.对并发执行而言，一个事务的执行不能被其他事务干扰，一个事务内部的操作及使用的数据对其他并发事务是隔离的，并发执行的各个事务之间不能相互干扰，成为事务的（隔离性）；

8.（E—R）模型是关系数据库的概念结构设计的一个有力工具；

9.关系数据库的（规范化理论）是使数据库设计方法走向完备的理论基础；

10.（数据库管理系统）是管理数据库的机构，是位于用户与操作系统之间的一层数据管理软件；

四．设计题：

某医院病房计算机管理中需要如下信息：

科室：科名、科地址、科电话、医生姓名；

病房：病房号、床位号、所属科室名；

医生：姓名、职称、所属科室名、年龄、工作证号；

病人：病历号、姓名、性别、诊断、主管医生、病房号；

其中，一个科室有多个病房，多个医生；一个病房只能属于一个科室，一个医生只属于一个科室，但可以负责多个病人的诊治，一个病人的主管医生只有一个。完成如下设计：

⑴       设计该计算机管理系统的E—R图；

⑵       将该E—R图转换为关系模型图；

⑶       指出转换结果中每个关系模式的候选码；

答：⑴画图；

⑵科室：科名、科地址、科电话、医生姓名；

病房：病房号、床位号、所属科室名；

医生：姓名、职称、所属科室名、年龄、工作证号；

病人：病历号、姓名、性别、诊断、主管医生、病房号

⑷     科室关系模式的候选码（组）为：科地址或科名；

病房关系模式的候选码为：病房号；

医生关系模式的候选码为：工作证号；

病人关系模式的候选码为：病历号；

注：候选码为关系中的某一属性组的值能唯一的标识一个元组；

课本内容整理：

1.       描述事物的符号记录称为数据；

2.       数据库：长期储存在计算机内，有组织，可分享的大量数据集合；

3.       数据三个基本特点：永久储存、有组织、可分享；

4.       数据库管理系统：位于用户与操作系统之间的一层数据管理软件；

5.       DBMS功能：a.数据定义 b.数据组织储存和管理 c.数据操纵 d.数据事务管理和运行管理 e.数据的建立和维护 f.其他功能；

6.       数据库系统由数据库、数据库管理系统、应用系统、数据库管理员构成；

7.       数据管理是指对数据进行分类、组织、编码、储存检索和维护，他是数据处理的中心问题；

8.       数据库系统的特点：a.数据结构化 b.数据分享型高，冗余度低，易扩充 c.数据独立性高；

9.       数据模型是数据库系统的核心和基础；

10.   数据模型的组成要素：a.数据结构 b.数据操作 c.数据的完整性约束；

11.   实体：客观存在并可以相互区别的事物称为实体；   

属性：实体具有的某一特性；    

码：唯一标识实体的属性集；    

实体型：用实体名及其属性名集合来抽象和刻化同类实体称为实体型；

12.   元组：表中的一行称为一个元组；              

分量：元组中的一个属性值；         

关系模式：对关系的描述，一般表示为关系名（属性1……属性n）；

13.   关系模型完整性：a.实体完整性   b.参照完整性  c.用户定义完整性；

14.   模式是数据库中全体数据的逻辑结构和特征描述；

15.   三级模式：a.模式       b.外模式      c.内模式 ；                        

模式也称逻辑模式，外模式也称子模式或用户模式，内模式也称储存模式，一个数据库只有一个模式、一个内模式，可以有多个外模式；

16.   二级映像：外模式／模式映像   模式／内模式映像；

17.   二级映像保证数据较高的逻辑独立性和物理独立性；

18.   若关系中的某一个属性的值能唯一标识一个元组，该属性组称为候选码，候选码的诸属性称为主属性；

19.   实体完整性：主属性不能为空；

20.   运算的三大要素：运算对象、运算符、运算结果；

21.   传统集合运算：a.并    b.差     c.交    d.笛卡尔积；

22.   专门的关系运算：a.选择   b.投影   c.连接    d.除；

23.   视图是导出表的虚表；

24.   SQL集数据查询、数据操纵、数据定义、数据控制于一身；

25.   SQL特点：a.综合统一   b.高度非过程化   c.面向集合操纵   d.同一种语法多种使用方法   e.语言简洁易学易用；

26.   数据查询           SELECT；

数据定义           CREATE   DROP  ALTER；

数据操纵           INSERT   UPDATE   DELETE；

数据控制           GRANT   REVOKE；

27.   SQL中，一个关系对应一个基本表，一个（或多个）基本表对应一个储存文件，一个表可以有若干索引，索引也可以存放在储存文件中；

28.   SQL通常不提供修改模式定义、修改视图定义和修改索引定义；

29.   函数依赖会导致数据冗余、插入异常、删除异常和更新异常；

30.   Z→Y但YX,则称X→Y是非平凡的函数依赖；

X→Y但YX，成X→Y是平凡的函数依赖；

若X→Y，Y→X，则记X←→Y；

在R(U)中，如果X→Y，并且对于X的任何一个真子集X’，都有X’不→Y，则称Y对X完全函数依赖，记XY；

若X→Y但Y不完全函数依赖于X，成Y对X部分函数依赖；

31.   第一范式：如果一个关系模式的所有属性都是不可分割的基本数据项

2NF：若R1NF且每个非主属性完全函数依赖于码；

3NF：关系模式R<UF>中若不存在这样的码X，属性组Y及非主属性Z，使得X→Y，Y→Z成立，Y不→X，称R<UF>3NF；

BCNF：关系模式R<UF>1NF，若X→Y且YX时，X必须含有码，则R<UF>BCNF;

32. 数据库设计的过程和基本步骤：1.需求分析；2.概念设计；3.逻辑设计；4.物理设计；5.数据库实施阶段；6.数据库运行和维护；

33．数据字典是系统中各类数据表述的集合，是数据收集和分析的结果；

    数据字典包括数据项、数据结构、数据流、数据存储和处理；

34．合并E-R图，生成初步E-R：1.属性冲突、2.命名冲突、3.结构冲突

35．事务：用户定义的一个数据库操作序列，这些操作要么都要做，要么都不做，是一个不可分割的工作单位；

   事务的四个特性：原子性、一致性、隔离性、持续性；

36．故障种类：1.事务内部、2.系统故障、3.介质故障、4.计算机病毒；

37．数据转储是数据库恢复中采用的基本技术；转储分为静态转储和动态转储，也可分为海量转储和增量转储；

38．日志文件是用来记录事务对数据库的更新操作的文件；

39．视图的作用：a.能简化用户操作（简化用户的数据查询操作）；b.能以多种角度看待同一种数据；c.对重构数据提供了一定程度的逻辑独立性；d.能够对机密数据提供安全保护；e.适当的利用视图可以更清晰的表达查询；

数据的物理独立性：用户的应用程序不依赖数据库的物理结构；

数据的逻辑独立性：当数据库重构时，如增加新的关系或对原有关系增加新的字段等，用户的应用程序不会受影响；

 

第二篇：数据结构知识点整理

数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号（数值、字符等）的集合。

数据元素（数据成员）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等 数据对象具有相同性质的数据元素（数据成员）的集合

数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。记为Data_Structure = {D, R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。

数据类型是指一种类型，以及定义在这个值集合上的一组操作的总称。

判断一个算法的优劣主要标准：正确性、可使用性、可读性、效率、健壮性、简单性。 算法效率的衡量方法：后期测试，事前估计 算法分析是算法的渐进分析简称

数据结构包括“逻辑结构” 和“物理结构”两个方面(层次):

逻辑结构是对数据成员之间的逻辑关系的描述，它可以用一个数据成员的集合和定义在此集合上的若干关系来表示物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”

线性表的定义：n（ ? 0）个表项的有限序列 L =（a1, a2, …, an） ai是表项，n是表长度。第一个表项是表头，最后一个是表尾。

线性表的特点：表中元素的数据类型相同；线性表中，结点和结点间的关系是一对一的，有序表和无序表线性表的存储方式。一，顺序存储方式，二，链表存储方式。

顺序表的存储表示有2种方式：静态方式和动态方式。

顺序表的定义是：把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中。

顺序表的特点：用地址连续的一块存储空间顺序存放各表项，各表项的逻辑顺序与物理顺序一致，对各个表项可以顺序访问，也可以随机访问 。

单链表是一种最简单的链表表示，也叫线性链表，用她来表示线性表时，用指针表示结点间的逻辑关系。特点：是长度可以很方便地进行扩充。

连续存储方式（顺序表）特点：存储利用率高，存取速度快缺点：插入、删除等操作时需要移动大量数据： 链式存储方式（链表） 特点：适应表的动态增长和删除。缺点：需要额外的指针存储空间

单链表的类定义：多个类表达一个概念(单链表)。分为：链表结点(ListNode)类 ，链表(List)类。

循环链表的概念：是另一种形式的表示线性表的链表，它的结点结构与单链表相同，与单链表不同的是链表中表尾结点的LINK域中不是NULL，而是存放了一个指向链表开始结点的指针，这样，只要知道表中任何一个结点的地址，就能遍历表中其他任何一结点。

双向链表的概念：在双向链表的没饿结点中应有两个链接指针作为它的数据成员：1LINK指示它的前驱结点，RLINK指示它的后继结点，因此，双向链表的每个结点至少有3个域：1LINK(前驱指针) DADA（数据） RLINK（后继指针）。 栈：定义为只允许在表的末端进行插入和删除的线性表。特点是：后进先出。

递归的定义 ：若一个对象部分地包含它自己，或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。以下三种情况常常用到递归方法一。 定义是递归的二。 数据结构是递归的三问题的解法是递归的。

队列：队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头，允许插入的一端叫做队尾。特性：先进先出。

优先级队列：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。多维数组是一维数组的推广。

多维数组是一维数组的推广。多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继。数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。 字符串是 n ( ? 0 ) 个字符的有限序列， 记作S : “c1c2c3…cn”其中，S 是串名字c1c2c3…cn”是串值ci 是串中字符n 是串的长度，n = 0 称为空串。

广义表是 n ( ≥0 ) 个表元素组成的有限序列，记作LS (a1, a2, a3, …, an)，LS 是表名，ai 是表元素，可以是表（称为子表），可以是数据元素（称为原子）。n为表的长度。n = 0 的广义表为空表。n > 0时，表的第一个表元素称为广义表 的表头（head），除此之外，其它表元素组成的表称为广义表的表尾（tail

有根树：一棵有根树 T，简称为树，它是n (n≥0) 个结点的有限集合。当n = 0时，T 称为空树；否则，T 是非空树，记作 T={ 空集 n=0

{r,T1,T2….Tn},n>0

r 是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为 m (m ? 0) 个互不相交的有限集合T1, T2, …, Tm，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继

二叉树的定义:一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

完全二叉树 :─ 若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树

二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作 V遍历根的左子树记作 L 遍历根的右子树记作 R。则可能的遍历次序有：前序 VLR 镜像 VRL；中序 LVR 镜像 RVL；后序 LRV 镜像 RLV

前序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则访问根结点 (V)；前序遍历左子树 (L)；前序遍历右子树 (R)。遍历结果- + a * b - c d / e f

树的后根次序遍历:当树非空时依次后根遍历根的各棵子树访问根结点：树后根遍历 EFBCGDA；对应二叉树中序遍历 EFBCGDA；树的后根遍历结果与其对应二叉树。

表示的中序遍历结果相同：树的后根遍历可以借助对应二叉树的中序遍历算法实现

最小堆和最大堆：如果有一个关键码集合K={K0,K1，K2，K3，….,Kn-1}，把它的所有元素按完全二叉树的顺序存储方式存放在一个一维数组中。并满足Ki≤K2i+1且Ki≤K2i+2(或者Ki≥K2i+1且KiK2i+2 )i=0,1,….[（n-2）/2]，则称这个集合为最小堆或最大堆。

堆是最高效的一种数据结构，每次出队列的是优先权最高的元素。用堆实现其存储表示，能够高效运作。

堆的建立：有2种方式建立最小的堆，一种方式是通过第一个构造函数建立一个空堆，其大小通过动态存储分配得到，另一中建立最小堆的方式是通过第二个构造函数复制一个记录数组并对其加以调整形成一个堆。 路径：从树中一个结点到达另一个结点之间的分支构成该两结点之间的路径。

路径长度：是指路径上的分支条数，树的路径长度是从树的根结点到每一个结点的路径长度之和。由树的定义，从根结点到达书中每一结点有且仅有一条路径。

Huffman树：带权路径长度最小的二叉树应是权值大的外结点离根结点最近的扩充二叉树。 带路径长度最小的扩充二叉树不一定是完全二叉树。

集合是成员(元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。

字典是一些元素的集合，每个元素有一个称作关键码（key）的域，不同元素的关键码互不相同。

散列方法：理想的搜索方法是可以不经过比较，一次直接从字典中得到要搜索的元素。如果在元素存储位置与其关键码之间建立一个确定的对应函数关系Hash()， 使得每个关键码与结构中一个唯一的存储位置相对应：Address ＝ Hash(key)。在插入时依此函数计算存储位置并按此位置存放。在搜索时对元素的关键码进行同样的计算，把求得的函数值当做元素存储位置，在结构中按此位置搜索。这就是散列方法。在散列方法中所用转换函数叫做散列函数。按此方法构造出来的表叫做散列表。使用散列方法进行搜索不必进行多次关键码的比较, 搜索速度比较快, 可以直接到达或逼近具有此关键码的表项的实际存放地址。

散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了冲突

搜索就是在数据集合中寻找满足某种条件的数据对象。搜索的结果通常有两种可能：搜索成功，即找到满足条件的数据对象。这时，作为结果，可报告该对象在结构中 的位置, 还可给出该对象中的具体信息。搜索不成功，或搜索失败。作为结果，应报告一些信息, 如失败标志、位置等 搜索结构通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象(或记录)组成。在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为关键码。使用基于关键码的搜索，搜索结果应是唯一的。但在实际应用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可能不唯一。实施搜索时有两种不同的环境。静态环境，搜索结构在插入和删除等操作的前后不发生改变。? 静态搜索表 动态环境，为保持较高的搜索效率, 搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。? 动态搜索表

顺序搜索主要用于在线性表中搜索。设若表中有 CurrentSize 个元素，则顺序搜索从表的先端开始，顺序用各元素的关键码与给定值 x 进行比较若找到与其值相等的元素，则搜索成功，给出该元素在表中的位置。若整个表都已检测完仍未找到关键码与 x 相等的元素，则搜索失败。给出失败信息

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：1每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同。2左子树（如果非空）上所有结点的关键码都小于根结点的关键码。3右子树（如果非空）上所有结点的关键码都大于根结点的关键码。4左子树和右子树也是二叉搜索树。

二叉搜索树为二叉排序树如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树

在二叉搜索树上进行搜索，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设想要在二叉搜索树中搜索关键码为 x 的元素，搜索过程从根结点开始。如果根指针为NULL，则搜索不成功；否则用给定值 x 与根结点的关键码进行比较：若给定值等于根结点关键码，则搜索成功，返回搜索成功信息并报告搜索到结点地址。若给定值小于根结点的关键码，则继续递归搜索根结点的左子树；否则。递归搜索根结点的右子 二叉搜索树的插入算法：为了向二叉搜索树中插入一个新元素，必须先检查这个元素是否在树中已经存在。在插入之前，先使用搜索算法在树中检查要插入元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。

图定义：图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝( V, E ) 其中 V = { x | x ? 某个数据对象} 是顶点的有穷非空集合； E = {(x, y) | x, y ? V } 或E = {<x, y> | x, y ? V && Path (x, y)}，是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。 有向图与无向图：在有向图中，顶点对 <x, y> 是有序的。在无向图中，顶点对(x, y)是无序的。

完全图：若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图

在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。

邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。在邻接表中，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边（边结点），结点中有另一顶点的下标 dest 和指针 link。对于带权图，边结点中还要保存该边的权值cost。顶点表的第 i 个顶点中保存该顶点的数据，以及它对应边链表的头指针adj 最短路径问题：如果从图中某一顶点（称为源点）另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。

排序：将一组杂乱无章的数据按一定的规律顺次排列起来。 数据表(datalist): 它是待排序数据元素的有限集合。

排序码(key): 通常数据元素有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分元素, 作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。 插入排序基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上, 直到元素全部插入为止。

排序