《计算机导论》复习

《计算机导论》复习

•考试范围：1〜8章

•考试题型：

-选择、填空、判断、问答、计算

・考试时带钢笔或珠笔，不准使用计算

o

1

第1章概述

•1936年，英国科学家阿兰・图灵提出图灵机模

型：把人在计算时所做的工作分解成简单的机

械化动作交给机器去执行，经过足够的时间和

有限次机械步骤求得解答。理论上可以计算任

何可计算函数。

•1946年2月由宾夕法尼亚大学研制成功的ENIAC

是第一台电子数字计算机。

2

•美籍匈牙利数学家冯•诺依曼提出现代计

算机基本结构——“冯•诺依曼计算机”：

-计算机应由运算器、控制器、存储器、

输入设备和输出设备五大部件组成；

-应采用二进制简化机器的电路设计；

-采用“存储程序”以便计算机能保存指令

和数据以及能够自动依次执行指令。

3

・第一代计算机：电子管；

・第二代计算机：晶体管；

・第三代计算机：集成电路；

・第四代计算机：大规模/超大集成电路

计算硬件发展的新趋势——并行计算、连网

4

・第一代软件：机器语言，汇编语言；

•第二代软件：高级语言；

•第三代软件：操作系统；

・第四代软件：结构化程序设计方法，UNIX,C,

DOS,鼠标+图形界面；

・第五代软件：面向对象程序设计，Windows,

Java,WWW;

5

第2章计算机基础知识

•数制：按进位原则进行计数）逢R进一。

基数：数制中所需的数字字符个数。R进制的基数=R

位权：是一个与数字位置有关的常数，位权=即

其中n取值：以小数点为界，向左0,1,2,3……,

向右T,-2,-3……

例：（275.8）I。=2x102+7xlO^Sx100+8x

6

二进制的算术运算

加：减：乘：除：

0+0=00-0=00X0=00+0=0

0+1=10-1=10X1=004^1=0

1+0=11-0=11X0=01+0（无意义）

1+1=01-1=01X1=11+1=1

二进制的逻辑运算

与AND：或OR：非（取反）:

0A0=00V0=0

0Al=0OV1=10=1

1AO=O1VO=1

1A1=11V1=11=0

十进制整数一二进制整数］I+进制小数=二进制小数

除2取余数直到商为0；乘2取整直到小数部分为0或

由下而上排列。达到精度；由上而下排列。

0.6875

2I751k

TX2

23711........1.3750

2|180X2

2I910........0.7500

2I40X2

2L201.........1.5000

X2

2

0........1.0000

结果为：1001011结果为：0.1011

二进制数口十进制数

\____________________________________________________________________________________7

位权相加法・,各位数码乘位权，再相加。

321

例：(1011-1)2=1X2+OX2+1X2+1X2°+1X2-1

=8+0+2+1+0.5=(11,5)10

「一…出门整数部分从右向左，小数部分从左向右，

二进制数每3位二进制一组，变为1位八进制。

、1米不足3位时分别在最左端和最右端补。凑够3位。

［八进制效J例:(1100101001011.1101)2=(14513.64)8

®整数部分从右向左，小数部分从左向右，

每4位二进制一组，变为1位十六进制。

不足4位时分别在最左端和最右端补0凑够4位。

例:(11010111101.1010001)2=(6BD.A2)16

位(bit)：计算机存储数据的最小单位(0、1)

字节(Byte)：处理数据的基本单位(8bit/Byte)

一个字(Word)由2、4或8个字节组成。

一个字的每一位由右至左编号。如32位字长:

31302524232270

0100011001001；-00110111

10

第三章数据表示法

•模拟信号和数字信号

•无符号数和有符号数

•符号位:二进制数的最高位表示“正”、

0为正，1为负。

11

为了运算方便，机器数采用原码、补码表示。

原码:正号为0,负号为1,数值部分为二进制绝

对值。

补码正数的补码和原码相同；负数的补码是将

其原码除符号位外各位取反，末位加1。

+5的原码、未卜码者口是00000101

-5

12

小数点位置固定的数称为定点数。

定点整数：小数点固定在数值部分最右端。

定点小数：小数点固定在数值部分最左端。

小数点位置不固定的数称为浮点数，分为阶码

(指数)和尾数两部分。

例：将十进制数+55以浮点数格式存放。

6

(55)10二(110111)2=0.110111*2

31302524232250

000001100

阶码阶码部分尾数尾数部分

符号位符号位

西文字符的编码:

ASCII4马(AmericanStandardCodeforInformationInterchange)

♦128个常用字符，用7位二进制编码，占一个字节，最高位0。

♦其中，控制字符：。〜32,127；普通字符：94个。

例如：“a”字符的编码为1100001,对应的十进制数是97；

字符对应的十六进制对应的十进制

换行OAH10

回车ODH13

空格20H32

O〜，9'30H-39H48〜57

*〜Z41H〜5AH65〜90

'a'〜卬61H〜7AH97〜122

14

和汉字有关的编码：

(1)汉字输入码：操作人员通过键盘输入的汉字编码。

(2)汉字国标码(GB2312—80)

每个汉字占两个字节的编码。所有汉字分区，每个

区94个汉字。区号和位号各加32构成国标码。

(3)机内码

计算机内部存储和加工汉字所用的编码。

每个汉字的国标码的每个字节最高位改为1,即成机内码。

汉字国标码汉字机内码

中8680(0101011001010000)2010101100010000)2

华5942(0011101100101010)20)111011^101010)2

(4)汉字字形码：点阵(汉字字形点阵的代码)

15

差错校验码一奇偶校验码

•为一个字节补充1bit（校验位），设置校验位的值

为。或1，使字节中的8bit和该校验位含有1值的个数

为奇数（奇校验）或偶数（偶校验）。

数据前校验编码乂禺校验编码

00000000100000000o'00000000

01010100901010100101010100

可

16

文本压缩方法:

关键字编码，

关键字编码是用单个字符代替常用单词或前后缀。

如：the—~and->+that->$

行程长度编码

在一些数据流中，某个字符可能连续地反复出现。

因此，重复字符序列被替换为：

标志字符+该字符+出现次数

17

文本压缩方法:

哈夫曼编码

1■计算信源符号出现的概率。p-0.125,a-0.25,

s-0.375,g-0,125,e-0,125

2.概率最小的两个符号概率相加合成一个概率。

3,将合成概率看成一个新组合符号概率，重复上述

做法，直到最后只剩下两个符号概率为止。

4.反过来逐步向前编码，每一步有两个分支各赋予

一个二进制码，可以对概率大的编码为1、,一,

18

■音频信息的数字化：

■捕捉声音时用固定的时间间隔对声波进行采样

（离散化处理），例如44.1kHz;（采样）

■将每个采样点的振幅值转换为二进制数值，例

如用8位或16位二进制表示。（量化）

■把量化后的信号数据编成一个二进制码组输出。

（编码）

•采样频率：每秒钟的采样次数。

•量化位数（采样精度）：存放采样点振幅值的二

进制位数。通常量化位数有8位、16位等。

19

■图像信息的数字化：

■用“m行xn列”个像素点来离散化一幅图像,

例如1024x768分辨率；（采样）

■将每个像素点的三基色强度转换为二进制值,

例如用8位、16位、24位、32位二进制表示。

（量化）

■数字化图像的数据量很大，所以需要采用编

码技术来压缩信息，减少数据量。（编码）

•分辨率：图像中的行数和列数，每个行与列的

交点就是一个像素。例如1024X768、。

•颜色深度：每个像素点颜色值的存储位数。

20

■视频信息的数字化：

■连续动态的视频由多帧静态图像组成。

■采样频率：每秒捕捉的画面帧数。

■采样精度：经采样后每帧所包含的颜色位

（色彩值）。如8位,32位。

■必须对海量的视频数据及其伴音进行压缩

和编码。

21

音频文件常用格式

wma,wav,mp3mid

图像文件常用格式

bmp,gif,jpgwmf

视频文件常用格式

avi,mov,mpg,dat

22

第3章计算机体系结构

•门电路：接受一个或多个输入信号，生

成一个输出信号。每种类型的门执行一

个特殊的逻辑函数。

•非门，与门，或门，异或门，与非门，

或非门等。

23

非门:

BooleanExpression逻辑框图符号真值表

与门:

BooleanExpression逻辑框图符号真值表

ABX=A*B

000

X=A*B010

100

111

24

或门:

BooleanExpression逻辑框图符号真值表

A__ABX=A+B

v0|

X=A+B__A00

011

101

111

异或门：两个输入相同时，输出是0,否则输出1。

BooleanExpression逻辑框图符号真值表

ABX=A㊉B

X=A㊉B000

011

101

110

25

与非门：让与门的结果再经过一个非门。

BooleanExpressionLogicDiagramSymbolTruthTable

ABX

AA

X=(A-B)•001

B011

101

110

或非门：让或门的结果再经过一个非门。

BooleanExpressionLogicDiagramSymbolTruthTable

AABX

X=(A+B)'001

B010

100

110

26

用晶体管构造门

否则Vout=1o极才不被接地，Vout=1o

27

“异或”逻辑表达式：X=A㊉B三A・B+A^

-28

半力口器halfadder：

计算两个数位的和并生成正确进位的电路。

A和

B㊉和二A㊉B

进位二

进位AB

&

29

全力口器fulladder：

计算两个数位的和并考虑进位输入的电路。

和二A㊉B㊉C

进位输出=AB+5人㊉田

进位输出、

30

加法器adder：8bit相加需要复制8次全加器电路。

一个bit位的进位输出将作为下一个bit位的进位输入o

最右边bit的进位输入是0,最左边bit的进位输出被

舍弃（溢出）。

Co

S3S2S1So

位加法器例子

S=A+B4

S3s2&S。=WH/i/o+8332g8o

31

5飞锁存器6飞latch)

S=0,R=1时，X=1o

R=0,S=1时，X=0o

S=1,R=1时，X保持不变。

和不能同时为。

清。端SR0

32

内存单元：存储信息的单位（字节）。内存中有大量的

内存单元。

内存单元的地址：每个内存单元都有唯一的地址。

33

•CPU的主要性能指标：

主频：CPU内核运算电路的运行频率。

CPU外频：CPU总线频率，外频提高则与内存交

换数据的速度越快。主频=外频X倍频系数。

数据总线宽度：即字长，如32位、64位。

CPU：算术和逻辑运算单元ALU、

控制器和寄存器组。

CPU可执行的一组指令称为指令集。

精简指令集和复杂指令集。一

34

、一口口

运舁肃

ALU:执行算术、逻辑运算

寄存器组：存源、中间数据

标志寄存器：保存标志信息

控制器

Be：口存放下一条指令的地址

IR：存放正执行指令的内容

译码器：区分指令执行的步骤

产生控制信号：向其它各部件发出控制信号，

保证各部件协调一致地工作

35

总线按所传输的内容分，有：

数据总线：传送数据。如：“奔腾”CPU有32条数

据线，表示每次可和内存并行交换32位二进制数。

地址总线：用于传送CPU发出的地址信息,即指明

数据总线上的数据的源地址或目的地址。地址总线的

宽度决定了CPU的最大寻址能力（即所允许的最大内

存容量）。

控制在线＞传送控制信号。

36

操作码：要完成的操作类型

操作数：操作数所在的地址或操作数本身

例：JMPM1;ADDREG1REG2

37

内存：直接与CPU交换信息的存储设备。用来存放计

算机运行期间所需的信息，如：指令、程序、文档。

外存：内存的延伸，长期存放暂时不用的数据。如

系统文件、应用程序、用户文档等。

I-----鄢态RAM

随机存储器(RAM)-

1----动态RAM(DRAM)

内存储器

住存）I-掩膜ROM

只读存信器(ROM)——PROM

।——EPROM

存储器

顺序存取存储器磁带

外存储器

（辅存）

直接存取存储器软盘、硬盘、光盘

高速缓冲存储器（Cache）

38

非vonNeumann结构：

不采用“线性的读取一执行周期”。

并行（分布式）处理

♦阵列计算机：多个处理机对不同数据同时运行

相同指令。

♦多指令流多数据流MIMD系统：多个处理机对不

同数据执行不同指令。

39

流水线技术(Pipeline)

♦将每条指令分解成多个阶段，几条指令的不同阶段

重叠运行，使控制器、运算器、存储器等同时工作。

♦如Pentium的6级流水线结构：

指令1取指译码地址生成取数执行写回

指令2取指译码地址生成取数执行写回

指令3取指译码地址生成取数执行写回

指令4取指译码地址生成取数执行写回

40

第4章操作系统

用户1用户2用户3……用户n

编译程序汇编程序文本编辑器…数据库系统

系统程序和应用程序

——操作系统-----

计算机硬件

操作系统：计算机硬件和软件资源的管理者。

41

操作系统构成：进程管理、内存管理、文件管理、

输入输出系统管理，作业管理。

操作系统主要类别：

11批处理系统

31实时系统

42

分时操作系统：

•“分时”的含义：时间片轮转，轮流占用CPU

•人机交互性好：程序的运行由用户自己操作。

•共享主机：多个用户同时使用同一台计算机。

•对每个用户而言好象独占主机。

实时操作系统：

•及时响应外部事件的请求，在规定的严格时间内完

成对该事件的处理。

­要求：及时响应、快速处理，高可靠性和安全性

•应用领域：过程控制、事务处理。

43

内存分配方案-连续内存分配

在可用内存中找到足够大的一块连续内存（如100KB）,

切出要求长度的内存（如70KB）分配，剩余内存（如

30KB）作为新空闲区留待以后分配或合并。

•首次适应（First-fit）策略

・最佳适应（Best-fit）策略

・最差适应（Worstf。策略

内存分配方案-分页式内存管理

为解决碎片问题和实现不连续分配，采用页式管理。

44

虚拟内存：

当一个用户程序要调入内存运行时，不是将该

程序的所有页面都装入内存，而是只装入部分

的页面，就可启动程序运行；

在运行的过程中，如果发现要运行的程序或要

访问数据不在内存，则向系统发出缺页中断请

求；

系统在处理这个中断时，将磁盘上相应的页面

调入内存，使得该程序能够继续运行。

45

进程是程序对某个数据集的一次执行过程。

♦:♦程序是静态概念（建立与删除）；进程是动态概念。

一个进程由三部分组成：

•进程控制块PCB,程序段，数据集

46

◎CPU调度：把CPU分配给某个就绪进程去运行。

◎不可抢占式：当前运行进程完成或阻塞或时间片

到时，才再分配处理机。

◎抢占式：将正运行进程强行撤下，处理机分配给

其它进程。例如当有一个优先权更高的进程进入就绪

队列时。

•先到先服务(FCFS,First-Come,First-Served)

•最短作业优先(SJF,Shortest-Job-First)

•轮转(RR,Round-Robin)：时间片轮转

47

文件系统和目录

文件：存储在外存上具有标识名的一组相关字

符流或记录的集合。透明存放和按名存取

文件的命名：文件名.扩展名

，布.:七

48

■OS将每个目录看成一张表，表中是该目录下所有

文件的信息。（其实目录本身也是一个文件）

■创建文件时，先在磁盘上为新文件分配一个空闲

块，然后在目录表中添加一新条目。

文件名权限建立时间文件长度第一磁盘块号盘块数其它

myOl.c1101605092268B565722

abc.exe001230000220324B356364

q123.doc110322083156342B4585715

■■■■■■■■■■■■■■■■■■■■■■■■.....................■■■■■■

xyz.txt11192210012B243411

49

从开始位置顺序读取字

符/记录，适合于磁带

访问方式

UNIX中的文件存取权限：

♦:♦用户分三类：文件主、同组用户、其他用户。

♦:♦权限有三种：读R、写W、执行X。

50

■磁盘调度：当多个进程都提出“磁盘访问请求”

时，需要对访盘请求的服务顺序进行调整，以降

低平均磁盘访问时间。

■FCFS先来先服务：按请求的次序服务。

■SSTF最短寻道时间优先：优先选择距当前磁

头位置最近的访问请求进行服务。

■SCAN扫描算法（电梯算法）：选择位于磁头移动方

向前方且距磁头位置最近的访问请求进行服务。

51

第5章网络计算

・计算机网络是一种利用通信线路和通信

设备，把分布在不同地点的多个独立的

计算机系统有机地连接起来，实现所连

接的计算机之间互相通信和资源共享的

计算机系统。

52

＞带宽：网络上数据传输的速率，单位bit/s。

，网络分类：局域网，城域网，广域网

＞拓扑结构：总线型，星型，环型

OSI网络体系结构参考模型

・应用层(AppIicationLayer)

•表示层(PresentationLayer)

•会话层(SessionLayer)

・传输层(TransportLayer)

•网络层(NetworkLayer)

•数据链路层(DataLinkLayer)

・物理层(PhysicaILayer)

53

,每段占1个字节，取值0—255

IP地址格式nnn.nnn.nnn.nnn

如202.112.0.36

A类

B类

C类

54

IP地址

3

域名

WWW.

t-t-V

主机名机构域领域国家域

DNS（域名服务器）：完成域名向IP地址的转换。

顶级域名分类：

类型名：如edu,gov,org,cn等。

区域名：如cn'uk/hk等。

55

Internet的典型应用

♦电子邮件E-MaiL文件传输FTP,远程登录

Telnet,全球信息网WWW,电子公告板BBS,

实时聊天ICQ,网络电话IPPhone

产茅—

56

第6章程序设计与算法分析

♦:♦计算机问题求解三阶段：不断反复的过程

♦:♦算法开发：得到问题的通用解决方案

♦分析问题、提出并测试算法

♦:♦算法实现：得到计算机可运行的程序

♦编码和测试程序

♦:♦维护：在实践中检验

♦实际运转、修改维护程序‘百

57

♦:♦两种程序设计方法：

4♦自顶向下方法(Top-downMethodology)

•程序设计模式：“数据结构+算法”

士在软件功能说明书中，动词是重点。

♦:♦面向对象程序设计(ObjectOriented

Programming)

♦程序设计模式：“对象+消息”

+在软件功能说明书中，名词是重点。

58

自顶向下程序设计方法

①自顶向下、逐步求精：逐层分解复杂任务，把任务

细节推延到下层模块中实现。

②模块化：每个模块完成特定的、相对简单的功能。

③流程控制结构化：程序通过顺序、分支、循环三种

基本控制结构来实现。

59

面向对象的程序设计方法

60

*继承inheritance：子类得到父类的全部属性和方法,

还可以扩充和覆盖父类的成员。

*多态polymorphism：也称重载。不同子类中同一方

法名可定义成不同代码，所以它们在收到同一消息

时做出的响应行为也不同。

*封装encapsulation：将属性和行为隐藏起来，外部

通过特定的接口访问对象成员。好处是保护成员，

修改程序时只涉及类的内部。

61

低级程序设计语言

机器语言：由二进制代码组成。能被计算机直接

理解和执行，但编程困难，可移植性差。

把机器指令中的操作码和操作数用英文助记符和

符号地址来表示，称为汇编语言。依赖于机器，

可移植性同样较差。

62

高级程序设计语言

♦编译器对整个源程序经过编译处理，产生一个与源

程序等价的目标程序；通过连接程序将目标程序和

有关的程序库组合成一个完整的可执行程序；

♦执行速度快，修改源程序后都必须重新编译。同一

种高级语言在不同CPU平台上需要不同的编译器。

编译器连接程序数据

源程序―L目标程序―L可执行程序！—,运行

.C.obj.exe结巢

63

♦解释程序对源程序进行逐句分析，若没有错误,

将该语句翻译成一个或多个机器语言指令，然后

立即执行这些指令；若解释时发现错误，则立即

停止，报错并提醒用户更正代码。

♦解释方式不生成目标程序，执行速度慢。

解释程序

高级语言

计算结果

源程序

据

64

♦Java源程序先经过编译生成Java字节码，然后由

JVM(JavaVirtualMachine,Java虚拟机)解释执行。

♦Java字节码相当于是“标准的机器语言”，速度快,

唯一，只要有相应的JV