错误纠错技术

海明码

海明码是一种多重（复式）奇偶检错编码，它将信息用逻辑形式编码。适合检验和纠错，设有n个信息位，k个校验位，则有以下关系：

海明码具体计算如下：

CRC

• 在使用crc校验时，设数据位为k，校验位为r，那么crc码的格式是k个数据位之后跟r个校验位

• 主要采用模二运算来构造校验位

CPU部分重点

由运算器，控制器，寄存器组，内部总线等部件组成，控制器由程序计数器，指令寄存器，指令译码器。。。。

控制器：控制整个计算机的各个部件工作，基本功能是从内存取指令和执行指令，负责依次访问程序指令，进行指令译码，并协调其他设备。

• cpu中对其访问速度最快的是通用寄存器

• 计算机系统的运算速度受多种因素的影响，64位微处理器可同时对64位数据进行运算，但不能说其速度是32位微处理器的2倍。

flynn分类法

Flynn主要根据指令流和数据流来分类，分为四类：

• 单指令流单数据流机器（SISD） SISD机器是一种传统的串行计算机，它的硬件不支持任何形式的并行计算，所有的指令都是串行执行，并且在某个时钟周期内，CPU只能处理一个数据流。因此这种机器被称作单指令流单数据流机器。早期的计算机都是SISD机器。

• 单指令流多数据流机器（SIMD） SIMD是采用一个指令流处理多个数据流。这类机器在数字信号处理、图像处理以及多媒体信息处理等领域非常有效。 Intel处理器实现的MMXTM、SSE （Streaming SIMD Extensions）、SSE2及SSE3扩展指令集，都能在单个时钟周期内处理多个数据单元。也就是说人们现在用的单核计算机基本上都属于SIMD机器。

• 多指令流单数据流机器（MISD） MISD是采用多个指令流来处理单个数据流。在实际情况中，采用多指令流处理多数据流才是更有效的方法。因此MISD只是作为理论模型出现，没有投入实际应用。

• 多指令流多数据流机器（MIMD） MIMD机器可以同时执行多个指令流，这些指令流分别对不同数据流进行操作。例如，intel和AMD的双核处理器就属于MIMD的范畴。

寄存器部分

• 程序计数器（指令计数器）是专用寄存器，具有寄存信息和计数两种功能，程序执行之前先将起始地址送入pc中；可以临时存储算术/逻辑运算结果，也可以存放指令地址；在程序开始执行前，将程序的起始地址送入PC，该地址在程序加载到内存时确定，因此PC的初始内容即是程序第一条指令的地址。执行指令时，CPU将自动修改PC的内容，以便使其保持的总是将要执行的下一条指令的地址。由于大多数指令都是按顺序执行的，因此修改的过程通常只是简单地对PC加1。当遇到转移指令时，后继指令的地址根据当前指令的地址加上一个向前或向后转移的位移量得到，或者根据转移指令给出 的直接转移的地址得到。

• 累加寄存器：累加寄存器是专门存放算术和逻辑运算的一个操作数和计算结果的寄存器，能进行加减，读出，移位，循环移位和求补等操作，是运算器的主要部分

• CPU依据指令周期的不同阶段来区分存在内存中以二进制编码形式存放的指令和数据

• 指令寄存器的位数处决于指令字长

• 加法器属于算术逻辑单元

• 指令寄存器对用户是完全透明的

DMA部分

• 在输入输出控制方法中，采用DMA可以使设备与主存之间的数据块传输无需CPU干预，这种方式很大程度下可以减少CPU的负担

• cpu是在一个总线周期结束时响应DMA

• 直接是主存和外设之间建立连接

中断

中断系统按照优先级排队，如果在处理优先级较低的任务时，突然来了一个高优先级的任务，此时，高级中断将会打断低级中断，此过程被称为中断嵌套，实现中断嵌套，使用堆栈最有效

主存---cache---cpu

采用分级存储体系的主要目的是为了解决存储容量、成本和速度之间的矛盾

cache

• cache与主存之间的转换工作由硬件完成

• 常用的虚拟存储器由主存-辅存两级存储器组成

• cache与主存之间的地址映像由硬件自动完成

• 多级高速缓存cache可以提高cpu访问主存或者指令的效率

• cache的设计思想是在合理的成本下控制命中率

主存

主存主要是由DRAM构成

存储器芯片的计算

直接上例题：

内存按字节编址，地址从A000OH到CFFFF H的内存，共存（）字节，若用存储容量为64k* 8btt的存储器芯片构成该内存空间，至少需要 （）片。

第一空：地址从A0000H到CFFFFH，存储单元个数共有CFFFFH+1-A0000H=30000H，即3x164个；按字节编址，即每个存储单元存放1个字节，也就是1B；该存储区域总容量=存储单元个数*存储单元内容=3x164x1B=3x216B=192KB。

第二空：若用存储容量为64Kx8bit的存储芯片构成，即单位芯片容量为64Kx8bit，总容量=单位芯片容量*片数，即片数=总容量/单位芯片容量=（192KB）/（64Kx8bit）=3

这里值得注意的是计算片数时需要注意单位的统一。

主存与Cache的地址映射方式

全相联地址映射：主存的任意一块可以映象到Cache中的任意一块（冲突最小）。

直接相联映射：主存中一块只能映象到Cache的一个特定的块中。

组相联的映射：各区中的某一块只能存入缓存的同组号的空间内，但组内各块地址之间则可以任意存放。

存储器的分类

所处的位置可分为内存和外存。

按构成存储器的材料可分为磁存储器、半导体存储器和光存储器。

按存储器的工作方式可分为读写存储器和只读存储器。

按访问方式可分为按地址访问的存储器和按内容访问的存储器。

按寻址方式可分为随机存储器、顺序存储器和直接存储器。

相联存储器是一种按内容访问的存储器。

寻址的分类

指令中的寻址方式就是如何对指令中的地址字段进行解释，以获得操作数的方法或 获得程序转移地址的方法。常用的寻址方式有：

• 立即寻址。操作数就包含在指令中。

• 直接寻址。操作数存放在内存单元中，指令中直接给出操作数所在存储单元的地址。

• 寄存器寻址。操作数存放在某一寄存器中，指令中给出存放操作数的寄存器名。

• 寄存器间接寻址。操作数存放在内存单元中，操作数所在存储单元的地址在某个寄存器中。

• 间接寻址。指令中给出操作数地址的地址。

• 相对寻址。指令地址码给出的是一个偏移量（可正可负），操作数地址等于本条 指令的地址加上该偏移量。

• 变址寻址。操作数地址等于变址寄存器的内容加偏移量。 题目给出的指令中，R1是寄存器，属于寄存器寻址方式，45是立即数，属于立即寻址方式。

总线系统

• 三总线结构的计算机总线系统由数据总线、地址总线、控制总线组成

• 总线结构的优势：

  • 简化系统结构，便于系统设计制造；

  • 大大减少了连线数目，便于布线，减小体积，提髙系统的可靠性；

  • 便于接口设计，所有与总线连接的设备均釆用类似的接口；

  • 便于系统的扩充、更新与灵活配置，易于实现系统的模块化；

  • 便于设备的软件设计，所有接口的软件就是对不同的口地址进行操作；

  • 便于故障诊断和维修，同时也降低了成本。

系统总线分类

系统总线包含有三种不同功能的总线：数据总线DB （Data Bus）、地址总线AB （Address Bus）和控制总线CB （Control Bus）。

• ISA （Industrial Standard Architecture）总线标准是IBM公司1984年为推出PC/AT机而建立的系统总线标准，所以也叫AT总线。它是对XT总线的扩展，以适应8/16位数据总线要求。

• EISA总线是1988年由Compaq等9家公司联合推出的总线标准。它在ISA总线的基础上使用双层插座，在原来ISA总线的98条信号线上又增加了98条信号线，也就是在两条ISA信号线之间添加一条EISA信号线。在实用中，EISA总线完全兼容ISA总线信号。

• PCI （Peripheral Component Interconnect）总线是当前最流行的总线之一，它是由Intel公司推出的一种局部总线。它定义了32位数据总线，且可扩展为64位。PCI总线主板插槽的体积比原ISA总线插槽还小，支持突发读写操作，最大传输速率可达132MB/S，可同时支持多组外围设备。

总线宽度的计算问题

总绒宽度为32bit,时钟频率为200MHz 若总线上每5个时钟周期传送一个32btt的字，则 该总线的带宽为（）MB/s。

总线宽度是指总线的线数，即数据信号的并行传输能力，也体现总线占用的物理空间和成本；总线的带宽是指总线的最大数据传输率，即每秒传输的数据总量。总线宽度与时钟频率共同决定了总线的带宽。 32bit / 8=4 Byte， 200MHz/5 * 4 Byte = 160 MB/s

计算机与安全

计算机病毒

• 计算机病毒的分类方法有许多种，按照最通用的区分方式，即根据其感染的途径以及采用的技术区分，计算机病毒可分为文件型计算机病毒、引导型计算机病毒、宏病毒和目录型计算机病毒。

  • 文件型计算机病毒感染可执行文件（包括EXE和COM文件）。

  • 引导型计算机病毒影响软盘或硬盘的引导扇区。

  • 目录型计算机病毒能够修改硬盘上存储的所有文件的地址。

  • 宏病毒感染的对象是使用某些程序创建的文本文档、数据库、电子表格等文件

• 典型网络病毒主要有宏病毒、特洛伊木马、蠕虫病毒、脚本语言病毒等。

• 宏病毒的传播方式通常如下：字处理程序Word在打开一个带宏病毒的文档或模板时，激活了病毒宏，病毒宏将自身复制至Word的通用（Normal）模板中，以后在打开或关闭文件时病毒宏就会把病毒复制到该文件中。

  • 特洛伊木马是一种秘密潜伏且能够通过远程网络进行控制的恶意程序。控制者可以控制被秘密植入木马的计算机的一切动作和资源，是恶意攻击者窃取信息的工具。 蠕虫病毒的传播过程一般表现为

  • ：蠕虫程序驻于一台或多台机器中，它会扫描其他机器是否有感染同种计算机蠕虫，如果没有，就会通过其内建的传播手段进行感染，以达到使计算机瘫痪的目的。

• “蠕虫”（Worm）是一个程序或程序序列。它利用网络进行复制和传播，传染途径是通过网络、移动存储设备和电子邮件。最初的蠕虫病毒定义是在DOS环境下，病毒发作时会在屏幕上出现一条类似虫子的东西，胡乱吞吃屏幕上的字母并将其改形，蠕虫病毒因此而得名。常见的蠕虫病毒有红色代码、爱虫病毒、熊猫烧香、Nimda病毒、爱丽兹病毒等。 冰河是木马软件，主要用于远程监控，冰河木马后经其他人多次改写形成多种变种，并被用于入侵其他用户的计算机的木马程序。

• 计算机病毒具有隐蔽性、传染性、潜伏性、触发性和破坏性等特定。

防火墙技术

• 防护墙的特性：

  • 控制进出网络的数据包和数据流向

  • 提供流量信息的日志和审计

  • 隐藏内部IP以及网络结构细节

• 防火墙分类：

  • 包过滤防火墙

  • 应用级网关防火墙

• 包过滤防火墙对数据包的过滤依据包括：源ip地址，源端口号，目标IP地址，目标端口号

• 防火墙按照受保护的程序，从高到底被分为：内网，BMZ，外网

• 防火墙的工作层次越高，工作效率越低，安全性越高

• 包过滤技术对用户和应用透明

漏洞扫描

用于检测目标主机安全弱点程序，仅扫描漏洞，进而修补漏洞而加强系统的可靠性

木马程序客户端运行在攻击者的机器上

机房安全属于物理安全，入侵检测属于网络安全，漏洞管理属于系统安全，数据库安全属于应用安全

加密解密技术

注意点：

• 对称加密适合加密大型文件，譬如加密的正文信息

• 非对称加密适合加密小文件，譬如数组签名等技术

• 为了防止发送者不可抵赖，一般使用的是数字签名技术，数字签名一般使用发送方的私钥加密，接收方使用发送方的公钥进行解密

• 为防止被第三方截取后篡改，一般使用的是消息摘要技术，数字摘要一般使用接收方的公钥加密，使用接收方的私钥解密

• 几种加密算法：

  • RSA基于大数定律，通常用于对消息摘要进行签名

  • IDEA和RC4事宜于进行数据传输加密

  • MD5为摘要算法

  • 对称加密算法：DES,三重DES，RC-5,IDEA,AES

• a和b在i1和i2两个ca处取得各自的证书，此时i1和i2互换公钥是a和b互信的必要条件

• MD5对任意长度的输入计算得到的结果长度为128位

RISC和CISC

CISC （复杂指令集计算机）的基本思想是：进一步增强原有指令的功能，用更为复杂的新指令取代原先由软件子程序完成的功能，实现软件功能的硬件化，导致机器的指令系统越来越庞大而复杂。CISC计算机一般所含的指令数目至少300条以上，有的甚至超过500条。

RISC （精简指令集计算机）的基本思想是：通过减少指令总数和简化指令功能，降低硬件设计的复杂度，使指令能单周期执行，并通过优化编译提高指令的执行速度，采用硬布线控制逻辑优化编译程序。在20世纪70年代末开始兴起，导致机器的指令系统进一步精炼而简单。

系统可靠度

并：R = 1-（1-R1）（1-R2）...（1-Rn）

串：R1 R2 R3...Rn

机器码之间的运算

• 机器码字长为n位的二进制数可以使用补码来表示2^n个不同的有符号的定点数

• 采用8位整数补码表述数据，可表述的范围为：-128~127

• 机器字长为n，最高位为符号位，其定点整数的最大值为2^(n-1) -1

• 两个浮点数相加时，首先需要对阶，既将小阶向大阶对齐，同时将尾数右移n位

• 浮点数中阶码用于表示范围，尾数用于表示精度

• 浮点数能表示的数字范围：

  

• 采用补码表示数据时，可以将符号位和其他位统一处理，减法也可以按加法处理，从而可以简化运算部件的设计

• 移位运算符就是在二进制的基础上对数字进行平移。按照平移的方向和填充数字的规则分为三种：<<（左移）、>>（带符号右移）和>>>（无符号右移）。在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方。

• 正负0编码相同的是补码和移码。

流水线

• 流水线的操作周期为操作中的最大时间

• 流水线方式执行n条指令，需要时间为：完成一条指令需要的时间+(指令条数-1)*MAX(一条流水线的时间)

• 流水线的吞吐率是最长流水段操作时间

流水线性能量度

对指令流水线性能的度量主要有吞吐率，加速比和效率等指标。

• 吞吐率是指单位时间内流水线所完成的任务数或输出结果的数量，最大吞吐率则是流水线在达到稳定状态后所得到的吞吐率，它取决于流水线中最慢一段所需的时间，所以该段成为流水线的瓶颈。

• 加速比定义为等功能的非流水线执行时间与流水线执行时间之比，加速比与吞吐率成正比，如果流水线断流，实际吞吐率将会明显下降，则加速比也会明显下降。

• 效率是指流水线的设备利用率，从时空图上看效率就是n个任务所占的时空区与m个段总的时空区之比。因此要使加速比和效率最大化应该流水线各级采用相同的运行时间。另外，流水线釆用异步控制并不会给流水线性能带来改善，反而会增加控制电路的复杂性。

补充

• 主板的BIOS保存在主板的ROM上面

• 随机访问存储器（RAM）有两类：静态的（SRAM）和动态的（DRAM），SRAM 比DRAM速度更快，但也贵得多。SRAM用来作为高速缓冲存储器（Cache），DRAM 用来作为主存及图形系统的帧缓冲区。SRAM将每个位存储在一个双稳态的存储器单元中，DRAM将每个位存储为对一个电容的充电，由于电容非常小，在10〜l00ms时间内会失去电荷，所以需要周期性地刷新充电以保持信息。 EEPROM是电可擦除可编程只读存储器。

• 32位的计算机内存容量为2g，按照字编址，可寻址范围为：2x1024x1024x1024x8//32=512x1024x1024,所以范围为512mb

• 入侵检测技术包含专家系统，模型检测，简单匹配

osi/rm七层模型

局域网只工作在物理层和数据链路层上

这里p和s跨越了层级所以不在同一个局域网下，在这种配置下ip全局广播分组不能够通过该路径

• 集线器连接的主机构成一个冲突域，交换机的每一个端口属于一个冲突域

tcp/ip协议簇

• ARP：地址解析协议 （ip转mac）

• RARP：反向地址解析协议 （mac转ip）

• 基于tcp的协议（均为可靠的协议）：

  • pop3：邮件传输协议

  • ftp：文件传输协议

  • http：传输网页数据

  • telnet：远程登陆

  • smtp：邮件传输协议

• 基于udp协议：

  • dhcp：ip地址动态分配

    • 客户机/服务器模式(c/s)

    • 租约默认8天，租约过半，客户机向dhcp服务器申请续租

    • 当租约超过87.5%时，如果仍然没有和当初提供ip的dhcp服务器联系上，将会开始联系其他的dhcp服务器

    • 固定分配、动态分配和自动分配

    • 假地址：169.254.x.x和0.0.0.0，出现这两个地址可能是服务器出故障了，也有可能是可客户机和服务器没有联系上

  • tftp：小文件传输协议

  • snmp：简单网络管理协议

  • dns：域名解析

    • 域名与ip之间的转换

    • 主机向本地域名服务器的查询采用递归查询

    • 本地域名服务器向根域名服务器的查询通常采用迭代查询

• ppp中的安全认证协议是CHAP

• DNS域名查询的次序：本地的hosts文件->本地DNS缓存->本地DNS服务器->根域名服务器

• ipv4->ip6隧道技术 ipv6->ip4翻译技术

• pop3协议采用c/s模式

• SMTP端口号为25，POP3端口为110

• tcp使用的流量控制的协议是：可变大小的窗口协议

分层设计：

• 分为三层：

  • 接入层：向本地网段提供用户接入

  • 汇聚层：网络访问策略控制、数据包处理、过滤、寻址

  • 核心层：数据高速交换以及转发，要求设备可靠性高，核心层多数为多态服务器容错

特殊含义的ip地址

常用的命令

ipconfig 显示信息； ipconfig /all 显示详细信息 ，可查看DHCP服务是否已启用； ipconfig /renew 更新所有适配器； ipconfig /release 释放所有匹配的连接。ipconfig/flushdns的含义是刷新并重设DNS解析器缓存。netstat –r用于显示核心路由表。arp –a用于查看ARP高速缓存中的内容。

网路安全

• ARP攻击造成网络无法跨网段通信的原因是：伪造网关ARP报文，使得数据包无法发送到网关

• 传输经过ssl加密的网页所采用的协议为https，默认端口是443

• FTP服务器的控制端口为21，上传文件时的端口为20

• 网络管理员通过命令行为方式对路由器进行管理，要确保id，口令和会话内容的保密性，应采用ssh的访问方式

• ie浏览器中安全级别最高的是受限节点

• 为了攻击远程主机，通常利用端口扫描技术检测远程主机状态

• SNMP服务中，必须要用adminstrator组成员身份登录才能完成SNMP服务的配置功能

媒体

• 图元是描述矢量图的基本组成单位

• 计算机收到的外设信号一般是模拟信号

• MPEG-1被应用到VCD；MPEG-2被应用到DVD；MPEG-7是多媒体内容描述接口标准

• 音乐合成技术主要有：FM，Wave Table两种

• dpi表示每英寸的像素

• 改变数字载波率可以改变音调，改变信号幅度可以改变音高

• 位图与矢量图相比较，位图占用空间大，处理侧重于获取和复制，显示速度快

常考的几种媒体分类

• 表示媒体：用于数据交换的编码

• 表现媒体：可用于输入输出的设备

几种媒体的编码

目前广泛使用的编码及压缩标准有JPEG、MPEG和H.261。

三级模式两级映像

内模式：（物理数据库）如何存储数据，关注数据的存放，使用什么数据结构，仅有一个模式

模式（概念模式）：数据库中的表，一个模式有多个外模式，仅有一个模式

外模式：视图

为了保证数据的独立性，使用两级映像

数据库设计过程

首先是需求分析，之后是概念结构设计，逻辑结构设计，最后是物理结构设计

• 需求分析的输出有：数据流图，数据字典，需求说明书

• 概念结构设计的输出有：er模型

• 逻辑结构设计的输出有：关系模式

规范化理论

函数依赖

• 部分函数依赖：主键是组合键时，组合键中，主键的某一部分已经可以确定该属性，那名称该依赖中存在部分函数依赖

  

• 传递函数依赖：A->B，B->C就是部分函数依赖

非规范化理论中可能出现的问题

在非规范化理论中，可能出现的问题包括：数据冗余、更新异常、插入异常、删除异常

键

超键，候选键，主键，外键

• 超键是唯一标识一个元组的属性组

• 当超键中消除掉多余的属性之后就变为候选键，候选键可以有多个

• 在多个候选键中任意选一个键，这个键就是我们所说的主键

• 外键一般联系的是其他关系上的主键

怎么求主键（候选码）：

• 首先将关系中的每个元素列出来，然后再看函数依赖，如果元素自始至终一直在函数依赖的左侧，那么该元素一定为主属性，如果某元素自始自终一直在函数依赖的右侧，那么该元素为非主属性，如果某个元素有时出现在左侧，有时又出现在右侧，那么该元素可能为主属性

• 之后，将通过上述方法筛选出来的主属性进行闭包运算，一个元素闭包无法推出所有的元素，尝试多个主属性推导闭包运算，能闭包运算推导出来的便是主键（候选码）

范式

模式分解

模式分解要遵循以下原则：

• 保持函数依赖

• 无损连接（可以还原）

判断一分为二的关系是否为无损分解：

例如假设关系R={R1,R2}

• 首先使用两个分解的关系求取他们之间的交集，之后分别进行R1-R2和R2-R1操作

• 之后将交集所求结果分别与结果集中的元素匹配得到的依赖和题目中所给的函数依赖相比较，只要有一组完全和函数依赖匹配，那么就说明为无损分解

• 

关系代数

基本的运算包括：并，交，差，笛卡尔积，选择，投影，连接

注意

并，交，差关系中，两个关系的属性字段必须一样

并发控制

事务

• 原子性（Atomicity）：事务是原子的，要么做，要么都不做。

• 一致性（Consistency）：事务执行的结果必须保证数据库从一个一致性状态变到另一个一致性状态。

• 隔离性（lsolation）：事务相互隔离。当多个事务并发执行时，任一事务的更新操作直到其成功提交的整个过程，对其它事物都是不可见的。

• 持久性（Durability）：一旦事务成功提交，即使数据库崩溃，其对数据库的更新操作也永久有效。

并发带来的问题

• 丢失更新

• 不可重复读

• “脏读”数据

解决：

• 一级封锁协议可以防止丢失修改

• 二级封锁协议可以防止丢失修改以及“脏读”数据

• 三级封锁协议可以防止丢失修改以及“脏读”数据，防止数据重复读取

• 两段锁协议可串行化但是可能发生死锁

E-R模型和关系模型

集成时产生的冲突以及解决方式：

• 属性冲突：属性域冲突和属性取值冲突（比如不同表中的同一个属性的不同数据类型）

• 命名冲突：包括同名异义和异名同义（两个表中的某个字段，取的名字是一样的，但是表达的意思是不一样的或者不同的意思的两个东西，但是名字一样）

• 结构冲突：同一对象在不同的应用中具有不同的抽象，以及同一实体在不同局部er图中所包含的属性个数和属性排列次序不完全相同（在某个表中，他可能是一个属性，单是在整个系统中有可能是一张表，级别不一样）

联系

• 一对多，一对一，多对多

数据库完整性约束

• 实体完整性约束

• 参照完整性约束

• 用户自定义完整性约束

• 触发器

数据库安全

• 用户标识和鉴定：最外层的安全保护措施，可以使用用户账户，口令以及随机数检验方式

• 存取控制：对用户进行授权，包括操作类型（增删改查）和数据对象（数据范围）的权限

• 密码存储和传输：对远程终端信息用密码传输

• 视图保护：对视图进行授权

• 审计：使用一个专用文件或者数据库，自动将用户对数据库的所有操作记录下来

数据备份

冷备份（静态备份）

• 将数据库正常关闭状态下，将数据库中的文件进行备份

• 优点

  • 快速

  • 易归档

  • 容易恢复到某个时间点

  • 与归档方法相结合，做数据库“最佳状态”时的恢复时的恢复

  • 低度维护，高度安全

• 缺点：

  • 单独使用时只提供某一个时间点上的恢复

  • 备份过程中数据库要停止其他运作，一心一意备份

  • 不能按表或者按用户恢复

  • 收外设介质的约束

热备份（动态备份）

• 在数据库运行时，利用备份软件进行备份

• 优点：

  • 支持表、文件级备份，备份时间短

  • 备份时，数据库可以做其他的事情

  • 恢复到某一个点时，速度很块

  • 可以对几乎所有数据库实体恢复

  • 恢复速度块

• 缺点

  • 出错后对dbms的损坏是毁灭性的

  • 热备份不成功所得结果不可用于恢复某个点

  • 维护困难

uml中的词汇表

包含三种构造快：

• 事物

• 关系

  • 依赖：是两个事物之间的语义关系，其中一个事物的变化会影响到另外一个事物的语义

    常见在某个类中使用某个其他的类

  • 关联：是一种结构关系，他描述一种链，链是对象之间的连接，两个类之间可以由多个不同角色标识的关联。

  • 泛化：是一种特殊/一般关系，特殊元素的对象可以替代一般元素的对象，这种方法，子元素共享父元素的结构和行为。

  • 实现：是类元之间的语义关系，其中类元一个类元指定了由另外一个类元保证执行的契约

• 图

多态

多态的实现受到继承的支持，利用类的继承的层次关系，把具有通用功能的消息存放在最高层次

几类多态

参数多态、包含多态、过载多态和强制多态四类。

包含多态是一个类型是另一个类型的子类型。

过载多态是同一个名字在不同的上下文中所代表的含义不同。

参数多态是应用广泛，最单纯的多态

强制多态是编译程序通过语义操作，把操作对象的类型强制转换，用来符合函数或者操作符的要求

动态绑定和静态绑定

• 动态绑定：强调在执行期间判断所引用对象的实际类型，根据其实际的类型调用其对应的方法，

• 静态绑定：（强调在执行时）把函数调用和响应调用的所需要的代码结合的过程称之为静态绑定

面向对象的几个阶段

进行面向对象分析（OOA）、面向对象设计（OOD）、面向对象实现和面向对象测试几个阶段。

分析阶段的目的是为了获得对应用问题的理解，确定系统的功能、性能要求，在此阶段主要关注系统的行为，明确系统需要提供什么服务。

设计阶段，采用面向对象技术将OOA所创建的分析模型转化为设计模型，其目标是定义系统构造蓝图。

实现阶段（面向对象程序设计），系统实现人员选用一种面向对象程序设计语言，采用对象、类及其相关概念进行程序设计，即实现系统。

UML中的几种图

对于一个复杂用例中的业务处理流程进行进一步的建模的最佳工具是uml的活动图

• 活动图：常见的形式是开始和结尾会有两个大黑点

  

• 顺序图：（用于表示系统中一个用例和多个对象的行为）

  

• 状态图

  

• 通信图

        

• 构件图：2符号形象叫棒棒糖，表示提供的接口；1符号形象叫插座，表示要求提供的接口。有这两个符号，这是一个组件图（构件图），系统构件和构件之间，类或接口之间的关系图。

类间关系

类间的关系可以分为：依赖，关联，聚合，组合，继承

依赖是两个事务间的语义关系，其中一个事物发生变化时会影响了一个事务的语义。若类A的方法中仅仅使用了类B的对象，那么类A依赖于类B。

泛化是一种特殊/一般关系，特殊元素（子元素）的对象可以替代一般元素（父元素）的对象，达到子元素可以共享父元素的结构和行为的目的。

关联是一种结构关系，描述一组对象之间连接的链，有单向关联、双向关联和自身关联（只涉及一个类）等。链上可以添加多重度、角色名称说明关联的对象数量以及行为。关联关系又有特殊类型，聚合和组合，用于描述部分和整体之间的结构关系，聚合暗示子类型独立于父类型而存在，比如班级和学生，班级删除之后，学生仍然可以存在。

组合暗示没有父类型，子类型无法独立存在， 如果类A的部分是由类B的对象组成，并且类A控制类B的生命周期，那么类A与类B是组合关系。

组合和聚合

组合（Composition）和聚合（Aggregation）都是关联（Association）的特殊种类。 组合是一种很强的“拥有”关系，部分和整体的生命周期通常一样。组合成的新对象完全支配其组成部分，包括它们的创建和湮灭等。一个组合关系的成分对象是不能被另一个组合构成的对象共享的。聚合同样表示“拥有”关系，但其程度不如组合强，有时候“部分”对象可以在不同的“整体”对象之间共享，并且“部分”对象的生命周期也可以与“整体”对象不同，甚至“部分”对象可以脱离“整体”对象而单独存在。一般而言，组合是值的合成（Aggregation by Value），而聚合是引用的合成（Aggregation by Reference ）。

设计模式

责任链模式和迭代器模式都是行为型对象模式。

• 责任链模式：通过给多个对象处理请求的机会，减少请求的发送者与接收者之间的耦合。将接收对象链接起来，在链中传递请求，直到有一个对象处理这个请求。

• 迭代器模式：提供一种方法来顺序访问一个聚合对象中的各个元素，而不需要暴露该对象的内部表示。

• 命令模式：将一个请求封装为一个对象，从而可用不同的请求对客户进行参数化，将请求排队或记录请求日志，支持可撤销的操作。

• 解释器模式：给定一种语言，定义它的文法表示，并定义一个解释器，该解释器用来根据文法表示来解释语言中的句子。

• 代理模式是为其他对象提供一种代理以控制对这个对象的访问，使得只有在确实需要这个对象时才对其进行创建和初始化。

• 桥接模式将对象的抽象和其实现分离，从而可以独立地改变它们，当一个抽象可能有多个实现吋，抽象类定义对该抽象的接口，而具体的子类则用不同方式加以实现。

• 组合模式描述了如何将对象组合成树形结构以构造一个层次结构来表示“部分-整体”，使得客户对单个对象和组合对象的使用具有一致性，这一结构由两种类型的对象所对应的类构成，使得可以组合基元对象以及其他的组合对象，从而形成任意复杂的结构。

• 装饰器模式则描述动态地给一个对象添加一些额外的职责。

• 外观模式为子系统中的一组接口提供一个一致的界面

• 享元模式运用共享技术有效地支持大量细粒度的对象。适用于：一个应用程序使用了大量的对象；完全由于使用大量的对象，造成很大的存储开销；对象的大多数状态都可变为外部状态；如果删除对象的外部状态，那么可以用相对较少的共享对象取代很多组对象：应用程序不依赖于对象标识。

• 装饰器模式描述了以透明围栏来支持修饰的类和对象的关系，动态地给一个对象添加一些额外的职责，从增加功能的角度来看，装饰器模式相比生成子类更加灵活。适用于：在不影响其他对象的情况下，以动态、透明的方式给单个对象添加职责；处理那些可以撤销的职责；当不能采用生成子类的方式进行扩充时。

• 工厂模式定义一个用于创建对象的接口，让子类决定将哪-个类实例化，使一个类的实例化延迟到其子类。适用于：当一个类不知道它所必须创建的对象的类的时候；当一个类希望由它的子类来指定它所创建的对象的时候；当类将创建对象的职责委托给多个帮助子类中的某一个，并且希望将哪一个帮助子类是代理者这一信息局部化的时候。

• 观察者模式定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。适用于：当一个抽象模型有两个方面，其中一个方面依赖于另一个方面，将这两者封装在独立的对象中以使它们可以各自独立地改变和复用；当对一个对象的改变需要同时改变其他对象，而不知道具体有多少对象有待改变时；当一个对象必须通知其他对象，而它又不能假定其他对象是谁，即不希望这些对象是紧耦合的。

• 中介者模式用一个中介对象来封装一系列的对象交互。中介者使各对象不需要显式地相互引用，从而使其耦合松散，而且可以独立地改变它们之间的交互。适用于：一组对象以定义良好但是复杂的方式进行通信，产生的相互依赖关系结构混乱且难以理解；一个对象引用其他很多对象并且直接与这些对象通信，导致难以复用该对象；想定制一个分布在多个类中的行为，而又不想生成太多的子类。欲使一个后端数据模型能够被多个前端用户界面连接，采用中介者模式最合适。

注意点

• 面向对象分析的第一步为确认问题域

• 面向对象技术中，对象应该具有：清晰的边界、良好定义行为、可扩展性

• 面向对象分析与设计中，实体主要负责数据和业务逻辑，边界类负责和用户交互（用户界面）、控制类负责实体类和界面类的交互。

• 在面向对象方法中，支持多态的是动态绑定

• 对象的状态标识了该对象的所有属性（通常是静态的）以及每个属性的当前值（通常是动态的）

沟通路径的计算方法

n个成员的沟通路径的计算公式为：{(n-1)*n}/2

值传递与地址传递

• 在地址传递的情况下，形参和实参之间可以实现数据的双向传递

• 地址方式的传递中，需要将实参的地址传递给形参，此时，实参必须是变量

语言及其分类

动态语言：程序运行时可以改变结构，类型检查是在运行时进行，便于阅读，不需要写过多关于类型的代码（弱类型语言）

脚本语言：参考python

栈区和堆区称为动态数据区，全局变量的存储在静态数据区

汇编语言编写的程序要由汇编程序将汇编语言翻译成机器语言，汇编程序输入的是用汇编语言书写的源程序，输出的是用机器语言表示的目标程序。

程序的执行

常量和变量

• 常量在程序运行过程中不能被修改，具有类型

• 常见的命名对象有：变量，函数，数据类型

• 规定数据类型语言的好处：

  • 翻译程序的过程中为数据分配合理的存储单元

  • 有利于对参与表达式计算的数据对象检查

  • 有利于规定对象的取值范围

编译程序和解释程序

• 解释方式下，翻译源程序时不生成独立的目标程序，编译程序则会将源程序翻译成独立保存的目标程序或中间代码

• 编译程序不参与用户程序的运行控制，解释程序参与，编译将会生成一个符号表

• 编译过程中为变量分配的一般是逻辑地址，程序运行时的一般是物理地址

执行过程

• 词法分析的输出是记号流，也就是语法分析的输入

• 编译程序分析源程序阶段依次是：词法，语法，语义

  • 词法分析是对字符逐个扫描，从中识别一个一个的单词符号

  • 语法规则是将单词符号序列分解为各种表达式、语句、程序等单位，主要针对结构的检查；表达式不完整、缺少必要的标点符号、关键字输入错误、数据类型不匹配、循环语句或选择语句的关键字不匹配等

  • 语义分析是分析语法结构的含义。

• 中间代码：与具体的机器无关，可以有若干种，可以将不同的高级语言翻译为中间代码，有利于与机器无关的优化处理以及提高编译的可移植性。中间代码可以用栈和队列表示，常见的中间代码有后缀式，三地址码，语法树

• 编译错误：idea的红色波浪线的就是编译错误，编译正确的程序必然不包含语法错误

反编译

反编译通常不能把执行文件转换为高级语言的源代码

词法 语法 语义

词法分析是编译过程的第一阶段，其任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个的“单词”符号。

语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”、“语句”和“程序”等（结构是否合法）。

语义分析阶段主要检查源程序是否包含语义错误，并收集类型信息供后面的代码生成阶段使用。

语法错误是指语言结构上的使用错误，是指编译时所发现的程序错误，如单词拼写错误、标点符号错、表达式中缺少操作数、括号不匹配等有关语言结构上的错误。

语义错误（逻辑错误）在编译阶段不会发现错误，往往是运行结果错误；代码的逻辑有问题，但是编译一般会运行正常。

语法分析有两种：至上而下，至下而上（移进归约分析法）

有限自动机和无限自动机

（用于词法分析）

补充部分

• 根据算术表达式计算逆波兰式的步骤（逆波兰式是利用的栈求职）：

  • 先根据算术表达式画出对应的二叉树

  • 将上部所求得的二叉树后序遍历

• 运行时结合是动态绑定，编译时结合是静态

• 程序语言的大多数语法现象可以用乔姆斯基的上下文无关文法描述

• 语法制导翻译是一种静态语义分析

存储管理

常用的I/O接口编址方法

• 统一编址方式下，是将I/O接口中有关的寄存器或存储部件看作存储器单元，与主存中的存储单元统一编址。这样，内存地址和接口地址统一在一个公共的地址空间里，对I/O接口的访问就如同对主存单元的访问一样，可以用访问内存单元的指令访问I/O接口。

• 单独编址是指通过设置单独的I/O地址空间，为接口中的有关寄存器或存储部件分配地址码，需要设置专门的I/o指令进行访问。这种编址方式的优点是不占用主存的地址空间，访问主存的指令和访问接口的指令不同，在程序中容易使用和辨认。

位视图的相关计算问题

直接上题：

选择题 某文件管理、统在磁盘上建立了位示图 （bitmap），记录磁盘的使用情况。若系统的字 长为32位，磁盘上的物理块依次编号为0、1、 2、…， 那么4096号物理块的使用情况在位示图 中的第（）个字中描述：若磁盘的容量为200GB.物理块的大小为1MB、那么位示图的大小为 （）个字。

解析：

• 系统中字长为32位，可记录32个物理块的使用情况，这样0〜31号物理块的使用情况在位示图中的第1个字中描述，32〜63号物理块的使用情况在位示图中的第2个字中描述，……，4064〜4095号物理块的使用情况在位示图中的第128个字中描述，4096〜4127号物理块的使用情况在位示图中的第129个字中描述。 （使用所求物理块/系统字长）

• 若磁盘的容量为200GB，物理块的大小为1MB，那么该磁盘就有204800个物理块（即200x1024），位示图的大小204800/32=6400个字。（求出物理块个数，就是把磁盘容量gb化为mb，之后该结果除系统字长除以物理块大小即可）

银行家算法

n个进程竞争某类资源，并且都需要m个该类资源，那么至少需要有（m-1）*n+1个该类资源，才能保证系统不会发生死锁

磁盘调度管理

• 一般磁盘调度先进行移臂调度找磁道，再进行旋转调度找扇区

相关的计算题

例题：假设磁盘臂位于15号柱面上，进程的请求序列如下表表示，果采用最短移臂调度算法，那么系统的响应序列应为

解释：首先这里是使用最短移臂调度算法，现在臂位于15号柱面的位置上，最近调度的原则，下一个将会是12号面，从上到下第一个九尾12，之后表格中还有12号面那么之后将会访问下面的哪一个2号面，以此类推。。。

• 在移臂调度中，先来先服务和最短寻找时间优先算法可能会导致随时改变移动臂的运动方向

• 页面淘汰的基本思想：

  • 当访问的页面不在内存时，系统应该首先淘汰未被访问的页面，因为根据程序的局部性原理，最近未被访问的页面下次被访问的概率更小；如果页面最近都被访问过，应该先淘汰未修改过的页面。因为未修改过的页面内存与辅存一致，故淘汰时无需写回辅存，使系统页面置换代价小。

SCAN(扫描调度算法)

简单的说就是在当前环境下找到最近的一个柱面排到最大后剩余的小柱号按从大到小往下排列，之后形成的序列即为所求

CSCAN(单向扫描调度算法)

文件读取问题

某磁盘有100个磁道，磁头从一个磁道 移至另一个磁道需要6ms。文件在磁盘上非连续 存放，逻辑上相邻数据块的平均距离为10个磁 道，每块的旋转延迟时间及传输时间分别为100 ms和20ms，则读取一个100块的文件需要（）ms

这里，读取一块的时间为：10*6=60，旋转延迟时间以及传输时间为：120ms，于是一块需要花时间60+120=180ms，100块需要：1800ms

逻辑地址与物理地址之间的转换

例：

选择题 某计算机、统页面大小为化，进程的 页面变换表如下所示。若进程的逻辑地址为2D16H。该地址经过变换后，其物理地址应为

有简单方法：直接看逻辑地址的首位数字，为2，之后看这个表上页号对应的数字2对应的是4，那么物理地址就是将之前的逻辑地址的首数字改为4即可，即4D16H

单缓冲与双缓冲之间的计算

假设磁盘块与缓冲区大小相同，每个盘 块读入缓冲区的时间为15μs，由缓冲区送至用 户区的时间是5μs，在用户区内系统对每块数据 的处理时间为lμs，若用户需要将大小为10个磁 盘块的Doc/文件迹块从磁盘读入缓冲区，并送至 甲户区进行处理，那么采用单缓冲区需要花费 的时间为（/）μs；采用双缓冲区需要花费的时 面为（）μS。

记住，单缓冲的话需要用（每个盘读入缓冲区的时间+由缓冲区送至用户区的时间）×盘块数量+系统对每块数据的处理时间

双缓冲只需要 每个盘读入缓冲区的时间×盘块数量+系统对每块数据的处理时间+由缓冲区送至用户区的时间

双缓存无需给每个缓冲传输时间算计在次数中

进程管理

三态和五态模型

pv操作

假设系统中n个进程共享m个资源，那么信号量s的取值范围为：-(n-m)~m

利用pv操作可以实现资源的互斥使用

前驱图

• 第一种：

  • 遇到这种前驱图的题目牢记“上p下v，从上到下，从左到右即可”

• 第二种：

  • 某计算机系统中有一个CPU、一台输入 设备一台输出设备，假设、统中有三个作业下 L、T2T3，系统采用忧先级调度，且T/的优先 级72的优先级73的优先级。若每个作业具有 三个程序段：输入I5、计算C和输出P、（i=1， 2，3），执行顺序为LI、C：P.则这三个作业各 程序段并发执行的前驱图如下所示。图中D、 ②分别为（），③、④分别为（/），、6 分别为（/）。选择题 某计算机系统中有一个CPU、一台输入 设备一台输出设备，假设、统中有三个作业下 L、T2T3，系统采用忧先级调度，且T/的优先 级72的优先级73的优先级。若每个作业具有 三个程序段：输入I5、计算C和输出P、（i=1， 2，3），执行顺序为LI、C：P.则这三个作业各 程序段并发执行的前驱图如下所示。图中D、 ②分别为（），③、④分别为（/），、6 分别为（/）。

    

    解决方案：这种题目很简单，利用规律将该图补充完整即可：

    

操作系统定义分类以及功能

操作系统是裸机上的第一层软件，其他系统软件和应用软件都建立在其上

操作系统的两个重要作业：

• 资源管理

• 改善人机界面，为用户提供良好的工作环境

补充

• 如果计算机系统的i/o接口与主存采用统一编址，那么输入输出操作是通过访存指令来完成的

• 在计算机运行过程中，cpu需要与外设进行数据交换，采用中断方式和DMA方式控制技术时，cpu与外设可以并行工作

• 用户利用“磁盘管理”程序可以对磁盘进行初始化，初建卷，可以选择使用FAT，FA32或NTFS文件系统格式化卷

• 假设某分时系统中采用简单时间片轮转法，当系统中的用户数量为n时，时间为q时，系统对每个用户的响应时间为T=n*q

• 实时系统对于来自外部的事件必须在被控对象规定时间内做出及时响应对其进行处理

• 在同一进程中的各个线程都可以共享该进程所拥有的资源，但是不能共享进程中某线程的栈指针。

• 当用户双击一个文件名时，windows系统通过建立的文件关联来决定使用什么程序打开该文件

• 嵌入式系统初始化过程主要有三个阶段，依次是：片级初始化 板级初始化 系统级初始化

  • 片级初始化完成嵌入式微处理器的初始化，包括设置嵌入式微处理器的核心寄存器和控制寄存器、嵌入式微处理器核心工作模式和嵌入式微处理器的局部总线模式等。片级初始化把嵌入式微处理器从上电时的默认状态逐步设置成系统所要求的工作状态。这是一个纯硬件的初始化过程。

  • 板级初始化完成嵌入式微处理器以外的其他硬件设备的初始化。另外，还需设置某些软件的数据结构和参数，为随后的系统级初始化和应用程序的运行建立硬件和软件环境。这是一个同时包含软硬件两部分在内的初始化过程。

  • 系统初始化过程以软件初始化为主，主要进行操作系统的初始化。BSP将对嵌入式微处理器的控制权转交给嵌入式操作系统，由操作系统完成余下的初始化操作，包含加载和初始化与硬件无关的设备驱动程序，建立系统内存区，加载并初始化其他系统软件模块，如网络系统、文件系统等。最后，操作系统创建应用程序环境，并将控制权交给应用程序的入口。

• i/o设备管理软件一般分为四个层次，具体层次从上往下分别是用户级i/o层，设备无关i/o层，设备驱动程序，中断处理程序，硬件

  • 硬件：完成具体的I/O操作。

  • 中断处理程序：I/O完成后唤醒设备驱动程序。

  • 设备驱动程序：设置寄存器，检查设备状态。

  • 设备无关I/O层：设备名解析、阻塞进程、分配缓冲区。

  • 用户级I/O层：发出I/O调用。

• 线性结构

• 非线性结构（图，树）

数组

注意题设是按行存储还是使用的列存储

稀疏矩阵

题设一般是要求得对应元素的下标，这里推荐使用的是代入法

线性表

顺序表和链表

顺序存储与链式存储对比

查找是在无须的情况下时间复杂度一样

栈和队列

• 栈是先进先出，队列是先进后出

• 循环队列，就是将队列的头尾相连结

  • 队空条件：头指针=尾指针

  • 队满条件：（尾指针+1）%最大容量=头指针（可以理解为尾指针下一个元素是头指针的话就是队满）

广义表

是线性表的推广

这个广义表中：

• 表头：a

• 表尾：(b,c),(d,e)

• 长度：表中包含的一级子表

• 深度：包含括号的层数，嵌套的最大次数

树与二叉树

满二叉树

树上没有缺失节点

完全二叉树

优先左节点上的树排满，否则不是，允许缺失右子树，不允许缺失左子树

二叉树上的一些重要的特性

二叉树遍历

• 层次遍历

• 前序遍历

• 中序遍历

• 后序遍历

树转二叉树

基本原则：

• 在一个树中，一个节点的孩子节点，都将成为二叉树的左子树结点

• 在一个树中，一个节点的兄弟节点，都将成为二叉树的右子树结点

• 如果有多个孩子，那么将这些孩子中最左边的作为左子树节点

• 如果有多个兄弟，那么将这些兄弟中最左边的作为右子树节点树转二叉树

  基本原则：

  • 在一个树中，一个节点的孩子节点，都将成为二叉树的左子树结点

  • 在一个树中，一个节点的兄弟节点，都将成为二叉树的右子树结点

  • 如果有多个孩子，那么将这些孩子中最左边的作为左子树节点

  • 如果有多个兄弟，那么将这些兄弟中最左边的作为右子树节点

反向构造二叉树

知道前中，中后可以反向构造出二叉树，前后不能推导出一个唯一的二叉树

查找二叉树（二叉排序树）

• 左孩子小于根节点

• 右孩子大于根节点

最优二叉树（哈夫曼树）

• 用于哈夫曼编码，用于压缩编码方式，无损压缩

• 带权路径长度：从根节点出发到该叶子节点的路径长度×叶子节点权长

线索二叉树

节点中存在大量的左或右节点缺失导致空间浪费

前序线索：首先先将树前序遍历，之后找到叶子节点，左孩子指针指向前序遍历的前驱节点，右孩子指针指向前序遍历的后继节点

后序和中序以此类推

平衡二叉树

• 任意节点的左右子树深度相差不超过1，每个每个节点的平衡度只能为1，0，-1

• 一个排序二叉树越平衡，这个二叉树的查找效率越高

图

存储方法

矩阵的大小取决于节点的数量，有n个节点，那么矩阵的大小为n×n

• 无向图在矩阵中关于对角线对称

邻接表的方式：首先将每个顶点的邻接顶点用链表表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针

图的遍历

• 深度遍历

  • 按照邻接的循序进行访问

• 广度遍历

拓扑排序

表示有向边之间开始的先后关系，称为活动网络，简称aov网络（后面的活动图的原来就是如此）

图的最小生成树

树的节点是n，变条数最大是n-1

• 普利姆算法：

  • 任选一个节点之后在剩余的节点中寻找与该节点最短距离的节点两节点相连接，之后将最短路径的节点作为开始节点寻找下一个最短路径的节点

• 克鲁斯卡尔算法：

  • 首先需要选择n-条最短边，任选一个顶点开始，从小到大选择出来之后（注意不要形成环路）树即为所求

算法

• 有穷，确定，0个或0个以上的输入，至少有一个输出，有效

查找

• 顺序查找：的时间复杂度O(n)，等概率的情况下，平均查找长度为（n+1）/2

• 二分查找法：（使用前提一定要是元素顺序排列）

  • 折半查找在查找成功时关键字的最多比较次数为[log2N]+1次

  • 时间复杂度为O（log2N）

• 散列表查找：基本规则是根据规则进行查找，线性探测法解决冲突

排序

分为稳定和不稳定排序，不稳定排序是同样的两个元素排序之后两者之间的前后顺序发生了变化

• 插入排序

  • 直接插入排序（排序速度会比较慢）

    开始时将前两个数字进行比较排出序列之后拿之后的元素分别先与前一个数字比较，如果比前者大就不动，如果小就继续向下比较，直到找到正确的插入位置

    

  • 希尔排序

    基本思想是分组，假设有n个元素，第一次与嗝n/2个元素的两个元素为一组，之后再次对半n/2/2（取奇数）,再两个两个一组（实际上是一种分组插入方法）

    

• 交换类排序：

  • 冒泡排序

    将较小的元素从底部往顶部元素相比较，找到合适的位置后停止移动

    

  • 快速排序（分治法排序）

    一开始定义一个基准指针和一指向末端的指针，之后拿序列中的元素一个个交换匹配交换匹配，之后形成一个基准在中间，两边分别为小于基准的元素集合和大于基准的元素集合之后分别将这两个集合排序，排完序后得到的序列即为排序后的序列

    

• 选择类排序

  • 选择排序

    首先在所有的序列元素中选择出最小的与第一个交换，之后再在剩余的序列中选择出一个最小的与第二个交换，依次类推

    

  • 堆排序

    如果是小堆，找到最后一个非叶子节点之后拿这个非叶子节点和其子节点相比较，如果子节点有比该节点还小的，两者替换，之后依次类推，大堆反之

    

• 归并排序

  将两个或者两个以上的有序子列合成一个新的序列表，假设将两个有序表合并成一个有序表合并过程为：将子序列中的第一个元素分别与下一个子序列的每个元素相比较，然后把比较过后的较小或者较大的元素复制在一个R序列表中

  

• 基数排序

  将每个元素按位拆分之后排序

  
  

算法应用

分治法

将一个规模为n的问题分解为多个规模较小的子问题，这些子问题互相独立，与原问题形式相同，递归的解决这些子问题，之后将各个子问题合并得到原问题的解

主要步骤为：分解，解决，合并

• 递归技术

回溯法

经典的迷宫问题

是一种优先深度搜索法，当搜索到某一步时，发现原先选择并不优或者达不到目标，就退回一步重新选择，既走不通就退回

贪心法

总是做出在当前来说最好的选择，并不是从整体上考虑，他所作的每一步都是在当前步骤上的局部最优选择，但是从整体上来讲并不是最优的选择，使得速度比较快，于是很难达到最好最优解

• 背包问题

动态规划法

也会将原问题分解为多个子问题之后再得到原问题的解，子问题可能不独立，有关系，需要依靠表格存储

补充

• 动态规划法一般需要依靠查表的方法来解决问题

常考部分：

• 著作权产生时间：自作品完成创作开始

• 我国授予专利权采用先来先得的原则，如果两个人同时申请，可以自行协商

• 翻译权是将某款软件从某种语言转换为另外一种语言

• 软件著作权的客体是计算机软件，即计算机程序以及相关文档

• 职务作品一般未经其他的约定其著作权均有公司享有

• 保护期受时间限制的有：发表权，（发明专利权，实用新型专利权为20年，外观设计权期限为10十年，可以延期）

• 商标归属：先来先得，先用先得的原则，如果两个人同时申请，可以自行协商，若不，抽签方式决定

• 《中华人民共和国著作权法》，《计算机软件保护条例》是构成我国保护计算机软件著作权的两个基本法律文件

• 我国《著作权法》对著作权的保护期限作了如下规定：著作权中的署名权、修改权、保护作品完整权的保护期不受限制。

• 第一种是依法禁止出版、传播的作品。第二种是不适用于《著作权法》的作品。它们包括下列作品：1.法律、法规，国家的决议、决定、命令和其他具有立法、行政、司法性质的文件，极其官方正式译文；2.时事新闻；3.历法、通用数表、通用表格和公式。不受著作权法保护。

cmmi和cmm的区别

CMMI成熟度级别：

1. 初级（Level 1）：无序的过程，没有明确定义的过程，依赖个人技能。

2. 可重复（Level 2）：过程已被定义并可重复执行，基于过去的经验。

3. 定义（Level 3）：过程已被标准化和文档化，并在整个组织范围内使用。

4. 管理过程（Level 4）：过程已被量化和管理，通过收集和分析数据来进行过程改进。

5. 优化（Level 5）：过程已被优化和持续改进，以达到最佳绩效水平。

CMM能力级别：

1. 初始（Level 1）：过程是不可预测的，依赖于个人能力。

2. 可重复（Level 2）：过程已被重复执行，但仍然是不可预测的。

3. 定义（Level 3）：过程已被标准化和文档化，并在整个组织中使用。

4. 管理（Level 4）：过程已被量化和管理，通过数据收集和分析来进行过程改进。

5. 优化（Level 5）：过程已被优化和持续改进，以达到最佳绩效水平。

环路复杂度的计算

环路复杂度的计算公式为：(线数量-节点数量)+2

子特性

iso/iec9126软件质量模型中有以下子特性：

• 功能性：

  • 适合性

  • 准确性

  • 互用性

  • 依从性

  • 安全性

• 可靠性：

  • 成熟性

  • 容错性

  • 易恢复性

• 易使用性

  • 易理解性

  • 易学性

  • 易操作性

• 效率

  • 时间特性

  • 资源特性

• 可维护性：

  • 易分析性

  • 易改变性

  • 易测试性能

  • 稳定性

• 可移植性

  • 适应性

  • 易安装性

  • 一致性

  • 易替换性

统一过程

统一过程定义了初起阶段、精化阶段、构建阶段、移交阶段，每个阶段达到某个里程碑时结束。初起阶段的里程碑是生命周期目标 ，精化阶段是生命周期框架，构建阶段的里程碑是初始运作功能，移交阶段的里程碑产品的发布。

冗余附加技术

在屏蔽硬件错误的容错技术中，冗余附加技术包括：关键程序和数据的冗余以及调用；检查、表决、切换、重构、复算的实现。

软件设计质量评审

通常从以下几个方面进行评审：

• 评价软件的规格说明是否合乎用户的要求，即总体设计思想和设计方针是否明确；需求规格说明是否得到了用户或单位上级机关的批准；需求规格说明与软件的概要设计规格说明是否一致等。

• 评审可靠性，即是否能避免输入异常（错误或超载等）、硬件失效及软件失效所产生的失效，一旦发生应能及时采取代替手段或恢复手段。

• 评审保密措施实现情况，即是否对系统使用资格进行检查；是否对特定数据、特定功能的使用资格进行检查；在检查出有违反使用资格的情况后，能否向系统管理人员报告有关信息；是否提供对系统内重要数据加密的功能等。

• 评审操作特性实施情况，即操作命令和操作信息的恰当性，输入数据与输入控制语句的恰当性；输出数据的恰当性；应答时间的恰当性等。

• 评审性能实现情况，即是否达到所规定性能的目标值。

• 评审软件是否具有可修改性，可扩充性、可互换性和可移植性。

• 评审软件是否具有可测试性。

• 评审软件是否具有复用性。

结构化分析和设计

数据流图

• 结构化方法进行系统分析时，一般使用数据流图来建立系统的逻辑模型

• 数据流图的组成：实体，数据存储，处理过程和处理流，顶层的数据流图描述了系统的输入与输出

• 数据流图中的基本加工：

  • 基本加工的说明有三种描述方案：结构化语言、判断表（决策表）、判断树（决策树）

  • 基本加工逻辑的基本描述为：

    • 必须有个基本加工说明

    • 必须描述基本加工如何把输入数据流变换为输出数据流的加工规则

    • 必须描述实现加工策略而不是实现加工的细节

    • 逻辑中包含的信息是充足的，完善的，有用的，无冗余的

结构化分析阶段

结构化分析阶段出来的产物将运用于结构化设计阶段

结构化设计（依据分析阶段的数据流图，分析软件与外部环境之间的交互关系，软件内模块之间的调用关系）

结构化设计主要包含：

• 体系结构设计（定义软件的主要结构元素以及关系）

• 数据设计（文件系统结构，数据库表结构）

• 接口设计（构件之间的内部接口，描述用户界面，外部接口）

• 过程设计（软件各个组成部分的算法以及内部的数据结构，并选用各种表达书来描述各种算法）

系统结构图又称为模块结构图，是软件概要设计中的工具，包括：模块、模块之间的调用关系、模块之间的通信、辅助控制符号（模块，调用，通信，控制）

系统设计知识

软件设计为系统制定蓝图，关注系统的总体结构、代码设计、处理过程、数据结构和界面模型

对于软件设计过程中，需要遵循高内聚，低耦合，模块大小适中

耦合

根据耦合性从低到高为非直接耦合、数据耦合、标记耦合、控制耦合、外部耦合、公共耦合和内容耦合。

• 如果一个模块访问另一个模块时，彼此之间是通过数据参数（不是控制参数、公共数据结构或外部变量）来交换输入、输出信息的，则称这种耦合为数据耦合；

• 如果一组模块通过数据结构本身传递，则称这种耦合为标记耦合；

• 若一组模块都访问同一个公共数据环境，则它们之间的耦合就称为公共耦合；

• 若一个模块直接访问另一个模块的内部数据、一个模块不通过正常入口转到另一个模块内部、两个模块有一部分程序代码重叠或者一个模块有多个入口，上述几个情形之一发生则说明两个模块之间就发生了内容耦合。

内聚

巧合内聚，指一个模块内的各处理元素之间没有任何联系。

逻辑内聚，指模块内执行几个逻辑上相似的功能，通过参数确定该模块完成哪一个功能。

时间内聚，把需要同时执行的动作组合在一起形成的模块。

通信内聚，指模块内所有处理元素都在同一个数据结构上操作，或者指各处理使用相同的输入数据或者产生相同的输出数据。

顺序内聚，指一个模块中各个处理元素都密切相关于同一功能且必须顺序执行，前一个功能元素的输出就是下一个功能元素的输入。

功能内聚，是最强的内聚，指模块内所有元素共同完成一个功能，缺一不可。

注意点：过程内聚要求模块内各程序块之间上个程序块的输出是下个程序块的输入；顺序内聚模块内各部分程序块之间只有执行的时间序列的要求。

测试和维护

系统测试阶段的测试目标来自于需求分析阶段

仓库风格

数据库系统、超文本系统和黑板系统都属于仓库风格。

该体系结构的优点包括：

• 对可更改性和可维护性的支持；

• 可复用的知识源；

• 支持容错性和健壮性。

缺点包括：

• 测试困难；

• 不能保证有好的解决方案；

• 难以建立好的控制策略；

• 低效；

• 昂贵的开发工作；

• 缺少对并行机制的支持。

软件维护工具

• 版本控制

• 文档分析

• 开发信息库

• 逆向工程

• 再工程

• 配置管理支持

软件维护性指标

• 可理解

• 可测试

• 可修改

• 可移植

• 可使用

• 可靠

• 效率

几种维护判断：

在软件开发完成交付用户使用后，就进入软件运行/维护阶段。软件维护活动根据其内容可以分为4种类型：

改正性维护，为了识别和纠正软件错误、改正软件性能上的缺陷、排除实施中的误使用，应进行的诊断和改正错误的过程；

适应性维护，由于信息技术飞速发展，软件运行的外部环境或数据环境可能会发生变化，为了使软件适应这种变 化，而修改软件的过程；

完善性维护，在软件使用过程中，用户往往会对软件提出新的功能与性能要求，为了满足这些要求，需要修改或再开发软件，以扩充软件功能、增强软件性能、改进加工效率、提高软件的可维护性而进行的维护活动；

预防性维护是为了提高软件的可维护性和可靠性等，为以后进一步改进软件打下良好基础而进行的维护工作。

自顶向下集成和自下向顶集成

顶向下集成优点:较早地验证了主要控制和判断点;按深度优先可以首先实现和验证一个完整的软件功能;功能较早证实，带来信心;只需一个驱动，减少驱动器开发的费用;支持故障隔离。缺点:柱的开发量大;底层验证被推迟;底层组件测试不充分。适应于产品控制结构比较清晰和稳定;高层接口变化较小;底层接口未定义或经常可能被修改;产口控制组件具有较大的技术风险，需要尽早被验证;希望尽早能看到产品的系统功能行为。

自底向上集成优点:对底层组件行为较早验证;工作最初可以并行集成，比自顶向下效率高;减少了桩的工作量;支持故障隔离。缺点:驱动的开发工作量大;对高层的验证被推迟，设计上的错误不能被及时发现。适应于底层接口比较稳定;高层接口变化比较频繁;底层组件较早被完成。

软件测试

好的软件测试用例中不包含多个等价无效类

• 白盒测试的几种测试方式：

  逻辑覆盖，语句覆盖是指选择足够的测试数据使被测试程序中每条语句至少执行一次。

  判定覆盖是指选择足够的测试数据使被测试程序中每个判定表达式至少获得一次“真”值和“假”值。

  条件覆盖是指构造一组测试用例，使得每一判定语句中每个逻辑条件的各种可能的值至少满足一次。

  路径覆盖是指覆盖被测程序中所有可能的路径。

• 黑盒测试中的几种测试方法：

  错误猜测、边界值分析、等价类划分

注意

• 外部实体一般为组织机构、人员、、第三方系统

• 数据流图建模：自顶向下，从抽象到具体

• 数据字典：数据字典是指对数据的数据项、数据结构、数据流、数据存储、处理逻辑、外部实体等进行定义和描述，目的是对数据流程图中的各个元素做出详细说明；数据字典中包含数据流、数据项、数据存储、基本加工

• 人交互的“黄金三原则”包括：置于用户控制之下，减少用户的记忆负担，保持界面的一致性