计算机科学导论
1 绪论
图灵模型是一个可编程的数据处理器，在图灵模型中，输出数据依赖于两方面因素的结合作用：输入数据和程序。通用图灵机是对现代计算机的首次描述，该机器只要提供了了合适的程序就能做任何运算。
基于冯?诺依曼模型建造的计算机分为4个子系统：存储器、算术运算单元(ALU)、控制单元和输入/输出单元。存储器用来存储数据和程序；算术运算单元进行计算和逻辑运算；输入/输出单元负责从计算机外部接收数据和程序，并把计算机的处理结果输出到计算机外部，控制单元是对其他子系统进行控制操作。
冯?诺依曼模型中的程序和指令在计算机中都以二进制比特存储，在计算机中，指令按顺序执行。
计算机由3大部分组成：计算机硬件、数据和计算机软件。硬件基于冯?诺依曼模型，且包含四部分。数据以0/1比特进行存储。图灵和冯?诺依曼模型的主要特征是程序的概念。程序被存储在计算机的存储器中，且必须是有序的指令集。指令集的作用实现重用。算法是按步骤解决问题的办法，计算机语言可以提高编程的效率，软件工程是指结构化程序的设计和编写，它不仅包括要完成某一任务的应用程序，还包括程序设计要严格遵循的原理和规则。而操作系统的诞生，是有一系列指令对所有程序来说是公用的，因此它是程序访问计算机部分提供方便的一种管理程序。
2 数字系统
在将十进制数转换到其他底的数值时，分为两部分，整数部分是进行连除，余数作为本位的数值，商进行下一步计算；小数部分是进行连乘，整数值作为本位的数值，小数值进行下一步计算。
3 数据存储
数据类型分为5种：数字、文本、音频、图像和视频。所有的数据类型都转换为称作位模式的统一表现形式。
数字在存储到计算机内存中之前被转换成二进制系统。有多种方法来处理符号。有两种方法来处理小数点：定点和浮点。整数可以被当作小数点位置固定的数字。无符号整数是永远不会为负的整数。存储有符号整数的方法之一是符号加绝对值格式。这种格式中，最左边用于显示符号且其余位定义绝对值。符号和绝对值互相分开。几乎所有的计算机都使用*二进制补码表示法*来存储位于n位存储单元中的有符号整数。在该方法中，无符号整数有有效范围被分为两个相等的子范围。每一个子范围用来表示非负整数，每二个子范围用来表示负整数。在二进制补码表示法中，最左边决定整数的符号。但符号和绝对值互相分开。实数是带有整数部分和小数部分的数字。实数使用浮点表示法存储在计算机中。在浮点表示法中数字由3部分组成：符号、位移量和定点数。
文本的片断是用来表示该语言中某个意思的一系列符号。我们可用位模式来表示每一个符号。不同的位模式集合被设计用于表示文本符号。硬件和软件制造商联合进来共同设计了一种名为Unicode的代码，这种代码使用32位表示一个符号。
总督表示声音或音乐。音频是模拟数据，我们不能够在一段时间记录无限数量的值，我们只能记录一些样本。样本数依赖于模拟信号中变化的最大数量。从每个样本测量得到的值是真实的数字。量化指的是将样本的值截取为最接近的整数值的一种过程。
存储在计算机中的图像使用两种不同的技术：光栅图或适量图。当我们需要存储模拟图像（如照片）时，就用到了光栅图。图像被扫描（采样）然后存储像素。用矢量图方法，图像被分解成几何图形的组合，诸如线段、矩形或圆形。每个几何形状由数学公式表达。
视频是图像（称为帧）在时间上的表示。一部电影就是一系列的帧逐个播放而形成运动的图像。换言之，视频是随空间（单个图像）和时间（一系列图像）变化的信息表现。
需要注意的地方是：
符号加绝对值的表示方法有两个0，分别是+0和-0，而二进制补码的表示法只有一个0。因此范围也不一样。
科学户数法中的规范化表示存储该数的3部分信息：符号、指数和尾数。小数点左边的1并没有存储，它们是隐含的。尾数是带符号的小数部分，像以符号加绝对值表示法存储的整数那样对待。
在余码系统中，正的和负的都以无符号数存储，将正整数添加到每个数字中，，统一按偏移量把数向右移。
在IEEE标准中，单精度数用32位来存储，符号1位、指数8位（偏移量为127）、尾数为23位，也称为余127码。双精度数彩共64位来存储，符号1位、指数11位（偏移量为1023）、尾数使用52位，也称为余1023码。
图像的表示中对像素的编码使用的是RGB数，共24位，称为真彩色，每个8位表示0~256之间的一个数；除了真彩色之外，另一种方法是用索引色，通常只有256个索引，只用8位来存储同样的像素。JPEG格式使用的是真彩色模式，但压缩了图像，gif格式使用的是索引色模式。
4 数据运算
数据运算分成三大类：逻辑运算、移位运算和算术运算。NOT运算符的唯一应用是求反，AND运算符的一个应用是对指定位进行置位(置0)，OR运算符的一个应用是对指定位置位(置1)，XOR运算符可以对指定位进行翻转。移位运算分为逻辑移位和算术移位，逻辑移位应用于不表示为符号数的模式，移动的空缺补0，其中循环移位会将移出的位补到空缺位。；算术移位假定模式为二进制补码的符号整数，向右移符号位保留，向左移符号位删除，空位补0。
计算机中对整数的加减法使用的是二进制补码进行运算，减法转化为补码的加法进行运算，而用符号加绝对值的形式非常复杂，要考虑8种情况。浮点数的实数的加减法简化为小数点对齐后的以符号加绝对值柳芽存储的两整数的加减法。
5 计算机组成
计算机的组成分成三大类（或子系统）：CPU、主存和输入/输出子系统。
中央处理单元（CPU）执行数据上的操作，它有三部分：算术运算单元（ALU）、控制单元和一系列寄存器。算术逻辑单元（ALU）负责算术、移位和逻辑运算。寄存器是快速独立的存储设备，它可暂时地保留数据。控制单元控制CPU中每个部分的操作。
主存是存储单元的集合。每一个单元有一个称为地址的标识符。数据被传输到内存或从内存取出是以称为字的二进制位组的方式。内存中唯一可标识的单元总数称为地址空间。有两种内存可用：随机存取存储器（RAM）和只读存储器（ROM）。
输入输出（I/O）子系统的设备集合允许计算机与外界交流，存储程序和数据，即使在计算机已关机时也可以。输入/输出设备分成两大类：非存储设备和存储设备。非存储设备允许CPU/内存与外界通信；存储设备可以存储以后被检
索的大量信息。存储设备被分成磁的和光的。
计算机中三个子系统的连接起重要的作为，因为在这些子系统间需要进行信息的通信。CPU和内存通常被三个连接连在一起（每个称为总线）：数据总线、地址总线和控制总线。输入/输出设备通过输入/输出控制器或接口与总线相连，使用的控制器有多种，如今最常见的有：SCSI、火线和USB。
有两种方法输入/输出设备的寻址：I/O独立寻址和I/O存储器映射寻址。在I/O独立寻址方法中，用来从内存读/写的指令完全不同于用来从输入/输出设备的读写指令。在I/O存储器映射寻址方法中，CPU把I/O控制器中的每个寄存器看成是内存中的字。
如今，通用计算机使用称为程序的一组指令来处理数据。计算机执行程序，从输入数据创建输出数据。程序和数据都存储在内存中，CPU使用重复的机器周期一条接一条，从头到尾执行程序中的指令。简化的周期由三阶段组成：取指令、译码和执行。
有三种使CPU和输入/输出设备同步的方法：程序控制输入/输出、中断控制输入/输出和直接存储器存取(DMA)。
在最近向十年中，计算机的体系结构和组织经历了许多变化。计算机体系结构分成两大类：CISC（复杂指令集计算机）和RISC（精简指令集计算机）。
现代计算机使用流水线技术来提高吞吐量。这个理念允许控制单元同时执行两个或三个阶段，这意味着下一条指令的处理可以在前一条结束前开始。
计算机传统上有一个控制单元、一个算术逻辑单元和一个内存单元。并行处理通过使用多指令流处理多数据流来改善吞吐量。
6 计算机网络
计算机网络是把数据从一个地方传送到另一个地方的硬件和软件的组合。网络的标准中最重要的是性能、可靠性和安全。网络中有种连接：点对点连接和多点连接。有四种常见的拓扑结构：网状型、星型、总线型和环型。其中最常用的是星型。
网络可以分为三大类：局域网（LAN）、广域网（WAN）和城域网（MAN）。互联网是能够互相通信的两个或多个网络，因特网是所有网络的总和。
控制因特网的协议集合称为TCP/IP协议族，由五层组成：应用层、传输层、网络层、数据链路层和物理层。路由器只使用下三层。
应用层负责向用户提供服务。应用层的地址是特定于应用程序的。
传输层负责整个消息的进程到进程的分发，意味着传输层的客户端与服务器间创建了一种逻辑连接。传输层中用端口号来标识进程。传输层的一个职责是多路复用和解多路复用。服务器使用众所周知的端口号，计算机使用传输层分配的临时端口号。另外，传输层负责拥塞控制、流量控制与差错控制。在TCP/IP协议族的发展历程中，有三种传输层协议：UDP、TCP和SCTP。UDP不提供属于单个消息的数据包间的逻辑连接，因此属于无连接协议。TCP支持传输层所有职责的协议，也被称为面向连接的协议。UDP速度最快，TCP速度最慢，不适合实时传输。SCTP适合于实时传输。
网络层负责单个数据包从源主机到目的主机的发送，网络层有一个特殊的职责——路由选择。网络层的协议主要是IP协议，另外还有辅助协议如ICMP、IGMP。IP协议提供的是尽力而为服务，差错控制等功能由上层协议完成。
数据链路层负责数据帧的节点到节点的发送。数据链路层还负责跳之间的差错控制和流量控制。它使用物理或MAC地址来标识节点。
物理层完成在物理设备上的二进制比特的传输。
TCP/IP层从上到下进行封装，每一层都会在上一层的数据基础上加上头或尾。因此实际上物理层传输的数据会远远多于应用层的数据。
电子邮件（E-mail）使用的主要协议是简单邮件传输协议（STMP）。电子邮件使用的其他协议是POP和IMAP。文件传输协议（FTP）是因特网上最常见任务的标准机制，用于计算机的文件传输。FTP与其他客户/服务器应用的不同之处在于，它建立了两个连接：一个用于数据传输，另一个用于控制命令的交换。
TELNET是允许用户访问远程计算机上任何应用程序的通用客户/服务器程序。换言之，它允许用户登录到远程的计算机上。登录后，用户可以使用远程计算机上可用的服务，并把结果传回本地计算机上。
万维网（WWW）是分页在全球并连在一起的信息存储库。为了使用WWW，我们需要三个组件：浏览器、Web服务器和超文本传输协议（HTTP）。
WWW上的文档可以分成三大类：静态、动态和活动。静态文档是内容固定的文档，客户端只能得到文档的副本。动态文档是浏览器请求文档时由Web服务器创建的。通用网关接口（CGI）是创建和处理动态文档的技术。活动文档是运行在客户端的一个程序。
7 操作系统
计算机系统由部分组成：硬件和软件。软件分成两大类：操作系统和应用程序。操作系统是计算机硬件和用户（程序和人）和人一个接口，它便利其他程序更加方便有效地运行，并能方便地对计算机硬件和软件资源进行访问。操作系统的两个主要设计目标是硬件的高效使用和资源的使用方便。
操作系统的载入是一个自举过程，自举程序放在ROM中，开机之后载入ROM，然后把操作系统载入RAM内存。操作系统经历了一处长期的演化历史：批处理操作系统、分时操作系统、单用户操作系统、并行系统和分页式系统。
现代操作系统至少有四个功能区域：内存管理器、进程管理器、设备管理器、文件管理器。操作系统还提供与用户交互的功能，称为图形界面或者命令解释程序。
现代操作系统的第一职责是内存管理。内存必须由操作系统控制，以避免内存溢出。内存管理技术可以分为两类：单道程序和多道程序。在单道程序中，内存的大部分容量都为一个程序独享。在多道程序中，多个程序同时在内存中。
现代操作系统的第二职责是进程管理。进行是运行的程序。进程管理使用调度器和队列来管理进程。进程管理涉及具有不同资源的不同进程间的同步问题。这可能潜在地造成死锁和饿死。死锁是指一个进程由于其他进程无限制地使用资源导致无法运行的情况。饿死是指一个进程由于资源分配限制太多而不能执行的情况。
现代操作系统的第三职责是设备或I/O管理。在计算机系统中，输入/输出设备在数目和速度上都有限制。因为这些设备与CPU和内存相比，速度很慢，所以，当一个进程访问输入/输出设备时，它对其他进程就不可用。设备管理器负责输入/输出设备的高效使用。
现代操作系统的第四职责是文件管理。操作系统使用文件管理器来控制对文件的访问。只有进程或用户被允许访问指定文件时，访问才被允许。访问的类型可以改变。
具有一些类似性的两个常见的操作系统是UNIX和Linux。UNIX是多用户、多进程、可移植的操作系统，它由四部分构成：内核、命令解释器、一组标准工
具和应用程序。Linux由三部分组成：内核、系统工具和系统库。微软流行的操作系统家族是Windows NT。Windows NT是面向对象的、多层的操作系统。它使用几个层，包括：硬件抽象层（HAL）、执行层和环境子系统层。
8 算法
算法是一组明确步骤的有序集合，它产生结果并在有限的时间内终结。结构化的程序或算法由三种结构组成：顺序、判断（选择）和重复（循环）。常用的表示算法的工具是UML（统一建模语言，即流程图）、伪代码和结构图。结构图是显示算法和子算法之间关系的高级设计工具。
结构化编程的原则要求算法被分解成称为子算法的小单元。每个子算法依次又可以分成更小的子算法。
通常有两种方法编写求解问题的算法：迭代和递归。如果一个算法不涉及算法的本身，即引用算法自身，那它就是迭代，如果算法出现在它的定义中，也就是引用自身，那就是递归定义。递归定义本身包含循环。
9 程序设计语言
计算机语言是指编写程序时，根据事先定义的规则（语法）而写出的预定语句的集合。经过多年的发展，计算机语言已经从机器语言演化为高级语言。计算机唯一识别的语言是机器语言。机器语言的缺点是依赖于计算机，不同的硬件的机器语言不一样。另外就是编写程序不方便。
汇编语言通过引入符号或助记符的指令和地址来代替二进制代码。称为汇编程序的特殊程序用于将汇编语言代码翻译成机器语言。
高级语言使程序员专注于应用程序，而不是计算机组织的复杂性。高级语言必须转化为机器语言，这个转化的过程称为解释或编译。高级语言程序称为源程序，翻译过来的机器语言程序称为目标程序。编译程序是把整个源程序翻译成目标程序。解释分为两种方法，Java语言之前的解释是把源程序的每一行翻译成相应目标程序行，并执行，如果遇到错误就中止，再重新解释和执行。Java语言之后，为取得了可移植性，翻译过程分成两步进行：编译和解释，编译创建的是Java虚拟机（JVM）的目标代码，再通过JVM模拟器来进行编译或解释。
编译和解释的不同在于编译在执行前翻译整个代码，而解释一次只翻译和执行源代码中的一行。但两种方法的翻译过程都是一样的：先由**词法分析器**创建助记符表。再由**语法分析器**来找出指令，然后由**语义分析器**确保不会有二义性，最后由**代码生成器**生成代码。
模式是计算机用来处理问题的方法，计算机语言可分为4种模式：过程式（强制性）、面向对象、函数式和说明式。
在过程式模式中，程序是操纵被动对象的活动主体，被动对象本身不能开始动作，它从活动主体接收动作。数据或数据项就是被动对象。活动主体发布的动作称为过程。在过程式模式中，对象和过程是完全分开的实体。过程与程序触发不同，程序不定义过程，它只触发或调用过程，过程必须已经存在。当使用过程式高级语言时，程序只是由许多过程调用构成，除此之外没有任何东西。所以考虑过程和被作用的对象后，过程式模式的程序实际上由三部分构成：对象创建部分、一组过程调用和每个过程的一组代码。开发者可以建立新的过程。FORTRAN、COBOL、Pascal、C和Ada都是高级过程式语言的例子。
面向对象模式处理活动对象，而不是被动对象，对象可以进行的动作都包含在这些对象中，只需要接收合适的外部刺激来执行其中的动作就可以。与面向过程不同，过程式模式中的过程是独立的实体，而面向对象模式中的过程（称为方
法）是属于对象领域的。在面向对象模式中，相同类型的对象需要一组方法，要创建这组方法，面向对象语言使用了称为类的单元。方法的格式与过程式语言中的函数非常相似，有头、局部变量和语句。在面向对象语言中，一个对象能从另一个对象继承，称为继承性。如果定义了一个类，可以定义继承一些特性的更具体的类。在面向对象模式中，多态性是指可以定义一些具有相同名字的操作，而这些操作在相关类中做不同的事情。C++和Java是面向对象语言的例子，C++的设计遵循三条基本原则：封装、继承和多态。而Java是完全面向类操作的，在C++中可以不用定义类就能解决问题，而Java中每个数据项都属于类。Java中类的方法的调用由编译器来完成。Java另一有趣的特点的多线程，线程是按顺序执行的动作序列，C++只允许单线程地执行（整个程序作为单线程），而Java 允许多线程执行（几行代码同时执行）。
在函数式模式中，程序被看成一个数学函数，函数是把一组输入映射到一组输出的黑盒子，函数式语言主要实现以下功能
定义一系列可供任何程序员调用的原始（原子）函数
允许程序员通过若干原始函数的组合来创建新的函数
函数式语言相对过程式语言具有两方面的优势：它支持模块化的编程并且允许程序员使用已经存在的函数来开发新的函数。这两个因素使得程序员能够编写出庞大而且不易出错的程序。函数式语言的代表是LISP和Scheme。
说明式模式依据逻辑推理原则响应查询。由希腊数学家定义的规范的逻辑基础上发展而来，后来发展成为一阶谓词演算。说明性的语言的缺憾是要收集大量的论据信息，因此迄今也只局限于人工智能领域。代表语言是Prolog。
过程式与面向对象式的一些常见概念有：标识符、数据类型、变量、字面量、常量、输入和输出、表达式和语句。标识符可以用来代表数据的位置从而不用直接操作数据的地址。大多数语言使用两类控制语句：判断和重复。结构化的编程中强烈推荐三种结构：顺序、选择和重复。
子程序在过程式语言中相当重要。子程序中的变量在子程序返回时被销毁，程序和子程序之间进行通信是通过参数，在主程序中称为实际参数，在子程序中称为形式参数。参数的传递方式有两种：传值和传引用。在传值参数中，参数是以副本的形式由主程序单向传给子程序，从子程序到主程序没有参数的通信。其优点是不会改变主程序中的值。传引用则用于在子程序中改变主程序的值，在传引用的时候，实际上传递的是变量在内存的地址。在C和C++中，子程序被设计为函数。
10 软件工程
软件生命周期是软件工程中的一个基础概念，和其他产品一样，软件也周期性地重复着一些阶段。在软件的生命历程中，软件在被开发之后，使用和修改这两个步骤会一直持续到软件过时。过时是指软件失去它的有效性。
在软件的生命周期中，开发过程包括四个阶段：分析、设计、实现和测试。开发过程有多种模型，最常见的两种是瀑布模型和增量模型。在瀑布模型中，开发过程只有一个方向的流动，意味着前一阶段不结束，后一阶段不能开始。如设计阶段应该在实现阶段开始前完成。瀑布模型的优点在于下一阶段开始前前一阶段已经完成，因此设计阶段能准确知道要做什么，因为有分析阶段的全部结果；测试阶段能测试整个系统，因为整个项目已经完成，缺点就是难于定位问题，因为过程中的一部分有问题，必须检查整个过程。增量模型中，开发者首先要完成整个系统的简化版本，这个版本表示了整个系统，但不包括具体的细节。在第二
个版本中，，更多的细节被加入，然后测试，只有现有系统正确之后，再加入新的功能，ADIT的过程一直持续下去，直到要求的功能全部被加入。
- 开发过程始于分析阶段，这个阶段生成规格说明文档，说明软件要实现的目标，而没有说明如何去做。分析阶段可以使用两种方法：面向过程分析和面向对象分析。
面向过程分析也称为结构化分析或经典分析，使用过程式语言，可以使用的建模工具有：数据流图、实体关系图和状态图。
数据流图显示系统中数据的流动，使用了4种符号：方形盒表示数据源或数据目的、带圆角的矩形表示过程（数据中的动作或操作）、末端开口的矩形表示数据存储的地方、箭头表示数据流。
实体关系图是使用的另一个工具。
状态图通常用于系统中的实体状态在响应事件时将会改变的情况。
面向对象分析使用面向对象语言，使用的工具有：用例图、类图、状态图。
用例图给出系统的用户视图，它显示用户与系统间的交互，用例图使用四种组件：系统、用例、动作者和关系。系统（用矩形表示）执行功能。系统中的行动用用例显示，它用圆角矩形表示，动作是使用系统的某人或某事。
类图考虑的系统涉及的实体。
状态图与面向过程中的状态图起相同作用。
设计阶段定义了系统如何完成在分析阶段所定义的，在设计阶段，系统所有的组成部分都被定义。
面向过程设计既要设计过程，也要设计数据。在面向过程设计中，整个系统被分解为一组过程或模块。说明模块间关系的常用工具是结构图。模块化则是将大项目分解成较小的部分，把大程序分解成能互相通信的小程序。在分解模块时，主要关心的是耦合和内聚。耦合是两个模块互相绑定紧密程度的度量，为了便于模块重用、不容易影响相关模块以及便于修改，软件系统中的模块间的耦合必须最小化。内聚是程序中处理过程相关紧密程度的度量，软件系统模块间的内聚必须最大化。
面向对象设计中，设计阶段通过详细描述类的细节来继续，要列出类的属性和方法的细节。
在实现阶段，程序员为面向过程设计中的模块编写代码，或编写程序单元实现面向对象设计的类。对面向过程设计，一般使用纯过程语言如C，而面向对象设计中C++和Java的使用都很普遍。
软件质量非常重要，可以划分成三个广义的度量：可操作性、可维护性和可迁移性。
可操作性的度量标准有：准确性、高效性、可靠性、安全性、及时性和适用性。准确性一般用故障平均时间、每千行代码错误数、用户请求变更数等度量。高效性可用性能指标。可靠性最显著的是故障平均时间。适用性通常是通过用户访谈来完成。
可维护性以保持系统正常运行并及时更新为参照。通常用可变性、可修正性、适应性和可测试性来度量。
可迁移性是指代码重用的能力，一般用重用性、互用性、可移植性来度量。
测试阶段的目标是发现错误，好的测试策略可以发现最多错误，常用测试是白盒测试和黑盒测试。
白盒测试（或玻璃盒测试）是基于知道软件是内部结构的，测试的目标是检
查软件所有的部分是否全部设计出来。它假定测试者知道有关软件的一切。白盒测试由软件工程师或一个专门的团队来完成，要求满足下面4符标准：
①每个模块中的所有独立路径至少被测试过一次
②所有判断结构的每个分支都被测试
③每个循环都被测试
④所有数据结构都被测试
常见的测试方法有基本路径测试和控制结构测试。基本路径测试是创建一组测试用例，要求执行软件中的每条语句至少一次。基本路径测试使用略论和圈复杂性找到必须被走过的独立路径。控制结构测试分为条件测试，用来检查是否所有的条件都被正确设置；数据流测试用来检查赋值语言的左值；循环测试是用来检查循环的正确性。
黑盒测试是在不知道程序的内部也不知道程序是如何工作的情况下测试程序。黑盒测试按照软件应该完成的功能来测试软件。最好的测试方法是穷尽测试，用输入域所有可能的值去测试软件，但一般不现实。随机测试则是用输入域的子集来测试，子集选择的方式非常重要，随机数生成器非常有用。边界值测试是测试输入域的边界值。
文档关乎软件的正确使用和有效维护。软件通常有三种独立的文档：用户文档、系统文档和技术文档。文档是一个持续的过程，直到软件包过时后才停止编写。
用户文档告诉用户如何使用软件包和熟悉软件包的各种特性，一个好的用户手册对于软件的销售非常重要。
系统文档定义软件本身，其目的是为了让其他人员也能维护和修改软件包，系统文档在开发的的个阶段都应该存在。
分析阶段用于记录收集的信息，需求和使用的方法必须基于它们的推论来清楚描述。
设计阶段中记录最终版本中使用的工具和最终的结构图。
实现阶段中记录代码的每个模块，包含注释和描述。
测试阶段中包含对最终产品的每种测试及结果，即使是令人不快的结果。
技术文档描述软件系统的安装和服务，应该如何安装到服务器和客户端，应该如何维护和更新。
11 数据结构
数据结构代表了有特殊关系的数据的集合，本章讨论了三种数据结构：数组、记录和链表，大多数编程语言内置了前两种，第三种通过指针和记录来模拟。
数组是元素的顺序集合，通常这些元素具有相同的数据类型。使用索引可以访问数组中的元素。数组一般与循环一起使用，数组的索引从0开始。使用数组不会减少指令执行的次数，实际上还有增加，但大大减少了需要写的程序的数目。在数组中有两种不同类型的标识符：数组的的名字和各个元素的名字，元素的名字是数组名加索引。多维数组可以提供一些方便的操作，如按行平均、按列平均等。一维数组的索引直接定义了元素在实际存储上的相对位置，多维数组在内存中可以使用行主序存储或列主序存储，第一种更为常见。
数组上常见的操作有：查找、插入、删除、检索和遍历。无序数组的查找是顺序查找，有序查找的使用折半查找。数组大小一般不可变。对于插入操作，分为尾部插入和其他位置插入，尾部插入可以直接操作，其他位置插入需要进行查找之后，再将插入位置之后的元素从后开始向后移动完成之后再插入。删除操作
也是查找之后，将删除位置的元素向前移动；检索操作直接使用索引号就可以完成。数组的遍历使用循环完成。当删除和插入的量较少，而需要大量的查找和检索时，数组是一种合适的结构。数组是一种静态数组结构，所以当数据项的数目记录是一个相关元素的集合，这些元素可能是不同的类型，但整个记录有一个名称。记录中的每个元素称为一个域，域是记录中有意义的命名数据的最小元素。域不同于变量主要在于它是记录的一部分。记录中的元素可以是相同类型或者不同类型，但记录中所有元素必须是关联的。大多数编程语言中使用`.`来分隔结构名和它成员的名字。数组定义了元素的集合，而记录定义了元素可以确认的部分，如数组可以定义一个班的学生，而记录定义了学生不同的属性，如标识、姓名或成绩等。如果我们需要定义元素的集合，且同时还需要定义元素的属性，那可以使用记录数组。如`student[1].id`等。数组和记录数组都可以看成是数据项的列表，数组可以被看成是记录数组一种特例，其中每个元素是只带一个域的记录。
链表是一个有序数据的集合，其中每个元素包含两部分：数据和链。链是下一个元素的地址。列表的名字标识该列表中的第一个元素。链表最后一个元素包含一个空指针表示链表的结束。如果头指针为空，则此链表为空链表。链表中的元素习惯上称为节点。
数组与链表都能表示内存中的数据项列表，区别在于数据项连接在一起的方式，在记录数组中，连接工具是索引，而链表中的连接工具是指向下一元素的链。数组的元素在内存中是连续存储的，而链表中的存储是有间隔的，节点的链把数据项胶在一起。链表的链表名是头指针的名字，而节点名没有明显的名字，这就导致了链表的操作与数组的区别，链表也有与数组相同的操作。链表的搜索只能是顺序搜索，从头指针开始依次向后。插入操作是在找到插入位置之后，改变此位置指向的位置及原来指向的位置即可，操作分在空表中插入、在表开始的位置插入、在表的末尾插入和在表中间插入四种。删除操作是找到待删除的节点之后，改变前一个位置的指向即可，分为删除首节点和删除其他任何节点。检索链表则是依次检索。遍历链表需要用到步行指针来依次处理，到空指针时结束。
当数据将要进行大量的插入和删除操作时，链表是非常高效的结构，但搜索一个链表比搜索一个数组要慢。链表是一种动态的数据结构，表可以从无节点开始，当需要新的节点时，表逐渐增长。
12 抽象数据结构
虽然多种简单的抽象数据类型（如整数、实数、字符、指针等）在所有的编程语言中已经被实现，但大多数语言并没有定义复杂的数据类型。抽象数据类型（ADT）是一个定义新数据类型、定义该数据类型以及封装数据和操作的包。程序员应该知道抽象数据类型以及可以应用的操作，而不用关心这些操作是如何完成的。即这些操作的实现是隐藏的。抽象概念意味着知道一个数据类型能做什么，如何去做是隐藏的。
抽象数据类型是对该数据类型有意义的操作封装在一起的数据声明，然后，用它封装数据和操作并对用户隐藏。抽象数据类型包括数据的定义、操作的定义、封装数据和操作三部分。抽象数据类型的模型包括两部分，数据结构和操作函数（公有操作和私有操作）。应用程序只能通过接口访问公有操作，私有操作是抽象数据类型内部用户使用的，公有操作和接口应该独立于实现，但私有操作依赖于抽象数据类型实现时所选择的数据结构。
栈是一种限制线性列表，该列表中的添加和删除被限制在称为栈顶的一端进
行。栈的特性是后进先出(LIFO)，如果一组数据入栈再出栈，那它的顺序就颠倒了。栈的基本操作有四种：建栈、入栈、出栈和空。栈的应用包括四大类：倒转数据、配对数据、数据延迟使用和回溯步骤。倒转数据的应用如将一个十进制数转化为二进制数，余数先入栈再出栈，这样顺序就是正确的。配对数据的常见操作是括号配对，左括号入栈，当有右括号时出栈。通过检查栈是否为空可以确定是否完全配对。栈的实现可以用数组或者队列。
队列是一种限制线性列表，数据的插入只能在尾部进行，数据的删除只能在头部进行。队列的特性是先进先出(FIFO)，保证了通过队列的数据被处理的次序就是数据被接收的次序。队列的基本操作有四种：建队列、入列、出列和空。队列的应用非常广泛，如处理用户需求、任务和指令。完成对作业或对系统设备的处理等等。队列的实现可以用数组或链表来实现。
广义线性表是一种像插入和删除等操作可以在表其中任何位置进行的表。可以在头部、中间或尾部。广义线性表是具有如下特性的元素集合
元素具有相同的类型
元素按顺序排列，这意味着有第一个元素和最后一个元素。
除第一个元素外每个元素都有唯一的前驱；除最后一个元素外每个元素都有后继。
每个元素是一个带有关键字段的记录。
元素按关键字值排序。
广义线性表的基本操作有：建表、插入、删除、检索、遍历和空。广义线性表的搜索是在实现层上进行的，不是在抽象数据类型层上。广义线性表可应用于元素被随机存取或顺序存取的情况。广义线性表可以用数组或者链表来实现。
树包括一组有限的元素，称为节点（或顶点）。同时包括一组有限的有向线段，用来连接节点，称为弧。如果树非空，则有一个没有进入弧的节点称为根。树中的其他节点都可以沿着从根开始的唯一路径到达，该路径是指一系列相邻连接的节点序列。树中的节点可以分成三类：根、叶子和内部。根的进入弧为0，外出弧为0或更多，叶子的进入弧为1，外出弧为0，内部节点的进入弧为1，外出弧为1或更多。节点之间的关系有子节点、双亲、兄弟节点、祖先。树中的每个节点都有可能有子树。每个节点的子树含有子节点中的一个和这个子节点的所有子孙。
二叉对是一棵树，且其中没有一个节点所含有的子树的个数超过两个，每个节点只有有0、1、2棵子树。这些树称为左子树和右子树。二叉树的递归定义是：二叉树是一棵空树或由一个根节点和两棵子树构成，而每棵子树也是二叉树。二叉树的常用运算是：建树、插入、删除、检索、空和遍历。
二叉树的遍历要求按照预定的顺序处理每一个节点且仅处理一次。两种常用的遍历次序是深度优先和广度优先。深度优先遍历三种标准次序是：前序遍历（根->左子树->右子树）、中序遍历（左子树->根->右子树）、后序遍历（左子树->右子树->根）。注意这三种遍历都是递归定义的。在广度优先遍历中，是先处理节点的所有子节点，再处理下一层。处理次序是(根->左节点—>右节点)，其定义也是递归定义的。
二叉树的应用如Hoffman编码和表达式树。Hoffman编码是用二叉树来生成一个符号串可变长度的二进制编码。表达式树是将一个算术表达式建为一个表达式树，根和内部节点是操作符，而叶子是操作数。三种标准遍历（前序、中序、后续）分别产生三种不同的表达式格式：中缀、后缀、前缀。其中只有中缀表达
式需要括号。我们在编程语言里面使用中缀表示，而编译程序通常是使用后缀表示。二叉树的实现用链表实现的效率更高，所以也更流行。
二叉搜索树(BST)是一种具有额外特性的二叉树，每个节点的关键字值大于左子树中的所有节点的关键字值，而小于右子树中所有节点的关键字值。BST一个非常有趣的特性是：如果对BST进行中序遍历，被访问的元素以升序排列。BST 的另一个有起的特性是可以使用折半查找，这个效率非常高。BST表比广义线性表更为常见，原因就是搜索效率高。广义线性表中只能使用顺序查找。BST可以使用数组或链表来实现，但链表的效率更高。
图是由一组节点（称为顶点）和一组顶点间的连线（称为边或弧）构成的一种抽象数据类型。树是定义成层次结构的，节点只能有一个双亲，而图中的节点可以有一个或多个双亲。图可能是有向的或无向的。图的应用如计算机网络中路径的选择等。
13 文件结构
文件是作为一个单元看待的相关数据的外部集合，文件的主要目的是存储数据。因为当计算机关机后，主存的内容将丢失，所以我们需要文件用更永久的形式存储数据。文件被存储在辅助或二级存储设备上。文件在二级设备上可读写，文件也可以只能写不能读，如系统显示器上显示的信息，广义上，键盘也是文件，虽然它不能存储数据。文件是数据记录的集合，每一个记录都由一个或多个域组成。存取方法决定了记录如何被检索：顺序的或随机的。如果需要顺序地存取文件，那么使用顺序文件结构；如果需要存取一指定的记录而无需检索出该记录前的所有记录，那么使用随机文件结构。随机存取结构有索引文件和散列文件。
顺序文件是一种在其中每个数据必须按顺序从头到尾一个接一个地进行存取的文件。顺序文件必须周期性地更新，以反映出信息的变体。与更新程序相关联的文件有4个：新主文件、旧主文件、事务文件和错误报告文件。新的永久数据文件称为新主文件，需要更新的永久文件是旧主文件，即使在更新后，旧主文件作为参考将继续保留。事务文件包含将要对主文件作的改变。改变分为三类：添加事务、删除事务和更改事务。处理事务需要键，键是文件中一个或多个能唯一标识数据的字段。错误报告文件是更新过程中的错误清单。
索引文件由数据文件构成，该数据文件是顺序文件且是一个索引。索引本身是一个只有两个域的非常小的文件，两个域是顺序文件的键和磁盘上相应记录的地址。索引是根据数据文件的键值排序的。在散列文件中，散列函数将键映射成记录地址。存取文件中的记录按如下步骤进行：将索引文件载入到内存中，用高效算法（如折半查找）来搜索项目，检索记录的地址，按照地址检索数据记录并返回给用户。索引文件的好处之一就是可以有多个索引，每个索引有不同的键。多键索引文件称为倒排文件。
在索引文件中，索引将键映射为地址，而散列文件中，散列函数将键映射成记录地址。散列文件无需额外的文件（索引），但散列文件自身也有问题。散列可以采用多种方法。在直接方法中，键就是地址，不需要任何的算法运算。它的好处是不会有同义词或冲突问题。不好的是不是文件中全体元素都有数据，因此会造成空间浪费。在求模法中，键被文件的大小除，得到的余数加上1就是地址。在数字析取散列法中，选择的数据是从键中被析取出来的用作地址。
在散列过程中，有可能会出现多个键值散列到文件中的相同地址，这样就产生了冲突。常见的几种冲突解决办法是：开放寻址解决法（主区地址查找开放的或者空闲的记录来用于存放新数据，如把冲突的数据存在下一个地址中去，不好
的是增加了未来冲突的可能性），链表解决法是在一个地址中包含了指向下一条记录的指针，桶散列法是把冲突的记录散列到桶（桶是一能接纳多个记录的节点，这种缺点是可能有很多浪费的存储单元）。
目录是大多数操作系统提供的用来组织文件的。目录的作用就像文件柜中的文件夹。但是，在大多数操作系统中的目录被表示成为一个包含关于其他文件的信息的特殊文件类型。目录不仅像一种索引文件用于告诉操作系统文件在辅助存储设备上的位置，还包含了关于它所包含的文件的其他信息，如访问权限、创建者、存取日期和修改日期。在大多数操作系统中目录被组织成像树的抽象数据类型。Unix系统下的特殊目录类型有：根目录、主目录、工作目录和父目录。文存储在存储设备中的文件是一个二进制位的序列，它可以被应用程序翻译成文件文件或二进制文件。文本文件是字符文件，在它们的内存储器格式中不能包含整数、浮点数或其他数据结构。二进制文件是用计算机的内部格式存储的数据集合。二进制文件中的数据只有当被程序正确地解释时才有意义。
14 数据库
数据库是一个组织内被应用程序使用的逻辑相一致的相关数据的集合。数据库的优点有：冗余较少、避免不一致性、效率、数据完整性、机密性。数据库管理系统（DBMS）是定义、创建、维护数据库的一种工具。数据库管理系统由5部分构成：硬件、软件、数据、用户和规程。数据库是逻辑上相关的数据集合，而不是物理上的，它的各个部分在物理上是可以分开的。数据是独立于软件的一个实体。用户可以分为两类：最终用户和应用程序。最终用户又可以分为两类：数据库管理员(DBA)和普通用户。应用程序需要存取和处理数据。数据库管理系统的最后一个部分是必须被明确定义并由数据库用户遵循的规程或规则的集合。
ANSI/SPARC为数据库管理系统建立了三层体系结构：内层、概念层和外层。内层直接与硬件交互。概念层或称公用层定义数据的逻辑视图。外层直接与用户交互。
传统的三种数据库模型是层次模型、网状模型和关系模型。最终只有关系模型存活下来。成为数据库设计中最常用的模型。另外两种派生于关系模型的数据库模型是分布式数据库和面向对象数据库。
在关系数据库管理系统(RDBMS)中，数据通过关系的集合来表示。从表面上看，关系就是二维表。但这并不代表数据以表的形式存储。关系有下列特征：名称（每一种关系具有唯一的名称）、属性（关系中的每一列都称为属性，属性在表中是列的头，表示数据的含义，每一列在关系范围内有唯一的名称。关系中属性的总数称为关系的度）、元组（关系中的行叫做元组。关系中行的总数叫做关系的基数）。
在关系数据库中，我们能定义几个操作，根据现有的关系建立新的关系。在结构化查询语言SQL的上下文中，提到了9种操作：插入、删除、更新、选择、投影、连接、并、交和差。
插入是一元操作，用于插入新的元组，插入的格式如下：
insert into RELATION-NAME values (..., ..., ...)`，注意插入的值中字符串要用引号括起来，而数值就不需要了。
删除也是一元操作，用于插入相应的元组。删除的格式如下：
delete from RELATION-NAME where CRITERIA
更新也是一元操作，用来更新元组中的部分属性值，更新格式如下：update RELATION-NAME set attribute1 = value1, attribute2 = value2, ...
where CRITERIA
选择也是一元操作，它应用于一个关系并产生另外一个关系，新关系中的元组是原关系元组的子集，选择的格式如下`select * from RELATION-NAME where CRITERIA`.选择的属性可以少一些。
投影也是一元操作，它应用于一个关系并产生另外一个新关系，新关系中的属性是原关系属性的子集。属性数减少，但元组的数量保持不变。操作格式如下`select attribute-list from RELATION-NAME`.
连接是二元操作，它基于共有的属性把两个关系组合起来，连接操作的格式如下`select attribute-list from RELATION1, RELATION2 where CRITERIA` 并也是二元操作，它将两个关系组合并成一个新的关系，限制条件是它们必须拥有相同的属性。操作格式如下`select * from RELATION1 union select * from RELATION2`
交也是二元操作，它对两个关系进行操作，创建一个新关系，这两个关系必须具有相同的属性。操作格式如下`select * from RELATION1 intersection select * from RELATION2`
差也是二元操作，它应用于具有相同属性的两个关系，生成的关系中的元组是那些存在于第一个关系中而不在第二个关系中的元组。操作格式如下`select * from RELATION1 minus select * from RELATION2`
数据库的设计是一个冗长且只能一步步来完成的任务。第一步通常涉及与数据库潜在用户的面谈，去收集需要存储的信息和每个部门的存取需求。第二步就是建立一个实体关系模型(ERM)，这种模型定义了一些信息需要维护的实体。下一步就是建立基于ERM的关系。在实体关系图(ER图)使用的几何图形中，矩形表示实体集，椭圆形表示属性，菱形表示关系集，线连接属性和实体以及连接实体集和关系集。
规范化是一个处理过程，通过此过程给定的一组关系转化成一组具有更坚固结构的新关系。规范化要允许数据库中表示的任何关系，要允许像SQL这样的语言去使用由原子操作组成的恢复操作，要移除插入、删除和更新操作中的不规则，要减少不娴的数据类型被加入时对数据库重建的需要。规范化的过程定义了一组层次范式，包括1NF、2NF、3NF、BCNF、4NF和5NF等，这些范式组成一个层次结构，层次越高，难度越大。
关系数据库不是当今唯一的数据模型，两个其他常见模型是分布式数据库和面向对象数据库。
15 数据压缩
数据压缩方法分为无损压缩（所有信息都可恢复）和有损压缩（部分信息丢失）。在无损压缩方法中，接收的数据是发送数据的完全复制。三种无损压缩方法分别是流程长度编码、Hoffman编码和LZ编码。
游程长度编码不需要知道字符出现频率的相关知识，并且当数据仅由0和1表示时十分有效。大致思想是将数据中连续重复出现的符号用一个字符和这个字符重复的次数来代替。在位模式中，如果数据只有两种符号，且一种符号比另一种符号使用更为频繁，那么这种压缩方法就更有效，如标记在两个1之间有多少个0，个数用4位二进制数来表示，多于15默认下一个仍表示0的数目，刚好15是加一个0000。
Hoffman编码是对出现更为频繁的字符分配较短的编码，对于出现较少的字符分配较长的编码。分配过程是建立一个二叉树，将最小概率的两个点组成二叉
树，将顶点值（二者之和）作为新值，再建树。Hoffman编码是一种即时的编码，它的特点是没有一个编码是其他编码的前缀。这样译码器可以即时明确地翻译出编码。
LZ编码是基于字典编码的算法的例子。在压缩阶段，需要同时做两件事：建立字典索引和压缩字符串。算法从未压缩的字符串中选取最小的子字符串，这些子字符串在字典中不存在。然后把子符串复制到字典并分配索引值，压缩时，除了最后一个字母之外，其他所有字符被字典中的索引代替，然后将索引和最后一个字母插入压缩字符串。
在有损压缩中，接收的数据并不需要是所发送数据的完全复制。本意讨论的三种有效有损压缩方法分别是JPEG、MPEG和MP3。
联合图像专家组(JPEG)是一种用来压缩图形和图像的方法。JPEG过程包括划分块、离散余弦变换、量化及无损压缩。有损压缩的损耗出现在量化这一步上。
运动图像专家组(MPEG)是一种用来压缩视频的方法。MPEG包括空间和时间压缩。前者和JPEG相似，后者则去掉了多余的帧。
MPEG第三代音频压缩格式(MP3)是MPEG标准的一部分。MP3使用感知编码技术压缩CD质量的音频。
16 安全
我们提到的三个安全目标：机密性、完整性和可用性。安全攻击分成三大类：为了实现安全目标和防止相应的攻击，ITU-U定义了下列的服务：数据机密性、数据完整性、身份验证、不可否认性和访问控制。两种技术被用来提供这些服务：密码术和隐写术。
对称密钥密码术使用一个密码进行加密和解密。Alice和Bob首先要认可一个共享的秘密，这个秘密构成了他们的密钥。为了发消息给Bob，Alice使用密钥加密消息；为了发消息给Alice，Bob使用相同的密钥加密消息。传统对称密钥密码是面向字符的，使用两种技术向入侵者隐藏信息：替换和置换。现代对称密钥密码是面向二进制位的，使用非常复杂的算法来加密和解密二进制位块。
非对角密钥密码术使用两个不同的密钥：私钥和公钥。Bob首先创建一对密钥，然后保存私钥，声明公钥。如果有人需要给Bob发送消息，那他就可以使用Bob的公钥进行加密，为了阅读消息，Bob使用他的私钥解密消息。
完整性就是保护信息免受修改。为了保持消息的完整性，消息要经过一个称为密码散列函数的算法。这个函数创建了消息的压缩影像，称为消息摘要。为了提供消息验证，需要消息验证代码(MAC)。MAC包含发送者和接收者共享的秘密。
数字签名是电子地签署文档的过程。它提供消息完整性、消息验证和不可否认性。
实体验证是一种用来让一方证明另一方身份的技术。实体验证使用三类验证：所知道的、所拥有的和所固有的。我们提到了四种验证技术：基于口令、质询-响应、零知识和生物测定。
对于对称密钥或非对称密钥密码术，双方都需要交换密钥。密钥管理方法允许我们交换密钥，而不需要面对面的密钥交换。在对称密钥密码术中，实用的解决方案是密钥分发中心(KDC)的使用。在非对称的密钥密码术中，实用的解决方案是使用谁机构(CA)的证书。
17 计算理论
我们可以定义一种只有三种语句的计算机语言：递增语句、递减语句和循环语句。递增语句给变量加1，递减语句给变量减1，循环语句是在变量的值不为
0时，重复一个动作或一系列动作。我们可以证明这种简单的语言能模拟一些流行语言中的多个语句。我们把每个模拟称为一个宏，它可以在其他模拟中使用，而不需要重复编码。
图灵机是为解决可计算问题而设计的，它是现代计算机的基础。图灵机由三部分组成：磁带、控制器和读写头。图灵机可以模拟简单语言的操作。邱奇-图灵论题是说：如果存在一个能完成一个符号操纵任务的算法，那么也存在一台完成这个任务的图灵机。这个论题无法得到证明，但是已经有论题支持，首先是尚未发现有图灵机不能模拟的算法，其次，所有在数学上已经得到证明的计算机模型都与图灵机等价。
在计算机科学理论中，在具体的计算机语言中，一个分配给任何程序的无符号数称为歌德尔数，这种分配有许多优点，首先，程序可以作为单一数据项输入给其他程序，第二，程序可以通过它的整数表示来引用，第三，该编号方式可以用来证明有一些问题计算机并不能解决，从而说明世界上问题的数量远远比曾经编写的程序数量要多得多。
一个经典的编程问题是：能否编写一个程序来测试任何可以用歌德尔数表示的程序是否会终止吗？不幸的是已经证明了这样的程序是不存在的，停机问题是不可解的（停机是指一个重复结构可能永远都不会结束）。停机问题不可解已经证明了许多其他的问题也是不可解的，因为它们可解那么停机问题也可解。
在计算机科学领域，问题可以分为两类：可解问题和不可解问题，可解问题又分为两种：多项式问题和非多项式问题。要证明一个问题是无法解决的，方法是证明如果它可以解决，那么停机问题也同样可以解决。换句话说，证明一个问题能否等同于证明停机总理能否解决。可解问题的复杂度的一种衡量方法是时间复杂度，用*大O表示法*显示。如果一个程序的复杂度为O(logn)、O(n)、O(n^2)、O(n^3)、O(n^4)或O(n^k)，则被称为多项式问题，即时间复杂度是多项式级别。如果一个程序的复杂度远比多项式复杂，如O(10^n)或O(n!)，则称为非多项式问题。
18 人工智能
人工智能是编程系统的研究，它能在一定程度上模仿人类的活动，如感知、思考、学习和动作。定义人工智能的一种方法是图灵测试，它比较人类和机器的智能行为。一个询问者对计算机和人类都提出一组问题，然后得到两组答案，但他不知道哪一组是来自人类，哪一组是来自计算机，在仔细检查答案之后，如果询问者无法区分哪一组来自人类，哪一组来自计算机，那么该计算机就通过了具有智能行为的图灵测试。
智能体是一个能感知环境、从环境中学习并智能地与环境交互的系统。智能体可以分为两大类：软件智能体和物理智能体。软件智能体是一组用来完成特殊任务的程序，如组织电子邮件、搜索引擎。物理智能体是一个用来完成各项任务的可编程系统。
虽然通用的语言（如C、C++和Java）能用来创建智能软件，但有两种专门为人工智能设计的语言：LISP和PROLOG。LISP把数据和程序都当成表，这就意味着LISP能改变它自身，这个特性与智能体的理念相吻合。智能体能从环境中学习并改善自身行为。PROLOG能使用逻辑推理来回答那些可以从知识库推导出来的问题。
知识表示是人工智能的第一步。我们讨论了四种常见的知识表示方法：语义网络、框架、谓词逻辑和基于规则的系统。
语义网使用有向图来表示知识，有向图由顶点和边构成，顶点表示概念、边表示两个概念之间的关系。概念是一个集合或一个子集，边可以定义一个实例关系（从实例指向它所属的集合），也可以定义一个对象的属性，还可以定义一个框架与语义网紧密相关。在语义网中，图用来表示知识；在框架中，数据结构（记录）用来表示相同的知识。框架的优点是程序更容易处理框架，而不是语义网。语义网中的一个节点变成一组框架中的一个对象，边被翻译成槽。
谓词逻辑是最常见的知识表示。从已知的事实推导出新的事实的过程称为推演。如果找不到反例，那么这个论断就是合法的。谓词逻辑使用了命题逻辑。超谓词逻辑包括高阶逻辑、默认逻辑、模态逻辑和时态逻辑。
基于规则的系统使用一组规则来表示知识，这些规则能用来从已知的事实中推导出新的事实。它由三部分构成：解释器（或推理器）、知识库和事实库。知识库是规则的数据库，事实库是知识库中的规则要使用的一组条件，解释器是一个处理器，它把规则和事实组合在一起。解释器有两种类型：正向推理和反向推理。
人工智能的一个目标是建立专家系统，完成通常需要人类专家经验的任务。它们可以用在人类专家缺少、昂贵或者不可用等场合。专家系统是建立在预先定义的相应领域专家经验的基础上的。知识的抽取过程通常是由知识工程师来完成的。为了能推导新的事实或采取动作，除了需要用知识表示语言表示的知识库外，还需要事实库。一个专家系统由7个部分组成：用户、用户界面、推理器、知识库、事实库、解释系统和知识库编辑器。
人工智能的另一个目标是创造行为像普通人类的机器，这个目标的第一部分涉及图像处理或计算机视觉，这是处理对象感知的一个人工智能领域。目标的第二部分是自然语言的语言处理、分析和翻译。
图像处理的第一步是边缘探测，去查找图像中的边缘在哪里。通常属于对象的表面和环境间是存在着明显的反差的。最简单的方法是分层亮度矩阵。分段是图像分析的下一步，分段的方法的方法有阈值化、分割和合并。接下来的一步是查找对象的深度或是图像中的对象。深度的查找可以帮助智能体测量对象距它多远。有两种常用的方法：立体视觉和运动。场景中的对象的方向可以用两种技术来发现：光照和纹理。图像处理的最后一步是对象识别。
语言理解分成四个连续的步骤：语音识别、语法分析、语义分析和语用分析。语音识别的目的是将语音转化为单词序列。语法分析这一步用来定义单词在句子中是如何组织的，正确分析句子第一步是良好定义的方法，然后使用词法分析器进行分析。语义分析是提取出句子的意思。语用分析是用来进一步明确句子的意图和消除歧义。
在人工智能中，问题求解的一种技术是搜索。搜索可以描述成使用一组状态（情形）求解一个问题。有两大类搜索，分别是蛮力搜索和启发式搜索。
如果智能体应该表现得像人类一样，那么它可能就需要学习。已经使用的方法中有几种为未来建立了希望。大多数方法使用归纳学习和从例子中学习。一个通常的方法是使用神经网络，使用神经网络试图模仿人脑的学习过程。
1计算机内存容量为512MB，它一共有多少个二进制位？ 512*1024*1024*8 2请说出三种计算机输入设备的名称，以及它们各自的特点或功能。 ①鼠标：是一种指点式命令输入设备，可极大地方便软件操作，尤其适用于图形操 系统环境下。②键盘：最主要的用途是输入文字和数字。③图像扫描仪：利用扫描仪，可以将印刷材料转换成数字格式，使其能够保存于计算机系统。 3请说出三种计算机输出设备的名称，以及它们各自的特点或功能。 ①打印机：是计算机产生硬备份输出的一种设备。②显示器：用户可以通过显示器方 便地观察输入和输出的信息。③音箱：可以将计算机内以数字形式存放的声音信息 转换成人类可以听到的机械振动的声音。 4什么是计算机网络？它有哪些基本功能？ 计算机网络是用通信设备和线路将分散在不同地点的，有独立功能的多个计算机系统互相连接起来，按照网络协议进行通信，实现资源共享的计算机的集合。计算机网络有如下功能：①信息传输；②资源共享；③分布式处理；④提高可靠性。 5计算机网络分别按照覆盖范围和拓扑结构可以划分哪几种？有何特点？ 计算机网络按覆盖范围可分为：①广域网，特点：几十千米到几千千米；②局域网，特点：10千米以内；③城域网，特点：几十千米以内。 计算机网络按拓扑结构可分为：①星型网络，特点：各节点通过通信线路直接与中心节点连接；②总线型网络，特点：所有节点都连接到一条公共传输线上；③树形网络，特点：节点按照层次连接，形成一个树状结构。④环形网络，特点：各节点通过通信线路连接成一个闭合的环。⑤网状型网络，特点：每个节点至少有两条线路和其他节点相连。 6Modem是计算机连网的一个主要设备，简述其功能及适合场合。 modem的功能包括两个方面：一是调制功能，将计算机输出的数字信号转换成适合电话线传输的模拟信号；另一个是解调功能，将电话线上传输的模拟信号转换为数字信号后给计算机处理。适用场合是利用modem通过普通电话线拨号上网。 7什么是ADSL？与传统的拨号上网方式相比，它有哪些优点？ ADSL是不对称数字电话线，是一种新型的宽带接入技术。与传统的拨号上网上网方式相比，传输速率大大提高。通过频分复用技术，同时分别传输语音、上行数据和下行数据三路信号。 8什么是IP地址？它由几部分组成？通常分为哪几类？如何识别？ IP地址是接入Internet的计算机拥有的一个由授权单位分配的唯一号码。它由网络号和主机号两部分组成，通常分为三类，即A类、B类和C类，通过IP地址中的第一个字节来识别，A类地址的范围在1～126，B类地址的范围在128～191，C类地址的范围在192～223。 9指出下列因特网应用层协议的作用：HTTP、SMTP、POP3、FTP、TELNET。 HTTP:进行网页多媒体数据的传送. SMTP:收发电子邮件,只能传送ASCII字符 POP3:
计算机科学导论 第1章 1、数据的定义：数据是客观事物属性的记录表示 2、数据的形式：数、文字、图像、图形、视频和音频 3、常见的数据存储介质：磁盘、光盘、磁带、内存储器、早期用过的纸质穿孔带和穿孔卡 4、信息产生三要素：（信息）源、理解规则、接收者 5、信息是数据的内涵，数据是信息的外在形式。 6、数据处理的基本环节：收集、录制和输入、加工、输出、存储、传输（图4页） 7、计算机作为数据处理机：输入设备、输出设备、存储器、中央处理器（CPU）、总线 8、计算机的应用领域：科学计算、（狭义的）数据处理、自动控制、制造业、通信业、办公自动化、娱乐、人工智能 9、提出现代化计算机体系结构的鼻祖是冯·诺依曼。 第2章 1、从数据处理功能的角度，可以把计算机硬件设备可分成四大部分：内存、CPU、输入输出设备和总线。 2、单元地址是内存单元在硬件层次的唯一标识。 3、内存储器的种类：随机存取存储器（RAM）、只读存储器（ROM）、高速缓冲存储器（cache） 4、CPU的主要组成部件：算术逻辑运算器（ALU）、控制器、寄存器 5、输入设备：字符输入设备、定位设备、扫描设备 6、输出设备：显示器、打印机、绘图仪 7、系统总线的类型：数据总线、地址总线、控制总线 8、微机的总线标准：ISA总线、PCI总线、USB总线 9、冯·诺依曼结构把存储器分为4级，即外存→内存→高速缓存→寄存器（图50页） 第3章 1、操作系统的资源管理对象主要是指CPU、内存、I/O设备和外存数据。 2、操作系统把资源管理相应地分为4个部分：CPU管理、存储器管理、设备管理、文件管理 3、作业的管理调度方式：单道作业方式、多道作业批处理方式、分时方式 4、I/O设备的输入输出控制 (1)程序控制输入输出 (2)中断控制输入输出 (3)直接存储器存储 （1）通道处理器和外围处理机 5、操作系统的常见类型 (1)多用户系统
《计算机科学导论》第2次作业答案 （第8章—第15章） 一、选择题 1．与批处理系统相比较，分时系统的最大优点在于( )。[A] A. 具有交互性 B. 资源利用率高 C．吞吐量大 D. 输入设备和输出设备 2．有一个128MB的应用程序，要在64MB的物理内存中运行，要求操作系统具有 的功能是（）。[D] A．磁盘管理 B. 进程管理 C. 内存保护 D. 虚拟存储 3. 以下不可能发生的进程状态转换是( )。[B] A．就绪态到运行态 B. 阻塞态到运行态 C. 运行态到阻塞态 D. 运行态到就绪态 4. 采用树形文件目录结构的主要目的是( )。[D] A．提高文件搜索效率 B．允许文件重名 C．便于文件分类 D．既可提高文件搜索效率，又可解决文件重名问题 5．关于死锁，以下说法错误的是( )。[A] A．多个进程并发使用独占设备，就一定会死锁 B．多个进程并发使用独占设备，只要安排一个合适的执行顺序，就不会死锁 C．对于不同的设备特性，在处理关于死锁的问题上，可以采取不同的解决策略D．死锁发生后，一定有多个进程处于永久等待状态 6．在OSI七层结构模型中，处于数据链路层与运输层之间的是( )。[B] A．物理层B．网络层C．会话层D．表示层 7．局域网中最常用的有线通信媒体是( )。[A] A．双绞线和基带同轴电缆 B. 基带同轴电缆和宽带同轴电缆 C．宽带同轴电缆和双绞线D．光缆和宽带同轴电缆 8．防火墙能提供（）服务。[ABCD] A．服务控制 B. 方向控制 C. 用户控制 D. 行为控制 9．在TCP／IP协议簇中，UDP协议在( )工作。[B] A．应用层 B. 传输层 C. 网络互联层 D. 网络接口层 10. 在IP地址方案中，159. 226.181.1是一个( )。[B] A . A类地址B．B类地址C．C类地址 D. D类地址 11．常见的图形图像包括（）。[ABC] A．GIF B. JPEG C. TIFF D. RMVB 12．运用计算机图形学和图像处理技术，将数据转换为图形或图像在屏幕上显示出来并进行交互处理的理论、方法和技术是( )。[C] A．人机交互技术C．现代的数据可视化技术 B．虚拟现实技术D．多媒体技术 13．当前用户界面的主流是（）。[B] A. 命令语言交互界面 B. 图形用户交互界面 C. 多媒体人机交互界面 D. 多通道人机交互界面
2011年计算机导论修订第二版课后练习答案 第一章一、简答题 1、什么是计算机？ 计算机系统是一种能够按照事先存储的程序，自动、高速的对数据进行输入、处理、输出和存储的系统。一个计算机系统包括硬件和软件两大部分。 2、解释冯·诺依曼所提出的“存储程序”概念。 把程序和数据都以二进制的形式同意存放在存储器中，由机器自动执行。不同的程序解决不同的问题，实现了计算机通用计算的功能， 3、计算机有哪些主要的特点？ 运算速度快`精度高 计算机的字长越长，其精度越高，现在世界上最快的计算机每秒可以运算几十万次以上。一般计算机可以有市纪委甚至几十位（二进制）有效数字，计算精度可由千分之几到百万分之几，是任何计算工具所望尘莫及的。具有逻辑判断和记忆能力 计算机有准确的逻辑判断能力和高超的记忆能力。能够进行各种逻辑判断，并根据判断的结果自动决定下一步应该执行的指令。高度的自动化和灵活性 计算机采取存储程序方式工作，即把编号的程序输入计算机，机器便可依次逐条执行，这就使计算机实现了高度的自动化和灵活性。 4、计算机有哪些主要的用途？ （1）科学计算（2）数据处理 (3) 实时控制（4）人工智能 （5）计算机辅助工程和辅助教育（6）娱乐和游戏 5、计算机发展中各个阶段的主要特点是什么？第一代计算机特征是采用电子管作为主要元器件第二代计算机特征是采用晶体管作为主要器件 第三代计算机特征是半导体中小规模集成电路第四代计算机特征是大规模和超大规模集成电路 6信息化社会的主要特点是什么？ 1·建立完善的信息基础设施 2·采用先进的信息技术 3·建立广泛的信息产业 4·拥有高素质的信息人才 5·构建良好的信息环境 7、信息化社会对计算机人才的素质和知识结构有哪些要求？ 在信息化社会中所需要的计算机人才是多方位的，不仅需要研究型、设计型的人才，而且需要应用型的人才；不仅需要开发型人才而且需要维护型、服务型、操作型的人才。要求计算机人才具有较高的综合素质和创新能力，并对于新技术的发展具有良好的适应性。 8、说明计算机科学与技术学科的知识体系及知识领域、知识单元和知识点的含义。 9计算机科学的研究范畴主要包括哪些？ 计算机科学技术的研究范畴主要包括计算机理论、硬件、软件、网络及其应用等。二、选择题 1 计算机是接受命令，处理输入以及产生【数据】的系统 2 冯·诺依曼的主要贡献是【提出了存储程序概念】 3 共科学研究，军事和大型组织用的高速，大容量计算机是【巨型计算机】 4 计算机硬件由5个基本部分组成，下面【总线】不属于这5个基本组成部分 5 其内容在电源断掉以后就消失又被暂时存储器的条件是【内存储器】 6 拥有高度结构化和组织化的数据文件被称为【数据库】 7 计算机系统必须具备的两部分是【硬件和软件】 8 计算机处理的5个要素是【输入，输出，处理，打印和存储】
写给同学们的几点说明： 1>关于教材 由于《计算机科学导论》课程涉及的内容广泛，任何一本教材均无法完全覆盖所有知识点。所以同学们在复习时应该以教学课件为主，指定教材仅供辅助参考使用。本复习资料提供的例题将全部指明其所考知识点在教学课件中的章节和页码。 2.关于考试题型和试卷结构 单项选择（10道题、每题2分、共20分）； 判断题（5道题、每题2分、共10分）； 名词解释（6道题、每题5分、共30分）； 简答题（3道题、每题10分、共30分）； 分析设计题（1道题、每题10分、共10分）。 3.关于考试范围 全部试题涉及的知识点在教学课件中均有体现，在本复习资料中也有示例。 一、客观部分：（单项选择、判断） （一）、选择部分 1、17世纪，（A ）发明了第一个数字计算器 A、Pascal B、Leibniz C> Jacquard D、Babbage ★考核知识点：计算硬件的发展历程（第1章PPt第21页） 2、内存的概念首次出现在（B ）当中 A、算盘 B、分析机 C、织布机 D、数字计算器 ★考核知识点：计算硬件的发展历程（第1章PPt第22页）
3、第一代计算机使用（A ）存储信息 A、真空管 B、品体管 C、集成电路 D、光纤 ★考核知识点：计算硬件的发展历程（第1章PPt第25页） 4、下列哪种语言是面向对象的编程语言（D ） A、Pascal B、BASIC C、C D、C++ ★考核知识点：计算软件的发展历程（第1章ppt第35-36页） 5、满足个人应用要求，体积小、价格便宜的计算机属于（A ） A、个人计算机 B、小型计算机 C、大型计算机 D、超级计算机 ★考核知识点：计算机的类型（第1章PPt第80页） 6、下列选项中不属于计算机存储设备的是（C ） A、内存 B、光盘 C、磁盘驱动器 D、U盘 ★考核知识点：计算机硬件设备（第1章ppt第83页） 7、在计算机软件层次结构小，位于汇编语言内层的是（D ） A、应用软件 B、操作系统 C、高级语言 D、机器语言 ★考核知识点：计算机软件层次（第1章PPt第89页） 8、数字836的基数可能是（D ） A、2 B、5 C、7 D、10 ★考核知识点：位置计数法（第2章ppt第5页）
《计算机科学导论》 实验指导书 欧阳一鸣王浩编 合肥工业大学计算机与信息学院 《计算机科学导论》实验 《计算机科学导论》实验课侧重培养学生的基本应用能力，要求学生通过上机实验，能够熟练掌握计算机的基本操作技能。该实验指导书共安排六个实验，内容包括：Windows的基本操作、使用Word 进行文字处理、利用Excel进行表格编排等等。要求学生做完实验后，写出实验报告，实验报告上需要写明的项目包括：实验名称、实验目的、实验设备、实验题目、实验步骤、实验结果。 实验一 Windows 基本操作 1.实验目的和要求 (1)掌握Windows 的启动和安全退出的方法。 (2)掌握Windows 的窗口、菜单栏、工具栏及任务栏的基本操 作。 (3)掌握Windows 常用快捷键的使用方法。 (4)掌握应用程序的多种启动方法以及切换和退出应用程序的 方法。 (5)掌握Windows 环境下的汉字输入方法。 (6)掌握Windows 帮助的使用。 (7)实验内容
(8)启动Windows ，打开“我的电脑”窗口，熟悉Windows 窗 口组成，然后对窗口作下列操作： 1)移动窗口。 2)改变窗口的大小、使滚动条出现，然后滚动窗口的内容。 3)最大化、最小化、复原和关闭窗口。 (9)打开“控制面板”窗口，再打开“控制面板”中的“字体” 窗口，然后进行下列操作： 1)通过任务栏和快捷键切换当前的窗口。 alt + tab 或alt +esc 2)以不同方式排列已打开的窗口（层叠、横向平铺、纵向平铺）。 3)在“我的电脑”窗口中，单击“查看”菜单下的“大图标”、 “小图标”、“列表”“详细资料”命令项，观察窗口中的各 项的变化。用工具栏上的“查看”命令按钮重复做一遍。 (10)通过二种方法查看当前的日期和时间，如果日期和时间不 正确，请进行修改。 (11)分别通过以下方法启动“画图”程序（windows-xp下程序 文件路径为" C:\WINDOWS\system32 \mspaint.exe" ，在windows2000下程序文件路径为" C:\WINNT\system32 \mspaint.exe"），然后退出该程序。 1)通过“开始”菜单→“程序”→“附件”，启动“画图”程
大学计算机科学导论论文 计算机科学与技术这一门科学深深的吸引着我们这些同学们，原先不管是国内还是国外都喜欢把这个系分为计算机软件理论、计算 机系统、计算机技术与应用。后来又合到一起，变成了现在的计算 机科学与技术。我一直认为计算机科学与技术这门专业，在本科阶 段是不可能切分成计算机科学和计算机技术的，因为计算机科学需 要相当多的实践，而实践需要技术;每一个人(包括非计算机专业)， 掌握简单的计算机技术都很容易(包括原先Major们自以为得意的程 序设计)，但计算机专业的优势是：我们掌握许多其他专业并不"深究"的东西，例如，算法，体系结构，等等。非计算机专业的人可以 很容易地做一个芯片，写一段程序，但他们做不出计算机专业能够 做出来的大型系统。今天我想专门谈一谈计算机科学，并将重点放 在计算理论上。 1)计算机语言 (2)计算机模型与软件开发方法 在各种实际应用系统的开发中，有一个重要的方向值得注意，即实时系统的开发。 数据库技术、多媒体技术、图形学技术等的发展产生了两个新方向，即计算可视化技术与虚拟现实技术。 计算机理论的一个核心问题 正如上面所论述的，计算机系的学生学习高等数学：知其然更要知其所以然。你学习的目的应该是：将抽象的理论再应用于实践， 不但要掌握题目的解题方法，更要掌握解题思想，对于定理的学习：不是简单的应用，而是掌握证明过程即掌握定理的由来，训练自己 的推理能力。只有这样才达到了学习这门科学的目的，同时也缩小 了我们与数学系的同学之间思维上的差距。 大学计算机科学导论论文范文二：大学计算机科学导论论文
计算机科学与技术这一门科学深深的吸引着我们这些同学们，原先不管是国内还是国外都喜欢把这个系分为计算机软件理论、计算 机系统、计算机技术与应用。后来又合到一起，变成了现在的计算 机科学与技术。我一直认为计算机科学与技术这门专业，在本科阶 段是不可能切分成计算机科学和计算机技术的，因为计算机科学需 要相当多的实践，而实践需要技术;每一个人(包括非计算机专业)， 掌握简单的计算机技术都很容易(包括原先Major们自以为得意的程 序设计)，但计算机专业的优势是：我们掌握许多其他专业并不"深究"的东西，例如，算法，体系结构，等等。非计算机专业的人可以 很容易地做一个芯片，写一段程序，但他们做不出计算机专业能够 做出来的大型系统。今天我想专门谈一谈计算机科学，并将重点放 在计算理论上。 1)计算机语言 随着20世纪40年代第一台存储程序式通用电子计算机的研制成功，进入20世纪50年代后，计算机的发展步入了实用化的阶段。 然而，在最初的应用中，人们普遍感到使用机器指令编制程序不仅 效率低下，而且十分别扭，也不利于交流和软件维护，复杂程序查 找错误尤其困难，因此，软件开发急需一种高级的类似于自然语言 那样的程序设计语言。1952年，第一个程序设计语言ShortCode出现。两年后，Fortran问世。作为一种面向科学计算的高级程序设 计语言，Fortran的最大功绩在于牢固地树立了高级语言的地位， 并使之成为世界通用的程序设计语言。Algol60的诞生是计算机语 言的研究成为一门科学的标志。该语言的文本中提出了一整套的新 概念，如变量的类型说明和作用域规则、过程的递归性及参数传递 机制等。而且，它是第一个用严格的语法规则——巴科斯范式(BNF) 定义语言文法的高级语言。程序设计语言的研究与发展在产生了一 批成功的高级语言之后，其进一步的发展开始受到程序设计思想、 方法和技术的影响，也开始受到程序理论、软件工程、人工智能等 许多方面特别是实用化方面的影响。在“软件危机”的争论日渐平 息的同时，一些设计准则开始为大多数人所接受，并在后续出现的 各种高级语言中得到体现。例如，用于支持结构化程序设计的PASCAL语言，适合于军队各方面应用的大型通用程序设计语言ADA，
龙源期刊网 https://www.doczj.com/doc/4c7479889.html, 关于《计算机科学导论》课程教学的思考 作者：乐天 来源：《中国信息技术教育》2013年第04期 摘要：《计算机科学导论》课程是计算机专业的入门课，为专业后续课程的学习起着引导作用。本文指出《计算机科学导论》课程教学中存在的问题，并对该课程的教学内容、教学方法和考核方式给出思考。 关键词：计算机科学导论；教学方法；考核方式 《计算机科学导论》课程是计算机专业的引导性课程，为计算机专业的新生提供了关于该专业学科的入门介绍。使学生能够全面掌握计算机的基础知识，并了解该专业的学生在该领域工作应具有的职业道德和应遵守的法律准则。《计算机科学导论》课程在大一第一个学期开设，新生虽然具有计算机的基本使用能力，但在计算机理论知识上的专业性不够，大部分的知识对新生来说都是第一次接触。如果一味地想把如此广的知识介绍给学生，理解上的难度会影响他们学习的积极性，效果并不好。根据该课程近几年的教学实践，笔者总结出了教学中存在的一些问题，并对教学内容的选取、教学方法和考核方式给出思考。 ● 教学中存在的问题 计算机科学导论的教学内容虽然相对浅显，但是涵盖的知识面很广，几乎包括计算机领域所有的理论知识，应用技术、热点研究问题等。在授课中不仅要把基本的概念介绍清楚，还要对最新的专业动态有所介绍。在教学过程中主要存在以下几个问题。 1.合适教材难以选择 我国的计算机科学导论教材非常多，按其内容主要有以下三种：一、内容为计算机各种办公软件的使用，使学生具有使用计算机的初步能力，和非计算机专业开设的《大学计算机文化基础》课程等同[1]；二、将计算机专业学生大学四年要学的专业核心课程进行了浓缩，内容 涉及面广；三、计算机和计算的本质属性用高度抽象的数学模型来刻画[2]，内容进行系统 化、形式化的概括。由于目前中小学已开始开设了相关的课程，新生都具有不同程度的使用计算机的能力。所以选择第一种教材对于计算机专业的学生会过于简单，失去“专业引导”课程的本质属性；第二种教材在广度和深度上是比较难以把握的；第三种教材过于抽象，教师难讲，一般院校的学生难以理解。再加之计算机科学技术和应用技术的发展变化非常快[3]，可谓日 新月异，许多教材内容的更新速度严重滞后。 2.理论教学过于复杂 新生非常渴望专业知识，计算机专业的新生对第一学期开设的计算机科学导论课程抱有很大的期望。教师希望通过讲授该课程给学生初步建立整个学科的框架，指明计算机专业学习的
第1章概述 习题(答案) 一?选择题 1. D 2. B 3. CD 4. C 5.A 6. ABC 7. A 8. C 9.B10. B 11. C12. A13. ABC14.B15. ABCD 16.C17.ABCDE 二?简答题 1简述计算机的发展阶段 计算机的出现是20世纪最辉煌的成就之一，按照采用的电子器件划分，计算机大致经历了四个阶段。 1. 第一代计算机(1946 —1957) 其主要特征是逻辑器件使用了电子管，用穿孔卡片机作为数据和指令的输入设备，用磁鼓 或磁带作为外存储器，使用机器语言编程。第一台计算机需要工作在有空调的房间里，如果希
望它处理什么事情，需要把线路重新连接接，把成千上万的线重新焊接。 1949年发明了可以存储程序的计算机，这些计算机使用机器语言编程，可存储信息和自动处理信息，存储和处理信息的方法开始发生革命性的变化。 第一代计算机体积大、运算速度低、存储容量小、可靠性低。几乎没有什么软件配置，主要用于科学计算。尽管如此，第一代计算机却奠定了计算机的技术基础，如二进制、自动计算及程序设计等，对以后计算机的发展产生了深远的影响。其代表机型有：ENIAC、IBM650(小 型机卜IBM709(大型机)等。 2. 第二代计算机(1958 —1964) 其主要特征是使用晶体管代替了电子管，内存储器采用了磁芯体，引入了变址寄存器和浮 点运算部件，利用I/O处理机提高了输入输出能力。这不仅使得计算机的体积缩小了很多，同时增加了机器的稳定性并提高了运算速度，而且计算机的功耗减小，价格降低。在软件方面配 置了子程序库和批处理管理程序，并且推出了Fortran、COBOL、ALGOL等高级程序设计语言及相应的编译程序，降低了程序设计的复杂性。除应用于科学计算外，它还开始应用在数据处理和工业控制等方面。其代表机型有IBM7090、IBM7094、CDC7600等。 3. 第三代计算机(1965 —1972) 其主要特征是用半导体中、小规模集成电路(Integrated Circuit，IC)作为元器件代替晶体管等分立元件，用半导体存储器代替磁芯存储器，使用微程序设计技术简化处理机的结构，这使 得计算机的体积和耗电量显著减小，而计算速度和存储容量却有较大提高，可靠性也大大加强。在软件方面则广泛地引入多道程序、并行处理、虚拟存储系统和功能完备的操作系统，同时还提供了大量的面向用户的应用程序。计算机开始定向标准化、模块化、系列化，此外，计算机的应用进入到许多科学技术领域。代表机器有IBM 360系列、富士通F230系列等。 4. 第四代计算机(1972年至今) 其主要特征是使用了大规模和超大规模集成电路，使计算机沿着两个方向飞速向前发展。 一方面，利用大规模集成电路制造多种逻辑芯片，组装出大型、巨型计算机，使运算速度向每秒十万亿次、百万亿次及更高速度发展，存储容量向百兆、千兆字节发展，巨型机的出现，推动了许多新兴学科的发展。另一方面，利用大规模集成电路技术，将运算器、控制器等部件集成在一个很小的集成电路芯片上，从而出现了微处理器。微型计算机、笔记本型和掌上型等超微型计算机的诞生是超大规模集成电路应用的直接结果，并使计算机很快进入到寻常百姓家。完善的系统软件、丰富的系统开发工具和商品化的应用程序的大量涌现，以及通信技术和计算 机网络的飞速发展，使得计算机进入了一个快速发展的阶段。 现在很多国家正在研制新一代的计算机，新一代计算机将是微电子技术、光学技术、超导 技术、电子仿生技术等多学科相结合的产物。它能进行知识处理、自动编程、测试和排错，以及用自然语言、图形、声音和各种文字进行输入和输出。新一代计算机的研究目标是打破计算机现有的体系结构，使得计算机能够具有像人那样的思维、推理和判断能力。已经实现的非传统计算技术有超导计算、量子计算、生物计算、光计算等。未来的计算机可能是超导计算机、量子计算机、生物计算机、光计算机、纳米计算机或DNA计算机等。
(多选题) 1: ROM的主要类型包括 A: ROM B: PROM C: EPROM D: CDROM 正确答案: (多选题) 2: 操作系统的特性包括 A: 并发性 B: 共享性 C: 虚拟性 D: 不确定性 正确答案: (多选题) 3: 计算机应用软件可用于 A: 科学计算 B: 文字处理 C: 工程设计 D: 数据处理 正确答案: (多选题) 4: 鼠标的主要部件有 A: 位置采样机构 B: 传感器 C: 专用处理芯片 D: 电荷耦合器件 正确答案: (多选题) 5: 计算机中操作系统的任务包括 A: 进程调度 B: 内存管理 C: 文件管理 D: 总线管理 正确答案: (判断题) 1: 门是对电信号执行基础运算的设备，用于接受一个输入信号，生成一个输出信号A: 错误 B: 正确 正确答案: (判断题) 2: 机器语言是内置在计算机电路中的指令，用助记码表示 A: 错误 B: 正确 正确答案: (判断题) 3: 布尔代数提供的是在集合{0,1}上的运算和规则 A: 错误 B: 正确 正确答案: (判断题) 4: 摩尔定律是指一个集成电路板上能够容纳的电路数量每年增长一倍 A: 错误 B: 正确 正确答案: (判断题) 5: 稳定排序算法是指占用有限额外空间的算法 A: 错误 B: 正确 正确答案: (判断题) 6: 网络协议就是为网络数据交换而制定的规则 A: 错误
(判断题) 7: 硬件是计算机系统中有形的装置和设备的总称 A: 错误 B: 正确 正确答案: (判断题) 8: 关系是元组的集合而不是元组的列表因此元组的出现顺序无关紧要A: 错误 B: 正确 正确答案: (判断题) 9: 实体是指某种抽象事物的集合 A: 错误 B: 正确 正确答案: (判断题) 10: 同步是一种进程相互合作的思想描述进程间相互制约的问题 A: 错误 B: 正确 正确答案: (判断题) 11: 软件危机完全是由软件自身的特点决定的 A: 错误 B: 正确 正确答案: (判断题) 12: 编译器是把用高级语言编写的程序翻译成机器码的程序 A: 错误 B: 正确 正确答案: (判断题) 13: 硬件是指计算机系统中有形设备和装置的总称 A: 错误 B: 正确 正确答案: (判断题) 14: 如果有三个或更多重复字符出现，适宜使用行程长度编码进行压缩A: 错误 B: 正确 正确答案: (判断题) 15: 视频中的一幅图像叫做一帧 A: 错误 B: 正确 正确答案: (单选题) 1: 软件测试说明书的完成时间应该在 A: 需求分析阶段开始 B: 需求分析阶段结束 C: 测试阶段开始 D: 测试阶段结束 正确答案: (单选题) 2: 目前应用最广泛的计算机网络拓扑结构是 A: 星型拓扑 B: 网状拓扑 C: 树状拓扑 D: 环状拓扑 正确答案: (单选题) 3: 在布尔运算中,下列计算错误的是哪个 A: 1+1=2
名词解释 数据总线，地址控制总线 答：（1)数据总线：用于微处理器与内存、微处理器与输入输出借口之间传送信息。 数据总线的宽度（根数）决定着每次能传输信息的位数，因此数据总线的宽度是决定 计算机性能的一个重要指标。目前微型计算机的数据总线大多是32位或64位。 (2)地址总线：从内存单元或输入输出端口中读出数据或写入数据， 首先要知道内存单元或输入输出端口的地址，地址总线就是用来传送这些地址信息的。 地址总线的宽度决定了微处理器能访问的内存空间的大小，若某款微处理器有32位根地址线，则最多能访问4GB的内存空间。 （3）控制总线：用于传输控制信息，进而控制对内存和输入输出设备的访问。 无损压缩和有损压缩 1.无损压缩：是指压缩后不损失任何信息，解压缩后的信息与压缩之前的信息完全相同。无损压缩的压缩比较小，一般在2:1到5:1之间，主要用于文本文件，指纹图像，医学图像的压缩等。 2，有损压缩是指压缩后有信息的损失，但解压缩后的信息使用户感觉不出有信息的损失，或虽有感觉但不影响信息的使用，有损压缩的压缩比较高，可以达到几十比一甚至上百比一。主要用于蚃，视频和音频的压缩 网格计算，云计算 网格计算： 网格的三要素：动态的资源共享；协调的利用在不同地点的资源；对于不同地点，不同单位的资源、人员等等按需要动态地组成“虚拟机构” 网格式一种技术为了达到多种类型的分布资源共享和协作，网格计算技术必须解决多个层次的资源共享和合作技术，制定网格的标准，将internet从 通信和信息交互的平台提升到一个资源共享的平台。 云计算： 是网格计算、分布式计算（Distributed Computing）、并行计算（Parallel Computing）、效用计算（Utility Computing）、网络存储 （Network Storage Technologies）、虚拟化（Virtualization）、负载均衡（Load Balance）等传统计算机和网络技术发展融合的产物。 云计算可以认为包括以下几个层次的服务：基础设施及服务（Iaas）、平台及服务（Paas）和软件及服务（Saas）。 数字鸿沟 又称信息鸿沟，是指当代信息技术领域中存在的差距现象。它既存在于信息技术的开发领域，也存在与信息技术的应用领域。特别是由网络技术产生的差距 2.5虚拟内存虚拟设备 虚拟内存：虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用内存（一个连续完整的地址空间）， 而实际上，它通常是被分割成多个物理内存的碎片，还有部分暂时存储在挖补磁盘存储器上，在需要时进行数据交换。 虚拟设备：指通过某种方法把一台独占物理设备改造成能提供多个用户共享使用的逻辑设备，这种逻辑设备称为虚拟设备。 通常虚拟技术将一台独占设备虚拟成多台逻辑设备，供多个用户进程同时使用，通常把
计算机科学导论复习整 理 文档编制序号：[KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688]
《计算机科学导论》课程考试重点知识 考试说明：选择题（共10小题，每小题2分，共20分）、名词解释题（共5小题，每小题4分，共20分）、简答题（共5小题，每小题6分，共30分）、综合题（共5小题，选做3小题。其中强化班同学必作1、2、3小题，普通班同学任选3小题作答，每小题10分，共30分）。 一、考试范围：1~10、15章，每章都有一定量的题目。 二、课后习题中的选择题全部要求。 三、重点掌握的知识点： 1．计算机操作系统: 操作系统就是合理管理并控制计算机系统内软、硬件资源，并能够合理组织工作流程、方便用户使用的程序的集合。 通常我们将操作系统的功能概括为两大功能：扩展的虚拟机功能、资源管理功能。 其中，资源管理功能包括了处理机管理、内存管理、设备管理、文件管理四大功能。而扩展的虚拟机提供友好的人机交互以及程序级接口，使得计算机看上去像是功能扩展了的机器。 2．存储器: 存储器是计算机的记忆装置，用于存放原始数据、中间数据、最终结果和处理程序。为了对存储的信息进行管理，把存储器划分成存储单元，每个单元的编号称为该单元的地址。各种存储器基本上都是以1个字节作为一个存储单元。存储器内的信息是按地址存取的，如要访问存储器中的某个信息，就必须知道它的地址。向存储器里存入信息也称为“写入”，写入新的内容将覆盖原来的内容。从存储器里取出信息也称为“读出”，信息读出后并不破坏原来存储的内容，因此信息可以重复读出，多次利用。 通常把内存储器、运算器和控制器合称为计算机主机，也可以说主机是由CPU与内存储器组成的，而主机以外的装置称为外部设备，外部设备包括输入/输出设备、外存储器等。
计算机科学导论第二版答案 【篇一：计算机科学导论习题答案】 题(答案) 一．选择题 1. d 2. b 3. cd 4. c 5. abc 6. a 7. b 8. b 9. abcd 10. abcde 二．简答题 1．什么是计算机系统？ 计算机系统是一种能够按照事先存储的程序，自动、高速地对数据进行输入、处理、输出和存储的系统，由计算机硬件系统和计算机软件系统两大部分组成。 2．请解释冯?诺依曼所提出的“存储程序”概念。 把程序和数据都以二进制的形式统一存放在存储器中，由机器自动执行。不同的程序解决不同的问题，实现了计算机通用计算的功能。3．控制器的主要功能是什么？ 控制器基本功能就是从内存中取出指令和执行指令，即控制器按程序计数器指出的指令地址从内存中取出该指令进行译码，然后根据该指令功能向有关部件发出控制命令，执行该指令。另外，控制器在工作过程中，还要接受各部件反馈回来的信息。 4．简述cpu 和主机的概念。 通常把运算器、控制器做在一个大规模集成电路块上称为中央处理器，又称cpu(central processing unit) 。 通常把内存储器、运算器和控制器合称为计算机主机，也可以说主机是由cpu 与内存储器组成的，而主机以外的装置称为外部设备，外部设备包括输入/输出设备，外存储器等。 5．什么是计算机软件？计算机软件的分类有哪些？ 软件是指用来指挥计算机运行的各种程序的总和以及开发、使用和维护这些程序所需的技术文档。 计算机软件系统分为系统软件和应用软件。计算机系统软件由操作系统、语言处理系统、以及各种软件工具等组成，指挥、控制计算机硬件系统按照预定的程序运行、工作，从而达到预定的目标。应用软件是用户利用计算机软、硬件资源为解决各类应用问题而编写的软件，包括用户程序及其说明性文件资料。 6．计算机有哪些主要的特点？
《计算机科学导论》课程考试重点知识 考试说明：选择题（共10小题，每小题2分，共20分）、名词解释题（共5小题，每小题4分，共20分）、简答题（共5小题，每小题6分，共30分）、综合题（共5小题，选做3小题。其中强化班同学必作1、2、3小题，普通班同学任选3小题作答，每小题10分，共30分）。 一、考试范围：1~10、15章，每章都有一定量的题目。 二、课后习题中的选择题全部要求。 三、重点掌握的知识点： 1．计算机操作系统: 操作系统就是合理管理并控制计算机系统内软、硬件资源，并能够合理组织工作流程、方便用户使用的程序的集合。 通常我们将操作系统的功能概括为两大功能：扩展的虚拟机功能、资源管理功能。 其中，资源管理功能包括了处理机管理、内存管理、设备管理、文件管理四大功能。而扩展的虚拟机提供友好的人机交互以及程序级接口，使得计算机看上去像是功能扩展了的机器。 2．存储器: 存储器是计算机的记忆装置，用于存放原始数据、中间数据、最终结果和处理程序。为了对存储的信息进行管理，把存储器划分成存储单元，每个单元的编号称为该单元的地址。各种存储器基本上都是以1个字节作为一个存储单元。存储器内的信息是按地址存取的，如要访问存储器中的某个信息，就必须知道它的地址。向存储器里存入信息也称为“写入”，写入新的内容将覆盖原来的内容。从存储器里取出信息也称为“读出”，信息读出后并不破坏原来存储的内容，因此信息可以重复读出，多次利用。 通常把内存储器、运算器和控制器合称为计算机主机，也可以说主机是由CPU与内存储器组成的，而主机以外的装置称为外部设备，外部设备包括输入/输出设备、外存储器等。 3．运算速度:计算机的运算速度是衡量计算机水平的一项主要指标，它取决于指令执行时间。运算速度的计算方法多种多样，目前常用单位时间内执行多少条指令来表示，而计算机执行各种指令所需时间不同。因此，常根据在一些典型题目计算中，各种指令执行的频度以及每种指令的执行时间来折算出计算机的等效速度。 4．计算机系统: 计算机系统是一种能够按照事先存储的程序，自动、高速地对数据进行输入、处理、输出和存储的系统，由计算机硬件系统和计算机软件系统两大部分组成。 5．CPU和主机的概念: 通常把运算器、控制器做在一个大规模集成电路块上称为中央处理器，又称CPU(Central Processing Unit)。 通常把内存储器、运算器和控制器合称为计算机主机，也可以说主机是由CPU与内存储器组成的，而主机以外的装置称为外部设备，外部设备包括输入/输出设备，外存储器等。 6．软件生存周期：软件生存周期是指一个软件从提出开发要求开始直到该软件报废为止的整个时期。通常，软件生存周期包括可行性分析和项目开发计划、需求分析、概要设计、详细设计、编码、测试、维护等活动，可以将这些活动以适当方式分配到不同阶段去完成。 7．软件危机：随着计算机应用的普及和深化，计算机软件的数量、规模、复杂程度和开发所需的人力、物力等都在急剧增加，计算机发展初期个人编写小程序的传统方法，已不再适合现代大型软件的开发，用传统方法开发出来的许多大型软件甚至无法投入运行。同时，由于计算机应用领域和硬件技术得到丁飞速发展，软件的生产速度、质量和规模远远适应不了对软件的需求，造成大量人力、物力、财力的浪费，在软件开发和维护过程中出现了巨大
《计算机科学导论》第1次作业 （第1章—第7章） 一、选择题 1. 电子计算机从诞生之日起，经历了4个发展阶段，目前所使用的第四代计算机的主要特点是( D )。 A．主要特征是逻辑器件使用电子管，用穿孔卡片机作为数据和指令的输入设备，用磁鼓或磁带作为外存储器，使用机器语言编程 B．主要特征是使用晶体管代替了电子管，内存储器采用了磁芯体，引入了变址寄存器和浮点运算硬件，利用I／O处理机提高了输入／输出能力 C．主要特征是用半导体中、小规模集成电路作为元器件代替晶体管等分立元件，用半导体存储器代替磁芯存储器，使用微程序设计技术简化处理机的结构，在软件方面则广泛地引入多道程序、并行处理、虚拟存储系统和功能完备的操作系统，同时还提供了大量的面向用户的应用程序 D．主要特征是使用了大规模和超大规模集成电路 2．计算学科的根本问题是( A )。 A．什么能被有效地自动进行B．NP问题 C．工程设计D．理论研究实验方法 3．计算机科学与技术研究的内容可以分为(ABC)。 A．基础理论B．专业基础C．应用D．实验 4．计算机科学技术的研究范畴包括( ABCD )。 A．计算机理论B．硬件C．软件D．网络及应用 5．计算机科学与技术学科的核心知识点个数是( C )个。 A．3 B．12 C．14 D．21 6．如果[X]补=11110011，则[-X]补是( D )。 A．11l 1001l B．01110011 C．00001100 D．0000110l 7．若十进制数据为137．625，则其二进制数为( B )。 A．10001001．11 B．10001001．101 C．1000l0ll．10l D．1011111．101 8．存储器存储容量单位中，1KB表示( A )。 A．1024个字节B．1024位C．1024个字D．1000个字节 9．数据总线、地址总线、控制总线3类划分根据是(A)。 A．总线传送的内容B．总线所处的位置 C．总线传送的方向D．总线传送的方式 10．每次可传送一个字或一个字节的全部代码，并且是对一个字或字节各位同时进行处理的信息传递方式是( B )。 A．串行方式B．并行方式C．查询D．中断 11．目标程序是( D )。 A．使用汇编语言编写的程序B．使用高级语言编写的程序 C．使用自然语言编写的程序D．机器语言程序 12．程序设计语言中用来组织语句生成一个程序的规则称为( A)。 A．语法B．汇编C．编译D．解释 13．汇编语言使用的助记符指令与机器指令通常是一一对应的，是使用（C）。 A．自然语言B．逻辑语言C．英语单词或缩写D．形式语言
第1章概述 习题(答案) 一．选择题 1. D 2. B 3. CD 4. C 5. ABC 6. A 7. B 8. B 9. ABCD 10. ABCDE 二．简答题 1．什么是计算机系统？ 计算机系统是一种能够按照事先存储的程序，自动、高速地对数据进行输入、处理、输出和存储的系统，由计算机硬件系统和计算机软件系统两大部分组成。 2．请解释冯?诺依曼所提出的“存储程序”概念。 把程序和数据都以二进制的形式统一存放在存储器中，由机器自动执行。不同的程序解决不同的问题，实现了计算机通用计算的功能。 3．控制器的主要功能是什么？ 控制器基本功能就是从内存中取出指令和执行指令，即控制器按程序计数器指出的指令地址从内存中取出该指令进行译码，然后根据该指令功能向有关部件发出控制命令，执行该指令。另外，控制器在工作过程中，还要接受各部件反馈回来的信息。 4．简述CPU和主机的概念。 通常把运算器、控制器做在一个大规模集成电路块上称为中央处理器，又称CPU(Central Processing Unit)。 通常把内存储器、运算器和控制器合称为计算机主机，也可以说主机是由CPU与内存储器组成的，而主机以外的装置称为外部设备，外部设备包括输入/输出设备，外存储器等。 5．什么是计算机软件？计算机软件的分类有哪些？ 软件是指用来指挥计算机运行的各种程序的总和以及开发、使用和维护这些程序所需的技术文档。 计算机软件系统分为系统软件和应用软件。计算机系统软件由操作系统、语言处理系统、以及各种软件工具等组成，指挥、控制计算机硬件系统按照预定的程序运行、工作，从而达到预定的目标。应用软件是用户利用计算机软、硬件资源为解决各类应用问题而编写的软件，包括用户程序及其说明性文件资料。 6．计算机有哪些主要的特点？ (1)运算速度快、精度高 计算机的字长越长，其精度越高，现在世界上最快的计算机每秒可以运算几十万亿次以上。一般计算机可以有十几位甚至几十位(二进制)有效数字，计算精度可由千分之几到百万分之几，是任何计算工具所望尘莫及的。 (2)具有逻辑判断和记忆能力 计算机有准确的逻辑判断能力和高超的记忆能力。能够进行各种逻辑判断，并根据判断的结果自动决定下一步应该执行的指令。 (3)高度的自动化和灵活性 计算机采取存储程序方式工作，即把编好的程序输入计算机，机器便可依次逐条执行，这
《计算机科学导论》课程考试重点知识 一、考试范围：1~9，11、13章，每章都有一定量的题目。 二、习题中的选择题全部要求。 三、各章节的重点如下： 第1章概述 1.电子计算机的发展过程 2.计算学科的根本问题 3.计算机科学与技术学科的定义 第2章计算机体系结构与组织 1．计算机采用二进制的原因 2．数制的表示及转换 3．定点数及其表示方法 4．数值数据的原码、反码、补码 5．英文字符的计算机编码(ASCII码) 6．简单的逻辑运算 7．微型计算机硬件组成 8．冯?诺依曼模型及特点 9．CPU和主机的概念。 10．计算机软件 11. 计算机系统的主要技术指标 12．计算机的基本运行方式 13. 输入输出系统的基本组成 第3章程序设计语言 1．程序的概念 2. 常见的程序低级语言和高级语言有哪些 3. 高级语言的共同特性 4、语言处理的基本过程 第4章程序设计基础 1．结构化程序设计思想 2. 结构化程序设计中常见的程序结构 3. 好的程序设计风格有哪些 4、数据结构的概念 5、数据的逻辑与物理结构 6、典型的几种数据结构运算及实现 第5章算法与复杂性 1．算法的定义及基本特征 2．常用的算法描述工具 3．算法设计的原则 第6章 1．信息的概念及特点 2. 信息系统的要素
3. 数据，数据库的基本概念 4．DBMS的组成部分 5．数据库系统的组成 6．数据库SQL的特点及功能 第7章软件工程 1．软件的生命周期 2．软件工程的概念 3．软件复杂性的度量要素 4．软件可靠性的含义及可靠性指标 第8章操作系统 1．操作系统的概念 2．并发、进程、地址空间的概念 3. 操作系统的基本组成 4．操作系统的功能 5. 主流操作系统有哪些 第9章网络计算 1．不同分类的数据通信方式 2．数据传输方式 3．计算机网络的概念 4．资源子网和通信子网的组成 5．链路与通路 6．计算机网络的拓扑结构及其每种拓扑结构的特点 7．网络协议的组成 8．网络体系结构（OSI/RM模型） 9．TCP/IP协议的体系结构 10．IP地址的概念及其分类 11．计算机网络安全技术中防火墙(Firewall)的基本功能及其技术分类 第11、13章 1．人机交互界面的主要形式 2．人机界面的设计原则 3．多媒体概念 4．数学建模概念 5. 计算机模拟的概念