《计算机导论》复习

1、计算机导论计算机导论复习复习1 1 计算机导论计算机导论复习复习 考试范围：考试范围：1 11111，1515，1616章章 考试题型：简答（考试题型：简答（1212选选1010） 考试时带考试时带2B2B铅笔、橡皮、钢笔或圆珠笔，铅笔、橡皮、钢笔或圆珠笔， 不准使用计算器。不准使用计算器。 计算机导论计算机导论复习复习2 2 第一章第一章 全景图全景图 19361936年，英国科学家阿兰年，英国科学家阿兰 图灵提出图灵机模图灵提出图灵机模 型：把人在计算时所做的工作分解成简单的机型：把人在计算时所做的工作分解成简单的机 械化动作交给机器去执行，经过足够的时间和械化动作交给机器去执行，经过足够

2、的时间和 有限次机械步骤求得解答。理论上可以计算任有限次机械步骤求得解答。理论上可以计算任 何可计算函数。何可计算函数。 19461946年年2 2月由宾夕法尼亚大学研制成功的月由宾夕法尼亚大学研制成功的ENIACENIAC 是第一台电子数字计算机。是第一台电子数字计算机。 计算机导论计算机导论复习复习3 3 美籍匈牙利数学家冯美籍匈牙利数学家冯 诺依曼提出现代计诺依曼提出现代计 算机基本结构算机基本结构“冯冯诺依曼计算诺依曼计算 机机”： 计算机应由运算器、控制器、存储器、计算机应由运算器、控制器、存储器、 输入设备和输出设备五大部件组成；输入设备和输出设备五大部件组成； 应采用二进制简化机

3、器的电路设计；应采用二进制简化机器的电路设计； 采用采用“存储程序存储程序”以便计算机能保存指令以便计算机能保存指令 和数据以及能够自动依次执行指令。和数据以及能够自动依次执行指令。 计算机导论计算机导论复习复习4 4 第一代计算机：电子管；第一代计算机：电子管； 第二代计算机：晶体管；第二代计算机：晶体管； 第三代计算机：集成电路；第三代计算机：集成电路； 第四代计算机：大规模第四代计算机：大规模/ /超大集成电路超大集成电路 计算硬件发展的新趋势计算硬件发展的新趋势并行计算、连网并行计算、连网 计算机导论计算机导论复习复习5 5 第一代软件：机器语言，汇编语言；第一代软件：机器语言，汇编语

4、言； 第二代软件：高级语言；第二代软件：高级语言； 第三代软件：操作系统；第三代软件：操作系统； 第四代软件：结构化程序设计方法，第四代软件：结构化程序设计方法，UNIXUNIX，C C， DOSDOS，鼠标图形界面；，鼠标图形界面； 第五代软件：面向对象程序设计，第五代软件：面向对象程序设计，WindowsWindows， JavaJava，WWWWWW； 计算机导论计算机导论复习复习6 6 第二章第二章 二进制数值和记数系统二进制数值和记数系统 数制：按进位原则进行计数，逢数制：按进位原则进行计数，逢R R进一。进一。 基数：数制中所需的数字字符个数。基数：数制中所需的数字字符个数。R R

5、进制的基数进制的基数=R=R 位权：是一个与数字位置有关的常数，位权位权：是一个与数字位置有关的常数，位权=R=Rn n 其中其中n n取值：以小数点为界，向左取值：以小数点为界，向左 0 0，1 1，2 2，33， 向右向右-1-1，-2-2，-3-3 例：例：(275.8)(275.8)10 10=2 =210102 27 710101 15 510100 08 81010-1 -1 计算机导论计算机导论复习复习7 7 计算机导论计算机导论复习复习8 8 计算机导论计算机导论复习复习9 9 二进制数二进制数 十进制数十进制数 位权相加法位权相加法：各位数码乘位权，再相加。：各位数码乘位权，

6、再相加。 例：例：(1011.1)2 = 123 + 022 + 121 + 120 + 12-1 = 8 + 0 + 2 + 1 + 0.5 = (11.5)10 整数部分从右向左，小数部分从左向右，整数部分从右向左，小数部分从左向右， 每每3位二进制一组，变为位二进制一组，变为1位八进制。位八进制。 不足不足3位时分别在最左端和最右端补位时分别在最左端和最右端补0凑够凑够3位。位。 例：例：(11.1101)2 = (14513.64)8 二进制数二进制数 八进制数八进制数 二进制二进制 十六进制十六进制 整数部分从右向左，小数部分从左向右，整数部分从右向左，小数部分从左向右， 每每4位二

7、进制一组，变为位二进制一组，变为1位十六进制。位十六进制。 不足不足4位时分别在最左端和最右端补位时分别在最左端和最右端补0凑够凑够4位。位。 例：例：(11010111101.1010001)2 = (6BD.A2)16 计算机导论计算机导论复习复习1010 位位(bit)：计算机存储数据的最小单位：计算机存储数据的最小单位(0、1) 字节字节(Byte)：处理数据的基本单位：处理数据的基本单位(8bit/Byte) 31 30 31 30 25 24 25 24 2323 22 7 022 7 0 0 1 0 0 0 1 1 0 0 10 0 1 1 0 10 0 11 1 一个一个字字(

8、Word)由由2、4或或8个字节组成。个字节组成。 一个字的每一位由右至左编号。如一个字的每一位由右至左编号。如32位字长：位字长： 计算机导论计算机导论复习复习1111 第三章第三章 数据表示法数据表示法 模拟信号和数字信号模拟信号和数字信号 无符号数和有符号数无符号数和有符号数 符号位符号位：二进制数的最高位表示：二进制数的最高位表示“正正”、 “负负”。 0 0为正，为正，1 1为负。为负。 计算机导论计算机导论复习复习1212 原码原码：正号为：正号为0 0，负号为，负号为1 1，数值部分为二进制绝，数值部分为二进制绝 对值。对值。 补码补码：正数的补码和原码相同；负数的补码是将：正数

9、的补码和原码相同；负数的补码是将 其原码除符号位外各位取反，末位加其原码除符号位外各位取反，末位加1 1。 -5 1 0 0 0 0 1 0 1原码原码 1 1 1 1 1 0 1 1 补码补码 +5的原码、补码都是的原码、补码都是00000101 为了运算方便，机器数采用原码、补码表示。为了运算方便，机器数采用原码、补码表示。 计算机导论计算机导论复习复习1313 u小数点位置固定的数称为定点数。小数点位置固定的数称为定点数。 定点整数：小数点固定在数值部分最右端。定点整数：小数点固定在数值部分最右端。 定点小数：小数点固定在数值部分最左端。定点小数：小数点固定在数值部分最左端。 u 小数点

10、位置不固定的数称为浮点数，分为阶码小数点位置不固定的数称为浮点数，分为阶码 （指数）和尾数两部分。（指数）和尾数两部分。 31 30 25 24 23 22 5 031 30 25 24 23 22 5 0 0 0 0 0 0 1 1 0 0 10 0 0 01 0 10 0 阶码部分阶码部分尾数部分尾数部分阶码阶码 符号位符号位 尾数尾数 符号位符号位 1 1 例例：将十进制数：将十进制数 +55 +55 以浮点数格式存放。以浮点数格式存放。 (55)(55)10 10 = (110111) = (110111)2 2 = 0.110111 = 0.110111 * * 2 26 6 计算机

11、导论计算机导论复习复习1414 西文字符的编码：西文字符的编码： ASCII码码(American Standard Code for Information Interchange) t128个常用字符，用个常用字符，用7位二进制编码，占一个字节，最高位位二进制编码，占一个字节，最高位0。 t 其中，控制字符：其中，控制字符：032，127；普通字符：；普通字符：94个。个。 例如：例如：“a”字符的编码为字符的编码为1100001，对应的十进制数是，对应的十进制数是97； 字符字符 对应的十六进制对应的十六进制 对应的十进制对应的十进制 换行换行 0AH 10 回车回车 0DH 13 空格

12、空格 20H 32 09 30H39H 4857 AZ 41H5AH 6590 az 61H7AH 97122 计算机导论计算机导论复习复习1515 和汉字有关的编码：和汉字有关的编码： 汉字输入码：操作人员通过键盘输入的汉字编码。汉字输入码：操作人员通过键盘输入的汉字编码。 (2) 汉字国标码汉字国标码(GB231280) 每个汉字占两个字节的编码。所有汉字分区，每个每个汉字占两个字节的编码。所有汉字分区，每个 区区94个汉字。区号和位号各加个汉字。区号和位号各加32构成国标码。构成国标码。 (3) 机内码机内码 计算机内部存储和加工汉字所用的编码。计算机内部存储和加工汉字所用的编码。 每个

13、汉字的国标码的每个字节最高位改为每个汉字的国标码的每个字节最高位改为1，即成机内码。，即成机内码。 汉字汉字 国标码国标码 汉字机内码汉字机内码 中中 8680(01010110 01010000)2 (11010110 11010000)2 华华 5942(00111)2 (10111)2 (4) 汉字字形码：点阵（汉字字形点阵的代码）汉字字形码：点阵（汉字字形点阵的代码） 计算机导论计算机导论复习复习1616 为一个字节补充为一个字节补充1bit（校验位），设置校验位的值（校验位），设置校验位的值 为为0或或1，使字节中的，使字节中的8bit和该校验位含有和该校验位含有1值的个数值的个数

14、为奇数（奇校验）或偶数（偶校验）。为奇数（奇校验）或偶数（偶校验）。 数据数据奇校验编码奇校验编码偶校验编码偶校验编码 0000 00001 0000 00000 0000 0000 0101 01000 0101 01001 0101 0100 计算机导论计算机导论复习复习1717 n关键字编码关键字编码 关键字编码是用单个字符代替常用单词或前后缀。关键字编码是用单个字符代替常用单词或前后缀。 如：如：the and+ that$the and+ that$ 文本压缩方法：文本压缩方法： n行程长度编码行程长度编码 在一些数据流中，某个字符可能连续地反复出现。在一些数据流中，某个字符可能连续

15、地反复出现。 因此，重复字符序列被替换为：因此，重复字符序列被替换为： 标志字符该字符出现次数标志字符该字符出现次数 计算机导论计算机导论复习复习1818 文本压缩方法：文本压缩方法： n哈夫曼编码哈夫曼编码 1.计算信源符号出现的概率。计算信源符号出现的概率。p-0.125, a-0.25, s-0.375, g-0.125, e-0.125 2.概率最小的两个符号概率相加合成一个概率。概率最小的两个符号概率相加合成一个概率。 3.将合成概率看成一个新组合符号概率，重复上述将合成概率看成一个新组合符号概率，重复上述 做法，直到最后只剩下两个符号概率为止。做法，直到最后只剩下两个符号概率为止。

16、 4.反过来逐步向前编码，每一步有两个分支各赋予反过来逐步向前编码，每一步有两个分支各赋予 一个二进制码，可以对概率大的编码为一个二进制码，可以对概率大的编码为1. 计算机导论计算机导论复习复习1919 l采样频率：每秒钟的采样次数。采样频率：每秒钟的采样次数。 l量化位数量化位数( (采样精度采样精度) )：存放采样点振幅值的二：存放采样点振幅值的二 进制位数。通常量化位数有进制位数。通常量化位数有8 8位、位、1616位等。位等。 音频信息的数字化：音频信息的数字化： 捕捉声音时用固定的时间间隔对声波进行采样捕捉声音时用固定的时间间隔对声波进行采样 （离散化处理），例如（离散化处理），例如

17、44.1kHz44.1kHz；（采样）（采样） 将每个采样点的振幅值转换为二进制数值，例将每个采样点的振幅值转换为二进制数值，例 如用如用8 8位或位或1616位二进制表示。位二进制表示。（量化）（量化） 把量化后的信号数据编成一个二进制码组输出。把量化后的信号数据编成一个二进制码组输出。 （编码）（编码） 计算机导论计算机导论复习复习2020 图像信息的数字化：图像信息的数字化： 用用“m m行行n n列列”个像素点来离散化一幅图像，个像素点来离散化一幅图像， 例如例如10241024768768分辨率；分辨率；（采样）（采样） 将每个像素点的三基色强度转换为二进制值，将每个像素点的三基色强

18、度转换为二进制值， 例如用例如用8 8位、位、1616位、位、2424位、位、3232位二进制表示。位二进制表示。 （量化）（量化） 数字化图像的数据量很大，所以需要采用编数字化图像的数据量很大，所以需要采用编 码技术来压缩信息，减少数据量。码技术来压缩信息，减少数据量。（编码）（编码） 分辨率：图像中的行数和列数，每个行与列的分辨率：图像中的行数和列数，每个行与列的 交点就是一个像素。例如交点就是一个像素。例如1024768。 颜色深度：每个像素点颜色值的存储位数。颜色深度：每个像素点颜色值的存储位数。 计算机导论计算机导论复习复习2121 视频信息的数字化：视频信息的数字化： 连续动态的视

19、频由多帧静态图像组成。连续动态的视频由多帧静态图像组成。 采样频率：每秒捕捉的画面帧数。采样频率：每秒捕捉的画面帧数。 采样精度：经采样后每帧所包含的颜色位采样精度：经采样后每帧所包含的颜色位 （色彩值）。如（色彩值）。如8 8位，位，3232位。位。 必须对海量的视频数据及其伴音进行压缩必须对海量的视频数据及其伴音进行压缩 和编码。和编码。 计算机导论计算机导论复习复习2222 bmp, gif, jpg, wmf avi, mov, mpg, dat wma, wav, mp3, mid 计算机导论计算机导论复习复习2323 第四章第四章 门和电路门和电路 门电路：接受一个或多个输入信号，

20、生门电路：接受一个或多个输入信号，生 成一个输出信号。每种类型的门执行一成一个输出信号。每种类型的门执行一 个特殊的逻辑函数。个特殊的逻辑函数。 非门，与门，或门，异或门，与非门，非门，与门，或门，异或门，与非门， 或非门或非门 等。等。 计算机导论计算机导论复习复习2424 非门：非门： 真值表真值表 0 01 1 1 10 0 X= AX= AA A X = AX = A 逻辑框图符号逻辑框图符号 与门：与门： 1 11 11 1 0 00 01 1 1 1 0 0 B B 0 00 0 0 00 0 X= AX= A* *B BA A 真值表真值表逻辑框图符号逻辑框图符号 X = A X

21、 = A * * B B 计算机导论计算机导论复习复习2525 或门：或门： 真值表真值表逻辑框图符号逻辑框图符号 1 11 11 1 1 10 01 1 1 1 0 0 B B 1 10 0 0 00 0 X= AX= AB BA A 异或门：异或门：两个输入相同时，输出是两个输入相同时，输出是0，否则输出，否则输出1。 0 01 11 1 1 10 01 1 1 1 0 0 B B 1 10 0 0 00 0 X= AX= A B BA A 真值表真值表逻辑框图符号逻辑框图符号 计算机导论计算机导论复习复习2626 与非门：让与门的结果再经过一个非门。与非门：让与门的结果再经过一个非门。

22、或非门：让或门的结果再经过一个非门。或非门：让或门的结果再经过一个非门。 计算机导论计算机导论复习复习2727 用晶体管构造门用晶体管构造门 晶体管本身晶体管本身 就是非门。就是非门。 非门非门 V1, V2都是都是1, 源极将被接地源极将被接地, Vout=0。 否则否则Vout=1。 与非门与非门 V1或或V2是是1时时, 源极将被源极将被 接地接地, Vout=0。 当当V1和和V2都是都是0时，源时，源 极才不被接地，极才不被接地，Vout=1。 或非门或非门 计算机导论计算机导论复习复习2828 “异或异或”逻辑表达式：逻辑表达式：X=A B=AB + AB A B X ADD RE

23、G1 REG2 指令格式：指令格式： 计算机导论计算机导论复习复习3838 内存：直接与内存：直接与CPUCPU交换信息的存储设备。用来存放计交换信息的存储设备。用来存放计 算机运行期间所需的信息，如：指令、程序、文档。算机运行期间所需的信息，如：指令、程序、文档。 外存：内存的延伸，长期存放暂时不用的数据。如外存：内存的延伸，长期存放暂时不用的数据。如 系统文件、应用程序、用户文档等。系统文件、应用程序、用户文档等。 计算机导论计算机导论复习复习3939 非非von Neumann结构：结构： 不采用不采用“线性的读取执行周期线性的读取执行周期”。 并行（分布式）处理并行（分布式）处理 w阵

24、列计算机：多个处理机对不同数据同时运行阵列计算机：多个处理机对不同数据同时运行 相同指令。相同指令。 w多指令流多数据流多指令流多数据流MIMDMIMD系统：多个处理机对不系统：多个处理机对不 同数据执行不同指令。同数据执行不同指令。 计算机导论计算机导论复习复习4040 流水线技术（流水线技术（PipelinePipeline） 取指取指译码译码地址生成地址生成取数取数执行执行写回写回 取指取指译码译码地址生成地址生成取数取数执行执行写回写回 取指取指译码译码地址生成地址生成取数取数执行执行写回写回 取指取指译码译码地址生成地址生成取数取数执行执行写回写回 w将每条指令分解成多个阶段，几条指

25、令的不同阶段将每条指令分解成多个阶段，几条指令的不同阶段 重叠运行，使控制器、运算器、存储器等同时工作。重叠运行，使控制器、运算器、存储器等同时工作。 w如如PentiumPentium的的6 6级流水线结构：级流水线结构： 计算机导论计算机导论复习复习4141 v计算机问题求解三阶段：不断反复的过程计算机问题求解三阶段：不断反复的过程 v算法开发：得到问题的通用解决方案算法开发：得到问题的通用解决方案 w分析问题、提出并测试算法分析问题、提出并测试算法 v算法实现：得到计算机可运行的程序算法实现：得到计算机可运行的程序 w编码和测试程序编码和测试程序 v维护：在实践中检验维护：在实践中检验

26、w实际运转、修改维护程序实际运转、修改维护程序 第六章第六章 问题求解和算法设计问题求解和算法设计 计算机导论计算机导论复习复习4242 v两种程序设计方法：两种程序设计方法： v自顶向下方法自顶向下方法 (Top-down Methodology) 程序设计模式：程序设计模式：“数据结构算法数据结构算法” 在软件功能说明书中，在软件功能说明书中，动词动词是重点。是重点。 v面向对象程序设计面向对象程序设计(Object Oriented Programming) 程序设计模式：程序设计模式：“对象消息对象消息” 在软件功能说明书中，在软件功能说明书中，名词名词是重点。是重点。 计算机导论计算

27、机导论复习复习4343 自顶向下程序设计方法自顶向下程序设计方法 自顶向下、逐步求精：逐层分解复杂任务，把任务自顶向下、逐步求精：逐层分解复杂任务，把任务 细节推延到下层模块中实现。细节推延到下层模块中实现。 模块化：每个模块完成特定的、相对简单的功能。模块化：每个模块完成特定的、相对简单的功能。 流程控制结构化：程序通过顺序、分支、循环三种流程控制结构化：程序通过顺序、分支、循环三种 基本控制结构来实现。基本控制结构来实现。 计算机导论计算机导论复习复习4444 面向对象的程序设计方法面向对象的程序设计方法 面向对象面向对象 = 类类 + 对象对象 + 继承继承 + 消息消息 + 通信通信

28、对一组具有对一组具有 相同属性和相同属性和 行为的对象行为的对象 的抽象描述。的抽象描述。 对象是类对象是类 的实例。的实例。 具有属性具有属性 和方法。和方法。 子类可以继承子类可以继承 父类的属性和父类的属性和 方法，实现代方法，实现代 码重用。码重用。 对象间通过消对象间通过消 息息(事件事件)进行通进行通 信，执行其它信，执行其它 对象的方法。对象的方法。 计算机导论计算机导论复习复习4545 继承继承 inheritance：子类得到父类的全部属性和方法，：子类得到父类的全部属性和方法， 还可以扩充和覆盖父类的成员。还可以扩充和覆盖父类的成员。 多态多态 polymorphism：也

29、称：也称重载。不同子类中同一方重载。不同子类中同一方 法名可定义成不同代码，所以它们法名可定义成不同代码，所以它们在收到同一消息在收到同一消息 时做出的响应行为也不同。时做出的响应行为也不同。 封装封装 encapsulation：将属性和行为隐藏起来，外部：将属性和行为隐藏起来，外部 通过特定的接口访问对象成员。好处是保护成员，通过特定的接口访问对象成员。好处是保护成员， 修改程序时只涉及类的内部。修改程序时只涉及类的内部。 计算机导论计算机导论复习复习4646 第七章第七章 低级程序设计语言低级程序设计语言 机器语言：由二进制代码组成。能被计算机直接机器语言：由二进制代码组成。能被计算机直

30、接 理解和执行，但编程困难，可移植性差。理解和执行，但编程困难，可移植性差。 把机器指令中的操作码和操作数用英文助记符和把机器指令中的操作码和操作数用英文助记符和 符号地址来表示，称为汇编语言。依赖于机器，符号地址来表示，称为汇编语言。依赖于机器， 可移植性同样较差。可移植性同样较差。 计算机导论计算机导论复习复习4747 第八章第八章 高级程序设计语言高级程序设计语言 目标程序目标程序 .obj.obj 源程序源程序 .c.c 可执行程序可执行程序 .exe.exe 编译器编译器连接程序连接程序数据数据 运行运行 结果结果 t编译器对整个源程序经过编译处理，产生一个与源编译器对整个源程序经过

31、编译处理，产生一个与源 程序等价的目标程序；通过连接程序将目标程序和程序等价的目标程序；通过连接程序将目标程序和 有关的程序库组合成一个完整的可执行程序；有关的程序库组合成一个完整的可执行程序； t执行速度快，修改源程序后都必须重新编译。同一执行速度快，修改源程序后都必须重新编译。同一 种高级语言在不同种高级语言在不同CPU平台上需要不同的编译器。平台上需要不同的编译器。 计算机导论计算机导论复习复习4848 t解释程序对源程序进行逐句分析，若没有错误，解释程序对源程序进行逐句分析，若没有错误， 将该语句翻译成一个或多个机器语言指令，然后将该语句翻译成一个或多个机器语言指令，然后 立即执行这些

32、指令；若解释时发现错误，则立即立即执行这些指令；若解释时发现错误，则立即 停止，报错并提醒用户更正代码。停止，报错并提醒用户更正代码。 t解释方式不生成目标程序，执行速度慢。解释方式不生成目标程序，执行速度慢。 数据数据 高级语言高级语言 源程序源程序 解释程序解释程序 计算结果计算结果 计算机导论计算机导论复习复习4949 tJava源程序先经过编译生成源程序先经过编译生成Java字节码，然后由字节码，然后由 JVM (Java Virtual Machine, Java虚拟机虚拟机)解释执行。解释执行。 tJava字节码相当于是字节码相当于是“标准的机器语言标准的机器语言”，速度快，速度快

33、， 唯一，只要有相应的唯一，只要有相应的JVM解释器，解释器，Java字节码可在任字节码可在任 何环境下运行，如：何环境下运行，如：PC、UNIX工作站、工作站、Macintosh等。等。 字节码文件字节码文件 .class.class 源程序源程序 .java.java 编译器编译器javacjavac解释器解释器javajava 运行运行 结果结果 在浏览器中运行的在浏览器中运行的Java字节码为字节码为Java Applet (Java小程序小程序)。 计算机导论计算机导论复习复习5050 程序设计时的程序设计时的 控制结构：顺序、分支、循环结构控制结构：顺序、分支、循环结构 顺序结构：

34、按照语句出现的先后顺序依次执行。顺序结构：按照语句出现的先后顺序依次执行。 分支结构：根据给定条件判断，决定程序执行的顺序。分支结构：根据给定条件判断，决定程序执行的顺序。 循环结构：重复多次执行语句集合。循环结构：重复多次执行语句集合。 计算机导论计算机导论复习复习5151 第九章第九章 抽象数据类型和算法抽象数据类型和算法 数据元素存放数据元素存放 在连续存储空在连续存储空 间中间中 顺序存储方式顺序存储方式 数据可以存放在数据可以存放在 不连续的存储空不连续的存储空 间中。间中。 通过指针指向下通过指针指向下 一数据元素。一数据元素。 数据域数据域指针域指针域 链式存储方式链式存储方式

35、计算机导论计算机导论复习复习5252 数组数组(Array)：按：按“行优先行优先”或或“列优先列优先”方式顺序存方式顺序存 储数组元素。插入删除元素时需移动大量元素。储数组元素。插入删除元素时需移动大量元素。 在一个有在一个有n n个元素的数组个元素的数组A A中的第中的第i i个元素之前插入个元素之前插入 一个元素一个元素x x时，将第时，将第i i个元素及其后的元素后移：个元素及其后的元素后移： for (j=n; j=i; j-) Aj+1=Aj;for (j=n; j=i; j-) Aj+1=Aj; Ai=x; Ai=x; n+; n+; 在一个有在一个有n n个元素的数组个元素的数

36、组A A中删除第中删除第i i个元素时，将个元素时，将 第第i i个元素之后的元素前移：个元素之后的元素前移： for (j=i; j=n; j+) Aj=Aj+1;for (j=i; jnext=p-next; p-next=s; 删除节点删除节点p时的操作：时的操作： 首先从链首首先从链首head开始，顺序查找到节点开始，顺序查找到节点q和它的和它的 后继节点后继节点p（该删除的节点），然后（该删除的节点），然后 q-next=p-next; 计算机导论计算机导论复习复习5454 线性表是由线性表是由n(n0)个数据元素个数据元素a1,a2,an组成的有限序列。组成的有限序列。 栈栈(St

37、ack)：只允许在表的一端进行插入和删除的线性表。：只允许在表的一端进行插入和删除的线性表。 队列队列(Queue)：限制在表的一端插入，在表的另一端删除。：限制在表的一端插入，在表的另一端删除。 数组数组(Array)是同类型数据元素构成的集合。是同类型数据元素构成的集合。 通过数组名和下标访问数组元素。按行优先顺序存储。通过数组名和下标访问数组元素。按行优先顺序存储。 树树(Tree)：一个结点最多有一个直接前趋结点但可以有多个直接：一个结点最多有一个直接前趋结点但可以有多个直接 的后继结点。的后继结点。 二叉树：二叉树： 根根 计算机导论计算机导论复习复习5555 折半查找：要求线性表事

38、先按关键字大小排好顺序并折半查找：要求线性表事先按关键字大小排好顺序并 且线性表采用顺序存储（即数组）方式。且线性表采用顺序存储（即数组）方式。 先取表的中间位置的结点关键字与所给定的关键字进行比先取表的中间位置的结点关键字与所给定的关键字进行比 较，如果相等，则查找成功；较，如果相等，则查找成功； 如果给定值比该结点的关键字大，则所找结点在表的后半如果给定值比该结点的关键字大，则所找结点在表的后半 部分；否则所找结点在表的前半部分；部分；否则所找结点在表的前半部分； 然后再把选定的部分表的中间结点的关键字与给定关键字然后再把选定的部分表的中间结点的关键字与给定关键字 进行比较；如此反复，直到

39、查找成功或者查找失败为止。进行比较；如此反复，直到查找成功或者查找失败为止。 选择排序，冒泡排序，快速排序选择排序，冒泡排序，快速排序 计算机导论计算机导论复习复习5656 二叉排序树：二叉排序树： 二叉树中的每个节点的关键字均大于其左子树上二叉树中的每个节点的关键字均大于其左子树上 所有节点的关键字，且小于等于其右子树上所有所有节点的关键字，且小于等于其右子树上所有 节点的关键字。节点的关键字。 例如，给出例如，给出K=10, 18, 3, 8, 19, 2, 7, 8，构造二叉排序树。，构造二叉排序树。 10 318 82 19 87 第第1个数就是树根。个数就是树根。 树的形状由数插入树

40、的形状由数插入 树的顺序决定。树的顺序决定。 计算机导论计算机导论复习复习5757 第十章第十章 操作系统操作系统 编译程序编译程序 汇编程序汇编程序 文本编辑器文本编辑器 数据库系统数据库系统 系统程序和应用程序系统程序和应用程序 操作系统操作系统 计算机硬件计算机硬件 用户用户1用户用户2用户用户3用户用户n 操作系统：计算机硬件和软件资源的管理者。操作系统：计算机硬件和软件资源的管理者。 计算机导论计算机导论复习复习5858 操作系统构成：进程管理、内存管理、文件管理、操作系统构成：进程管理、内存管理、文件管理、 输入输出系统管理，作业管理。输入输出系统管理，作业管理。 操作系统主要类别

41、：操作系统主要类别： 批处理系统批处理系统 分时系统分时系统 实时系统实时系统 计算机导论计算机导论复习复习5959 “分时分时”的含义：时间片轮转，轮流占用的含义：时间片轮转，轮流占用CPUCPU 人机交互性好：程序的运行由用户自己操作。人机交互性好：程序的运行由用户自己操作。 共享主机：多个用户同时使用共享主机：多个用户同时使用同一台计算机同一台计算机。 对每个用户而言好象独占主机。对每个用户而言好象独占主机。 及时响应外部事件的请求，在规定的严格时间内完及时响应外部事件的请求，在规定的严格时间内完 成对该事件的处理。成对该事件的处理。 要求：及时响应、快速处理，高可靠性和安全性要求：及时

42、响应、快速处理，高可靠性和安全性 应用领域：过程控制、事务处理。应用领域：过程控制、事务处理。 计算机导论计算机导论复习复习6060 内存分配方案内存分配方案- -连续内存分配连续内存分配 首次适应首次适应(First-fit)策略策略 最佳适应最佳适应(Best-fit)策略策略 最差适应最差适应(Worst-fit)策略策略 在可用内存中找到足够大的一块连续内存在可用内存中找到足够大的一块连续内存( (如如100KB)100KB)， 切出要求长度的内存切出要求长度的内存( (如如70KB)70KB)分配，剩余内存分配，剩余内存( (如如 30KB)30KB)作为新空闲区留待以后分配或合并。

43、作为新空闲区留待以后分配或合并。 内存分配方案内存分配方案- -分页式内存管理分页式内存管理 为解决碎片问题和实现不连续分配，采用页式管理。为解决碎片问题和实现不连续分配，采用页式管理。 计算机导论计算机导论复习复习6161 虚拟内存：虚拟内存： 当一个用户程序要调入内存运行时，不是将该当一个用户程序要调入内存运行时，不是将该 程序的所有页面都装入内存，而是只装入部分程序的所有页面都装入内存，而是只装入部分 的页面，就可启动程序运行；的页面，就可启动程序运行； 在运行的过程中，如果发现要运行的程序或要在运行的过程中，如果发现要运行的程序或要 访问数据不在内存，则向系统发出缺页中断请访问数据不在

44、内存，则向系统发出缺页中断请 求；求； 系统在处理这个中断时，将磁盘上相应的页面系统在处理这个中断时，将磁盘上相应的页面 调入内存，使得该程序能够继续运行。调入内存，使得该程序能够继续运行。 计算机导论计算机导论复习复习6262 进程是程序对某个数据集的一次执行过程。进程是程序对某个数据集的一次执行过程。 v程序是静态概念程序是静态概念(建立与删除建立与删除)；进程是动态概念。；进程是动态概念。 一个进程由三部分组成：一个进程由三部分组成： 进程控制块进程控制块PCBPCB，程序段，数据集，程序段，数据集 新进程新进程 就绪就绪运行运行 终止终止 等待等待 允许允许 中断中断 退出退出 允许允

45、许 I/O操作或事件的完成操作或事件的完成I/O操作或事件的等待操作或事件的等待 计算机导论计算机导论复习复习6363 CPU调度：把调度：把CPU分配给某个就绪进程去运行。分配给某个就绪进程去运行。 不可抢占式：当前运行进程完成或阻塞或时间片不可抢占式：当前运行进程完成或阻塞或时间片 到时，才再分配处理机。到时，才再分配处理机。 抢占式：将正运行进程强行撤下，处理机分配给抢占式：将正运行进程强行撤下，处理机分配给 其它进程。例如当有一个优先权更高的进程进入就绪其它进程。例如当有一个优先权更高的进程进入就绪 队列时。队列时。 先到先服务先到先服务 (FCFS, First-Come, Firs

46、t-Served)(FCFS, First-Come, First-Served) 最短作业优先最短作业优先 (SJF, Shortest-Job-First)(SJF, Shortest-Job-First) 轮转轮转(RR, Round-Robin)(RR, Round-Robin)：时间片轮转：时间片轮转 计算机导论计算机导论复习复习6464 第十一章第十一章 文件系统和目录文件系统和目录 文件：文件：存储在外存上具有标识名的一组相关字存储在外存上具有标识名的一组相关字 符流或记录的集合。符流或记录的集合。 文件的命名：文件名文件的命名：文件名.扩展名扩展名 计算机导论计算机导论复习复习6565 OS将每个目录看成一张表，表中是该目录下所有将每个目录看成一张表，表中是该目录下所有 文件的信息。（其实目录本身也是一个文件）文件的信息。（其实目录