浙江省计算机三级数据库复习资料全Word文件下载.docx
《浙江省计算机三级数据库复习资料全Word文件下载.docx》由会员分享，可在线阅读，更多相关《浙江省计算机三级数据库复习资料全Word文件下载.docx（25页珍藏版）》请在冰点文库上搜索。
顺序存储的线性表也称为顺序表。
线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。
插入、删除操作
单链表的插入操作：
1空表插入/头插入
if（head==null）
head=newNode<
T>
（x,null）;
//空表插入
else
{
Node<
q=newNode<
//头插入
q.next=head;
head=q;
}
2中间插入/尾插入
Node<
q.next=p.next;
p.next=q;
单链表的删除操作：
3头删除
head=head.next;
4中间/尾删除
if（p.next!
=null）
p.next=p.next.next;
双链表的插入操作：
q=newDLinkNode（x）;
q.prev=p.prev;
q.next=p;
p.prev.next=q;
p.prev=q;
双链表的删除操作：
p.prev.next=p.next;
（p.next）.prev=p.prev;
3）数组是一种数据结构，数据元素具有相同的数据类型。
数组逻辑结构与存储结构的关系：
数组采用的是顺序存储结构，即使用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存放次序与它们在线性表中的逻辑次序相同，即元素ai与其前驱a（i-1）及后继a（i+1）的存储位置相邻。
所以数组的存储结构表现其存储结构。
4）栈是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。
允许操作的一段称为栈顶，不允许操作的一端称为栈底。
栈中插入元素的操作称为入栈，删除元素的操作称为出栈。
没有元素的栈称为空栈。
栈的插入和删除只允许在栈顶进行，每次入栈即成为当前栈顶元素，每次出栈元素总是最后一个入栈元素，因此栈也称为后进先出表。
逻辑结构
存储结构
采用顺序存储结构的栈称为顺序栈，采用链式存储结构的栈称为链式栈。
进栈、出栈操作：
链式栈使用单链表即可，不需要使用循环链表或双链表，并且头结点的作用不明显。
采用不带头结点的单链表实现栈。
单链表的第一个结点为站定结点，设top指向栈顶结点，入栈操作是在当前栈顶结点之前插入新结点；
出栈操作是删除栈顶结点并返回栈顶元素值，再使top指向新的栈顶结点。
5）队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。
允许入队的一端称为队尾，允许出队的一端称为队头。
向队列中插入元素的过程成为入队，删除元素的过程成为出队。
没有元素的队列称为空队列。
由于插入和删除操作分别在队尾和队头进行，最先入队的元素总是最先出队，因此队列也称为先进先出表。
采用顺序存储结构的栈称为顺序队列，采用链式存储结构的栈称为链式队列。
循环队列：
如果循环使用顺序队列的连续存储单元，则将顺序队列设计成在逻辑上首尾相接的循环结构，称为顺序循环队列。
进队、出队操作：
以不带头结点的单链表实现链式队列。
设指针front和rear分别指向队头和队尾结点，入队操作将结点链在队尾结点之后，并使front指向新的队尾结点；
出队操作，当队列不空时，取得队头结点值，删除该节点，并使front指向后续结点。
6）二叉树是n（n>
=0）个结点组成的有限集合，n=0时称为空二叉树；
n>
0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。
二叉树也是递归定义的。
二叉树的性质
性质1：
若根结点的层次为1，则二叉树第i层最多有2i1（i≥1）个结点。
性质2：
在高度为k的二叉树中，最多有2k1个结点（k≥0）。
性质3：
设一棵二叉树的叶子结点数为n0，2度结点数为n2，则n0=n2+1。
性质4：
一棵具有n个结点的完全二叉树，其高度。
性质5：
一棵具有n个结点的完全二叉树，对序号为i（0≤i＜n）的结点，有：
1若i=0，则i为根结点，无父母结点；
若i>
0，则i的父母结点序号为。
2若2i+1＜n，则i的左孩子结点序号为2i+1；
否则i无左孩子。
3若2i+2＜n，则i的右孩子结点序号为2i+2；
否则i无右孩子。
二叉树的存储结构
1.二叉树的顺序存储结构
顺序存储结构仅适用于完全二叉树跟满二叉树。
2.二叉树的链式存储结构
二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问一次。
虽然二叉树是非线性结构，但遍历二叉树访问结点的次序是线性的，而且访问的规则和次序不止一种。
二叉树的遍历规则有孩子优先和兄弟优先。
孩子优先：
先根次序：
访问根结点，遍历左子树，遍历右子树。
中根次序：
遍历左子树，访问根结点，遍历右子树。
后根次序：
遍历左子树，遍历右子树，访问根结点
二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树。
哈夫曼树定义为带权外路径长度最短的二叉树
路径长度：
从根结点到所有结点的路径长度之和
（a）、（b）、（c）、（d）的路径长度为1x2+2x2+3x2=12
外路径长度：
从根结点到所有叶子结点的路径长度之和
（a）、（b）、（c）、（d）的外路径长度为2+3x2+1=9
从根到X结点的带权路径长度是X结点的权值与从根到X结点路径长度的乘积。
所有叶子结点的带权路径长度之和称为二叉树的带权外路径长度。
二叉树的带权外路径长度
7）检索方法：
（P259）顺序查找算法描述为：
从线性表的一端开始，依次将每个元素的关键字与给定值进行比较，若有相等者，则查找成功；
否则比较继续，直到比较完所有元素，仍未有相等者，则查找不成功，给出结果信息。
平均查找长度为（n+1）/2,查找一个元素的平均比较次数为n，查找失败需比较n+1次，时间复杂度为O（n）。
查找成功的平均查找长度：
查找失败的平均查找长度：
（P262）二分查找又叫折半查找，时间复杂度为O（log2n）。
折半查找算法分析
8）排序方法：
直接插入排序总的关键码比较次数为n^2/4，总的记录移动个数也约为n^2/4；
二分法插入排序关键码比较次数为O（nlog2n）,记录移动个数为O（n^2）；
shell排序法的关键码比较次数和记录移动个数均为n^1.3左右。
冒泡排序的最坏时间复杂度为O（n2）,最好的时间复杂度为O（n），算法的平均时间复杂度为O（n2）。
快速排序的最坏时间为O（n^2），平均时间复杂度为（nlgn）。
插入排序：
每趟将一个元素，按其关键字大小插入到它前面已排序的子序列中，使得插入后的子序列仍是排序的，依此重复，直到全部元素插入完毕。
直接插入排序
数据序列已排序（最好情况）的时间复杂度为O（n）
数据序列反序排列（最坏情况）的时间复杂度为O（n的平方）
数据序列随机排列的时间复杂度为O（n的平方）
折半插入排序
希尔排序
交换排序
冒泡排序的基本思想是：
比较相邻两个元素的关键字值，如果反序，则交换。
若按升序排序，每趟将被扫描的数据序列中的最大元素交换到最后位置，就像气泡从水里冒出来一样。
快速排序是一种分区交换排序算法。
快速排序的基本思想是;
在数据序列中选择一个值作为比较的基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，见大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置。
同时，序列被划分成两个子序列，再用同样的方法分别对两个子序列进行排序，直到子序列的长度为1，则完成排序。
选择排序
直接选择排序的基本思想是：
第一趟从n个元素的数据序列中选出关键字最小（或最大）的元素并放到最前（或最后）位置，下一趟再从n-1个元素中选出最小（大）的元素并放到次前（后）位置。
以此类推，经过n-1趟完成排序
堆排序
（1）创建最小堆
（2）堆排序
归并排序
数据库系统
1）数据库的基本概念：
信息是经过加工处理并对人类社会实践和生产活动产生决策影响的数据。
数据是人们用于记录事物情况的物理符号。
为了描述客观事物而用到的数字、字符以及所有能输入到计算机中并能被计算机处理的符号都可以看作是数据。
数据处理是指将数据转换成信息的过程。
它包括对数据的收集、存储、分类、计算、加工、检索和传输等一系列活动。
数据库系统的组成与结构
数据库系统是由计算机系统、数据库及其描述机构、数据库管理系统和有关人员组成。
考察数据库系统的结构可以有多种不同的层次或不同的角度。
从数据管理系统的角度看，数据库通常采用三级模式结构，这是数据库管理系统的内部结构；
从数据库最终用户的角度看，数据库系统的结构可分为集中式结构、分布式结构、客户/服务器结构、并型结构，这是数据库系统的外部的体系结构。
这里主要介绍数据库系统的内部结构——当前大部分数据库系统采用的三级模式结构。
数据库系统三级模式结构的概念和原理及其数据独立性
它包括外模式、模式和内模式。
模式：
是整个数据库当中所有实体和关系的集合，是所有用户的公共数据视图，与应用无关。
每个数据库中只有一个模式，也称逻辑模式。
外模式：
是模式的一个子集，或是模式的一个局部表现形态。
内模式：
也叫存储模式，是对模式的数据及数据的定义内容进行组织、存储的表达形式，在什么地方存储、如何存储是内模式要解决的内容
根据各类人员与数据库的不同关系，可把视图（所谓视图是指观察、认识和理解数据的范围、角度和方法）分为三种：
对应于用户的外部视图
对应于应用程序员的概念视图
对应于系统程序员的内部视图
2）数据库系统的数据模型：
常见的数据模型：
层次数据模型、网状数据模型、关系数据模型。
层次：
通过树形结构表示实体及联系。
如描述学校管理机构。
每个结点表示一个实体（型），箭头表示实体（型）间的联系（由父到子）。
层次数据模型主要特点：
有且仅有一个根结点；
每个非根结点有且仅有一个父（直接上层）结点。
它最适合表示实体的一对多联系。
网状：
通过网状结构表示实体及联系。
“网”中每个结点表示一个实体（型），结点之间箭头表示实体（型）间的联系。
网状数据模型主要特点：
网状数据模型可能有多个根结点，某些非根结点可能有多个父结点，适合表示实体的多对多联系。
层次与网状模型优缺点:
优点:
能直观、形象地描述实体及其联系，易于被人们所理解和掌握。
缺点:
数据结构较复杂，存储数据需要更多的链接指针；
在检索数据时，需要考虑数据的存储路径；
在插入或删除数据时，涉及到调整链接指针。
关系
关系模型与层次模型和网状模型相比有着本质的差别，它是用二维表格来表示实体及其相互之间的联系。
一个关系就是没有重复行和重复列的二维表，二维表的每一行在关系中称为元组，每一列在关系中称为属性。
学生关系的每一行代表一个学生的记录，每一列代表学生记录的一个字段。
属性个数（n）称为关系的元。
关系、关系模式、关系数据库模式、关系数据库的定义（关系、元组、属性、域、关键字、数据项）
关系：
⏹关系的描述称为关系模式，可以表示为R（U,D,DOM,F）
R为关系名，U为属性名集合，D为域集合，DOM为属性向域的映像集合，F为属性间的依赖关系集合
⏹关系模式是型，关系是值
⏹例：
学生选修课成绩登记表，定义关系模式SC如下：
SC（
{sno,cno,grade},
{N（6）,N（3）},
{（sno,N（6））,（cno,N（3））,（grade,N（3））},
{（sno,cno）→grade}
）
关系模式：
关系数据库：
⏹关系数据库基本概念
关系数据库就是一些相关的二维表和其他数据库对象的集合。
关系数据库中的所有信息都存储在二维表格中；
一个关系数据库可能包含多个表；
除了这种二维表外，关系数据库还包含一些其他对象，如视图等。
1．关系
一个关系就是一张二维表，通常将一个没有重复行、重复列的二维表看成一个关系，每个关系都有一个关系名。
2．元组
二维表的每一行在关系中称为元组（Tuple）。
一行描述了现实世界中的一个实体，或者描述了不同实体间的一种联系。
3．属性
二维表的每一列在关系中称为属性（Attribute），每个属性都有一个属性名，各个属性的取值称为属性值。
每个属性有一定的取值范围，称为值域。
4．关键字
关系中能惟一区分、确定不同元组的属性或属性组合，称为该关系的一个关键字。
关键字又称为键或码（Key）。
码
候选码
能唯一标示一个元组的属性组
主码
多个候选码中的主要应用属性组，其中的
每个属性都称为主属性，不属于任何候选
码的属性称为非码属性
合成码
码含有多个属性
外码
不是当前关系的码，但是其他关系中的
全码
所有属性共同组成关系模式的候选码
5．域（集合）
域是一组具有相同数据类型的值的集合。
6.主属性和非主属性
定义5设Ai是关系模式R的一个属性，若Ai属于R的某个候选关键属性，称Ai是R的主属性，否则，称Ai为非主属性。
3）关系运算：
选择、投影、集合并运算、集合差运算、笛卡儿积、连接
运算符
含义
集合运算符
∪
－
∩
并
差
交
逻辑运算符
┐
Λ
ν
非
与
或
专门的关系运算符
×
σ
∏
∞
%
广义笛卡尔积
选择
投影
连接
除
比较运算符
≥
>
≤
<
=
≠
大于等于
大于
小于等于
小于
等于
不等于
1.选择（selection）:
对关系而言，选择是从行的角度取关系的子集
公式表示:
R[F]或σF（R）={t|t∈RΛF（t）=True}
公式的含义：
R中使布尔函数为真的元组集，F为布尔函数，即限定条件
F的基本形式为：
x1θy1[Φx2θy2……],其中θ为比较运算符，Φ为逻辑运算符，x1,y1是属性名或常量，属性名也可用序号表示
例：
σ5=‘IS’（student）或student[5=‘IS’]
σSage<
19（student）或student[Sage<
19]
2.投影（projection）:
对关系而言，投影是从列的角度取关系的子集
R[A]或∏A（R）={t[A]|t∈R}
包含A中各属性组的元组集
投影之后不仅取消了某些属性列，而且还可能取消某些元组
∏Sname,Sdept（student）或student[Sname,Sdept]
∏2,5（student）或student[2,5]
3.集合并（union）
R∪S={t|t∈Rνt∈S}
R、S为同类关系（关系的度相同，且相应属性都来自相同的域），并的结果与R、S也是同类关系
⏹R和S
具有相同的目n
相应的属性取自同一个域
⏹R-S
仍为n目关系，由属于R而不属于S的所有元组组成
R-S={t|tR∧tS}
4.集合差（difference）
R－S={t|t∈RΛ┐t∈S}={t|t∈RΛt∈S}
R、S为同类关系，差的结果与R、S也是同类关系
5．笛卡尔积
给定一组域D1,D2，...，Dn，这些域可以完全不同，也可以部分或全部相同，D1、D2、…、Dn的笛卡尔积为：
D1×
D2×
…×
Dn={（d1，d2，…，dn）|di∈Di，i=1，2，…，n}，其中每一个元素（d1，d2，…，dn）称作一个n元组（n-tuple）或简称元组，它的每个元素di取自对应的集合Di。
元组中的每一个值di称作一个分量（component）
若di为有限集，其基数为mi（i=1,2,3…n）,则D1×
Dn的基数为
m=∏mi
例如，设A={1，2}，B={a，b}，则A×
B={（1，a），（1，b），（2，a），（2，b）}。
6.连接（join）:
R∞FS或R[F]S={trts|tr∈RΛts∈SΛF（tr,ts）=True}
或表示为：
R∞AθBS或R[F]S={trts|tr∈RΛts∈SΛtr[A]θts[B]）=True}
从两个关系的笛卡尔积中选取属性间满足一定条件的元组
4）关系数据库基本概念：
函数依赖的基本概念
定义1对于R中属性X的任何一个具体值，Y仅有唯一的具体值与之对应，则称R的属性Y函数依赖于属性X。
记为：
X→Y，X称为决定因素。
完全函数依赖、部分函数依赖
定义2在R中，如果属性集Y函数依赖于属性集X，且不函数依赖于X的任意真子集，则称Y完全函数依赖于X，记做：
XY，否则，称Y部分函数依赖于X，记做：
XY。
关系SC（Sno,Cno,Grade）中，由于
SnoGrade,CnoGrade，所以有
（Sno,Cno）Grade
传递函数依赖
定义3设X，Y，Z是关系模式R的不同属性集，若XY（并且Y∈X），YZ，称X传递决定Z，或称Z传递函数依赖于X，记做XZ。
如关系Std（Sno,Sdept,Mname）中，有
Sno→Sdept，Sdept→Mname，且Sdept∈Sno，
所以SnoMname
5）规范化理论：
第一范式、第二范式、第三范式的定义
第一范式：
⏹对关系模式的规范化要求分成从低到高不同的层次，分别称为第1范式、第2范式、第3范式、Boyce-Codd范式、第4范式和第5范式。
⏹定义6当关系模式R的所有属性都不能分解为更基本的数据单位时，称R是满足第1范式的，则R∈1NF。
⏹第1范式要求一行中的每一列仅有唯一的值并且具有原子性。
例如，如果关于员工的关系中有一个工资属性，而工资又由更基本的两个数据项基本工资和岗位工资组成，则这个员工的关系模式就不满足1NF。
第二范式：
⏹定义7如果关系模式R满足第1范式，并且R的所有非主属性都完全函数依赖于R的码，称R满足第2范式，简记为R∈2NF。
⏹例如在学生表（学号,姓名,系名,系负责人,课程名,成绩）中存在非主属性对码的部分函数依赖
姓名,系名,系负责人完全函数依赖于学号
姓名,系名,系负责人部分函数依赖于{学号，课程名}
⏹消除表中非主属性对码的部分函数依赖
⏹采取投影分解方法得到两个新的关系
学生情况（学号,姓名,系名,系负责人）
成绩（学号，课程名，成绩）
第三范式：
⏹定义8如果R∈2NF，且它的任何一个非主属性都不传递依赖于R的任意一个候选关键字，称R满足第3范式，简记为R∈3NF。
⏹第三范式要求非主键列互不依赖，消除传递依赖。
如果非主属性之间存在了函数依赖，就会存在传递依赖，这样就不满足第三范式。
定理若关系模式R符合3NF条件，则R一定符合2NF条件。
⏹消除表中非主属性对码的传递函数依赖
将函数关系中起传递作用的非主属性（决定方）和由它完全决定的非主属性取出单独构成一个关系模式
将决定方和余下的非主属性加上主码构成另外一个关系模式
升级会员 