《计算机科学导论》课程复习大纲参考

1、文档供参考，可复制、编制，期待您的好评与关注！ 一、名词解释1、位置计数法：讲义第2章ppt第5页一种表达数字的系统，数位按顺序排列，每个数位有一个位值，数字的值是每个数位和位值的乘积之和2、模拟数据：讲义第2章ppt第15页是一种连续表示法，模拟它表示的真实信息3、数字数据：讲义第2章ppt第15页是一种离散表示法，把信息分割成了独立的元素4、原码： 课本P37，讲义第2章ppt第28页将数的符号数码化，即用一个二进制位表示符号：对整数，该位取0，对负数，该位取1。而数值部分保持数的原由形式（有时需要在高位部分添几个0）。这样所得结果为该数的原码表示。5、补码：课本P37 ，讲义第2章ppt

2、第32页，一个负数加模的结果即是该数的补码，它与该负数等价，或者说是一对一的，一个正数的补码就是它本身6、反码：课本P37，讲义第2章ppt第37页正数的反码与其原码、补码相同；负数的反码等于原码除符号位外，按位求反；X补= X反+17、溢出：讲义第2章ppt第38页当运算的结果超出某种数据类型所表示的数的范围时，机器不能正确表示，这时要产生溢出；在溢出的情况下，机器将产生错误的结果8、字符集：讲义第2章ppt第53页字符集：字符和表示它们的代码的清单；常用字符集：ASCII、Unicode9、RGB表示法：讲义第2章ppt第85页在计算机中，颜色通常用RGB(red-green-blue)值

3、表示，其中的三个数字说明了每种基色的份额如果用0255之间的数字表示一种元素的份额，0：该颜色没有参与；255：该颜色完全参与其中10、布尔代数：讲义第3章ppt第22页 提供的是集合0,1上的运算和规则 这个集合及布尔代数的规则被用来研究电子和光学开关主要代数运算：补、和、积11、布尔函数：讲义第3章ppt第29页设B=0,1，则Bn=(x1，x2，xn)|xiB，1i n是由0和1所能构成的所有n元有序列的集合从Bn到B的函数称为n度布尔函数x称为布尔变元12、文字：讲义第3章ppt第47页 布尔变元或其补14、小项：讲义第3章ppt第47页 布尔变元x1，x2，xn的小项是一个布尔积y1

4、y2yn，其中yi=xi，或 小项是n个文字的积，每个文字对应于一个变元 一个小项对一个且只对一个变元值的组合取值115、积之和展开式：讲义第3章ppt第48页 给定一个布尔函数，可以构造小项的布尔和使得：当此布尔函数具有值1时它的值为1，当此布尔函数具有值0时它的值为0 此布尔和中的小项与使得此函数值为1的值的组合对应 表示布尔函数的小项的和称为此函数的积之和展开式或析取范式16、门：讲义第3章ppt第53页 对电信号执行基础运算的设备，接受一个或者多个输入信号，生成一个输出信号 门是构成数字逻辑电路的基元，基本的门电路包括与、或、非、异或、与非、或非17、电路：讲义第3章ppt第53页 相

5、互关联的门的组合，用于实现特定的逻辑函数 计算机的所有硬件都是使用不同的电路复合而成 电路主要分为组合电路和时序电路逻辑框图与真值表：讲义第3章ppt第53页 逻辑框图：电路的图形化表示，不同类型的门有专用符号 真值表：列出了所有可能的输入值和相关输出值的表，用于分析电路的输入输出规律18、无需在意条件：讲义第3章ppt第96页 在某些电路中，由于输入值的一些组合从未出现过，所以对其输出值可以任意选择，函数对于这种组合的值称为无需在意条件 在卡诺图中，用d作其记号19、指令：讲义第3章ppt第131页 将计算机看成是一台信息处理机 处理只能一步一步地进行，一次进行一项基本操作 指令：人给机器下

6、达的完成一项基本操作的命令 指令只能由1和0来编写20、程序：讲义第3章ppt第132页 完成一项任务需要将其分解成一系列能由指令实现的基本操作，即一系列指令 程序：完成一项任务所需的并且按照一定顺序排列起来的一系列指令21、驱动程序：讲义第3章ppt第198页 是一种可以使计算机和设备通信的特殊程序，可以说相当于硬件的接口，操作系统只有通过这个接口，才能控制硬件设备的工作 底层硬件是设备管理和操作的最终执行者，驱动程序则体现系统的设备控制能力，也是硬件设备存在的基本条件 越高级的操作系统需要安装的驱动程序越少22、算法：讲义第4章ppt第8页 在有限的时间内用有限的数据解决问题或子问题的明确

7、指令集合23、编译器：讲义第4章ppt第55页编译器：把用高级语言编写的程序翻译成机器码的程序24、基本操作：讲义第4章ppt第76页指算法运行中起主要作用且花费最多时间的操作 两个实数矩阵的乘法问题中，矩阵的实数元素之间的数乘 对N个整数进行排序的算法中，整数间的比较和交换25、T(n)：讲义第4章ppt第77页 算法的时间复杂度，用问题实例长度的函数表示 也就是用该算法用于问题长度为n的实例所需要的基本操作次数来刻画26、排序问题：讲义第4章ppt第95页 是人们对数据集合最常用的基本操作之一 通讯录或电话本中记录一般按照人名的字典顺序排列 打牌时按牌色和点数排列 体育比赛的获奖情况按实际

8、成绩排序 所有计算机工作中，排序占25%以上27、稳定排序算法：讲义第4章ppt第96页 相同大小的元素不被交换的算法28、原址排序算法：讲义第4章ppt第96页 占用有限额外空间或者说额外空间与n无关29、计算机网络：讲义第5章ppt第7页计算机网络是为了通信和共享资源而以各种方式连在一起的一组计算设备。30、数据库：讲义第6章ppt第27页按照数据结构来组织、存储和管理数据的仓库，综合管理多个实体众多记录和字段，更加灵活实用二、简答题1、请叙述计算硬件的发展历程 讲义第1章ppt第17页1936年图灵机是计算机的理论模型，计算机的发展到目前为止共经历了四个时代，从1946年到1959年这段

9、时期我们称之为“电子管计算机时代”。第一代计算机的内部元件使用的是电子管。从1960年到1964年，由于在计算机中采用了比电子管更先进的晶体管，所以我们将这段时期称为“晶体管计算机时代”。晶体管比电子管小得多，不需要暖机时间，消耗能量较少，处理更迅速、更可靠。从1965年到1970年，集成电路被应用到计算机中来，因此这段时期被称为“中小规模集成电路计算机时代”。集成电路（Integrated Circuit，简称r）是做在晶片上的一个完整的电子电路，这个晶片比手指甲还小，却包含了几千个晶体管元件。从1971年到现在，被称之为“大规模集成电路计算机时代”。第四代计算机使用的元件依然是集成电路，不

10、过，这种集成电路已经大大改善，它包含着几十万到上百万个晶体管，人们称之为大规模集成电路（LargeScale lntegrated Circuit，简称LSI）和超大规模集成电路（Very Large Scale lntegrated Circuit，简称VLSI）。2、请叙述计算软件的发展历程 讲义第1章ppt第29页1946年第一台电子计算机问世以来，计算机已被广泛地应用于生产、生活的各个领域，推动着社会的进步与发展。计算机科学的发展依赖于计算机硬件和软件技术的发展，软件是用计算机语言编写的。计算机语言的发展经历了从机器语言、汇编语言到高级语言的历程。20世纪50年代初（1951-1959

11、年），计算机发明之初，科学家只能用二进制数编制的指令控制计算机运行。机器语言是计算机唯一能识别并直接执行的语言，每一条计算机指令均由一组“0”、“1”数字，按一定的规则排列组成，若要计算机执行一项简单的任务，需要编写大量的这种指令。这种有规则的二进制数组成的指令集，就是机器语言（也称为指令系统）。20世纪50年代末（1959-1965年），出现了汇编语言。汇编语言用比较容易识别、记忆的助记符替代特定的二进制串。汇编语言是符号化的机器语言，执行效率仍接近于机器语言。1970年，瑞士计算机科学家Niklaus.Wirth开发了第一个结构化程序设计语言Pascal语言，标志着结构化程序设计时期的开始

12、。Pascal语言的简洁明了以及丰富的数据结构，为程序员提供了极大的方便性与灵活性，同时它特别适合微计算机系统。结构化程序设计方法也在整个20世纪70年代的软件开发中占绝对统治地位。除Pascal语言外，常见的结构化程序设计语言还有C、FORTRAN、True BASIC等。1990年以来，面向对象分析、测试、度量和管理等研究得到了长足的发展，并在全世界掀起了一股面向对象热潮，至今盛行不衰。面向对象程序设计在软件开发领域掀起了巨大的变革，极大地提高了软件开发效率。3、简述计算机的四种类型及各自的特点 讲义第1章ppt第80页 个人计算机 满足个人应用要求，体积小、价格便宜 台式机（Deskto

13、p）、便携式计算机（Laptop、Notebook） 小型计算机 体积比个人计算机大一点，计算与存储能力更强 适用于中小型企业和科研机构的计算处理要求 大型计算机 体积更大，需要专门的机房和维护环境 系统性能更高，数据存储空间更大 一般用于大型企业和科研机构的数据中心和计算服务平台 超级计算机 拥有远胜于其他计算机的计算能力和存储能力 用于国家战略服务和专项的超级数据计算4、请解释等值原理并说明其应用领域 讲义第2章ppt第6页是一种将字符串转换为更短长度数值的方法，广泛应用于索引、加密等领域其中一种散列算法就是进行基数转换5、二进制数1010110、八进制数754、十六进制数ABC转换为十进

14、制后各是多少 讲义第2章ppt第8页1010110(2)=1*26+1*24+1*22+1*21=86(10)754(8)=7*82+5*81+4*80=448+40+4=492(10)ABC(16)=10*162+11*161+12*160=2560+176+12=2748(106、十进制数43转换为二进制、八进制、十六进制各是多少 讲义第2章ppt第12页43(10)=101011(2) 43(10)=53(8) 43(10)=2B(16)7、说明字符表示的基本思想并列举两种常用的字符集 讲义第2章ppt第52页 基本思想：Ø 列出所有字符，赋予每个字符一个二进制字符串Ø

15、; 要存储一个特定的字母，保存它对应的串即可 需要表示和保存的字符Ø 英语字母，阿拉伯数字，标点符号，空格8、比较关键字编码和行程长度编码的基本思想及特点 讲义第2章ppt第58页关键字编码（特点：用单个字符代替常用的单词）Ø 在文本中有一些常见词汇Ø the，and，which，that，whatØ 如果这些单词占用更少的空间，文档就会减小Ø 即使每个单词节省的空间有限，但是整个文档节省的总空间仍可能非常可观行程长度编码（重复字符的序列用标志字符，后面加重复字符和说明字符重复次数的数字替换）Ø 迭代编码Ø 把一系列重复字符

16、替换为它们重复出现的次数Ø 常用于一些大规模数据流中9、说明赫夫曼编码的基本思想和编码规则 讲义第2章ppt第67页基本思想Ø 在常规字符集中，每个字符都由定长的位串表示Ø 文本中很少使用字母“X”，为什么要让它占用的位数与其他常用字符一样呢？Ø 为了解决这一问题，应该用不同长度的位串表示每个字符Ø 令较少的位表示经常出现的字符，而将较长的位串留给不经常出现的字符，这样文档的整体大小将比较小编码规则Ø 列出要编码的字符出现的频率Ø 编码令出现频率最高的字符拥有最短位串Ø 同时保证表示一个字符的位串不会是表示另一个字

17、符的位串的前缀10、列举几种常见的音频格式 讲义第2章ppt第77页.wav （Microsoft公司用于Windows平台的音频文件格式）.cda（音质最好的音频格式）.mp3（目前处于统治地位的音频数据格式，动态影像专家压缩标准音频层面3）.mid（可供数字合成器和其他设备交换信息）.wma（既有较好的音质，又适合于在网络传播）.ra，.rm，.rmx（主要用于在低速广域网上实时传输音频信息、质量较差）11、列举几种常见的图像格式 讲义第2章ppt第95页以后.jpg（对色彩的信息保留较好）.bmp（不采用任何压缩，文件较大）.gif（一个gif文件中可以存多幅彩色图像，从而形成动画）.t

18、if（占用空间大，较完整的保留原有信息）.png（经常用于Java程序，特别是Java手机程序中）12、列举几种常见的视频格式 讲义第2章ppt第95页.avi（兼容好，调用方便，图像质量好、文件较大）ASF、MPEG、DIVX、MOV、RMVB13、列举色彩三要素及其含义 讲义第2章ppt第103页 亮度Ø 描述光作用于人眼时引起的明暗程度感觉Ø 彩色光辐射的功率越大，亮度越高Ø 彩色光辐射的功率越小，亮度越低 色调Ø 描述人眼看到光时产生的彩色感觉Ø 颜色的类别Ø 不同波长的光呈现不同的颜色 色饱和度Ø 某一颜色的深浅程

19、度（浓度）Ø 高饱和度的深色光可掺入白色光被冲淡14、说明显示分辨率和图像分辨率的异同 讲义第2章ppt第91-92页显示分辨率Ø 显示屏上能够显示出的像素数目Ø 如果显示分辨率为1024*768 显示屏分成768行 每行显示1024个像素 整个显示屏含有796432个像素点Ø 显示分辨率越高，显示的图像质量越高图像分辨率Ø 组成一幅图像的像素密度，表示为每英寸多少点Ø 如果用200dpi扫描一幅2*2.5英寸的彩色照片，则得到一幅400*500个像素点的图像Ø 对于同样大小的一幅图像 组成的像素数目越多，则分辨率越高，图像

20、越逼真 组成的像素数目越少，则分辨率越低，图像越粗糙15、说明视频压缩的常用方法及适用范围 讲义第2章ppt第102页 时间压缩根据连续帧之间的差别压缩电影的技术 空间压缩基于静态图像的压缩方法的电影压缩技术16、设计并绘制三人多数表决器电路 讲义第3章ppt第62页某个组织的一切事务都由一个三人委员会决定，每个委员对提出的建议可以投赞成票或反对票。一个建议如果得到了至少两张赞成票就获通过。设计一个电路，来判断建议是否获得通过 分析 如果第一个委员投赞成票，则令x=1，否则为0 如果第二个委员投赞成票，则令y=1，否则为0 如果第三个委员投赞成票，则令z=1，否则为0 必须设计一个电路使得对于

21、输入x、y、z，如果其中至少有两个为1，则此电路产生输出117、设计并绘制两路开关电路 讲义第3章ppt第64页 某盏灯需要由两个开关控制，当灯是关闭时，按下任何一个开关都可以打开此灯；当灯是打开时，按下任何一个开关都可以关闭此灯。 分析 当第一个开关关闭时，令x=1，否则为0 当第二个开关关闭时，令y=1，否则为0 当灯是打开时，令F(x,y)=1，否则为0 假设当两个开关都是关闭时，灯是打开的18、设计并绘制三路开关电路 讲义第3章ppt第66页 某盏灯需要由三个开关控制，当灯是关闭时，按下任何一个开关都可以打开此灯；当灯是打开时，按下任何一个开关都可以关闭此灯。 分析 当第一个开关关闭时

22、，令x=1，否则为0 当第二个开关关闭时，令y=1，否则为0 当第三个开关关闭时，令z=1，否则为0 当灯是打开时，令F(x,y,z)=1，否则为0 假设当三个开关都是关闭时，灯是打开的19、设计并绘制半加法器电路 讲义第3章ppt第68页20、简述布尔函数最小化的作用 讲义第3章ppt第79页 产生布尔积的布尔和，使其包含的文字之积的个数最少，这个过程称作布尔函数的最小化。 相应的电路含有最少的门和最少的输入。 作用 降低成本 提高电路可靠性 在一块芯片上设计更合适的电路 减少电路计算时间21、绘制冯诺依曼体系结构并说明其核心部件的功能 讲义第3章ppt第128页22、请说明鼠标的基本构件

23、讲义第3章ppt第173页23、请说明驱动程序和应用程序的异同 讲义第3章ppt第198-201页 每个位于总线上的设备必须包含系统设备管理器下的驱动程序，但不一定都包含应用程序 驱动程序位于操作系统下层，提供设备的存取操作 应用程序位于操作系统上层，不需要直到设备所用地址、信号种类或者通信协议 Windowssystem下存放着一些驱动程序24、你是如何理解自顶向下和面向对象两种设计方法的？它们有何异同？讲义第4章ppt第28-40页自顶向下设计一种程序开发技术，其中问题被分解为更容易处理的子问题，这些子问题的解决方案组合起来构成整体问题的解决方案，面向过程设计是一种自顶向下逐步求精的设计方

24、法,是单入口单出口的程序结构.设计者用一个main函数概括出整个应用程序需要做的事,而main函数由对一系列子函数的调用组成.其特征是以函数为中心,用函数来作为划分程序的基本单位,数据在过程式设计中往往处于从属的位置. 模块一个用于解决问题或子问题的封闭步骤集合 抽象步骤细节仍未明确的算法步骤 具体步骤细节完全明确的算法步骤面向对象面向对象的程序设计的基本思想是使用对象、类、继承、封装、消息等基本概念来进行程序设计,允许开发者从问题的局部开始,一点一点地构建出整个程序,在开发过程中逐步加深对系统的理解.面向对象设计以数据为中心,类作为表现数据的工具,是划分程序的基本单位. 对象在问题背景中具有

25、意义的事物或实体 类描述了一组类似的对象，它们有一些共同的属性和行为 方法处理对象中数据的指定算法，定义了类的某种行为25、请绘图说明算法复杂度的渐进性质 讲义第4章ppt第78页如果解决问题P的算法A和算法B，其时间复杂度分别是TA(n)和TB(n)，则判断A、B性能优劣的标准是查看在n足够大时TA(n)和TB(n)的大小关系26、请说明冒泡排序算法的原理 讲义第4章ppt第100页对尚未排序的各元素从头到尾依次比较相邻的两个元素是否逆序（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺

26、序。可以看出如果有 n 个元素，那么一共要进行 n-1 轮比较，第 i 轮要进行 j=n-i 次比较。（如：有5个元素，则要进行5-1轮比较。第3轮则要进行5-3次比较）经过优化后的算法根据不同的情况有可能减小排序的次数27、请说明快速排序算法的原理 讲义第4章ppt第105页快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。28、请列举计算机网络拓扑结构的主要类型 讲义第5章ppt第13页网状拓

27、扑 星型拓扑 树状拓扑 环状拓扑29、请对比操作系统与应用软件的异同 讲义第6章ppt第3-4页按与硬件相关的密切程度, 通常将计算机的软件分为系统软件和应用软件。用户直接使用的软件通常为应用软件, 而应用软件通常是通过系统软件来指挥计算机的硬件完成其功能的。最重要的系统软件是操作系统(Operation System,OS),它完成指挥计算机运行的各个细节, 亦即, 操作系统是计算机系统中用于指挥和管理其自身的软件。操作系统是一管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。操作系统是一个庞大的管理控制程序，大致包括5个方面的管理功能:进程与处理机管理、作业管理、存储管理、设备

28、管理、文件管理。有效地组织和管理系统中的各种软硬件资源，合理地组织计算机系统工作流程，控制程序的执行，并向用户提供一个良好的工作环境和友好的接口。应用软件通常是由计算机专业人员为满足人们完成特定任务的要求开发的, 这些软件通常以特定的操作系统作为其运行基础（称应用平台）。30、请说明数据库建模与实现过程 讲义第6章ppt第29页在设计数据库时，对现实世界进行分析、抽象、并从中找出内在联系，进而确定数据库的结构，这一过程就称为数据库建模。它主要包括两部分内容：确定最基本的数据结构；对约束建模。1.需求分析阶段：通过调查分析，确定用户的功能需求和信息需求，综合各个用户的应用需求，描述出数据流图和数

29、据字典。 2.概念设计阶段：对需求分析阶段得到的结果经行综合、归纳与抽象，形成一个独立于具体DBMS的概念模式，通常指得到一个E-R模型。 3.逻辑设计阶段：将概念模型按照一定的转换规则转换为DBMS所支持的数据模式，并对其经行优化。首先将E-R图转换成具体的数据库产品支持的数据模型，如关系模型，形成数据库逻辑模式；然后根据用户处理的要求、安全性的考虑，在基本表的基础上再建立必要的视图(View)，形成数据的外模式 4.数据库物理设计阶段：为逻辑数据模型确定最适合于应用环境的物理结构，包括存储结构和存取方法。根据DBMS特点和处理的需要，进行物理存储安排，建立索引，形成数据库内模式5、数据库实

30、施：利用DBMS提供的数据语言和平台、根据逻辑设计和物理设计的结果建立数据库，编制并调试程序运行，组织数据的输入，并试运行。6、运行与维护：调试运行后的数据库应用系统正式运行，并在运行过程中，按照软件工程的方法经行不断地测试、维护。三、分析与设计题1、利用卡诺图方法化简 讲义第3章ppt第94页原式=2、利用奎因-莫可拉斯基方法化简 讲义第3章ppt第99页3、已知整型数组NUM长度为N，设计算法求得其最大元和最小元。请说明算法的基本思想并绘制对应的程序流程图 讲义第4章ppt第89页 求n元中的最大元MAX(n)和最小元MIN(n)4、已知整型数组NUM=8,9,2,6,3,1,7,5，设计算法将NUM按照从大到小的顺序排列。请说明算法的基本思