教学课件-大学计算机基础(第3版)-孙淑霞

第1章引论目录

1.1计算机发展历史1.2计算模型1.3计算机系统1.4计算机文化和计算思维1.5计算机的应用及其发展前景1.1计算机发展历史——起源人类追求的计算工具算筹算筹计数法算盘机械加法器Pascaline巴贝奇差分机MARK-1自动数字计算机1.1计算机发展历史——起源1946年，世界上第一台电子数字积分计算机ENIAC(ElectronicNumericalIntegratorAndCalculator)在美国诞生了。5000次加法/秒体重30吨占地170m218000多只电子管1500个继电器1.1计算机发展历史——历史第五代：具有人工智能的计算机——研制中第一代（1946--1955）电子管5千--4万（次/秒）第二代（1956--1963）晶体管几万—几十万（次/秒）第三代（1964--1971）集成电路几十万--百万（次/秒）第四代（1971--至今）超大规模集成电路几百万--百亿（次/秒）1.1计算机发展历史——新技术云计算（CloudComputing）是一种通过Internet以服务的方式提供动态的、可伸缩的、虚拟化资源的计算模式。移动互联网（MobileInternet）是指互联网的技术、平台、商业模式和应用与移动通信技术结合并实践的活动的总称。物联网（TheInternetofthings）顾名思义就是物物相连的互联网。1.2计算模型——图灵与图灵机模型“计算机界诺贝尔奖”——图灵奖阿兰•图灵（AlanTuring）“计算机科学的奠基人”、“人工智能之父”英国著名数学家、逻辑学家、密码学家提出了“图灵机”和“图灵测试”1.2计算模型——图灵与图灵机模型图灵机模型理论是计算学科最核心的理论之一，图灵机模型为计算机设计指明了方向。图灵机由三部分组成：一条两端都可无限延长的被分为一个个小方格的纸带、一个有限状态控制器和一个在带子上可以左右移动的读写头。……a1a2……ai……an……控制器状态q11.2计算模型——图灵与图灵机模型图灵机的形式化定义一台图灵机是一个七元组（Q，∑，Γ，δ，q0，B，F），其中：Q是有限状态集

∑是有限输入字符集Γ是有限输入带字符集 δ是状态转移函数q0是初始状态 B是空格符F是有限终结状态集1.2计算模型——冯•诺依曼计算机冯·诺依曼：美籍匈牙利数学家，提出了著名的“存储程序”设计思想。存储程序工作原理存储程序到内存自动按地址执行程序1949EDSACJohnVonNouma1.2计算模型——冯•诺依曼计算机指令是能被计算机识别并执行的二进制代码，它规定了计算机能完成的某一种操作。是对计算机进行程序控制的最小单位。程序是为完成一项特定任务而用某种语言编写的一组指令序列。指令系统是一台计算机的所有指令的集合。机器指令格式操作码操作数机器执行什么操作执行对象（具体数、存放位置）1.2计算模型——冯•诺依曼计算机12输入设备输入信息存储器运算器控制器输出设备表示数据信息流向表示控制信息流向冯·诺依曼计算机模型1.2计算模型——哈佛结构哈佛结构（Harvardarchitecture）是一种将程序指令存储和数据存储分开的存储器结构，它是一种并行体系结构，它可减轻程序运行时的访存瓶颈，从而提高执行速度和数据的吞吐量，提高数字信号的处理能力。程序计数器（PC）程序存储器数据存储器地址数据地址数据CPU1.2计算模型量子计算机（QuantumComputer）是一种遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。生物计算机（Bio-computer）是将生物工程技术产生的蛋白质分子作为原材料制成生物芯片，利用有机化合物存储数据的计算机。1.3计算机系统——系统构成硬件系统计算机系统软件系统主机外部设备总线输入设备输出设备中央处理器（CPU）内存储器系统软件应用软件RAMROM运算器控制器1.3计算机系统——硬件系统运算器：对数据进行算术运算和逻辑运算的部件。控制器：电子计算机的指挥部，负责协调指挥各部件的工作。存储器：计算机记忆或暂存数据的部件。输入设备：输入是指利用某种设备将数据转换成计算机可以接收的编码的过程，所使用的设备称为输入设备。输出设备：用来输出处理结果的设备。总线：用于连接计算机中的五大组成部件构成一个完整的硬件系统。1.3计算机系统——软件系统系统软件软件应用软件操作系统程序设计语言语言处理程序诊断程序数据库管理系统办公软件浏览器图形图像处理软件其他应用软件1.3计算机系统——计算机工作过程例：计算机计算2+3的执行步骤。第一步：输入指令（将数据和程序输入到存储器中）第二步：取数指令（从存储器取数2）第三步：取数指令（从存储器取数3）第四步：加法指令（执行2+3的运算）第五步：存数指令（将计算结果5送到存储器保存）第六步：输出指令（输出计算结果）1.3计算机系统——计算机工作过程指令执行过程简图执行指令解释指令从存储器取出指令1.3计算机系统——典型计算机系统台式机的性能更强，可扩展性好。笔记本携带方便，输入和定位功能好。掌上计算机和智能手机小巧轻便，可扩展性差。台式机笔记本智能手机掌上计算机1.4计算机文化和计算思维计算机是一种“可以传授给人知识的工具”，也是一种“无比有力的知识工具”。计算机文化是人类社会的生存方式因使用计算机而发生根本性变化而产生的一种崭新文化形态。真正对人类生活带来直接冲击的，不是计算机硬件本身，而是来自软件这种人类知识的产物。1.4计算机文化和计算思维科学达尔文曾给科学下过一个定义：“科学就是整理事实，从中发现规律，作出结论”。科学一般包含：自然科学、社会科学和思维科学。思维思维是高级的心理活动，是认识的高级形式。思维是人脑对现实事物概括、加工、揭露本质特征。人脑对信息的处理包括分析、抽象、综合、概括等。1.4计算机文化和计算思维人类文明进步和科学发现的三大科学是理论科学、实验科学和计算科学。三种科学与三种思维的对应：理论科学←→理论思维：理论思维又叫推理思维，以推理和演绎为特征，以数学学科为代表。实验科学←→实验思维：实验思维又叫实证思维，以观察和总结自然规律为特征，以物理学科为代表。计算科学←→计算思维：计算思维又叫构造思维，以设计和构造为特征，以计算机学科为代表。1.4计算机文化和计算思维计算思维（computationalthinking）：2006年由美国CarnegieMellon大学周以真（JeannetteWing）教授提出，她认为计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等的一系列思维活动。这些基础概念包括嵌套、递归、约简、转化、仿真、并行、抽象、分解、建模、预防、保护、恢复、冗余、容错、纠错、启发式推理、规划、学习、调度等。计算思维是如同所有人都具备“读、写、算”（简称3R）能力一样，都必须具备的思维能力。1.4计算机文化和计算思维计算思维表述体系框架中8类概念关系图计算思维的培养不是一门课程就可以解决的，而是需要一系列课程的学习逐渐形成的一种解决问题的思维能力。计算抽象自动化设计通信记忆协作评估1.4计算机文化和计算思维计算思维的例子1E8LieGroup1.4计算机文化和计算思维计算思维的例子2对大型客机进行的模拟风洞实验1.5计算机的应用及其发展前景计算机的应用科学计算过程控制计算机辅助系统数据处理人工智能网络应用全球卫星定位系统（GPS）地理信息系统（GIS）虚拟现实（VR）智能家电智能手机……其他应用1.5计算机的应用及其发展前景计算机的发展前景巨型化微型化网络化智能化ENIAC多媒体化大学计算机基础第3版姓名：时间：第二章计算机硬件基础目录

2.1理解0和12.2计算机中的数制及其运算2.3数据的存储与表示2.4数据压缩123452.5计算机硬件组成2.1.1《易经》中的0和12.1.2电路中的0和12.1理解0和12.1.3计算机中的0和12.1理解0和12.1.1

《易经》中的0和12.1.1《易经》中的0和1易经通过阴/阳来使用0和1，起始即把0和1赋予了语义，并注意了阴阳的位置与组合关系。期望通过这些内容反映一些规律性的内容。01阴阳语义符号化表达

语义符号化：是指将现实世界的语义用符号表达，进而进行基于符号的计算的一种思维，将符号赋予不同语义，则能计算不同的现实世界问题。易经通过阴/阳来使用0和1，起始即把0和1赋予了语义，并注意了阴阳的位置与组合关系。期望通过这些内容反映一些规律性的内容。语义符号化表达表达成了符号，也就能够进行计算易经通过阴/阳的演变(即0/1的运算)体现了变化中的规律(即蕴含的语义关系及转换关系)例如：二十四节气的演变规律例如：生命规律的演变规律冬至一阳生夏至一阴生2.1理解0和12.1.2

电路中的0和12.1.2电路中的0和1串联电路中的逻辑“与”关系逻辑“与”运算关系表开关A开关B灯泡F0（断开）0（断开）0（熄灭）0（断开）1（闭合）0（熄灭）1（闭合）0（断开）0（熄灭）1（闭合）1（闭合）1（发亮）2.1.2电路中的0和1并联电路中的逻辑“或”关系逻辑或运算关系表开关A开关B灯泡F0（断开）0（断开）0（熄灭）0（断开）1（闭合）1（发亮）1（闭合）0（断开）1（发亮）1（闭合）1（闭合）1（发亮）2.1.2电路中的0和1实现非功能的简单电路2.1理解0和12.1.3

计算机中的0和12.1.3计算机中的0和1计算机为什么采用二进制？可编码任意信息算术运算规则简单

适合逻辑运算

实现技术(电子元器件)简单

2.2.1数制的概念2.2.2常用数制2.2计算机中的数制及其运算2.2.3各种数制的转换2.2.4二进制数的算术逻辑运算2.2数制及其运算2.2.1

数制的概念2.2.1数制的概念（1）基数是一个计数制系统允许使用的基本数字符号（数符）的个数。例如十进制的数符分别为0、1、2、3、4、5、6、7、8、9，所以十进制的基数为10。依次类推，二进制、八进制、十六进制的基数分别是2、8、16。（2）权是以基数为底的幂，表示处于该位的数字所代表的值的大小。在一个数字当中，处在不同位置上的相同数字所表示的值也是不同的。一个数字在某个位置上的值等于该数字与这个位置上的因子的乘积，而该因子的值是由所在位置相对于小数点的距离来确定，这个因子就是位权。（3）进位制：用数码和带有权值的数位来表示有大小关系的数值型信息的表示方法。2.2数制及其运算2.2.2

常用数制2.2.2常用数制二进制：1)二进制只有两个数码：0和1;2)二进制数位i的权值：2i;3)二进制表示数值：逢二进1，借1当二；高数位的1相当于低数位的2。4)二称为计数制的基值，即“二进制”

76543210.-1-211110101.01（）2

2.2.2常用数制二进制不方便之处：与十进制相比，一个数值的数码位数长，识认比较困难。例如：245的二进制表示：

11110101另外，二进制与十进制转换也不是很方便，因此引出八进制、十六进制等2.2.2常用数制任意进制r进制

r进制的一位数表示有r个数码：0,1,…r-1r进制数位i的权值：rir进制表示数值：逢r进1，借1当r；高数位的1相当于低数位的r。

r称为计数制的基值，即“r进制”2.2.2常用数制方法一：后缀脚标数字表计数制

(dn-1dn-2……d2d1d0.d-1d-2……d-m)r其中，r为计数制的数字或汉字形式例如(365.2)10,（11011.01)2,（3460.32)8,(596.12)16方法二：利用后缀表示各种进位计数制后缀B(binary):二进制数；后缀O(octal):八进制数；后缀H(hex):十六进制数,后缀D(decimal):十进制数。例如365.2D,11011.01B,3460.32O,596.12H各种进位计数制的表示方法2.2数制及其运算2.2.3

各种数制的转换2.2.3各种数制的转换r进制数值的大小及其与十进制的转换

(F5.4)16=F×161+5×160+4×16-1=(245.25)102.2.3各种数制的转换(753.37)8

=

753.37O=7×82+5×81+3×80+3×8-1+7×8-2=(491.484375)10(753.37)16=

753.37H=7×162+5×161+3×160+3×16-1+7×16-2=(1875.2148)10(753.37)12=7×122+5×121+3×120+3×12-1+7×12-2=(1071.2986)10同一个数串，由于进位制不同其所表达的数值大小也是不同的2.2.3各种数制的转换“除基取余”2.2.3各种数制的转换(139)10=()210001011(269)10=()8415(396)10=()1618C2.2.3各种数制的转换“乘基取整”2.2.3各种数制的转换例如：(0.525)10=(0.8666)16166.4

166.4

0.525168.4

166.4

2.2.3各种数制的转换2.2.3各种数制的转换

目标进制源进制十进制二进制八进制十六进制十进制

整数部分，除基数倒取余数；小数部分，乘基数取整数二进制按权展开

三位并一位四位并一位八进制一位拆三位

以二进制为桥梁十六进制一位拆四位以二进制为桥梁

2.2数制及其运算2.2.4

二进制数的算术和逻辑运算2.2.4二进制数的算术运算运算规则简单：逢二进一；借一当二。想想十进制的算术运算口诀:1+1,1+2,1+3,…,1+9,2+1,…,确实复杂2.2.4二进制数的算术运算算术运算按位计算并考虑进位和借位；乘除法运算可转为多次加减法运算来进行；有很多快速进行加减乘除运算的算法。例1:10111B+10011B=?10111+)10011010101101010B例2:10111B－10011B=?10111-)100110010000100B2.2.4二进制数的逻辑运算“与”运算(AND):当X和Y都为真时,XANDY也为真;否则均为假。“或”运算(OR):当X和Y都为假时,XORY也为假;否则均为真。“非”运算(NOT):当X为真时,NOTX为假;当X为假时,NOTX为真。“异或”运算(XOR):当X和Y都为真或都为假时,XXORY为假;否则为真。“与”运算：两把钥匙都有才能开门“或”运算：只要有任何一把钥匙便能开门2.3数据的存储与表示2.3.2原码、反码和补码2.3.3整数的存储2.3.4实数的存储2.3数据的存储与表示2.3.5字符编码2.3.6汉字编码2.3.7多媒体数据的表示2.3数据的存储与表示2.3.2

原码、反码和补码2.3.2原码、反码和补码存储编码转换中间码运算编码原码反码补码2.3.2原码、反码和补码反码正数的反码与其原码相同；负数的反码是把除符号位外的其他位变反2.3.2原码、反码和补码正数的补码与原码相同负数的补码为该数的反码加1补码2.3数据的存储与表示2.3.3

整数的存储2.3.3整数的存储整数是没有小数部分的整型数字，可以当作小数点位置是固定的数字。存储整数一般采用定点表示法，小数点是假设的并不实际存储。例如机器字长为16位，符号位占1位，数值部分占15位，故十进制数+32767的定点数表示如下所示：2.3.3整数的存储无符号整数：不考虑符号的一连串二进制数字序列，比如一个任务的执行次数、内存单元的存储地址等，都可以用无符号整数表示。有符号整数：负数可以用有符号整数来表示。有符号整数主要有两种方法，一种是前面所讲的二进制补码记数法，另外一种方法是余码记数法。2.3数据的存储与表示2.3.4

实数的存储2.3.4实数的存储实数是带有整数部分和小数部分的数字，小数部分的存储要指明其小数点的位置。小数点在计算机中通常有两种表示方式，即定点数和浮点数。2.3.4实数的存储浮点数的表示定点数的表示2.3数据的存储与表示2.3.5

字符编码2.3.5字符编码ASCII码(美国标准信息交换码)(AmericanStandardCodeforInformationInterchange)b7b6b5b4b3b2b1b0ASCII编码位Computer01000011011011110110110101110000011101010111010001100101011100102.3数据的存储与表示2.3.6

汉字编码2.3.6汉字编码汉字编码是指将汉字转换成二进制代码的过程汉字处理过程:通过汉字外码输入,以汉字内码存储,以汉字字形码输出计算机内部由外到内由内到外2.3.6汉字编码大国标码汉字输入码汉字“大”如何输入、存储和显示的？输入“大”拼音输入：“da”字形输入：“dddd”输入计算机后，一个汉字对应唯一的编码2.3.6汉字编码机内码汉字交换码是为了在不同汉字系统之间准确无误的交换汉字信息而制定的统一编码汉字字形码在计算机中显示“大”对汉字的形状进行的编码2.3.5字符编码字型码机内码国标码输入码“大”国标码：0110100001110011机内码：11101000111100112.3数据的存储与表示2.3.7

多媒体数据的表示2.3.7多媒体数据的表示图像按编码方式可分为：位图图像：由静态的像素点组成，直接按像素点位置画出，例如BMP,JPG,GIF…矢量图像：由若干特定点的位置和相关数学公式计算动态画出，例如wmf,emf,dwg2.3.7多媒体数据的表示位图图像编码：由于位图图像的存储量大(水平像素数目×垂直像素数目×每像素位数)，通常都需要进行压缩存储，不同的压缩采用了不同的图像编码。水平像素点数垂直像素点数像素点的位数单色图像黑白(1位)灰度图像

黑白之间灰度(8位)彩色图像

16色(4位)256色(8位)24位真彩色32位真彩色2.3.7多媒体数据的表示声音2.3.7多媒体数据的表示视频数字化过程扫描采样量化编码模拟视频信号数字视频信号视频是连续的图像图像是离散的视频2.4数据的压缩2.4.1普通数据的压缩2.4.2图像的压缩2.4数据的压缩2.4.1

普通数据的压缩2.4.1普通数据的压缩数据压缩可分成两种类型：无损压缩和有损压缩无损数据压缩是对文件的数据存储方式进行优化，压缩后信息不受损失，对压缩后的数据进行还原，得到的数据与原始数据完全相同。有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息的理解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。2.4数据的压缩2.4.2

图像的压缩2.4.2图像的压缩图像数据的冗余主要表现为：图像中相邻像素间的相关性引起的空间冗余；图像序列中不同帧之间存在相关性引起的时间冗余；不同彩色平面或频谱带的相关性引起的频谱冗余。数据压缩的目的就是通过去除这些数据冗余来减少表示数据所需的比特数。2.4.2图像的压缩图像压缩可以是有损数据压缩也可以是无损数据压缩无损压缩：即从压缩后的数据可以完全恢复原来的图像，信息没有损失。有损压缩：压缩后的数据无法完全恢复原来的图像，信息有一定损失。2.5.1计算机硬件结构2.5.2处理器2.5计算机的硬件组成2.5.3存储器2.5.4输入输出设备2.5计算机硬件2.5.1

计算机硬件结构2.5.1计算机硬件结构存储器输入设备输出设备运算器控制器冯·诺依曼体系2.5.1计算机硬件结构2.5.1计算机硬件结构主板（华硕M5G）2.5.1计算机硬件结构主板与外部设备的接口2.5.1计算机硬件结构存储器输入设备输出设备运算器控制器微机的硬件由CPU、存储器、输入/输出设备构成；输入/输出设备通过I/O接口与系统相连；各部件通过总线连接。总线2.5计算机硬件2.5.2

处理器2.5.2处理器CPU是计算机的大脑，计算机的运算、控制都是由它来处理的。运算器:主要是完成各种算术运算和逻辑运算。控制器:用来协调和指挥整个计算机系统的操作。2.5.2处理器400480088086Core2P4P3P2Pentium80486803862.5.2处理器2002年9月，“龙芯”1号研制成功2005年4月,64位CPU——“龙芯“2号推出2008年，龙芯3号多核处理器推出狗剩1号MZD110我国自主研发的CPU2.5.2处理器字长：64位机，一次能处理8个字节CPU主频：工作频率或时钟频率。主频的高低直接影响CPU的运算速度CPU外频：指CPU与周边设备进行数据传输的频率。在正常情况下，CPU总线频率与内存频率相同，两者之间数据交换速度跟着提高。前端总线频率：

简称FSB，是CPU和外界交换数据的最主要通道，因此前端总线的数据传输能力对计算机整体性能作用很大。CPU的主要性能指标2.5计算机硬件2.5.3

存储器2.5.3存储器计算机存储器的三级存储结构存储器是计算机的记忆装置。RAMROM硬盘等Cache内存储器外存储器高速缓存2.5.3存储器、半导体存储器、磁存储器、光存储器2.5.3存储器按工作方式随机读写、只读、顺序读写、直接存取按信息保存易失性(挥发性)、非易失性(非挥发性)按系统中的地位主存(内存)、辅存(外存)、高速缓存(Cache)2.5.3存储器主存储器简称主存或内存。内存是CPU能够直接访问的存储器，所有的程序和数据只有被装入内存才能被执行和处理。2.5.3存储器随机读写存储器（RAM）SRAM、DRAM只读存储器（ROM）PROM、EPROM、EEPROM、快闪存储器外存储器除计算机内存及缓存以外的存储器，CPU不能直接访问的存储器硬盘存储器光盘存储器软盘存储器

移动存储器外存储器磁盘结构及原理硬盘容量=硬盘面数×每面磁道数×每磁道扇区数×每扇区字节数2.5计算机硬件2.5.4

输入输出设备2.5.4输入设备2.5.4输出设备3D打印快速成型技术中的一种。他是一种以数字模型为基础，运用粉末状金属或塑料等可粘合材料，通过逐层打印的方式来构造物体的技术。计算机硬件编码0和1二进制进制数计算机采用二进制不同进制数之间的转换编码数值编码、字符编码、汉字编码、多媒体数据表示总结第3章计算机软件基础什么是虚拟化?

为什么要使用？如何让虚拟机跑得更快？花点时间掌握，受益无穷！3.2.4虚拟化技术3.2.4虚拟化技术什么是虚拟化？本质是虚拟的、模拟的通过软件技术模拟一个“真实的”计算机的运行环境效果上是真实的对运行在这种环境中的软件而言，其看到的东西和真的没有什么两样关键是要实践最初使用时可能半信半疑，用多了就会习惯并喜欢3.2.4虚拟化技术什么是虚拟机？通过虚拟机软件“虚拟的”计算机，完全就像真正的计算机那样工作虚拟机的部件与工作过程有主板、网卡、显卡、内存、硬盘、光驱、USB等所有的硬件，有“电源”开关有与真实计算机一样的BIOS设置和启动过程需要安装操作系统和应用软件虚拟机实例：一个虚拟机的硬件配置虚拟机实例：一个虚拟机的BIOS设置虚拟机实例：一个运行WinXP的虚拟机(未进入全屏显示)3.2.4虚拟化技术什么是应用程序虚拟化？为应用程序虚拟出一个“真实的”操作系统环境，让应用程序能正常地工作于其中目前比较流行的工具是Vmware的ThinApp(瘦应用)类似沙箱软件什么时候需要应用虚拟化制作绿色软件(让软件不用安装即可使用)3.2.4虚拟化技术什么是存储虚拟化？存储(通常是磁盘)是虚拟的、但效果是真实的在系统中所看到的硬盘可能并非是一个硬盘，而可能是某个硬盘的一部分或某几个硬盘的组合或部分通过软件技术和网络技术将不同位置、技术、规格的多个硬盘“虚拟”为一个或多个没有硬件特性差异、没有位置差异且容量灵活可变、速度更快、安全可靠性更高的逻辑硬盘，提供给多台计算机系统使用一般应用于数据中心，个人用户很少使用3.2.4虚拟化技术数据中心用户：使用少量性能较好的物理机虚拟出很多台虚拟机节约建设成本和运行成本(如能源消耗)，资源利用率高单台虚拟机(服务器)的性能比原来有很大提升每台虚拟机的资源(硬件配置)随时可调，整个系统的适应性更好，资源的利用率更高，应用的需求能得到更好的满足虚拟机提供的是虚拟的标准硬件，系统的迁移、备份和恢复非常方便，多个系统的复制(克隆)非常迅速检修更换物理机时，其上运行的虚拟机可在线(对外不中断运行)转移到其它物理机上运行，系统的运行更加安全可靠3.2.4虚拟化技术个人用户：在PC上虚拟出多台虚拟机(一般不同时开机运行)为了创建多种演示环境和学习，在同一计算机上方便地、互不干扰地安装并运行不同的操作系统临时需要多台计算机(联网)开展实验安装当前硬件不支持的操作系统，如Windows98、WindowsNT用于软件测试、安全测试和从事对系统有风险的工作提供干净、安全的系统环境，用于特别重要且敏感的工作用于分发复杂的应用系统用于系统安装与配置、复杂应用系统的教学与培训3.2.4虚拟化技术CPU对虚拟化的支持：让虚拟机“跑”得更快运行速度：虚拟机系统＜物理机系统若物理机较快，则虚拟机的“慢”就感觉不到较大的内存有助于虚拟机运行速度的提升专门设计的CPU有特殊的结构和指令集，能减少“虚拟”过程的开销，让虚拟机的性能与物理机接近(绝不可能相等)现今的Intel和AMD的CPU均提供对虚拟化的支持使用时应检查BIOS设置里相应的选项是否已打开什么是命令行？为什么要使用？怎么用？组合的命令：批处理输入、输出重定向3.4操作系统的命令行操作3.4.1命令行普通用户使用计算机操作系统的两种形式图形用户界面（GraphicalUserInterface，简称GUI）命令行界面（CommandLineInterface，简称CLI）GUI：一般用户的首选，推广计算机应用的基础简单易学，不用掌握相应的命令及命令语法操作效率相对低下，需要耗费较多的系统资源GUI软件设计较繁杂，不可能将所有的操作都做在“菜单”或窗口里，有些操作并没有以GUI的形式提供3.4.1命令行CLI：高级用户提高操作效率、实现管理自动化的钥匙是图形用户界面得到普及之前使用最为广泛的用户界面不支持鼠标，通过键盘输入指令，以文本字符形式显示结果也称字符用户界面（CUI，CharacterUserInterface）操作效率和准确度高、能灵活丰富地表达要进行的操作，可以方便地完成许多在图形界面中很繁琐的操作能实现操作维护的自动化、能远程执行、快速高效地完成Windows不擅长或无法完成的工作CLI耗费的系统资源很少，软件设计较容易实现需要记住用英文书写的操作命令及其功能，理解复杂命令的选项的含义，操作不像GUI那么直观、易懂CLI还在不断被加强和发展，如Windows的PowerShell3.4.1命令行学习CLI的意义提高操作效率和准确率更好地管理和维护计算机，特别是实现这些操作的自动化远程诊断和处理计算机故障为以后使用其他类似系统和设备打下基础，如linux克服畏难情绪——对于以后要学习程序设计的用户，命令行相当于非常简单的语句3.4.1命令行进入命令行界面CLI的提供(实现)者：Cmd.exe点击“开始”菜单的“运行…”或“搜索程序和文件”，键入cmd点击“开始”菜单中的“所有程序→附件→命令提示符”退出命令行界面：输入命令Exit或直接关闭命令提示符窗口3.4.1命令行什么是命令？命令如何执行？功能如何体现？命令就是指令，通常表现了一个英文单词跟上若干参数，如DirD:\执行命令就是执行代表该命令的程序，用户发布命令其实是让操作系统(计算机)去执行代表该命令的程序命令的功能和意义完全取决于代表该命令的程序，若偷换掉相应的程序，则命令的结果肯定不是预期要执行这些程序，还得先将它们调入内存问题是：这些程序在哪里、文件名是什么？？？3.4.1命令行内部命令与外部命令内部命令是Cmd.exe本身实现的功能相应的程序包含在Cmd.exe中，已随其调入内存，直接执行常用的内部命令有：Dir、Cd、Copy、Md、Rd、Del、Type功能通常比较简单(程序短小)、使用频率高外部命令对应的程序以文件形式存储在外存(磁盘、U盘等)也称可执行文件，文件扩展名为.exe、.com、.bat和.cmd常用的外部命令：Fc、Find、Move、Format狭义的外部命令与广义的外部命令内部与外部命令无绝对界限，是发展变化的，一般不需区分3.4.1命令行常用的命令正确的学习方法：会使用系统帮助在“帮助和支持”窗口中输入“命令行参考”进行搜索输入命令Help输入每个命令并跟上“/?”或者使用“Help命令名”掌握以下操作技巧，提高操作效率在命令行上前后翻阅、编辑已输入过的命令“当前驱动器”和“当前目录”的灵活使用，通配符的使用，文件名中有空格时的处理办法使用TAB键自动、快速、准确输入文件名3.4.1命令行批处理批处理的简单理解：一批先后执行的命令批处理文件：用来存放这批命令的文件，为文本文件，扩展名为.cmd或.bat，可用记事本进行编辑批处理文件的执行方法批处理的应用：什么时候需要使用？有何收益？提高操作效率和准确率快速、完整地执行经常要进行的操作对计算机进行自动化的管理与维护3.4.1命令行输入、输出重定向输入重定向的使用<举例、操作演示输出重定向的使用>>>举例、操作演示管道的含义和使用|举例、操作演示什么时候需要使用重定向？大学计算机基础第3版姓名：时间：第三章计算机软件基础目录

3.1计算机软件概述3.2操作系统概述3.3操作系统的组成3.4操作系统的命令行操作123453.5办公软件3.1计算机软件概述3.1

计算机软件概述3.1计算机软件概述建立在硬件之上的程序、数据及相应文档的集合，是计算机硬件与用户之间的应用接口。系统软件应用软件支撑软件3.1计算机软件概述系统软件（systemsoftware）是指控制和协调计算机及外部设备，支持应用软件开发和运行的系统，是无需用户干预的各种程序的集合，主要功能是调度，监控和维护计算机系统；负责管理计算机系统中各种独立的硬件，使得它们可以协调工作。常见的系统软件：操作系统、语言处理程序和数据库管理系统等各种程序。3.1计算机软件概述应用软件（applicationsoftware）是指为满足用户不同领域、不同问题的应用需求而提供的专用软件。可分为用户程序和应用软件包两类。办公软件——微软Office

图像处理软件——Adobe的Photoshop

媒体播放器软件——WindowsMediaPlayer3.1计算机软件概述支撑软件（supportsoftware）是指支撑各种软件的开发与维护的软件，又称为软件开发环境。它主要包括中间件、各种接口软件和工具软件。IBM公司的WebSphere、微软公司的Studio.NET等。3.2.1操作系统的概念3.2.2操作系统的发展3.2操作系统概述3.2.4常见的操作系统3.2.3虚拟化技术3.2.5移动操作系统3.2.1操作系统概念操作系统：计算机系统中直接控制和管理各种软硬件资源，以方便用户充分而有效地利用这些资源的程序的集合。应用程序操作系统硬件管理和调配资源，组织计算机高效工作管理提供用户与计算机的交互接口服务3.2.2操作系统的发展并行操作系统分时操作系统实时操作系统批处理操作系统分布式操作系统3.2.3虚拟化技术虚拟化技术（VirtualizationTechnology）是指通过软件技术模拟一个“真实的”计算机的运行环境：对制造这种环境的软件设计者而言，这种环境是虚拟的；对使用这种环境的用户而言，感觉这是不可思议的、非常神奇而且最初使用时是半信半疑的；对运行在这种环境中的软件而言，其看到的东西和真的没有什么两样。3.2.3虚拟化技术虚拟机（VirtualMachine）就是“虚拟的”计算机，通过虚拟机软件，可以在一台物理计算机上模拟出一台或多台虚拟的计算机。3.2.4常见的操作系统DOSWindowsUNIXLinuxMacOS3.2.5移动操作系统移动操作系统（简称MobileOS）是指在移动设备上运作的操作系统。常见的移动操作系统：诺基亚的Symbian、Maemo和MeeGo；谷歌的Android；苹果的iOS；RIM的BlackBerryOS，微软的WindowsMobile（Phone）等，它们之间的应用软件往往互不兼容。3.3.1进程管理3.3.2存储器管理3.3操作系统的组成3.3.4设备管理3.3.3文件管理3.3.5用户界面3.3操作系统的组成操作系统进程管理存储管理文件管理设备管理用户接口CPU内存外存外设用户对计算机系统中的软硬件资源进行管理和控制；合理组织计算机的工作流程；为用户提供一个使用计算机的接口和界面3.3.1进程管理I1C1P1C2C3输入设备处理机输出设备I2I3P2P3程序1程序2程序3t1t2t3t4t5t6t7t8t9顺序执行的程序3.3.1进程管理并发执行的程序I1C1P1C2输入设备处理机输出设备I2I3P2P3程序1程序2程序3t1t2t3t4t5C33.3.1进程管理进程就绪态运行态等待态事件发生等待事件时间片用完进程调度3.3.2

存储器管理存储器管理主要负责对内存的合理分配和回收，以及内、外存之间数据的交换等，避免“内存不足”引起的程序不能执行的错误。3.3.2

存储管理分区调度（partitionedstoragemanagement）技术是由内存管理器预先把可分配的内存空间分割成若干个连续区域，每个区域的大小可以相同，也可以不同。每个程序完全载入内存，并占用连续存储空间。每个分区保存一个程序，CPU交替为各个程序服务，从而提高了CPU的使用效率。3.3.2存储管理分页调度（Pagingmanagement）将内存分成大小相等若干部分，称为(物理)块或帧。程序被分为大小相等的部分称为页（page）。页和帧的大小通常是相同的。在为进程分配内存时，将进程中的若干个页分别装入到多个连续或不连续的物理块中。3.3.2

存储管理请求分页调度（Demandpaging）是指程序被分为不同的页，不需要把所有程序页一次全部载入内存，可以部分依次载入内存运行，然后一个页被另一个页所替代。请求分段调度（Demandstaging）是指程序将按照程序员的观点划分成段，例如按模块（函数或子程序）划分，即一个独立的模块被划分为一个段。这些模块被载入内存执行，然后被其他模块所替代。3.3.2

存储管理虚拟存储（VirtualMemory）是为弥补内存不足而采用的一种内存和外存交换的技术，即程序在运行过程中一部分存在内存，另一部分存在外存，根据程序运行需要，请求分页调度、请求分段调度，或请求分页和分段调度调入要使用的内容，置换出不再使用或暂不使用的内容。3.3.3

文件管理计算机系统中的程序和数据，都是以文件形式保存在外存空间的，称为软件资源或信息资源，因此信息管理通常被称为文件管理。文件管理负责文件的存取和对文件库进行管理，主要任务为：管理文件目录，为文件分配存储空间，执行用户发出的文件操作命令。3.3.3

文件管理文件的结构指文件的组织形式，任何文件都存在两种形式的结构：逻辑结构和物理结构，用户可见的是文件的逻辑结构，系统实现的是文件的物理结构。逻辑结构无结构的流式文件有结构的记录文件定长记录变长记录物理结构顺序文件索引文件链接文件3.3.3

文件管理文件系统采用“目录”结构管理文件。计算机通过查询目录来实现对文件的“按名存取”。3.3.3

文件管理系统对文件的保护常采用存取控制方式来实现，所谓存取控制就是对不同用户规定不同的文件访问权限，以防止文件被非法访问。存取控制矩阵口令方式密码方式3.3.4设备管理设备管理（DeviceManagement）主要是指对输入／输出（I／O）设备访问的管理。设备驱动程序CPU、内存设备I/O接口3.4.1命令行3.4.2批处理3.4操作系统的命令行操作3.4.3输入、输出重定向3.5.1字处理3.5.2电子表格3.5办公软件3.5.3演示文稿3.5.1字处理长文档排版图文混排表格排版文档排版文档排版1.字符排版主要是对文字进行字体、字号、字形、字符的加粗、字符颜色、上标或下标、倾斜或下划线，字间距等格式进行设置2.段落排版包括对齐方式、行间距、项目符号和编号、段落的缩进量、底纹等文档排版3.页面设置以整个文档或文档中的整节内容作为操作单位，用于规范文档内容在纸张布局中的格式编排，对整个文档的外观进行设置。文档排版表格排版1.插入表格以整个文档或文档中的整节内容作为操作单位，用于规范文档内容在纸张布局中的格式编排，对整个文档的外观进行设置。规则表格表格排版2.表格布局和设计行列插入和删除合并和拆分单元格调整行高和列宽设置单元格中文本的对齐方式边框线设置底纹设置图文混排右图的电影节海报中，插入的椭圆形状作为海报背景被设置为“衬于文字下方”插入的图片和标题艺术字设置为“浮于文字上方”长文档排版1.样式（Style）是指将若干条格式编排命令组成一个组，然后给这个组起一个新的名字，这个新名字可以当作格式编排命令来使用。样式分为Word内置样式和用户自定义样式，用户可以通过如右图所示的对话框对其进行修改，图为样式名称为“标题2”的格式组。长文档排版2.模板（Formwork）以.dotx为扩展名的文件，可以认为它是一个框架或一种样式。新建文件时，可选择一种本机模板，只要填入具体内容或修改其中的某些内容，或者利用所提供的样式排版文档，就可以得到与某一类文档格式相同的文档。用户很容易在已有模板的基础上，创建一个新的模板。Word2010新建模板长文档排版不同的标题和正文的样式一旦设置好，就可以在长文档的不同章节和位置进行快速的相同格式化操作，同时将多级列表和样式链接起来，可以在进行格式化的同时，实现标题的自动编号，如图。长文档排版3.题注管理为了较好的管理插图和表格，可以对插入对象设置题注。题注包括标签、编号和文字，其中编号可以包含章节号。长文档排版交叉引用在正文引用题注的位置，使用“交叉引用”将自动在文档中插入引用内容，一旦题注有改变，文档中的交叉引用内容也会随之变化。长文档排版4.页眉页脚在长文档中设置的页眉和页脚通常都有一些特别的要求：每一章节奇偶页页眉不同封面不显示页码目录和正文页码独立编号基于上面的要求，在进行页面和页脚设置时，需要考虑将文档分为不同的节，不同的节可以使用不同的页眉和页脚设置。长文档排版5.建立目录在段落设置中有一个格式属性为大纲级别，大纲级别可以很好的对应不同级别的标题和正文。在正确设置了文档各段落的大纲级别后，可以手动或自动建立文档目录，建立后的目录支持自动更新，可以满足文档后期编辑和修改的需要。一级标题二级标题3.5.2电子表格图表数据管理公式和函数单元格及地址工作簿与工作表1工作簿和工作表工作簿MicrosoftExcel2010的电子表格文件称为工作簿，扩展名为.xlsx工作簿就像多页表格的账本，每一个工作簿可以包含多张工作表工作表工作表是电子表格软件的工作平台，用于输入和处理数据工作表是由若干行和列构成的一个电子表格。表格的行号用1、2、3、……等自然数表示，列标用A、B、C、……等字符表示。系统默认的工作表为3个，工作表的默认名称分别为sheet1、sheet2、sheet3工作表2单元格与单元格地址在工作表中，行和列构成了单元格，每个工作表最多约有100万*1.6万个单元格。单元格的地址由列标和行号组成，例如J4表示第4行第J列的单元格。单元格地址有三种表示：相对地址是由列标和行号组成，如B5、B1:D5。公式中引用了相对地址，公式将随地址而变化。绝对地址是在列标和行号前分别加上$符号，如$B$5、$B$1:$D$5。如果公式中引用了绝对地址，绝对地址固定不变，即不随地址变化。混合地址是在列标或行号前加上$符号，如$B5、D$5。若行设为绝对地址，则行地址不变，若列设为绝对地址，则列地址不变。3公式类型优先级运算符说明算术运算符3-负数（如

–1）%百分比^乘方*和

/乘和除+和

–加和减文本运算符2&连接两个文本字符串常见的运算符=E4*0.3+F4*0.2+G4*0.53函数Excel提供了常用、财务、逻辑、文本、日期和时间、查找与引用、数学和三角、统计等多种类别的函数，函数由函数名和括号内的自变量组成。IF(logical_test,value_if_true,value_if_false)IF(J4>=90,“优秀”,“”)加入良好判断IF(J4>=90,“优秀”,IF(J4>=80,“良好”,“”))加入合格判断加入不合格判断…常用函数求和函数：格式为SUM（计算区域求平均值函数：格式为AVERAGE（计算区域）求个数函数：格式为COUNT（计算区域）求最大值函数：格式为MAX(计算区域)求最小值函数：格式为MIN(计算区域)四舍五入函数：格式为ROUND（单元格，保留小数位数），是对指定单元格中的数值按照要求保留位数，进行四舍五入。排位函数：格式为RANK(查找值，参照区域)，功能是返回查找值在参照区域中的排位。4数据管理（1）排序将表格中数据以递增、递减或自定义序列的方式进行有序的显示。Excel支持按多个关键字排序。以“班级”为主关键字，“总成绩”为次要关键字进行的排序。排序的结果为，班级按照“一班、二班、三班”的顺序排列，相同班的学生记录按总成绩降序排列。4数据管理（2）筛选数据筛选是把符合条件的数据行显示在工作表内，隐藏那些不希望显示的行和不符合条件的数据。若筛选列为数值类型数据，可以设置数值满足的区域条件，如设置筛选条件为“60≤平时成绩＜90”若筛选列为文本类型数据，通常使用“开头是”、“包含”和“结尾是”等条件4数据管理（3）分类汇总分类汇总是将已排序的字段作为分类字段，选择汇总项进行数据的统计、求和等操作。4数据管理（3）数据透视表可以快速合并和比较大量数据，旋转其行和列可以看到源数据的不同汇总，而且可以显示感兴趣字段的明细数据5图表选择图表类型选择数据添加序列选择序列值编辑轴标签建立图表步骤设置样式5图表图表类型特性应用场景图表实例饼图反映部分占整体的构成比例收支表中各项支出比例产品的市场份额柱形图

各项之间的比较

一段时间内的数据变化

学生成绩的比较

一年中多个月份的销售额变化条形图反映不同项目之间的比较适合分类轴文字较多的项目曲线图反映随时间变化的趋势一年中多个月份的销售额变化散点图反映相关性或分布关系体重与身高之间的关系3.5.3演示文稿演示文稿设计原则演示文稿的制作PowerPoint2010演示文稿的制作（1）创建一个演示文稿。（2）选择一个合适的版式。（3）将确定好的幻灯片内容（文字、图形、图像、表格等）添加到幻灯片中（4）外观设置、应用主题、设置背景、编辑幻灯片母版（5）动画和超链接设置（6）演示文稿的放映和排练计时演示文稿的设计原则（1）设计明确的导航系统。（2）主体风格与视觉美感。（3）内容组织的层次感。（4）内容展现的形象化。（5）内容展现的动态感。（6）演示文稿的规整感。演示文稿电子表格计算机操作系统字处理操作系统操作系统的概念操作系统的管理功能办公软件字处理：图文混排、长文档电子表格：公式函数、数据管理、图表演示文稿总结第4章算法基础目录

4.1算法的基本概念4.2算法的三种结构4.3算法的表示4.4算法设计基本方法4.5算法的评价4.1算法的基本概念4.1.1算法的起源《周髀算经》《九章算术》最早四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法（简称埃氏筛），线性方程组求解第一个算法欧几里得算法（辗转相除法）求两个正整数A和B的最大公约数：Step1:比较A和B两个数，将A设置为较大的数，B为较小的数；Step2:A除以B，得到余数R；Step3:

如果R等于0，则最大公约数就是B，否则将B赋值给A，R赋值给B，重复Step2、Step3。4.1算法的基本概念4.1.2算法的定义和特性为解决问题采用的方法和步骤。算法是一组明确步骤的有序集合，它产生结果并在有限时间内终止。算法特性①有穷性：一个算法必须在执行有穷步之后结束。②确定性：算法的每一步骤都必须是确切定义的。③输入：一个算法有0个、1个或多个输入。④输出：一个算法必须有1个或多个输出值。⑤可行性：算法的每一步操作都应该是可执行的。4.2算法的三种结构1.顺序结构

按照顺序从上向下依次执行A和B，A和B代表算法的步骤。2.选择结构根据给定的条件判断选择哪一条分支，执行相应的步骤。3.循环结构在给定条件成立时，反复执行某些步骤，直到条件不成立为止。AAA4.3算法的表示4.3.1自然语言自然语言（NaturalLanguage）人们日常使用的语言。【案例4.1】求任意3个正整数a、b、c中的最大者。用自然语言可将算法表示如下：Step1：输入3个正整数a，b，c。Step2：若a大于b，则将a放到max中，否则将b放到max中。Step3：若c大于max，则将c放到max中。Step4：输出max。4.3算法的表示4.3.2流程图常用传统流程图符号求任意3个正整数a、b、c中的最大者的流程图4.3算法的表示4.2.3伪代码伪代码（Pseudo-code）又称程序设计语言PDL，是用介于自然语言和计算机语言之间的文字和符号来描述算法。reada,b,cifa>b

a→maxelse

b→maxifc>max

c→maxprintmax4.3算法的表示4.2.4程序设计语言用程序设计语言（ProgrammingLanguage）表示算法就是用计算机高级语言编写程序，程序是可以在计算机上经过编译、连接、运行出结果的算法表示。intmax(inta,intb,intc) { intmax;

if(a>b) max=a; else max=b; if(c>max) max=c; returnmax;}

intmain(void) { inta,b,c,Imax;

scanf("%d%d%d",&a,&b,&c); Imax=max(a,b,c); printf("max=%d",Imax);}4.3算法设计基本方法4.3.1求和【案例4.2】计算1~100的和。YN开始0=>sum1=>kk≤100sum+k=>sumk+1=>k结束思考1：如何计算m~n之间的偶数或奇数之和。思考2：如何计算下式：4.3算法设计基本方法4.3.2累乘【案例4.3】计算10！。思考1：如何计算

的流程图。思考2：如何计算下式：4.3算法设计基本方法4.3.3穷举【案例4.4】百钱买百鸡。我国古代的《张丘建算经》中有一个著名的百鸡问题：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？假设鸡翁、鸡母、鸡雏分别为a,b,c只，由题意可得如下两个方程：a+b+c=100

（1）5a+3b+c/3=100

（2）采用穷举法，依次对a,b,c取值范围内的各数一一试探，找出满足方程（1）和（2）的组合。流程图参见教材4.9。4.3算法设计基本方法4.3.4迭代【案例4.5】猴子吃桃问题。一只猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求猴子第一天共摘了多少个桃子？迭代法又称递推法，它是从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。4.3算法设计基本方法4.3.4迭代素数是指只能被1和它自己整除的数。【案例4.6】给定一个数n，判断n是不是素数。可以证明，只需依次用2~

或2~之间的各数去除n就可说明n是不是素数。4.3算法设计基本方法4.3.5递归递归是把一个复杂的问题逐层分解为最简单问题，再由最简单问题逐层回代，直到求出问题的解。【案例4.6】年龄问题。有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人的岁数，他说比第3个人大2岁。问第3个人的岁数，他说比第2个人大2岁。问第2个人，他说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大？4.3算法设计基本方法4.3.5递归（续）4.3算法设计基本方法【案例4.7】Fibonacci数列。“兔子繁殖问题”：假定一对小兔子一个月就可以长成大兔子（一雄一雌），而一对大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，到年底时将有多少对兔子?

（假设兔子没有死亡而且严格按照上述规律长大与繁殖）月兔1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合计1123581321345589144兔子繁殖的结果4.3.5递归（续）4.3算法设计基本方法假设第N个月的兔子数目是F(N)，可以得到如下公式：该公式递归地定义了Fibonacci数列。4.3.5递归（续）4.3算法设计基本方法【案例4.8】给2个变量a和b分别输入50和10，然后将大数50存放在b中，小数10存放在a中。4.3.6两个变量值的交换4.3算法设计基本方法1．顺序查找4.3.7查找【案例4.9】在给定的10个数{23，45，62，12，33，87，90，55，13，79}组成的列表中查找数12。4.3算法设计基本方法2．二分查找4.3.7查找查找是从列表的中间位置开始，如果该位置上的数据和目标数据（待查找的数据）相等，则查找成功；若目标数据大于中间位置的数据，则在查找表的后半部分继续进行二分查找，否则在前半部分进行二分查找。即先确定目标数据所在区域，然后逐步缩小区域，直到查找成功或失败为止。【案例4.10】在给定的10个数{8，12，35，46，55，67，78，82，90，96}的列表中查找数35。4.3算法设计基本方法4.3.7查找【案例4.10】在给定的10个数{8，12，35，46，55，67，78，82，90，96}的列表中查找数35。4.3算法设计基本方法4.3.8排序1．冒泡排序将待排序的数据依次进行相邻两个数据的比较，如不符合顺序要求（由大到小或由小到大）就立即交换。这样值大（或小）的就会像冒气泡一样逐步升起。按此方法对数据经过一轮比较移位后称为一趟冒泡，第1趟冒泡的效果是将数据值最大（或最小）的元素交换到了最后的位置，即该数据排序的最终位置。n个数据最多需要进行n

1趟冒泡。4.3算法设计基本方法4.3.8排序2．选择排序从待排序的n个数据的列表（R1,R2,R3,...,Rn）中选出最小的数（按升序）或最大的数（按降序），将它与R1交换；然后再从余下的n-1个数中选出次小（或次小）的元素与R2进行交换；第i趟排序时（R1,R2,...,Ri-1）已排好序，在当前无序的（Ri,...,Rn）中再选出最小（或最大）的元素，将它与Ri元素交换，使（R1,R2,...,Ri）成为有序。依此类推，经过n-1趟排序后，全部数据就递增（或递减）有序了。【案例4.12】用选择排序法将N（N=7）个无序数据（9,5,7,2,4,8,3）其按升序排列。4.3算法设计基本方法4.3.8排序3．插入排序把n个待排序的数据分为两部分：{R1，...，Ri

1}为已排好序的有序表，{Ri，Ri+1，...，Rn}为未排序的无序表（初始时，令i=2）。然后，把未排序部分的第1个数据Ri依次与R1，...，Ri-1比较，并插入到有序表的适当位置上，使得｛R1，...，Ri｝变为一个新的有序表，直到未排序表中的数据元素全部插入到有序表中。【案例4.13】用插入排序法将N（N=5）个无序数据（30,16,25,17,12）其按升序排列。初始数据[30]16251712第1步

[1630]251712第2步

[162530]1712第3步

[16172530]12第4步

[1216172530]4.4算法的评价1．时间复杂度

算法的时间复杂度（TimeComplexity）是指算法执行所需要的计算工作量。按数量级递增排列，常见的时间复杂度有：常数阶O(1)，对数阶O(log2n)，线性阶O(n)等，线性对数阶O(nlog2n)，平方阶O(n2)，立方阶O(n3)，...，k次方阶O(nk)，指数阶O(2n)。2．空间复杂度

一个算法的空间复杂度（SpaceComplexity）是指算法运行所需的内存大小，包括输入数据所占空间、程序本身所占空间以及算法执行过程中所需要的辅助空间，其中辅助空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。本章小结算法是为解决问题采用的方法和步骤，它具有5个重要特性：有穷性、确定性、输入、输出、可行性。算法有三种结构：顺序、选择（分支）、循环。顺序结构按照顺序从上向下依次执行算法步骤；选择结构根据给定的条件判断选择执行相应的步骤；循环结构在给定条件成立时，反复执行某些算法步骤。算法的表示有多种方法，常用的有：自然语言、流程图、伪代码、程序设计语言等。求和是对数相加时用到的一种基本方法。累乘对一系列数的求乘积的方法。穷举法是依题目的部分条件确定答案的大致范围，在此范围内对所有可能的情况逐一验证，直到全部情况验证完。本章小结迭代法是从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。递归是把一个复杂的问题逐层分解为最简单问题，再由最简单问题逐层回代，直到求出问题的解。顺序查找和二分查找是常用的查找