浙江省高等学校数据库技术三级考试辅导材料题库.doc

浙江省数据库技术三级考试大纲基本要求1.掌握数据结构的基础知识；2.掌握数据库的基本概念；3.熟练掌握E-R模型、关系模型、关系代数运算及关系模式的规范化；4.掌握结构化查询语言SQL常用语句；5.了解数据库管理系统SQL SERVER的常用操作；6.能进行简单的数据库应用系统设计。考试范围 一、数据结构基础（20%）1数据结构的基本概念及有关术语：数据、数据元素、数据类型、数据的逻辑结构、数据的存储结构、算法和算法分析、算法的时间及空间复杂性；2线性表：线性表的概念、逻辑结构、存储结构（顺序存储、链式存储），插入、删除操作；3数组：数组的定义、数组逻辑结构与存储结构的关系；4栈：栈的概念、逻辑结构、存储结构，进栈、出栈操作；5队列：队列的定义、逻辑结构、存储结构，循环队列，进队、出队操作；6二叉树：二叉树的定义及相关术语、性质、存储结构，二叉树的遍历，哈夫曼树；7查找：查找表的有关概念、顺序查找、二分查找；8排序：排序的基本概念、选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序。二、数据库系统（80%） 1 数据库的基本概念：信息、数据和数据处理、数据库系统的组成与结构；2 数据库管理系统的三级模式结构的概念、原理和对数据独立性的意义，数据独立性的含义；3 数据库系统的数据模型：层次、网状、关系和面向对象的模型的含义、特点和主要区别；4 关系模型、关系、关系模式、关系数据库模式、关系数据库的定义（关系、元组、属性、域、关键字、数据项）；主属性和非主属性；5 关系运算：关系代数运算（并、交、差、笛卡儿积、选择、投影、连接、除）、关系的完整性约束；6 关系数据库基本概念：函数依赖的定义和相应的概念；完全函数依赖、部分函数依赖和传递函数依赖定义；7 规范化理论：第一范式、第二范式、第三范式和BCNF范式的定义、关系模式规范化的方法和关系模式分解的方法及分解准则；8 关系数据库规范化：1NF，2NF，3NF，BCNF；9 结构化查询语言SQL：数据库操作（数据类型、库的创建与撤消、表的创建、修改与撤消、视图的创建与撤消、索引的创建与撤消），数据库查询（单表查询、多表连接查询、分组查询、按序查询、统计查询），数据更新（表和视图中数据的插入、删除和修改）；10典型数据库管理系统SQL SERVER：创建数据库、创建表、表的插入、删除和修改、数据库查询、建立表索引；11数据库应用系统设计技术：数据模型的基本概念、E-R图向关系模型的转换、数据模型优化、设计视图、逻辑设计，物理设计。浙江省数据库技术三级考试辅导材料第一讲：内容概要：数据结构的基本概念及有关术语1、 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其关系和操作的学科。数据的逻辑结构-数据关系之间的逻辑关系； 数据的存储结构-数据的逻辑结构在计算机中的表示；操作算法-插入、删除、修改、查询、排序等；数据的逻辑结构： 集合 线性结构 -表、栈、队列 非线性结构 -树、图 数据的存储结构： 顺序存储结构 -数组 链式存储结构 -指针 2、数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称；数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理；数据类型是对数据的取值范围、每一数据的结构以及允许施加操作的一种描述。 3、算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法有五个特性：（1）有穷性- 一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成；（2）确定性- 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。（3）可行性- 一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入- 一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。（5）输出- 一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。 评价算法好坏的标准：（1）正确性：算法应当满足具体问题的需求。（2）可读性：可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误难以调试和修改。 （3）健壮性：当输入数据非法时，算法也能适当地作出反应或进行处理，不会产生莫名其妙的输出结果。（4）时间复杂性：效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。时间复杂度：一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n） 分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。 （5）空间复杂性：存储量需求指算法执行过程中所需要的最大存储空间。空间复杂性(Space Complexity)作为算法所需存储空间的量度，记作S(n)=O(f(n) 其中n为问题的规模（或大小）。一个程序上机执行所需空间包括：程序指令存储的空间；数据存储的空间；变量分配的空间。第二讲内容概要：基本数据结构及其操作：线性表的定义、逻辑结构、存储结构（顺序存储、链式存储），插入删除操作2.1 线性表的定义线性表n个数据元素的有限序列，记为(a1,a2,ai-1,ai,ai+1,，an)。例如：26英文字母表(A,B,C,X,Y,Z)、一个班级的学生成绩报表等表长线性表中元素的个数直接前驱元素线性表中ai-1领先于ai，则ai-1是ai的直接前驱元素直接后继元素线性表中ai领先于ai+1，则ai+1是ai的直接后继元素2.2 线性表的存储结构1、两种存储结构：顺序 存储数组链式存储链表2、线性表的顺序存储结构存储地址内存状态数据元素在线性表中的位序b1b+l2b+(i-1)lib+(n-1)lnb+nl空闲b+(maxlen-1)l注：设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。所以，线性表的第i个数据元素ai的存储位置为loc(ai)=loc(a1)+(i-1)*l。上述图中第一个元素存储位置设为b。3、线性表的链式存储结构L=(a1,a2,an)注：(a)为非空表，(b)为空表。2.3 基于链式存储的线性表操作算法* 带头结点的单链表（如右：a图为非空表，b图为空表）2.4 循环链表循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，如下图所示为单链的循环链表。注：(a)为非空表，(b)为空表。l 循环链表的操作与单链表的差别：循环链表的操作与单链表基本一致，差别仅在于算法中的循环条件不是p或p-next是否为空，而是它们是否等于头指针。2.5顺序存储线性表与链式存储线性表的比较*顺序表的优点：存取数据速度快占用的存储空间小*顺序表的缺点：需占用连续存储空间插入操作需移动元素*链表的优点：不需占用连续存储空间插入操作不需移动元素*链表的缺点：存储数据麻烦、速度慢占用的存储空间大第三讲：内容概要：数组的定义、数组逻辑结构与存储结构的关系。3.1 数组的定义数组是程序设计中的常用数据类型。它分为一维数组、二维数组和多维数组。数组一旦被定义，它的维数就不再改变。因此，数组只有存取元素和修改元素值的操作，它一般不作插入和删除操作。一维数组是一个线性表。二维数组也可以看作是一个线性表，它的每个数据元素是一个定长的线性表。3.2 数组的存取结构数组一般采用顺序存取结构(1)对于一维数组：用一组连续存储单元存放数组中的数据元素。(2)对于二维数组，有下面两种存储方式：以行序为主序的存储方式，如图(1)所示；以列序为主序的存储方式，如图(2)所示； 浙江省计算机三级数据库知识点数据结构1.基本概念数据 是信息的载体，是计算机程序加工的“原料”。数据不仅包括整数、实数、字符串，还包括图像和声音等。数据元素 是数据的基本单位，数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项（也可以成为字段、域、属性）组成。数据项 是具有独立含义的最小标识单位。数据结构 指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括数据的逻辑结构、数据的存储结构和数据的运算，这三方面是一个整体，孤立地去理解一个方面，而不注意它们之间的的联系是不可取的。数据的存储结构可以用顺序、链接、索引和散列存储方法得到。数据类型 是指一个值的集合以及在这些值上定义的一组操作的总称。按“值”是否可分解，可将数据类型划分为两类：原子类型和结构类型。时间代价 就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的时间，也以某种单位由f(1)增至f(n)，则称该算法的时间代价为f(n)。空间代价 就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的空间，也以某种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。2.线性表线性表 是由n(n=0)个数据元素（结点）a1,a2,an组成的有限序列。带头结点的单循环链表 中，判断空链表的条件是head=head-next.仅设尾指针的单循环链表 中，判断空链表的条件为rear=rear-next.双向链表 既可以用来表示线性结构，也可以用来表示非线性结构，其每个结点包括三个域：一个数据域和两个指针域，一个指向它的前趋，另一个指向它的后继。在双向链表中，若d是指向表中任一结点的指针，则有llink(rlink(d)=rlink(llink(d)=d.队列 在两个方向都有限制，插入只能在表的一端进行（只入不出），而删除只能在表的另一端进行（只出不进），允许插入的一端称队尾（rear），允许删除的一端称队头（front），队列的操作原则是先进先出。栈 是一种插入、删除只能在表的一端进行的线性表。在栈中，允许插入和删除的一端叫栈顶，不允许插入和删除的一端叫栈底。满足后进先出的原则。串（字符串） 是一种特殊的线性表，它的字符序列由零个或多个字符组成。a=称为空串，长度为0.求子串序列号：用index(a,sb)表示子串sb在串a中的序号。3.多维数组、稀疏矩阵和广义表数组 是由类型相同的数据元素构成的有序集合。行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。计算二维数组的地址：Loc(i,j)=Loc(0,0)+(行标*i+j)*L稀疏矩阵 可用一个三元组（i,j,value）表示，将这些三元组按某种次序排成一个线性表。4.树形结构树 是一类非线性结构。树的表现形式还有嵌套集合的形式、广义表的形式和凹入表示法的形式。树的结点 包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度。度为0的结点称为叶子或终端结点，度不为0的结点称为非终端结点或分支结点。树内各结点的度的最大值称为树的度。结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。树中结点的最大层次称为树的深度，从一结点到叶结点的最长路径称为该结点的高度。森林 是m棵互不相交的树的集合。（对树中每个结点而言，其子树的集合即为森林）二叉树 又是另一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且其子树有左右之分，次序不能随意颠倒。二叉树的性质： a.在二叉树的第i层至多有2(i-1)个结点(i=1).b.深度为k的二叉树至多有2k-1个结点(k=1).c.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2,则n0=n2+1.d.具有n个结点的完全二叉树的深度为【log2n】+1e.f.。满二叉树： 一棵深度为k且有2k-1个结点的二叉树。完全二叉树： 深度为k,有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树