软考学习笔记-数据库工程师第五章－网络基础知识
第五章 网络基础知识
1、网络的拓朴结构
计算机网络拓朴主要是指通信子网的拓朴构型。网络拓朴影响着网络的性能，以及整个网络的设计、功能、可靠性和通信费用
总线结构：只有一条双向通路，便于采用广播式传送信息；总线拓朴结构属于分布式控制，无须中央处理器，结构简单；节点的增删和位置的变动容易，扩充性能好；节点的接口通常采用无源线路，可靠性高；设备少价格低，安装使用方便；但因为电气信号通路多，干扰较大，对信号的质量要求高。负载重时线路的利用率低。网上的信息延迟不确定，故障隔离和检测困难。
星状结构：维护容易，配置灵活；故障隔离和检测容易；网络延迟时间短节点与中央交换单元直接连通，各节点之间的通信必须经过中央单元转换；网络共享能力差；线路利用率低，中央单元负荷重。
环状结构：环形网中信息流动方向是固定的，两个节点间只有一条通路，路径控制简单；有旁路设备，节点一旦发生故障，系统自动旁路，可靠性高；信息要串行穿行多个节点，传输效率低，系统响应速度慢；环路封闭，扩充较难。
树状结构：是总线结构的扩充形式，主要用于多个网络组成的分组结构中。
分布式结构：无严格的布点规定，各节点之间有多条线路相连。有较高的可靠性，资源共享方便，网络响应时间短；因为节点与多个节点相连，故节点的路由选择和流量控制难度大，管理复杂；硬件成本高。
2、网络的协议和标准
一个网络协议主要包括3个要素：语法、语义和时序。协议是一组约定的规则，它有助于通信实体间的相互理解和正确通信。协议中有3个要素，其中语法定义数据的表示形式；语义则能使数据管理所需的信息得到正确理解；时序则规定了通信应答信号之间的间隔和先后关系。
在IEEE802局域网标准中只定义了物理层和数据链路层。其中又把数据链路层分为了逻辑链路控制LLC和介质访问控制MAC。
以太网IEEE802.3采用的是带冲突检测的载波监听多路访问协议技术CSMA/CD。802.3,802.3u,802.3z。
802.3u采用非屏蔽双绞线，并使用与802.3一样的介质访问控制（MAC）层；802.3z对MAC规范进行了重定义，并重定义了物理层标准。
令牌环网IEEE802.5，FDDI类似于令牌环网协议，但是采用双环技术。
PPP协议，具备用户验证能力，可以解决IP分配。PPP和其他协议共同派生出了PPPoE和PPPOA，主要用于ADSL。
ADSL，非对称用户数据线，速率上行1M下行8M，把线路按频段分成语音、上行和下行3个信道。
数字专线DDN，综合业务数字网ISDN
帧中继FR，双工并保持顺序不变。是一种基于可变帧长的数据传输网络。适用于带宽需求64K－2M，通信距离较长，数据有突发性时。
异步传输模式ATM，是一种面向分组的快速分组交换模式，使用异步时分复用技术，将信息流分割成定长的信息元。共有4层，用户层、ATM适配层、ATM层、物理层。有2种连接类型，永久虚电路和交换虚电路。
TCP/IP协议是internet协议的核心，分为5方面：逻辑编址、路由选择、域名解析、错误检测、流量控制及对应用程序的支持。
TCP/IP分层模型由4层组成，应用层（FTP,telnet,smtp,nfs,snmp）、传输层（TCP，UDP）、网际层（IP,icmp,arp,rarp）、网络接口层(802.3,802.5,FDDI,ppp）。
TCP/IP的传输层任务是提供应用程序之间的通信服务，这种通信又叫端到端的通信。网际层又叫IP层，它接收传输层的请求，传送某个具有目的地址信息的分组。网络接口层又称为数据链路层。
3、构建网络
网络互联的设备有：中继器（及集线器）、网桥（及交换机）、路由器、网关。
在构建一个网络的过程中，主要考虑服务器、客户机、网络设备、通信介质、、网络软件等，以及协议的选择和设备的连接方式。
4、关于IP地址
IP地址分为5类：A，B，C，D，E。
A类网络地址占有1个字节，定义最高位为0来标识此类地址。余下7位为真正的网络地址，支持1－126个网络。第一个字节的10进制表示为000－127。后面3个字节作为主机地址，提供2^24 - 2个端点的寻址。
B类网络地址占有2个字节，定义最高位为10来标识此地址。余下14位为真正的网络地址，第一个字节的10进制表示为128－191。
C类网络地址占有3个字节，定义最高位为110来标识此地址。余下21位为真正的网络地址，第一个字节的10进制表示为192－223。
D类网络地址用于组播，定义最高位为1110来标识此类地址。第一个字节的10进制表示为224－239。
E类网络地址为实验保留，定义最高位为1111来标识此类地址。第一个字节的10进制表示为240－255。
可变长子网掩码VLSM，就是在IP地址后面加上“/网络号及子网络号编址比特数”。如：193.168.125.0/27，就表示前27位为网络号。
5、网络的信息安全：主要就是信息的存储安全和传输安全。信息的存储安全包括信息的使用安全（用户的标识与验证、用户存取权限限制、安全问题跟踪），计算机病毒的防治，系统安全监控，数据的加密，防止非法攻击。
WindowsNT的网络结构中，包括的两个接口是NDIS和TDI。通过边界定义了各个层次间的统一接口，两个主要的边界层为NDIS和TDI。
NDIS，网络设备接口规范；
TDI，传输驱动程序接口。
防火墙技术经历了包过滤、应用代理网关和状态检测三个发展阶段。
包过滤路由器是最简单常用的防火墙。一般工作在网络层，对经过网络的信息进行分析并按策略进行限制，其核心是包过滤的算法设计。优点是速度快、实现方便；缺点是安全性差、兼容差，日志记录能力差。
双宿主主机防火墙，由具有两个以上网口的堡垒主机构成，通过代理服务器软件从一个子网访问另一个子网。优点是加强了日志功能；缺点是若堡垒主机被攻破意味着失去了网络的安全。
屏蔽主机网关防火墙，是由过滤路由器和应用网关组成。过滤路由器的作用是进行包过滤；应用网关的作用是代理服务。共建立了两道安全屏障。优点是安全性高；缺点是配置复杂。
被屏蔽子网防火墙，由两个包过滤路由器和一个应用网关（堡垒主机）组成。两个包过滤路由器中间形成一个DMZ区。
6、重发器也称为中继器或转发器，是一种在物理层上互联网段的设备。
网关也称为信关，工作在应用层，实现网络间协议转换的功能，也被称为协议转换器。
Kerberos是分布式环境下的身份认证系统。为了防止relay攻击，它使用了一次性的ticket和时间戳。常用的数字证书格式有PGP和X.509证书。
SSL是要建立一条安全的连接。是传输层安全协议。
HTTPS用于安全地传送单个报文，属于应用层协议。
SOCKS5是增加了认证功能的SOCKS协议。SOCKS用于代理基于TCP/IP的网络应用。SOCKS服务器端实现于应用层，SOCKS客户机实现于应用层和传输层之间。协议的作用是在两个没有直接IP联系的主机之间实现通信。
SNMP是一种广泛使用的网络管理协议，用来收集网络上设备信息。其对应的管理信息库为MIB-2。
7、OSI参考模型的三个主要概念是Service, Interface, Protocol。
OSI/RM中的1－3层负责通信功能，称为通信子网。5－7层属于资源子网的功能范围，称为资源子网层。传输层起着承接作用。
物理层，只是为它的上一层提供一个物理连接，在这一层数据还没有被组织；
数据链路层，负责两个相邻结点间的线路上无差错地传送以帧为单位的数据，并进行流量控制。数据链路层要负责建立、维持和释放数据链路的连接；
网络层，为传输层提供端到端的交换网络数据传送功能，屏蔽传输细节，为传输层建立、维持和拆除一条或多条通信路径。在这一层帧被组成数据包；
传输层，为会话层提供透明可靠的数据传输服务，保证端到端的数据完整性。选择网络层的最适宜服务，提供建立、维护、拆除传输链接的功能。在这一层传输的是报文；
会话层，为表示层实体提供建立、维护、结束会话连接的功能。完成通信进程的逻辑名字与物理名字间的对应，提供会话管理服务；
表示层，为应用层提供能解释所交换信息含义的一组服务，提供格式化的表示和转换数据服务，数据的压缩、解压、加密和解密工作也是由表示层完成；
应用层，提供OSI用户服务，提供网络与用户应用软件间的接口服务。
8、ISDN为了使通信网络内部的变化对终端用户是透明的、不可见的，它必须提供一个标准的用户接口。
宽带ISDN可以提供许多业务，其中会议电视属于会话型业务。窄带ISDN向用户提供基本速率144Kb/s的基本速率接口BRI，和速率2Mb/s的一次群速率接口PRI。
双绞线多用于10BASE－T和100BASE－T的以太网中，一段双绞线的最大长度为100m，只能连接一台计算机。双绞线的每端需要一个RJ45插头，各段双绞线通过集线器相连，利用双绞线最多可连接64个结点到中继器。
屏蔽双绞线STP，非屏蔽双绞线UTP。10BASE-T, 10BASE-F的最后一个字母是以线缆类型命名的，T表示双绞线，F表示光纤。
以太网遵循IEEE802.3标准。采用粗缆的标准称为10Base5，规定每段粗缆的长度不超过500米。采用细缆的标准称为10BASE2，工作距离为185米。否则要使用重发器（即中继器）相连。整个网的长度不能超过2500米。若超过该长度则要分成两个网，网间使用网桥相连。这是在数据链路层的连接。
千兆以太网支持3种传输介质。多模光纤工作距离为500米，单模光纤的工作距离为2000米；宽带同轴电缆的工作距离只有25米；5类UTP双绞线仍然是最大传输100米。
符合以太网标准的物理地址采用连续编码方法，它使用的地址长度是48bit。
域名解析的两种主要方式是反复解析和递归解析。
从网络高层协议角度看，网络攻击可以分为服务攻击与非服务攻击。
防火墙一般可提供4种服务，它们是服务控制、方向控制、行为控制和用户控制。
防火墙是一种被动的网络安全措施。
2008年12月28日日曜日
软考学习笔记-数据库工程师第四章－程序设计语言基础
软考学习笔记-数据库工程师第四章－程序设计语言基础
第四章 程序设计语言基础
1、程序设计语言的基本概念
低级语言和高级语言
编译程序和解释程序：解释程序会直接解释执行源程序或者将源程序翻译成某种中间表示形式后再执行。
编译程序则会将源程序翻译成目标语言程序，然后在计算机上运行目标程序。
二者的根本区别是，在编译方式下，机器上运行的是与源程序等价的目标程序，源程序和编译程序都不参加目标程序的执行过程；而在解释方式下，解释程序和源程序要参与到程序的运行过程中，运行程序的控制权在解释程序。解释器翻译源程序时不生成独立的目标程序，而编译器则需将源程序翻译成独立的目标程序。
程序设计语言的定义：一般地，程序设计语言涉及3个方面，语法、语义和语用。语言的实现有个语境问题，包括编译环境和运行环境。
2、程序设计语言的分类：按程序设计方法的不同分为4种。分别是命令式程序设计语言和结构化设计语言、面向对象的程序设计语言、函数式程序设计语言、逻辑型程序设计语言。
命令式程序设计语言：它是基于动作的语言，也称为过程式语言。随着函数、库、模块的使用，出现了结构化程序设计技术。在结构化程序设计中任何程序段的编写都基于3种基本结构，就是顺序、选择、循环。典型的实例有Pascal,C。
面向对象的程序设计语言：面向对象的语言一般包括这3个概念，对象、类、继承。对象是人们要研究的任何事物，它具有状态和操作；类是由用户定义的数据类型，它将具有相同状态、操作和访问机制的多个对象抽象成一个对象类，属于这种类的一个对象叫作类实例或类对象，类代表一般而该类的一个对象代表具体；继承，类与类之间可以组成继承层次，以达到概念复用和代码重用。
函数式程序设计语言：是一种面向值的语言，其基本概念来自LISP。主要应用于符号数据处理，如微积分、数理逻辑、游戏推演以及人工智能。
逻辑型程序设计语言：是陈述式语言，其基本概念来自PROLOG，不是严格的通用程序设计语言。PROLOG的基本运算单位是Horn子句。主要用在人工智能领域，也用在自然语言处理、数据库查询、算法描述等，尤其适合作为专家系统的开发工具。
FORTRAN是世界上最早出现的高级程序设计语言，是由一个主程序或一个主程序与若干个子程序组成，且都是独立的程序单位；
COBOL是一种面向事务处理的高级语言，主要用于情报检索、商业数据处理等管理领域；
ALGOL是另一个较早出现的高级语言，是一个分程序结构语言，每个分程序由begin和end括起来；
PASCAL语言体现了结构化程序设计风格，将分程序和过程这两个概念合并为“过程”。一个PASCAL程序本身可看成是一个操作系统所调用的过程；
C语言在系统应用和实时处理应用中成为主要的开发语言；
C＋＋中最主要的是增加了类机制，成为一种面向对象的设计语言，并最大限度的与C兼容；
JAVA是一种新型的面向对象的Internet编程语言，扩充了对分布式及C/S结构的支持，是一种强类型语言，隐含了指针以避免由于指针引起的问题；
LISP是基于表处理的函数语言，该语言中的程序和数据的形式是等价的，数据结构可以作为程序执行，程序也可以作为数据修改
3、程序设计语言的基本成分：包括数据、运算、控制和传输。
数据成分，是程序操作的对象，具有存储类别、类型、名称、作用域和生存期等属性，使用时要为它分配内存空间。常量、变量、全局量、局部量。
运算成分，指明允许使用的运算符号及运算规则。
函数：函数的定义，函数的声明，函数的调用。函数的定义包括函数首部和函数体。函数应先声明后引用。函数调用时实参与形参间交换信息的方法有传值调用和引用调用两种。
传值调用中，若函数调用时以实参向形式参数传递相应类型的值，这种方式下，形式参数将不能向实际参数返回信息；除非使用用指针作形参，在调用时先对实参进行取地址运算，然后将实参地址传递给指针形参，这样才可以实现被调用函数对实际参数的修改。
4、汇编程序的基本原理
汇编语言是面向机器的符号化程序设计语言。计算机需要使用汇编程序对汇编源程序进行翻译才能运行。一般汇编语言都提供指令语句、伪指令语句、宏指令语句进行编程。
指令语句， 又称机器指令语句，汇编后能产生相应的机器代码，可以被CPU直接识别执行。
伪指令语句，指示汇编程序在汇编源程序时完成某些工作，如给变量分配存储单元地址，给某个符号赋值。
宏指令语句，允许用户将多次重复使用的程序段定义为宏，宏指令语句就是对宏的引用。
指令语句与伪指令语句的区别：指令语句经汇编后将产生相应的机器代码，而伪指令语句不产生机器代码；指令语句是在程序运行时完成，而伪指令语句只能在源程序被汇编时完成。
汇编程序：它的基本工作是将每一条可执行汇编语句转换成对应的机器指令；处理源程序中出现的伪指令和宏指令。汇编程序一般需要扫描源程序2次才能完成翻译过程，第一次主要是计算符号的值，第二次才产生目标程序。
5、编译程序的工作阶段，编译程序的过程分为6个阶段，另有2个辅助的管理程序。分为是：词法分析、语法分析、语义分析、中间代码生成器、代码优化、目标代码生成6个阶段和符号表管理、出错处理程序。中间代码的特征是与具体的机器无关。
代码优化和中间代码生成两个阶段并不是每种编译程序都必须的。
语法分析中的预测分析法是自顶向下的一种语法分析方法。
编译器在语义分析阶段进行表达式的类型检查及类型转换。
编译过程的各个阶段都会涉及到表格管理和出错处理。
第四章 程序设计语言基础
1、程序设计语言的基本概念
低级语言和高级语言
编译程序和解释程序：解释程序会直接解释执行源程序或者将源程序翻译成某种中间表示形式后再执行。
编译程序则会将源程序翻译成目标语言程序，然后在计算机上运行目标程序。
二者的根本区别是，在编译方式下，机器上运行的是与源程序等价的目标程序，源程序和编译程序都不参加目标程序的执行过程；而在解释方式下，解释程序和源程序要参与到程序的运行过程中，运行程序的控制权在解释程序。解释器翻译源程序时不生成独立的目标程序，而编译器则需将源程序翻译成独立的目标程序。
程序设计语言的定义：一般地，程序设计语言涉及3个方面，语法、语义和语用。语言的实现有个语境问题，包括编译环境和运行环境。
2、程序设计语言的分类：按程序设计方法的不同分为4种。分别是命令式程序设计语言和结构化设计语言、面向对象的程序设计语言、函数式程序设计语言、逻辑型程序设计语言。
命令式程序设计语言：它是基于动作的语言，也称为过程式语言。随着函数、库、模块的使用，出现了结构化程序设计技术。在结构化程序设计中任何程序段的编写都基于3种基本结构，就是顺序、选择、循环。典型的实例有Pascal,C。
面向对象的程序设计语言：面向对象的语言一般包括这3个概念，对象、类、继承。对象是人们要研究的任何事物，它具有状态和操作；类是由用户定义的数据类型，它将具有相同状态、操作和访问机制的多个对象抽象成一个对象类，属于这种类的一个对象叫作类实例或类对象，类代表一般而该类的一个对象代表具体；继承，类与类之间可以组成继承层次，以达到概念复用和代码重用。
函数式程序设计语言：是一种面向值的语言，其基本概念来自LISP。主要应用于符号数据处理，如微积分、数理逻辑、游戏推演以及人工智能。
逻辑型程序设计语言：是陈述式语言，其基本概念来自PROLOG，不是严格的通用程序设计语言。PROLOG的基本运算单位是Horn子句。主要用在人工智能领域，也用在自然语言处理、数据库查询、算法描述等，尤其适合作为专家系统的开发工具。
FORTRAN是世界上最早出现的高级程序设计语言，是由一个主程序或一个主程序与若干个子程序组成，且都是独立的程序单位；
COBOL是一种面向事务处理的高级语言，主要用于情报检索、商业数据处理等管理领域；
ALGOL是另一个较早出现的高级语言，是一个分程序结构语言，每个分程序由begin和end括起来；
PASCAL语言体现了结构化程序设计风格，将分程序和过程这两个概念合并为“过程”。一个PASCAL程序本身可看成是一个操作系统所调用的过程；
C语言在系统应用和实时处理应用中成为主要的开发语言；
C＋＋中最主要的是增加了类机制，成为一种面向对象的设计语言，并最大限度的与C兼容；
JAVA是一种新型的面向对象的Internet编程语言，扩充了对分布式及C/S结构的支持，是一种强类型语言，隐含了指针以避免由于指针引起的问题；
LISP是基于表处理的函数语言，该语言中的程序和数据的形式是等价的，数据结构可以作为程序执行，程序也可以作为数据修改
3、程序设计语言的基本成分：包括数据、运算、控制和传输。
数据成分，是程序操作的对象，具有存储类别、类型、名称、作用域和生存期等属性，使用时要为它分配内存空间。常量、变量、全局量、局部量。
运算成分，指明允许使用的运算符号及运算规则。
函数：函数的定义，函数的声明，函数的调用。函数的定义包括函数首部和函数体。函数应先声明后引用。函数调用时实参与形参间交换信息的方法有传值调用和引用调用两种。
传值调用中，若函数调用时以实参向形式参数传递相应类型的值，这种方式下，形式参数将不能向实际参数返回信息；除非使用用指针作形参，在调用时先对实参进行取地址运算，然后将实参地址传递给指针形参，这样才可以实现被调用函数对实际参数的修改。
4、汇编程序的基本原理
汇编语言是面向机器的符号化程序设计语言。计算机需要使用汇编程序对汇编源程序进行翻译才能运行。一般汇编语言都提供指令语句、伪指令语句、宏指令语句进行编程。
指令语句， 又称机器指令语句，汇编后能产生相应的机器代码，可以被CPU直接识别执行。
伪指令语句，指示汇编程序在汇编源程序时完成某些工作，如给变量分配存储单元地址，给某个符号赋值。
宏指令语句，允许用户将多次重复使用的程序段定义为宏，宏指令语句就是对宏的引用。
指令语句与伪指令语句的区别：指令语句经汇编后将产生相应的机器代码，而伪指令语句不产生机器代码；指令语句是在程序运行时完成，而伪指令语句只能在源程序被汇编时完成。
汇编程序：它的基本工作是将每一条可执行汇编语句转换成对应的机器指令；处理源程序中出现的伪指令和宏指令。汇编程序一般需要扫描源程序2次才能完成翻译过程，第一次主要是计算符号的值，第二次才产生目标程序。
5、编译程序的工作阶段，编译程序的过程分为6个阶段，另有2个辅助的管理程序。分为是：词法分析、语法分析、语义分析、中间代码生成器、代码优化、目标代码生成6个阶段和符号表管理、出错处理程序。中间代码的特征是与具体的机器无关。
代码优化和中间代码生成两个阶段并不是每种编译程序都必须的。
语法分析中的预测分析法是自顶向下的一种语法分析方法。
编译器在语义分析阶段进行表达式的类型检查及类型转换。
编译过程的各个阶段都会涉及到表格管理和出错处理。
软考学习笔记-数据库工程师第三章-操作系统知识
软考学习笔记-数据库工程师第三章-操作系统知识
三、操作系统知识
1、操作系统的定义：是管理计算机中各种软件、硬件资源的程序和相关文档的集合，是一种系统软件。
操作系统能有效的组织和管理系统中的各种软、硬件资源，合理地组织计算机工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。
操作系统的两个重要作用：
通过资源管理，提高系统的使用效率；
改善人机界面，向用户提供友好的工作环境。
操作系统的4个特征：并发性、共享性、虚拟性、不确定性。
操作系统的5个管理功能：进程管理、文件管理、存储管理、设备管理、作业管理
操作系统的分类：
批处理系统，计算机自动、顺序地执行作业流产生的每一个作业，以节省人工操作时间和提高机器的使用效率。分为单道批处理系统和多道批处理系统。优点是同一批内的各作业次次执行，改善了cpu,io的使用效率，提高了吞吐量。缺点是磁盘需要人工装卸，作业需要人工分类，监督程序易受用户程序破坏，缺少交互性。
分时系统， 具有如下特征：多路性、独立性、交互性、及时性。
实时系统，分为实时控制系统和实时信息处理系统。主要特点有：快速的响应时间、有限的交互能力、高可靠性
网络操作系统，使得计算机更有效地共享网络资源，为网络用户提供所需各种服务的软件和有关协议的集合。
分布式操作系统，是由多个分散的计算机经网络连接而成，各主机无主次之分。为分布式计算机配置的操作系统称为分布式操作系统。
微机操作系统
嵌入式操作系统
2、研究操作系统的观点
资源管理的观点：从这种观点看，操作系统的管理对象是计算机系统的资源，操作系统则是管理计算机系统的程序集合。这种观点是在共享的前提下以资源分配、使用和回收为出发点，考虑操作系统各部分程序的功能和算法。
虚拟机的观点：操作系统加裸机构成虚拟计算机。虚拟机的观点是从功能分解的角度出发，考虑操作系统的结构，将操作系统分成若干层次，每一层完成特定的功能。
3、顺序程序执行时的特征：顺序性、封闭性、可再现性；
并发程序执行时的特征：非封闭性、程序和机器执行程序的活动不在一一对应、并发程序间的相互制约性。
引入进程的原因：由于程序并发执行破坏了程序的封闭性和可再现性，使得程序和执行程序的活动不在一一对应，此时用静态的程序概念已经不能描述系统中程序动态执行的过程，所以引入了进程。
4、进程的定义：就是程序的一次执行，该程序可以和其它程序并发执行。
进程的组成：进程通常是由程序、数据及进程控制块（PCB）组成的。
进程的程序部分是进程执行时不可修改部分，它描述了进程需要完成的功能；
进程的数据部分是进程的可修改部分；
进程控制块是进程的描述信息和控制信息，是进程存在的惟一标志。
进程和程序的区别是：进程具有状态而程序没有。
5、进程的状态及状态间的切换
三态模型：运行、就绪、阻塞。
五态模型：新建态、终止态、运行、就绪、阻塞。
新建态：对应于进程刚刚被创建时还没有被提交，并等待系统完成创建进程的所有必要信息的状态。整个过程分为两个阶段，一是为一个新建进程创建必要的管理信息，另一是让进程进入就绪状态。因为有了新建态，操作系统可以根据系统的性能和主存的容量限制而推迟新建态的提交。
终止态也分为两个阶段，一是等待操作系统进行善后处理，另一是释放主存。
具有挂起状态的进程状态：当系统资源不能满足所有进程的运行要求时，必须将某些进程挂起，放在磁盘对换区，暂时不参加调度，以平衡系统负载。有这样几个状态：活跃就绪、静止就绪、活跃阻塞、静止阻塞。
6、进程的控制，就是对系统中所有进程从创建到消亡的全过程实施有效的控制。操作系统的内核为系统实现进程控制和存储管理提供了有效的控制机制。
大多数操作系统内核均包含支撑功能和资源管理功能。
支撑功能：中断处理、时钟管理、原语操作。
原语是由若干条机器指令构成的，用于完成特定功能的一段程序。内核在执行某些基本操作时往往是通过原语操作实现的。原语在执行过程中不可分割。内核中包含的原语有进程控制、进程通信、资源管理等。
资源管理功能：进程管理、存储器管理、设备管理。
7、进程间通信
进程间的同步：一般来说，一个进程相对于另一个进程的运行速度是不确定的，即进程是在异步环境下运行。每个进程都以各自独立的不可预知的速度向前推进，但相互合作的进程需要在某些确定点上协调它们的工作，当一个进程到达了这些点后，除非另一进程已完成了某些操作，否则就不得不停下来等等这些操作结束。
进程间的互斥：在多道程序系统中，各进程可以共享各类资源，但有些资源一次只能供一个进程使用，称为临界资源(critial resource)。同步是进程间的直接制约问题，互斥是进程间的间接制约问题。
临界区(critial section)是对临界资源实施操作的那段程序。互斥临界区管理的原则为：有空即进、无空则等、有限等待、让权等待。
8、整形信号量与PV操作
整形信号量是一个整形变量，根据控制对象的不同赋不同的值。信号量分为两类：
公用信号量：实现进程间的互斥，每个相关进程即可对它施行P操作也可以进行V操作，初值为1或资源的数目；
私用信号量：实现进程间的同步，只有一个进程可以对它施行P操作，其它进程只能做V操作，初值为0或某个正整数。
信号量S的物理意义：S＞＝0表示某资源的可用数，S＜0则其绝对值表示阻塞队列中等待该资源的进程数。
PV操作是实现进程同步与互斥的常用方法。PV操作是低级通信原语，其中P操作表示申请一个资源，V操作表示释放一个资源。
P操作定义：S:=S-1，若S＞＝0，则执行P操作的进程继续执行；否则若S＜0，则该进程为阻塞状态，并将其插入阻塞队列。
V操作定义：S:=S+1，若S＞0，则执行V操作的进程继续执行；否则，若S＜＝0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，执行V操作的进程继续执行。
利用PV操作实现进程的互斥：令信号量mutex的初值为1，当进入临界区时执行P操作，临界区时执行V操作。
P(mutex)
临界区
V(mutex)
怎样利用PV操作实现进程的同步：可用一个信号量与消息联系起来，当信号量的值为0时表示希望的消息未产生，当信号量的值为非0时表示希望的消息已经存在。假定用信号量S表示某条消息，进程可以通过调用P操作测试消息是否到达，调用V操作通知消息已准备好。最典型的是单缓冲区的生产者和消费者的同步问题。如果采用PV操作来实现进程PA和进程PB间的管道通信，并且保证这两个进程并发执行的正确性，则至少需要2个信号量，信号量的初值分别为0、1。
9、高级通信原语，因为PV操作不足以描述复杂的进程间的信息交换，所以引入高级通信原语。
高级通信原语有这么几种：共享存储系统、消息传递系统、管道通信。
进程通信有直接和间接两种方式。间接方式是以信箱以为媒介。
10、管程(monitor)：另一种同步机制，采用资源集中管理的方法，将系统中的资源用某种数据结构抽象地表示出来。由于临界区是访问共享资源的代码段，因而建立一个管程来管理进程提出的访问请求。采用这种方式对共享资源的管理就可以借助数据结构及在其上实施操作的若干过程来进行。对共享资源的申请和释放可以通过过程在数据结构上的操作来实现。
11、进程调度，在某些系统中一个作业从提交到完成需要经历高、中、低三级的调度。
高级调度（又称长调度、作业调度或接纳调度），它决定输入池中的哪个后备作业可以调入主系统做好运行的准备，成为一个或一组就绪进程。
中级调度（又称对换调度），它决定处于交换区中的哪个就绪进程可以调入主存，以便直接参与CPU的竞争。
低级调度（又称进程调度），它决定处于主存中的哪个进程使用CPU。
调度方式，是指当有更高优先级的进程来到时如何分配CPU。调度的方式分为可剥夺式和不可剥夺式两种。
常用的调度算法：先来先服务，主要用于宏观调度，有利于长作业，有利于CPU繁忙的作业；
时间片轮转，主要用于微观调度，提高了并发性和响应时间，最终提高了资源利用率；
优先级调度， 分为静态和动态两种；
多级反馈调度，是在时间片轮转和优先级算法的基础上改进得到。其特点是：照顾了短进程以提高系统吞吐量，照顾I/O型进程以获得较好的I/O设备利用率并缩短响应时间，不必估计进程的执行时间和动态调节优先级。
12、死锁：就是指两个以上的进程相互请求对方已经占有的资源时而导致无法继续运行下去的现象。
几种会产生死锁的情况：进程推进程顺序不当，同类资源分配不当，PV使用不当。
进程资源有向图：由方框、圆圈和有向边3部分组成。其中资源用方框表示，进程用圆圈表示。在方框中每一个小圆圈代表一个资源。有向边分别代表请求资源和分配资源。
死锁产生的原因：因为竞争资源或进程推进顺序非法。进程推进顺序仍是关于进程请求和释放资源的顺序。
死锁产生的4个必要条件：互斥条件、请求保持条件、不可剥夺条件、环路条件。
互斥是说进程对所要求的资源有排它性控制。请求保持是说进程断续地请求资源，但后续的资源被阻塞。环路是指在发生死锁时在进程资源有向图中，每个进程都占有了下一个进程请求的一个或多个资源。
死锁的4种处理：鸵鸟策略；
预防策略，即破坏死锁产生的4个必要条件之一；
避免策略，即精心分配资源，主动回避死锁；
检测与解除死锁
13、线程
传统的进程有两个基本属性，即可拥有资源的独立单位，和可独立调度、分配的基本单位。引入线程后，将传统进程的两个属性分开，线程作为可独立调度和分配的基本单位，进程作为独立拥有资源的单位。因此，用户可以通过创建线程来完成任务，以减少程序并发执行时的时空开销。
14、存储器的结构：(寄存器)--缓存－主存－辅存。
虚拟地址，又称为逻辑地址、相对地址、程序地址。它是从0号单元开始编址，并顺序分配所有的符号名所对应的地址单元，它不是主存中的真实地址。
地址空间，又称逻辑地址、虚地址。
存储空间，又称物理地址空间，是物理地址的集合。相对地址空间通过地址再定位机构转换到绝对地址空间。
重定位：程序的逻辑地址被转换成主存的物理地址的过程称为地址重定位。分为静态重定位和动态重定位。
静态地址重定位的优点是无需硬件地址变换机构的支持，它的缺点是必须为程序分配连续的存储区域且执行期间不能扩充不能移动并难以共享；
动态地址重定位要依赖于硬件的地址变换机构。它解决了静态重定位的各种缺点。
进行存储管理的目的是：对主存空间进行分配和管理；主存扩充；存储保护；提高空间的利用率。
主存扩充技术，通过交换和覆盖实现，其中交换是由操作系统实现，覆盖是由操作系统提供覆盖机制但由用户进行控制。
15、分区存储管理，按分区方式的不同分为固定分区、可变分区、可重定位分区。
可变分区有4种请求和释放分区的算法：最佳适应算法、最差适应算法、首次适应算法、循环首次适应算法。
为减少分区碎片而使用的可重定位算法，基本思想是移动所有已分好的分区，使其靠拢成为连续区域。
分区保护管理：有2种方法。一是“上界/下界寄存器”，另一种是“基址/限长寄存器”的方法。其中上界寄存器和基址寄存器都是放的作业的装入地址。下界寄存器放作业的结束地址，限长寄存器放作业的长度。因此调入作业所需要的物理地址必需满足：
上界寄存器＜＝物理地址＜＝下界寄存器
或 基址寄存器＜＝物理地址＜＝物理地址＋限长寄存器
分区管理方案是解决多道程序共享主存的可行方案，但它要求用户的程序必须装入地址连续的空间中。
16、页式存储管理
分页原理：将一个进程的地址空间划分成若干大小相等的区域，称为页。相应地将主存空间划分成与页相同大小的若干物理块，称为块或页框。在为进程分配主存时，将进程中若干页分别装入多个不相邻的块中。
地址结构由2部分组成：页号＋页内地址
页表：又称为页面映射表。作用是实现从页号到物理块号的地址映射。
快表：是页表方式的改良，是在地址映射机构中增加一个联想存储器（是由一组高速存储器组成），这就是所谓的快表。它用来保存当前访问频率最高的少数活动页的页号及相关信息。 另外还有一种方法是增加高速寄存器来保存页表，但这样的成本太大。
两级页表机制：是为了减少页表占用的连续地址空间，而提出的方法。使用两级或多级页表机制来存储页表。
17、分段存储管理
原理：在分段式存储管理系统中，为每个段分配一个连续的分区，而进程中的各个段可以离散地分配到主存的不同分区中。在系统中为每个进程建立一张段映射表，简称段表。每个段在表中占有一个项，记录该段在主存中的起始地址（基址）和段的长度。进程在执行时，通过查段表来找到每个段所对应的主存区。因此，段表实现了逻辑段到物理主存区的映射。
分段系统的地址结构：段号(名)＋段内地址
特点：段是信息的逻辑单位，因此分段的一个突出优点是易于实现段的共享，即若干个进程共享一个或多个段，而且对段的保护也很简单。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统方便。
段页式存储管理，原理是先将主存划分为大小相等的存储块（页框），再将用户程序按程序的逻辑关系分为若干个段，为每个段命名，然后将每个段划分为若干个页，以页架为单位离散分配。
段页式系统的地址结构：段号＋段内页号＋页内地址
18、虚拟存储管理
程序的局部性：时间局限性和空间局限性。前者指程序中的某条指令或某个存储单元一旦被执行或访问，则在不久的将来可能会再次发生（因为程序中存在着大量的循环操作）；后者指一旦程序访问了某个存储单元，则不久的将来该存储单元附近的存储单元也最有可能被访问（因为程序是顺序执行的）。
虚拟存储器，从用户的角度看，是这样一个系统，它所具有的主存容量比实际主存容量大得多。它是根据局部性原理，在一个作业运行之前只把部分程序和数据装入主存，其余部分留在磁盘上。如果要访问的页或段未在主存中(称为缺页或缺段)则将它们调入主存。
虚拟存储器的实现：
请求分页系统，它是在分页系统的基础上，增加了请求调页和页面置换功能后所形成的页式虚拟存储系统。
请求分段系统，它是在分段系统的基础上，增加了请求调段和段置换功能后所形成的段式虚拟存储系统。
请求段页式系统，它是在段页式基础上，增加了请求调页和页面置换功能后所形成的段页式虚拟存储系统。
其中请求分页系统是目前常用的一种虚拟存储器方式。其页面置换算法的好坏直接影响系统性能，不当的置换算法可能会导致系统“抖动”。常用的页面置换算法有：最佳置换算法、先进先出置换算法、最近最久未使用置换算法和最近未用置换算法。
虚拟存储器的特征：离散性、多次性、对换性、虚拟性。工作集的概念是指在某段时间间隔里，进程实际要访问的页面的集合。
虚存容量不是无限的，它受主存和外存可利用的总容量限制；虚存还受计算机总线地址结构限制。虚存的扩大是以牺牲CPU工作时间和主存与外存交换时间为代价的。虚存是由操作系统调度，采用主存外存交换技术，各道程序在必须使用时调入主存，不用的程序则调出主存。
19、设备管理，包括各种设备分配、缓冲区管理和实际物理I/O设备操作，通过管理达到提高设备利用率和方便用户使用的目的。
设备的分类
按数据组织分为：块设备 ，如磁带、磁盘
字符设备，如打印机、交互式终端
按资源分配分为：独占设备，如打印机
共享设备，如磁盘
虚拟设备，如利用假脱机技术将一台独占设备变为多个用户共享的逻辑设备。
按数据传输速率：低速设备，如键盘、鼠标
中速设备，如打印机
高速设备，如磁盘
设备管理的目标是如何提高设备的利用率，为用户提供方便统一的界面。
设备管理的任务是保证在多道程序环境下，当多个进程竞争使用设备时，按一定策略分配和管理各种设备，控制设备的各种操作，完成I/O设备与主存之间的数据交换。
20、I/O软件
IO设备管理软件分为4层：由低到高为中断处理程序－－设备驱动程序－－与设备无关的系统软件－－用户级软件
设备驱动程序是直接同硬件打交道的软件模块，它与IO设备的硬件结构有密切的联系。它的任务就是接受来自与设备无关的上层软件的抽象请求，进行与设备有关的处理。
设备的IO方式：
通道 ， 使数据的传输独立于CPU，CPU只须向通道发出IO命令，由通道完成IO任务后再向CPU发出中断信号。
DMA ， 是指数据在主存和IO设备之间直接传送，CPU只需要在首尾做些处理。
缓冲技术，缓冲区技术可提高外设利用率，使外设尽可能处于忙状态。分为硬件缓冲(由硬件寄存器实现)和软件缓冲(由操作系统实现)。缓冲技术的优点是：可以缓和CPU与IO设备间速度不匹配的矛盾；减少CPU的中断频率，放宽对中断响应时间的限制；提高CPU和IO设备之间的并行性。
21、Spooling技术
Spooling是外围设备联机操作的简称，又称为假脱机系统。Spooling实际上是用一类物理设备模拟另一类物理设备的技术，是使独占使用的设备变成多台虚拟设备的技术，是一种速度匹配技术。
Spooling由预输入程序、缓输出程序、井管理程序、输入井输出井组成。
Spooling系统中拥有一张作业表来登记进入系统的所有作业的作业名、状态、预输入表位置等信息。每个作业拥有一张预输入表来登记该作业的各个文件的情况，包括设备类、信息长度及存放位置等。（包括图）
输入井中的作业有4种状态：提交、后备、执行、完成。
22、磁盘调度，分为移臂调度和旋转调度两种。并且是先进行移臂调度，然后再进行旋转调度。因为访问磁盘最耗时的是寻道时间，所以磁盘调度的目标是减少磁盘的平均寻道时间。
磁盘驱动调度， 常用的磁盘调度算法有先来先服务FCFS、最短寻道时间SSTF、扫描算法SCAN(又称为电梯调度算法)、单向扫描调度算法CSCAN、N-Step-SCAN算法(磁臂粘着)、FSCAN算法。
FCFS的优点是简单，缺点是平均寻道时间太长；SSTF的优点是每次的寻道时间最短，缺点是不能保证平均寻道时间最短，且有高度局部化的倾向，会推迟某些请求以致引起饥饿；SCAN的优点是避免了饥饿现象，缺点是可能有个别请求被严重延迟；C－SCAN为的是避免SCAN的缺点
旋转调度算法， 该算法用来计算，当移动臂定位后，有多个进程等待访问该柱面时，这些进程的访问顺序。系统应该选择延迟时间最短的进程对磁盘的扇区进行访问。
23、文件：具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。文件是一种抽象机制，它隐藏了硬件和实现细节。
文件管理系统：就是操作系统中实现文件统一管理的一组软件和相关数据的集合，是专门负责管理和存取文件信息的软件机构，简称文件系统。
文件系统的功能：按名存取、统一的用户接口、并发访问和控制、安全性控制、优化性能、差错恢复。
文件的结构和组织：文件的结构是指文件的组织形式。从用户的角度看到的文件组织形式称为文件的逻辑结构；从实现的角度看文件在存储器上的存放方式，称为文件的物理结构。
文件的逻辑结构分为2类：一是有结构的记录式文件；另一是无结构的流式文件。
文件的物理结构，决定了文件的逻辑块号到物理块号的转换方式。常见的物理结构有：连续结构(顺序结构)、链接结构、索引结构、多个物理块的索引表（链接、多重索引表、unix的索引结构）。索引顺序文件既适合于交互方式应用，也适合于批处理方式应用。
文件目录，就是文件控制块的有序集合。文件控制块FCB是用于描述和控制文件的数据结构。常见的目录结构有3种：一级目录结构，二级目录结构，多级目录结构。
文件的存取方法有顺序和随机两种。
磁盘分配表，就是外存进行空间管理的数据结构。
常用的空闲空间管理方法：位示图、空闲表法、空闲链表及成组链接法。
文件的使用：文件系统为每个文件与该文件在磁盘上的存放位置建立了对应关系。文件系统通过用户给出的文件名查找对应文件的存放位置并读出内容。在多用户环境下，操作系统为每个文件建立和维护关于访问权限等方面的信息。为此操作系统在操作级和编程级为用户提供文件服务。
文件共享：是指不同用户使用同一文件。有多种共享形式，采用文件名与文件说明分离的目录结构有利于实现文件共享。
在Unix系统中允许多用户基于索引结点的共享，或利用符号链接共享同一个文件。基于索引结点的共享方式又有静态共享和动态共享两种方式。这样子，会在打开文件表、系统打开文件表、内存i结点表及磁盘间形成一副关系图。这种关系图在辅导教材的155页的几个例子中有图解，可以体味。
符号链接会增加系统的读盘次数，而硬链接的共享文件的目录文件表目中已包括了共享文件的索引结点号。
文件保护：文件系统对文件的保护采用存取控制方式进行。存取控制就是不同的用户对文件的访问规定不同的访问权限。常用的存取控制方式有，存取控制矩阵、存取控制表、用户权限表、密码。
存取控制矩阵，就是一个二维矩阵，一维列出全部用户，另一维列出全部的文件，每个矩阵元素表示某个用户对某个文件的存取权限。
存取控制表，就是按用户对文件的访问权力的差别对用户进行分类，该存取控制表可存放在每个文件的文件控制块中。UNIX使用的这种方式，用9位二进制数表示三类用户对文件的存取权限，该权限存在文件索引节点的di_mode中。
用户权限列表，以用户或用户组为单位将用户可存取的文件集中起来存入表中，表中的每个条目表示该用户对相应文件的存取权限。这相当于把存取控制矩阵简化为一行。
系统的安全性：分为4个级别，系统级、用户级、目录级和文件级。
文件系统的可靠性：转储与恢复，日志文件，文件系统的一致性。
24、作业，是系统为完成一个用户的计算任务所做的工作总和。作业中的每个步骤又称为作业步。
作业控制：分为脱机控制和联机控制两种方式。在脱机控制中用户必须使用作业控制语言（JCL）编写作业说明书，并同作来一同提高给系统
作业控制块JCB：是记录作业各种有关信息的登记表。JCB是作业存在的惟一标志，其中包括用户名、作业名和状态标志等信息。JCB被用于在输入井中形成作业后备队列。
作业的4种状态：提交、后备、执行和完成。注意它们的状态转换图。
作业调度算法：先来先服务算法、短作业优先、响应比高者优先、优先级、均衡调度算法。其中响应比是取值于“作业响应时间除以作业执行时间”，作业响应时间是作业时间与作业等待时间之和。
作业周转时间 ＝ 作业完成时间－作业提交时间 ，N个作业的平均周转时间就是取N个作业的周转时间平均值。
作业带权周转时间 ＝ （作业完成时间－作业提交时间）/ 作业执行时间
25、UNIX操作系统
UNIX系统的结构：它是一种多用户、多任务的分时操作系统，一般由存储管理、进程管理、设备管理和文件系统管理几个部分组成。
unix文件系统的目录结构是树形带交叉勾连的，根目录记为"/"。目录是一个包含目录项的文件。进程可以通过系统调用访问文件。unix文件系统的布局如图所示：
｜引导块｜超级块｜索引结点区｜数据存储区｜
Unix进程的组成：由控制块PCB、正文段和数据段组成。
Unix进程的控制：有一个进程控制子系统，提供了如fork,exec,exit,wait,signal,kill,msgsnd,msgrcv等系统调用，以完成进程的同步、通信、存储及调度。
Unix进程的调度：采用优先数算法，进程的优先数随进程的运行情况而变化。
Unix进程的存储：早期采用对换技术；高版本的Unix的主存管理采用的分页式虚拟存储机制，以对换技术作为辅助手段。
Unix的设备管理：Unix上包括两类设备，即块设备和字符设备。Unix设备管理有这样的特点，
块设备与字符设备具有相同的层次结构（对它们的控制方法和所采用的数据结构、层次结构相同）；
将设备作为一个特殊文件并赋予一个文件名（文件存取与对设备的使用，具有了统一的接口）；
采用完善的缓冲区管理技术（预先读、异步写、延迟写）。
26、Windows操作系统
Windows的体系结构：通过硬件实现了核心态和用户态两种特权状态。核心组件使用了面向对象的设计原则，一般不能直接访问某个数据结构中由单个组件维护的消息，这些组件只能使用外部接口传送参数访问或修改这些数据。
Windows的核心态模块有：核心、执行体、硬件抽象层、设备驱动程序、图形引擎。
Windows的文件系统：NTFS使用64位簇进行索引，NTFS的特征有可恢复性、安全性、大磁盘和大文件、多数据流和通用索引功能。
在Windows中进程是资源分配的单位，并将进程作为对象来进行管理。Windows的线程是内核线程，是处理机的调度单位。
存储管理，Windows默认使用二级页面表结构来转换物理地址和虚拟地址。
Windows的设备管理，建立了广义的资源管理概念，并统一地用对象模型来描述和规范化，大大降低了系统的复杂性。在输入输出上，建立了一个一致的高层界面－－IO设备虚拟界面。将所有的读写数据看成直接送往虚拟文件的字节流。
三、操作系统知识
1、操作系统的定义：是管理计算机中各种软件、硬件资源的程序和相关文档的集合，是一种系统软件。
操作系统能有效的组织和管理系统中的各种软、硬件资源，合理地组织计算机工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。
操作系统的两个重要作用：
通过资源管理，提高系统的使用效率；
改善人机界面，向用户提供友好的工作环境。
操作系统的4个特征：并发性、共享性、虚拟性、不确定性。
操作系统的5个管理功能：进程管理、文件管理、存储管理、设备管理、作业管理
操作系统的分类：
批处理系统，计算机自动、顺序地执行作业流产生的每一个作业，以节省人工操作时间和提高机器的使用效率。分为单道批处理系统和多道批处理系统。优点是同一批内的各作业次次执行，改善了cpu,io的使用效率，提高了吞吐量。缺点是磁盘需要人工装卸，作业需要人工分类，监督程序易受用户程序破坏，缺少交互性。
分时系统， 具有如下特征：多路性、独立性、交互性、及时性。
实时系统，分为实时控制系统和实时信息处理系统。主要特点有：快速的响应时间、有限的交互能力、高可靠性
网络操作系统，使得计算机更有效地共享网络资源，为网络用户提供所需各种服务的软件和有关协议的集合。
分布式操作系统，是由多个分散的计算机经网络连接而成，各主机无主次之分。为分布式计算机配置的操作系统称为分布式操作系统。
微机操作系统
嵌入式操作系统
2、研究操作系统的观点
资源管理的观点：从这种观点看，操作系统的管理对象是计算机系统的资源，操作系统则是管理计算机系统的程序集合。这种观点是在共享的前提下以资源分配、使用和回收为出发点，考虑操作系统各部分程序的功能和算法。
虚拟机的观点：操作系统加裸机构成虚拟计算机。虚拟机的观点是从功能分解的角度出发，考虑操作系统的结构，将操作系统分成若干层次，每一层完成特定的功能。
3、顺序程序执行时的特征：顺序性、封闭性、可再现性；
并发程序执行时的特征：非封闭性、程序和机器执行程序的活动不在一一对应、并发程序间的相互制约性。
引入进程的原因：由于程序并发执行破坏了程序的封闭性和可再现性，使得程序和执行程序的活动不在一一对应，此时用静态的程序概念已经不能描述系统中程序动态执行的过程，所以引入了进程。
4、进程的定义：就是程序的一次执行，该程序可以和其它程序并发执行。
进程的组成：进程通常是由程序、数据及进程控制块（PCB）组成的。
进程的程序部分是进程执行时不可修改部分，它描述了进程需要完成的功能；
进程的数据部分是进程的可修改部分；
进程控制块是进程的描述信息和控制信息，是进程存在的惟一标志。
进程和程序的区别是：进程具有状态而程序没有。
5、进程的状态及状态间的切换
三态模型：运行、就绪、阻塞。
五态模型：新建态、终止态、运行、就绪、阻塞。
新建态：对应于进程刚刚被创建时还没有被提交，并等待系统完成创建进程的所有必要信息的状态。整个过程分为两个阶段，一是为一个新建进程创建必要的管理信息，另一是让进程进入就绪状态。因为有了新建态，操作系统可以根据系统的性能和主存的容量限制而推迟新建态的提交。
终止态也分为两个阶段，一是等待操作系统进行善后处理，另一是释放主存。
具有挂起状态的进程状态：当系统资源不能满足所有进程的运行要求时，必须将某些进程挂起，放在磁盘对换区，暂时不参加调度，以平衡系统负载。有这样几个状态：活跃就绪、静止就绪、活跃阻塞、静止阻塞。
6、进程的控制，就是对系统中所有进程从创建到消亡的全过程实施有效的控制。操作系统的内核为系统实现进程控制和存储管理提供了有效的控制机制。
大多数操作系统内核均包含支撑功能和资源管理功能。
支撑功能：中断处理、时钟管理、原语操作。
原语是由若干条机器指令构成的，用于完成特定功能的一段程序。内核在执行某些基本操作时往往是通过原语操作实现的。原语在执行过程中不可分割。内核中包含的原语有进程控制、进程通信、资源管理等。
资源管理功能：进程管理、存储器管理、设备管理。
7、进程间通信
进程间的同步：一般来说，一个进程相对于另一个进程的运行速度是不确定的，即进程是在异步环境下运行。每个进程都以各自独立的不可预知的速度向前推进，但相互合作的进程需要在某些确定点上协调它们的工作，当一个进程到达了这些点后，除非另一进程已完成了某些操作，否则就不得不停下来等等这些操作结束。
进程间的互斥：在多道程序系统中，各进程可以共享各类资源，但有些资源一次只能供一个进程使用，称为临界资源(critial resource)。同步是进程间的直接制约问题，互斥是进程间的间接制约问题。
临界区(critial section)是对临界资源实施操作的那段程序。互斥临界区管理的原则为：有空即进、无空则等、有限等待、让权等待。
8、整形信号量与PV操作
整形信号量是一个整形变量，根据控制对象的不同赋不同的值。信号量分为两类：
公用信号量：实现进程间的互斥，每个相关进程即可对它施行P操作也可以进行V操作，初值为1或资源的数目；
私用信号量：实现进程间的同步，只有一个进程可以对它施行P操作，其它进程只能做V操作，初值为0或某个正整数。
信号量S的物理意义：S＞＝0表示某资源的可用数，S＜0则其绝对值表示阻塞队列中等待该资源的进程数。
PV操作是实现进程同步与互斥的常用方法。PV操作是低级通信原语，其中P操作表示申请一个资源，V操作表示释放一个资源。
P操作定义：S:=S-1，若S＞＝0，则执行P操作的进程继续执行；否则若S＜0，则该进程为阻塞状态，并将其插入阻塞队列。
V操作定义：S:=S+1，若S＞0，则执行V操作的进程继续执行；否则，若S＜＝0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，执行V操作的进程继续执行。
利用PV操作实现进程的互斥：令信号量mutex的初值为1，当进入临界区时执行P操作，临界区时执行V操作。
P(mutex)
临界区
V(mutex)
怎样利用PV操作实现进程的同步：可用一个信号量与消息联系起来，当信号量的值为0时表示希望的消息未产生，当信号量的值为非0时表示希望的消息已经存在。假定用信号量S表示某条消息，进程可以通过调用P操作测试消息是否到达，调用V操作通知消息已准备好。最典型的是单缓冲区的生产者和消费者的同步问题。如果采用PV操作来实现进程PA和进程PB间的管道通信，并且保证这两个进程并发执行的正确性，则至少需要2个信号量，信号量的初值分别为0、1。
9、高级通信原语，因为PV操作不足以描述复杂的进程间的信息交换，所以引入高级通信原语。
高级通信原语有这么几种：共享存储系统、消息传递系统、管道通信。
进程通信有直接和间接两种方式。间接方式是以信箱以为媒介。
10、管程(monitor)：另一种同步机制，采用资源集中管理的方法，将系统中的资源用某种数据结构抽象地表示出来。由于临界区是访问共享资源的代码段，因而建立一个管程来管理进程提出的访问请求。采用这种方式对共享资源的管理就可以借助数据结构及在其上实施操作的若干过程来进行。对共享资源的申请和释放可以通过过程在数据结构上的操作来实现。
11、进程调度，在某些系统中一个作业从提交到完成需要经历高、中、低三级的调度。
高级调度（又称长调度、作业调度或接纳调度），它决定输入池中的哪个后备作业可以调入主系统做好运行的准备，成为一个或一组就绪进程。
中级调度（又称对换调度），它决定处于交换区中的哪个就绪进程可以调入主存，以便直接参与CPU的竞争。
低级调度（又称进程调度），它决定处于主存中的哪个进程使用CPU。
调度方式，是指当有更高优先级的进程来到时如何分配CPU。调度的方式分为可剥夺式和不可剥夺式两种。
常用的调度算法：先来先服务，主要用于宏观调度，有利于长作业，有利于CPU繁忙的作业；
时间片轮转，主要用于微观调度，提高了并发性和响应时间，最终提高了资源利用率；
优先级调度， 分为静态和动态两种；
多级反馈调度，是在时间片轮转和优先级算法的基础上改进得到。其特点是：照顾了短进程以提高系统吞吐量，照顾I/O型进程以获得较好的I/O设备利用率并缩短响应时间，不必估计进程的执行时间和动态调节优先级。
12、死锁：就是指两个以上的进程相互请求对方已经占有的资源时而导致无法继续运行下去的现象。
几种会产生死锁的情况：进程推进程顺序不当，同类资源分配不当，PV使用不当。
进程资源有向图：由方框、圆圈和有向边3部分组成。其中资源用方框表示，进程用圆圈表示。在方框中每一个小圆圈代表一个资源。有向边分别代表请求资源和分配资源。
死锁产生的原因：因为竞争资源或进程推进顺序非法。进程推进顺序仍是关于进程请求和释放资源的顺序。
死锁产生的4个必要条件：互斥条件、请求保持条件、不可剥夺条件、环路条件。
互斥是说进程对所要求的资源有排它性控制。请求保持是说进程断续地请求资源，但后续的资源被阻塞。环路是指在发生死锁时在进程资源有向图中，每个进程都占有了下一个进程请求的一个或多个资源。
死锁的4种处理：鸵鸟策略；
预防策略，即破坏死锁产生的4个必要条件之一；
避免策略，即精心分配资源，主动回避死锁；
检测与解除死锁
13、线程
传统的进程有两个基本属性，即可拥有资源的独立单位，和可独立调度、分配的基本单位。引入线程后，将传统进程的两个属性分开，线程作为可独立调度和分配的基本单位，进程作为独立拥有资源的单位。因此，用户可以通过创建线程来完成任务，以减少程序并发执行时的时空开销。
14、存储器的结构：(寄存器)--缓存－主存－辅存。
虚拟地址，又称为逻辑地址、相对地址、程序地址。它是从0号单元开始编址，并顺序分配所有的符号名所对应的地址单元，它不是主存中的真实地址。
地址空间，又称逻辑地址、虚地址。
存储空间，又称物理地址空间，是物理地址的集合。相对地址空间通过地址再定位机构转换到绝对地址空间。
重定位：程序的逻辑地址被转换成主存的物理地址的过程称为地址重定位。分为静态重定位和动态重定位。
静态地址重定位的优点是无需硬件地址变换机构的支持，它的缺点是必须为程序分配连续的存储区域且执行期间不能扩充不能移动并难以共享；
动态地址重定位要依赖于硬件的地址变换机构。它解决了静态重定位的各种缺点。
进行存储管理的目的是：对主存空间进行分配和管理；主存扩充；存储保护；提高空间的利用率。
主存扩充技术，通过交换和覆盖实现，其中交换是由操作系统实现，覆盖是由操作系统提供覆盖机制但由用户进行控制。
15、分区存储管理，按分区方式的不同分为固定分区、可变分区、可重定位分区。
可变分区有4种请求和释放分区的算法：最佳适应算法、最差适应算法、首次适应算法、循环首次适应算法。
为减少分区碎片而使用的可重定位算法，基本思想是移动所有已分好的分区，使其靠拢成为连续区域。
分区保护管理：有2种方法。一是“上界/下界寄存器”，另一种是“基址/限长寄存器”的方法。其中上界寄存器和基址寄存器都是放的作业的装入地址。下界寄存器放作业的结束地址，限长寄存器放作业的长度。因此调入作业所需要的物理地址必需满足：
上界寄存器＜＝物理地址＜＝下界寄存器
或 基址寄存器＜＝物理地址＜＝物理地址＋限长寄存器
分区管理方案是解决多道程序共享主存的可行方案，但它要求用户的程序必须装入地址连续的空间中。
16、页式存储管理
分页原理：将一个进程的地址空间划分成若干大小相等的区域，称为页。相应地将主存空间划分成与页相同大小的若干物理块，称为块或页框。在为进程分配主存时，将进程中若干页分别装入多个不相邻的块中。
地址结构由2部分组成：页号＋页内地址
页表：又称为页面映射表。作用是实现从页号到物理块号的地址映射。
快表：是页表方式的改良，是在地址映射机构中增加一个联想存储器（是由一组高速存储器组成），这就是所谓的快表。它用来保存当前访问频率最高的少数活动页的页号及相关信息。 另外还有一种方法是增加高速寄存器来保存页表，但这样的成本太大。
两级页表机制：是为了减少页表占用的连续地址空间，而提出的方法。使用两级或多级页表机制来存储页表。
17、分段存储管理
原理：在分段式存储管理系统中，为每个段分配一个连续的分区，而进程中的各个段可以离散地分配到主存的不同分区中。在系统中为每个进程建立一张段映射表，简称段表。每个段在表中占有一个项，记录该段在主存中的起始地址（基址）和段的长度。进程在执行时，通过查段表来找到每个段所对应的主存区。因此，段表实现了逻辑段到物理主存区的映射。
分段系统的地址结构：段号(名)＋段内地址
特点：段是信息的逻辑单位，因此分段的一个突出优点是易于实现段的共享，即若干个进程共享一个或多个段，而且对段的保护也很简单。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统方便。
段页式存储管理，原理是先将主存划分为大小相等的存储块（页框），再将用户程序按程序的逻辑关系分为若干个段，为每个段命名，然后将每个段划分为若干个页，以页架为单位离散分配。
段页式系统的地址结构：段号＋段内页号＋页内地址
18、虚拟存储管理
程序的局部性：时间局限性和空间局限性。前者指程序中的某条指令或某个存储单元一旦被执行或访问，则在不久的将来可能会再次发生（因为程序中存在着大量的循环操作）；后者指一旦程序访问了某个存储单元，则不久的将来该存储单元附近的存储单元也最有可能被访问（因为程序是顺序执行的）。
虚拟存储器，从用户的角度看，是这样一个系统，它所具有的主存容量比实际主存容量大得多。它是根据局部性原理，在一个作业运行之前只把部分程序和数据装入主存，其余部分留在磁盘上。如果要访问的页或段未在主存中(称为缺页或缺段)则将它们调入主存。
虚拟存储器的实现：
请求分页系统，它是在分页系统的基础上，增加了请求调页和页面置换功能后所形成的页式虚拟存储系统。
请求分段系统，它是在分段系统的基础上，增加了请求调段和段置换功能后所形成的段式虚拟存储系统。
请求段页式系统，它是在段页式基础上，增加了请求调页和页面置换功能后所形成的段页式虚拟存储系统。
其中请求分页系统是目前常用的一种虚拟存储器方式。其页面置换算法的好坏直接影响系统性能，不当的置换算法可能会导致系统“抖动”。常用的页面置换算法有：最佳置换算法、先进先出置换算法、最近最久未使用置换算法和最近未用置换算法。
虚拟存储器的特征：离散性、多次性、对换性、虚拟性。工作集的概念是指在某段时间间隔里，进程实际要访问的页面的集合。
虚存容量不是无限的，它受主存和外存可利用的总容量限制；虚存还受计算机总线地址结构限制。虚存的扩大是以牺牲CPU工作时间和主存与外存交换时间为代价的。虚存是由操作系统调度，采用主存外存交换技术，各道程序在必须使用时调入主存，不用的程序则调出主存。
19、设备管理，包括各种设备分配、缓冲区管理和实际物理I/O设备操作，通过管理达到提高设备利用率和方便用户使用的目的。
设备的分类
按数据组织分为：块设备 ，如磁带、磁盘
字符设备，如打印机、交互式终端
按资源分配分为：独占设备，如打印机
共享设备，如磁盘
虚拟设备，如利用假脱机技术将一台独占设备变为多个用户共享的逻辑设备。
按数据传输速率：低速设备，如键盘、鼠标
中速设备，如打印机
高速设备，如磁盘
设备管理的目标是如何提高设备的利用率，为用户提供方便统一的界面。
设备管理的任务是保证在多道程序环境下，当多个进程竞争使用设备时，按一定策略分配和管理各种设备，控制设备的各种操作，完成I/O设备与主存之间的数据交换。
20、I/O软件
IO设备管理软件分为4层：由低到高为中断处理程序－－设备驱动程序－－与设备无关的系统软件－－用户级软件
设备驱动程序是直接同硬件打交道的软件模块，它与IO设备的硬件结构有密切的联系。它的任务就是接受来自与设备无关的上层软件的抽象请求，进行与设备有关的处理。
设备的IO方式：
通道 ， 使数据的传输独立于CPU，CPU只须向通道发出IO命令，由通道完成IO任务后再向CPU发出中断信号。
DMA ， 是指数据在主存和IO设备之间直接传送，CPU只需要在首尾做些处理。
缓冲技术，缓冲区技术可提高外设利用率，使外设尽可能处于忙状态。分为硬件缓冲(由硬件寄存器实现)和软件缓冲(由操作系统实现)。缓冲技术的优点是：可以缓和CPU与IO设备间速度不匹配的矛盾；减少CPU的中断频率，放宽对中断响应时间的限制；提高CPU和IO设备之间的并行性。
21、Spooling技术
Spooling是外围设备联机操作的简称，又称为假脱机系统。Spooling实际上是用一类物理设备模拟另一类物理设备的技术，是使独占使用的设备变成多台虚拟设备的技术，是一种速度匹配技术。
Spooling由预输入程序、缓输出程序、井管理程序、输入井输出井组成。
Spooling系统中拥有一张作业表来登记进入系统的所有作业的作业名、状态、预输入表位置等信息。每个作业拥有一张预输入表来登记该作业的各个文件的情况，包括设备类、信息长度及存放位置等。（包括图）
输入井中的作业有4种状态：提交、后备、执行、完成。
22、磁盘调度，分为移臂调度和旋转调度两种。并且是先进行移臂调度，然后再进行旋转调度。因为访问磁盘最耗时的是寻道时间，所以磁盘调度的目标是减少磁盘的平均寻道时间。
磁盘驱动调度， 常用的磁盘调度算法有先来先服务FCFS、最短寻道时间SSTF、扫描算法SCAN(又称为电梯调度算法)、单向扫描调度算法CSCAN、N-Step-SCAN算法(磁臂粘着)、FSCAN算法。
FCFS的优点是简单，缺点是平均寻道时间太长；SSTF的优点是每次的寻道时间最短，缺点是不能保证平均寻道时间最短，且有高度局部化的倾向，会推迟某些请求以致引起饥饿；SCAN的优点是避免了饥饿现象，缺点是可能有个别请求被严重延迟；C－SCAN为的是避免SCAN的缺点
旋转调度算法， 该算法用来计算，当移动臂定位后，有多个进程等待访问该柱面时，这些进程的访问顺序。系统应该选择延迟时间最短的进程对磁盘的扇区进行访问。
23、文件：具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。文件是一种抽象机制，它隐藏了硬件和实现细节。
文件管理系统：就是操作系统中实现文件统一管理的一组软件和相关数据的集合，是专门负责管理和存取文件信息的软件机构，简称文件系统。
文件系统的功能：按名存取、统一的用户接口、并发访问和控制、安全性控制、优化性能、差错恢复。
文件的结构和组织：文件的结构是指文件的组织形式。从用户的角度看到的文件组织形式称为文件的逻辑结构；从实现的角度看文件在存储器上的存放方式，称为文件的物理结构。
文件的逻辑结构分为2类：一是有结构的记录式文件；另一是无结构的流式文件。
文件的物理结构，决定了文件的逻辑块号到物理块号的转换方式。常见的物理结构有：连续结构(顺序结构)、链接结构、索引结构、多个物理块的索引表（链接、多重索引表、unix的索引结构）。索引顺序文件既适合于交互方式应用，也适合于批处理方式应用。
文件目录，就是文件控制块的有序集合。文件控制块FCB是用于描述和控制文件的数据结构。常见的目录结构有3种：一级目录结构，二级目录结构，多级目录结构。
文件的存取方法有顺序和随机两种。
磁盘分配表，就是外存进行空间管理的数据结构。
常用的空闲空间管理方法：位示图、空闲表法、空闲链表及成组链接法。
文件的使用：文件系统为每个文件与该文件在磁盘上的存放位置建立了对应关系。文件系统通过用户给出的文件名查找对应文件的存放位置并读出内容。在多用户环境下，操作系统为每个文件建立和维护关于访问权限等方面的信息。为此操作系统在操作级和编程级为用户提供文件服务。
文件共享：是指不同用户使用同一文件。有多种共享形式，采用文件名与文件说明分离的目录结构有利于实现文件共享。
在Unix系统中允许多用户基于索引结点的共享，或利用符号链接共享同一个文件。基于索引结点的共享方式又有静态共享和动态共享两种方式。这样子，会在打开文件表、系统打开文件表、内存i结点表及磁盘间形成一副关系图。这种关系图在辅导教材的155页的几个例子中有图解，可以体味。
符号链接会增加系统的读盘次数，而硬链接的共享文件的目录文件表目中已包括了共享文件的索引结点号。
文件保护：文件系统对文件的保护采用存取控制方式进行。存取控制就是不同的用户对文件的访问规定不同的访问权限。常用的存取控制方式有，存取控制矩阵、存取控制表、用户权限表、密码。
存取控制矩阵，就是一个二维矩阵，一维列出全部用户，另一维列出全部的文件，每个矩阵元素表示某个用户对某个文件的存取权限。
存取控制表，就是按用户对文件的访问权力的差别对用户进行分类，该存取控制表可存放在每个文件的文件控制块中。UNIX使用的这种方式，用9位二进制数表示三类用户对文件的存取权限，该权限存在文件索引节点的di_mode中。
用户权限列表，以用户或用户组为单位将用户可存取的文件集中起来存入表中，表中的每个条目表示该用户对相应文件的存取权限。这相当于把存取控制矩阵简化为一行。
系统的安全性：分为4个级别，系统级、用户级、目录级和文件级。
文件系统的可靠性：转储与恢复，日志文件，文件系统的一致性。
24、作业，是系统为完成一个用户的计算任务所做的工作总和。作业中的每个步骤又称为作业步。
作业控制：分为脱机控制和联机控制两种方式。在脱机控制中用户必须使用作业控制语言（JCL）编写作业说明书，并同作来一同提高给系统
作业控制块JCB：是记录作业各种有关信息的登记表。JCB是作业存在的惟一标志，其中包括用户名、作业名和状态标志等信息。JCB被用于在输入井中形成作业后备队列。
作业的4种状态：提交、后备、执行和完成。注意它们的状态转换图。
作业调度算法：先来先服务算法、短作业优先、响应比高者优先、优先级、均衡调度算法。其中响应比是取值于“作业响应时间除以作业执行时间”，作业响应时间是作业时间与作业等待时间之和。
作业周转时间 ＝ 作业完成时间－作业提交时间 ，N个作业的平均周转时间就是取N个作业的周转时间平均值。
作业带权周转时间 ＝ （作业完成时间－作业提交时间）/ 作业执行时间
25、UNIX操作系统
UNIX系统的结构：它是一种多用户、多任务的分时操作系统，一般由存储管理、进程管理、设备管理和文件系统管理几个部分组成。
unix文件系统的目录结构是树形带交叉勾连的，根目录记为"/"。目录是一个包含目录项的文件。进程可以通过系统调用访问文件。unix文件系统的布局如图所示：
｜引导块｜超级块｜索引结点区｜数据存储区｜
Unix进程的组成：由控制块PCB、正文段和数据段组成。
Unix进程的控制：有一个进程控制子系统，提供了如fork,exec,exit,wait,signal,kill,msgsnd,msgrcv等系统调用，以完成进程的同步、通信、存储及调度。
Unix进程的调度：采用优先数算法，进程的优先数随进程的运行情况而变化。
Unix进程的存储：早期采用对换技术；高版本的Unix的主存管理采用的分页式虚拟存储机制，以对换技术作为辅助手段。
Unix的设备管理：Unix上包括两类设备，即块设备和字符设备。Unix设备管理有这样的特点，
块设备与字符设备具有相同的层次结构（对它们的控制方法和所采用的数据结构、层次结构相同）；
将设备作为一个特殊文件并赋予一个文件名（文件存取与对设备的使用，具有了统一的接口）；
采用完善的缓冲区管理技术（预先读、异步写、延迟写）。
26、Windows操作系统
Windows的体系结构：通过硬件实现了核心态和用户态两种特权状态。核心组件使用了面向对象的设计原则，一般不能直接访问某个数据结构中由单个组件维护的消息，这些组件只能使用外部接口传送参数访问或修改这些数据。
Windows的核心态模块有：核心、执行体、硬件抽象层、设备驱动程序、图形引擎。
Windows的文件系统：NTFS使用64位簇进行索引，NTFS的特征有可恢复性、安全性、大磁盘和大文件、多数据流和通用索引功能。
在Windows中进程是资源分配的单位，并将进程作为对象来进行管理。Windows的线程是内核线程，是处理机的调度单位。
存储管理，Windows默认使用二级页面表结构来转换物理地址和虚拟地址。
Windows的设备管理，建立了广义的资源管理概念，并统一地用对象模型来描述和规范化，大大降低了系统的复杂性。在输入输出上，建立了一个一致的高层界面－－IO设备虚拟界面。将所有的读写数据看成直接送往虚拟文件的字节流。
软考学习笔记-数据库工程师第二章- 数据结构与算法
软考学习笔记-数据库工程师第二章- 数据结构与算法
第二章 数据结构与算法
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
for(j=0;j
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
for(j=i+1;j
temp=data[i];data[i]=data[k];data[k]=temp;
}
}
}
希尔排序，又称为缩小增量排序。它是在直接插入排序的基础上加以改进得到的排序方法。基本思想就是：设定一个初始间隔d,d
快速排序，基本思想是通过一趟排序将待排序的记录分割为独立的两部分，其中一部分的关键字均比另一部分小，然后再分别对这两部分记录继续进行排序。具体做法：在头尾设两个指针low,high，分别指向第一个元素和最后一个元素。设枢轴记录为正向（返向）的第一个记录。当初始序列有序时，快速排序蜕变为冒泡排序，此时算法的时间复杂度为n*n。
例如，对50个整数进行快速排序时，因为初始序列有序，所以排序过程退化为冒泡排序，总过程中的比较次数为49+48+...+1 = 49*50/2
堆排序，基本思想是对一组待排序记录的关键字，首选把它们按堆的定义排成一个序列，从而输出堆顶的最小关键字。然后将剩余关键字再调整成堆，便得到次小关键字，反复进行，直至全部关键字排成有序序列。
归并排序，是将两个或多个有序表合并成一个新的有序表。是一种稳定的排序。
基数排序，是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。它不是基于关键字比较的排序方法，其平均时间复杂度为O(d*n)，适合于n值很大而关键字较少的序列。
基于关键字比较的内部排序方法的时间复杂度的下限为O(nlogn)，简单排序、希尔排序、快速排序、堆排序和归并排序是要熟练掌握的排序方法。（重要）
排序方法好坏的两条因素：执行算法的时间；执行算法所需要的附加空间。
常用的外部排序方法是归并排序。
25、分治法，将一个规模为n的问题逐步分解为k个规模更小的子问题，这些子问题互相独立且与原问题性质相同，逐个解决分解出的子问题，由这些子问题的解构造出原问题的解，当k=2时称为二分法。如解决棋盘覆盖问题。
分治法适用的问题一般具有这些特征：
原问题可以分解成多个子问题，这些子问题与原问题相比只是规模的下降而其结构和求解方法与原问题相同；
若子问题的规模足够小，则直接求解，否则递归地求解子问题；
在得到各子问题的解后，能采用某种方法构造出原问题的解。
动态规划法，与分治法类似也是先将待求解的问题分解成若个个子问题，先求解子问题，然后从子问题的解得到原问题的解。不同的是适合于动态规划法求解的问题所分解得到的子问题之间往往不是独立的。动态规划法常用来求解具有最优性质的问题。即问题的最优解包含了其子问题的最优解。如求解多边形游戏问题。
设计动态规划法的步骤为：
1）找出最优解的性质，并刻画其结构特征；
2）递归地定义最优值；
3）以向前或向后处理方式计算出最优值；
4）根据计算最优值得到的信息，构造最优解。
贪心法，通过一系列的选择来得到一个问题的解，它所做的每一次选择都是当前情况下某种意义的最好选择，即贪心选择。如果待求解的问题具有最优子结构特征，也就是原问题的最优解包含子问题的最优解，并且可以通过局部的贪心选择来达到问题的全局最优解时，可通过贪心法进行求解。贪心标准的选择和问题的结构决定是否可以使用贪心法。如用于二分最小覆盖问题。
回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结点出发搜索解空间树。算法搜索到解空间树的任意结点时，首先判断该结点是否包含问题的解。如果不包含则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则进入这棵子树继续按深度优先搜索。如收费公路重建问题。
分支限界法，它类似于回溯法，也是在解空间中搜索问题解的算法，但分支限界法求解的目标是找出满足条件的一个解，如有多个解则要找出某种意义下的最优解。分支限界法以广度优先或以最小耗费优先的方式搜索解空间树。如最大完备子图问题。
26、算法的几个基本特征
有穷性，确定性，能行性，输入，输出。
程序 ＝ 数据结构 ＋ 算法
内容关键字：
线性表、栈、队、串、数组
树、二叉树、森林、线索二叉树、霍夫曼树
图、有向图、无向图、最小生成树、拓朴排序、关键路径
查找、静态查找（顺序、折半、分块）、动态查找（二叉排序树、平衡二叉树、哈希表）
排序、直接插入、简单选择、冒泡、希尔、快速、堆、归并、基数
第二章 数据结构与算法
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
for(j=0;j
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
for(j=i+1;j
temp=data[i];data[i]=data[k];data[k]=temp;
}
}
}
希尔排序，又称为缩小增量排序。它是在直接插入排序的基础上加以改进得到的排序方法。基本思想就是：设定一个初始间隔d,d
快速排序，基本思想是通过一趟排序将待排序的记录分割为独立的两部分，其中一部分的关键字均比另一部分小，然后再分别对这两部分记录继续进行排序。具体做法：在头尾设两个指针low,high，分别指向第一个元素和最后一个元素。设枢轴记录为正向（返向）的第一个记录。当初始序列有序时，快速排序蜕变为冒泡排序，此时算法的时间复杂度为n*n。
例如，对50个整数进行快速排序时，因为初始序列有序，所以排序过程退化为冒泡排序，总过程中的比较次数为49+48+...+1 = 49*50/2
堆排序，基本思想是对一组待排序记录的关键字，首选把它们按堆的定义排成一个序列，从而输出堆顶的最小关键字。然后将剩余关键字再调整成堆，便得到次小关键字，反复进行，直至全部关键字排成有序序列。
归并排序，是将两个或多个有序表合并成一个新的有序表。是一种稳定的排序。
基数排序，是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。它不是基于关键字比较的排序方法，其平均时间复杂度为O(d*n)，适合于n值很大而关键字较少的序列。
基于关键字比较的内部排序方法的时间复杂度的下限为O(nlogn)，简单排序、希尔排序、快速排序、堆排序和归并排序是要熟练掌握的排序方法。（重要）
排序方法好坏的两条因素：执行算法的时间；执行算法所需要的附加空间。
常用的外部排序方法是归并排序。
25、分治法，将一个规模为n的问题逐步分解为k个规模更小的子问题，这些子问题互相独立且与原问题性质相同，逐个解决分解出的子问题，由这些子问题的解构造出原问题的解，当k=2时称为二分法。如解决棋盘覆盖问题。
分治法适用的问题一般具有这些特征：
原问题可以分解成多个子问题，这些子问题与原问题相比只是规模的下降而其结构和求解方法与原问题相同；
若子问题的规模足够小，则直接求解，否则递归地求解子问题；
在得到各子问题的解后，能采用某种方法构造出原问题的解。
动态规划法，与分治法类似也是先将待求解的问题分解成若个个子问题，先求解子问题，然后从子问题的解得到原问题的解。不同的是适合于动态规划法求解的问题所分解得到的子问题之间往往不是独立的。动态规划法常用来求解具有最优性质的问题。即问题的最优解包含了其子问题的最优解。如求解多边形游戏问题。
设计动态规划法的步骤为：
1）找出最优解的性质，并刻画其结构特征；
2）递归地定义最优值；
3）以向前或向后处理方式计算出最优值；
4）根据计算最优值得到的信息，构造最优解。
贪心法，通过一系列的选择来得到一个问题的解，它所做的每一次选择都是当前情况下某种意义的最好选择，即贪心选择。如果待求解的问题具有最优子结构特征，也就是原问题的最优解包含子问题的最优解，并且可以通过局部的贪心选择来达到问题的全局最优解时，可通过贪心法进行求解。贪心标准的选择和问题的结构决定是否可以使用贪心法。如用于二分最小覆盖问题。
回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结点出发搜索解空间树。算法搜索到解空间树的任意结点时，首先判断该结点是否包含问题的解。如果不包含则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则进入这棵子树继续按深度优先搜索。如收费公路重建问题。
分支限界法，它类似于回溯法，也是在解空间中搜索问题解的算法，但分支限界法求解的目标是找出满足条件的一个解，如有多个解则要找出某种意义下的最优解。分支限界法以广度优先或以最小耗费优先的方式搜索解空间树。如最大完备子图问题。
26、算法的几个基本特征
有穷性，确定性，能行性，输入，输出。
程序 ＝ 数据结构 ＋ 算法
内容关键字：
线性表、栈、队、串、数组
树、二叉树、森林、线索二叉树、霍夫曼树
图、有向图、无向图、最小生成树、拓朴排序、关键路径
查找、静态查找（顺序、折半、分块）、动态查找（二叉排序树、平衡二叉树、哈希表）
排序、直接插入、简单选择、冒泡、希尔、快速、堆、归并、基数
软考学习笔记-数据库工程师第一章-计算机系统知识
软考学习笔记-数据库工程师第一章-计算机系统知识
第一章 计算机系统知识
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、计算机安全等级：技术安全性、管理安全性、政策法律安全性。一些重要的安全评估准则：“美国国防部和国家标准局的《可信计算机系统评测标准》 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 种可能性
20060322 by 高兴
第一章 计算机系统知识
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、计算机安全等级：技术安全性、管理安全性、政策法律安全性。一些重要的安全评估准则：“美国国防部和国家标准局的《可信计算机系统评测标准》 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 种可能性
20060322 by 高兴
今天刚查了分,通过了数据库工程师考试
今天刚查了分,通过了数据库工程师考试.
首先真心的感谢希赛网站!感谢csai使我慢慢的走出了困境和迷惑.
去年刚过了软件设计师, 虽然对考数工带来一些帮助.
但感觉要通过数工,不容易,还是要花费一番功夫.
这次 2008年5月 数工
上午:62
下午:55
搞银行后台开发,感觉自己遇到瓶颈,怎样才能提高自己,我经常问自己?
并不满足于应付当前的工作,以后的系统将被换掉,将会应用更多的数据库的新技术.
这次通过数工,感觉在理论方面长进不少,觉得在提高数据库方面找到了突破口.
以下是考试的一点心得,对自己是一个小结.也希望能与您们分享,带来些帮助.
下面我就 因材而进行说说:
【上午准备】
一.考过的软设的,准备考数工的.
我觉得上午题目可以花比较少的时间学习,重点要放在数据库理论知识,毕竟上午考察的数据库的比较多,
a.要看萨师宣.<<数据库概论>>第三版,目前我知道最新好像是第三版.要带着习题集边看边做.
b.数据库系统工程师考试考点分析与真题详解(信息系统综合知识篇)(第2版)这个是一定要看的,
一边看一遍进行自个总结.碰到还不懂得一定要去看书.
二.没有考过软设,准备考数工的.
感觉要学习的内容很多.
在上面的内容要加上:
需要加上计算机原理与体系结构,存储器系统,可靠性与系统性能评测,数据结构与算法,操作系统重点掌握.
如计算机原理与体系结构: cache三种映射方式,计算机的划分,中断机制,寻址方式等.
存储器系统: 虚拟内存的三种映射方式,及其某种方式物理地址的计算,还有类似于地址换算问题.
数据结构: 这个比较头疼,我没有好的方法学.
操作系统: 进程管理(深刻理解pv和信号,多种形式的消费者问题),作业管理,设备管理等(中断机制的应用).
可适当的看看软设的上午题目.
小结: 估计很多人在学cache和虚拟存储器的映射很头疼,当时我看得时候,我翻看了计算机系统结构的书和操作系统的书,
并将cache和虚拟内容进行了多种方式的横向比较,他们之间的思想是类似.
其他的内容,基本是记忆再记忆.
【下午准备】
下午就题型来讲,与软设进行比较.感觉少了程序设计题目.也少了uml图之类的题目.
偏向数据库设计题目.
a.先在你的机器安装一个数据系统,如sqlserver或db2等.<----理论联系实际,做到学以致用.
(如果你工作就要使用数据,那就不用了)最主要一点你要有一个数据库管理系统的环境.
b.下午题型就目前来看,应该是这几类:数据流程图,数据库设计(E-R图,模式分解,范式,函数依赖),
数据库操作sql语言,数据库运行和管理.其中数据库sql语言建议在实际环境去实现一下,这样你更能深刻理解.
c.数据库系统工程师考试考点分析与真题详解(数据库设计与管理篇)(第2版)这是必看的,
不懂得查阅萨老师的书。
【时间安排的问题】
立则兴,不立则废.
但毕竟每个人的功底不一样,计划仅仅针对个体,不能通用. 我仅仅谈谈大的方向,
1.知彼: 开始可以在csai上看看试题分析, 看上下午各考哪些内容,分值是怎样分布的.
2.知己: 针对这些知识点,与自己的知识架构进行比对,分层次标出熟练程度.如:不懂,熟悉,熟练等等.
3.吸收: 找个好群,进入进行交流.如找不到,可以大量上网查别人的经验,然后形成自己的"鸡尾酒".
4.计划: 有了以上的前提,你应该可以制定一个最适合自己的计划了.
小结: 建议前期先看薄弱环节,不慌做题,到了最后一个半月再去做题,特别是做错的题目,
要重点思考.
能告诉我，数据库系统工程师考试的考试地点吗？我是北京的！我在baidu找了，但没找到！
指点一下你的经验，还有该看什么书！（数据库系统工程师考试考点分析与真题详解(数据库设计与管理篇、综合篇、考点分析与真题详解)这些书我都有）。
以下为blog主人的回复：
1.北京的可以看看这个: http://www.bjpta.gov.cn/news_z.asp?news_id=575
2.我觉得这个两本书就够了,靠数工我觉得要能理解数据库原理的很多基础概念.再者丁宝康的<数工考试全程指导>也不错,但一点,一定看了之后要做后面的习题.
3.怎样准备上午,我的文中应该说清楚了.
4.考试的过程使我深刻的明白了"学而不思则罔".
看希赛出的那个《数据库真题详解》，
感觉那个很有用
我的数工，53/46 ，不知道过了没？
第一次参加软徒刑啊！不知道 分数线是怎么一回事啊？
我的数工，53/46 ，不知道过了没？
第一次参加软考啊！不知道 分数线是怎么一回事啊？
以下为blog主人的回复：
恭喜你了,应该可以的.你都46了,呵呵.
分数线一般在7月下旬就出来.
首先真心的感谢希赛网站!感谢csai使我慢慢的走出了困境和迷惑.
去年刚过了软件设计师, 虽然对考数工带来一些帮助.
但感觉要通过数工,不容易,还是要花费一番功夫.
这次 2008年5月 数工
上午:62
下午:55
搞银行后台开发,感觉自己遇到瓶颈,怎样才能提高自己,我经常问自己?
并不满足于应付当前的工作,以后的系统将被换掉,将会应用更多的数据库的新技术.
这次通过数工,感觉在理论方面长进不少,觉得在提高数据库方面找到了突破口.
以下是考试的一点心得,对自己是一个小结.也希望能与您们分享,带来些帮助.
下面我就 因材而进行说说:
【上午准备】
一.考过的软设的,准备考数工的.
我觉得上午题目可以花比较少的时间学习,重点要放在数据库理论知识,毕竟上午考察的数据库的比较多,
a.要看萨师宣.<<数据库概论>>第三版,目前我知道最新好像是第三版.要带着习题集边看边做.
b.数据库系统工程师考试考点分析与真题详解(信息系统综合知识篇)(第2版)这个是一定要看的,
一边看一遍进行自个总结.碰到还不懂得一定要去看书.
二.没有考过软设,准备考数工的.
感觉要学习的内容很多.
在上面的内容要加上:
需要加上计算机原理与体系结构,存储器系统,可靠性与系统性能评测,数据结构与算法,操作系统重点掌握.
如计算机原理与体系结构: cache三种映射方式,计算机的划分,中断机制,寻址方式等.
存储器系统: 虚拟内存的三种映射方式,及其某种方式物理地址的计算,还有类似于地址换算问题.
数据结构: 这个比较头疼,我没有好的方法学.
操作系统: 进程管理(深刻理解pv和信号,多种形式的消费者问题),作业管理,设备管理等(中断机制的应用).
可适当的看看软设的上午题目.
小结: 估计很多人在学cache和虚拟存储器的映射很头疼,当时我看得时候,我翻看了计算机系统结构的书和操作系统的书,
并将cache和虚拟内容进行了多种方式的横向比较,他们之间的思想是类似.
其他的内容,基本是记忆再记忆.
【下午准备】
下午就题型来讲,与软设进行比较.感觉少了程序设计题目.也少了uml图之类的题目.
偏向数据库设计题目.
a.先在你的机器安装一个数据系统,如sqlserver或db2等.<----理论联系实际,做到学以致用.
(如果你工作就要使用数据,那就不用了)最主要一点你要有一个数据库管理系统的环境.
b.下午题型就目前来看,应该是这几类:数据流程图,数据库设计(E-R图,模式分解,范式,函数依赖),
数据库操作sql语言,数据库运行和管理.其中数据库sql语言建议在实际环境去实现一下,这样你更能深刻理解.
c.数据库系统工程师考试考点分析与真题详解(数据库设计与管理篇)(第2版)这是必看的,
不懂得查阅萨老师的书。
【时间安排的问题】
立则兴,不立则废.
但毕竟每个人的功底不一样,计划仅仅针对个体,不能通用. 我仅仅谈谈大的方向,
1.知彼: 开始可以在csai上看看试题分析, 看上下午各考哪些内容,分值是怎样分布的.
2.知己: 针对这些知识点,与自己的知识架构进行比对,分层次标出熟练程度.如:不懂,熟悉,熟练等等.
3.吸收: 找个好群,进入进行交流.如找不到,可以大量上网查别人的经验,然后形成自己的"鸡尾酒".
4.计划: 有了以上的前提,你应该可以制定一个最适合自己的计划了.
小结: 建议前期先看薄弱环节,不慌做题,到了最后一个半月再去做题,特别是做错的题目,
要重点思考.
能告诉我，数据库系统工程师考试的考试地点吗？我是北京的！我在baidu找了，但没找到！
指点一下你的经验，还有该看什么书！（数据库系统工程师考试考点分析与真题详解(数据库设计与管理篇、综合篇、考点分析与真题详解)这些书我都有）。
以下为blog主人的回复：
1.北京的可以看看这个: http://www.bjpta.gov.cn/news_z.asp?news_id=575
2.我觉得这个两本书就够了,靠数工我觉得要能理解数据库原理的很多基础概念.再者丁宝康的<数工考试全程指导>也不错,但一点,一定看了之后要做后面的习题.
3.怎样准备上午,我的文中应该说清楚了.
4.考试的过程使我深刻的明白了"学而不思则罔".
看希赛出的那个《数据库真题详解》，
感觉那个很有用
我的数工，53/46 ，不知道过了没？
第一次参加软徒刑啊！不知道 分数线是怎么一回事啊？
我的数工，53/46 ，不知道过了没？
第一次参加软考啊！不知道 分数线是怎么一回事啊？
以下为blog主人的回复：
恭喜你了,应该可以的.你都46了,呵呵.
分数线一般在7月下旬就出来.
2008年12月26日金曜日
20天通过数据库系统工程师考试全攻略
20天通过数据库系统工程师考试全攻略
随着考试的日子越来越近，很多以前没有进行过准备或者没有时间准备的考生非常的着急，不知在这20多天的时间里如何进行复习，对通过考试是坚持还是放弃，难以决择!有的是初次参加数据库系统工程师考试，有的已是屡战屡败好几次了;也许都因准备不足，产生不同程度的考前综合症，影响了考试的效果。下面我针对这些症状，开几贴良方给大家，以助您一臂之力。
一.治疗糊涂症和盲目症。
症状：
·对数据库系统工程师考试的大纲不了解，要考哪些课程也不清楚。
·对数据库系统工程师考试的题型、重点、难点都不知道。
·对自己的能力估计不准确，或者是抱着试一试的态度。
·从来不关心考试的动向，了解出题的趋势。
·从不与人交流。
·……
良方(第1～2天)：
1. 到学赛网www.educity.cn 上找到数据库系统工程师的考试大纲，下载后通看几篇，了解该考试要考到哪些课程，涉及到哪些知识点，自己对哪些课程和知识点比较陌生，做到心中有数。
2. 在学赛网www.educity.cn 上找到数据库系统工程师考试的历年试题分析(至少有2005年上半年到2007年下半年)，下载后查看考试的题型、知识点。
3. 到学赛网的测试平台内做一做历年试题，测测自己的水平，以定位自己能力。
4. (最佳良方)学习《数据库系统工程师串讲视频教程》。该视频教程根据最新的数据库系统工程师考试大纲和希赛教育进行考试辅导和阅卷的经验，对其中的难点问题进行了详细的分析和讲解，基本上囊括了考试的所有知识点。这个教程不但包括了对考试大纲的分析，历年试题的重点、难点分析，分值分布，而且还介绍了试题解答方法和技巧，以及考试中出现的常见问题及对策。通过专家的详细讲解，使我们迅速掌握考试重点和难点知识;掌握解答问题的方法和技巧，彻底解决“答不到点子上”的问题。最主要的是能起到事半功倍的效果，在短时间内备考，极大地提高考试通过率。
5. 到学赛网的论坛http://bbs.educity.cn/bbs/index.asp 里来溜溜，可以将自己不懂的问题发出来，也可以看看人家的问题和复习方法，多交流，多沟通，三人行必有我师。
二.治疗心浮气燥症和紊乱症。
症状：
·随着考试时间的临近，越发不能平静下来看书，心浮气燥。
·看书时没有目的性，不带着任务走，看到哪里算哪里;看后不做题进行巩固。
·做练习题时遇到较复杂一点的，就没有耐性，只想看答案。
·渴望有模拟试题做，有了却又草率作答(草率的理由是“工作忙，没时间”)。
·拿着书，就想着做题;做着题，又想着看书;结果书没看好，题也没有在规定的时间内完成。
·尽想着有什么剂世良方，却又不肯静下心来脚踏实地，找出自己的薄弱环节。
·……
良方(第3～20天)：
1. 根据第一阶段的治疗，了解了大纲，了解了考试的题型、重点、难点、主要分值分布点;接下来是静下心，针对自己在那些高分值的薄弱环节，重点突破，弄懂弄透彻，切不可似是而非。
2. 到学赛网www.csai.cn 的在线测试平台，认认真真的在规定的时间内做几套历年试题，一是起到“练兵”的效果;二是以便发现自己的不足，熟悉考试的题型。
3. (良方)学习《数据库系统工程师考试试题讲解视频教程》。学习希赛教育的数据库系统工程师考试试题讲解视频教程，该视频教程对2004年11月至2007年11月的数据库系统工程师考试的试题进行了详细的讲解，包括计算机与软件工程知识、数据库基础知识，对考试所涉及的知识点进行了深入分析。通过学习试题讲解视频教程，我们可以迅速掌握考试所涉及的知识点，了解试题的出题动向和试题结构。同时，从历年考试试题来看，试题重复的概率越来越高，特别是上午的试题，很多试题原样不动地又出现了，或者只换了一个数字又被“翻新”了。因此，熟悉历年试题，掌握历年试题中所涉及的知识点，是备考的一个捷径。
4. (最佳良方)参加希赛教育冲刺班或强化班，做模拟试题。需要参加希赛教育的辅导，现在既可以参加冲刺班，也可以参加强化训练班。通过模拟试题来强化知识结构，查漏补缺。特别是对于下午的练习，和自己在一些重要知识点的薄弱环节上需要老师的指导。从往年阅卷的情况来看，相当一部分考生的上午成绩合格，却下午成绩不理想。在做模拟试题的时候，需要做一套试题，就掌握该套试题所涉及的知识点，特别是对自己做错的试题，要更加认真对待。还可以参加在线课堂的综合知识答疑，与辅导老师实时在线聊考试的重点、难点以及考试的方法与技巧。
三.治疗投机症和投降症。
症状：
·因为准备不足，四处打听偏方，企图得到什么“内部消息”、“权威消息”、“重点点题”等。
·企图发挥考场上的侦察能力。
·眼看时间只有20多天了，准备不足，放弃考试了。
·虽然前段时间复习了部分内容，但还有几大块没有动手，可能考不过，放弃算了。
·下午试题做不对几个，基本功又不太好，看到历年试题的题干就没信心做下去了。
·进入考场，还没动笔做，就两股发膻，肌肉发僵。
·考试过程中，或是埋头苦干，完不成;或是见难就撤，走为上策。
·……
良方(第1～20天)：
1. 数据库系统工程师考试范围十分广泛，涉及的学科众多，即要考查基础理论知识，又要考查数据库的设计能力;而且每年的出题变化大。有很多小的培训结构或者个人胡乱的介绍一些重点，放出一些不负责任的消息，往往会误导很多人。
2. 希赛IT教育软考辅导平台从来不押题，不散发一些所谓的权威消息;而是求真务实，全心全意为考生，每年的过级率达到80%以上(绝对真实)。
3. 再一次向那些准备不充分的考生推荐最佳良方，学习 《数据库系统工程师串讲视频教程》和《数据库系统工程师考试试题讲解视频教程》，这是短期提高和通过考试的最佳选择。
4. 放弃考试，那就是没有一丝希望了;如若鼓劲冲一把，向上跳一跳，也许您就摘到了这个“果果”。
5. 有限的时间里，有好的方法与勇气，通过考试是极大可能的。要知道狭路相逢，勇者胜;勇者相遇，智者胜。
6. 进入了考场，就要抛弃所有杂念，合力向前。(1)要全盘了解考试试题，不要拿卷就埋头苦干。(2)先做容易的题目，再做难的，合理安排好时间。(3)下午解题的方法与技巧非常重要，根据多年的辅导和阅卷经验，希赛辅导平台内的专家总结出了很多宝贵的经验。(4)要养成复查的习惯。
四.总结。
因种种的原因，造成你前段时间对数据库系统工程师考试的准备不足，心里恐慌、压抑、怀疑等等不良综合症。在剩下20多天的时间里，如何高效的学习和提高呢?这主要是取决于你的态度，若选择拼搏，那你就要鼓足勇气的同时，采用良好的学习方法和权威有用的学习资料，或接受正规的辅导。如若你选择了放弃，那就开开心心迎接下一次报名，不要苦了自己。
【详情请见】
· 希赛教育2008年5月软考冲刺班、强化班辅导招生：http://educity.cn/ruankao/kspx_cc.htm
· 软考视频教程：http://platform.educity.cn/learn.htm
· 2008年上半年国家软考指定教材：http://educity.cn/ruankao/200705rk.htm
随着考试的日子越来越近，很多以前没有进行过准备或者没有时间准备的考生非常的着急，不知在这20多天的时间里如何进行复习，对通过考试是坚持还是放弃，难以决择!有的是初次参加数据库系统工程师考试，有的已是屡战屡败好几次了;也许都因准备不足，产生不同程度的考前综合症，影响了考试的效果。下面我针对这些症状，开几贴良方给大家，以助您一臂之力。
一.治疗糊涂症和盲目症。
症状：
·对数据库系统工程师考试的大纲不了解，要考哪些课程也不清楚。
·对数据库系统工程师考试的题型、重点、难点都不知道。
·对自己的能力估计不准确，或者是抱着试一试的态度。
·从来不关心考试的动向，了解出题的趋势。
·从不与人交流。
·……
良方(第1～2天)：
1. 到学赛网www.educity.cn 上找到数据库系统工程师的考试大纲，下载后通看几篇，了解该考试要考到哪些课程，涉及到哪些知识点，自己对哪些课程和知识点比较陌生，做到心中有数。
2. 在学赛网www.educity.cn 上找到数据库系统工程师考试的历年试题分析(至少有2005年上半年到2007年下半年)，下载后查看考试的题型、知识点。
3. 到学赛网的测试平台内做一做历年试题，测测自己的水平，以定位自己能力。
4. (最佳良方)学习《数据库系统工程师串讲视频教程》。该视频教程根据最新的数据库系统工程师考试大纲和希赛教育进行考试辅导和阅卷的经验，对其中的难点问题进行了详细的分析和讲解，基本上囊括了考试的所有知识点。这个教程不但包括了对考试大纲的分析，历年试题的重点、难点分析，分值分布，而且还介绍了试题解答方法和技巧，以及考试中出现的常见问题及对策。通过专家的详细讲解，使我们迅速掌握考试重点和难点知识;掌握解答问题的方法和技巧，彻底解决“答不到点子上”的问题。最主要的是能起到事半功倍的效果，在短时间内备考，极大地提高考试通过率。
5. 到学赛网的论坛http://bbs.educity.cn/bbs/index.asp 里来溜溜，可以将自己不懂的问题发出来，也可以看看人家的问题和复习方法，多交流，多沟通，三人行必有我师。
二.治疗心浮气燥症和紊乱症。
症状：
·随着考试时间的临近，越发不能平静下来看书，心浮气燥。
·看书时没有目的性，不带着任务走，看到哪里算哪里;看后不做题进行巩固。
·做练习题时遇到较复杂一点的，就没有耐性，只想看答案。
·渴望有模拟试题做，有了却又草率作答(草率的理由是“工作忙，没时间”)。
·拿着书，就想着做题;做着题，又想着看书;结果书没看好，题也没有在规定的时间内完成。
·尽想着有什么剂世良方，却又不肯静下心来脚踏实地，找出自己的薄弱环节。
·……
良方(第3～20天)：
1. 根据第一阶段的治疗，了解了大纲，了解了考试的题型、重点、难点、主要分值分布点;接下来是静下心，针对自己在那些高分值的薄弱环节，重点突破，弄懂弄透彻，切不可似是而非。
2. 到学赛网www.csai.cn 的在线测试平台，认认真真的在规定的时间内做几套历年试题，一是起到“练兵”的效果;二是以便发现自己的不足，熟悉考试的题型。
3. (良方)学习《数据库系统工程师考试试题讲解视频教程》。学习希赛教育的数据库系统工程师考试试题讲解视频教程，该视频教程对2004年11月至2007年11月的数据库系统工程师考试的试题进行了详细的讲解，包括计算机与软件工程知识、数据库基础知识，对考试所涉及的知识点进行了深入分析。通过学习试题讲解视频教程，我们可以迅速掌握考试所涉及的知识点，了解试题的出题动向和试题结构。同时，从历年考试试题来看，试题重复的概率越来越高，特别是上午的试题，很多试题原样不动地又出现了，或者只换了一个数字又被“翻新”了。因此，熟悉历年试题，掌握历年试题中所涉及的知识点，是备考的一个捷径。
4. (最佳良方)参加希赛教育冲刺班或强化班，做模拟试题。需要参加希赛教育的辅导，现在既可以参加冲刺班，也可以参加强化训练班。通过模拟试题来强化知识结构，查漏补缺。特别是对于下午的练习，和自己在一些重要知识点的薄弱环节上需要老师的指导。从往年阅卷的情况来看，相当一部分考生的上午成绩合格，却下午成绩不理想。在做模拟试题的时候，需要做一套试题，就掌握该套试题所涉及的知识点，特别是对自己做错的试题，要更加认真对待。还可以参加在线课堂的综合知识答疑，与辅导老师实时在线聊考试的重点、难点以及考试的方法与技巧。
三.治疗投机症和投降症。
症状：
·因为准备不足，四处打听偏方，企图得到什么“内部消息”、“权威消息”、“重点点题”等。
·企图发挥考场上的侦察能力。
·眼看时间只有20多天了，准备不足，放弃考试了。
·虽然前段时间复习了部分内容，但还有几大块没有动手，可能考不过，放弃算了。
·下午试题做不对几个，基本功又不太好，看到历年试题的题干就没信心做下去了。
·进入考场，还没动笔做，就两股发膻，肌肉发僵。
·考试过程中，或是埋头苦干，完不成;或是见难就撤，走为上策。
·……
良方(第1～20天)：
1. 数据库系统工程师考试范围十分广泛，涉及的学科众多，即要考查基础理论知识，又要考查数据库的设计能力;而且每年的出题变化大。有很多小的培训结构或者个人胡乱的介绍一些重点，放出一些不负责任的消息，往往会误导很多人。
2. 希赛IT教育软考辅导平台从来不押题，不散发一些所谓的权威消息;而是求真务实，全心全意为考生，每年的过级率达到80%以上(绝对真实)。
3. 再一次向那些准备不充分的考生推荐最佳良方，学习 《数据库系统工程师串讲视频教程》和《数据库系统工程师考试试题讲解视频教程》，这是短期提高和通过考试的最佳选择。
4. 放弃考试，那就是没有一丝希望了;如若鼓劲冲一把，向上跳一跳，也许您就摘到了这个“果果”。
5. 有限的时间里，有好的方法与勇气，通过考试是极大可能的。要知道狭路相逢，勇者胜;勇者相遇，智者胜。
6. 进入了考场，就要抛弃所有杂念，合力向前。(1)要全盘了解考试试题，不要拿卷就埋头苦干。(2)先做容易的题目，再做难的，合理安排好时间。(3)下午解题的方法与技巧非常重要，根据多年的辅导和阅卷经验，希赛辅导平台内的专家总结出了很多宝贵的经验。(4)要养成复查的习惯。
四.总结。
因种种的原因，造成你前段时间对数据库系统工程师考试的准备不足，心里恐慌、压抑、怀疑等等不良综合症。在剩下20多天的时间里，如何高效的学习和提高呢?这主要是取决于你的态度，若选择拼搏，那你就要鼓足勇气的同时，采用良好的学习方法和权威有用的学习资料，或接受正规的辅导。如若你选择了放弃，那就开开心心迎接下一次报名，不要苦了自己。
【详情请见】
· 希赛教育2008年5月软考冲刺班、强化班辅导招生：http://educity.cn/ruankao/kspx_cc.htm
· 软考视频教程：http://platform.educity.cn/learn.htm
· 2008年上半年国家软考指定教材：http://educity.cn/ruankao/200705rk.htm
登録:
投稿 (Atom)