浙江省计算机三级数据库复习资料

1、-. z.数据构造根底数据构造的根本概念及有关术语：数据是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机承受的各种符号集合的统称。表示一个事物的一组数据称为一个数据元素，数据元素是数据的根本单位。它可以是一个不可分割的原子项，也可以由多个数据项组成。数据类型是指一个类型和定义在这个类型上的操作集合。数据构造data structure指数据元素之间存在的关系数据的逻辑构造是指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的假设干关系来表示，常被称为数据构造。根据数据元素之间逻辑关系的不同数学特性，数据构造可分为三种：线性构造、树构造和图，其中树构造和图又称为非线性构

2、造。P2数据元素及其关系在计算机中的存储表示或实现称为数据的存储构造，也称为物理构造。数据的逻辑构造从逻辑关系角度观察数据，与数据的存储无关，是独立与计算机的。而数据的存储构造是逻辑构造在计算机存中的实现，是依赖于计算机的。数据存储构造的根本形式有两种：顺序存储构造和链式存储构造。数据的存储构造被分为顺序构造、构造、索引构造、散列构造四种算法是一个有穷规则的集合，其规则确定一个解决*一特定类型问题的操作序列。算法分析主要包含时间代价和空间代价两个方面。时间代价就是当问题的规模以*种单位由1增至n时，解决该问题的算法实现运行时所消耗的时间，也以*种单位由f(1)增至f(n)，则称该算法的时间代价

3、为f(n)。空间代价就是当问题的规模以*种单位由1增至n时，解决该问题的算法实现运行时所消耗的空间，也以*种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。算法的时间及空间复杂性度量算法的时间效率算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率。T(n)=O(f(n) 度量算法的空间效率空间复杂度指算法在执行时为解决问题所需要的额外存空间，不包括输入数据所占用的存储空间。 S(n)=O(f(n) 根本数据构造及其操作：线性表是由n(n=0)个类型一样的数据元素a0,a1,a(n-1)组成的有限序列。P36线性表的逻辑构造：其中，元素

4、ai的数据类型可以是整数、浮点数、字符或类；n是线性表的元素个数，称为线性长度。假设n=0,则为空表；假设n0,ai(0in-1)有且仅有一个前驱元素a(i-1),没有后继元素a(i+1),a0没有前驱元素，a(n-1)没有后继元素线性表的存储构造顺序存储、链式存储线性表的顺序存储构造使用一组连续的存单元依次存放线性表的数据元素，元素在存的物理存放次序与它们在线性表中的逻辑次序一样，即元素ai与其前驱a(i-1)及后继a(i+1)的存储位置相邻。顺序存储的线性表也称为顺序表。线性表的链式存储是用假设干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表

5、示数据元素之间的顺序关系。插入、删除操作单链表的插入操作：空表插入/头插入if(head=null) head=new Node(*,null); /空表插入else Nodeq= new Node(*,null); /头插入 q.ne*t=head; head=q;中间插入/尾插入Nodeq= new Node(*,null); q.ne*t=p.ne*t; p.ne*t=q;单链表的删除操作：头删除head = head.ne*t;中间/尾删除if (p.ne*t!=null) p.ne*t = p.ne*t.ne*t;双链表的插入操作：q = new DLinkNode(*);q.pre

6、v = p.prev;q.ne*t = p;p.prev.ne*t = q;p.prev = q;双链表的删除操作：p.prev.ne*t = p.ne*t;if (p.ne*t!=null) (p.ne*t).prev = p.prev;数组是一种数据构造，数据元素具有一样的数据类型。数组逻辑构造与存储构造的关系：数组采用的是顺序存储构造，即使用一组连续的存单元依次存放线性表的数据元素，元素在存的物理存放次序与它们在线性表中的逻辑次序一样，即元素ai与其前驱a(i-1)及后继a(i+1)的存储位置相邻。所以数组的存储构造表现其存储构造。栈是一种特殊的线性表，其插入和删除操作只允许在线性表的一

7、端进展。允许操作的一段称为栈顶，不允许操作的一端称为栈底。栈中插入元素的操作称为入栈，删除元素的操作称为出栈。没有元素的栈称为空栈。栈的插入和删除只允许在栈顶进展，每次入栈即成为当前栈顶元素，每次出栈元素总是最后一个入栈元素，因此栈也称为后进先出表。逻辑构造存储构造采用顺序存储构造的栈称为顺序栈，采用链式存储构造的栈称为链式栈。进栈、出栈操作：链式栈使用单链表即可，不需要使用循环链表或双链表，并且头结点的作用不明显。采用不带头结点的单链表实现栈。单链表的第一个结点为站定结点，设top指向栈顶结点，入栈操作是在当前栈顶结点之前插入新结点；出栈操作是删除栈顶结点并返回栈顶元素值，再使top指向新的

8、栈顶结点。队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进展。允许入队的一端称为队尾，允许出队的一端称为队头。向队列中插入元素的过程成为入队，删除元素的过程成为出队。没有元素的队列称为空队列。由于插入和删除操作分别在队尾和队头进展，最先入队的元素总是最先出队，因此队列也称为先进先出表。逻辑构造存储构造采用顺序存储构造的栈称为顺序队列，采用链式存储构造的栈称为链式队列。循环队列：如果循环使用顺序队列的连续存储单元，则将顺序队列设计成在逻辑上首尾相接的循环构造，称为顺序循环队列。进队、出队操作：以不带头结点的单链表实现链式队列。设指针front和rear分别指向队头和队尾结点，入队操作

9、将结点链在队尾结点之后，并使front指向新的队尾结点；出队操作，当队列不空时，取得队头结点值，删除该节点，并使front指向后续结点。二叉树是nn=0个结点组成的有限集合，n=0时称为空二叉树；n0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。二叉树也是递归定义的。二叉树的性质性质1：假设根结点的层次为1，则二叉树第i层最多有2i1i1个结点。性质2：在高度为k的二叉树中，最多有2k1个结点k0。性质3：设一棵二叉树的叶子结点数为n0，2度结点数为n2，则n0=n2+1。性质4：一棵具有n个结点的完全二叉树，其高度。性质5：一棵具有n个结点的完全二叉树，对序号为

10、i0in的结点，有：假设i=0，则i为根结点，无父母结点；假设i0，则i的父母结点序号为。假设2i+1n，则i的左孩子结点序号为2i+1；否则i无左孩子。假设2i+2n，则i的右孩子结点序号为2i+2；否则i无右孩子。二叉树的存储构造二叉树的顺序存储构造顺序存储构造仅适用于完全二叉树跟满二叉树。二叉树的链式存储构造二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问一次。虽然二叉树是非线性构造，但遍历二叉树访问结点的次序是线性的，而且访问的规则和次序不止一种。二叉树的遍历规则有孩子优先和兄弟优先。孩子优先：先根次序：访问根结点，遍历左子树，遍历右子树。中根次序：遍历左子

11、树，访问根结点，遍历右子树。后根次序：遍历左子树，遍历右子树，访问根结点二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树：1假设左子树不空，则左子树上所有结点的值均小于它的根结点的值；2假设右子树不空，则右子树上所有结点的值均大于它的根结点的值；3左、右子树也分别为二叉排序树。哈夫曼树定义为带权外路径长度最短的二叉树路径长度：从根结点到所有结点的路径长度之和(a)、(b)、c、(d)的路径长度为1*2+2*2+3*2=12外路径长度：从根结点到所有叶子结点的路径长度之和(a)、(b)、c、(d)的外路径长度为2+3*2+1=9从根到*结点的带权路径长度是*结点的权值与从根

12、到*结点路径长度的乘积。所有叶子结点的带权路径长度之和称为二叉树的带权外路径长度。二叉树的带权外路径长度检索方法：P259顺序查找算法描述为：从线性表的一端开场，依次将每个元素的关键字与给定值进展比拟，假设有相等者，则查找成功；否则比拟继续，直到比拟完所有元素，仍未有相等者，则查找不成功，给出结果信息。平均查找长度为n+1/2,查找一个元素的平均比拟次数为n，查找失败需比拟n+1次，时间复杂度为O(n)。查找成功的平均查找长度：查找失败的平均查找长度：P262二分查找又叫折半查找，时间复杂度为O(log2n)。折半查找算法分析排序方法：直接插入排序总的关键码比拟次数为n2/4，总的记录移动个数

13、也约为n2/4；二分法插入排序关键码比拟次数为O(nlog2n),记录移动个数为O(n2)；shell排序法的关键码比拟次数和记录移动个数均为n1.3左右。冒泡排序的最坏时间复杂度为O(n2),最好的时间复杂度为O(n)，算法的平均时间复杂度为O(n2)。快速排序的最坏时间为O(n2)，平均时间复杂度为(nlgn)。插入排序：每趟将一个元素，按其关键字大小插入到它前面已排序的子序列中，使得插入后的子序列仍是排序的，依此重复，直到全部元素插入完毕。直接插入排序数据序列已排序最好情况的时间复杂度为On数据序列反序排列最坏情况的时间复杂度为On的平方数据序列随机排列的时间复杂度为On的平方折半插入排

14、序希尔排序交换排序冒泡排序的根本思想是：比拟相邻两个元素的关键字值，如果反序，则交换。假设按升序排序，每趟将被扫描的数据序列中的最大元素交换到最后位置，就像气泡从水里冒出来一样。快速排序是一种分区交换排序算法。快速排序的根本思想是;在数据序列中选择一个值作为比拟的基准值，每趟从数据序列的两端开场交替进展，将小于基准值的元素交换到序列前端，见大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置。同时，序列被划分成两个子序列，再用同样的方法分别对两个子序列进展排序，直到子序列的长度为1，则完成排序。选择排序直接选择排序的根本思想是：第一趟从n个元素的数据序列中选出关键字最小或最

15、大的元素并放到最前或最后位置，下一趟再从n-1个元素中选出最小大的元素并放到次前后位置。以此类推，经过n-1趟完成排序堆排序1创立最小堆2堆排序归并排序数据库系统数据库的根本概念：信息是经过加工处理并对人类社会实践和生产活动产生决策影响的数据。数据是人们用于记录事物情况的物理符号。为了描述客观事物而用到的数字、字符以及所有能输入到计算机中并能被计算机处理的符号都可以看作是数据。数据处理是指将数据转换成信息的过程。它包括对数据的收集、存储、分类、计算、加工、检索和传输等一系列活动。数据库系统的组成与构造数据库系统是由计算机系统、数据库及其描述机构、数据库管理系统和有关人员组成。考察数据库系统的构

16、造可以有多种不同的层次或不同的角度。从数据管理系统的角度看，数据库通常采用三级模式构造，这是数据库管理系统的部构造；从数据库最终用户的角度看，数据库系统的构造可分为集中式构造、分布式构造、客户/效劳器构造、并型构造，这是数据库系统的外部的体系构造。这里主要介绍数据库系统的部构造当前大局部数据库系统采用的三级模式构造。数据库系统三级模式构造的概念和原理及其数据独立性它包括外模式、模式和模式。模式：是整个数据库当中所有实体和关系的集合，是所有用户的公共数据视图，与应用无关。每个数据库中只有一个模式，也称逻辑模式。外模式：是模式的一个子集，或是模式的一个局部表现形态。模式：也叫存储模式，是对模式的数

17、据及数据的定义容进展组织、存储的表达形式，在什么地方存储、如何存储是模式要解决的容根据各类人员与数据库的不同关系，可把视图所谓视图是指观察、认识和理解数据的围、角度和方法分为三种：对应于用户的外部视图对应于应用程序员的概念视图对应于系统程序员的部视图数据库系统的数据模型：常见的数据模型：层次数据模型、网状数据模型、关系数据模型。层次：通过树形构造表示实体及联系。如描述学校管理机构。每个结点表示一个实体型，箭头表示实体型间的联系由父到子。层次数据模型主要特点：有且仅有一个根结点；每个非根结点有且仅有一个父(直接上层)结点。它最适合表示实体的一对多联系。网状：通过网状构造表示实体及联系。网中每个结

18、点表示一个实体(型)，结点之间箭头表示实体(型)间的联系。网状数据模型主要特点：网状数据模型可能有多个根结点，*些非根结点可能有多个父结点，适合表示实体的多对多联系。层次与网状模型优缺点:优点:能直观、形象地描述实体及其联系，易于被人们所理解和掌握。缺点:数据构造较复杂，存储数据需要更多的指针；在检索数据时，需要考虑数据的存储路径；在插入或删除数据时，涉及到调整指针。关系关系模型与层次模型和网状模型相比有着本质的差异，它是用二维表格来表示实体及其相互之间的联系。一个关系就是没有重复行和重复列的二维表，二维表的每一行在关系中称为元组，每一列在关系中称为属性。学生关系的每一行代表一个学生的记录，每

19、一列代表学生记录的一个字段。属性个数n称为关系的元。关系、关系模式、关系数据库模式、关系数据库的定义关系、元组、属性、域、关键字、数据项关系：关系的描述称为关系模式，可以表示为R(U,D,DOM,F)R为关系名，U为属性名集合，D为域集合，DOM为属性向域的映像集合，F为属性间的依赖关系集合关系模式是型，关系是值例：学生选修课成绩登记表，定义关系模式SC如下：SCsno,o,grade,N(6),N(3),(sno,N(6),(o,N(3),(grade,N(3),(sno,o)grade关系模式：关系的描述称为关系模式，可以表示为R(U,D,DOM,F)R为关系名，U为属性名集合，D为域集合

20、，DOM为属性向域的映像集合，F为属性间的依赖关系集合关系模式是型，关系是值例：学生选修课成绩登记表，定义关系模式SC如下：SCsno,o,grade,N(6),N(3),(sno,N(6),(o,N(3),(grade,N(3),(sno,o)grade关系数据库：关系数据库根本概念关系数据库就是一些相关的二维表和其他数据库对象的集合。关系数据库中的所有信息都存储在二维表格中；一个关系数据库可能包含多个表；除了这种二维表外，关系数据库还包含一些其他对象，如视图等。1关系一个关系就是一二维表，通常将一个没有重复行、重复列的二维表看成一个关系，每个关系都有一个关系名。2元组二维表的每一行在关系中

21、称为元组(Tuple)。一行描述了现实世界中的一个实体，或者描述了不同实体间的一种联系。3属性二维表的每一列在关系中称为属性(Attribute)，每个属性都有一个属性名，各个属性的取值称为属性值。每个属性有一定的取值围，称为值域。4关键字关系中能惟一区分、确定不同元组的属性或属性组合，称为该关系的一个关键字。关键字又称为键或码(Key)。码候选码能唯一标示一个元组的属性组主码多个候选码中的主要应用属性组，其中的每个属性都称为主属性，不属于任何候选码的属性称为非码属性合成码码含有多个属性外码不是当前关系的码，但是其他关系中的主码全码所有属性共同组成关系模式的候选码5域集合域是一组具有一样数据类

22、型的值的集合。6.主属性和非主属性定义5 设Ai是关系模式R的一个属性，假设Ai属于R的*个候选关键属性，称Ai是R的主属性，否则，称Ai为非主属性。关系运算：选择、投影、集合并运算、集合差运算、笛卡儿积、连接运算符含义运算符含义集合运算符并差交逻辑运算符非与或专门的关系运算符%广义笛卡尔积选择投影连接除比拟运算符=大于等于大于小于等于小于等于不等于1.选择selection:对关系而言，选择是从行的角度取关系的子集公式表示:RF或F(R)=t|tR F(t)=True公式的含义：R中使布尔函数为真的元组集，F为布尔函数，即限定条件F的根本形式为：*1y1*2y2,其中为比拟运算符，为逻辑运算

23、符，*1,y1是属性名或常量，属性名也可用序号表示例：5=IS(student) 或 student5=ISSage19(student) 或 studentSage192.投影projection:对关系而言，投影是从列的角度取关系的子集公式表示:RA或A(R)=tA|tR公式的含义：包含A中各属性组的元组集投影之后不仅取消了*些属性列，而且还可能取消*些元组例：Sname,Sdept(student)或 studentSname,Sdept2,5(student)或 student2,53.集合并unionR S=t|t R t SR、S为同类关系关系的度一样，且相应属性都来自一样的域，并

24、的结果与R、S也是同类关系R和S具有一样的目n相应的属性取自同一个域R - S 仍为n目关系，由属于R而不属于S的所有元组组成R -S = t|tRtS 4.集合差differenceR S=t|t R t S= t|t R t SR、S为同类关系，差的结果与R、S也是同类关系R和S具有一样的目n相应的属性取自同一个域R - S 仍为n目关系，由属于R而不属于S的所有元组组成 R -S = t|tRtS 5笛卡尔积给定一组域D1,D2，.，Dn，这些域可以完全不同，也可以局部或全部一样，D1、D2、Dn的笛卡尔积为：D1D2Dn= (d1，d2，dn)|diDi，i=1，2，n，其中每一个元素

25、(d1，d2，dn)称作一个n元组n-tuple或简称元组，它的每个元素di取自对应的集合Di。元组中的每一个值di称作一个分量ponent假设di为有限集，其基数为mi(i=1,2,3n),则D1D2Dn的基数为m=mi例如，设A=1，2，B=a，b，则AB=(1，a)，(1，b)，(2，a)，(2，b)。6.连接join:公式表示:R F S或RFS=trts|trR ts S F(tr,ts)=True或表示为：R A B S或RFS=trts|trR ts S trAtsB)=True公式的含义：从两个关系的笛卡尔积中选取属性间满足一定条件的元组关系数据库根本概念：函数依赖的根本概念定义1 对于R中属性*的任何一个具体值，Y仅有唯一的具体值与之对应，则称R的属性Y函数依赖于属性*。记为：*Y，*称为决定因素。完全函数依赖、局部函数依赖定义2 在R中，如果属性集Y函数依赖于属性集*，且不函数依赖于*的任意真子集，则称Y完全函数依赖于*，记做： * Y，否则，称Y局部函数依赖于*，记做：* Y 。例：关系SC