免费智能真题库 > 历年试卷 > 程序员 > 2016年下半年 程序员 下午试卷 案例
  第4题      
  知识点：   队列   广度优先遍历   矩阵   数据模型   数组

 
【说明】
图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点v出发进行广度优先遍历的过程是：
①访问顶点v；
②访问V的所有未被访问的邻接顶点w1,w2,...,wk；
③依次从这些邻接顶点w1,w2,...,wk出发，访问其所有未被访问的邻接顶点；依此类推，直到图中所有访问过的顶点的邻接顶点都得到访问。
显然，上述过程可以访问到从顶点V出发且有路径可达的所有顶点。对于从v出发不可达的顶点u，可从顶点u出发再次重复以上过程,直到图中所有顶点都被访问到。
例如，对于图4-1所示的有向图G，从a出发进行广度优先遍历，访问顶点的一种顺序为a、b、c、e、f、d。

设图G采用数组表示法（即用邻接矩阵arcs存储），元素arcs[i][j]定义如下：

图4-1的邻接矩阵如图4-2所示，顶点a~f对应的编号依次为0~5。因此，访问顶点a的邻接顶点的顺序为b，c，e。
函数BFSTraverse(Graph G)利用队列实现图G的广度优先遍历。
相关的符号和类型定义如下：

代码中用到的队列运算的函数原型如表4-1所述，队列类型名为QUEUE。

【代码】
 
问题：4.1   阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
 
 
 

   知识点讲解    
   · 队列    · 广度优先遍历    · 矩阵    · 数据模型    · 数组
 
       队列
               队列的定义
               队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头（front）。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。
               由队列的定义可知，队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（First In First Out, FIFO）的原则组织数据的，因此，队列也被称为"先进先出"表。
               下图是一个队列的进出示意图，通常用指针front指示队头的位置，用指针rear指向队尾的位置。
               
               队列的进出示意图
               队列的基本操作
               队列的基本操作主要有以下6种。
               .InitQueue（&Q）：初始化操作，构造一个队列Q。
               .QueueEmpty（Q）：若栈Q为空队列，返回1，否则返回0。
               .EQueue（&Q, e）：插入元素e到队列Q的尾部。
               .OQueue（&Q,&e）：删除Q的队首元素，并用e返回其值。
               .GetQhead（Q,&e）：用e返回Q的队首元素。
               .ClearQueue（&Q）：将Q清空为空队。
               队列的顺序存储结构
               顺序存储结构采用一维数组（向量）实现，设队列头指针front和队列尾指针rear，并且假设front指向队头元素的前一位置，rear指向队尾元素。若不考虑队满，则入队操作语句为Q[rear++]=x；若不考虑队空，则出队操作语句为x=Q[++front]。当然，出队时，并不一定需要队头元素（与退栈类似）。
               按上述的做法，有可能出现假溢出，即队尾已到达一维数组的高端，不能再入队，但因为连续出队，队列中元素个数并未达到最大值。解决这种问题，可用循环队列。在循环队列中，需要区分队空和队满：仍用front=rear表示队列空，在牺牲一个单元的前提下，用front==（rear+1）% MAX表示队列满。在这种约定下，入队操作的语句为：rear=（rear+1）%MAX, MAX, Q[rear]=x；出队操作语句为：front=（front+1）% MAX。
               顺序队列的类型定义如下：
               
               顺序队列定义为一个结构类型，该类型变量有3个数据域：data、front、rear。其中data为存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量，取值范围是0~QueueSize-1。约定队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示队头元素在一维数组中的当前位置的前一个位置，这种顺序队列说明如下。
               .初始化时，设置SQ.front=SQ.rear=0。
               .队头指针的引用为SQ.front，队尾指针的引用为SQ.rear。
               .队空的条件为SQ.front==SQ.rear；队满的条件为SQ.front=（SQ.rear+1）% QueueSize。
               .入队操作：在队列未满时，队尾指针先加1（要取模），再送值到队尾指针指向的空闲元素。出队操作：在队列非空时，队头指针先加1（要取模），再从队头指针指向的队头元素处取值。
               .队列长度为（SQ.rear+QueueSize-SQ.front）% QueueSize。
               特别应注意的是：在循环队列的操作中队头指针、队尾指针加1时，都要取模，以保持其值不出界。
               在循环队列上队列的实现基本操作的函数如下。
               1）初始化initqueue（SQueue *SQ）
               
               2）判空QueueEmpty（SQueue SQ）
               
               3）入队EQueue（SQueue *SQ, ElemType e）
               
               4）出队OQueue（SQueue *SQ, ElemType *e）
               
               5）取队首元素GetQhead（SQueue *SQ, ElemType *e）
               
               6）清队列ClearQueue（SQueue *SQ）
               
               队列的链式存储结构
               队列的链接实现称为链队，链队实际上是一个同时带有头指针和尾指针的单链表。头指针指向队头节点，尾指针指向队尾节点即单链表的最后一个节点。为了简便，链队设计成一个带头节点的单链表。
               链队的类型定义如下：
               
               链队列的说明如下。
               .队列以链表形式出现，链首节点为队头，链尾节点为队尾。
               .队头指针为LQ→front，队尾指针为LQ→rear，队头元素的引用为Q→front→data，队尾元素的引用为LQ→rear→data。
               .初始化时，设置LQ→front=LQ→rear=NULL。
               .进队操作与链表中链尾插入操作一样；出队操作与链表中链首删除操作一样。
               .队空的条件为LQ→front==NULL。理论上，只要系统内存足够大，链队是不会满的。
               在链队上实现队列基本操作的函数如下。
               1）队列初始化InitQueue（LQueue *LQ）
               
               2）入队EQueue（LQueue *LQ, ElemType e）
               
               3）出队OQueue（LQueue *LQ, ElemType *e）
               
               4）判空QueueEmpty（LQueue *LQ）
               
               5）取队首元素GetQhead（LQueue *LQ, ElemType *e）
               
               6）清队列ClearQueue（LQueue *LQ）
               
               循环队列中的边界条件判别准则
               判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一个布尔变量来区别队列的空和满；二是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满；三是设置一个计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。
               双端队列的作用
               双端队列是限定插入和删除操作在线性表的两端进行，可将其看成是栈底连在一起的两个栈，但其与两个栈共享存储空间是不同的。共享存储空间中的两个栈的栈顶指针是向两端扩展的，因而每个栈只需一个指针；而双端队列允许两端进行插入和删除元素，因而每个端点必须设立两个指针，如下图所示。
               
               双端队列的示意图
               在实际应用中，可对双端队列的输出进行限制（即一个端点允许插入和删除，另一个端点只允许插入），也可对双端队列的输入进行限制（即一个端点允许插入和删除，另一个端点只允许删除）。可见，采用双端队列可增加应用中的灵活性。
 
       广度优先遍历
        图的广度优先遍历的基本思想是：给定图G=（V，E），从图中某个源点v出发，在访问了顶点v之后，接着就尽可能先在横向搜索v的所有邻接点。在依次访问v的各个未被访问过的邻接点w1，w2，…，wk之后，分别从这些邻接点出发依次访问与w1，w2, …，wk邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问过为止，此时从v开始的搜索过程结束。若G是连通图，则遍历完成；否则，在图G中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至图G中所有顶点均已被访问为止。采用广度优先搜索法遍历图的方法称为图的广度优先遍历。
        为确保先访问的顶点其邻接点亦先被访问，在搜索过程中可使用队列来保存已访问过的顶点。当访问v和u时，这两个顶点相继入队，此后，当v和u相继出队时，分别从v和u出发搜索其邻接点v1，v2，…，vs和u1，u2, …，ut，对其中未访者进行访问并将其入队。这种方法是将每个已访问的顶点入队，保证了每个顶点至多只有一次入队。
 
       矩阵
        矩阵是很多科学与工程计算问题中研究的数学对象。在数据结构中主要讨论如何在尽可能节省存储空间的情况下，使矩阵的各种运算能高效地进行。
        在一些矩阵中，存在很多值相同的元素或者是零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。压缩存储的含义是为多个值相同的元素只分配一个存储单元，对零元不分配存储单元。
               特殊矩阵
               常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。对于特殊矩阵，由于其非零元的分布都有一定的规律，所以可将其压缩存储在一维数组中，并建立起每个非零元在矩阵中的位置与其在一维数组中的位置之间的对应关系。
               若矩阵An×n中的元素有aij=aji（1≤i，j≤n）的特点，则称之为对称矩阵。
               若为对称矩阵中的每一对元素分配一个存储单元，那么就可将n2个元素压缩存储到能存放n（n+1）/2个元素的存储空间中。不失一般性，以行为主序存储下三角（包括对角线）中的元素。假设以一维数组B［n（n+1）/2］作为n阶对称矩阵A中元素的存储空间，则B［k］（0≤k<n（n+1）/2）与矩阵元素aij（aji）之间存在着一一对应的关系。
               
               对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为零。一个n阶的三对角矩阵如下图所示。
               
               三对角矩阵示意图
               若以行为主序将n阶三对角矩阵An×n的非零元素存储在一维数组B［k］（0≤k<3n-2）中，则元素位置之间的对应关系为：
               k=3×（i-1）-1+j-i+1=2i+j-3（1≤i，j≤n）
               其他特殊矩阵可作类似的推导和计算，这里不再一一说明。
               稀疏矩阵
               在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。
               对于稀疏矩阵，存储非零元素时必须同时存储其位置（即行号和列号），所以三元组（i，j，aij）可唯一确定矩阵中的一个元素。由此，一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。
               一个6行7列的稀疏矩阵如下图所示，其三元组表为（1，2，12），（1，3，9），（3，1，-3），（3，6，14），（4，3，24），（5，2，18），（6，1，15），（6，4，-7））。
               
               稀疏矩阵示意图
               稀疏矩阵的三元组表构成一个线性表，其顺序存储结构称为三元组顺序表，其链式存储结构称为十字链表。
 
       数据模型
        1）信息结构与E-R方法
        （1）数据的3种范畴。数据需要进行认识、理解、整理、规范和加工，然后才能存放到数据库中。也就是说，数据从现实生活进入到数据库实际经历了若干个阶段。一般划分为3个阶段，也就是数据的3种范畴，即现实世界、信息世界、机器世界。
        ①现实世界。存在于人们头脑之外的客观世界，也就是客观存在并可以相区分的客观事物或抽象事物，称为实体。
        ②信息世界。客观事物必然在人们的头脑中产生反映，把这种反映称为信息。
        ③机器世界。对信息世界的信息进行数据化，数据化后的信息称之为数据。
        （2）E-R方法。我们需要对现实世界的信息结构进行描述，最常用的方法是实体－联系方法，即通常所说的E-R（Entity-Relationship）方法。E-R方法使用的工具称为E-R图，它所描述的现实世界的信息结构称为企业模式（Enterprise Schema），也把这种描述结果称为E-R模型。
        E-R图的3个要素是实体、属性以及实体和属性之间的联系。
        ①实体。在E-R图中用矩形框表示实体，把实体名写在方框内。
        ②属性。实体的属性用椭圆框表示，框内写上属性名，并用连线与相应的实体相连。这种画法有点麻烦，后来也有直接将属性名写在实体旁边，并对实体的标识属性标注下划线。
        ③联系。联系本身也有属性，联系是通过相关联的实体的有关属性体现出来的。实体之间的联系用菱形框表示，框内写上联系名，并用连线与有关的实体相连。实体之间联系的基本类型有一对一（1∶1）、一对多（1∶n）和多对多（m∶n）3种。
        实体之间的联系类型并不取决于实体本身，而是取决于现实世界的管理方法，或者说取决于语义，即同样两个实体，如果有不同的语义，则可以得到不同的联系类型。比如有仓库和器件两个实体，下面来讨论它们之间的联系。
        ①如果规定一个仓库只能存放一种器件，并且一种器件只能存放在一个仓库，这时仓库和器件之间的联系是一对一的。
        ②如果规定一个仓库可以存放多种器件，但是一种器件只能存放在一个仓库，这时仓库和器件之间的联系是一对多的。
        ③如果规定一个仓库可以存放多种器件，同时一种器件可以存放在多个仓库，这时仓库和器件之间的联系是多对多的。
        2）数据库系统的体系结构
        数据库系统的应用结构经历了集中式结构、文件服务器的网络结构到现在客户机／服务器网络结构以及分布式网络结构。
        （1）集中式数据库系统。集中式数据库系统，就是将数据以及数据的管理都集中在一台计算机上。这类数据库效率高，可靠性好，数据冗余少，数据独立性高。
        （2）客户机／服务器（C/S）数据库系统。在客户机／服务器数据库系统中，数据库服务器的平台与客户端无关，其数据库管理系统集中负责管理数据库服务器上的数据和资源，它向客户提供一个开放的使用环境，客户端的用户通过数据库接口访问数据库。客户端称为前台，服务器称为后台。前台的工作包括管理用户接口或界面、采集数据、向后台发出请求等；而后台负责管理外设、存取共享数据、响应前台请求并送回结果。客户端的应用程序和数据一般是用户自己专用的，而服务器的功能和数据是所有用户共享的。
        （3）分布式数据库系统。分布式数据库系统就是数据物理的分布存储在不同的计算机上，这些物理上分布存储的数据在逻辑上构成一个整体的数据库。也就是一个物理上分布于计算机网络的不同地点，而逻辑上又属于同一系统的数据集合。网络上每个地点的数据库都有自治能力，能够完成局部应用；同时每个地点的数据库又属于整个系统，通过网络也可以完成全局应用。
        3）传统的三大模型
        数据库中不仅要存放数据本身，还要存放数据与数据之间的联系，可以用不同的方法表示数据与数据之间的联系，把表示数据与数据之间联系的方法称为数据模型。传统的数据模型有层次数据模型、网络数据模型和关系数据模型。
        （1）层次数据模型。用树形结构来表示实体之间的联系的模型称为层次模型。支持层次模型的典型系统诞生于1970年前后，就是IBM公司的IMS（Information Management System）。构成层次模型的树是由节点和连线组成的，节点表示实体集（文件或记录型），连线表示相连两个实体之间的联系，这种联系只能是一对多的。通常把表示"一"的实体放在上方，称为父节点；而把表示"多"的实体放在下方，称为子节点。层次模型表示一对多的联系是直接而方便的。但由于层次模型有以下两点限制：
        ①有且仅有一个节点无父节点，这个节点即为树的根。
        ②其他节点有且仅有一个父节点。
        这样就使得多对多联系不能直接用层次模型表示，但是如果把多对多联系转换成一对多联系，又会出现一个子记录型有多个父记录型的结果，这同样不符合层次数据库的要求。解决的办法只有把它分解成两个层次型。层次数据模型或层次数据库是由若干层次型构成的，或者说它是一个层次型的集合。
        （2）网络数据模型。如果取消层次模型中的两点限制，即允许每一个节点可以有多个父节点，便形成了网络。用网络结构来表示实体之间联系的数据模型称为网络数据模型。网络模型和层次模型在本质上是一样的，从逻辑上看它们都是用连线表示实体之间的联系，用节点表示实体集；从物理上看，层次模型和网络模型都是用指针来实现两个文件之间的联系，其差别仅在于网络模型中的连线或指针更加复杂，更加纵横交错，从而使数据结构更复杂。在网络模型中同样使用父节点和子节点这样的术语，并且同样把父节点安排在子节点的上方。网络数据模型的典型代表是CODASYL系统。
        （3）关系数据模型。关系数据模型源于数学，它把数据看成二维表中的元素，而这个二维表就是关系。用关系（表格数据）表示实体和实体之间联系的模型称为关系数据模型。通俗地讲，关系就是一个二维表格，表格中的每一行称为一个元组，它相当于一个记录值，每一列是一个属性值集，列可以命名，称为属性名。这里的属性与前面讲到的实体属性（特征）或记录的字段意义相当。由此可见，关系是元组的集合，如果表格有n列，则称该关系是n元关系。关系应满足以下性质。
        ①表格中的每一列都是不可再分的基本属性。
        ②各列被指定一个相异的名字。
        ③各行相异，不允许重复。
        ④与行、列次序均无关。
        综合以上4点，可以说：一个关系是一个文件，该文件中的每个记录是唯一的，所有记录具有相同个数和类型的字段，也就是说，所有记录有同样的固定长度和格式。在关系数据模型中实体本身以及实体与实体之间的联系都用关系来表示，实体之间的联系不再通过指针来实现。
        对于用户，关系方法应该是很简单的，但是关系数据库管理系统本身是很复杂的。关系方法之所以对用户简单，是因为它把大量的困难转给了数据库管理系统。关系数据库管理系统一经投入使用，便逐步取代了层次数据库和网状数据库。现在耳闻目睹的数据库管理系统，全部都是关系数据库管理系统，像Sybase、Oracle、Informix、MS SQL Server、FoxPro、Access等。
        4）数据独立性和三层模式结构
        数据独立性是指应用程序与存储数据相互独立的特性。也就是当修改数据的组织方法和存储结构时，应用程序不用修改的特性。数据独立性又分为存储数据独立性和概念数据独立性。
        （1）存储数据独立性。以前所熟悉的计算机文件，都是真正在磁盘上存在的物理文件或存储文件，应用程序也是针对这样的文件而写的。在存储文件中，不仅存储了管理现实世界所需要的各种数据，还存储了大量为了管理文件本身所需要的辅助数据，如索引和指针等。为了使应用程序与这些索引和指针等分离开来，使之只关心管理现实世界所需要的各种数据本身，把程序分成两部分，一部分是应用程序或用户程序（User-Program），另一部分是存储子程序（Storage-Routine）。用户程序操作一个物理上并不存在的概念文件或逻辑文件，而实际操作则是交由存储子程序去操作存储文件来完成的。这时如果修改存储文件的组织方法或存储结构，将与用户程序无关，而存储子程序则可以做成通用的和商品化的程序。实际上，这里的存储子程序就是后来的数据库管理系统的数据存储子系统。概念文件只是"概念上"的，它实际上并不存在，可以把它看作存储文件的抽象。也可以假设概念文件只包含用户有用的数据，像指针那些辅助字段被屏蔽掉了。或者说，概念文件是用户存取存储文件的结构或框架。
        通过概念文件只需要关心文件中有哪些数据，至于数据是怎么存储的、还有哪些指针和索引都不用关心。显然这种两级方案给用户程序带来了存储数据独立性，即不管存储文件的存储方法和存储结构怎么改变，用户程序都能继续正确执行。
        存储数据独立性的最大好处是可以大大节省程序的维护代价。一般在一个大的系统中，会有很多用户程序操作存储文件，如果所有这些程序都通过存储子程序和概念文件完成它们的操作，那么当要改变存储文件的存储方法时，所有这些程序都不会受到影响。
        （2）概念数据独立性。每个用户程序并不一定使用概念文件中的全部数据字段，不同的用户程序只是从概念文件中抽取部分字段为自己所用。把从概念文件抽取的部分字段称为外部文件，这也为获得概念数据独立性奠定了基础。
        概念数据独立性也称为逻辑数据独立性，它是指当用户程序操作的概念文件有插入或删除字段的情况发生时（当然是通过存储文件），用户程序仍能正确执行的性质。当然，插入或删除的字段与这个用户程序是无关的，也就是说，它们不是这个用户程序使用的字段。
        （3）数据库的三层模式结构。不管是概念文件还是外部文件，它们都不真正含有数据，只是存取存储文件的结构或框架；概念文件是存储文件的抽象，而外部文件是概念文件的部分抽取。使用这种三层结构不仅可以使数据具有独立性，使数据和程序的代价大大降低，而且还可以使数据达到共享，使同一数据满足更多用户的不同需求。
        5）关系数据库
        （1）关系模型的基本概念。设D1,D2,…,Dn为任意集合，定义D1,D2, …,Dn的笛卡儿积为
        D1×D2×…×Dn={(d1,d2, …,dn)|di∈Di，i=1, 2, …，n}
        笛卡儿积D1×D2×…×Dn的任意一个子集称为D1,D2，…，Dn上的一个n元关系。
        可以把二元关系看成二维表，给表的每一列取个名字，称为属性，n元关系就有n个属性，属性的名字要唯一，其取值范围Di（i=1, 2, …,n）称为值域。
        如果一个属性集的值能唯一标识一个关系的元组而又不含有多余的属性，则称该属性集为候选关键字。有时一个关系中有多个候选关键字，这时可以选择其中一个作为主关键字，简称关键字。每一个关系都有一个并且只有一个主关键字。
        如果一个属性集不是所在关系的关键字，但是是其他关系的关键字，则该属性集称为外部关键字。
        关系模式就是二维表的表框架或结构，它相当于文件结构或记录结构。
        关系模型是所有的关系模式、属性名和关键字的汇集，是模式描述的对象。
        对应于一个关系模型的所有关系的集合称为关系数据库。
        关系模型下的术语列举如下。
        ①属性：数据项（字段）。
        ②元组：记录（值）。
        ③关系：文件（值）。
        ④关系模式：记录类型（文件格式）。
        ⑤关系名：文件名（记录名）。
        ⑥数据库模式：概念模式。
        最后概括一下关系的性质。
        ①列是同质的，即每一列中的分量是同类型的数据，来自同一个值域。
        ②不同的列可以出自同一个值域，每一列称为属性，要给予不同的属性名。
        ③列的顺序是无关紧要的，即列的次序可以任意交换。
        ④元组不可以重复，即任意两个元组不能完全相同。
        ⑤行的顺序是无关紧要的，即行的次序可以任意交换。
        ⑥每一分量必须是不可分的最小数据项。
        ⑦每个关系都有一个主关键字唯一标识它的各个元组。
        （2）关系模式。关系数据库同样具有3层模式，即概念模式、存储模式和外部模式。关系概念模式主要包括对出现在数据库中的每个关系的说明，包括对关系名、属性名和属性的取值范围（类型）的说明。在关系数据模型中可以不说明关系与关系之间的联系（关系与关系之间的联系是通过连接字段实现的）。比如有以下的关系：
        花名册（学号，姓名，年龄）
        成绩单（学号，姓名，成绩）
        关系存储模式从原理上讲与其他类型数据库系统的存储模式没有什么不同，每个概念文件都对应一个存储文件。一般基于主关键字进行直接存取需要建立一个主索引（唯一索引），通过辅助关键字进行存取需要建立一个辅助索引（一般索引）。在关系存储模式中不用说明存储文件，存储文件的说明由关系数据库管理系统根据基本表（概念文件）的定义自动映射产生。所以，在关系存储模式中要说明的主要内容就是索引。
        关系外部模式的定义和其他类型数据库系统的外部模式一样，在关系数据库中外部文件被称为视图（View）。
        （3）关系代数。关系代数是对关系运算的总和。关系运算分为以下两类。
        ①传统的集合运算，这种运算将关系看作元组的集合。
        ②专门的关系运算。
        传统的集合运算是二目运算，设关系R和S均是n元关系，且相应的属性值取自同一个值域，则可以定义并运算（∪）、交运算（∩）、差运算（-）以及前面讲的笛卡儿乘积。
        ①R和S的并是集合，记为R∪S, R∪S={x|x∈R∨x∈S}。
        ②R和S的交是集合，记为R∩S, R∩S={x|x∈R∧x∈S}。
        ③R和S的差，或S关于R的相对补是集合，记为R-S，R-S={x|x∈R∧x?S}。
        在关系代数中，有4种基本的专门关系运算，即选择（Select）、投影（Project）、自然连接（Join）和除法运算（Division）。
        ④选择运算是最简单的运算，它从指定的关系中选择某些元组形成一个新的关系，被选择的元组是用满足某个逻辑条件来指定，表示为σF（R），其中σ是选择运算符，R是关系名，F是逻辑表达式。
        比如，对下表所示的订购单关系，选择职工号为E3的元组构成新的关系，可以有如下的选择运算：
        
        
        订购单关系表
        结果如下表所示。
        
        运算结果表
        ⑤投影运算是对指定的关系进行投影操作，根据该关系分两步产生一个新关系。首先选择指定的属性，形成一个可能含有重复行的表格，然后删除重复行形成新的关系，表示为πA（R），其中π是投影运算符，A是被投影的属性或属性集。
        比如：对订购单关系选取职工号和供应商号两列组成新的关系，可以有以下投影运算：
        
        结果如下表所示。
        
        π运算结果表
        ⑥自然连接运算定义如下：当两个关系R和S的某些列具有相同的属性名时，可利用这些同名属性列的相同值作为连接条件将两个关系连接起来，构成自然连接。在连接后的关系中，不仅含有R与S不同的属性列，而且含有相同的属性列，其元组的数目由公共属性列中的相同值决定。
        设R是属性名为（A1,A2， …,Am, …,Ak1）的k1元关系，S是属性名为（A1,A2,…,Am, …,Bk2）的k2元关系，其中A1,A2, …,Am是同名属性列，进行自然连接的步骤如下：选出关系R和S中属性A1,A2,…,Am完全相同的所有元组；对这些元组进行笛卡儿乘积；最后去掉重复属性。
        ⑦除法运算是指用一个m+n度的关系R除以一个n度关系S，运算结果生成一个m元的新关系。这里R的第m+i个属性和S的第i个属性（i=1, 2, …,n）必须是在相同的域上定义。如果把R的前m个属性看作一个组合属性x，后n个属性看成一个组合属性y，则S也可类似地看成一个组合属性y。这样以S中的y值来对R进行分组，当组中含有y值时，则组中的x值便构成了R除以S的一个元组。R除以S的数学表达式为
        R÷S=πa（R）-πa[πa（R）×S-R]
        式中，a为关系R中除去与S关系相同的其余属性。
        6）关系数据库标准数据语言SQL
        查询是SQL（Structured Query Language，结构化查询语言）的重要组成部分但不是全部，其主要特点如下。
        ①SQL是一种一体化的语言，包括数据定义、数据查询、数据操纵和数据控制等方面的功能，它可以完成数据库活动中的全部工作。
        ②SQL是一种高度非过程化的语言，它没有必要一步步地告诉计算机"如何"去做，而只需要描述清楚用户要"做什么"，SQL就可以将要求交给系统，自动完成全部工作。
        ③SQL非常简洁。虽然SQL功能很强，但它只有为数不多的几条命令。另外，SQL的语法也非常简单，它很接近自然语言（英语），因此容易学习、掌握。
        ④SQL可以直接以命令方式交互使用，也可以嵌入到程序设计语言中以程序方式使用。现在很多数据库应用开发工具，都将SQL直接融入自身的语言之中，使用起来更方便。这些使用方式为用户提供了灵活的选择余地。此外，尽管SQL的使用方式不同，但SQL的语法基本是一致的。
        （1）SQL的数据定义功能。SQL的数据定义功能包括数据库的定义、基本表的定义、视图的定义、存储过程的定义、规则的定义和索引的定义等。
        创建表的命令如下：
        
        修改表的命令如下：
        
        在SQL中，只允许以增加新的属性（ADD）和修改属性类型的长度（MODIFY）这两种方式修改表结构，不允许诸如更改属性名、删除属性等修改，这是从数据完整性的角度加以限制的。
        删除表的命令如下：
        
        建立索引的命令如下：
        
        索引分为两类，即唯一（UNIQUE）索引和普通索引。默认是以升序（ASC）方式建立索引，如果需要也可以按降序（DESC）方式建立索引。
        删除索引的命令如下：
        
        建立视图的命令如下：
        
        其中可以是任意的SELECT查询，它说明和限定了视图中的数据。删除视图的命令格式如下：
        
        （2）SQL的数据查询功能。SQL的核心是查询。SQL的查询命令也称为SELECT命令，其基本形式由SELECT-FROM-WHERE查询块组成，多个查询块可以嵌套执行。SELECT命令的语法如下：
        
        具体解释如下。
        .SELECT说明要查询的数据，"*"表示要指定表中的全部数据，DISTINCT说明要去掉重复元组。
        .FROM说明要查询的数据来自哪个（些）表，可以基于单个表或多个表进行查询。
        .WHERE说明查询条件，即选择元组的条件。
        .GROUP BY短语用于对查询结果进行分组，可以利用它进行分组汇总。
        .HAVING短语必须跟随GROUP BY使用，它用来限定分组必须满足的条件。
        .ORDER BY短语用来对查询的结果进行排序。
        .COMPUTE短语可以进行带明细的分组汇总。
        查询中有以下几个特殊运算符。
        .BETWEEN…AND：表示在……和……之间。
        .LIKE：字符串匹配运算符，可用通配符"*"表示0个或多个字符，"？"表示一个字符。
        .NOT：否定运算符。另外SQL中"不等于"用"！="表示。
        .ANY和SOME：在进行比较运算时只要子查询中有一行能使结果为真，则结果就为真；而ALL则要求子查询行中所有行都使结果为真时，结果才为真。
        .EXISTS或NOT EXISTS：用来检查在子查询中是否有结果返回。
        SQL不仅具有一般的检索能力，而且还有计算方式的检索。用于计算检索的函数有以下几种。
        .COUNT：计数。
        .SUM：求和。
        .AVG：计算平均值。
        .MAX：求最大值。
        .MIN：求最小值。
        （3）SQL的数据操作功能。SQL的操作功能是指对数据库中数据的操作，主要包括数据的插入、更新和删除。
        插入的命令如下：
        
        更新的命令如下：
        
        删除的命令如下：
        
        （4）SQL的数据控制功能。SQL的数据控制功能主要是指对数据库中数据的安全控制和管理，即对数据的安全提供保护，这主要表现在对数据使用的授权（GRANT）和收回授权（REVOKE）。每个用户对自己拥有的资源可以有任意的操作权限，同时也可以把其中的一部分权限授予他人。
        SQL的授权命令如下：
        
        权限可以是SELECT、INSERT、DELETE、UPDATE（<列名>［；<列名>］、ALTER和INDEX等，也可用ALL表示所有权限。
        收回权限的命令如下：
        
 
       数组
               数组的定义及基本运算
               一维数组是长度固定的线性表，数组中的每个数据元素类型相同。n维数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
               设有n维数组A［b1，b2，…，bn］，其每一维的下界都为1，bi是第i维的上界。从数据结构的逻辑关系角度来看，A中的每个元素A［j1，j2，…，jn］（1≤ji≤bi）都被n个关系所约束。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言，这n个关系仍是线性的。
               以下面的二维数组A［m］［n］为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。
               
               可将A看作一个行向量形式的线性表：
               Am*n=［［a11a12…a1n］［a21a22…a2n］…［am1am2…amn］］
               也可将A看作列向量形式的线性表：
               Am*n=［［a11a21…am1］［a12a22…am2］…［a1na2n…amn］］
               数组结构的特点如下：
               （1）数据元素数目固定。一旦定义了一个数组结构，就不再有元素的增减变化。
               （2）数据元素具有相同的类型。
               （3）数据元素的下标关系具有上下界的约束且下标有序。
               在数组中通常做下面两种操作：
               （1）取值操作。给定一组下标，读其对应的数据元素。
               （2）赋值操作。给定一组下标，存储或修改与其相对应的数据元素。
               几乎所有的程序设计语言都提供了数组类型。实际上，在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是，不能对数组进行整体的运算，只能对单个数组元素进行运算。
               数组的顺序存储
               由于数组一般不作插入和删除运算，也就是说，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
               对于数组，一旦确定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置，也就是说，在数据的顺序存储结构中，数据元素的位置是其下标的线性函数。
               二维数组的存储结构可分为以行为主序（按行存储）和以列为主序（按列存储）两种方法，如下图所示。
               
               二维数组的两种存储方式
               设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为：
               Loc（aij）=Loc（a11）+（（i-1）×n+（j-1））×L
               同理，以列为主序优先存储的地址计算公式为：
               Loc（aij）=Loc（a11）+（（j-l）×m+（i-1））×L
   题号导航      2016年下半年 程序员 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第4题    在手机中做本题