2023年浙江省计算机三级数据库复习资料.docx

数据构造基本1） 数据构造基本概念及有关术语：数据是描述客观事物数字、字符以及所有能输入到计算机中并能被计算机接受多种符号集合统称。体现一种事物一组数据称为一种数据元素，数据元素是数据基本单位。它可以是一种不可分割原子项，也可以由多种数据项构成。数据类型是指一种类型和定义在这个类型上操作集合。数据构造（data structure）指数据元素之间存在关系数据逻辑构造是指数据元素之间逻辑关系，用一种数据元素集合和定义在此集合上若干关系来体现，常被称为数据构造。根据数据元素之间逻辑关系不一样数学特性，数据构造可分为三种：线性构造、树构造和图，其中树构造和图又称为非线性构造。P2数据元素及其关系在计算机中存储体现或实现称为数据存储构造，也称为物理构造。数据逻辑构造从逻辑关系角度观测数据，与数据存储无关，是独立与计算机。而数据存储构造是逻辑构造在计算机内存中实现，是依赖于计算机。数据存储构造基本形式有两种：次序存储构造和链式存储构造。数据存储构造被分为次序构造、链接构造、索引构造、散列构造四种算法是一种有穷规则集合，其规则确定一种处理某一特定类型问题操作序列。算法分析重要包括时间代价和空间代价两个方面。时间代价就是当问题规模以某种单位由1增至n时，处理该问题算法实现运行时所消耗时间，也以某种单位由f(1)增至f(n)，则称该算法时间代价为f(n)。空间代价就是当问题规模以某种单位由1增至n时，处理该问题算法实现运行时所消耗空间，也以某种单位由g(1)增至g(n)，则称该算法空间代价为g(n)。算法时间及空间复杂性 度量算法时间效率算法时间效率指算法执行时间随问题规模增长而增长趋势，一般采用时间复杂度来度量算法时间效率。T(n)=O(f(n) 度量算法空间效率空间复杂度指算法在执行时为处理问题所需要额外内存空间，不波及输入数据所占用存储空间。 S(n)=O(f(n) 2） 基本数据构造及其操作：线性表是由n(n=0)个类型相似数据元素a0,a1,a(n-1)构成有限序列。P36线性表逻辑构造：其中，元素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)存储位置相邻。次序存储线性表也称为次序表。线性表链式存储是用若干地址分散存储单元存储数据元素，逻辑上相邻数据元素在物理位置上不一定相邻，必要采用附加信息体现数据元素之间次序关系。插入、删除操作单链表插入操作： 空表插入/头插入if(head=null) head=new Node(x,null)； /空表插入else Nodeq= new Node(x,null)； /头插入 q.next=head; head=q; 中间插入/尾插入Nodeq= new Node(x,null)； q.next=p.next; p.next=q;单链表删除操作： 头删除head = head.next; 中间/尾删除if (p.next!=null) p.next = p.next.next;双链表插入操作：q = new DLinkNode(x);q.prev = p.prev;q.next = p;p.prev.next = q;p.prev = q;双链表删除操作：p.prev.next = p.next;if (p.next!=null) (p.next).prev = p.prev;3） 数组是一种数据构造，数据元素具有相似数据类型。数组逻辑构造与存储构造关系：数组采用是次序存储构造，虽然用一组持续内存单元依次存储线性表数据元素，元素在内存物理存储次序与它们在线性表中逻辑次序相似，即元素ai与其前驱a(i-1)及后继a(i+1)存储位置相邻。因此数组存储构造体现其存储构造。4） 栈是一种特殊线性表，其插入和删除操作只容许在线性表一端进行。容许操作一段称为栈顶，不容许操作一端称为栈底。栈中插入元素操作称为入栈，删除元素操作称为出栈。没有元素栈称为空栈。栈插入和删除只容许在栈顶进行，每次入栈即成为目前栈顶元素，每次出栈元素总是最终一种入栈元素，因而栈也称为后进先出表。逻辑构造存储构造采用次序存储构造栈称为次序栈，采用链式存储构造栈称为链式栈。进栈、出栈操作：链式栈使用单链表即可，不需要使用循环链表或双链表，并且头结点作用不明显。采用不带头结点单链表实现栈。单链表第一种结点为站定结点，设top指向栈顶结点，入栈操作是在目前栈顶结点之前插入新结点；出栈操作是删除栈顶结点并返回栈顶元素值，再使top指向新栈顶结点。5） 队列是一种特殊线性表，其插入和删除操作分别在线性表两端进行。容许入队一端称为队尾，容许出队一端称为队头。向队列中插入元素过程成为入队，删除元素过程成为出队。没有元素队列称为空队列。由于插入和删除操作分别在队尾和队头进行，最先入队元素总是最先出队，因而队列也称为先进先出表。逻辑构造存储构造采用次序存储构造栈称为次序队列，采用链式存储构造栈称为链式队列。循环队列：假如循环使用次序队列持续存储单元，则将次序队列设计成在逻辑上首尾相接循环构造，称为次序循环队列。进队、出队操作：以不带头结点单链表实现链式队列。设指针front和rear分别指向队头和队尾结点，入队操作将结点链在队尾结点之后，并使front指向新队尾结点；出队操作，当队列不空时，获得队头结点值，删除该节点，并使front指向后续结点。6） 二叉树是n（n0）个结点构成有限集合，n=0时称为空二叉树；n0二叉树由一种根结点和两棵互不相交、分别称为左子树和右子树子二叉树构成。二叉树也是递归定义。二叉树性质性质1：若根结点层次为1，则二叉树第i层最多有2i-1（i1）个结点。 性质2：在高度为k二叉树中，最多有2k-1个结点（k0）。 性质3：设一棵二叉树叶子结点数为n0，2度结点数为n2，则n0=n2+1。 性质4：一棵具有n个结点完全二叉树，其高度 。性质5：一棵具有n个结点完全二叉树，对序号为i（0in）结点，有： 若i=0，则i为根结点，无父母结点；若i0，则i父母结点序号为。 若2i+1n，则i左孩子结点序号为2i+1；否则i无左孩子。 若2i+2n，则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） 排序措施：直接插入排序总关键码比较次数为n2/4，总记录移动个数也约为n2/4；二分法插入排序关键码比较次数为O(nlog2n),记录移动个数为O(n2)；shell排序法关键码比较次数和记录移动个数均为n1.3左右。冒泡排序最坏时间复杂度为O(n2),最佳时间复杂度为O(n)，算法平均时间复杂度为O(n2)。迅速排序最坏时间为O(n2)，平均时间复杂度为(nlgn)。插入排序：每趟将一种元素，按其关键字大小插入到它前面已排序子序列中，使得插入后子序列仍是排序，依此反复，直到所有元素插入完毕。直接插入排序数据序列已排序（最佳状况）时间复杂度为O（n）数据序列反序排列（最坏状况）时间复杂度为O（n平方）数据序列随机排列时间复杂度为O（n平方）折半插入排序希尔排序互换排序冒泡排序基本思想是：比较相邻两个元素关键字值，假如反序，则互换。若按升序排序，每趟将被扫描数据序列中最大元素互换到最终位置，就像气泡从水里冒出来同样。迅速排序是一种分区互换排序算法。迅速排序基本思想是;在数据序列中选用一种值作为比较基准值，每趟从数据序列两端开始交替进行，将不不小于基准值元素互换到序列前端，见不不不小于基准值元素互换到序列后端，介于两者之间位置则成为基准值最终位置。同步，序列被划提成两个子序列，再用同样措施分别对两个子序列进行排序，直到子序列长度为1，则完毕排序。选用排序直接选用排序基本思想是：第一趟从n个元素数据序列中选出关键字最小（或最大）元素并放到最前（或最终）位置，下一趟再从n-1个元素中选出最小（大）元素并放到次前（后）位置。以此类推，通过n-1趟完毕排序堆排序（1）创立最小堆（2）堆排序归并排序数据库系统 1） 数据库基本概念：信息是通过加工处理并对人类社会实践和生产活动产生决策影响数据。数据是人们用于记录事物状况物理符号。为了描述客观事物而用到数字、字符以及所有能输入到计算机中并能被计算机处理符号都可以看作是数据。数据处理是指将数据转换成信息过程。它波及对数据搜集、存储、分类、计算、加工、检索和传播等一系列活动。数据库系统构成与构造数据库系统是由计算机系统、数据库及其描述机构、数据库管理系统和有关人员构成。考察数据库系统构造可以有多种不一样层次或不一样角度。从数据管理系统角度看，数据库一般采用三级模式构造，这是数据库管理系统内部构造；从数据库最终顾客角度看，数据库系统构造可分为集中式构造、分布式构造、客户/服务器构造、并型构造，这是数据库系统外部体系构造。这里重要简介数据库 系统内部构造目前大某些数据库系统采用三级模式构造。数据库系统三级模式构造概念和原理及其数据独立性它波及外模式、模式和内模式 。模式：是整个数据库当中所有实体和关系集合，是所有顾客公共数据视图，与应用无关。每个数据库中只有一种模式，也称逻辑模式。外模式：是模式一种子集，或是模式一种局部体现形态。内模式：也叫存储模式，是对模式数据及数据定义内容进行组织、存储体现形式，在什么地方存储、怎样存储是内模式要处理内容根据各类人员与数据库不一样关系，可把视图（所谓视图是指观测、认识和理解数据范围、角度和措施）分为三种： 对应于顾客外部视图 对应于应用程序员概念视图 对应于系统程序员内部视图2） 数据库系统数据模型：常用数据模型：层次数据模型、网状数据模型、关系数据模型。层次：通过树形构造体现实体及联络。如描述学校管理机构。每个结点体现一种实体（型），箭头体现实体（型）间联络（由父到子）。层次数据模型重要特点：有且仅有一种根结点；每个非根结点有且仅有一种父(直接上层)结点。它最适合体现实体一对多联络。网状：通过网状构造体现实体及联络。“网”中每个结点体现一种实体(型)，结点之间箭头体现实体(型)间联络。网状数据模型重要特点：网状数据模型也许有多种根结点，某些非根结点也许有多种父结点，适合体现实体多对多联络。层次与网状模型优缺陷:长处:能直观、形象地描述实体及其联络，易于被人们所理解和掌握 。缺陷:数据构造较复杂，存储数据需要更多链接指针；在检索数据时，需要考虑数据存储途径；在插入或删除数据时，波及到调整链接指针。关系关系模型与层次模型和网状模型相比有着本质差异，它是用二维表格来体现实体及其互相之间联络。一种关系就是没有反复行和反复列二维表，二维表每一行在关系中称为元组，每一列在关系中称为属性。学生关系每一行代表一种学生记录，每一列代表学生记录一种字段。属性个数（n）称为关系元。关系、关系模式、关系数据库模式、关系数据库定义（关系、元组、属性、域、关键字、数据项）关系：n 关系描述称为关系模式，可以体现为R(U,D,DOM,F) R为关系名，U为属性名集合，D为域集合，DOM为属性向域映像集合，F为属性间依赖关系集合n 关系模式是型，关系是值n 例：学生选修课成绩登记表，定义关系模式SC如下：SC（sno,cno,grade,N(6),N(3),(sno,N(6),(cno,N(3),(grade,N(3),(sno,cno)grade）关系模式：n 关系描述称为关系模式，可以体现为R(U,D,DOM,F) R为关系名，U为属性名集合，D为域集合，DOM为属性向域映像集合，F为属性间依赖关系集合n 关系模式是型，关系是值n 例：学生选修课成绩登记表，定义关系模式SC如下：SC（sno,cno,grade,N(6),N(3),(sno,N(6),(cno,N(3),(grade,N(3),(sno,cno)grade）关系数据库：n 关系数据库基本概念 关系数据库就是某些有关二维表和其她数据库对象集合。关系数据库中所有信息都存储在二维表格中；一种关系数据库也许包括多种表；除了这种二维表外，关系数据库还包括某些其她对象，如视图等。1关系一种关系就是一张二维表，一般将一种没有反复行、反复列二维表当作一种关系，每个关系均有一种关系名。2元组二维表每一行在关系中称为元组(Tuple)。一行描述了现实世界中一种实体，或者描述了不一样实体间一种联络。3属性二维表每一列在关系中称为属性(Attribute)，每个属性均有一种属性名，各个属性取值称为属性值。每个属性有一定取值范围，称为值域。4关键字关系中能惟一区别、确定不一样元组属性或属性组合，称为该关系一种关键字。关键字又称为键或码(Key)。 码候选码能唯一标示一种元组属性组主码多种候选码中重要应用属性组，其中每个属性都称为主属性，不属于任何候选码属性称为非码属性合成码码具有多种属性外码不是目前关系码，不过其她关系中主码全码所有属性共同构成关系模式候选码5域（集合）域是一组具有相似数据类型值集合。 6.主属性和非主属性 定义5 设Ai是关系模式R一种属性，若Ai属于R某个候选关键属性，称Ai是R主属性，否则，称Ai为非主属性。3） 关系运算：选用、投影、集合并运算、集合差运算、笛卡儿积、连接 运算符含义运算符含义集合运算符并差交逻辑运算符非与或专门关系运算符%广义笛卡尔积选用投影连接除比较运算符=不不不小于等于不不不小于不不小于等于不不小于等于不等于1.选用（selection）:对关系而言，选用是从行角度取关系子集 公式体现:RF或F(R)=t|tR F(t)=True 公式含义：R中使布尔函数为真元组集，F为布尔函数，即限定条件 F基本形式为：x1y1x2y2,其中为比较运算符，为逻辑运算符，x1,y1是属性名或常量，属性名也可用序号体现例： 5=IS(student) 或 student5=ISSage19(student) 或 studentSage192.投影（projection）:对关系而言，投影是从列角度取关系子集 公式体现:RA或A(R)=tA|tR 公式含义：包括A中各属性组元组集 投影之后不仅取消了某些属性列，并且还也许取消某些元组例：Sname,Sdept(student)或 studentSname,Sdept2,5(student)或 student2,5 3.集合并（union） R S=t|t R t S R、S为同类关系（关系度相似，且对应属性都来自相似域），并成果与R、S也是同类关系n R和S 具有相似目n 对应属性取自同一种域n R - S 仍为n目关系，由属于R而不属于S所有元组构成 R -S = t|tRtS 4.集合差（difference） R S=t|t R t S= t|t R t S R、S为同类关系，差成果与R、S也是同类关系n R和S 具有相似目n 对应属性取自同一种域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，其中每一种元素(d1，d2，dn)称作一种n元组（n-tuple）或简称元组，它每个元素di取自对应集合Di。 元组中每一种值di称作一种分量（component） 若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 公式含义：从两个关系笛卡尔积中选用属性间满足一定条件元组 4） 关系数据库基本概念：函数依赖基本概念定义1 对于R中属性X任何一种详细值，Y仅有唯一详细值与之对应，则称R属性Y函数依赖于属性X。记为：XY，X称为决定原因。完全函数依赖、某些函数依赖定义2 在R中，假如属性集Y函数依赖于属性集X，且不函数依赖于X任意真子集，则称Y完全函数依赖于X，记做： X Y， 否则，称Y某些函数依赖于X，记做：X Y 。例：关系SC(Sno,Cno,Grade)中，由于Sno Grade，Cno Grade，因此有(Sno,Cno) Grade传递函数依赖定义3 设X，Y，Z是关系模式R不一样属性集，若X Y (并且YX) ，Y Z，称X传递决定Z，或称Z传递函数依赖于X，记做X Z。例：如关系Std(Sno,Sdept,Mname)中，有 Sno Sdept，Sdept Mname，且Sdept Sno，因此Sno Mname 5） 规范化理论：第一范式、第二范式、第三范式定义第一范式：n 对关系模式规范化规定提成从低到高不一样层次，分别称为第1范式、第2范式、第3范式、Boyce-Codd范式、第4范式和第5范式。n 定义6 当关系模式R所有属性都不能分解为更基本数据单位时，称R是满足第1范式，则R 1NF。n 第1范式规定一行中每一列仅有唯一值并且具有原子性。例如，假如有关员工关系中有一种工资属性，而工资又由更基本两个数据项基本工资和岗位工资构成，则这个员工关系模式就不满足1NF。第二范式：n 定义7 假如关系模式R满足第1范式，并且R所有非主属性都完全函数依赖于R码，称R满足第2范式，简记为R 2NF。n 例如在学生表(学号,姓名,系名,系负责人,课程名,成绩)中存在非主属性对码某些函数依赖 姓名,系名,系负责人完全函数依赖于学号 姓名,系名,系负责人某些函数依赖于学号，课程名n 消除表中非主属性对码某些函数依赖n 采用投影分解措施得到两个新关系 学生状况(学号,姓名,系名,系负责人) 成绩(学号，课程名，成绩)第三范式：n 定义8 假如R 2NF，且它任何一种非主属性都不传递依赖于R任意一种候选关键字，称R满足第3范式，简记为R 3NF 。n 第三范式规定非主键列互不依赖，消除传递依赖。假如非主属性之间存在了函数依赖，就会存在传递依赖，这样就不满足第三范式。定理 若关系模式R符合3NF条件，则R一定符合2NF条件。n 消除表中非主属性对码传递函数依赖 将函数关系中起传递作用非主属性（决定方）和由它完全决定非主属性取出单独构成一种关系模式 将决定方和余下非主属性加上主码构成此外一种关系模式