《2007计算机导论复习.ppt》由会员分享，可在线阅读，更多相关《2007计算机导论复习.ppt（72页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机导论计算机导论复习复习考试范围：考试范围：1 11111，1515，1616章章考试题型：简答（考试题型：简答（1212选选1010）考试时带考试时带2B2B铅笔、橡皮、钢笔或圆珠笔，铅笔、橡皮、钢笔或圆珠笔，不准使用计算器。不准使用计算器。1 1第第一一章章 全景图全景图19361936年，英国科学家阿兰年，英国科学家阿兰 图灵提出图灵提出图灵机图灵机模型：模型：把人在计算时所做的工作分解成简单的机械化把人在计算时所做的工作分解成简单的机械化动作交给机器去执行，经过足够的时间和有限动作交给机器去执行，经过足够的时间和有限次机械步骤求得解答。理论上可以计算任何可次机械步骤求得解答。理论上
2、可以计算任何可计算函数。计算函数。19461946年年2 2月由宾夕法尼亚大学研制成功的月由宾夕法尼亚大学研制成功的ENIACENIAC是第一台电子数字计算机。是第一台电子数字计算机。2 2美籍匈牙利数学家冯美籍匈牙利数学家冯 诺依曼提出诺依曼提出现代计现代计算机基本结构算机基本结构“冯冯诺依曼计算机诺依曼计算机”：计算机应由运算器、控制器、存储器、计算机应由运算器、控制器、存储器、输入设备和输出设备五大部件组成；输入设备和输出设备五大部件组成；应采用二进制简化机器的电路设计；应采用二进制简化机器的电路设计；采用采用“存储程序存储程序”以便计算机能保存指令和以便计算机能保存指令和数据以及能够自
3、动依次执行指令。数据以及能够自动依次执行指令。3 3第一代计算机：第一代计算机：电子管电子管；第二代计算机：第二代计算机：晶体管晶体管；第三代计算机：第三代计算机：集成电路集成电路；第四代计算机：第四代计算机：大规模大规模/超大集成电路超大集成电路计算硬件发展的新趋势计算硬件发展的新趋势并行计算、连网并行计算、连网4 4第一代软件：第一代软件：机器语言，汇编语言机器语言，汇编语言；第二代软件：第二代软件：高级语言高级语言；第三代软件：第三代软件：操作系统操作系统；第四代软件：第四代软件：结构化程序设计方法，结构化程序设计方法，UNIXUNIX，C C，DOSDOS，鼠标图形界面，鼠标图形界面；
4、第五代软件：第五代软件：面向对象程序设计，面向对象程序设计，WindowsWindows，JavaJava，WWWWWW；5 5第第二二章章 二进制数值和记数系统二进制数值和记数系统数制：按进位原则进行计数，逢数制：按进位原则进行计数，逢R R进一。进一。基数：数制中所需的数字字符个数。基数：数制中所需的数字字符个数。R R进制的基数进制的基数=R=R位权：是一个与数字位置有关的常数，位权位权：是一个与数字位置有关的常数，位权=R Rn n其中其中n n取值：以小数点为界，向左取值：以小数点为界，向左 0 0，1 1，2 2，33，向右向右-1-1，-2-2，-3-3例：例：(275.8)(2
5、75.8)1010=210=2102 27107101 15105100 0810810-1-16 67 78 8二进制数二进制数 十进制数十进制数位权相加法位权相加法：各位数码乘位权，再相加。各位数码乘位权，再相加。例：例：(1011.1)2=123+022+121+120+12-1 =8+0+2+1+0.5=(11.5)10整数部分从右向左，小数部分从左向右，整数部分从右向左，小数部分从左向右，每每3位二进制一组，变为位二进制一组，变为1位八进制。位八进制。不足不足3位时分别在最左端和最右端补位时分别在最左端和最右端补0凑够凑够3位。位。例：例：(1100101001011.1101)2=
6、(14513.64)8 二进制数二进制数 八进制数八进制数二进制二进制 十六进制十六进制整数部分从右向左，小数部分从左向右，整数部分从右向左，小数部分从左向右，每每4位二进制一组，变为位二进制一组，变为1位十六进制。位十六进制。不足不足4位时分别在最左端和最右端补位时分别在最左端和最右端补0凑够凑够4位。位。例：例：(11010111101.1010001)2=(6BD.A2)16 9 9位位(bit)：计算机存储数据的最小单位计算机存储数据的最小单位(0、1)字节字节(Byte)：处理数据的基本单位处理数据的基本单位(8bit/Byte)31 30 31 30 25 24 25 24 232
7、3 22 7 022 7 00 1 0 0 0 1 1 0 0 10 0 1 1 0 10 0 11 1一个一个字字(Word)由由2、4或或8个字节组成。个字节组成。一个字的每一位由右至左编号。如一个字的每一位由右至左编号。如32位字长：位字长：1010第三章第三章 数据表示法数据表示法模拟信号和数字信号模拟信号和数字信号无符号数和有符号数无符号数和有符号数符号位符号位：二进制数的最高位表示二进制数的最高位表示“正正”、“负负”。0 0为正，为正，1 1为负。为负。1111原码原码：正号为正号为0 0，负号为，负号为1 1，数值部分为二进制绝，数值部分为二进制绝对值。对值。补码补码：正数的补
8、码和原码相同；负数的补码是将正数的补码和原码相同；负数的补码是将其原码除符号位外各位取反，末位加其原码除符号位外各位取反，末位加1 1。-5 1 0 0 0 0 1 0 1原码原码1 1 1 1 1 0 1 1补码补码+5的原码、补码都是的原码、补码都是00000101为了运算方便，机器数采用原码、补码表示。为了运算方便，机器数采用原码、补码表示。1212u小数点位置固定的数称为定点数。小数点位置固定的数称为定点数。定点整数：小数点固定在数值部分最右端。定点整数：小数点固定在数值部分最右端。定点小数：小数点固定在数值部分最左端。定点小数：小数点固定在数值部分最左端。u 小数点位置不固定的数称为
9、浮点数，分为阶码小数点位置不固定的数称为浮点数，分为阶码（指数）和尾数两部分。（指数）和尾数两部分。31 30 25 24 23 22 5 031 30 25 24 23 22 5 00 0 0 0 0 1 1 0 0 10 0 0 01 0 10 0阶码部分阶码部分尾数部分尾数部分阶码阶码符号位符号位尾数尾数符号位符号位1 1例例：将十进制数：将十进制数 +55+55 以浮点数格式存放。以浮点数格式存放。(55)(55)1010=(110111)=(110111)2 2=0.110111*2=0.110111*26 61313西文字符的编码：西文字符的编码：ASCII码码(American
10、Standard Code for Information Interchange)t128个常用字符，用个常用字符，用7位二进制编码，占一个字节，最高位位二进制编码，占一个字节，最高位0。t 其中，控制字符：其中，控制字符：032，127；普通字符：；普通字符：94个。个。例如：例如：“a”字符的编码为字符的编码为1100001，对应的十进制数是，对应的十进制数是97；字符字符 对应的十六进制对应的十六进制 对应的十进制对应的十进制 换行换行 0AH 10 回车回车 0DH 13 空格空格 20H 32 09 30H39H 4857 AZ 41H5AH 6590 az 61H7AH 9712
11、21414和汉字有关的编码：和汉字有关的编码：(1)汉字输入码：操作人员通过键盘输入的汉字编码。汉字输入码：操作人员通过键盘输入的汉字编码。(2)汉字国标码汉字国标码(GB231280)每个汉字占两个字节的编码。所有汉字分区，每个区每个汉字占两个字节的编码。所有汉字分区，每个区94个汉字。区号和位号各加个汉字。区号和位号各加32构成国标码。构成国标码。(3)机内码机内码计算机内部存储和加工汉字所用的编码。计算机内部存储和加工汉字所用的编码。每个汉字的国标码的每个字节最高位改为每个汉字的国标码的每个字节最高位改为1，即成机内码。，即成机内码。汉字汉字 国标码国标码 汉字机内码汉字机内码中中 86
12、80(01010110 01010000)2 (11010110 11010000)2 华华 5942(00111011 00101010)2 (10111011 10101010)2 (4)汉字字形码：点阵（汉字字形点阵的代码）汉字字形码：点阵（汉字字形点阵的代码）1515差错校验码奇偶校验码为一个字节补充为一个字节补充1bit（校验位），设置校验位的值（校验位），设置校验位的值为为0或或1，使字节中的，使字节中的8bit和该校验位含有和该校验位含有1值的个数值的个数为奇数（奇校验）或偶数（偶校验）。为奇数（奇校验）或偶数（偶校验）。数据数据奇校验编码奇校验编码偶校验编码偶校验编码0000
13、00001 0000 00000 0000 00000101 01000 0101 01001 0101 01001616n关键字编码关键字编码关键字编码是用单个字符代替常用单词或前后缀。关键字编码是用单个字符代替常用单词或前后缀。如：如：thethe and+that$and+that$文本压缩方法：文本压缩方法：n行程长度编码行程长度编码在一些数据流中，某个字符可能连续地反复出现。在一些数据流中，某个字符可能连续地反复出现。因此，重复字符序列被替换为：因此，重复字符序列被替换为：标志字符该字符出现次数标志字符该字符出现次数1717文本压缩方法：文本压缩方法：n哈夫曼编码哈夫曼编码1.计算信
14、源符号出现的概率。计算信源符号出现的概率。p-0.125,a-0.25,s-0.375,g-0.125,e-0.1252.概率最小的两个符号概率相加合成一个概率。概率最小的两个符号概率相加合成一个概率。3.将合成概率看成一个新组合符号概率，重复上述将合成概率看成一个新组合符号概率，重复上述做法，直到最后只剩下两个符号概率为止。做法，直到最后只剩下两个符号概率为止。4.反过来逐步向前编码，每一步有两个分支各赋予反过来逐步向前编码，每一步有两个分支各赋予一个二进制码，可以对概率大的编码为一个二进制码，可以对概率大的编码为1.1818l采样频率采样频率：每秒钟的采样次数。：每秒钟的采样次数。l量化位
15、数量化位数(采样精度采样精度)：存放采样点振幅值的二：存放采样点振幅值的二进制位数。通常量化位数有进制位数。通常量化位数有8 8位、位、1616位等。位等。音频信息的数字化：音频信息的数字化：捕捉声音时用固定的时间间隔对声波进行采样捕捉声音时用固定的时间间隔对声波进行采样（离散化处理），例如（离散化处理），例如44.1kHz44.1kHz；（采样）（采样）将每个采样点的振幅值转换为二进制数值，例将每个采样点的振幅值转换为二进制数值，例如用如用8 8位或位或1616位二进制表示。位二进制表示。（量化）（量化）把量化后的信号数据编成一个二进制码组输出。把量化后的信号数据编成一个二进制码组输出。（编
16、码）（编码）1919 图像信息的数字化：图像信息的数字化：用用“m m行行nn列列”个像素点来离散化一幅图像，个像素点来离散化一幅图像，例如例如10247681024768分辨率；分辨率；（采样）（采样）将每个像素点的三基色强度转换为二进制值，将每个像素点的三基色强度转换为二进制值，例如用例如用8 8位、位、1616位、位、2424位、位、3232位二进制表示。位二进制表示。（量化）（量化）数字化图像的数据量很大，所以需要采用编数字化图像的数据量很大，所以需要采用编码技术来压缩信息，减少数据量。码技术来压缩信息，减少数据量。（编码）（编码）分辨率分辨率：图像中的行数和列数，每个行与列的：图像中
17、的行数和列数，每个行与列的交点就是一个像素。例如交点就是一个像素。例如1024768。颜色深度颜色深度：每个像素点颜色值的存储位数。：每个像素点颜色值的存储位数。2020 视频信息的数字化：视频信息的数字化：连续动态的视频由多帧静态图像组成。连续动态的视频由多帧静态图像组成。采样频率：每秒捕捉的画面帧数。采样频率：每秒捕捉的画面帧数。采样精度：经采样后每帧所包含的颜色位采样精度：经采样后每帧所包含的颜色位（色彩值）。如（色彩值）。如8 8位，位，3232位。位。必须对海量的视频数据及其伴音进行压缩必须对海量的视频数据及其伴音进行压缩和编码。和编码。2121图像文件常用格式图像文件常用格式bmp
18、,gif,jpg,wmf 视频文件常用格式视频文件常用格式avi,mov,mpg,dat音频文件常用格式音频文件常用格式wma,wav,mp3,mid 2222第四章第四章 门和电路门和电路门电路：接受一个或多个输入信号，生门电路：接受一个或多个输入信号，生成一个输出信号。每种类型的门执行一成一个输出信号。每种类型的门执行一个特殊的逻辑函数。个特殊的逻辑函数。非门，与门，或门，异或门，与非门，非门，与门，或门，异或门，与非门，或非门或非门 等。等。2323非门：非门：真值表真值表0 01 11 10 0X=AX=AA AX =AX =A逻辑框图符号逻辑框图符号与门：与门：1 11 11 10
19、00 01 11 10 0B B0 00 00 00 0X=A*BX=A*BA A真值表真值表逻辑框图符号逻辑框图符号X =A *BX =A *B2424或门：或门：真值表真值表逻辑框图符号逻辑框图符号1 11 11 11 10 01 11 10 0B B1 10 00 00 0X=AX=AB BA A异或门：异或门：两个输入相同时，输出是两个输入相同时，输出是0，否则输出，否则输出1。0 01 11 11 10 01 11 10 0B B1 10 00 00 0X=AX=A B BA A真值表真值表逻辑框图符号逻辑框图符号2525与非门：让与门的结果再经过一个非门。与非门：让与门的结果再经过
20、一个非门。或非门：让或门的结果再经过一个非门。或非门：让或门的结果再经过一个非门。2626用晶体管构造门用晶体管构造门晶体管本身晶体管本身就是非门。就是非门。非门非门V1,V2都是都是1,源极将被接地源极将被接地,Vout=0。否则否则Vout=1。与非门与非门V1或或V2是是1时时,源极将被源极将被接地接地,Vout=0。当当V1和和V2都是都是0时，源时，源极才不被接地，极才不被接地，Vout=1。或非门或非门2727“异或异或”逻辑表达式：逻辑表达式：X=A B=AB+ABABX&2828半加器半加器 half adder：计算两个数位的和并生成正确进位的电路。计算两个数位的和并生成正确
21、进位的电路。和和=A =A B B进位进位=AB=AB和和进位进位&2929全加器全加器 full adder：计算两个数位的和并考虑进位输入的电路。计算两个数位的和并考虑进位输入的电路。和和进位输入进位输入进位输出进位输出&+C和和=A =A B B C C进位输出进位输出=AB=AB+C(+C(A A B B)3030加法器加法器 adder：8bit相加需要复制相加需要复制8次全加器电路。次全加器电路。一个一个bit位的进位输出将作为下一个位的进位输出将作为下一个bit位的进位输入。位的进位输入。最右边最右边bit的进位输入是的进位输入是0，最左边，最左边bit的进位输出被的进位输出被舍
22、弃（溢出）。舍弃（溢出）。4 4位加法器例子位加法器例子31311 1 输出端输出端0 0 输出端输出端清清 0 0 端端置置 1 1 端端ABS-RS-R锁存器锁存器(S-R latch)(S-R latch)S=0,R=1时，时，X=1。R=0,S=1时，时，X=0。S=1,R=1时，时，X 保持不变。保持不变。S和和R不能同时为不能同时为0。3232第五章第五章 计算部件计算部件内存单元：存储信息的单位内存单元：存储信息的单位(字节字节)。内存中有大量的。内存中有大量的内存单元。内存单元。内存单元的地址：每个内存单元都有唯一的地址。内存单元的地址：每个内存单元都有唯一的地址。3333CP
23、UCPU的主要性能指标的主要性能指标 ：u 主频：主频：CPUCPU内核运算电路的运行频率。内核运算电路的运行频率。u CPUCPU外频：外频：CPUCPU总线频率，外频提高则与内存交总线频率，外频提高则与内存交换数据的速度越快。主频外频换数据的速度越快。主频外频倍频系数。倍频系数。u 数据总线宽度：即字长，如数据总线宽度：即字长，如3232位、位、6464位。位。CPU：算术和逻辑运算单元算术和逻辑运算单元ALU、控制器和寄存器组。控制器和寄存器组。CPU可执行的一组指令称为可执行的一组指令称为指令集指令集。精。精简指令集和复杂指令集。简指令集和复杂指令集。3434运算器运算器ALU:执行算
24、术、逻辑运算执行算术、逻辑运算寄存器组寄存器组:存源、中间数据存源、中间数据标志寄存器标志寄存器:保存标志信息保存标志信息控制器控制器 PC：存放下一条指令的地址：存放下一条指令的地址 IR：存放正执行指令的内容：存放正执行指令的内容 译码器译码器：区分指令执行的步骤：区分指令执行的步骤 产生控制信号产生控制信号：向其它各部件发出控制信号，：向其它各部件发出控制信号，保证各部件协调一致地工作保证各部件协调一致地工作3535总线总线按所传输的内容分，有：按所传输的内容分，有：数据总线：数据总线：传送数据。如：传送数据。如：“奔腾奔腾”CPUCPU有有3232条数条数据线，表示每次可和内存并行交换
25、据线，表示每次可和内存并行交换3232位二进制数。位二进制数。地址总线：地址总线：用于传送用于传送CPUCPU发出的地址信息，即指明发出的地址信息，即指明数据总线上的数据的源地址或目的地址。地址总线的数据总线上的数据的源地址或目的地址。地址总线的宽度决定了宽度决定了CPUCPU的最大寻址能力的最大寻址能力 (即所允许的最大内即所允许的最大内存容量存容量)。控制总线：控制总线：传送控制信号。传送控制信号。3636指令执行周期：指令执行周期：1 1、取指令、取指令3 3、执行、执行4 4、指针增加，、指针增加，指向下一条指令指向下一条指令2 2、分析指令、分析指令及取数及取数操作码操作码 操作数操
26、作数 操作码：要完成的操作类型操作码：要完成的操作类型操作数：操作数所在的地址或操作数本身操作数：操作数所在的地址或操作数本身例：例：JMP M1;ADD REG1 REG2指令格式：指令格式：3737内存：直接与内存：直接与CPUCPU交换信息的存储设备。用来存放计交换信息的存储设备。用来存放计算机运行期间所需的信息，如：指令、程序、文档。算机运行期间所需的信息，如：指令、程序、文档。外存：内存的延伸，长期存放暂时不用的数据。如系外存：内存的延伸，长期存放暂时不用的数据。如系统文件、应用程序、用户文档等。统文件、应用程序、用户文档等。3838非非von Neumann结构：结构：不采用不采用
27、“线性的读取执行周期线性的读取执行周期”。并行（分布式）处理并行（分布式）处理 w阵列计算机：多个处理机对不同数据同时运行相阵列计算机：多个处理机对不同数据同时运行相同指令。同指令。w多指令流多数据流多指令流多数据流MIMDMIMD系统：多个处理机对不同系统：多个处理机对不同数据执行不同指令。数据执行不同指令。3939流水线技术（流水线技术（PipelinePipeline）取指取指译码译码地址生成地址生成取数取数执行执行写回写回取指取指译码译码地址生成地址生成取数取数执行执行写回写回取指取指译码译码地址生成地址生成取数取数执行执行写回写回取指取指译码译码地址生成地址生成取数取数执行执行写回写
28、回指令指令指令指令1 1指令指令指令指令2 2指令指令指令指令3 3指令指令指令指令4 4w将每条指令分解成多个阶段，几条指令的不同阶段将每条指令分解成多个阶段，几条指令的不同阶段重叠运行，使控制器、运算器、存储器等同时工作。重叠运行，使控制器、运算器、存储器等同时工作。w如如PentiumPentium的的6 6级流水线结构：级流水线结构：4040v计算机问题求解三阶段：不断反复的过程计算机问题求解三阶段：不断反复的过程v算法开发：得到问题的通用解决方案算法开发：得到问题的通用解决方案w分析问题、提出并测试算法分析问题、提出并测试算法v算法实现：得到计算机可运行的程序算法实现：得到计算机可运
29、行的程序w编码和测试程序编码和测试程序v维护：在实践中检验维护：在实践中检验w实际运转、修改维护程序实际运转、修改维护程序第六章第六章 问题求解和算法设计问题求解和算法设计4141v两种程序设计方法：两种程序设计方法：v自顶向下方法自顶向下方法(Top-down Methodology)程序设计模式：程序设计模式：“数据结构算法数据结构算法”在软件功能说明书中，在软件功能说明书中，动词动词是重点。是重点。v面向对象程序设计面向对象程序设计(Object Oriented Programming)程序设计模式：程序设计模式：“对象消息对象消息”在软件功能说明书中，在软件功能说明书中，名词名词是重
30、点。是重点。4242自顶向下程序设计方法自顶向下程序设计方法自顶向下、逐步求精：逐层分解复杂任务，把任务自顶向下、逐步求精：逐层分解复杂任务，把任务细节推延到下层模块中实现。细节推延到下层模块中实现。模块化：每个模块完成特定的、相对简单的功能。模块化：每个模块完成特定的、相对简单的功能。流程控制结构化：程序通过顺序、分支、循环三种流程控制结构化：程序通过顺序、分支、循环三种基本控制结构来实现。基本控制结构来实现。4343面向对象的程序设计方法面向对象的程序设计方法面向对象面向对象=类类+对象对象+继承继承+消息消息+通信通信 对对一组具有一组具有相同属性和相同属性和行为的对象行为的对象的抽象描
31、述。的抽象描述。对象是类对象是类的实例。的实例。具有属性具有属性和方法。和方法。子类子类可以继承可以继承父类的属性和父类的属性和方法，实现代方法，实现代码重用。码重用。对象间通过消对象间通过消息息(事件事件)进行进行通信，执行其通信，执行其它对象的方法。它对象的方法。4444继承继承 inheritance：子类得到父类的全部属性和方法，：子类得到父类的全部属性和方法，还可以扩充和覆盖父类的成员。还可以扩充和覆盖父类的成员。多态多态 polymorphism：也称：也称重载。不同子类中同一方重载。不同子类中同一方法名可定义成不同代码，所以它们法名可定义成不同代码，所以它们在收到同一消息在收到同
32、一消息时做出的响应行为也不同。时做出的响应行为也不同。封装封装 encapsulation：将属性和行为隐藏起来，外部：将属性和行为隐藏起来，外部通过特定的接口访问对象成员。好处是保护成员，通过特定的接口访问对象成员。好处是保护成员，修改程序时只涉及类的内部。修改程序时只涉及类的内部。4545第七章第七章 低级程序设计语言低级程序设计语言机器语言：由二进制代码组成。能被计算机直接机器语言：由二进制代码组成。能被计算机直接理解和执行，但编程困难，可移植性差。理解和执行，但编程困难，可移植性差。把机器指令中的操作码和操作数用英文助记符和把机器指令中的操作码和操作数用英文助记符和符号地址来表示，称为
33、汇编语言。依赖于机器，符号地址来表示，称为汇编语言。依赖于机器，可移植性同样较差。可移植性同样较差。4646第八章第八章 高级程序设计语言高级程序设计语言目标程序目标程序.objobj源程序源程序.c.c可执行程序可执行程序.exe.exe编译器编译器连接程序连接程序数据数据运行运行结果结果t编译器对整个源程序经过编译处理，产生一个与源编译器对整个源程序经过编译处理，产生一个与源程序等价的目标程序；通过连接程序将目标程序和程序等价的目标程序；通过连接程序将目标程序和有关的程序库组合成一个完整的可执行程序；有关的程序库组合成一个完整的可执行程序；t执行速度快，修改源程序后都必须重新编译。同一执行
34、速度快，修改源程序后都必须重新编译。同一种高级语言在不同种高级语言在不同CPU平台上需要不同的编译器。平台上需要不同的编译器。4747t解释程序对源程序进行逐句分析，若没有错误，解释程序对源程序进行逐句分析，若没有错误，将该语句翻译成一个或多个机器语言指令，然后将该语句翻译成一个或多个机器语言指令，然后立即执行这些指令；若解释时发现错误，则立即立即执行这些指令；若解释时发现错误，则立即停止，报错并提醒用户更正代码。停止，报错并提醒用户更正代码。t解释方式不生成目标程序，执行速度慢。解释方式不生成目标程序，执行速度慢。数据数据高级语言高级语言源程序源程序解释程序解释程序计算结果计算结果4848t
35、Java源程序先经过编译生成源程序先经过编译生成Java字节码，然后由字节码，然后由JVM(Java Virtual Machine,Java虚拟机虚拟机)解释执行。解释执行。tJava字节码相当于是字节码相当于是“标准的机器语言标准的机器语言”，速度快，速度快，唯一，只要有相应的唯一，只要有相应的JVM解释器，解释器，Java字节码可在任字节码可在任何环境下运行，如：何环境下运行，如：PC、UNIX工作站、工作站、Macintosh等。等。字节码文件字节码文件.class.class源程序源程序.java.java编译器编译器javacjavac解释器解释器javajava运行运行结果结果在
36、浏览器中运行的在浏览器中运行的Java字节码为字节码为Java Applet(Java小程序小程序)。4949程序设计时的程序设计时的 控制结构控制结构：顺序、分支、循环结构顺序、分支、循环结构顺序结构：顺序结构：按照语句出现的先后顺序依次执行。按照语句出现的先后顺序依次执行。分支结构：分支结构：根据给定条件判断，决定程序执行的顺序。根据给定条件判断，决定程序执行的顺序。循环结构：循环结构：重复多次执行语句集合。重复多次执行语句集合。5050第九章第九章 抽象数据类型和算法抽象数据类型和算法数据元素存放数据元素存放在连续存储空在连续存储空间中间中顺序存储方式顺序存储方式 数据可以存放在数据可以
37、存放在不连续的存储空不连续的存储空间中。间中。通过指针指向下通过指针指向下一数据元素。一数据元素。数据域数据域指针域指针域链式存储方式链式存储方式 5151数组数组(Array)：按：按“行优先行优先”或或“列优先列优先”方式顺序方式顺序存储数组元素。插入删除元素时需移动大量元素。存储数组元素。插入删除元素时需移动大量元素。在一个有在一个有n n个元素的数组个元素的数组A A中的第中的第i i个元素之前插入个元素之前插入一个元素一个元素x x时，将第时，将第i i个元素及其后的元素后移：个元素及其后的元素后移：for (j=n;j=i;j-)Aj+1=for (j=n;j=i;j-)Aj+1=
38、AjAj;AiAi=x;=x;n+;n+;在一个有在一个有n n个元素的数组个元素的数组A A中删除第中删除第i i个元素时，将个元素时，将第第i i个元素之后的元素前移：个元素之后的元素前移：for (j=i;j=n;j+)for (j=i;jnext=p-next;p-next=s;删除节点删除节点p时的操作：时的操作：首先从链首首先从链首head开始，顺序查找到节点开始，顺序查找到节点q和它的和它的后继节点后继节点p（该删除的节点），然后（该删除的节点），然后 q-next=p-next;5353线性表线性表是由是由n(n0)个数据元素个数据元素a1,a2,an组成的有限序列。组成的有限
39、序列。栈栈(Stack)：只允许在表的一端进行插入和删除的线性表。：只允许在表的一端进行插入和删除的线性表。队列队列(Queue)：限制在表的一端插入，在表的另一端删除。：限制在表的一端插入，在表的另一端删除。数组数组(Array)是同类型数据元素构成的集合。是同类型数据元素构成的集合。通过数组名和下标访问数组元素。按行优先顺序存储。通过数组名和下标访问数组元素。按行优先顺序存储。树树(Tree)：一个结点最多有一个直接前趋结点但可以有多个直：一个结点最多有一个直接前趋结点但可以有多个直接的后继结点。接的后继结点。二叉树二叉树：根根5454折半查找折半查找：要求线性表事先按关键字大小排好顺序并
40、：要求线性表事先按关键字大小排好顺序并且线性表采用顺序存储（即数组）方式。且线性表采用顺序存储（即数组）方式。先取表的中间位置的结点关键字与所给定的关键字进行比先取表的中间位置的结点关键字与所给定的关键字进行比较，如果相等，则查找成功；较，如果相等，则查找成功；如果给定值比该结点的关键字大，则所找结点在表的后半如果给定值比该结点的关键字大，则所找结点在表的后半部分；否则所找结点在表的前半部分；部分；否则所找结点在表的前半部分；然后再把选定的部分表的中间结点的关键字与给定关键字然后再把选定的部分表的中间结点的关键字与给定关键字进行比较；如此反复，直到查找成功或者查找失败为止。进行比较；如此反复，
41、直到查找成功或者查找失败为止。选择排序，冒泡排序，快速排序选择排序，冒泡排序，快速排序 5555二叉排序树二叉排序树：二叉树中的每个节点的关键字均大于其左子树上二叉树中的每个节点的关键字均大于其左子树上所有节点的关键字，且小于等于其右子树上所有所有节点的关键字，且小于等于其右子树上所有节点的关键字。节点的关键字。例如，给出例如，给出K=10,18,3,8,19,2,7,8，构造二叉排序树。构造二叉排序树。10318821987第第1个数就是树根。个数就是树根。树的形状由数插入树的形状由数插入树的顺序决定。树的顺序决定。5656第十章第十章 操作系统操作系统编译程序编译程序 汇编程序汇编程序 文
42、本编辑器文本编辑器 数据库系统数据库系统系统程序和应用程序系统程序和应用程序操作系统操作系统计算机硬件计算机硬件用户用户1用户用户2用户用户3用户用户n操作系统：计算机硬件和软件资源的管理者。操作系统：计算机硬件和软件资源的管理者。5757操作系统构成：操作系统构成：进程管理、内存管理、文件管理、进程管理、内存管理、文件管理、输入输出系统管理，作业管理。输入输出系统管理，作业管理。操作系统主要类别：操作系统主要类别：批处理系统批处理系统1 1分时系统分时系统2 2实时系统实时系统3 35858分时操作系统分时操作系统:“分时分时”的含义：的含义：时间片轮转，轮流占用时间片轮转，轮流占用CPUC
43、PU人机交互性好：程序的运行由用户自己操作。人机交互性好：程序的运行由用户自己操作。共享主机：多个用户同时使用共享主机：多个用户同时使用同一台计算机同一台计算机。对每个用户而言好象独占主机。对每个用户而言好象独占主机。实时操作系统：实时操作系统：及时响应外部事件的请求，在规定的严格时间内完及时响应外部事件的请求，在规定的严格时间内完成对该事件的处理。成对该事件的处理。要求：要求：及时响应、快速处理，高可靠性和安全性及时响应、快速处理，高可靠性和安全性应用领域：过程控制、事务处理。应用领域：过程控制、事务处理。5959内存分配方案内存分配方案-连续内存分配连续内存分配首次适应首次适应(First
44、-fit)策略策略最佳适应最佳适应(Best-fit)策略策略最差适应最差适应(Worst-fit)策略策略在在可用内存中找到足够大的一块连续内存可用内存中找到足够大的一块连续内存(如如100KB)100KB)，切出要求长度的内存切出要求长度的内存(如如70KB)70KB)分配，剩余内存分配，剩余内存(如如30KB)30KB)作为新空闲区留待以后分配或合并。作为新空闲区留待以后分配或合并。内存分配方案内存分配方案-分页式内存管理分页式内存管理为解决碎片问题和实现不连续分配，采用页式管理。为解决碎片问题和实现不连续分配，采用页式管理。6060虚拟内存：虚拟内存：当一个用户程序要调入内存运行时，不
45、是将该当一个用户程序要调入内存运行时，不是将该程序的所有页面都装入内存，而是只装入部分程序的所有页面都装入内存，而是只装入部分的页面，就可启动程序运行；的页面，就可启动程序运行；在运行的过程中，如果发现要运行的程序或要在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请访问数据不在内存，则向系统发出缺页中断请求；求；系统在处理这个中断时，将磁盘上相应的页面系统在处理这个中断时，将磁盘上相应的页面调入内存，使得该程序能够继续运行。调入内存，使得该程序能够继续运行。6161进程进程是程序对某个数据集的一次执行过程。是程序对某个数据集的一次执行过程。v程序是静态概念程序是
46、静态概念(建立与删除建立与删除)；进程是动态概念。；进程是动态概念。一个进程由三部分组成：一个进程由三部分组成：进程控制块进程控制块PCBPCB，程序段，数据集，程序段，数据集新进程新进程就绪就绪运行运行终止终止等待等待允许允许中断中断退出退出允许允许I/O操作或事件的完成操作或事件的完成I/O操作或事件的等待操作或事件的等待6262 CPU调度：把调度：把CPU分配给某个就绪进程去运行。分配给某个就绪进程去运行。不可抢占式：当前运行进程完成或阻塞或时间片不可抢占式：当前运行进程完成或阻塞或时间片到时，才再分配处理机。到时，才再分配处理机。抢占式：将正运行进程强行撤下，处理机分配给抢占式：将正
47、运行进程强行撤下，处理机分配给其它进程。例如当有一个优先权更高的进程进入就绪其它进程。例如当有一个优先权更高的进程进入就绪队列时。队列时。先到先服务先到先服务 (FCFS,First-Come,First-Served)(FCFS,First-Come,First-Served)最短作业优先最短作业优先 (SJF,Shortest-Job-First)(SJF,Shortest-Job-First)轮转轮转(RR,Round-Robin)(RR,Round-Robin)：时间片轮转时间片轮转6363第十一章第十一章 文件系统和目录文件系统和目录文件：文件：存储在外存上具有标识名的一组相关字存储
48、在外存上具有标识名的一组相关字符流或记录的集合。符流或记录的集合。透明存放和按名存取透明存放和按名存取透明存放和按名存取透明存放和按名存取文件的命名：文件的命名：文件名文件名.扩展名扩展名6464 OS将每个将每个目录目录看成看成一张表，表中是该目录下所有一张表，表中是该目录下所有文件的信息。（其实目录本身也是一个文件）文件的信息。（其实目录本身也是一个文件）创建文件创建文件时，先在磁盘上为新文件分配一个空闲时，先在磁盘上为新文件分配一个空闲块，然后在目录表中添加一新条目。块，然后在目录表中添加一新条目。文件名文件名权限权限建立时间建立时间文件长度文件长度第一磁盘块号第一磁盘块号盘块数盘块数其
49、它其它my01.c1101605092268B565722abc.exe001230000220324B356364q123.doc110322083156342B4585715xyz.txt 11192210012B2434116565访问方式访问方式顺序访问顺序访问随机访问随机访问从开始位置顺序读取字符从开始位置顺序读取字符/记录，适合于磁带记录，适合于磁带可在任何位置读可在任何位置读取字符取字符/记录，适记录，适合于磁盘合于磁盘/光盘光盘UNIX中的文件存取权限：中的文件存取权限：v 用户分三类：文件主、同组用户、其他用户。用户分三类：文件主、同组用户、其他用户。v 权限有三种：读权限有
50、三种：读R、写、写W、执行执行X。6666 磁盘调度：当多个进程都提出磁盘调度：当多个进程都提出“磁盘访问请求磁盘访问请求”时，需要对访盘请求的服务顺序进行调整，以时，需要对访盘请求的服务顺序进行调整，以降低平均磁盘访问时间。降低平均磁盘访问时间。FCFS先来先服务：按请求的次序服务。先来先服务：按请求的次序服务。SSTF最短寻道时间优先：优先选择距当前磁最短寻道时间优先：优先选择距当前磁头位置最近的访问请求进行服务。头位置最近的访问请求进行服务。SCAN扫描算法扫描算法(电梯算法电梯算法)：选择位于磁头移动方：选择位于磁头移动方向前方且距磁头位置最近的访问请求进行服务。向前方且距磁头位置最近