计算机科学导论复习资料整理（精心汇编）

《计算机科学导论》课程考试重点知识考试说明：选择题（共 10小题，每小题2分，共20分、名词解释题（共5小题，每小题420、简答题（共5小题，每小题630、综合题（共5题，选做3小题。其中强化班同学必作小题10分，共30分）。

1、2、3小题，普通班同学任选 3小题作答，每一、考试范围：1~10、15章，每章都有一定量的题目。二、课后习题中的选择题全部要求。三、重点掌握的知识点：计算机操作系统:操作系统就是合理管理并控制计算机系统内软、 硬件资源并能够合理组织工作流程、方便用户使用的程序的集合。通常我们将操作系统的功能概括为两大功能：扩展的虚拟机功能、资源管理功能。其中，资源管理功能包括了处理机管理、内存管理、设备管理、文件管理四大功能。而扩展的虚拟机提供友好的人机交互以及程序级接口， 使得计算机看上去像是功扩展了的机器。结果和处理程序。为了对存储的信息进行管理，把存储器划分成存储单元，每个单元的编号称为该单元的地址。各种存储器基本上都是以 1个字节作为一个存储单元。存储器内的信息是按地址存取的，如要访问存储器中的某个信息，就必须知道它的地址。向存储器里存入信息也称为“写入”，写入新的内容将覆盖原来的内容。从存储器里取出信息也称为“读出”，信息读出后并不破坏原来存储的内容，因此信息可以重复读出，多次利用。通常把内存储器、运算器和控制器合称为计算机主机，也可以说主机是由 CPU与内存储器组成的，而主机以外的装置称为外部设备，外部设备包括输入外存储器等。

/输出设备、运算速度:计算机的运算速度是衡量计算机水平的一项主要指标，它取决于:数据进行输入、处理、输出和存储的系统，由计算机硬件系统和计算机软件系统两大部分组成。和主机的概念:通常把运算器、控制器做在一个大规模集成电路块上称中央处理器，又称CPU(CentralProcessingUnit) 。通常把内存储器、运算器和控制器合称为计算机主机，也可以说主机是由

CPU与内存储器组成的，而主机以外的装置称为外部设备，外部设备包括输入外存储器等。

/输出设备，大型软件开发和维护过程中遇到的一系列严重问题称为“软件危机”Crisis) 。

(Software信息：信息

是客观事物的属性和相互联系特性的表现，它号的组合，而将这些信息进行传输的载体可以是文字、声音、图形、图像等。输入和输出设备输入和出设备简称I/O(Input/Output)设备将程序和数据输入计算机，输出设备将计算机处理的结果

设备。用户通过输入(如数字、字母、符号和图形常用的输出设备有：显示器、打印机、绘图仪等。:系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。质量的定义有多种说法，从实际应用来说，软件质量定义如下：与所确定的功能和性能需求的一致性。与所成文的开发标准的一致性。与所有专业开发的软件所期望的隐含特性的一致性。点整数则把小数点固定在数据数值部分的右边。字长:在计算机中，用若干二进制位表示一个数或一条指令，前者称为数据字，后者称为指令字。字长的直接影响计算机的功能强弱、精度高低和速度快慢。计算机处理数据时，一次可以运算的数据长度称为一个“字” (Word)，字的长度为字长。一个字可以是一个字节(Byte，简称B)，也可以是多个字节。常用的字长有8位（bit、16位、32位、64位等。如某一类计算机的字由长度为32位，相应的计算机称为 32位机。

4个字节组成，则字的:存储器的容量反映计算机记忆信息的能力，

它常以字节为单位表计算机中的操作大多是与内存交换信息， 但内存的存取速度相对 的算术和辑运算的速度要低1～2个数量级。因此，内存的读写速度也是影响计算机运行速度的主要因素之一。为了度量信息存储容量，将 8位二进制位(8bits) 称为1个字节，字节是计算机中数据处理和存储容量的基本单位。

1024个字节称为1K字节(1KB)，1024K个字节称1兆字节(1MB)1024个字节称为1G字节(1GB)1024个字节称为1T字节(1TB)现在微型计算机主存容量大多数在兆字节以上。计算机软件。软件是指用来指挥计算机运行的各种程序的总和以及开发、 用和维护这些程序所需的技术文档。理系统、以及各种软件工具等各种软件程序组成，指挥、控制计算机硬件系统按照预定的程序运行、工作，从而达到预定的目标。应用软件是用户利用计算机软、硬件资源为解决各类应用问题而编写的软件，包括用户程序及其说明性文件资料。并发：并发通常指多个任务可以在同一个时间段内同时执行，即允许多任务在宏观上并行，微观上仍然是串行的 (对于单系统而言)。时刻同时执行。并行的。只有在多处理机系统中，任务的并行执行才是可能的。并行系统往往也可以支持任务的并发执行。:完成的，这些微指令操作是按时钟周期的节拍来“动作”的，时钟周期的微秒数反映出计算机的运算速度。有时也用时钟周期的倒数——时钟频率

(兆频)，即人们常说的主频来表示。一般说来，主频越高

(时钟周期越短)，计算机的运算速度越快。但是，主频并不能全面准确地反映计算机的运算速度，而每秒钟执行百万条指令数(MIPS)指标则能较全面准确地反映计算机的运算速度。近十年来，微计算机的主频IBMPC/XTPentium4CPU己超过1GMz并且在不断提高.网络操作系统:治，各计算机都有各自的软、硬件资源，系统的主要目的是共享网络资源、信息交换和协作。收、发双方在时间基准上保持一致，系统需要一个同步时钟，用于传输大量的信息。是任意的，字符与字符之间的间隔也是任意的，即各个字符之间是异步的。软件工程：软件工程是研究大规模程序设计的方法、工具和管理的一门工程科学，也就是运用系统的、规范的和可定量的方法来开发、运行和维护软件的系软件工程的理论、方法、技术都是建立在计算机科学的基础上，它是用管理学的原理、方法来进行软件生产管理；用工程学的观点来进行费用估算、制定进度和实施方案；用数学方法来建立软件可靠性模型以及分析各种算法和性质。软件工程是指导计算机软件开发和维护的工程学科。标，执行其功能的正确程度。一个可靠的程序应要求是正确的、完整的、一致的和健壮的。信号:信号(Signal) 是携带信息的传输介质，在通信系统中常用电信号光信号、载波信号、脉冲信号、调制信号等描述。运算器:运算器又称算术逻辑单元(Arithmetic LogicUnit是计机对数据进行加工处理的部件，它的主要功能是对二进制数进行加、减、乘、除等之下实现其功能的，运算结果由控制器发出的指令送到内存储器中。编译程序:编译程序是把高级语言程序 (源程序)作为一个整体来处理，在应用源程序执行之前，就将程序源代码“翻译”成目标代码

(机器语言)，编译后码。

(目标程序代:成，控制器是用来控制计算机各部件协调工作，并使整个处理过程有条不紊地进行。它的基本功能就是从内存中取出指令和执行指令，即控制器按程序计数器指出的指通常把运算器、控制器集成在一个大规模集成电路板上称为中央处理器，又CPU(CentralProcessingUnit) 。26．程序运行的局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。局部性原理又表现为：时间局部性和空间局部性。时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指空间局部性是指一旦程序访问了某个存储单元，则不久之后。其附近的存储单元也将被访问。另外，根据程序的局部性理论， Denning提出了工作集理论。所谓工作是指进程运行时被频繁访问的页面集合。显然我们知道只要使程序的工作集全部集中在内存中，就可以大大减少进程的缺页次数；否则会使进程在运行过程中频繁出现缺页中断，从而出现频繁的页面调入能的下降，甚至出现“抖动”。

/调出现象，造成系统性划分工作集可以按定长时间或定长页面两种方法进行划分。 当颠簸象发生时，说明系统的负荷过大，通常采用处理器均衡调度。另一种是控制缺页率，当缺页率达到上限时，则增加内存分配量；当缺页率达到下限时，就减少内存的分配量。27审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义，有时把这个工作称为静态语义分析或静态审查。28．操作系统的基本组成：现代操作系统至少由存储管理、进程管理、设备管理、文件管理以及用户接口五个部分组成。用户接口一般包含命令接口(如shell命令)和程序接口。信等多个部分。存储管理解决内存分配与回收、内存保护、地址映射、虚拟存储等问题。设备管理涉及到中断技术、 I/O硬件与I/O软件、数据传输控制技术等。文件管理要解决文件的命名、文件属性、文件操作、文件的逻辑与物理结构文件的存取方式、磁盘物理空间管理、目录、文件可靠性等问题。29n

T(n)，(Spacecomplexity)程序在计算机中运行所占用空间的大小。简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。记为， S(n)，其中，n代表求解问题的规模。时间复杂度和空间复杂度同样，引入符号“ O”来表示T(n)、S(n)与求解问题规模n之间的数量级关系。分组交换：分组交换采用存储转发的技术，把来自用户的信息暂存于存储装置中，并划分为多个一定长度的分组，每个分组前边都加上固定格式的分组标记(Lable)址转发分组。分组在各交换节点之间传送比较灵活，交换节点不必等待整个报文的其他分组到齐，而是一个分组、一个分组地转发。这样可以大大压缩节点所需的存储容量，也缩短了网路时延。另外，较短的报文分组比长的报文可大大减少差错的产生，提高了传输的可靠性。但分组交换也有缺点，分组存储转发时，会产生时延；携带控制信息会增加开销 (Overhead)；分组交换网还需要专门的管和控制机制。它把瀑布模型与专家系统结合在—起。该模型在实施过程中要建立知识库，将模型本身、软件工程知识与特定领域的知识分别存入数据库。以软件工程知识为基础的生成规则构成的专家系统与含应用领域知识规则的其他专家系统相结合，构成这一应用领域软件的开发系统。络层次结构及其协议的集合。换种说法，它是计算机网络及其部件所应能完成的各种功能的精确定义。具体的功能；层与层之间的功能有明确的界限；相邻层之间有接口标准，接口定义了低层向高层提供的操作服务； 计算机间的通信是建立在同层次之间的基础上。高性能计算机：高性能计算机的概念并无明确的定义，一般认为运算速度非常快的计算机就可以认为是高性能计算机。严格地讲，高性能计算机是一个拥有最先进的硬件、软件、网络和算法的综合概念， “高性能”的标准是随着技的发展而发展的。目标代码生成阶段的任务：目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后援寄存器的调度等。域名系统：由于 IP地址很难记忆，为了使用和记忆方便，因特网还采用了域名管理系统，简称 DNS(DomainName。域名系统与 IP地址的结构一右面，各分量之间用“.·.三级域名.二级域名.顶级域名。一个DBM的组成部分：DBM通常由四部分组成，也是 DBM要完成的功能：数据定义语言 及其翻译处理程序：定义数据库中的数据对象。数据操纵语言 及其编译(或解释)程序：实现对数据库的查询、插入删除、修改等操作。安全性、完整性，并对数据并发访问进行控制，完成数据库的故障恢复等功能。转储等功能。模块划分的原则（和 54相同）计算机的基本运行方式：计算机的基本运作方式可概括为所谓的“ IPOS循环。IPOS循环即输入(Input) 、处理(Processing) 、输出(Output) 和存储(Storage)，它反映了计算机进行数据处理的基本步骤。输入处理

)提供的数据。对数值、逻辑、字符等各种类型的数据进行操作，按指定的方式进行转换。输出将处理所产生的结果等数据由输出设备出。存储计算机可以存储程序和数据供以后使用。

(如显示器、打印机、绘图仪等 )进行输者程序＝算法＋数据结构逐步求精的设计方法和单入口单出口的控制结构。资源子网和通信子网的组成（与 51相同）字符，一个字符地对源程序进行扫描，读入源程序，对构成源程序的字符流进行扫描和分解，通过词法分析从而识别出一个个单词

(也称单词符号或符号 )。网络计算机：网络计算机（ NETWORKCOMPT称N，是专用于高速网络环境下的计算机终端设备。是基于处理器芯片和网络基础的新一代计算机产品，是一种新的桌面计算机。 除了有人机交互必需的显示器，键盘鼠标外，没有硬盘，软盘，光驱等外部存储设备，是一种瘦客户机。网络计算机具有以下优点：易管理，维护简单，使用方便。维护的地方，大大减少了计算机网络的维护工作，成本低廉。安全性强，无论是防止病毒的侵犯，还是资料维护的安全， 都比PC要好的多。耗非常小。中数据的正确性、有效性、相容性，防止错误的数据进入数据库。正确性是指数据的合法性；有效性是指数据是否属于所定义的有效范围；相容性是指表示同一个事实的多个数据应该相同。收、发双方在时间基准上保持一致，系统需要一个同步时钟，用于传输大量的信息。是任意的，字符与字符之间的间隔也是任意的，即各个字符之间是异步的。计算机进行信息获取、表示、存储、处理、控制等的理论、原则、方法和技术的学术是科学的体现；技术得益于科学，它又向科学提出新的课题。语法分析的任务：语法分析是编译过程的第二个阶段，任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序” “语句“表达式”等等。(Algorithm)合，它在有限的时间内终止并产生结果”

是一组明确的、可以执行的步骤的有序集。算法的特性有：有穷性(可终止性)间内执行完成。确定性：算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。有效性(可执行性)确定的结果。据。结构化方法遵循的原则：

1个或多个输出数重要，但是，用户的需求不是一次就能够明确的，而是随着系统开发工作的深入，用户的需求表达和开发人员对用户需求的理解才能逐步明确、深化和细化。这就要求软件的开发要有用户的积极参与。否则，往往导致开发缓慢、不断反复、甚至失败。先分析、再设计、后实现的原则。结构化方法强调在进行系统设计和系统题。“自项向下”的原则，即从总体目标和功能出发，逐级分解、逐步细化，将整个开发系统分解，先实现某些子系统，然后再实现总的目标和功能。遵循这个原则，可以将一个复杂的问题分解成若干个比较简单的问题分别加以解决，从而降低了解决问题的难度。阶段成果文档化。结构化方法强调要将每一工作阶段的成果， 用明确的字和标准化的图形、表格等文档化工具进行完整而又准确的描述。这些文档即可标志阶段开发工作的结束，又是下阶段工作开展的主要依据。连网外设、各种软件资源与信息资源织成。资源子网负责全网的数据处理业务，向网络用户提供各种网络资源与网络服务。通信子网由通信控制处理机、 通信线路与其他通信设备组成， 负责完成网络据传输、转发等通信处理任务。数据库的三级模式结构：数据库系统通常采用三级模式结构， 它也是数据库管理系统内部的系统结构。模式也称逻辑模式，是数据库中全体数据的逻辑结构和特征的描述， 是所有用户的公共数据视图。模式层中定义了数据模型和模式图表，一个数据库系统中只有一个模式。外模式

DBM的主要功能都在这层。也称子模式或用户模式，是数据库用户可见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，通常与某一应用需求相对应。这层将来自模式层的数据转化为用户所熟悉的格式和视图。外模式通常可以有任意多个。内模式式层决定数据存储在存储设备中的实际位置，并处理数据的存取方法及数据在设备间的数据传输。数据库系统的内模式也只有一个。么全做，要么全都不做，是一个不可分割的工作单位。所有的事务都具有原子性(Atomicity) 一致性(Consistency) 隔离性(Isolation) 持续性(Durability) ，或简称ACID特性。都不做，不可以分割。变到另一个一致性状态。隔离性：系统内多个事务的执行是相互独立的，互不相扰。持续性：一个事务一旦执行成功，对于数据库中数据的改变是永久的。模块划分的原则：模块的划分不能够随意进行，而是应该遵循一定的原则：划分的模块要有尽量高的功能独立性，而模块之间应该是低耦合 (关联少)的。增加模块间关联度。模块间接口是必须是明确的。模块间可以有调用关系，这个调用的层次不能太多。尽量注意提高模块的复用率，提高开发效率。软件危机的表现形式：软件的质量难以保证开发的软件可靠性差。由于在开发过程中，没有确保软件质量的体系和措施，在运行中暴露出大量的问题。这种不可靠的软件，轻者会影响系统正常工作，重者会发生事故，造成生命财产的重大损失。软件开发成本和开发进度难以控制经费预算经常突破，完成时间一再拖延。由于缺乏软件开发的经验和软件开发数据的积累，使得开发工作的计算很难制定。主观盲目制定的计算，执行起来和足，进度计划无法按时完成，开发时间一再拖延。软件的维护非常困难开发的软件可维护性差。开发过程没有统一的、公认的规范，软件开发人员各自的风格工作，各行其事。开发过程无完整、规范的文档，发现问题后进行杂乱无章的修改。 程序结构不好，运行进发现错误也很难修改，导致维护性差。用户对“已完成”的软件系统不满意开发的软件不能满足用户要求。 开发初期对用户的要求了解不够明确， 未能到明确表达。开发工作开始后，软件人员和用户又未能及进交换意见，使得一些问题不能及时解决，导致开发的软件不能满足用户的要求，使开发失败。对某一机器，用 位二进制代码表示一个浮点数，阶码为为位。求真值的浮点数的表示形式，要求列出计算步骤。105（）将十进制数578.43转换为8421BC码。（2）将逻辑表达式化简AB ，要求列出化简步骤。（3）1101.101

m=4位，尾数合，包括了数据的逻辑结构、物