计算机导论复习要点.doc

All rights reserved by SunWanjie计算机导论复习要点一、 复习要点1、 计算机科学的基本思路P(11) L5从理论研究、到模型抽象及工程设计是计算机科学的基本思路。l 理论研究是基础，是连接学科科学研究与工程应用开发研究的重要环节；l 模型抽象是对客观现象和规律的描述和刻划；l 工程设计是对科学理论的工程化实现。2、 计算机理论研究的四个步骤P(11) L8理论研究，基于计算机科学的数学基础和计算机科学理论，广泛采用数学的研究方法，包含以下四个步骤：l 对研究对象的概念抽象（定义）；l 假设对象的基本性质和对象之间可能存在的关系（定理）；l 确定这些性质和关系是否正确（证明）；l 解释结果。3、 模型抽象的四个步骤P(11) L12模型抽象，基于计算机科学的实验科学方法，广泛采用实验物理研究方法。按照对客观现象和规律的实验研究过程，包括以下四个步骤：l 确定可能世界（环境）并形成假设；l 构造模型并做出预言；l 设计实验并收集数据；l 分析结果。4、 工程设计的四个步骤P(11) L16工程设计，广泛采用工程科学的研究方法。按照为解决某一问题而构造系统或装置的过程，包括以下四个步骤：l 叙述要求；l 给定技术条件；l 设计并实现该系统或装置；l 测试和分析该系统。5、 计算机科学的学科内容P(13) L2l 计算机科学的学科内容是以的理工科基础科目，包括物理学（主要是电子技术科学）、基础数学（含离散数学、线性代数等）为基础理论支撑发展起来的，理论与实践相结合的学科。按照基础理论、基本开发技术、应用以及它们与硬件设备联系的紧密程度分成三个层次即理论基础层、专业基础层和应用层。6、 决策系统P(20) L1l 20世纪60年代初，计算机处理突破了数值计算的框框，广泛用于非数值计算。需要解决的问题：数据的存储、加工和访问，导致了数据库理论和技术的出现。应用方向：信息管理系统（MIS）、决策系统（DDS）等。l 决策系统是针对各种各样的决策问题，以决策科学理论为指导，以信息系统为基础，开发的一类能进行某一方面自动或半自动决策，并进行相应的简单处理的系统7、 实时系统P(20) L9l 实时系统的开发是一个重要的方向。系统在运行过程中需要对数据进行实时响应和处理。实时系统由于存在数据通信的时间延迟引起系统的不确定性、系统调试的困难等多种因素，因此如何保证系统开发的正确性是一个大问题。l 实时系统是指这样一些系统，它们的运行及系统行为与时间有关，系统在运行过程中需要对数据进行实时响应和处理。8、 虚拟现实P(21) L30l 数据库技术、多媒体技术、图形学技术等的发展产生了两个新方向，即计算可视化技术与虚拟现实技术。l 所谓虚拟现实(VR)是用计算机生成逼真的三维视觉、听觉、触觉等真实感觉形成的虚拟世界，集多媒体的表现技术于一体，使用户可以在这样一种虚拟环境中通过与计算机的交互感受真实的世界和活动过程。9、 计算机的发展历史1.1节l MARK-1：人们一直认为艾肯制造的MARK-1是世界上第一台通用程序控制计算机。然而不幸的是，由于它的运算速度很慢，而且也不能进一步提高，因此，机电计算机一诞生就注定要很快地被电子计算机所取代。l EDVAC：从1944年8月到1945年6月在冯诺伊曼的带领下，计算机的设计工作获得了巨大的进展。存储程序通用电子计算机方案EDVAC 方案就这样问世了。EDVAC 方案规定新型计算机有5个组成部分： 计算器CA； 逻辑控制装置CC； 存储器M； 输入I； 输出O。同ENIAC相比，EDVAC方案有两个重大改进：为充分发挥电子元件的高速度而采用了二进制；提出了“存储程序”，可以自动地从一个程序指令进到下一个程序指令，其作业顺序可以通过一种称为“条件转移”的指令而自动完成。l UNIVACI：第一台用于商业数据处理的电子计算机。l ENIAC：1946年2月15日是人类历史上第一台现代电子计算机揭幕典礼的日子。埃尼阿克是世界上第一台真正能运转的大型电子计算机。它同几年后研制的冯诺伊曼机一起，奠定了现代计算机原型。10、存储程序式计算机P(33) L7l 计算机中，要实现机器的自动计算，必须先根据题目的要求，编制出求解该问题的计算程序（Computational Program），并通过输入设备将该程序存入计算机的存储器中，称为“程序存储”。l 存储程序式计算机由五部分组成，它们分别是：运算器（Arithmetic Unit）；控制器（Control Unit）；存储器（Memory）；输入设备（Input Device）；输出设备（Output Device ）。11、运算器P(34) L8l 运算器（Arithmetic Unit）是计算机对各种数据和信息进行算术和逻辑运算的部件，由各种逻辑电路组成，它们包括寄存器、加法器、移位器、多路选择器和一些控制电路。l 通用寄存器组用于存放参加运算的数据。l 输入端的多路选择器用于通用寄存器组中选出一路数据送入加法器中参加运算。l 输出端的多路选择器对输出结果有移位输出的功能。l 加法器和控制电路组成的逻辑电路能完成加、减、乘、除及逻辑运算的功能。12、控制器P(35) L6l 控制器（Control Unit）是统一指挥和控制计算机各个部件按时序协调操作的中心部件。它主要由程序计数器（PC）、指令寄存器（IR）、指令译码器（ID）、地址产生器（AGU）、时间发生器（TGU）和微程序控制部件组成。l 程序计数器（PC: Program Counter）由若干位触发器及逻辑门电路所组成，用来存放将执行的指令在主存储器中的存储地址。l 指令译码器（ID: Instruction Decode）由门组合线路组成，用来对指令操作码部分（）进行译码，产生的译码信号识别了该指令要进行的操作，并传送给微控制部件，以产生相应的控制信号。l 指令寄存器（IR: Instruction Register）是由若干位触发器所组成，用来暂时存放从主存中取出的指令。由时间发生器（TGU）产生“时标”。而计算机执行一条指令则是按一定时间顺序执行一系列微操作实现的，这个“时间顺序”，就是所谓的“时标”。13、指令l 指令：让计算机执行某种操作的命令。14、指令系统l 指令系统是指计算机硬件语言的系统，也叫机器语言。15、位P(45) L5l 当代计算机把信息表示成位的模式。一个二进制数的位（bit）是两个数字“0”和“1”中的一个，这里我们仅仅把它们看做是没有数字意义的符号。16、位运算P(45) L14l 与（AND）、或（OR）和异或（XOR）的运算。l 布尔运算AND语句是由逻辑乘AND组合两个相类似的语句而形成，其通用形式：P AND Q表示：只有当成分语句P和Q都为真时，该语句才是真，除此之外的任何情况下，都为假。l 布尔运算OR语句的通用形式为：P OR Q表示：当至少有一个成分语句为真时，该语句就为真。l 布尔运算XOR语句的通用形式为：P XOR Q表示：要么P为真，要么Q为真，即P和Q不相同时，该语句就为真。l 布尔运算NOT是另一种形式的布尔运算。它由一个语句形成，其通用形式为：NOT P表示：如果语句P为真，该语句就为假；反之亦然。17、数制及转换十进制： 八进制：二进制： 二进制转十进制： 十进制转二进制：18、数据压缩P(68) L16l 通用数据压缩技术：为了存储和传输数据，减小数据的规1、 模是很有帮助的。完成这项工作的技术叫做数据压缩。该方法有以下几种：2、 扫描宽度编码是用一个指明重复的数值以及该数值在序列中出现的次数的代码替代这个序列的过程。3、 关联编码法是记录连续的数据块之间的差别，而不是记录整个数据块，即每个数据块是以其与前一数据块的关系数据项的形式编码。4、 频率相关编码法是指用不同长度的模式表示数据项。数据项的位模式的长度与数据项被使用的频率成反比。5、 Lempel-Ziv（LZW）编码系统是自适应字典编码法的实例。术语字典指的是构成压缩信息的标准组件的集合。在自适应字典编码系统中，在编码过程期间字典允许变化。l 影像压缩1、 GIF系统通过把可能分配给一个像素的颜色数目减少到仅为256个的方法来研究问题，这意味着每个像素的值可以用一个字节而不是用三个字节表示。2、 另一种彩色影像的压缩技术是JPEG，它已经成为一个表示彩色图像的有效标准。19、并行处理P(84) L1l 并行性是指在同一时刻或在同一时间间隔内完成两种或两种以上性质相同或不相同的工作，并行性是指时间上的重叠。它可分为同时性和并发性两种。1、 同时性是指两个或多个事件在同一时刻发生。2、 并发性则是两个或多个事件在同一时间间隔内发生。l 增加处理的并行性，主要采用“时间重叠” 和“资源重复”两种途径：1、 时间重叠是指多个处理过程在时间上2、 互相错开，轮流重叠地使用同一套硬件设备的各个部分，以加速硬件周转，赢得时间，提高处理速度。3、 资源重复是采用重复设置硬件设备的方法来提高计算机的处理速度。20、并行处理的四个级别P(84) L14l 现有的并行计算机系统，可分别实现以下四个级别上的并行处理： 作业或程序级并行； 任务或过程级并行； 指令级并行； 指令内部级并行。21、根据指令流和数据流的多重性的计算机系统分类P(84) L27l 根据指令流和数据流的多重性可将计算机系统分为下列四类： 单指令流单数据流（SISD）：只有一个指令部件，一次只对一条指令译码，并且只对一个操作部件分配数据。 单指令流多数据流（SIMD）：有多个处理单元，它们在同一个控制部件的管理下执行同一条指令，并向各个处理单元分配各自需要的不同数据。 多指令流单数据流（MISD）：包含多个处理单元，同时执行多条指令对同一数据及其中间结果进行不同的处理。 多指令流多数据流（MIMD）：这类计算机系统内有多个处理机，实际上是多个独立的SISD计算机的有机的集合，它们同时运行多个程序并对各自的数据进行处理。22、通道P(85) L7l 通道是一个特殊功能的处理器，它有自己的指令和程序专门负责数据输入输出的传输控制。l 在具有通道的计算机内有两类总线： 存储总线，它承担CPU与内存、通道与内存之间的数据传输任务； 通道总线，即I/O总线，它承担外部设备与通道之间的数据传输任务。l 通道的基本功能有： 接受CPU的I/O指令，按指令要求与指定的外部设备进行连接； 从内存选择属于该通道的通道指令，经译码后向设备控制器和设备发送各种命令； 组织外部设备和内存之间的数据传输，并根据需要提供数据中间缓存的空间，以及提供数据存入内存的地址和传送的数据量； 检查设备及设备控制器的工作状态，形成并保存通道本身的状态信息，并将这些状态信息送到内存指定单元，供CPU使用； 将外部设备的中断请求及通道本身的中断请求按顺序及时报告给CPU。23、通道的类型P(86) L9l 通道的类型根据外设共享通道的情况及信息传送速度的要求，通道可分为多类： 选择通道：又称高速通道，可连接多台高速设备，但它们不能同时工作。选择通道主要用于连接高速外部设备，如磁盘机、磁带机等。 成组多路通道：规定多个设备以数据组（块）为单位交叉使用通道。当几个子通道同时请求为自己服务时，用优先级排队方法裁决。成组多路通道适用于中、高速设备，如磁带机、宽行打印机等。 字节多路通道：规定与其连接的各设备按字节为单位交叉使用通道。24、计算机软件P(97) L1l 计算机软件是指用计算机指令和计算机算法语言编写的程序，以及运行程序所需的文档、数据。l 计算机软件包括： 程序，用算法语言描述计算机处理问题的算法； 文档，软件开发过程中的需求分析、方案设计、编程方法、维护等文档资料； 使用说明书、用户手册、操作手册、维护手册等； 使用计算机的人员的知识和能力25、软件的特点P(97) L11l 软件实现的功能容易改变和修改；l 软件适宜选择多种方法和算法进行比较；l 软件适宜用在条件判别和控制转移多的情况；l 软件适宜进行复杂的算法处理；l 软件实现不如硬件实现速度快；l 软件不适宜用在对安全性要求高的情况，其原因是容易被篡改和破坏。 26、系统软件及分类P(98) L18l 管理计算机资源、提供用户使用界面的操作系统l 用于数据高效处理的输入输出程序l 通信传输、控制处理的程序l 计算机系统诊断、监控、故障处理程序l 计算机语言编辑、编译、链接程序l 数据库管理系统l 软件开发工具及支援程序27、应用软件及分类P(99) L1l 应用软件是计算机用户在系统软件平台上开发的程序。应用软件适应信息社会各个领域的应用需求，每一领域的应用具有许多共同的属性和要求，具有普遍性。l 应用软件种类有： (1) 数值计算处理，包括：数值解析；统计解析；数理规则；预测、模拟；线性规划；日程计划。(2) 工程技术应用，包括：CAD、CAM；结构分析；数值控制。(3) 公用技术应用，包括：文档处理；图形处理；图像处理；信息检索；机械翻译；自然语言处理；模式识别；专家系统；决策支持；CAI。 (4) 通用管理，包括：财务管理；人事管理；物资管理；图书资料管理。 (5) 各类专业管理，包括：医疗、保健管理；学校、教育管理；公共交通管理；银行金融、交易管理；文化管理等。 (6) 办公自动化，包括：报表处理；日程管理；文件汇总；文件收发、传送管理等。28、软件的开发过程P(99) L18l 可行性讨论；l 需求分析；l 系统设计(概要设计、详细设计)；l 程序开发；l 编码，单元测试；l 系统测试；系统维护。 29、软件开发技术的发展原因及趋势P(101) L27及P(106) L2l 软件开发技术的发展主要基于三个方面的原因： 信息化社会的需要，这是它得以发展的动力； 计算机硬件的性能越来越高，价格越来越便宜，这是它得以发展的基础； 使用计算机的人越来越多，计算机应用越来越广泛，这是软件开发技术得以发展的环境。 l 发展的趋势主要表现在四个方面： 自动化程度的提高。 把需求分析包括到软件工作的范围内，使软件开发过程进一步向用户方面延伸，离用户更近了，避免了以往“你出算法，我编程序”的做法带来的种种问题； 把软件开发工作延伸到项目管理和版本管理，把软件开发从一次编程扩展到全过程，这是软件研制从个体的、手工作坊的方式向科学的、有组织的方式转变的重要表现； 研究吸收了许多管理科学的内容和方法，如开发人员的组织，质量的控制、开发过程的协调等，这一变化把软件开发项目负责人的思想和方法摆在了更重要的位置，这是符合软件规模越来越大、软件开发工作越来越依赖组织与管理的发展趋势的。 30、结构化程序设计P(102) L8l SD是功能分解的方法，采用模块化设计。l SD方法采用的是自顶向下、逐步分解的方法，直到最低层的模块达到所要求的规模为止，一般采用HLPO图示，意思是分层结构加输入、输出处理。 l SD方法主要是为程序员服务的，是从程序员如何编程、测试及编写文档去考虑问题的。这种思想是早期的以手工方式、个人编写程序的工作环境下的想法。l 缺点：是增大了程序的工作量，程序的运行效率不高，不适合大型软件的研制过程和规律。 31、软件工程的开发方法P(102) L24l 软件的规模越来越大，复杂程度越来越高，把软件的质量和设计寄予各个程序员的技能、工作态度是靠不住的，这就要求软件生产成为有组织的、可以管理的工程项目。用工程项目实施的方法来组织软件的开发称为软件工程学（Software Engineering），缩写SE。 32、面向对象的开发方法P(103) L13l 面向对象的程序设计方法（Object Oriented Programming），缩写为OOP，是人们解决软件复杂性的一种新的软件开发技术。OOP的思想方法越来越接近人们的思维方式，它丢开了持续许久的“自顶向下”（TopDown）和“自底向上”（BottomUp）方法的争论，把对于复杂系统的认识归结为对一批对象及其关系的认识。OOP使用户以更自然、更简便的方式进行软件开发。 l 面向对象的基本思想可以归纳为以下四点： 客观世界的任何事物都是对象(Object)，它们都有一些静态属性（相应于数据结构），也都有一些有关的操作（相应于程序模块）。作为一个整体，对外不必公开这些属性与操作，这称为“封装性”（Encapsulation）； 对象之间有抽象与具体、群体与个体、整体与部分等几种关系，这些关系构成对象的网络结构； 较大的对象所具有的性质自然地成为它的子类的性质，不必加以说明和规定，这称为“继承性”（Inheritance）； 对象之间可以互相传送“消息”（Message）并进行联系，一个消息可以是传送一个参数，也可以是使一个对象开始某个操作。 33、算法P(106) L21l 算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。l 算法+数据结构=程序l 算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。制定一个算法，一般要经过设计、确认、分析、编码、测试、调试、计时等阶段。 34、算法学习的五个方面P(107) L3l 设计算法。 表示算法。 确认算法。 分析算法。 验证算法。35、算法的特性P(107) L15l 确定性。 能行性。 输入。 输出。 有穷性。 35、算法的描述方法P(107) L56l 自然语言l 图形，如NS图、流程图，图的描述与算法语言的描述对应l 算法语言，即计算机语言、程序设计语言、伪代码l 形式语言，用数学的方法，可以避免自然语言的二义性36、算法的评价l 空间复杂性S（n）：按算法所编制的程序在计算机中所占用的存储单元的总数。n是问题的规模，显然S（n）是随n的增长而增加。l 时间复杂性f（n）：按算法所编制的程序在计算机执行时所耗费的时间。显然f（n）随 n的增长而增加。 37、程序设计语言P(112) L12l 机器语言 汇编语言 高级语言 非过程化的语言 38、计算机程序P(114) L2l 计算机程序是用算法语言描述的解题步骤，或者讲是用程序设计语言实现的算法，程序是一串指令序列的集合，它能被计算机执行。 39、程序流程图P(114) L14l 数据流程图 系统流程图 程序流程图 40、程序设计的过程P(119) L13l 用高级语言编制程序的过程为：(1) 用编辑工具，如WORD、EDIT书写源程序，建立源程序文件，文件扩展名与所用的语言有关，例如C+语言的源程序文件扩展名为.cpp；(2) 编译源程序文件，生成目标文件，文件扩展名为.obj；(3) 链接目标文件，生成可执行文件，文件扩展名为.exe；(4) 在计算机上执行可执行程序文件，进一步调试和维护。 41、汇编程序P(120) L4l 汇编程序是把用汇编语言编写的汇编语言源程序翻译成机器语言的程序。汇编语言的指令与机器语言的指令基本上保持了一一对应关系，所以汇编的过程就是对汇编指令逐行进行处理，翻译成计算机可以理解的机器指令，处理步骤为： (1) 把指令的助记符操作码转换成相应的机器操作码； (2) 把符号操作数转换成相应的地址码； (3) 把操作码和操作数构造成机器指令。 42、解释程序P(120) L25l 解释程序的功能是对用高级语言编写的源程序按动态顺序进行逐句分析翻译，解释一句后立即得到执行结果。解释程序不产生目标代码。同编译程序相比，解释程序本身的编写比较容易。解释程序对源程序的解释执行比编译程序产生的目标代码程序的执行速度要慢。 43、编译程序P(121) L1l 编译程序也叫编译系统，是把用高级语言编写的面向过程的源程序翻译成目标程序的语言处理程序。l 编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段：词法分析；语法分析；中间代码生成；代码优化；目标代码生成。主要是进行词法分析和语法分析，又称为源程序分析，分析过程中发现有语法错误，给出提示信息。 44、良好的程序设计风格P(122) L17l 良好的程序设计风格 ：(1) 编码格式和编码约定在整个程序中应保持一致；(2) 程序中应给出必要的注释，尤其在变量定义、调用接口、参数传递处，在修改程序时应注明修改人、时间、简要的修改原因；(3) 对变量、函数标识等的命名，采用“匈牙利命名法”，避免含义不明确的缩写，从命名就可以一目了然读出命名标识的含义和数据类型；(4) 采用缩进格式，突出程序的逻辑层次结构；(5) 每一行只写一条语句，使用括号间隔表达式或语句的组成部分，使组成部分清晰；(6) 使用结构化、面向对象的编程技术，提高程序可重用性、可扩充性；(7) 除非完全必要，应尽量避免多任务和多重处理；(8) 尽量避免使用复杂的算术和逻辑表达式；(9) 提高程序健壮性，预防用户的操作错误，做到废进废出。 45、操作系统P(127) L15l 人们认识到必须找到某种方法将计算机硬件的复杂性与程序员分离开来，在计算机裸机上加载一层软件来管理整个系统，同时给用户提供一个更容易理解和编程的接口，这个接口称为虚拟机，这层软件是操作系统。l 操作系统是系统软件的基本部分。 l 操作系统是计算机系统的核心，是用户和其他软件与计算机裸机之间的桥梁 。46、OS的功用P(128) L1l 三项主要作用：（1）为计算机中运行的程序管理和分配系统中的各种软硬件资源（2）为用户提供友善的人机界面（图形用户界面）（3）为开发和运行应用程序提供高效率的平台l 其它辅助功能：辅导用户操作（帮助功能）、显示系统状态、处理软硬件错误、保护系统安全47、OS的类型P(128) L22l 操作系统有三种基本类型：批处理系统：又分为单道批处理和多道批 处理 分时系统：具有多路性、交互性、独占性特点 实时系统： 具有提供及时响应和高可靠性特点 48、OS的结构P(131) L13l 操作系统的结构有三种：整体式结构、核心结构和层次结构。 整体式结构是指将整个操作系统作为一个整体运行操作系统时，不能响应其他中断。核心结构是指把操作系统分为外壳部分和核心部分。层次结构是把操作系统的功能分层，每层有明确的功能，提供接口与上下层联系，上层软件调用下层软件提供的服务。 49、进程P(132) L3l 进程是操作系统的基本单位。一个进程本质上是一个程序的执行，每个进程有其自己的地址空间，地址空间中包括可执行程序、程序用到的数据及堆栈，进程可以读写该空间中的内容。与每个进程相关的还包括一组寄存器、程序计数器和指针等。l 进程的三种状态为： 运行状态，表示进程正占用CPU。 就绪状态，表示进程准备占用CPU。 等待状态，表示进程由于某种原因暂时不能占用CPU，正在等待某个事件发生。 l PCB一般应包含这样一些信息： 进程名，即进程标识符。 当前状态，说明了进程当前所处的状态。 状态链指针，指出该进程所在队列中的下一进程。 优先级，表示进程要求CPU响应处理的快慢。 对资源的需求。 存储指针（该进程对应的程序和数据的起始物理地址）。 现场保留区和通信信息。 50、进程控制块P(132) L19l 进程控制块PCB（Process Control Block）是为实现对进程的管理而引进的专门的数据结构，也叫PCB表，它是进程存在的惟一标志。PCB随着进程的创建而建立，随着进程的撤消而撤消。 51、死锁P(133) L13l 当两个或两个以上的进程因争用系统资源而无休止地互相等待时，就发生进程死锁，这是系统的一种出错状态，应采取预防措施避免出现死锁现象。l 预防死锁的方法有：静态预先分配所有资源法、有序资源分配法和受控资源分配法。 52、软件工程的7条基本原理P(146) L7l 用生命周期计划严格管理 l 坚持进行阶段评审 l 产品一致性控制 l 采用最新的软件设计技术 l 清楚地审查软件产品 l 人员应该少而精 l 不断改进软件工程实践的必要性 53、软件生命周期P(148) L31l 软件定义时期：问题定义、可行性研究、需求分析l 软件开发时期 ：四个阶段组成：总体设计、详细设计、编码和单元测试、综合测试l 软件维护时期 ：改正性维护、适应性维护、完善性维护、预防性维护54、生命周期方法学P(148) L25l 软件生命周期阶段的划分方法与软件规模、种类、开发方式、开发环境以及开发时使用的方法有关，应该遵循的一条基本原则，就是使各阶段的任务彼此间尽可能相对独立，同一阶段各项任务的性质尽可能相同，从而降低每个阶段任务的复杂程度，简化不同阶段之间的联系，有利于软件开发工程的组织管理。软件定义、软件开发、软件维护组成了软件生命周期 55、计算机网络发展的四个阶段P(158) L1l 联机终端网络、计算机-计算机网络、计算机网络体系结构、Internet（因特网）阶段56、NII的基本组成P(160) L17l NII的基本组成有通信网络、计算机设备、动态的信息和人。57、NII的层次结构P(160) L27l 传输层次、网络层次、用户界面层次 、信息服务层次 58、计算机网络的分类P(161) L11l 计算机网络的分类有多种方法，按所覆盖的地域范围分类，可以分为：局域网LAN（Local Area Network）；城域网MAN（Metropolitan Area Network）；广域网WAN（Wide Area Network）。l 按采用的交换技术划分，可以分为：电路交换网；分组交换网；信元交换网（ATM网）。l 按用途划分，可以分为：专用网，例如金融网、教育网、税务网；公用网，例如帧中继网、DDN网、X.25网。 l 网络拓扑结构用来描述网络的连接形状和组成形式，网络拓扑结构有总线型、环型、星型、网状型、树型等。l 计算机网络的传输介质分为有线和无线两大类。 59、网络通信协议P(161) L26l 网络通信协议是通信双方在通信时遵循的规则和约定，网络通信协议是信息网络中使用的通信语言。通信是在人们之间传递消息，一次通信要有三个因素：（1） 通信双方有通信的愿望和要求；（2） 通信双方之间有通信的信道；（3） 通信双方遵循彼此认可的通信规则，即通信协议或网络协议。l 网络通信协议有三个要素：（1） 语法，即信息格式；（2） 语义，某些信息组合的含义；（3） 同步，即收、发双方能分辨出通信的开始和结束。60、TCP/IP协议P(163) L1l TCP（传输控制协议)和IP(网际协议)是两个最基本、最重要的协议61、OSI/RM P(163) L24l TCP/IP协议与OSI模型的关系如图所示。62、IP地址P(164) L2l 计算机网络中的地址有：使用地址、IP地址、物理地址。在计算机网络中的IP地址是由二进制数组成的。l Internet上每台计算机都应有一个惟一的IP地址。IP地址用32位二进制数标识计算机网络中的每一台计算机。l 每个IP地址由网络标识（NetID）和主机标识（HostID）两部分组成 。l IP地址按第一个字节的前几位是0或1的组合，标识为A、B、C、D、E五类地址，如图所示。ll IP地址的特点：惟一性：网络上的每台计算机都有一个与众不同的惟一的IP地址简明性：所有地址的长度都是32个二进位l IP地址的格式：包含类型号、网络号和主机号 3个部分63、DNS P(165) L7l 域名系统DNS（Domain Name System），它的核心是分级的、基于域的命名机制，以及为了实行这个命名机制的分布式数据库系统l DNS域名空间采用层次结构，从根域名开始，有顶级域名，下面再划分各级子域名，网络中的计算机主机名接在某一子域名后面。（1）国家顶级域名，用两个英文字母的缩写标识一个国家 ；（2） 国际顶级域名为int，供国际组织使用；（3） 通用顶级域名，为各个行业、机构使用。 64、URL P(167) L2l URL（Uniform Resource Locate）是一种统一格式的Internet 信息资源地址的标识方法，URL的位置对应在IE浏览器窗口中的地址栏，URL将Internet上提供的服务统一编址，URL的格式为：协议服务类型：/主机域名：端口号/文件路径/文件名65、WWW P(169) L1l World Wide Web是一种基于Internet 的跨越全球的超媒体网络系统，它把分散在全世界各地服务器上的文本、图形、音频和视频等信息资源有机地结合在一起，组成Web网页，通过超链接在Internet上构成一个巨大的逻辑网络，这也正是World Wide Web（原义为遍布世界的蜘蛛网）一词的含义和由来。WWW采用B/S（Browse/Server）模式 66、HTTP P(170) L3l HTTP被定义为“无状态”协议，它可以用来提高数据传送速度。67、FTPl 文件传输协议68、HTML P(170) L10l HTML是标准通用标记语言SGML（Standard Generalized Markup Language）的一个应用和发展，SGML的国际标准为ISO 8879。l HTML是一种标注语言，用标记符号标记和描述信息的显示格式。超文本链接是用超文本链接标记符A/A指明的，例如链接中国中央电视台的标记方法为：A href=中央电视台/A。l 20世纪90年代以来又研制了扩展标记语言XML（Xtended Markup Language）。68、网络安全的层次P(171) L3l 操作系统层的安全、用户层安全、传输层安全、网络层安全、数据链路层安全69、防火墙的作用 P(174) L6l 防火墙对流经它的信息进行扫描，确保进入子网和流出子网的信息的合法性，它还能过滤掉黑客的攻击，关闭不使用的端口，禁止特定端口流出信息, 等等 70、DS P(181) L1l 数据结构71、DS的研究内容 P(182) L11l 数据结构包括三个方面的研究内容： （1）数据的逻辑结构, 即数据是如何组织的。 线性表 树 图 集合 （2）数据的存储结构，数据在计算机中是如何存储的顺序存储 链式存储 索引存储 散列存储 （3）数据的操作实现算法。插入、删除、查找、排序等。72、顺序存储方式 P(192) L2l 所谓顺序存储结构，就是用一组连续的存储单元存放二叉树中的结点。完全二叉树由于其结构上的特点，通常采用顺序方式存储。 73、链式存储 P(193) L1l 二叉树的链式存储结构是用链建立二叉树中结点之间的关系，通常采用的链式存储结构为二叉链表。 74、栈 P(186) L16l 栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时，称之为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。75、队列 P(189) L1l 对于队列我们并不陌生，商场、银行的柜台前需要排队.队列是一种只允许在表的一端进行插入操作而在另一端进行删除操作的线性表。表中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队头和队尾分别由队头指示器（或称队头指针）和队尾指示器（或称队尾指针）指示。当队列中没有数据元素时，称之为空队列。队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。l 根据队列的定义，每次进队列的数据元素都放在原当前队尾之后而成为新的队尾元素，每次出队列的数据元素都是原队头元素。76、二叉树 P(190) L21l 二叉树是结点的有限集合，这个有限集合或者为空集（称为空二叉树），或者由一个根结点及两棵不相交的、分别称为这个根的左子树和右子树的二叉树组成。77、文件 P(194) L19l 存放在外存储器中的数据为文件78、文件系统的功能 P(194) L25l 统一管理文件存储空间（即外存），实施存储空间的分配与回收。即在用户创建新文件时为其分配空闲区，而在用户删除或修改某个文件时，回收和调整存储区。l 确定文件信息的存放位置及存放形式。l 实现文件从名字空间到外存地址空间的映射，实现文件的按名存取。即文件有一个用户可见的逻辑结构，用户按照文件逻辑结构所给定的方式进行信息的存取和加工，并且这种逻辑结构是独立于物理存储设备的，从而使用户不必了解文件存放的物理结构和查找方法等与存取介质有关的部分，只需给定一个代表某一文件的文件名，文件系统就会自动地完成对与给定文件名相对应文件的有关操作。l 有效实现对文件的各种控制操作（如建立、撤销、打开、关闭文件等）和存取操作（如读、写、修改、复制、转储等）。l 实现文件信息的共享，并且提供可靠的文件保密和保护措施。79、顺序文件 P(196) L20l 顺序文件是指文件中的物理记录按其在文件中的逻辑记录顺序依次存入存储介质而建立的。顺序文件在存储介质中可以有两种不同的实现结构：连续结构和链结构。80、文本文件 P(197) L17l 文本文件是一种典型的顺序文件，其文件的逻辑结构又属于流式文件。l 特别的是，文本文件是指以ASCII码方式(也称文本方式)存储的文件，更确切地说，英文、数字等字符存储的是ASCII码，而汉字存储的是机内码。文本文件中除了存储文件有效字符信息（包括能用ASCII码字符表示的回车、换行等信息）外，不能存储其他任何信息，因此文本文件不能存储声音、动画、图像、视频等信息。81、索引文件 P(198) L12l 为了提高文件的检索效率，可以采用索引方法组织文件。采用索引这种结构，逻辑上连续的文件可以存放在若干不连续的物理块中，但对于每个文件，在存储介质中除存储文件本身外，还要求系统另外建立一张索引表，索引表记录了文件信息所在的逻辑块号和与之对应的物理块号。索引表也以文件的形式存储在存储介质中，索引表的物理地址则由文件说明信息项给出。82、HASH文件 P(199) L13l 哈希表中数据记录是这样组织的：某一个关键字为key的数据记录在放入哈希表时，根据key确定该数据记录在哈希表中的位置。从数学的观点看就是产生一个函数变换：l DH（key）l 其中，key是数据记录的关键字，D是数据记录在哈希表中的存储位置，H称为哈希函数。l 在建立一个哈希表之前需要解决两个主要问题：（1） 构造一个合适的哈希函数（2） 冲突的处理l 哈希文件是利用哈希函数法组织的文件，它类似于哈希表，即根据文件记录的关键字的特点设计一种哈希函数和处理冲突的方法从而将记录散列到外存储器上。由于哈希文件中通过计算来确定一个记录在存储设备上的存储位置，因而逻辑顺序的记录在物理地址上不是相邻的，因此哈希文件不宜使用磁带存储，只适宜使用磁盘存储；并且哈希文件这种结构只适用于定长记录文件和按记录键随机查找的访问方式。83、数据库 P(202) L4l 数据库(DB,DataBase)是存放数据的仓库，只不过这个仓库在计算机存储设备上，而且数据是按一定的格式存放的。l 在科学技术飞速发展的今天，人们的视野越来越广，数据量急剧增加，过去人们把数据存放在文件柜里，现在人们借助计算机和数据库技术科学地保存和管理大量的复杂的数据，以便能方便而充分地利用这些宝贵的信息资源。l 所谓数据库是长期储存在计算机内、有组织的、可共享的数据集合。数据库中的数据按一定的数据模型组织、描述和储存，具有较小的冗余度、较高的数据独立性和易扩展性，并可为一定范围内的各种用户共享。84、DBMS P(203) L21l 数据库是长期存储在计算机内有组织的大量的共享的数据集合，它可以供在一定范围内的各种用户共享，且具有最小的冗余度和较高的数据与程序的独立性。如何科学地组织和存储数据，并且高效地获取和维护数据呢？完成这个任务的是一个系统软件数据库管理系统。l 数据库管理系统（DBMS，DataBase Management System）是操纵和管理数据库的软件系统，它由一组计算机程序构成，管理并控制数据资源的使用。在计算机软件系统的体系结构中，数据库管理系统位于用户和操作系统之间。85、DBMS的基本功能 P(203) L29l 数据库管理系统是数据库系统的核心，主要是实现对共享数据有效的组织、管理和存取，它的基本功能包括以下几个方面：（1） 数据库定义功能（2） 数据操纵功能（3） 数据库的运行管理（4） 数据组织、存储和管理功能（5） 数据库的建立和维护功能（6） 其他功能86、数据库技术的发展 P(207) L2087、媒体及分类 P(211) L15l 媒体是指人们用于存储和传送各种信息的载体。从计算机处理信息的角度可将媒体归类为最基本的五种，即感觉媒体、表示媒体、显示媒体、存储媒体以及传输媒体。l 感觉媒体（2） 表示媒体（3） 显示媒体（4） 存储媒体（5） 传