数据库工程师考试材料
1.计算机数据库系统知识
计算机系统由硬件系统和软件系统组成。硬件由运算器、控制器、存储器、输入设备、输出设备5部分组成;软件由系统软件、应用软件组成。
运算器:对数据进行处理的部件，主要完成算术和逻辑运算;
控制器:从主存中取出指令，并指出下一条指令在主存中的位置，取出的指令经指令寄存器送往指令译码器，经过对指令的分析发出相应的控制和定时信息;
控制器的组成部分为:
程序计数器
指令寄存器
指令译码器
状态条件寄存器
时序产生器
微信号发生器
计算机硬件的典型结构:单总线、双总线(以cpu为中心、以存储器为中心)、采用通道的大型系统。
2、二、八、十、十六进制间的转换方法
十进制转换成二进制:十进制整数转换成二进制整数通常采用除2取余法，小数部分乘2取整法。
例如，将30D转换成二进制数。
2| 30 ….0 ----最右位
2 15 ….1
2 7 ….1
2 3 ….1
1 ….1 ----最左位
? 30D=11110B
八、十六进制转二进制方法类似。
二进制数转换成八进制数:对于整数，从低位到高位将二进制数的每三位分为一组，若不够三位时，在高位左面添0，补足三位，然后将每三 位二进制数用一位八进制数替换，小数部分从小数点开始，自左向右每三位一组进行转换即可完成。例如:将二进制数1101001转换成八进制数，则
001 101 001B
| | |
1 5 1O
1101001B = 151O
八进制数转换成二进制数:只要将每位八进制数用三位二进制数替换，即可完成转换，例如，把八进制数(643.503)8，转换成二进制数，则
(6 4 3 . 5 0 3)8
| | | | | |
(110 100 011 . 101 000 011)2
(643.503)8=(110100011.101000011)2
二进制与十六进制之间的转换
(1)二进制数转换成十六进制数:由于2的4次方=16，所以依照二进制与八进制的转换方法，将二进制数的每四位用一个十六进制数码来表示，整数部分以小数点为界点从右往左每四位一组转换，小数部分从小数点开始自左向右每四位一组进行转换。
(2)十六进制转换成二进制数
如将十六进制数转换成二进制数，只要将每一位十六进制数用四位相应的二进制数表示，即可完成转换。
例如:将(163.5B)16转换成二进制数，则
( 1 6 3 . 5 B )16
| | | | |
(0001 0110 0011. 0101 1011 )2
(163.5B)16=(101100011.01011011)2
二进制的算术、逻辑运算
3、数据在计算机中的表示方法:各种数据在计算机中表示的形式称为机器数，其特点是用0,1表示，如0表示正号，1表示负号，小数点隐含表示而不占位置。机器数对应的实际数据称为真值。机器数分为无符号数和有符号数。无符号数表示正数。
带符号的机器数可采用原码、反码、补码等码制进行计算。
4、汉字编码:汉字处理包括汉字的编码输入、存储、输出等环节。
输入码(数字编码、拼音码、字形编码)、内部码(简称汉字内码)(GB2312-80用2字节表示一个汉字，Unicode用4字节表
示一个汉字)、字形码(点阵、矢量函数，汉字的输出方式)
5、cpu的功能:程序控制、操作控制、时间控制、数据处理
6、计算机系统分类:Flynn分类法(按指令流、数据流分类)、冯式分类法(按最大并行度分类)
指令流:机器执行的指令序列;
数据流:指令调用的数据序列。
7、计算机系统结构和计算机组成的区别:系统结构是指计算机系统在总体上、功能上需要解决的问题;计算机组成是指在逻辑上如何具体实现的问题。
8、计算机并行的发展:不同于同时性的是，并发性是指两个或两个以上事件在同一时间间隔内连续发生;分为存储器操作并行，处理器操作步骤并行(流水线处理机)，处理器操作并行(阵列处理机)，指令、任务、作业并行(多处理机、分布式处理系统、计算机网络)。
9、存储器的层次结构:高速缓存、主存、辅存。(有人将cpu内部的寄存器也作为一个存储层次)
存储器的分类:存储器按位置分为内存(主存)和外存(辅存);按工作方式分为读写存储器和只读存储器;按访问方式分为按地址访问和按内容访问的存储器;按寻址方式分为随机寻址、顺序、直接寻址存储器。
相连存储器是一种按内容访问的存储器。其工作原理是把数据作为关键字与存储器中的每一单元比较，找出与关键字相同的数据。相连存储器可用在高速缓存中;在虚拟存储器中用来作段表、页表或快表存储器;用在数据库和知识库中。
高速缓存:由控制部分和cache部分组成。cache部分放主存的部分拷贝信息，控制部分判断cpu要访问的信息是否在cache中命中，并按替换算法决定主存的哪一块信息放到cache中的哪一块里面。
一般来说，Cache的功能全部由硬件实现。
高速缓存与主存的地址映像方法有3种，即直接映像，全相连映像，组相连映像(组使用直接相连而组内的块使用全相连方式)
在Cache的替换算法中，“近期最少使用LRU算法”是命中率最高的一种算法。
10、虚拟存储器，是由主存、辅存、存储管理单元和操作系统的存储管理软件组成的存储系统。它将大容量的外存也纳入存储管理器的管理范围，具体执行程序时要先判断程序是否在主存中，若不在则需从辅存中调入。按工作方式分为:
页式虚拟存储器
段式虚拟存储器
段页式虚拟存储器
11、磁盘阵列raid，是由多台磁盘存储器组成的，一个大而快速、可靠的外存子系统。
raid0 是不具备容错能力的阵列，N个磁盘组成的0级阵列，其平均故障时间间隔是单个磁盘存储器的N分之一;但其数据传输速率是单 的N倍。
raid1 使用镜像容错技术
raid2 使用汉明码容错技术
raid3 一般使用一个检验盘
raid4 只使用一个检验盘
raid5 没有专门的检验盘，它在每块盘上都写数据和检验信息。
12、CISC--复杂指令集计算机 RISC--精简指令集计算机
RISC的特点: 指令种类少;
指令长度固定、格式少;
寻址方式少，适合于组合逻辑控制器;
设置最少的访问内存指令，访问内存比较花时间;
在CPU内部设置大量寄存器，使操作在CPU内部快速进行;
适合于流水线操作，容易并行执行。
13、输入输出技术
内存与接口的编址方式分为内存和接口地址独立的编址方式，和内存、接口地址统一的编址方式。
直接程序控制(无条件传送方式、程序查询方式)(整个输入输出过程是在cpu执行程序的控制下完成)
中断方式 (cpu得用中断方式完成数据的输入输出操作)
直接存储器存取(DMA)方式 ，数据直接在内存与IO设备间成块传送，cpu只需在开始和结束时进行处理，过程中无须干涉。
DMA传送的一般过程为:
1)外设向DMA控制器提出DMA传送请求;
2)DMA控制器向CPU提出请求;
3)CPU允许DMA工作，处理总路线控制的转交;
4)
输入输出处理机(IOP)方式 ，由一个专用的处理机完成主机的输入输出操作。
14、流水线技术，是将一条指令分解成一连串执行的子过程，在cpu中将一条指令的串行执行过程变为若干条指令的子过程重叠执行。
特点是，流水线可分成若干相互联系的子过程;执行每个子过程的时间尽量相等;形成流水处理需要准备时间;指令流发生不能顺序执行时会使流水线中断。
两个指标，吞吐率(单位时间里流水线处理机流出的结果数，对指令而言就是单位时间里执行的指令数);
建立时间(所有子过程执行一遍用时之和)
15、总线的分类--芯片内总线、元件级总线、内总线(即系统总线)、外总线(即通信总线)
常见的几种内总线:ISA总线(长短两个插座，分别有64个、32个接点)，EISA总线，PCI总线。其中PCI总线的工作与处理器的工作是相对独立的，即总线时钟和处理器时间是独立、非同步的，PCI总线上的设备即插即用。
常见的几种外总线:RS-232C(是一条串行总线)，SCSI(是一条并行总线)，USB(由4条信号线组成，两条用于传送数据，另两条传送+5V 500mA的电源)，IEE1394(是一条串行总线，由6条信号线组成，两条传数据两条传控制信号两条传电源，支持即插即用和热插拔)
16、阵列处理机，又称并行处理机，它将重复设置的多个处理单元连成阵列，在控制部件的控制下，对分配给自己的数据进行处理，并行地完成一条指令规定的操作。这是一种单指令多数据流计算机(SIMD)
17、多处理机，是由多台处理机组成的系统。每台处理机有自己的控制部件，可以执行独立的程序，共享一个主存和所有外设。它是多指令流多数据流计算机。
按其构成分为:异构(非对称)型多处理机系统，同构(对称)型多处理机系统，分布式处理系统
4种多处理机的结构:总线结构，交叉开关结构，多端口存储器结构，开关枢纽式结构
18、并行处理机，与采用流水结构的单机系统都是单指令流多数据流计算机，它们的区别是，并行处理机采用资源重复技术，而流水结构的单机系统使用时间重叠技术。
并行处理机有2种典型结构:具有分布式存储器的，具有共享式存储器的。它们的共同点是在系统中设置多个处理单元，各个处理器按一定
接方式交换信息，在统一的控制部件作用下，各自处理分配来的数据，并行的完成同一指令所规定的操作。
19、信息安全的基本要素
机密性
完整性
可用性
可控性
可审查性
20、计算机安全等级:技术安全性、管理安全性、政策法律安全性。一些重要的安全评估准则:“美国国防部和国家
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
局的《可信计算机系统评测标准》TCSEC/TDI”、“欧共体的信息技术安全评估准则ITSEC”、“ISO/IEC国际标准”、“美国联邦标准”。其中TCSEC/TDI分了4个组7个等级，C2是安全产品的最低等级。
21、安全威胁与影响数据安全的因素
安全威胁是指某个人、物、事件对某一资源的机密性、完整性、可用性或合法性所造成的危害。典型的安全威胁有很多种。
影响数据安全的因素有内部和外部两种。内部因素:可采取多种技术对数据加密;制定数据安全规划;建立安全存储体系;建立事故应急
计划
项目进度计划表范例计划下载计划下载计划下载课程教学计划下载
和容灾措施;重视安全管理并建立安全管理规范。
外部因素:按密级划分使用人员的权限;使用多种认证方式;设置防火墙;建立入侵检测、审计和追踪;同时注意物理环境的保护。
22、加密技术包括两个元素:算法和密钥。加解密算法设计的关键是满足3个条件“可逆性”，“密钥安全”，“数据安全”。
数据加密技术分为对称加密(以DES算法为代表)、非对称加密(以RSA算法为代表)、不可逆加密3种。
目前常用的对称加密算法有:DES数据加密标准算法(使用56位密钥，对64位二进制数据块加密，基本加密运算为置换运算、移位运算 、模加运算);
3DES(使用2个56位密钥，加、解、加);
RC-5;
国际数据加密算法IDEA(类似于3DES，使用128位密钥，PGP系统在使用该算法)
比较有名的非对称加密算法:RSA算法，它是建立在大素数因子分解的理论基础上的算法。其公钥密码长度大于100位，算法运算速度较慢，多用于加密信息量小的场合，可以使用RSA算法来实现数字签名。
23、密钥管理，主要是指密钥对的管理，包括密钥的产生、选择、分发、更换和销毁、备份和恢复等。多密钥的管理可以使用KDC。
24、数据完整性保护，是在数据中加入一定的冗余信息，从而能发现对数据的任何增删改。方法是在发送或写入时对所要保护的数据进行检验和作加密处理，产生报文验证码MAC，附在数据后面。在接受或读出数据时根据约定的密钥对数据进行检验和作加密运算，将所得的结果与MAC比较，根据结果是否一致判断数据是否完整。
25、认证技术，主要是解决网络通信双方的身份认可。认证的过程涉及到加密和密钥交换。加密可使用对称加密、不对称加密和二者混合使用的方法。一般有账户名/口令认证、使用摘要算法认证、基于PKI公开密钥的认证。
PKI是一种遵守既定标准的密钥管理平台，它能为所有网络应用提供加密和数字签名等密码服务及必需的密钥和证书管理体系。PKI的基础技术包括加密、数字签名、数据完整性机制、数字信封、双重数字签名等。完整的PKI系统必须包括CA、数字证书库、密钥备份及恢复系统、证书作废系统、应用接口API等基本部分。
PKI使用证书进行公钥管理，通过CA将用户的公钥和用户其它住处绑在一起，以在因特网上验证用户身份。
26、HASH函数，输入一个不定长的字符串，返回一个固定长度的字符串(即HASH值)。单向HASH函数用于产生信息摘要;信息摘要简要地描述了一份较长的信息或文件，可以被看作是一份文件的数字指纹，信息摘要用于创建数字签名。
27、数字签名的过程:
信息发送者使用一单向HASH函数对信息生成信息摘要;
信息发送者使用自己的私钥加密信息摘要;
信息发送者将信息本身和已签名的信息摘要一并发送出去;
信息接收者使用发送者的公钥对信息摘要解密，再使用同一单向HASH算法对信息生成信息摘要并进行验证是否一致。
28、数字加密的过程:
信息发送者先生成一个对称密钥，使用该密钥对信息加密;
信息发送者使用接收者的公钥加密上述对称密钥;
信息发送者将上两步的结果内容都传给接收者(这就是数字信封);
信息接收者使用私钥解密对称密钥，并使用对称密钥解密信息本身。
29、SSL安全协议，一个能够保证任何安装了SSL的客户和服务器之间事务安全性的协议，主要用于提高应用程序之间数据的安全系数。SSL提供3方面服务:客户和服务器的合法性认证;加密传送的数据;保护数据的完整性。
30、数字时间戳技术，就是数字签名技术的一个变种，不同的是这个要由认证单位DTS提供数字签名。它的过程是:先形成需要加时间戳的信息的信息摘要;将信息摘要送到DTS，DTS
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
收到的日期及时间;DTS进行数字签名，然后送回用户。
31、计算机病毒的定义，它是一种程序，具有修改别的程序的特性，并使用被修改的程序也具有这样的特性。
病毒的特点:寄生性，隐毕性，非法性，传染性，破坏性。
按病毒的寄生方式和入侵方式分成:系统引导型病毒，文件外壳型，混合型病毒，目录型病毒，宏病毒(也叫数据病毒)。
需要注意的几点:变种、病毒程序加密、多形性病毒、病毒的伪装。
计算机病毒防治的手段:人工预防;软件预防;管理预防。
解决网络安全问题的技术包括:划分网段、局域网交换技术和VLAN;加密技术、数字签名和认证、VPN技术;防火墙技术;入侵检测技术;网络安全扫描技术。
32、计算机的RAS技术，R(可靠性)、A(可用性)、S(可维修性)。
计算机可靠性的模型有:串联系统模型、并联系统、N模冗余系统。
串联系统可靠性 R = R1*R2*...Rn 平均故障率 = L1+L2+..Ln
并联系统可靠性 R = 1 - (1-R1)(1-R2)..(1-Rn)
N模冗余系统由2n+1个子系统和一个表决器组成，只要n+1个子系统工作正常，系统就工作正常。
提高可靠性的办法:提高元件质量、改进加工工艺与工艺结构、完善电路设计、发展容错讲述。
33、计算机性能评测的常用方法:时钟频率法、指令执行速度法、等效指令执行速度法、数据处理速率法、核心程序法。
基准测试程序有，整数测试程序、浮点测试程序、SPEC基准测试程序、TPC基准程序。
34、计算机故障包括永久故障、间歇性故障和偶然故障。故障诊断分为故障检测和故障定位两方面。
容错，就是通过冗余方法来消除故障影响。硬件冗余有时间冗余和器件冗余两种。
故障处理步骤，封闭、检错、重复执行、诊断、重构与恢复、修复、重入。
35、BCD(Binary-Coded Decimal)码又称为“二—十进制编码”，专门解决用二进制数表示十进数的问题。
压缩BCD码
每一位数采用4位二进制数来表示，即一个字节表示2位十进制数。例如:二进制数10001001B，采用压缩BCD码表示为十进制 数89D。
非压缩BCD码
每一位数采用8位二进制数来表示，即一个字节表示1位十进制数。而且只用每个字节的低4位来表示0,9，高4位为0。
例如:十进制数89D，采用非压缩BCD码表示为二进制数是:
00001000 00001001B
36、ASCII是 AmericanStandardCodeforInformationInterchange的缩写，用来制订计算机中每个符号对应的代码，这也叫做计算机的内码(code)。每个ASCII码以1个字节(Byte)储存，从0到数字127代表不同的常用符号，例如大写A的ASCII码是65，小写a则是97，阿拉伯数字0则是 48。由于ASCII字节的七个位，最高位并不使用。
第0,32号及第127号(共34个)是控制字符或通讯专用字符，如控制符:LF(换行)、CR(回车)、FF(换页)、DEL(删除)、BEL(振铃)等;通讯专用字符:SOH(文头)、EOT(文尾)、ACK(确认)等;
第33,126号(共94个)是字符，其中第48,57号为0,9十个阿拉伯数字;65,90号为26个大写英文字母，97,122号为26个小写英文字 母，其余为一些标点符号、运算符号等。
注意:在计算机的存储单元中，一个ASCII码值占一个字节(8个二进制位)，其最高位(b7)用作奇偶校验位。所谓奇偶校验，是指在代码 传送过程中用来检验是否出现错误的一种方法，一般分奇校验和偶校验两种。奇校验规定:正确的代码一个字节中1的个数必须是奇数， 若非奇数，则在最高位b7添1;偶校验规定:正确的代码一个字节中1的个数必须是偶数，若非偶数，则在最高位b7添1。
37、按位与的特殊用途:
清零。 方法: 与一个各位都为零的数值相与，结果为零。
取一个数x中某些指定位。 方法: 找一个数，此数的各位是这样取值的:对应x数要取各位，该数对应位为1，其余位为零。此数与x 相就可以得到x中的某些位。
例:设X=10101110
(1)取X的低4位
(2)取X的bit2、bit4、bit6位
38、某EPROM芯片上有24条地址线A0-A23，8条数据线D0-D7，则该芯片的容量为“16M”。
EPROM芯片上的地址线决定了该芯片有多少个存储单元，数据线数表明每个存储单元所存储的数据位数。24条地址线则有16M个存储单元，8条数据线决定了每个存储单元存1个字节。所以容量为16M字节。
39、机内码、国标码、区位码
根据汉字的国家标准，用两个字节(16位二进制数)表示一个汉字。但使用16位二进制数容易出错，比较困难，因而在使用中都将其转换为十六进制数使用。国标码是一个四位十六进制数，区位码则是一个四位的十进制数，每个国标码或区位码都对应着一个唯一的汉字或符号，但因为十六进制数我们很少用到，所以大家常用的是区位码，它的前两位叫做区码，后两位叫做位码。
国标码规定，每个汉字(包括非汉字的一些符号)由2字节代码表示。每个字节的最高位为0，只使用低7位，而低7位的编码中又有34个适用于控制用的，这样每个字节只有27 - 34 = 94个编码用于汉字。2个字节就有94 94=8836个汉字编码。在表示一个汉字的2个字节中，高字节对应编码表中的行号，称为区号;低字节对应编码表中的列号，称为位号。
国标码与机内码转换关系:为了不与7位ASCII码发生冲突，把国标码每个字节的最高位由0改为1，其余位不变的编码就是汉字字符的机内码 。也可以理解为国标码加上8080H后得到机内码，或是机内码减去8080H后得到国标码。
国标码与区位码转换关系:将国标码减去2020H后，得到区位码。
如某汉字机内码是BFF0H，则国标码为3F70H，区位码为1F50H。
40、在采用三总线的运算器中，三条总线分别与运算器的两个输入一个输出相连接，各自有自己的通路。因此执行一次操作只需一步即可完成。在运算器的两个输入和一个输出上不再需要设置暂存器。
41、光盘上的信号是记录在光盘表面的凹坑及平面上。凹坑与平面的交接处代表1，因此在光盘上不允许有连续的两个1
42、磁盘非格式化容量 = 最大位密度*最内圈周长*总磁道数 --实际上就是使用磁盘的面积乘以位密度
格式化容量 = 每道扇区数*扇区容量*总磁道数
总磁道数为:(外半径 - 内半径)* 磁道密度
常识:有一个多盘片组成的盘组，在向磁盘记录一个文件时，如果超出了一个磁道容量，那么剩下的部分将存于其他盘面的同一编号的磁道上。因为盘组中的多个盘面形成一系列柱面，在向磁盘写入文件时会尽可能记录在同一柱面上，当一个柱面记录不下时，再记录到相邻的柱面上。
43、微指令根据编码方式的不同分为水平微指令和垂直微指令。
水平微指令，长度较长、操作具有高度并行性、编码简单、执行速度快，更多地体现了控制器的硬件细节;
垂直微指令，长度较短、并行度低、功能弱、效率低、编程容易但微程序长。
排列组合公式为: 求n上数中m个数的组合有多少， C = n(n-1)(n-2)..(n-m+1)/m!
例如求n个数中每2个数组合的可能性，C = n(n-1)/2 种可能性
2.数据结构与算法
1、线性表的定义及特点
线性表是若干数据元素组成的有限集合;
线性表的特点是，有惟一的起始结点和惟一的终端结点，其它元素都有惟一的直接前驱和惟一的直接后继。
线性表的抽像数据类型定义包括2方面，
数据对象、关系的定义;
线性表有关操作的定义;
线性表的数据对象是具有相同性质数据元素的集合。
线性表的有关操作有:
基本操作:初始化线性表、撤消线性表、判/置空表、取表长、取前驱元素、取后继元素、取第i个元素、遍历等。
插删操作:在顺序结构下，结点的插入(n/2)和删除[(n-1)/2]主要是进行元素的移动;在链式结构下，结点的插删是调整指针的指向。
查找操作:在顺序表中可以进行折半查找，在链表中只能进行顺序查找。
2、线性表的基本存储结构及特点，线性表有顺序和链式两种存储结构。
顺序存储结构是:用一组地址连续的存储单元依次存储线性表中的数据元素;
链式存储结构是:用一组地址任意的存储单元存储线性表中的数据元素。(存储单元节点可以是连续的，也可以是不连续的)
链式存储结构包括，
单链表(又称线性链表)，结点的结构体有两个域，分别存储数据元素和当前元素有关系的其它元素所在结点的指针
双向链表，每个结点包含两个指针，分别指明直接前驱和直接后继元素，可以在两个方向上遍历其后及其前的元素;
循环链表，链表中最后一个结点的指针指向第一个结点，开成环状结构，可以在任意位置上方向不变地遍历全表;
静态链表，借助数组描述线性表的链式存储结构。
3、栈的定义:是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。
栈的特点:是先进后出(FILO)。在线结构中，允许进行插、删操作的一端称为栈顶，相应另一端称为栈底。不含数据的栈称为空栈。
栈的基本运算有:置空栈、判空栈、元素入栈、出栈和读取栈顶元素的值。
栈的存储结构:顺序栈和链栈。
顺序栈指，用一组连续的存储单元依次存储自栈顶到栈底的元素，同时设置指针top指示栈顶元素的位置。顺序栈的空间容量是有限的，要预先定义。顺序栈的入栈和出栈操作是通过修改数组下标来完成。假设栈底对应于数组下标较大的一端，那么在元素入栈时就是下标减1，而元素出栈时就是下标加1。
链栈，类似于线性链表，栈顶指针就是链表首结点的位置，元素的插删操作限定在首结点处进行。
栈的应用:表达式计算，数制转换，括号匹配，迷宫问题，递归问题
4、队列的定义:是一种先进先出(FIFO)的线性表。
队列的特点:它只允许在表的一端插入元素而在表的另一端删除元素。在队列中允许插的一端叫队尾(rear)，允许删的一端叫队头(front)。
队列的基本运算:置队空、判队空、入队、出队、读队头元素等。
队列的存储结构:顺序队列和链队列。
顺序队列，又被叫作循环队列，设顺序队列Q，Q.front表示队头指针，Q.rear表示队尾指针，则Q.front和Q.rear
相等且为0时为空队列;元素入队时Q.rear加1，元素出队时Q.front加1。因为顺序队列的空间容量是提前设定的，所以当Q.rear达到了上限时表示队列满。 为区别队列空和队列满两种情况下可能出现的Q.front == Q.rear，有两种方法。一个是设置一个标识位，以区别头尾指针相同时队列是空还是满;另一个方法是牺牲一个元素空间，约定以Q.rear所指的下一个位置是Q.front时表示队列满。
链队列，链队列为空的判定条件是头尾指针相同且均指向头结点。
队列的应用:常用于需要排队的场合，如操作系统中的打印队列，离散事件的复读机模拟等。
5、串的定义:是仅由字符构成的有限序列。是取值范围受限的线性表。一般记为S = 'a1a2..an'。
串的几个概念:空串、空格串、子串、串相等、串比较。
串的几个操作:赋值操作StrAssign(s,t)、联接操作Concat(s,t)、求串长StrLength(s)、串比较StrCompare(s,t)、求子串SubString(s,start,len)。
串的存储:静态存储(顺序存储)，是定长的存储结构。当串超长时，超过部分将被截断。
堆存储，通过程序语言提供的字符数组定义串的存储空间，事先不限定串的长度，在程序执行过程中动态地申请地址连续的串值的空间。
块链存储，使用链表存储串值，每个结点可以存储一个或多个字符，同时每个结点设置一个指针指向后继结点。
串的模式匹配:朴素的模式匹配法、KMP算法。
6、数组:是定长线性表在维数上的扩张，即线性表中的每个元素又是一个线性表。N维数组是一种同构的数据结构，其每个数据元素类型相同，结构一致。
数组的特点: 数组元素数目固定。一旦定义了一个数组结构就不再有元素的增减变化;
数据元素具有相同的类型;
数据元素的下标关系受上下界的约束且下标有序。
数组的基本运算:
给定一组下标，存取相应的数据元素;
给定一组下标，修改相应的数据元素中的某个数据项的值。
数组的存储: 数组的固定结构适于使用顺序存储。对于数组，只要知道它的维数和长度，就可以为它分配存储空间。反之，只要给出一组下标就可以求出该数组元素的存储位置。就是说，在数组的顺序存储结构中，数据元素的位置是其下标的线性函数。
以行为主序; Loc(Aij) = Loc(Aij) + ((i-1)*n + (j-1))*L
以列为主序; Loc(Aij) = Loc(Aij) + ((j-1)*m + (i-1))*L
多维数组的顺序存储计算:例如3维数组A[1..10, 5..8, -3..6]，数组空间的起始位置是a，每个元素占4个存储单元，试以行为主存储和以列为主存储时给出数组元素A[i,j,k]的存储地址。
解:理解上面给出的以行为主序和以列为主序的两个线性函数公式。把3维数组拆开计算，例如以行为主序时先将3维数组看成是有一个行和2个列的数组，算出此时以行为主占用了多少空间。然后再单独看两个列的组合B[j,k]又会占用多少空间。前后结果相加就是这个3维数组元素在以行为主序存储时的地址。如下，
以行为主序时，A[i,j,k]前面的元素个数是: (i-1)(8-5+1)(6-(-3)+1) + (j-5)(6-(-3)+1) + k-(-3) = 40i-40 + 10j-50 + k+3 =
40i + 10j + k -87
因此A[i,j,k]的地址为a + (40i+10j+k-87)*4
以列为主序时，A[i,j,k]的地址为a + (40k+10j+i+69)*4
7、特殊矩阵与稀疏矩阵，稀疏矩阵就是非零元素很少的矩阵，而特殊矩阵是非零元素分布有规律的一类矩阵。为节省空间，在存储它们时都使用压缩存储，特殊矩阵有压缩算法，稀疏矩阵使用三元组顺序表或使用十字链表存储矩阵元素。
8、广义表的定义:是由零个或多个单元素或子表所组成的有限序列。广义表的长度是指广义表中元素的个数，深度是指广义表展开后所含的括号的最大层数。
广义表的基本运算:取表头head(LS)，非空广义表的第一个元素称为表头;
取表尾tail(LS)，非空广义表中除第一个元素之外，由其余元素构成的表称为表尾。表尾必定是一个表。
Head(LS)=a1, Tail(LS)=(a2,a3,...,an)
9、树的定义:树是n(n>=0)个结点的有限集合。当n=0时称为空树。在任一非空树中，有且仅有一个称为根的结点;其余m个结点可分为m(m>=0)个互不相交的有限集，其中每个子集合又都是一棵树，称为根结点的子树。
树的定义是递归的，树形结构具有明显的层次结构。
树的术语:双亲和孩子，兄弟，结点的度，叶子结点，内部结点，结点的层次，树的高度，有序树和无序树，森林。
树的基本操作是:先根遍历和后根遍历。
10、二叉树的定义:二叉树是另一种树形结构，它的特点是每个结点至多有两棵子树并且有左右之分，且左、右子树的次序不能颠倒。
满二叉树，若二叉树上每一层的结点数目都达到最大值，则称为满二叉树;
完全二叉树，若二叉树的除第H层以外，其余各层的结点数目达到了最大值，而第H层上的结点集中存放在左侧，则称为完全二叉树;
非完全二叉树，就是完全二叉树的相反情况。
二叉树的性质: 1)二叉树第i层(i>=1)上至多有2^(i-1)个结点;
2)深度为K的二叉树至多有2^k -1 个结点(k>=1);
3)对任何一棵二叉树，若其终端结点个数为N0，度为2的结点个数为N2，则N0 = N2 + 1 ;
4)具有n个结点的完全二叉树的深度为log(2,n)+1;
5)对一棵有n个结点的完全二叉树的结点按层次自左至右进行编号，则对任一结点i (1<=i<=n)有:
若i=1，则i是根结点;若i>1则其双亲为i/2;
若2i>n,，则结点i无左孩子，否则其左孩子为2i;
若2i+1>n,则结点i无右孩子，否则其右孩子为2i+1;
例:一棵有124个叶结点的完全二叉树，最多有多少结点,
N0=N2+1
N=N0+N1+N2
N1=1
综合上面3个表达式可以求解。
例2:具有N个结点的满二叉树，其叶子结点个数为多少,
设其深度为h，则: N0=2^(h-1)
N = 2^h - 1
所以N0 = (n+1)/2
二叉树的存储结构:
二叉树的顺序存储结构，若采用二叉树的性质5对树中的结点进行编号，即树根结点的编号为1，若编号为i的结点存在左孩子，则其左孩子的编号为2i;若编号为i的结点存在右孩子，则其右孩子的编号为2i+1，这样利用数组元素的下标作为结点的编号，表示出结点间的关系。
二叉树的链式存储结构，二叉链表(有单向性)和三叉链表(有双向性)。
遍历二叉树，有4种方式:先序、中序、后序和层序遍历。
先序遍历二叉树的操作定义为:访问根结点;先序遍历根的左子树;先序遍历根的右子树。(若二叉树为空，则进行空操作)
中序遍历二叉树的操作定义为:中序遍历根的左子树;访问根结点;中序遍历根的右子树.(若二叉树为空，则进行空操作)
后序遍历二叉树的操作定义为:后序遍历根的左子树;后序遍历根的右子树;访问根结点。
层序遍历二叉树的操作定义为:从根结点开始，从或到右依次访问每层上的结点。
二叉树遍历思想的关键:首先在想象中把二叉树补齐为满二叉树，叶子结点也要被想象为有2个子结点。然后，画一条路线，从根出发，逆时针沿着二叉树的外缘移动，全程对每个结点均途经三次。若第一次经过时即访问，则是先序遍历;若是第二次经过结点时访问结点，则是中序遍历;若是第3次经过时访问则是后序遍历。这3种方法的路径相同，但结果不同。
遍历二叉树的基本操作就是，访问结点。--遍历二叉树实质上是按一定规则，将树中的结点排成一个线性序列。
11、线索二叉树:对于有N个结点的二叉树的二叉链表存储表示，其中必有N+1个空指针。遍历时使结点中原本为空的左孩子指针或(和)右孩子指针指向结点的前驱或(和)后继，这样的处理称为对二叉树的线索化，指向前驱或后继的指针称为线索。加上线索的二叉树称为线索二叉树。
为了区分结点中的指针是孩子还是线索，在结点结构中增加标志域ltag, rtag。两个标志取值0，则lchild,rchild域分别指向左孩子和右孩子;两个标志取值1，则lchild,rchild域分别指向直接前驱和直接后继。
访问线索二叉树时，如何查找结点的前驱和后继,以中序线索二叉树为例，令P指向树中的某个结点，
当p->ltag = 0时，P的中序直接前驱一定是其左子树进行中序遍历得到的最后一个结点，也可以沿P的左子树根结点出发沿右孩子指针向下查找，直到找到一个没有右孩子的结点时为止，该结点就是P的直接前驱结点，也称为P的左子树中“最右下”的结点。
当P->rtag = 0时，P的中序直接后继一定是其右子树进行中序遍历得到的第一个结点， 也可以沿P的右子树根结点出发沿左孩子指针向上查找，直到找到一个没有右孩子的结点时为止，该结点就是P的直接后继结点，也称为P的右子树中“最左下”的结点。
12、二叉树的应用:最优二叉树(又称霍夫曼树)，是一种带权路径长度最短的树。
路径，是从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。
树的路径长度，是从根到每一个叶子结点之间的路径长度之和。
结点的带权路径长度，是从该结点到树根之间的路径长度与该结点权的乘积。
树的带权路径长度，是树的所有叶子结点的带权路径长度之和，记为 WPL 。
如何构造最优二叉树,使用霍夫曼算法如下:
1)将给定的N个结点的权值构成N棵二叉树的集合F，其中每棵树Ti只有一个权为Wi的根结点，其左右子树为空;
2)在F中选取两棵根结点的权值最小的树作为左右子树，并新生成一个根结点，根结点的权值为左右子树的权值和;
3)从F中删除被取出的两棵树并将新生成的树放入F;
4)重复2，3步骤到只剩一棵树为止，这棵树就是最优二叉树。最优二叉树的形式不唯一，但其WPL值却是唯一确定的。
霍夫曼编码:若要设计长度不等的编码，则任一字符的编码都不是其他字符编码的前缀，这种编码称为“前缀编码”。要设计总长最短的二进制前缀编码，应以N种字符出现的频率作为权来构造一棵霍夫曼树，由此得到的二进制前缀编码称为霍夫曼编码。树的左右分枝分别标上0和1(或相反)。从根到叶子路径上的0，1组成的串就是每个字符的二进制编码。
13、树的存储结构
1)树的双亲表示法，用一组连续的存储单元存储树的结点，并在每个结点中附设一个指示器，指示其双亲结点在该存储结构中的位置;
2)树的孩子表示法，是在存储结构中用指针指出结点的每个孩子。要为树的每个结点的孩子建立一个链表，则N个结点的树具有N个单链表，这N个单链表的头指针又排成了一个线性表(头指针即树的存储结构中每个结点的指示器)。
将上两种方法结合起来可以形成树的双亲孩子表示法。
3)树的孩子兄弟表示法，是指用二叉链表表示树。在链表的结点中设置两个指针域，分别指向该结点的第一个孩子和下一个兄弟。 |firstchild| data |nextbrother| 若将树的孩子指针解释为左孩子、兄弟指针解释为右孩子，则可以得到这棵树的二叉树结构。
14、树的遍历:
先根遍历;
后根遍历。
树进行先根遍历也就是对转换得到的二叉树进行先序遍历;对树进行后根遍历也就是对转换得到的二叉树进行中序遍历。
(先根遍历的顺序是:由根出发从左至右遍历每棵子树。后根遍历的顺序是从左至右从每棵子树的叶子结点向根的方向访问子树，最后访问根结点。)
15、森林的遍历:
先序遍历森林;
中序遍历森林。
先序遍历森林，若森林非空，访问森林中第一棵树的根结点，先序遍历第一棵子树根结点的子树森林，再先序遍历除第一棵树之外的树所构成的森林。
中序遍历森林，若森林非空，中序遍历森林中第一棵树的子树森林，再访问第一棵树的根结点，再中序遍历除第一棵树以外的树所构成的森林。
16、树、森林和二叉树的转换
利用树的孩子兄弟表示法可以由一棵树转成唯一的一棵二叉树。
森林如何转换成二叉树呢,因为树根没有兄弟，所以树转换成二叉树后一定没有右子树，所以森林转换成二叉树的方法是:
1)先将森林中的每棵树全转成二叉树;
2)用第一棵树的根做新二叉树的根，第一棵树转为二叉树后得到的左子树做为新二叉树的左子树，第二棵树作为新二叉树的右子树，第三棵树作为新二叉树的右子树的右子树，依此类推，森林便转为了一棵二叉树。
17、图的定义:在数据结构中，图是一个由顶点集合和边集合构成的二元组，其中边表示顶点之间的关系。
图的主要术语:
有向图，图中每条边都是有方向的，弧、弧尾、弧头;
无向图，图中的边是没有方向的，边;
无向完全图，图中的N个结点之间每两个结点间都有边，共有n(n-1)/2条边;
有向完全图，图中的N个结点之间每两个结点间都有方向相反的两条弧，共有n(n-1)条弧;
度、入度、出度，顶点v的度是指关联于该顶点的边的数目，记作D(v)。若是有向图则以该顶点为终点的有向边数目称为入度，从该顶点出发的有向边的数目称为出度，有向图的度是入库和出度的和。
路径，两个顶点之间由边组成的一条通路。若是有向图则路径也有方向。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路。若首尾顶点以外的顶点均不相同则是简单路径，若只有首尾顶点相同则称为简单回路。
子图，一个图的顶点集合与边集合都从属于另一个图，则称之为另一个图的子图;
连通图与连通分量，在无向图中若两个顶点之间有路径则称为这两个顶点是连通的。若无向图中任两个顶点间都是连通的则称其为连通图。该无向图的最大连通子图称为它的连通分量。
强连通图与强连通分量，是有向图的连通概念;
网，边(弧)带权值的图称为网;
生成树，是一个极小的连通子图，它包括图中的全部顶点，但只有构成一棵树的n-1条边;
有向树和生成森林，一个有向图恰有一个顶点的入度为0其它顶点的入度均为1，则这是一棵有向树。生成森林是一个有向图中的若干棵有向树组成，特点是含有全部顶点但只有足以构成若干棵不相交的有向树的弧。
图的存储结构:
邻接矩阵表示法，用于表示图有顶点之间的关系。对于个有n个顶点的图G,(V，E)来说，其邻接矩阵就是一个n阶方阵。依靠判断图的两顶点间是否存在边或弧来决定Aij=1或Aij=0;网的邻接矩阵，当两顶点间存在边或弧时Aij等于权值否则Aij等于无穷。
邻接链表表示法，为图的每个顶点建立一个单链表，单链表中的结点表示依附于相应顶点的边或弧，有表头结点和表结点两种结构类型。
图的遍历:深度优先搜索;广度优先搜索。一个类似于先根遍历，一个类似于层序遍历。
生成树的概念:生成树是连通图的一个子图，它由全部顶点和一次遍历图所经过的边组成。图的生成树不惟一，按深度优先搜索得到深度优先生成树，按广度优先搜索得到广度优先生成树。一个非连通图，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，称为非连通图的生成树森林。
18、最小生成树:连通网的边是带有权值的，将生成树的各边权值和称为生成树的权。其中权值最小的生成树称为最小生成树。
构造最小生成树的两种算法:
普里母算法:以一个顶点集合U作为初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U至U,V时为止。例如初始只给U一个顶点且边的集合TE,,,;这种算法的时间复杂度为O(n^2)，因为它由顶点推算出的，所以适合于边稠密的网的最小生成树。
克鲁斯卡尔算法:假设连通网N,(V，E)，令最小生成树的初始状态为只有n个顶点而无边的非连通图T,(V，,,)，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。信此类推，直至T中所有顶点都在一个连通分量上为止。这种算法与顶点数无关，所以适合计算顶点多而边稀疏的网的最小生成树。
19、AOV网(active on vertex):在有向图中，以顶点表示活动，用有向边表示活动之间的优先关系，这样的网称为AOV网。在AOV网中不应出现有向环。
拓朴排序:是将AOV网中所有顶点排成一个线性序列的过程，并且该序列满足:若在AOV网中从顶点Vi到Vj有一条路径，则在该线性序列中，顶点Vi必然在Vj之前。
拓朴排序的方法:在AOV网中选一个入度为0的顶点并输出它;从网中删除该顶点及与其有关的边;重复前两步至网中不存在入度为0的顶点为止。这样操作会有两种结果:一个是所有顶点已输出，也就是拓朴排序完成，说明网中不存在回路;另一个可能结果是尚有未输出的结点，剩余顶点均有前驱顶点，表明网中存在回路～
也可以进行逆拓朴排序，即计算出度为0的顶点。拓朴算法的时间复杂度为O(n+e)。
AOE网(active on edge):，在带权有向图中，以事件表示顶点，以边表示活动，以边上的权值表示活动持续的时间，则这种网称为用边表示活动的网，简称AOE网。
AOE网特点:
1)顶点所表示的事件是指该顶点的所有进入边所表示的活动已完成，所有发出边表示的活动可以开始的一种状态。
2)对一个工程来说，要有一个开始状态和一个结束状态，所以在AOE网中有一个入度为0的开始顶点，称为源点;有一个出度为0的结束顶点，称为汇点。AOE网中也不允许存在回路。
3)完成整个工程的时间是从开始顶点到结束顶点间的最长路径的长度(指该路径上的权值和)。
活动的松驰时间:用活动的持续时间和该活动两侧的两个事件的关键路径时间，二者取差。
关键路径:从源点到汇点的路径长度最长路径称为关键路径。关键路径上的所有活动均是关键活动。
最短路径,,,
20、查找的基本概念
1)查找是一种常用的基本运算。查找表是由同一类型数据元素构成的集合;
2)静态查找表，指在进行查找运算时不再修改的已经构造好的查找表。静态查找表只进行两种操作:查询某个特定的数据元素是否在查找表中;检索某个特定的数据元素的各种属性。
3)动态查找表，是可以进行另两种操作的查找表，即在查找表中插入一个数据元素;从查找表中删除一个数据元素。
4)关键字，是数据元素的某个数据项的值，用它来识别这个数据元素;
5)主关键字，指能唯一标识一个数据元素的关键字;
6)次关键字，指能标识多个数据元素的关键字;
7)查找，根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录，并返回结果。
顺序查找，从表的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字和给定值相等则查找成功;若整个表均比较过仍未找到则查找失败。若要查找的记录不在表中则需进行n+1次查找。
平均查找长度为(n+1)/2。
折半查找(二分查找)，可以用二叉树进行分析，以中间记录为根，左子表为左子树，右子表为右子树，依此类推。关键字的比较次数即为被查找结点在树中的层数。查找成功或失败时所比较的关键字数不超过树的层数。折半查找只适用于有序顺序表(以数组方式存储的有序表)。 n=2^k - 1, k=log(n+1)
分块查找，又称为索引顺序查找，综合使用上面两种方法。
将长度为n的表均匀分为b块，每块含有s个记录，按顺序查找确定元素所在的块，则ASL = Lb + Lw , 即块内查找与索引查找之和。
ASL=(b+1)/2 + (s+1)/2 , 当s取n的平方根时，ASL取得最小值“n的平方根加1"。
21、二叉排序树(又称二叉查找树):二叉查找树或者是一棵空树，或者具有这样的特性，
1)若二叉查找树的左子树非空，则左子树上的结点值均小于根结点的值;
2)若它的右子树非空，则右子树上的结点值均大于根结点的值;
3)左、右子树的子身就是一棵二叉查找树。
二叉查找树的查找过程从根结点开始，过程类似于折半查找(二分查找)。二叉查找树的插入操作按它的特性法则进行插入，若是空树则作根结点，否则会成为一个新的叶子结点。在二叉查找树中删除一个结点时不能把该结点的子树也删掉，只能删除这个结点但仍要保持二叉查找树的特性，相当于是从一个有序序列中删除一个元素，不能破坏其它元素的有序性。一种方法是，如果删除结点,P，则可以用,P的直接前驱或直接后继代替,P，同时删除它的直接前驱(或直接后继)。
二叉排序树顺序存储在一地址连续的空间内，则序列按中序递增存储。
22、平衡二叉树:它或者是一棵空树，或者具有这样的性质:它的左右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。
平衡因子: 某结点的平衡因子定义为该结点的左子树深度减去它的右子树深度。平衡二叉树上的所有结点的平衡因子只可能是,1、0和1。
为了得到树形均匀的二叉排序树，在构造二叉排序树的过程中可以使用几种办法让它保持为一棵平衡二叉树。每插入一个新结点时，就检查是否打破了平衡。若是，则找出最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡二叉树中结点间关系，达到新的平衡。
最小不平衡二叉树是指离插入结点最近且以平衡因子的绝对值大于1的结点作为根的子树。
平衡二叉树上的插入操作引起不平衡的解决方法:
1)单向右旋平衡处理 ,,用于在根的左子树根结点的左子树上插入新结点情况
2)单向左旋平衡处理 ,,用于在根的右子树根结点的右子树上插入新结点情况
3)双向旋转(先左旋后右旋)操作 ,,用于在根的左子树根结点的右子树上插入新结点的情况
4)双向旋转(先右旋后左旋)操作 ,,用于在根的右子树根结点的左子树上插入新结点的情况
B树，有几个比较鲜明的特点。如:一棵m阶的B树中每个结点至多有m棵子树;非终结点(根除外)至少有m/2棵树;根至少有两棵子树(当根不是叶子时);所有叶子结点出现在同一层次上。
23、哈希表的定义:根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关健字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表。这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。哈希函数是从关键字集合到地址集合的映像。
对于哈希表主要考虑两个问题:一是如何构造哈希函数;一是如何解决冲突。
构造哈希函数要解决好两个问题:首先哈希函数是一个压缩映像函数;其次哈希函数应具有较好的散列性。前者为节省空间，后者为减少冲突。常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法。
处理冲突的方法:
1)开放地址法 Hi = (H(key) + Di)%m i=1,2,...,k (k<=m-1)
H(key)为哈希函数;m为哈希表的表长;Di为增量序列。
Di=1,2,3,...,m-1 称为线性探测再散列;
Di=1^2,-1^2,2^2,-2^2...,k^2 (k<=m/2) 称为二次探测再散列;
Di,伪随机序列，称为随机探测再散列。
最简单的产生探测序列的方法是线性探测，即当冲突时顺序对下一单元进行探测并存储。在用线性探测法解决冲突构造的哈希表中进行查找时有3种可能结果:一是在某一位置上找到关键字等于key的记录，查找成功;一是按探测序列查找不到而又遇到了空单元，查找失败，此时可进行插入操作;一是查遍全表，未查到指定关键字且存储区已满，要进行溢出处理。
线性探测法的缺点是“溢出处理需别编程序”，“很容易产生聚集现象”。
2)链地址法 ，它在符号表的每一个记录增加一个链域，链域中存放下一个有相同哈希函数值的记录的的存储地址。
3)再哈希法 ，Hi = RHi(key) i= 1,2,..,k RHi均是不同的哈希函数，即在同义词发生地址冲突时计算另一个哈希函数地址，直到解决。
4)建立一个公共溢出区，一溢出全放这里去;
哈希表的装填因子， a = (表中添入的记录数/哈希表长度) ,,a越小，发生冲突的可能越小
虽然哈希表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得哈希表的查找过程仍是一个给定值和关键字进行比较的过程。仍须以平均查找长度衡量哈希表的查找效率。
在查找过程中须与给定值进行比较的关键字的个数取决于3个因素:哈希函数、处理冲突方法、哈希表的装填因子。
24、排序:稳定的排序、不稳定的排序。
内部排序、外部排序。
简单排序法:包括直接插入排序、冒泡排序和简单选择排序。它们的算法复杂度为O(n，2)，在元素已经基本有序的情况下，使用直接排序方法可获得较高的效率O(n)。直接插入排序和冒泡排序是稳定的排序方法，简单选择排序是不稳定的排序方法。
直接插入排序适用于”在文件局部有序或文件长度较小的情况下的一种最佳内部排序方法“。直接插入排序的时间复杂度为O(n*n)，若记录序列为正序时其时间复杂度可提高到O(n)。正序,,
冒泡排序算法: void bubblesort(int data[], int n){
int i,j,tag,temp;
for(i=0,tag=1;tag==1&&i
data[j+1]){
temp=data[j];data[j]=data[j+1];data[j+1]=temp;
tag=1;
}
}
}
简单选择排序算法:void selectsort(int data[], int n){
int i,j,k,temp;
for(i=0;i [,<目标列表达式>]...
FROM <表名或视图名>[,<表名或视图名>]
[WHERE <条件表达式>]
[GROUP BY <列名 1> [HAVING <条件表达式>]]
[ORDER BY <列名 2> [ASC|DESC]...]
其中，子句顺序是:SELECT、FROM、WHERE、GROUP BY、HAVING和ORDER BY。HAVING只能和GROUP
BY搭配使用。
SELECT对应关系代数运算中的投影运算;FROM对应笛卡尔积;WHERE对应选择。
SELECT查询中没有全程量词，也没有逻辑蕴涵，但可以通过谓词转换来实现。,
(二)简单查询
(三)连接查询
检索至少选修了课程号为C1和C3的学生号:SELECT Sno FROM SC SCX, SC SCY WHERE SCX.Sno =
SCY.Sno AND SCX.Cno = 'C1' AND SCY.Cno = 'C3';
(四)子查询与聚集函数， 子查询也叫嵌套查询。
例:检索选修课程名为MS的学生号和学生姓名。
SELECT Sno, Sname
FROM Students
WHERE Sno IN
(SELECT Sno FROM SC
WHERE Cno IN
(SELECT Cno FROM C WHERE Cname = 'MS'));
聚集函数:AVG, MIN, MAX, SUN, COUNT
使用谓词ANY和ALL必须同时使用比较运算符，其含义与等价的转换关系如下:
,ANY ,,, ,MIN
,ALL ,,, ,MAX
,ANY ,,, ,MAX
,ANY ,,, IN
,,ALL,,, NOT IN
几个例子:查询其他系比计算机系CS所有学生年龄都要小的学生姓名及年龄。
SELECT Sname, Sage
FROM Students
WHERE Sage < ALL
(SELECT Sage
FROM Students
WHERE SD = 'CS')
AND SD<>'CS';
用,MIN代替上面的,ALL:
SELECT Sname, Sage
FROM Students
WHERE Sage <
(SELECT MIN(Sage)
FROM Students
WHERE SD = 'CS')
AND SD<>'CS';
(五)分组查询
GROUP BY 子句
HAVING 子句，如果在元组被分组之前需要按某种方式加以限制，使不需要的分组为空，可以在GROUP BY子
句后面加一个HAVING子句。
注意:空值在任何聚集操作中都会被忽视，COUNT(,)是计算某个关系中所有元组数目之种，但COUNT(A)是
计算A属性中非空的元组个数之和。
例:针对供应商数据库中的S、P、J。SPJ关系，查询哪一个工程至少用了3家供应商(包含3家)供应的零件的平
均数量，并按工程号降序排列。
SELECT JNO，AVG(QTY)
FROM SPJ
GROUP BY JNO
HAVING COUNT(DISTINCT(SNO)),2
ORDER BY JNO DESC;
(六)别名运算
(七)字符串操作， 使用操作符LIKE的模式匹配。%匹配任意字符串，_ 可以匹配任意一个字符。
在Like中可以使用转义字符，将特殊字符当作普通字符处理，如反斜杠“\"。
(八)集合操作， 保留字UNION，INTERSECT，EXCEPT分别对应并、交、差。保留字用于两个查询时，其两
侧应用括号括起来。
例:学生和教师的关系模式如下，查询既是女研究生又是教师且工资大于1500元的名字和地址。
(SELECT Name, Address
FROM Students
WHERE SEX='女' AND Type='研究生')
INTERSECT
(SELECT Name, Address
FROM Teachers
WHERE Salary >=1500)
查询不是教师的学生:(SELECT Name, Address FROM Students)
EXCEPT
(SELECT Name, Address FROM Teachers)
(九)视图的查询和删除
视图的查询:当查询视图表时，通常先将其转换成等价的对基本表的查询，然后执行查询语句。即系统先从数据字典
中取出该视图的定义，然后与视图中的查询语句结合起来，形成一个修正的查询语句。
视图更新要遵守的规则:
从多个基本通过连接操作导出的视图不允许更新;
对使用了分组、集函数操作的视图不允许更新;
若视图是从单个基本表通过投影、选取操作导出的，则允许进行更新操作。
WITH子句，将一个复杂的查询分解成一小视图,,
(十)插入、删除和修改语句
插入: INSERT INTO 表名(字段名[，字段名]...)
VALUES(常量[，常量]...);
删除: DELETE FROM 表名
WHERE 条件表达式;
修改: UPDATE 表名
SET 列名,值表达式
[WHERE条件表达式]
5、SQL中的授权
数据库中的完整性是指数据库的正确性和相容性。
(一)主键约束 PRIMARY KEY
完整性约束条件:完整性约束条件作用的对象有关系、元组、列3种，每种又分为静态、动态两类。
完整性控制:有3方面的功能，定义功能、检测功能、处理功能。这样来保证实现对数据的完整性控制。检查是否违
背完整性约束的时机 有两个:立即执行约束和延迟执行约束。前者在一条语句执行完后立即检查，后者在整个事
务执行完成后进行。
实体完整性(PRIMARY KEY子句)，关系中只能有一个主键，声明主键的方法有两个，就是primary key放的位置
不同。
如， CREATE TABLE Students
(Sno CHAR(8),
Sname CHAR(10),
Sex CHAR(1),
Sdept CHAR(20),
Sage NUMBER(3),
PRIMARY KEY(Sno));
或 CREATE TABLE Students
(Sno CHAR(8) PRIMARY KEY,
Sname CHAR(10),
Sex CHAR(1),
Sdept CHAR(20),
Sage NUMBER(3));
(二)外键约束 FOREIGN KEY(参照完整性)
格式: FOREIGN KEY(属性名)REFERENCES 表名(属性名)
[ON DELETE[ CASCADE|SET NULL]]
ON DELETE CASCADE指明删除参照关系的元组时，同时删除参照关系中的元组。
(三)属性值上的约束 NULL和CHECK
如果要求某属性为空，在定义时在数据类型的后面加上NOT NULL。
如， CREATE TABLE Students
(Sno CHAR(8),
Sname CHAR(10) NOT NULL,
Sex CHAR(1),
Sdept CHAR(20),
Sage NUMBER(3),
PRIMARY KEY(Sno));
在Students表中，要求男生的年龄在15,25之间，女生的年龄在15,24之间。
如， CREATE TABLE Students
(Sno CHAR(8),
Sname CHAR(10) NOT NULL,
Sex CHAR(1),
Sdept CHAR(20),
Sage NUMBER(3),
PRIMARY KEY(Sno))
CHECK(Sage >=15 AND ((SEX='M' AND Sage<=25) OR
(SEX='F' AND Sage<24)));
(四)全局约束 CREATE ASSERTIONS
全局约束是指一些较复杂的完整性约束，会涉及到多个属性间的联系或多个关系间的联系。分为两种:基于元组的检查子句和断言。
1)使用CHECK子句对单个关系的元组值加以约束，可以在关系的定义中的任何地方加上CHECK及约束条件;
2)断言: CREATE ASSERTION ,断言名, CHECK(,条件,)
例如，在教学数据库模式Students,SC,C中加一个约束，不允许男同学选修“张勇”教师的课。
CREATE ASSERTION ASSE,SC1 CHECK
(NOT EXISTS
(SELECT , FROM SC WHERE Cno IN
(SELECT Cno FROM C WHERE TEACHER='张勇')
AND Sno IN
(SELECT Sno FROM Students WHERE SEX='M')));
又如，在Students,SC,C中有一个约束，每门课最多允许50名男同学选修。
CREATE ASSERTION ASSE,SC2 CHECK
(50,,ALL(SELECT COUNT(SC.Sno)
FROM Students,SC
WHERE Students.Sno=SC.Sno AND SEX='M'
GROUP BY Cno));
(五)授权与销权，DBMS数据控制应具有这样的功能，通过GRANT和REVOKE将授权通知系统并存入数据字典;当用户提出请求时，检查其授权情况。
授权语句格式:
GRANT ,权限,[，,权限,]...
[ON,对象类型,,对象名,]
TO ,用户,[，,用户,]...
[WITH GRANT OPTION];
PUBLIC与WITH GRANT OPTION:PUBLIC参数可以将权限授给所有用户;后者使获得授权的用户还可以将此权限授给其它用户。
例如，将对供应商S、零件P及项目J的所有操作权限授给用户User1及User2。
GRANT ALL PRIVILEGES ON TABLE S, P, J TO User1,User2;
将S的插入权限授组User1，并允许将此权限授给其他用户。
GRANT INSERT ON TABLE S TO User1 WITH GRANT OPTION;
DBA把数据库SPJ中建立表的权限授给用户User1。
GRANT CREATETAB ON DATABASE SPJ TO User1;
收回授权语句格式:
REVOKE <权限>[,<权限>]...
[ON <对象类型><对象名>]
FROM <用户>[,<用户>]...;
例如， REVOKE ALL PRIVILEGES ON TABLE S , P, J FROM User1,User2;
REVOKE INSERT ON TABLE S FROM User1 WITH GRANT OPTION;
REVOKE SELECT ON TABLES S FROM PUBLIC;
REVOKE UPDATE(Sno) ON TABLE S FROM User1; ,,将权限的控制定位在某一个属性上
6、触发器，触发器是一种特殊类型的存储过程，它是通过事件触发而执行的。主要特点是，当被声明的事件发生时触发器被激活;触发器激活后不会立即执行，而是先测试触发条件;如果触发条件满足，则由DBMs执行与该触发器相连的动作。
创建触发器，不同数据库使用的触发器语法不同。
例:假定银行数据库关系模式为: Account(Account-no, branch-name,balance)
Loan(Loan-no, branch-name, amount)
depositor(customer-name, Account-no)
假定银行在处理透支时，不是将账户余额设成负值，而是将账户余额设置为零，并且建立一笔贷款，其金额为透支金额。这笔贷款的贷款号应该等该透支帐户的账户号。采用SQL,99标准创建触发器如下:
CREATE TRIGGER overdraft_trigger after update on Account
Refferencing new row as nrow
For each row
When nrow.balance<0
Begain atomic
Insert into borrower
(SELECT customer-name, Account-no
FROM depositor
Where nrow.account-no=depositor.account-no);
Insert into values
(nrow.account-no, nrow.branch-name, nrow.balance);
update account set balance=0
Where account.account-no=nrow.account-no
End
When nrow.balance<0是触发条件;
Begin atomic ... End子句用来将多行SQL语句集成为一个复合语句。其中前两条Insert into语句表示在borrower和loan关系中建立新的贷款业务，update语句用来将账户余额清零。
Referencing old row as 子句建立一个变量，用来存储已经被更新或删除的行的旧值。Referencing new row as 可以被update和Insert语句使用，可以存放经过更新的新值。
Referencing old table as 或Referencing new table as 子句可以用来指向临时表，使之容纳所有被影响的行。临时表不能使用before触发器，但可以用after触发器。
触发器在事件之前被激发，可以避免非法更新。
例9.45:仓库管理数据库中有如下关系，
inventory(item, level)，表示仓库中某种商品的现有量。
minlevel(item, level)，表示仓库中存有某种商品的量小量。
reorder(item, amount)，表示某种商品小于最小量时要订购的数量。
orders(item, amount)，表示定购某种商品的量。
CREATE TRIGGER reorder_trigger after update of amount on inventory --我怀疑amount应该是level
Referencing old row as orow, new row as nrow
For each row
When nrow.level <= (SELECT level
FROM minlevel
Where minlevel.item = orow.item)
And orow.level > (SELECT level
FROM minlevel
Where minlevel.item = orow.item)
Begin
Insert into orders
(SELECT item, amount
FROM reorder
Where reorder.item = orow.item)
End
删除触发器: DROP TRIGGER {trigger}[,...,n]
10.系统开发与运行
1、软件工程知识
软件工程是指应用计算机科学、数学及管理科学等原理，以工程化的原则和方法来解决软件问题的工程。其目的是提高软件生产率，提高软件质量，降低软件成本。
在经历60年代的软件开发危机后，人们开展了软件开发模型、开发方法、工具与环境的研究，提出了瀑布模型、深化模型、螺旋模型和喷泉模型等开发模型，出现了面向数据流方法、面向数据结构的方法和面向对象方法等开发方法，以及一批计算机辅助的软件工程工具和环境。
2、软件生存周期:可以分为6个阶段。计划制定、需求分析、设计、编码、测试、运行维护。
计划制定: 确定待开发软件系统的总目标，对其进行可行性分析，并对资源分配，合理安排进度计划。
参加人员有，用户、项目负责人和系统分析员。
该阶段产生的文档有，可行性分析报告和项目计划书。
需求分析: 确定系统功能、性能、数据及界面等要求，从而确定系统的逻辑模型。
参加人员有，用户、项目负责人和系统分析员。
产生的文档有，需求规格说明书。
软件设计: 分为概要设计和详细设计。
概要设计参加人员为，系统分析员和高级程序员;详细设计参加人员有，高级程序员和程序员。
该阶段产生的文档有，设计规格说明书(可以分为概要设计说明书和详细设计说明书)。
编码: 产生的文档为源程序清单。
测试: 文档为测试计划和测试报告。
运行及维护
3、软件开发项目管理基础知识
成本管理:有两种方法。 开发费用 , 人月数 , 每个人月的代价
开发费用 , 源代码行数 , 每行平均费用
风险分析:涉及3个概念，一是关心未来，第二是关系变化，第三是要解决选择问题。风险分析实际包括4个活动:风险识别、风险预测、风险评估和风险控制。
进度管理:有两种安排方式，一是交付日期已确定，另一个是仅确定了大致的日期，最终交付日期由开发部门确定。常用两种图形描述方法。
Gantt甘特图，横轴表示时间，纵轴表示任务，水平线表示任务的进度安排。它可以很好的描述任务间的并行性，但不能反映任务间的依 赖关系，不能确定整个项目的关键;
PERT图， 是一个有向图，图中的箭头表示任务，图中的结点称为事件，表示流入结点的任务的结点和流出结点的任务的开始。仅当流入结点的任务都结束时，该事件才出现，流出结点的任务才能开始。每个任务有一个松驰时间。为了表示任务间的关系，图中还可以加入一些空任务(虚线表示)。一个事件有事件号、出现该事件的最早时刻、最迟时刻。松驰事件为0的任务构成了关键路径。PERT图不能反映任务的并行性。
人员管理:主程序员组、无主程序员组、层次式程序员组。
4、软件开发方法:主要掌握3种方法，分别是结构化方法、面向对象方法和原型法。
结构化方法:是目前最成熟的开发方法之一，分为结构化分析和结构化设计。
面向对象方法:从现实世界中客观存在的事物出发来构造软件系统。软件系统适用的业务范围称作软件的问题领域，把问题领域中事物的特征抽象地描述成类，由类建立的对象作为系统的基本构成单位，它们的内部属性与服务描述了客观存在的事物的静态和动态特征。对象类之间的继承关系、聚集关系、消息和关联反映了问题域中事物之间实际存在的各种关系。
原型法:在获得一组基本需求后，快速地加以实现，随着用户和开发人员对系统理解的加深而不断进行补充和细化，是一种动态定义技术。
5、软件开发环境:是指支持软件产品开发的软件系统，它由软件工具集和环境集成机制构成。环境集成机制为工具集成和软件开发、维护及管理提供统一的支持，通常包括数据集成、控制集成和界面集成。有几个特征，环境的服务是集成的;环境的服务可用于各种软件开发活动;环境应支持小组工作方式。
6、ISO/IEC9126软件质量模型
由3个层次组成，分别是:质量特性,,质量子特性,,量度指标。
质量特性(质量子特性):
功能性(适合性、准确性、互用性、依从性、安全性)
可靠性(成熟性、容错性、易恢复性)
易使用性(易理解性、易学性、易操作性)
效率 (时间特性、资源特性)
可维护性(易分析性、易改变性、稳定性、易测试性)
可移值性(适应性、易安装性、一致性、易替换性)
MC Call软件质量模型，从软件产品的运行、修正和转移3个方面确定了11个质量特性。
产品运行(正确性、可靠性、易使用性、效率、完整性)
产品修正(可维护性、灵活性、可测试性)
产品转移(可移值性、复用性、互用性)
7、软件质量保证:是指为提高软件质量而进行的有计划、有组织的活动。
软件质量保证包括的7个主要活动相关的任务:应用技术方法、进行正式的技术评审、软件测试、标准的实施、控制变量、量度、记录保存和报告。
8、软件过程能力评估
软件产品的质量取决于软件开发过程。
软件过程评估，是软件改进和软件能力评价的前提。
软件过程评估的意义:是软件过程改进的需要。软件过程不断改进是软件工程的基本原理之一;软件过程改进是软件生存周期的基本过程之一。
是降低软件风险的需要。
软件能力成熟度模型CMM:是对软件组织进化阶段的描述。分为5个成熟度级别，初始级,可重复级,已定义级,已管理级,优化级。比较有名的一个基于CMM模型的产品是成熟度调查表，可以用于一个机构软件过程实力、弱点和风险。
8、系统分析的目的和任务:对现行系统做进一步的详细调查，将调查所得到的文档资料集中，对组织内部整体管理善和信息处理过程进行分析，为系统开发提供所需资料，并提交系统方案说明书。
系统分析的主要步骤是:由现实系统得出物理模型,,抽象出逻辑模型,,优化出新的逻辑模型,,逻辑模型具体化，得到新系统的物理模型。最终编写系统方案说明书。
9、结构化分析方法:采用“自顶向下、逐层分解”的开发策略。
数据流程图DFD:在逻辑上描述系统的功能、输入、输出和数据存储。DFD的基本成分有，数据流、加工、数据存储、外部实体。它们各有特定的图形表示。
分层数据流图的画法: 1)画系统的输入和输出; ,,称为顶层图
2)画系统的内部，将顶层图的加工分解成若干个加工，并用数据流连接; ,,称为0层图
确定加工的方法:在数据流的组成或值发生变化的地方应画一个加工;也可根据系统功能确定加工。
确定数据流方法:用户把若干个数据看作一个单位来处理时，可把这些数据看成是一个数据流。
3)画加工的内部;
4)重复第3步的分解过程至所有的加工都足够简单。
对图和加工进行编号: 顶图不必编号;
0层图只有一张，图中的加工号可以是0.1, 0.2, ...或是1, 2, ..
子图号就是父图中被分解的加工号
子图中的加工号同样由图号、圆点和序号组成
注意分析教材513页的实例:某考务处理系统有如下功能:对考生送来的报名单进行检查;
对合格的报名单进行检查;
对阅卷站送来的成绩清单进行检查，并根据考试中心指定的合格标准审定合格者;
制作考生通知单送给考生;
生成各种报表。
画图中应注意的问题:适当地为数据流、加工、数据存储及外部实体命名;
画数据流而不是控制流;
一个加工的输出数据流不应与输入数据流同名;
允许一个加工有多条数据流流向另一个加工，也允许一个加工有两个相同的输出数据流流向两个不同的加工;
保持父图与子图平衡;
在自顶而下的分析过程中，如果一个数据存储首次出现时只与一个加工有关，那么可以把它作为内部文件而不必画出
保持数据守恒，即一个加工的输出数据流中的数据必须直接从该加工的输入数据流中获得或产生;
每个加工都必须有输入、输出数据流;
在整套数据流图中，每个数据存储都必须有读的数据流和写的数据流。
数据词典DD:就是为数据流图中的每个数据流、文件、加工，以及更细节的数据项做出说明。其中对加工的说明称为“小说明”或“加工逻辑说明”。常用的加工逻辑说明方法有3种:结构化语言、判定表和判定树。结构化语言分为内外两层，外层有严格的语法，而内层语法灵活，接近于自然语言。
10、统一建模语言UML:它提供了9种基本元素的图形，分别是:类图、对象图、用例图、序列图、协作图、状态图(活动图、构件图、部署图)。
UML由3个要素构成:UML的基本构造块、支配这些构造块如何放置在一起的规则、运用于整个语言的一些公共机制。
在UML提供的图中，可以采用类图，对逻辑数据库模式建模;状态图，用于接口、类和协作的行为建模，并强调对象行为的事件顺序;活动图，用于系统的功能建模，并具强调对象间的控制流。
11、系统分析报告:数据流图、数据字典和加工说明应该成为系统分析报告的主体。并且一份完整的系统分析报告应该包括如下内容。
组织情况概述
现行系统概述
系统逻辑模型
新系统在各个业务处理环节拟采用的管理方法、算法或模型
与新系统相配套的
管理制度
档案管理制度下载食品安全管理制度下载三类维修管理制度下载财务管理制度免费下载安全设施管理制度下载
和运行体制的建立
系统设计和实施的初步计划
用户领导审批意见
12、系统设计的目的和任务:主要目的是为系统制定蓝图，在各种技术和实施方法中权衡利弊，精心设计，合理使用种种资源，最终形成系统的详细设计方案。
系统设计的任务分为两个步骤:首选是把总任务分解为许多基本的、具体的任务。合理地组织这些具体任务可以构成总任务，称为总体结构设计，也称为概要结构设计; 其次是为各个具体任务选择适当的技术手段和处理方法，即详细设计。
系统总体结构设计原则:分解,协调原则
自顶而下原则
信息隐蔽、抽象原则
一致性原则
明确性原则
模块间耦合尽可能小，模块内组合尽可能紧凑
模块的扇入系数和扇出系数要合理
模块的规模要适当
模块化设计: 模块是组成系统的基本单位，应该具备4个元素，分别是，输入和输出、处理功能、内部数据、程序代码。
模块结构图， 是采用HIPO图(分层输入,处理,输出)形式绘制而成的框图。它主要关心模块的外部属性，即上下级模块、同级模块之间的数据传递和调用关系。它主要由5种基本符号表示:模块、调用、数据、控制和转接。
存储设计:首先要解决数据的整体结构设计，然后要确定数据资源分布和安全保密属性。
13、系统详细设计
代码设计
输出设计 ,,确定输出内容、选择输出设备与介质、确定输出格式
输入设计 ,,输入原则:最小量、简单性、早检验、少转换
处理过程设计 ,,总体结构设计将系统分解成许多模块，并决定每个模块的外部特征，即功能和界面。计算机处理过程的设计则是要确定每个模块的内部特征，包括局部的数据组织、控制流、每一步的具体加工要求及实施细节等。
处理过程的关键是，用一种合适的表达方法来描述每个模块的执行过程。常用的描述方式有图形、语言和表格3类。例如，程序流图、盒图NS、形式语言、决策树、决策表。盒图就是用一个盒子表示一个步骤，可以嵌套，只能从上头进入下头输出，因此限制了控制转移，保证了程序的良好结构。
用户界面设计 ,,包括菜单方式、会话方式、操作提示以及操作权限管理方式等。权限管理一般是通过入网口令和建网时定义该节点级别来实现的。
安全控制设计 ,,包括数据处理和环境两方面
系统设计说明书
一份完整的系统设计说明书应包括:
1)引言
背景,,摘要,,工作条件/限制,,参考和引用资料,,专门术语定义
2)系统总体设计方案
模块设计,,代码设计,,输入设计,,输出设计,,数据库设计说明,,模型库及方法库设计,,网络设计,,安全保密设计,,实施方案说明书。
从系统调查、系统分析到系统设计是信息系统开发的主要工作，它们的工作量应占到总开发量的70%。
14、系统实施的任务: 按总体设计方案购置和安装计算机网络系统;
软件准备,,其中编写程序是一个重要任务;
人力培训;
数据准备;
试运行。
程序设计:主要依据是系统设计阶段的HIPO图、数据库结构和编码设计。
结构化程序设计方法:适用于某些过程不规范、模块划分不细或有特殊业务处理需要模块程序量较大时。主要强调3点规则:模块内部程序各部分要按自顶向下的结构划分;各程序部分应按功能组合;各程序间联系尽量使用调用子程序实现。
快速原型式方法:首先将HIPO图中具有普遍性的功能模块集中实现，构造系统原型，再对一些特定的功能和模块进行补充。
面向对象的程序设计方法:OOD,
15、软件测试方法:分为人工测试和机器测试。
人工测试，又称为代码审查。
机器测试，分为黑盒测试、白盒测试。
黑盒测试,,也称为功能测试，主要测试软件的外部特性。
白盒测试,,也称为结构测试，根据程序内部结构、逻辑，以程序的路径和过程进行测试。
软件测试步骤:可以分为4步，如下
1)单元测试，即模块测试
2)组装测试，即集成测试。又分为非增量式集成和增量式集成。前者可以对模块进行并行测试，后者使测试更彻底。
3)确认测试，进一步检查软件的功能和性能是否与用户要求的一致。以系统方案说明书为基础，检查软件有效性。
确认测试首先要进行有效性测试以及软件配置审查，然后进行验收测试和安装测试，最后经各部门认可后交付使用。
4)系统测试，将已经确认的软件、硬件、外设及网络结合起来，进行系统的各种组装测试和确定测试。
调试:试探法、回溯法、对分查找法、归纳法、演绎法。
16、系统转换
实际运行，是对系统最好的检验和测试方法。这个阶段的工作有:
对系统进行初始化、输入各原始数据记录;
记录系统运行数据和状况;
核对新、老系统的输出结果;
考察输入方式(方便、效率、误操作)
测试响应速度
系统转换方式:直接转换、并行转换、分段转换。
17、系统维护，系统的可维护性可以定义性的定义为维护人员理解、改正、改动和改进这个软件的难易程序。
系统可维护性的评价指标:可理解性、可测试性、可修改性。
文档，是软件可维护性的决定因素。
系统维护主要包括硬件设备的维护、应用软件的维护和数据的维护。
18、系统评价，分为广义和狭义两种。广义的评价是指从系统开发的开始到结束的每一阶段都需要进行评价。狭义的评价是指在系统建成并投入运行之后进行的全面和综合的评价。
从总体上可以将广义评价分为立项评价、中期评价、结项评价。
19、系统运行管理
运行管理制度:包括种类机房安全运行管理制度，和信息系统的其他管理制度。
日常运行管理内容:包括系统运行情况记录、审讯追踪、审查应急措施落实、系统资源管理、软件及文档管理
11.数据库设计
1、数据库设计概述:数据库设计属于系统设计的范畴。参照软件工程对生命周期的定义，也把数据库设计分为6个步骤:数据库规划、需求收集分析、数据库设计与应用程序设计、实现、测试、运行与维护。
数据库设计:数据库的设计是对用户数据的组织和存储设计;应用程序的设计是在数据库设计的基础上对数据操作及业务实现的设计，包括事务设计和用户界面设计。
实现:依照设计使用DBMS支持的DDL语言实现数据库的定义，用高级程序语言编写应用程序。
2、系统需求分析，是用户和设计人员对数据库应用系统所涉及的内容和功能的理解和描述。
用户对系统的需求包括:数据需求、围绕这些数据的业务处理需求、数据安全性需求、数据完整性需求。
需求分析阶段是以调查和分析为主要手段的，以此获得用户对系统的信息要求和处理要求。
需求分析阶段要完成的主要工作是建立数据字典和数据流图。
需求分析的方法和步骤:使用数据字典描述用户的信息要求，使用数据流图描述业务处理过程。
数据字典包括，数据项、数据结构、数据流、数据存储、处理过程。
数据项:是数据的最小单位，一般包括项名、含义和说明、别名、类型、长度、取值范围及该项与其它项的逻辑关系。如采购单号;
数据结构:是若干有意义的数据项的集合，包括数据结构名、含义和组成成分。如采购单;
数据流:既可以是数据项也可以是数据结构，它表示某一次处理的输入输出数据，包括数据流名、说明、数据来源和去向及需要的数据项和数据结构。如采购计划数据流;
数据存储:加工中需要存储的数据，包括数据存储名、说明、输入数据流、输出数据流、组成成分、数据量、存取方式以及存取频度等。如原材料的价目表，在计算成本和支付采购费用的处理过程中要用到这些数据;
处理过程:是加工处理过程的定义和说明，包括处理名称、输入数据、输出数据、数据存储及响应时间等，如采购支付处理。
,,,,,,,,,,,,,,,,,,,,,,,,
处理过程名: 采购支付
说明: 根据采购单、原材料价目表，计算出应付原材料采购费用
输入数据: 采购单
数据存储: 原材料价目表
输出数据: 支付费用表
,,,,,,,,,,,,,,,,,,,,,,,,
3、概念结构设计，是在需求分析的基础上，对用户信息加以分类、聚集和概括，建立信息模型，并依照选定的数据库
管理系统软件把它们转换为数据的逻辑结构，再依照软硬件环境，最终实现数据的合理存储。这一过程被称为“数据建模”。
数据建模的过程，可以分为3个阶段:概念结构设计、逻辑结构设计、物理结构设计。
概念结构设计的策略有4种:自顶而下、自底而上、逐步扩张、混合策略。
概念结构设计最常用的方法是1976年由一位华人学者提出的E,R方法。将现实世界的信息结构统一由实体、属性及实体之间的联系来描述。
使用E,R方法时，需要对现实事物抽象并以E,R图的形式描述出来，有3种抽象的方法:
分类， 将现实世界中具有共同特征和行为的事物定义为一种类型。个体与类型关系是is member of
聚集， 定义某一类型所具有的属性。各个属性是所属类型的一个成分，is part of
概括， 由一种已知类型定义新的类型。已知类称为超类，新定义类称为子类，关系为is subset of
4、用E,R方法建立概念模型
步骤:选择局部应用;逐一设计分E,R图;E,R图合并。
注意属性与实体的区别:属性不可再分;属性不能与其它实体发生联系。
分E,R图的合并方法就是将具有相同实体的两个或多个E,R图合而为一。合并过程中可能会发生的冲突有:属性冲突、命名冲突、结构冲突。
对合并后的E,R进行优化的方法有3个:
1)实体类型的合并， 凡具有1:1或1:n联系的实体都可以合并，减少实体个数;
2)冗余属性的消除;
3)冗余联系的消除， 合并后的E,R图中可能会出现实体联系的环状结构，消除直接联系，保留间接联系。
5、逻辑结构设计，是在概念结构设计基础上进行的数据模型设计，可以是层次、网状和关系模型。逻辑结构设计的主要任务是:
确定数据模型;
将E,R图转换为指定的数据模型;
确定完整性约束;
确定用户视图。
6、E,R图向关系模式的转换:
1)实体向关系模式的转换
将E,R图中的实体逐一转换为一个关系模式，其中实体名对应关系模式的名称，实体的属性转换成关系的属性，实体标识符就是关系的码。
2)联系向关系模式的转换
一对一联系的转换:有2种方式。
一种方式，是将联系转换成一个独立的关系模式，关系模式的名称取联系的名称，关系的属性包括该联系所关联的两个实体的码和联系的属性，关系的码可以取自任一方实体的码;
另一种方式，是将联系归并到关联的两个实体的任一方，在一方实体属性集中增加另一方实体的码和该联系的属性，归并后的实体码保持不变。
一对多联系的转换:有2种方式。
第一种方式，是将联系转换成一个独立的关系，关系的名称取联系的名称，关系的属性包括该联系所关联的两个实体的码和联系的属性，关系的码是多方实体的码;
第二种方式，是将联系归并到关联的两个实体的多方，在待归并的多方实体属性集中增加一方实体的码和该联系
的属性，归并后的多方实体的码保持不变。
多对多联系的转换:只有1种方式。
那就是将该联系转换成一个独立的关系，关系的名称取联系的名称，关系的属性包括该联系所关联的两个多方实体的码及该联系的属性，关系的码是两个多方实体的码构成的属性组。
7、关系模式的规范化
由E,R图转换得来的初始关系模式可能会有数据冗余或更新异常，需要进一步得进行规范化处理:
1)根据语义确定各关系的数据依赖;
2)根据数据依赖确定关系的范式;
3)对不合要求的范式进行分解，达到3NF、BCNF或4NF;
4)对关系进行评价和修正。因为最规范的关系不一定是最合适的关系。
关系的完整性约束有:主码约束、检查约束、参照性约束
8、数据库的物理设计
物理设计一般应做这些工作:
确定数据分布;
确定存储结构;
确定存取方式。
存储结构是指数据文件中记录之间的物理结构，可以是顺序存储、哈希存储、堆存储或B，树存储等。要根据数据的处理要求和变更频度，选定合理的物理结构。
为提高数据的访问速度，会采用索引技术。同样也要根据数据处理和修改要求，选择恰当的索引字段和类型。
数据的存取方式，是由其存储结构决定了的。
9、数据系统的实现，是根据设计，由开发人员编写代码程序来完成的，包括数据库的操作程序和应用程序。
数据库的操作程序使用SQL语言实现，主要有:DDL、DML、事务处理程序、存储过程、触发器。
嵌入式SQL因为其复杂性，已逐惭被ODBC、ADO接口技术取代。
10、数据库系统的实施方法:
建立实际的数据库结构(DDL)
装载测试数据试运行
装载数据，即卸载实验数据，加载用户数据，正式运行。
11、数据库的保护，是通过数据库的恢复、安全性控制、完整性控制、并发控制，来实现的。
事务，是数据库处理的基本逻辑单位，事物的原子性、一致性、隔离性和持久性(简称ACID)保证了数据更新的正确性。面向数据更新的应用程序的编写，必须以事务为单位进行数据的操作。
数据库的备份与恢复:
数据备份与日志备份是数据库恢复技术的主要依据。数据备份又称为数据转储，分为静态和动态两种方式。日志备份用来记录对数据库系统的更新操作，写日志的次序严格按照并发事务执行的时间次序，必须先写日志后写数据库。
数据库系统中的故障类型:事务故障、系统故障、介质故障。
恢复策略:有2种操作，分别是撤销事务(UNDO)和重做事务。
事务故障的恢复:可以UNDO产生故障的事务，回到该事务执行前的正确状态;
系统故障的恢复:系统故障会导致数据库不一致，恢复方法是先UNDO未完成的事务，再REDO已提交的事务;
介质故障的恢复:需要DBA参与，重装数据库、装入数据库的备份和日志文件的副本，再由系统完成UNDO、REDO操作。
数据库的安全性，是保证数据库不被非法用户访问和破坏的机制。包括:权限机制(GRANT)、视图机制、数据加密。数据加密可以防止数据在存储和传输过程中失密。
数据库的完整性，是保证数据库不被合法用户的错误操作而破坏。完整性是指数据的正确性和相容性。
数据库的并发控制:
1)并发操作，可能会带来数据的不一致性有3种，丢失修改、不可重复读和读脏数据。
2)加锁:控制的手段就是加锁。排他锁(写锁X)和共享锁(读锁S)。X锁将独占数据，数据上有S锁时事务只能加S锁读而不能加X锁写。
3)封锁协议:
一级封锁协议，事务T在修改数据A前必须先对A加X锁，直到事务结束才能释放X锁。这样解决了丢失修改的问题;
二级封锁协议，在一级封锁协议基础上，事务T在读数据A前必须对其加上S锁，读完即释放S锁。这样使得一个事务不能读取其他事物修改中的数据，解决了读脏数据问题;
三级封锁协议，在一级封锁协议基础上，事务T在读数据A前必须对其加上S锁，直到事务T结束才释放S锁。这样使得一个事务在读取数据期间，其他事务只能读取该数据而不能修改，所以解决了不可重复读的问题;
两段锁协议，对任何数据进行读写前都必须加锁，在释放一个封锁后，事务不再申请和获得任何其它封锁。这样可以缩短持锁时间，提高并发性，同时解决了数据的不一致性。
12.数据库运行与管理
1、数据库系统的运行策略: 从物理环境上保障系统的稳定运行;
从对人员的要求上做保障;
应用数据库的安全性策略;
做好数据库的备份与恢复工作。
2、数据库系统的监控对象和监控方式
监控对象有3个，性能监控、故障监控、安全监控。
监控方式有2种，系统监控和应用程序监控。
3、数据库维护
因为某些原因需要修改数据库的结构，称为数据重构，包括表结构的修改和视图的修改。
视图机制一方面可以实现数据的逻辑独立性，另一方面可以实现数据的安全性。
文档是对系统结构和实现的描述，必须与系统保持调度的一致性。数据库重构过程中的所有修改必须在文档中体现出来。
4、数据库系统的运行统计
系统监控和运行统计是DBA掌握数据库系统运行状态最有效的手段。系统监控用来保障系统的稳定运行，系统统计则用来了解系统性能，作为性能调整的依据。
5、数据库系统的审计，是一种DBMS工具，它记录数据库资源和权限的使用情况。审计是被动的。
6、数据库系统的管理
(1)数据字典的管理:数据字典是存储在数据库中的所有对象信息的知识库，其中存储的数据称为元数据。数据字典是只读的。
(2)数据完整性维护和管理:作用对象有列、行、表3种。列级约束、主码约束和参照完整性约束是在数据库定义过程中定义的，存在数据字典中。更为复杂的约束可以编写触发器程序实现。
因此，由DBMS管理的约束，可通过修改数据库定义完成维护和管理;
由应用程序实现的复杂的完整性约束，要通过分析修改程序(触发器程序)来实现。
(3)数据库的存储管理:数据库中的数据是以文件形式存储在物理存储设备上的，程序通过DBMS完成I/O操作来访问数据。提高系统访问效率的有效手段就是提高I/O操作的效率。使用这样几种手段管理数据的存储，可以有效地提高性能:
1)索引文件和数据文件分开存储，事务日志文件存储在高速设备上;
2)适时修改数据文件和索引文件的页面大小;
3)定期对数据进行排序;
4)增加必要的索引项。
也可以增加计算机内存，引入调整存储设备等外部方式提高系统的访问效率。
(4)数据库备份与恢复的管理:
设定合理的备份周期和备份时间;
把事务日志文件保存在最稳定的存储设备上;
定期在事务日志文件中加入检查点(checkpoint)，检查点记录数据库的正确状态点。在数据库恢复过程中，可以反向扫描日志文件找到第一个检查点，执行UNDO、REDO操作。
(5)数据库的并发控制与死锁管理:多用户数据库DBMS都提供并发控制机制。在实际运行过程中，死锁的产生多是因为事务程序的错误引起。管理员需要使用系统监控工具和系统日志，找出频繁产生死锁的事务。分析原因，修改事务程序，减少死锁。
(6)数据库的安全管理:
建立网络安全(防火墙)
操作系统级安全(登录用户管理)
DBMS级安全(访问DB的用户验证密码)
角色和用户授权管理
使用视图和存储过程
使用审计功能
7、数据库系统的性能调整
1)SQL语句的编码检验:通过DBMS提供的监控和统计功能，找出频繁执行的SQL语句并对其进行优化。步骤为，
(1)尽可能地减少多表查询或建立物化视图;
(2)以不相关子查询代替相关子查询;
(3)只检索需要的列;
(4)用带IN的条件子句等价替换OR子句;
(5)经常提交COMMIT，以尽早释放锁。
2)表设计的评价:首先要求关系都能符合3NF或BCNF，然后还要根据实际运行情况对表进行调整。
调整的原则是: 如果频繁地访问涉及的是对两个相关表进行连接操作，则将这两个表合并;
如果频繁地访问只是在表中的一部分字段上进行，则考虑分解表或将该部分单独拿出作为一个表;
对于很少更新的表，引入物化视图。
3)索引的改进:索引的调整原则如下，
如果查询是瓶颈,,在关系上新建适当的索引，通常在作为查询条件的属性上建立索引可以提高查询效率;
如果更新是瓶颈,,因为每次更新都会重建表上的索引，引起效率的降低，可以考虑删除某些索引;
选择适当的索引类型,,比如经常使用范围查询，可以使用B树索引，比散列索引更高效;
将有利于大多数据查询和更新的索引设为聚簇索引。
4)设备的增强:高速的计算机、增加内存、高速网络设备、高速存储设备。
13.网络与数据库
1、分布式数据库的目标: 一是，借助网络把分散在不同地域的数据管理起来;
另一是，各个地域的数据库系统仍能支持本地应用。
分布式数据的定义: 分布性;逻辑相关性;场地透明性;场地自治性。全部满足这些条件的数据库系统称为完全分布式数据库系统。
分布式数据库的特点:
1)数据的集中控制性;
2)数据独立性;
3)数据冗余可控性;
4)场地自治性;
5)存取的有效性,,分布式数据库系统中的查询优化有两个级别。一个是全局优化，决定在多个副本中选取合适的场地副本，使得场地间的数据传输量及次数最少，从而减少系统通信开销;另一个是局部优化，这与传统的集中式数据库中的优化是相同的。
上面的这些特点中，前3点都是数据库系统优于文件系统的方面，并且除第4点以外，传统数据库也应该具有这些特点。
2、分布式数据库的体系结构
(A)分布式数据库系统的模式结构:目前国际上还没有统一的标准。国内提出的4层模式结构如下:全局外层、全局概念层、局部概念层、局部内层。
1)全局外层 ,,分布式数据库的全局视图是针对分布式数据库特定的全局用户，是对分布式数据库的最高层的抽象。
2)全局概念层,,是分布式数据库的整体抽象，但比集中式的概念层有更多的描述。全局概念层有3种模式描述信息，全局概念模式、分片模式、分配模式。
(1)全局概念模式:描述分布式数据库全局数据的逻辑结构;
(2)分片模式:描述全局数据逻辑划分的视图，每一个逻辑划分就是一个分片;
(3)分配模式:是分片后的物理分配视图。
因此分布式数据库的定义语言除了需要提供概念模式的定义语句外，还要提供分片模式和分配模式的定义语句。全局概念模式到分片模式的映射是一对多的;分片模式到分配模式的映射是一对多的或一对一的，这要由数据分布的冗余策略决定。作为GDBA，将负责全局数据结构的定义、逻辑分布的定义和物理分布的定义。
3)局部概念层,,该层由局部概念模式描述，全局概念模式经逻辑划分后被分配在各局部场地上。
4)局部内层 ,,相当于集中式数据库的内层。
4层结构的全局数据库和局部数据库分离、数据独立性、透明性、数据冗余控制都体现了分布式数据库的特点。
(B)数据分布:数据的划分和放置是数据分布问题的两个重要方面。有几种处理策略，集中式、分割式、复制式
和混合式。
(C)数据分片:也称数据分割。对于关系数据库，数据分片有3种方法，水平分片(元组)、垂直分片(属性)、混合分片(水平和垂直)。水平划分元组为若干不相交的子集，可以通过合并操作恢复全局关系。垂直划分关系的属性为若干子集，要求所有属性都要被划分且每一垂直片都包含该全局关键字，可以通过连接操作恢复该全局关系。
数据分片要遵守的原则为:完备性条件;可重构条件;不相交条件(关键字除外)。
D)分布透明性:也称为分布独立性，由高到低分成了3个级别，分片透明性,,分配透明性,,局部数据模型 (
透明性。
局部数据模型透明性，也称为局部映像透明性，是透明性的最底层，在4层模式中处理分配模式和局部概念模式之间。全局数据模型与每个节点上局部数据库的数据模型的转换是由分配模式与局部概念模式之间的映像实现的。当某个节点上的数据库的数据模型改变时，只要改变分配模式到该节点局部概念模式之间的映像即可，应用程序不受影响，从而实现了局部数据模型透明性。
(E)分布式数据库管理系统DDBMS:有两大类，综合型和联合型。前者是新建的一个分布式数据库，后者是整合已经存在的多个节点的数据而形成。联合型又可以分为同构型和异构型。
分布式数据库管理系统由4部分组成:LDBMS、GDBMS、GDD(全局数据字典)、CM(通信管理)。
一个完全的分布式管理系统要符合12条规则:场地自治性;非集中式管理;高可用性;位置独立性;数据分割独立性;数据复制独立性;分布式查询;分布式事务管理;硬件独立性;操作系统独立性;网络独立性;数据库管理系统独立性。
注意理解分布式数据库系统结构模式图，和分布式数据库管理系统结构图。
3、分布式查询处理和查询优化
与集中式数据库环境中的查询相比，分布式数据库环境中的查询还要考虑到:数据、信息传输的延迟问题;网络中存在多处理器时的并行数据处理机会。这两点都会影响到查询的速度。
查询优化器，在分布式数据库系统中它的任务是控制和加快查询的执行与数据传输的过程。在分布式查询处理技术中，查询优化的基本类型通常包括2类:针对查询执行代价的优化，和针对查询响应时间的优化。
查询执行代价优化的目标是，使查询执行所使用的系统资源尽量少(最便宜);
查询响应时间优化的目标是，尽量减少响应时间而不计较系统资源的消耗(最快)。
4、分布事务管理
1)分布式事务:在分布式数据库系统中，一个分布式事务是由若干个不同站点上的子事务组成的。
2)分布式事务与集中式事务的相同特性:与集中式事务的特性相同为ACID，原子性、一致性、隔离性和持久性。
分布式事务与集中式事务的不同特性:执行特性、操作特性和控制报文。执行过程中，分布式事务要必须创建一个控制进程，协调子事务、数据及控制报文;而集中式事务仅由并行调度算法进行调度即可。操作过程中，分布式事务还要加入大量的通信原语和控制原语。集中式事务没有使用控制报文。
3)分布式数据库故障:分为节点故障(事务故障、系统故障、介质故障)，通信故障(报文故障、网络分割故障)。其中报文故障包括报文错、报文丢失、报文延迟。
4)分布式数据库的恢复原则:保证事务原子性的措施称为事务故障恢复，有几个原则是，
孤立和逐步退出事务的原则UNDO;
成功结束事务原则REDO;
夭折事务的原则。(撤消全部事务，恢复到初态)
在分布式事务恢复中，本地事务的恢复和集中式事务的恢复相同，由本地事务管理器LTM执行。整个的分布式事务的恢复由LTM与DTM(分布式事务管理器)协同完成。
5)两阶段提交协议2PC(准备提交、建议提交/撤销、全局提交/撤销、确认)
在2PC中，将分布式事务的某一个代理指定为协调者，其它代理都是参与者。参与者可以进行单方面撤销。2PC可以分为两个步骤:先是表决阶段，然后是执行阶段。表决中实行一票否决。
2PC对故障的恢复:(1)场地故障 参与者在写入“建议提交”前发生故障 : ,,协调者等到超时后将取消事务，该参与者自行可以 终止事务。
参与者在写入“建议提交”后发生故障: ,,而其它参与者可以正常结束事务，该参与者 要访问协调者或其它参与者获得之前协调者作出 的决定并执行相应的操作。
协调者在写入“准备提交”后，在写入“全局提交/撤销”前发生故障:
,,协调者从头恢复提交协议
协调者在写入“全局提交/撤销”后，在写入“事务结束”记录前发生故障:
,,协调者恢复时要给所有的参与者重发之前的全局决定。
(2)报文丢失 丢失参与者的回答报文(建议提交/撤销): ,,协调者将取消整个事务
丢失“准备提交”报文: ,,协调者在超时后将取消整个事务
丢失“全局提交/撤销”报文: ,,涉案参与者将请求协调者重发该报文
丢失“确认”报文: ,,协调者将重发全局报文，参与者无论子事务 提交与否都要给予确认。
(3)网络分割故障，整个网络被分为2组，协调者组和参与者组。各自进行故障处理。
6)三阶段提交协议3PC(在2PC基础上增加了，全局预提交和准备就绪，两个报文，可以确认所有参与者的状态)
第一阶段，协调者向所有的参与者发“准备提交”报文，只有所有参与者都投票“建议提交”，才会进入第二阶段;
第二阶段，协调者向所有的参与者发“全局预提交”报文，只有所有参与者都投票“准备就绪”，才能进入第三阶段;
第三阶段，协调者向所有的参与者发“全局提交”报文。
3PC仅降低了阻塞发生的可能性，不是完全的非阻塞协议。
3PC对故障的恢复: 协调者发出的“准备提交”报文延迟，参与者超时而撤销子事务;
协调者等待参与者投票时超时，协调者将撤销事务;
参与者处于“赞成提交”状态，而等待全局预提交时超时，参与者将进入恢复处理过程;
参与者处于“准备就绪”状态，而等待全局提交时超时，参与者将进入恢复处理过程。
在3PC协议中，恢复处理过程惟一可以做的是就近访问一个参与者，依照协调者之前作出的决定安排自己的操作。
5、WEB数据库
WEB数据库由数据处理和资源共享这两种技术结合而成，也称为网络数据库。
WWW下的WEB数据库，RDB增加了DB的面向对象成分、增加各种中间件(CGI、ISAPI、ODBC、JDBC、ASP)，通过应用服务器解释执行各种HTML中嵌入的脚本，来解决Internet应用中数据库的显示、维护、输出及到HTML的格式转换。
WEB服务器的连接方案，有2套:服务器端方案(CGI、SAPI、ASP、PHP、JSP)和客户端方案(JDBC、DHTML)。
连接数据库的常用方法有:ODBC、DAO、RDO、ADO。ADO是DAO、RDO的简化合集。
6、应用开发平台ASP、PHP、JSP
ASP，ASP服务器被含在了IIS服务器中，ASP中使用的是VBscript，ASP安装配置简单、易学易用。ASP缺点是使用了组件带来了安全性问题，另外ASP不能跨平台使用。
PHP，简单易学，可以跨平台，具有良好的数据库交换能力，与Apache紧密结合，安全性好。缺点是安装配置复杂，并且缺少企业级的支持。
JSP，可移值性好，可以跨平台，伸缩性强大，多样化并有强大的工具支持。缺点是安装配置管理都较复杂，只适用于大型系统。
7、关于CGI(Common Gateway Interface)
是最早出现的动态网页发布技术。通过CGI接口，服务器可以向CGI程序发送信息，CGI程序也可以向服务器发送信息。可以使用任何可形成可执行程序的程序语言编写CGI程序，如C Shell、Perl、C、C，，、FROTRAN和数据库语言。CGI支持ODBC方式。
8、关于ASP(Active Server Page)
ASP提供了一个在服务器端执行脚本指令的环境(包括VBscript,html,JavaScript等)，脚本可以嵌入HTML中，还可以通过ActiveX控件实现更加强大的功能。
ASP通过ADO对象模块来存取数据库，只要数据具有对应的ODBC或OLE DB驱动程序。ASP提供的ADO对象模块俾昼作夜了下列6个对象和3个集合。 Connection对象
Recordset对象
Fields集合
Field对象
Command对象,,返回值为Recordset对象
Parameter集合
Parameter对象
Error集合
Error对象
9、关于Servlet和JSP
Servlet是一个运行在WEB服务器中的Java程序。它从浏览器获取一个HTTP请求，动态生成内容，并把HTTP信息返回给浏览器。Servlet优点是运行在服务器端且可以更直接地访问数据库。
JSP技术通常与Java Servlet技术结合，可以在HTML或其它标记语言中嵌入Java代码段并且调用外部Java组件。JSP是一个前端的处理工具，可以使用JavaBean实现更为复杂的业务逻辑和动态功能。
JSP最大的优点是将网页的静态内容(HTML代码)和动态内容(Java代码)分隔处理，易于人员分工。
10、XML的应用
采用文件存储XML，会受到文件系统的一些限制(大小、迸发性、工具选择、版本、安全性、综合性)。
XML与数据库的数据转换:
文档的逆反回归不一致性，将数据存储到数据库时会丢失大量文档相关的信息。同样地，从数据库中检索数据并生成的XML文档，除非预定义的实体一，不包含任何字符数据和实体引用，并且同层元素和属性的出现顺序常常就是从数据库中返回数据的顺序。
XML与数据库之间传输数据，需要进行相互映射。有两种映射方式:模板驱动、模型驱动。
第十四章 数据库发展趋势与新技术
1、面向对象数据库系统应该具有以下特征:
表达和管理对象的能力;
具有任意复杂度的对象结构;
具有与面向对象编程语言交互的接口;
具有表达和管理数据库变化的能力。
2、面向对象数据模型
面向对象数据模型可以看作在一个更高层次上实现数据模型的新成员，并经常用作高层概念模型，尤其在软件工程领域中更是如此。
面向对象数据模型的基本概念有对象、类、继承、对象标识和对象嵌套。
对象结构:属性集合、方法集合、消息集合
对象类 :在面向对象数据库中，类是一系列相似对象的集合，对应于E,R模型中的实体集概念。类是面向对象系统和数据库系统之间最重要的连接。首先，类直接说明了一个实例及其所属类之间的实例关系;其次，类提供了构成查询的基础;另外，类可以用来增加面向对象数据库的语义完整性;最后，类提出了所有对象的属性和方法的规格说明，便于生成对象。
类的概念相似于关系，类的属性相拟于关系的属性，对象相似于关系中的一个元组。
继承与多重继承:在面向对象的数据模型中，所有类形成了一个有限的层次结构或者是一个有根的无环有向图，称之
为层次。
对象标识:每个对象惟一的、由系统生成的对象标识OID。几种常用的标识为，值、名称、内置名。对象标识要求必须具有永久持久性。根据实际应用的需求，大多面向对象数据库系统允许有对象和值两种标识表示方法共同使用。
对象嵌套:在面向对象数据模型中，对象的一个属性可以是一个单一值，也可以是一个来自值域的值集，即一个对象的属性可以是一个对象，形成了嵌套关系。
3、面向对象数据库语言:包括对象定义语言和对象操纵语言。对象查询语言是对象操纵语言的一个重要子集。
面向对象数据库语言应该具有这些功能:类的定义和操纵;
操作/方法的定义;
对象的操纵。
4、对象关系数据库系统
在今天的商业领域中，占统治地位的数据库管理系统产品有2个:关系数据库系统和面向对象数据库系统。另外还有两种主要的类型是层次数据库和网关数据库。
对象关系数据模型扩展关系数据模型的方式是提供一个包括复杂数据类型和面向对象的更丰富的类型系统。
(1)嵌套关系:元组在一个属性上取值可以是一个关系，于是关系可以存储在关系中，从而形成了关系的嵌套。这样，一个复杂的对象可以用嵌套关系的单个元组来表示。
(2)复杂类型:集合是集合体类型的一个实例，另外的集合体类型包括数组和多重集合。面向对象关系数据库允许属性是集合。
(3)继承、引用类型:SQL99仅支持单继承
(4)与复杂类型有关的查询: 路径表达式;(使用右向箭头符号，例如select head-->name,head-->address from
departments)
以集合体为值的属性;
嵌套与解除嵌套。(将一个嵌套关系转换为1NF的过程称为解嵌套，反向过程就是嵌套。嵌套可以通过SQL的分组扩展实现，即不使用聚集函数而只是返回多重集合)
(5)函数与过程:对象关系数据库系统中允许用户定义函数与过程，既可以用SQL来定义，也可以用外部的程序设计语言来定义。
(6)面向对象与对象关系:几种数据库系统的能力如下，
关系系统 ,,简单数据模型、功能强大的查询语言以及高保护性;
对象关系系统,,复杂数据模型、功能强大的查询语言以及高保护性;
以持久化程序设计语言为基础的面向对象系统,,复杂数据类型、与程序设计语言集成以及高性能。
5、ERP与数据库
ERP的形成经历了四个阶段:基本MRP阶段、闭环MRP阶段、MRP,2阶段以及ERP阶段。
基本MRP，在传统的库存理论中引入了时间分段和反映产品结构的物料清单，从而较好的解决了库存管理和生产控制中的难题。
闭环MRP，在基本MRP的基础上，加入了对能力的约束的考虑，如供货能力或运输能力，从而形成了信息回路，称为闭环MRP。
MRP,2，以生产计划为主线，统一计划和控制各种资源，使企业的物流、信息流、资金流都畅通，也实现了动态反馈。
ERP，它继承了MRP,2的基本思想，但是把管理重心转移到财务上来，在全过程中贯穿财务成本控制的概念。
6、ERP设计的总体思路
一个中心，两类业务，三条干线。即以“财务”为中心，处理“计划”和“执行”两类业务，围绕“供应链管理、生产管理、财务管理”这3条干线。
在ERP系统的设计过程中怎么样应用数据库技术:
1)先要绘制出业务处理流程图;
2)绘制出数据流程图;
3)绘制E,R图; ,,前3步都是在前一步的基础上发展深入，一步步为数据库设计打好基础。
4)绘制功能模块图。
7、决定支持系统
决策支持系统实质上是在管理信息系统的基础上发展起来的。它综合利用了各种数据、信息、知识，特别是模型技术，能够辅助各级决策者解决决策问题。决策支持系统的新特点就是增加了模型库和模型库管理系统。
8、数据仓库
数据仓库已成为建立决策支持系统的重要技术手段，是建立决策支持系统的基础。
数据仓库的数据有4个特征:面向主题的、集成的、不可更新的和随时间不断变化的。
数据仓库的数据模型与传统的数据库相比有一些区别:它不包含纯操作型的数据;扩充了码的结构，增加了时间属性作为码的一部分;增加了一些导出数据。
数据仓库的设计过程与传统数据库相似，分为三级数据模型，即概念模型、逻辑模型、物理模型。概念模型使用E,R图描述，长方形表示主题而不再是实体，其它雷同。逻辑模型就是关系模型。
在进行数据仓库设计时，需要把数据分割和粒度划分结合起来考虑。粒度划分就是确定数据仓库中数据单元的详细程序级别，数据分割类似于数据分片概念。
元数据是数据仓库设计的一个重要组成部分。
9、数据转移技术
数据转移技术也称为数据转换或数据变换，把多种传统资源或外部资源信息中不完善的数据自动转换为准确可靠的数据。
数据转移技术有4种转移类型: 1)简单转移 (数据元的类型转换、日期/时间格式转换、字段解码)
2)清洗 (检查字段中的有效值、重新格式化某些类型的数据，如地址)
3)集成
4)聚集和概括
10、OLTP，联机事务处理，以快速事务响应和频繁的数据修改为特征，方便用户使用数据库快速处理具体业务。
OLAP，联机分析处理，是以数据仓库进行分析决策的基础，是针对待定问题的联机数据访问和分析。
它们是两类不同的应用。
OLTP与OLAP的对比:
OLTP OLAP
数据库原始数据 数据库导出数据或数据仓库数据
细节性数据 综合性数据
当前数据 历史数据
经常更新 不可更新，但周期性刷新
一次性处理的数据量小 一次性处理的数据量大
响应时间要求高 响应时间合理
用户数量大 用户数量相对较少
面向操作人员，支持日常操作 面向决策人员，支持管理需要
面向应用，事务驱动 面向分析，分析驱动
11、企业决策支持解决方案，需要从决策支持系统的体系结构(C/S较流行)、软件工具和开发(原型法、生命周期法)3个方面加以分析。
第十五章 知识产权基础 第十六章 标准化
1、知识产权的概念，是指民事权利主体基于智力创造性的智力成果。可以分为工业产权和著作权(版权)。
知识产权的特点:无形性、双重性、确认性、独占性、地域性、时间性。
2、计算机软件受著作权保护的条件:按计算机软件保护条例规定，受保护的软件产品应“独立创作、可被感知、逻辑合理”。
计算机软件保护条例规定，合法受保护的对象为“程序和文档”，著作权法不保护软件开发使用的思想、概念、发现、原理、算法、处理过程和运算方法。
计算机软件著作权的权利有2类，人身权和财产权。人身权包括发表权、开发者身份权(署名权)。
财产权，计算机软件保护条例规定，软件著作权人享有:使用权、复制权、修改权、发行权、翻译权、注释权、信息网络传播权、出租权、使用许可权和获得报酬权、转让权。
计算机软件著作权的归属问题:
1)职务开发软件著作权的归属;
2)合作开发软件著作权的归属;
3)委托开发的软件著作权的归属;
4)接受任务开发的软件著作权归属; ,,3,4两条中都是先依据
合同
劳动合同范本免费下载装修合同范本免费下载租赁合同免费下载房屋买卖合同下载劳务合同范本下载
或协议来确认著作权归属，如未明确归定则著作权属于实 际的开发者。
5)主体变更后软件著作权的归属;
6)权利转让后软件著作权的归属;
7)司法、判决引起的软件著作权归属问题;
8)保护期满权利丧失。
3、计算机软件的商业秘密权
商业秘密的定义:在,中华人民共和国反不正当竞争法,中将商业秘密定义为“不为公众所知的、能为权利人带来经济利益、具有实用性并经权利人采取保密措施的技术信息和经营信息”。经营秘密和技术秘密是商业秘密的基本内容。
商业秘密的构成条件:未公开性、具有实用性、保密性。一项商业秘密要受到法律保护，必须具备这三个条件。
,中华人民共和国反不正当竞争法,保护计算机软件，是以计算机软件中是否包含着“商业秘密”为必要条件。即使软件尚未开发完成，在软件中已经形成的知识内容也可以作为商业秘密。
4、授予专利权的条件:新颖性、创造性、实用性。
专利法不适用的对象有:违法违德妨害公共利益的发明，客观世界已存在但未揭示的规律、性质和现象，智力活动的规则和方法，病的诊断及治疗方法，动物和植物的品种，原子核变换得到的物质。
发明专利的保护期为20年，实用新型专利权和外观设计专利权的保护期为10年。公民的作品发表权的保护期为公民终生及其死后50年。我国商标权的保护期为10年，到期时可以续注，每次10年。计算机软件著作权保护期为50年。
我国著作权法不保护“法律、法规、国家机关的决议等性质的文件，及其官方正式译文。
我国著作权法规定:作者的署名权、修改权、保护作品完整权的保护期不受限制。
著作权法规定:为介绍、评论某一作品或者说明某一问题，在作品中适当引用他人已经发表的作品，可以不经著作人许可，但应当指明作者姓名、作品名称且不能侵犯著作权人享有的其他权利。
著作权法规定:汇编若干作品、作品的片段或者不构成作品的数据或者其他材料，对其内容的选择或者编排体现独创性的作品，为汇编作品，其著作权由汇编人享有，但行使著作权时，不得侵犯原作品的著作权。
软件工程师接受单位的任务，独立完成了某应用软件的开发和设计，其软件著作权属于“单位的法人”。
我国专利法规定，申请专利的发明创造，在申请日以前6个月内，有下面情况发生的，不会丧失新颖性:
1)在中国政府主办或者承认的国际展览会上首次展出的;
2)在规定的学术会议或者技术会议上首次发表的;
3)他人未经申请人同意而泄露其内容的。
专利申请日:以专利局收到完整专利申请文件的日期为专利申请日。如果申请文件是邮寄来的，则以寄出的邮戳日期为申请日。
5、标准化的基本过程:标准产生子过程、标准实施子过程、标准更新子过程。
标准的编号: 国际标准编号形式为,, 标准代号，专业类号，顺序号，年代号
我国标准编号形式为,, 标准代号，标准发布顺序号，年代号(年号即发布年份的后两位数字)
国家标准代号:GB(强制性的) GB/T(推荐性的)
行业标准代号:由汉语拼音大写字母组成，加上斜线T后变为推荐标准。如:JR(金融)
地方标准代号:由DB加上两位地方代码(北京为11)
企业标准代号:由Q加上斜线再加上企业代号组成。如Q/**。
6、国际标准组织: ISO,,国际标准化组织
IEC,,国际电工委员会
ITU,,国际电信联盟
国家标准组织: ANSI,,美国国家标准
DIN,,德国国家标准
BS,,英国国家标准
JIS,,日本 SIS,,瑞典 SNV,,瑞士 NF,,法国
UNI,,意大利
GJB,,中华人民共和国国家军用标准
行业协会标准: IEEE,,美国电气电子工程师学会
7、采用国际标准的程度分为:等同IDT、等效EQV、非等效NEQ。
8、过程评估标准ISO/IEC 15504，它提供了一个软件过程评估的框架。它可以被任何软件企业用于软件的设计、管理、监督、控制以及提高获得、供应、开发、操作、升级和支持能力。它涉及了过程评估的各个方面，其文档主要包括9个部分。
ISO标准每5年复审一次。我国的国家标准有效期也是5年。国家标准的最后两位数字是年号。
条码中对应条码符号的一组阿拉伯数字称为条码代码，条码代码供人们直接识读，可以通过键盘向计算机输入数据。
ISO9000:2000,质量管理体系 基础和术语,标准提出的“8项质量管理原则”，是在总结了质量管理经验的基础上，明确了一个组织在实施质量管理中必须遵循的原则，也是ISO9000:2000族标准制定的指导思想和理论基础。
ISO9000系列标准是国际化标准化组织质量管理和质量保证技术委员会于1987年分布的质量管理和质量保证系列标准。
目前ISO9000:2000系列标准它包括5项具体标准。
ISO12207是软件生命周期过程的国际标准。
ISO/IEC JTC1是制定信息技术领域国际标准的机构。
浙公网安备 33021202002483