计算机复习要点和难点

1、计算机技术复习要点和难点林筱源 编第1章 绪论图灵模型-可编程数据处理器图灵模型是一种适用于通用计算机的模型冯诺伊曼计算机基于冯诺伊曼模型的计算机被划分为4大子系统：存储器、算术逻辑单元、控制单元、输入输出单元。计算机由三大部分构成：硬件、软件、数据。程序和数据都存储在存储器中。程序由指令序列构成,顺序执行。使用二进制。计算和计算机发展历史机械计算机器(1930年之前)：第一台利用存储和编程概念的机器是Jacquard loom(提花织机)。电子计算机的诞生(19301950)：第一台通用的、完全电子化的计算机ENIAC(1946年美国宾州大学)(冯.诺伊曼模型)计算机的诞生(1950年至今)

2、：第一台基于冯氏思想的计算机EDVAC(1950年宾夕法尼亚大学)计算机时代划分第一代（19501959年）商用计算机为主要特征,限于计算机专家使用。计算机体积庞大,使用真空电子管作为电子开关，费用昂贵。第二代（19591965年）晶体管代替真空管，减小体积与功耗，费用减低，开始应用到中小企业。Fortran和Cobol高级语言出现，编程更容易，编程任务和计算机运算任务分离。第三代（19651975年）集成电路的应用，进一步减小计算机体积和成本，配操作系统。小型计算机出现，软件业诞生。第四代（19751985年）大规模和超大规模集成电路应用，微型计算机、单板机的出现。计算机网络出现。第五代（1

3、985年至今）掌上电脑、笔记本电脑的诞生，第二代存储媒体（CD-ROM、DVD）的改进，多媒体应用，虚拟现实等第2章 数字系统十进制转其它进制整数：除基取余；小数：乘基取整。例：转124.02为二进制和八进制-从小数点出发,往左除2取余;往右乘2取整1<-3<-7<-15<-31<-62<-124 .02->.04->.08->.16->.32->.64->.28->.560 0 1 1 1 1 1 0 0 。0 0 0 0 0 1 0 1 0 二进制：1111100.000001011 7 4 。 0 1 2 八进

4、制：174.012建议：1)用位权凑数法验证甚至取代! 2)转十六进制或八进制可先转成二进制再行转换不易错。二进制十六进制(八进制)互转 见上例按照4位(3位)从小数点出发分组：整数从右向左分组，小数从左向右分组，不足4位(3位)补零，分别转换。第3章 数据存储位(bit)、字节(Byte)、字(Word)8 b=1 B；1n B=1 W(n随具体机型不同)。注：内存最小存储单位是1字节，但实际每次存取以字为单位。存储数字成为机器数存储数字的基本问题是如何把可能带正负符号和小数点的字面数完全用二进制位形式表示出来，成为所谓的机器数。机器数总是定长表示的，所谓位模式，常见8位、16位。无符号整数

5、存储表示没有正负符号的整数(0无穷大)表示：用8位可表示0255、16位表示065535。有符号整数存储表示有符号加绝对值表示法(原码)、反码、补码，补码普遍实际使用。其共同特点是把其最高位用作符号位：0为正1为负。但只有负数才有原码、反码和补码的区别；正数大家都一样，均使用原码的表示法。使用补码有如下优点：1)0有唯一的表示。而原码、反码均有+0和-0两种表示。2)补码运算,其符号位可当作普通数位直接参与运算,其结果(包括新符号位)仍正确,这大大方便了运算处理简化了运算器设计。3)由于1)的缘故，补码能表示数的范围比原码、反码多出一个数，如8位补码形式表示范围为：-128127。而原码、反码

6、均为-127127。例:如机器数用8位一个字节表示，写出6和-6的原码、反码和补码。由于6的二进制数为110，其：正数6的机器数原码、反码和补码均相同，为110左添0补足8位即00000110 (与无符号数也相同)。负数-6的机器数其原码、反码和补码各不同：。原码=10000110 (编码的最高位即左端首位用作符号位：0为正1为负；右端数位部分放110左添0补足7位)反码=11111001 (原码的数位部分取反=>反码)补码=11111010 (反码+1=>补码) 直接写补码可参看以下例子：负数-6如直接写补码可法一：取绝对值二进制数:110->补足8位:00000110-&

7、gt;取反:11111001->加1：11111010法二(简单不易错)：取绝对值二进制数:110->补足8位:00000110->右侧连续0及首个1不变，其余位取反:11111010(一)如上述“补码运算”定义为“求补”：对任何机器数“取反加1”或“右侧连续0及首个1不变，其余位取反”,则上例可理解为6机器数00000110求补则得-6机器数11111010负数的补码：等于其对应正数(即其绝对值)机器数求补(即取反加1或右侧连续0及首个1不变，其余位取反)任意机器数(无论正负),求补一次得其负值(相反数);求补两次得回其原值一个机器数不管其正负，只要执行一次补码运算就必得到

8、其相反数的机器数形式，即正机器数得负机器数(利用此写出负数的补码)；负机器数得正机器数(利用此得出负数的真值)例一: 问11111101其真值为何?11111101求补得00000011,原数的负值为3,故原数为-3例二: 问01111111其负值如何表示(原数为+127此即问-127补码如何表示)?01111111求补得10000001,此即其负值(-127)。另可注意到：10000001-1=10000000即-127-1=-128此为8位补码可表示的最小值(二)补码运算,其符号位可当作普通数位直接参与运算,其结果(包括新符号位)仍正确,这极大简化了运算处理(不必单独考虑符号位)难点：一个

9、溢出数的机器数表示方法总结如下：正数(溢出)-直接写其二进制无符号数表示，并取其位模式即可(超长时左端可以被切除)。无符号数同此。实际与不溢出做法一样。例：342的8位机器数：101010110取右8位得01010110实际为342对256求余数：342%256=86负数(溢出)-补码：与不溢出做法一样即：取绝对值(正数)二进制数->(数太大可能会超过位模式长可以切左端)取位模式长->求补(右侧连续0及首个1不变，其余位取反)。例：-342的8位补码：101010110取右8位得01010110->求补得10101010为-86-145的8位补码：写145二进制数100100

10、01->求补得01101111为111负数(溢出)-原码(8位机器数)：负数(溢出)为其正数对127求余数再加1即公式：X=(X%127)+1(其中%表示求余数)，取二进制数位模式长即可。注：4位机器数是(X%7)+1，16位机器数是(X%32767)+1例：-342的8位原码：(342%127)+1=88+1=89即1011001->取位模式长得01011001-145的8位原码：(145%127)+1=19即10011->取位模式长得00010011例一、11111101即:(-3)+01000001+ 65-0011111062例二、11111101即:(-3)+111

11、11111+(-1)-11111100 (-4)例三、11111101即:(-3)-11111111-(-1)-11111110 (-2)例四、11111101即:(-3)+10000001+(-127)-01111110 (-130)负溢出(变为126)注：8位补码形式表示数范围-128127,-130负溢出2,故循环变正为126例五、01111110即:126+00000101+ 5-10000011 131正溢出(变为-125)注：8位补码形式表示数范围-128127,131正溢出4,故循环变负为-125(三)“求补”所执行的“取反加1”操作还有一更直接和便捷的实用方法对应：即将该二进数

12、右端连续的0及首个1保持不变，其余位取反，也同样完成“求补”操作。浮点数(也称实数即含有小数的数)存储表示单精度浮点数(对应C语言的float数据类型)：用4个字节32位存储，最高1位符号位S，指数E占8位(采用余127码即原指数须加偏移量127)，尾数M占23位。其对应科学计数法：± 1 . 尾数 × 2原指数。例一、按余码127（单精度浮点数）存储-161.875解答：为负数S=1/确定符号位S 十进制转二进制：161.87510100001.111 规范化：(1.0100001111)2×27/小数点左移7位使只保留1位整数，故指数为7 E= 7+127 =

13、 134(10000110)2/原指数加偏移量127得到E并转二进制 M= 0100001111/取小数点后内容作为尾数M结果为：1 10000110 01000011110000000000000/把S、E、M连接起来并在尾部补0成32位(尾数23位)例二、按余码127（单精度浮点数）译码内存中的(11000000111100000000000000000000)2 解答：1 10000001 11100000000000000000000/把S、E、M分开 符号S=1，为负数 指数E=(10000001)2=128+1=129，原指数=E-127=129-127=2 尾数M=111 该数为

14、-1.尾数×22即-1.111×22去规范化，即-111.1二进制转十进制：-111.1-7.5该数值是-7.5存储文本英文文字信息应用ASCII码美国信息交换码标准ASCII码使用7位表示(实际使用1个字节即8位，其最高位为0)，可表示128个不同符号。编码范围从000 0000到 111 1111 (编号0127,十六进制007F)。其排列次序以十六进制为依据，每16个为1列共8列。前两列为控制字符(为功能符无显示形象)，其中有回车0D换行0A退格08制表09；第3列(202F)为符号，其头一个为空格20(十进制32)；第4列(303F)前边放数符09对应编码3039；

15、第5、6列(405F)主要放大写字母(AZ)，其中A为41(十进制65)其余字母顺延；第7、8列(607F)主要放小写字母(az)，其中a为61(十进制97)其余字母顺延。相同大小写字母位差值20(十进制32)。Unicode码使用32位表示符号，最多可表示232个符号。代码的不同部分被分配，用于表示来自世界上不同语言的符号。汉字字符编码*存储音频处理过程：采样(模拟信号采点记录值)量化(将样本值截取到整数值)编码(用无符号整数或原码编码成位模式)声音编码标准主流标准：MP3（MPEG Layer3）采样率：44100位深度：16采样后，通过去除人耳无法识别的信息的压缩方法进行压缩存储，压缩方

16、法参见第15章。存储图像图像种类：位图(光栅图)-记录像素点、矢量图-记录轮廓几何图形公式位图(光栅图)解析度(分辨率）：图像需要记录像素数的度量，以扫描的行、列数表示，如1024×768。色彩深度：记录每个像素颜色所使用的位模式长度(即二进制位数)。如灰度图片8位, 真彩图片24位。真彩色的特点使用24位来编码表示一个像素的颜色基于三原色原理（RGB），使用8位表示每种颜色(原色)分量，每种颜色的强度介于0255之间调色板技术(索引色)真彩色可表示224=16万种颜色，许多应用中并不需要，且占用较大的空间从大的颜色集中选择一些颜色（通常256种）并对其建立索引（取值0255）扫描图

17、像时，对每个像素，使用索引值表示其颜色。使用索引色方案减少了图像的存储空间图像编码标准JPEG（联合图像专家组）使用真彩色模式，但通过压缩技术来减少存储位数，具体参见第15章GIF（图形交换格式）使用索引色模式矢量图矢量图编码方案并不存储每个像素的颜色值；图形被分解成几何图形的组合，如线段、矩形、圆等。每个几何图形由数学公式表达，如线段由端点坐标描述。矢量图由定义如何绘制这些形状的一系列指令构成。矢量图像缩放不会影响质量，文件尺寸小，但需要较多处理时间。光栅图正相反，文件尺寸太大；放大图像会出现失真(马赛克)。存储视频视频视频是图像（帧）在时间上的表示。每秒记录和播放25或30帧图像即为视频。

18、视频是一系列帧连续播放而形成的运动图像。视频是随空间和时间变化的色彩信息表示。视频的存储存储视频的本质，就是逐帧存储每一个帧的图像。视频通常压缩存储，参见第15章。第4章 数据运算逻辑运算在实际中应用对指定位复位(即置0)通过构造第二个参与运算的特定数即掩码，执行AND与运算，可以对前一个数的指定位复位(置为0)。利用AND与逻辑只要一边为0则结果为0的特性(同1为1其余为0)，需要置0的位在掩码对应位设为0其余位设为1。例：设置掩码，复位8位位模式的最左5位，以00110110为例验证。解答：掩码设为00000111(00110110)2AND(00000111)2=(00000110)2，

19、即(36)16AND(07)16=(06)16，写成十进制即54 AND7=6 x x x x x x x xAND)1 0 1 1 0 1 0 1 掩码-x 0 x x 0 x 0 x对指定位置位(即置1)通过构造第二个参与运算的特定数即掩码，执行OR或运算，可以对前一个数的指定位置位(置为1)。利用OR或逻辑只要一边为1则结果为1的特性(同0为0其余为1)，需要置1的位在掩码对应位设为1其余位设为0。 x x x x x x x xOR)1 0 1 1 0 1 0 1 掩码-1 x 1 1 x 1 x 1对指定位反转(如对所有位反转可直接用NOT取反运算即可，单目运算无须设掩码)通过构造第

20、二个参与运算的特定数即掩码，执行XOR异或运算，可以对前一个数的指定位反转。利用XOR异或逻辑只要一边为1则结果为另一边取反的特性(相异为1其余为0)，需要反转位在掩码对应位设为1其余位设为0。例：设置掩码，反转8位位模式的最左5位，以00110110为例验证。解答：掩码设为11111000(00110110)2XOR(11111000)2=(11001110)2，即(36)16XOR(F8)16=(CE)16，写成十进制即54 XOR248=206 x x x x x x x xXOR)1 0 1 1 0 1 0 1 掩码- - - -x x x x x x x x检测指定位(或取得指定位)

21、*通过构造第二个参与运算的特定数即掩码，执行AND与运算，可以对前一个数的指定位取下来检测为何值。利用AND与逻辑只要一边为1则结果保持不变的特性(同1为1其余为0)，需要取下来检测的位在掩码对应位设为1其余位设为0。掩码中设置为1的位，运算后前一个数对应位被取下来；掩码中设置为0的位，运算后对应位被置0。如结果等于掩码则所测位均为1，否则所测位有为0的。例：设置掩码，取得8位位模式的最左5位，以00110110为例验证。解答：掩码设为11111000(00110110)2AND(11111000)2=(00110000)2，即(36)16AND(F8)16=(30)16，写成十进制即54 A

22、ND248=48 x x x x x x x xAND)1 0 1 1 0 1 0 1 掩码-x 0 x x 0 x 0 x移位运算总体上，左移产生乘2的效果；右移产生除2的效果。逻辑移位：不考虑符号位的移位运算，移出补0。应用于无符号整数。循环移位：不考虑符号位，循环移出的位补充到另一侧。应用于无符号整数。算术移位：考虑符号位的移位运算，应用于二进制补码格式的带符号整数。算术右移中保留符号位(即移入原符号位)，产生除2的效果算术左移丢弃符号位，如果新符号位与原来相同，运算成功，否则产生溢出；算术左移产生乘2的效果。第5章 计算机组成计算机系统构成地址空间存储器中可标识的所有独立地址单元的总数

23、称为地址空间。一台计算机每次访问内存存取实际是以字为单位进行的，所谓独立地址单元即指字，而字的地址编号范围即地址空间。1个字(Word)=1n 字节(Byte)，n随具体机型不同。例如，64K字节存储器、字长为1字节的系统具有范围为065535的地址空间。这里64KB=64KW=64×1024W=65536 W=26×210W=216W, 需要用16个二进制位来给每个字来编码其地址号：00000000000000001111111111111111(即地址编号065535),共有65536个单元编号。计算机内部传输使用并行传输，即每位需用一根线传输，16位传输在电路上需要1

24、6根地址线。同样是64K字节存储器、如计算机字长为32位(对应4个字节)，则有64 K÷4=16K字，16KW=16×1024W=24×210W=214W，需要用14位来编码其地址号，电路上需要14根地址线，其地址空间为0(16K-1)=016383，。换句话说，地址空间(以字来度量)与内存空间(以字节度量)只在1个字=1个字节时对应相同，地址空间计算依据是每次访问存取的字而非字节，而内存空间大小则总是以字节来度量的。三总线数据总线：线的根数由字长决定，如该计算机字长为32位(4个字节)，并行传输则需要32根数据线，CPU和内存之间一次传送32位数据。地址总线：要

25、访问主存中的某个字，首先通过地址总线传送地址。线的根数取决于存储空间大小及计算机字长。如内存容量最大2GB：2G=2KKK=21×210×210×210=231，即有231个字节，需31位来编址字节；但访问以字为单位，如字长32位即每字4字节，231÷4=229有229个字只需29位编址每个字,传送29位地址需要29根地址线。控制总线：用于发送控制命令，线的根数取决于计算机所需要的控制命令总数。如该计算机指令系统有256条控制命令：256=28，需要8位对每条命令编号,故需要8根控制线。主板及其上接口主板(Main Board,Mother Board,

26、System Board)：是一台PC机的主体所在，主要由PCB印制电路板和它上面的各种元器件组成。主板是所有电脑配件的总平台，它为CPU、显卡、内存、硬盘、光驱及各种设备等提供工作平台及插口。现在不少主板本身集成了声卡、显卡和网卡模块。主板上有密密麻麻的线路，负责各个部件之间的信息传输。传输数据信号的称为数据总线；传输地址信号的称为地址总线；传输控制信号的称为控制总线。主板靠近机箱后面板一侧集中安装了主板的对外接口，连同PCI和ISA扩展槽上安插的各种功能板卡上的接口一同形成了主机箱后面板上的信号接口。程序执行程序：完成特定任务的一组指令序列，由指令和数据按特定顺序组合而成。计算机通过执行程

27、序，将输入数据转换成输出数据。指令：是计算机硬件能执行的特定操作，是对计算机进行程序控制的最小单位；通常一条指令代码中包含操作码和操作数(地址或数据)。指令系统：计算机中所有指令的集合。通常指该机型配备的汇编-机器语言指令集。程序执行过程：要执行的程序和数据都必须放到内存中。CPU不断从内存中取出指令和数据并加以执行。具体由控制单元分三步实施：取指令译码执行。取指令：由控制单元将下一条要执行的指令复制到指令寄存器中，程序计数器自动加1指向内存中的下一条指令。译码指令：控制单元对指令寄存器中的指令进行译码，产生系统可以执行的二进制代码。执行指令：控制单元发送命令到某个部件完成操作。如从内存中加载

28、（读）数据项；或将两个寄存器中的内容相加并将结果保存到输出寄存器中。输入/输出的三种同步方法：计算机需要通过命令把数据从I/O设备传输到CPU和内存。因为输入/输出设备的运行速度比CPU要慢很多，CPU的操作必须和输入/输出设备同步(CPU等待输入/输出设备)。程序控制输入输出最简单的同步：CPU等待I/O设备；CPU遇I/O指令要等待执行完毕，不断查询设备状态，效率非常低。中断控制输入输出指令交I/O设备执行后，CPU不等待而转向其它工作，I/O完成后通知 CPU中断返回。直接存储器存取(DMA)前两种方式(程序控制输入输出和中断控制输入输出)，是在I/O设备和CPU之间传输数据，数据在输入

29、后也被传送到内存，输出时数据从内存中读取。DMA方式适合高速I/O设备(如磁盘)和主存之间直接传输大量数据块(不需要通过CPU的数据传输)。由DMA控制器负责数据的传输。第6章 计算机网络计算机网络技术是计算机技术和通信技术相结合的产物。是随社会对信息共享和信息传递的要求而发展起来的。发展四个阶段(计算机网络经历了由简单到复杂、从单机到多机的发展历程，从ARPAnet到Internet)面向终端的计算机网络计算机通信网络计算机互联网络高速互联网络4种拓扑结构网状拓扑结构：广域网中最常采用的一种网络形式，没有流量问题；通过冗余链路实现健壮性，一条链路的故障不影响整个网络；电缆数量多，成本高。可多

30、种通信信道,多种传输速率,可靠性高。环行结构：容易安装和重构；环的断裂是致命的。延时固定,实时性强,可靠性高;任一站点或线路故障将全网瘫痪。总线型结构：容易安装；总线故障是致命的。信道利用率高,传输速率高;产生冲突,可靠性不高。星型结构：局域网中最常见结构，便宜，安装简单，易于扩展；依赖中央单个点(集线器)。灵活简单,延时较短,误码率较低;线路利用率不高,中央结点负荷太重。网络分类局域网LAN：通常是私有的，连接单个办公室、大楼或校园，局限于几公里内。局域网为个人计算机或工作站资源共享而设计，共享资源包括硬件、软件或者数据。广域网WAN：提供长距离的数据传输，地理上可覆盖国家、洲或全球，可以是

31、点到点的拨号网络，也可以是连接因特网的骨干网。城域网MAN：介于LAN和WAN之间，通常覆盖一个镇或城市。用来为哪些需要高速连接且终端分布在城市内的客户服务。因特网Internet：最著名互联网是因特网(Internet)，称国际互联网，由成千上万个互相连接的网组成国际性网络。TCP/IP协议族是Internet网络体系结构的核心，事实上的国际标准。设计目标：实现异种网的网际互连。采用四层(或五层)体系结构：应用层：|协议：HTTP 、DNS、FTP、SMTP、POP |地址：URL统一资源定位符 |数据单元：消息传输层：|协议：TCP、UDP、SCTP |地址：端口号 |数据单元：段、用户数

32、据报、包网络层：也称互联网层或网际层 |协议：IP、ICMP、ARP、RARP |地址：IP地址 |数据单元：数据包(分组) |节点设备：路由器(Router)数据链路层：也称主机到网络层或网络接口层 |协议：LAN、WAN、MAN |地址：MAC地址|数据单元：数据帧 |节点设备：交换机(Switch)、网桥(Bridge)物理层：|数据单元：二进制位=>电信号 |节点设备：集线器(Hub)IP地址：接入互联网的每一台计算机都有一个全球唯一的地址标识。IPv4地址：由4个字节(32位)组成，采用点分十进制记法。可43亿个IP地址。IPv6地址：由16个字节(128位)组成。可340万亿

33、IP地址。广播地址：(主机号)全1作广播之用零地址：全0标识当前网络或当前主机回送地址：本机测试用子网掩码：用子网掩码分离网络号和主机号。缺省子网掩码：A类：B类：C类：子网掩码与IP地址进行“按位与”运算：得该IP地址的网络地址、网络号、主机号电子邮件E-Mail电邮地址：用户名电子邮件服务器域名简单邮件传输协议SMTP：用于发送邮件邮局协议POP：基本的邮件访问协议(接收邮件)MIME多用途因特网邮件扩展协议：允许非ASCII码数据通过SMTP传输的补充协议域名系统DNS域名：网上的应用服务器通常会注册由若

34、干单词文字组成由“.”分隔的域名以便于记忆一般域名形式：主机资源名.单位名.网络名.顶级域名,如越往后涵盖范围越大主机数目越多域名服务器：Internet中有些特殊的服务器，专门从事域名翻译成IP地址工作文件传输协议FTP客户/服务器(C/S)方式工作，默认端口21，可匿名登录和帐号登录FTP服务器下载或上传文件。远程登录TELNET通过将本地终端作为远程系统的终端来实现本地系统同远程系统建立连接远程登陆后，允许用户在远程计算机上执行程序。万维网(World Wide Web)是基于超文本技术的分布式信息库，由节点和超链接组成超文本(hypertext)：文档中不同部分通过关键字建立连接，使信

35、息得以用交互方式搜索，以客户/服务器(Client/Server)方式提供web服务。Web上有效的超文本或超媒体文档称为页面，主页面或根页面称为主页。浏览器：安装在客户端的软件程序用于解释和显示Web文档。有早期的网景Netscap浏览器,现在的微软IE浏览器、谷歌浏览器、360安全浏览器、百度浏览器、腾讯浏览器、搜狗浏览器、猎豹浏览器等。Web服务器：存储页面提供客户机浏览。超文本传输协议HTTP：用来存取万维网中数据的协议，用文本、超文本、音频、视频等形式传输数据，支持在文档之间的跳转。统一资源定位器URL：HTTP使用叫做统一资源定位器URL的特殊地址系统，用来定位网络服务器中存储的超

36、文本文档。使每一文档在整个因特网范围内具有惟一的地址，URL相当于一个文件名在网络范围的扩展，格式：文档类型静态文档：内容固定，创建、存储在服务器上，客户访问时得到文档的副本。动态文档：客户请求到达后，Web服务器运行创建动态文档，文档因每次请求而动态创建。活动文档：许多应用需要在客户端运行程序或脚本，称为活动文档。浏览器请求活动文档时，服务器发送文档，文档在客户端浏览器控制下运行。超文本标记语言HTML(Hyper Text Marked Language)是用于创建Web页面的语言HTML文档由< >括起的标记和内容构成，标记用于定义内容显示方式，也可以定义超链接和图片、声音等

37、内容,以.html 或 .htm 、.xml作文件名后缀。第7章 操作系统操作系统OS：最重要系统软件，是计算机所有硬软件资源的大管家并负责提供人机交互的操作界面(人机接口)操作系统是计算机硬件(程序和人)的接口，它使得其它程序更加方便有效地执行，并能方便地对计算机硬件和软件资源进行存取。两个设计目标：有效地使用硬件；容易地使用资源。程序、作业、进程、线程程序：由程序员编写的一组稳定指令，存于外存中作业：从程序被选中执行到其运行结束并再次成为程序的这段过程中，程序被成为作业进程：正在执行的程序线程：进程中的一个实体例如：当在一台PC上同时用两个不同的QQ号登录时，每一个QQ是一个进程；而当在一

38、个QQ上和多人同时聊天时，每一个聊天窗口就是一个线程。操作系统演化和分类1、批处理系统：上世纪50年代，使用穿孔卡片输入数据，用行式打印机输出结果，使用磁带作为辅助存储介质。2、分时系统：将处理器的时间分成很短的时间片,多个用户或多个任务依次轮流使用时间片，共享CPU、内存和外部设备等资源。3、个人系统(单用户操作系统)：适合个人计算机的操作系统，微机操作系统。4、并行系统：多CPU系统，每个CPU可以执行一个程序或程序的一部分，多个任务可以并行处理而不再是利用“分时技术”的串行处理。5、分布式系统：数据和资源分布在联网的不同计算机中，一个程序作业可由远隔千里的多台计算机共同完成。6、实时系统

39、：用在实时过程控制中，能及时响应外部事件请求，在规定时间内完成对该事件的处理，控制实时任务协调一致运行。操作系统组成操作系统功能：对计算机系统所有硬软件资源进行合理有效的控制管理和调度使之协调有序运行并提供人机交互的操作界面(人机接口)，具体说有五大管理：CPU管理(又称处理机管理或进程管理)存储管理设备管理文件管理人机接口管理(即用户界面)存储管理(内存管理器)单道程序：前一部分内存用来装载操作系统，后边内存专用于装载单一的整个程序。一个程序运行后，其它程序才能运行。多道程序：同一时刻可以装入多个程序在内存中并存并同时执行，CPU轮流为它们服务。多道程序存储管理的分类：非交换技术：程序一次性

40、全部装入分区调度(内存分区:不定长；程序全部连续装入)分页调度(内存分帧:定长；程序分页全部装入但可不连续)交换技术：加载当前页段运行, 随着程序执行动态淘汰和载入请求分页调度(内存分帧:定长；程序不必全部装入可分页依次动态装入)请求分段调度(内存分段:不定长；程序不必全部装入可按功能模块分段依次动态装入)请求分页分段调度(内存分帧:定长；程序不必全部装入可按功能模块分段,段再可分页依次动态装入)虚拟内存作业调度采用内存交换技术，虽然只有部分程序加载到内存，一部分仍放在磁盘中，但用户感觉整个程序“已经”加载到内存中运行，这个感觉上更大的内存就是虚拟内存。实际即拿出一部分硬盘空间来充当内存使用，

41、以缓解内存的紧张。进程管理(处理机管理)进程调度五种状态变迁：保持状态：程序被选中成为作业，在进入内存执行前为保持状态。就绪状态：作业全部或部分载入内存后成为进程，转为就绪状态，排队轮候CPU。执行(运行)状态：就绪的进程获得CPU得以执行转为执行状态。执行状态下时间片用完，则转为就绪状态。等待(阻塞)状态：执行的进程遇到输入/输出操作，转为等待状态。待输入/输出操作完成，则转为就绪状态。终止状态：进程执行完成，转为终止状态退出内存。三个队列：作业队列、就绪队列、I/O队列死锁：进程需要的资源被对方占有，双方都不肯先放手，从而形成了僵持局面谓之死锁。当操作系统对进程的资源请求不做任何限制时，会

42、发生死锁。死锁的四个必要条件：互斥、资源占有、抢先、循环等待。饿死：当操作系统对进程分配资源有太多限制时，可能会导致进程长期得不到资源的现象，此现象被称为饿死。设备管理输入/输出设备速度相对CPU和内存低很多，设备之间差异大，设备管理器负责有效使用它们。不停监视所有输入/输出设备的状态，为进程分配设备；为每一个设备维护一个队列，维护等候进程的信息；控制用于访问输入/输出设备的不同策略。文件管理控制对文件的访问；管理对文件的创建、删除和修改；为文件命名；管理文件的存储；负责归档和备份。人机接口管理(即用户界面)用户界面是用来接收用户（进程）的输入并向操作系统解释这些请求的程序。用户界面有两类：传

43、统命令方式，如UNIX；窗口和菜单驱动的图形界面GUI，如WINDOWS。主流操作系统UNIX操作系统，是一个强大的多用户、多任务的分时操作系统，支持多种处理器架构，最早于1969年在AT&T公司的贝尔实验室开发。1973年成功地用C语言(为此专门整合了BCPL形成B语言，再改良B语言形成今天大名鼎鼎的C语言)重写了Unix的第三版内核。从此，Unix的修改、移植相当便利，为日后普及打下了坚实基础。而Unix和C的完美结合使C与Unix都很快成为世界软件的主导。Linux是一套免费使用和自由传播的类Unix操作系统，可通过网络或其他途径免费获得，并可任意修改其源代码。全球无数程序员参与

44、了Linux编写和修改，使其不断发展完善壮大，是一款著名的免费和开源(开放源代码)的自由软件。注：自由软件是一种可以不受限制地自由使用、复制、研究、修改和分发的软件。自由软件可以自由取得，并且它的源代码可以自由修改并散布。Windows,是微软公司研发的一套图形界面的桌面操作系统，它问世于1985年，用于IBM PC类个人计算机。其前身Microsoft DOS是传统命令行界面的单用户单任务操作系统。开始WINDOWS是在DOS上开发的窗口形式图形界面，用户通过图形化界面方便的调用原来在dos中复杂的命令，一直到WIN98，才开发出甩开DOS的独立WINDOWS系统。第8章 算法算法：就是解决

45、问题的步骤。设计算法就是编排合理明确的处理步骤顺序，避免错乱和冗余重复。算法有优劣，依目标而定。程序设计首先是设计算法，其次才是根据算法来编写语言指令代码。仅使用这三种结构设计算法即为结构化程序设计,可使程序更健壮、易读、好维护三种基本结构：顺序、判断(选择)、循环(重复)。例：5个元素由小到大选择法排序用k来记录扫描中获得最小元素序号0 1 2 3 4 序号值5 7 3 2 6k=0,2,3 1趟选出3号与0号交换2 7 3 5 6 k=1,2 2趟选出2号与1号交换2 3 7 5 6 k=2,3 3趟选出3号与2号交换2 3 5 7 6 k=3,4 4趟选出4号与3号交换2 3 5 6 7

46、常见算法选择法排序：由小到大排序即每趟扫描选出最小的元素与首元素交换位置，这首元素即排好。下趟就从下一元素开始扫描作同样处理，每趟将会排好其最前方的一个元素，依此类推。n个元素须做n-1趟扫描，第1趟扫描有n-1次比较，以后每趟扫描少1次比较；总比较次数：(n-1)+.+2+1=n×(n-1)/2。冒泡法排序：例：5个元素由小到大冒泡法排序0 1 2 3 4 序号值5 7 3 2 6 5比7不换;7比3比要换;7比2要换;7比6要换5 3 2 6 7 1趟排好7。5比3要换;5比2要换;5比6不换3 2 5 6 7 2趟排好6。3比2要换;3比5不换2 3 5 6 7 3趟排好5。2

47、比3不换2 3 5 6 7 4趟排好3。每趟扫描从头开始两两比较不符既定顺序的则立即交换。每趟排好最后一个,下趟少排一个。n个元素须做n-1趟扫描，第1趟扫描有n-1次比较，以后每趟扫描少1次比较；总比较次数：(n-1)+.+2+1=n×(n-1)/2。插入法排序：例：5个元素由小到大插入法排序0 1 2 3 4 序号值5|7 3 2 6 第1元素划为已排序列表5 7|3 2 6 1趟3 5 7|2 6 2趟2 3 5 7|6 3趟2 3 5 6 7| 4趟把第1个元素划为已排序列表,其后为未排序列表。每趟取出未排序列表中的首元素，将其插入到已排序列表中合适的位置上。依此类推n个元素

48、须做n-1趟。折半查找(二分法查找)当列表中数据有序时，采用效率非常高的折半查找算法。折半查找时，先测试中间元素，可以判断出目标在列表的前半部分还是后半部分，从而排除掉一半数据。重复折半过程，直至找到目标或确定目标不在列表中。处理过程中，其头序号、尾序号和中点序号可按如下关系计算：每次测试的中点序号=(头序号+尾序号)/2 取其整数部分(不作四舍五入)切除前半部分时，新的头序号=原中点序号+1例：有序序列5,7,12,18,20,35,67,73,81,90设置bot=0,top=9,查找67的过程。0 1 2 3 4 5 6 7 8 9序号值 解题过程中：bot=0，5，6 top=9，6

49、mid=4，7，5，65 7 12 18 20 35 67 73 81 90 mid=(bot+top)/2=(0+9)/2=4.5 取mid=4为20<67, 应切除前半部 5 7 12 18 20 35 67 73 81 90 bot=原mid+1=5,mid=(bot+top)/2=(5+9)/2=7 取mid=7为73>67, 应切除后半部 5 7 12 18 20 35 67 73 81 90 top=原mid-1=6,mid=(bot+top)/2=(5+6)/2=5.5 取mid=5为35<67, 应切除前半部 5 7 12 18 20 35 67 73 81

50、90 bot=原mid+1=6,mid=(bot+top)/2=(6+6)/2=6 取mid=6为67=67, 找到！切除后半部分时，新的尾序号=原中点序号-1结构图结构图是一种高层设计工具，显示算法中不同功能模块之间的关系。采取以下方法保证得到结构化的程序：1 自顶向下2 逐步细化3 模块化设计4 结构化编码递归和迭代算法中一些重复处理的步骤除了使用循环(即迭代)方法往往还可使用递归方法解决。递归即自我调用。而且个别特殊问题只能使用递归算法解决,如梵塔趣题。第14章 数据库数据库管理系统DBMS数据库管理系统是定义、创建、维护数据库的一种工具，同时允许用户控制数据库中的数据存取。其构成包括：

51、硬件、软件、数据、用户、规程。数据库体系结构三层体系结构：内层：直接与硬件交互，决定数据在存储设备中的实际存储位置。概念层：又称公用层，定义数据的逻辑视图，把内部视图转化为用户所看到的外部视图。外层：直接与用户交互，它将来自概念层的数据转化为用户熟悉的格式和视图。数据库模型层次模型：组织成一棵倒置的树，每实体可有若干子节点，但只有一个双亲。网状模型：通过图组织，部分实体有多条路径。关系模型：数据被组织成称为关系的二维表，表或关系之间相互关联。是最主流、最常用的数据库模型。关系数据库模型关系数据库管理系统RDBMS：在其中，数据通过关系的集合表示。关系：就是二维表，数据的外部视图是关系或表的集合

52、，它是数据的逻辑结构。关系数据库：由一组相互关联(通过关键字有机联系)的关系二维表组成。关系二维表关系(表)名：在关系数据库中，每一个关系(表)有唯一的名称。属性：关系(表)中的列称为属性(亦称字段、数据项)，每一列在关系内有唯一的名称。属性的数量称为关系的度。元组：关系(表)中的行称为元组(亦称记录)，通过一组属性值描述一条记录。行的总数称为关系的基数。结构化查询语言SQLSQL是美国国家标准协会(ANSI)和国际标准组织(ISO)用于关系数据库上的标准化语言。是一种可通用于各类关系数据库管理系统RDBMS的数据库命令式操作语言。使用SQL可以方便地描述各种关系操作。SQL只是对关系操作的描

53、述，实际的操作是提交给DBMS后由DBMS完成。关系操作在关系数据库中，常用操作有9种(前5种为一元操作即单表操作后4种为二元操作即双表操作，用SQL描述)：插入：用于在一个表中插入一条新的元组记录行。格式：insert into 表名 values(记录各属性值(逗号隔开,字串加双引号)删除：一个表中删除由where条件子句指定的相应元组记录行。格式：delete from 表名 where 属性名=值更新：用来一个表中更新修改由where条件子句指定的元组记录行中的部分属性值。格式：update 表名 set 属性名1=值,属性名2=值,. where 属性名=值选择：从一个表选出由whe

54、re条件子句指定的元组记录行生成同格式的一个数据子集新表。格式：select * from 表名 where 属性名=值投影：从一个表选出部分属性列生成一个属性子集新表。格式：select 属性名1,属性名2,. from 表名连接：把两个不同表按照关键字(共有属性)连接后再作投影即从中选择所需属性构成一个属性子集新表。格式：select 属性名1,属性名2,. from 表名1,表名2 where 表名1.属性名=表名2.属性名并：把两个格式相同但内容可能不同表并成一个表(含全部内容但无重复)。格式：select * from 表名1 union select * from 表名2交：把两个格式相同但内容可能部分不同表提取其重复共有的元组记录构成新表(只含共有内容)格式：select * from 表名1 intersection select * from 表名2差：把两个格式