计算机科学导论 2010 期末复习题1 / 12一、名词解释1、位置计数法：讲义第 2 章 ppt 第 5 页一种表达数字的系统，数位按顺序排列，每个数位有一个位值，数字的值是每个数位和位值的乘积之和2、模拟数据：讲义第 2 章 ppt 第 15 页是一种连续表示法，模拟它表示的真实信息3、数字数据：讲义第 2 章 ppt 第 15 页是一种离散表示法，把信息分割成了独立的元素4、原码： 课本 P37，讲义第 2 章 ppt 第 28 页将数的符号数码化，即用一个二进制位表示符号：对整数，该位取 0，对负数，该位取 1。而数值部分保持数的原由形式（有时需要在高位部分添几个 0） 。这样所得结果为该数的原码表示。5、补码：课本 P37 ，讲义第 2 章 ppt 第 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)值表示，其中的三个数字说明了每种基色的份额如果用 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 的小项是一个布尔积 y1y2yn，其中 yi=xi，或 小项是 n 个文字的积，每个文字对应于一个变元 一个小项对一个且只对一个变元值的组合取值 115、积之和展开式：讲义第 3 章 ppt 第 48 页 给定一个布尔函数，可以构造小项的布尔和使得：当此布尔函数具有值 1 时它的值为 1，当此布尔函数具有值 0 时它的值为 0 此布尔和中的小项与使得此函数值为 1 的值的组合对应 表示布尔函数的小项的和称为此函数的积之和展开式或析取范式16、门：讲义第 3 章 ppt 第 53 页 对电信号执行基础运算的设备，接受一个或者多个输入信号，生成一个输出信号 门是构成数字逻辑电路的基元，基本的门电路包括与、或、非、异或、与非、或非17、电路：讲义第 3 章 ppt 第 53 页 相互关联的门的组合，用于实现特定的逻辑函数 计算机的所有硬件都是使用不同的电路复合而成计算机科学导论 2010 期末复习题2 / 12 电路主要分为组合电路和时序电路逻辑框图与真值表：讲义第 3 章 ppt 第 53 页 逻辑框图：电路的图形化表示，不同类型的门有专用符号 真值表：列出了所有可能的输入值和相关输出值的表，用于分析电路的输入输出规律18、无需在意条件：讲义第 3 章 ppt 第 96 页 在某些电路中，由于输入值的一些组合从未出现过，所以对其输出值可以任意选择，函数对于这种组合的值称为无需在意条件 在卡诺图中，用 d 作其记号19、指令：讲义第 3 章 ppt 第 131 页 将计算机看成是一台信息处理机 处理只能一步一步地进行，一次进行一项基本操作 指令：人给机器下达的完成一项基本操作的命令 指令只能由 1 和 0 来编写20、程序：讲义第 3 章 ppt 第 132 页 完成一项任务需要将其分解成一系列能由指令实现的基本操作，即一系列指令 程序：完成一项任务所需的并且按照一定顺序排列起来的一系列指令21、驱动程序：讲义第 3 章 ppt 第 198 页 是一种可以使计算机和设备通信的特殊程序，可以说相当于硬件的接口，操作系统只有通过这个接口，才能控制硬件设备的工作 底层硬件是设备管理和操作的最终执行者，驱动程序则体现系统的设备控制能力，也是硬件设备存在的基本条件 越高级的操作系统需要安装的驱动程序越少22、算法：讲义第 4 章 ppt 第 8 页 在有限的时间内用有限的数据解决问题或子问题的明确指令集合23、编译器：讲义第 4 章 ppt 第 55 页编译器：把用高级语言编写的程序翻译成机器码的程序24、基本操作：讲义第 4 章 ppt 第 76 页指算法运行中起主要作用且花费最多时间的操作 两个实数矩阵的乘法问题中，矩阵的实数元素之间的数乘 对 N 个整数进行排序的算法中，整数间的比较和交换25、T(n) ：讲义第 4 章 ppt 第 77 页 算法的时间复杂度，用问题实例长度的函数表示 也就是用该算法用于问题长度为 n 的实例所需要的基本操作次数来刻画26、排序问题：讲义第 4 章 ppt 第 95 页 是人们对数据集合最常用的基本操作之一 通讯录或电话本中记录一般按照人名的字典顺序排列 打牌时按牌色和点数排列 体育比赛的获奖情况按实际成绩排序 所有计算机工作中，排序占 25%以上27、稳定排序算法：讲义第 4 章 ppt 第 96 页 相同大小的元素不被交换的算法28、原址排序算法：讲义第 4 章 ppt 第 96 页 占用有限额外空间或者说额外空间与 n 无关29、计算机网络：讲义第 5 章 ppt 第 7 页计算机网络是为了通信和共享资源而以各种方式连在一起的一组计算设备。30、数据库：讲义第 6 章 ppt 第 27 页按 照 数 据 结 构 来 组 织 、 存 储 和 管 理 数 据 的 仓 库 ， 综 合 管 理 多 个 实 体 众 多 记 录 和 字 段 ， 更 加 灵 活 实 用二、简答题计算机科学导论 2010 期末复习题3 / 121、请叙述计算硬件的发展历程 讲义第 1 章 ppt 第 17 页1936 年图灵机是计算机的理论模型，计算机的发展到目前为止共经历了四个时代，从 1946 年到 1959 年这段时期我们称之为“电子管计算机时代”。第一代计算机的内部元件使用的是电子管。从 1960 年到 1964 年，由于在计算机中采用了比电子管更先进的晶体管，所以我们将这段时期称为“晶体管计算机时代” 。晶体管比电子管小得多，不需要暖机时间，消耗能量较少，处理更迅速、更可靠。从 1965 年到 1970 年，集成电路被应用到计算机中来，因此这段时期被称为“中小规模集成电路计算机时代” 。集成电路（Integrated Circuit，简称 r）是做在晶片上的一个完整的电子电路，这个晶片比手指甲还小，却包含了几千个晶体管元件。从 1971 年到现在，被称之为“大规模集成电路计算机时代”。第四代计算机使用的元件依然是集成电路，不过，这种集成电路已经大大改善，它包含着几十万到上百万个晶体管，人们称之为大规模集成电路（LargeScale lntegrated Circuit，简称LSI）和超大规模集成电路（Very Large Scale lntegrated Circuit，简称 VLSI） 。2、请叙述计算软件的发展历程 讲义第 1 章 ppt 第 29 页1946 年第一台电子计算机问世以来，计算机已被广泛地应用于生产、生活的各个领域，推动着社会的进步与发展。计算机科学的发展依赖于计算机硬件和软件技术的发展，软件是用计算机语言编写的。计算机语言的发展经历了从机器语言、汇编语言到高级语言的历程。20 世纪 50 年代初（1951-1959 年） ，计算机发明之初，科学家只能用二进制数编制的指令控制计算机运行。机器语言是计算机唯一能识别并直接执行的语言，每一条计算机指令均由一组“0”、 “1”数字，按一定的规则排列组成，若要计算机执行一项简单的任务，需要编写大量的这种指令。这种有规则的二进制数组成的指令集，就是机器语言（也称为指令系统） 。20 世纪 50 年代末（1959-1965 年） ，出现了汇编语言。汇编语言用比较容易识别、记忆的助记符替代特定的二进制串。汇编语言是符号化的机器语言，执行效率仍接近于机器语言。1970 年，瑞士计算机科学家 Niklaus.Wirth 开发了第一个结构化程序设计语言Pascal 语言，标志着结构化程序设计时期的开始。Pascal 语言的简洁明了以及丰富的数据结构，为程序员提供了极大的方便性与灵活性，同时它特别适合微计算机系统。结构化程序设计方法也在整个 20 世纪 70 年代的软件开发中占绝对统治地位。除 Pascal 语言外，常见的结构化程序设计语言还有 C、FORTRAN、True BASIC 等。1990 年以来，面向对象分析、测试、度量和管理等研究得到了长足的发展，并在全世界掀起了一股面向对象热潮，至今盛行不衰。面向对象程序设计在软件开发领域掀起了巨大的变革，极大地提高了软件开发效率。3、简述计算机的四种类型及各自的特点 讲义第 1 章 ppt 第 80 页 个人计算机 满足个人应用要求，体积小、价格便宜 台式机（Desktop） 、便携式计算机（ Laptop、Notebook） 小型计算机计算机科学导论 2010 期末复习题4 / 12 体积比个人计算机大一点，计算与存储能力更强 适用于中小型企业和科研机构的计算处理要求 大型计算机 体积更大，需要专门的机房和维护环境 系统性能更高，数据存储空间更大 一般用于大型企业和科研机构的数据中心和计算服务平台 超级计算机 拥有远胜于其他计算机的计算能力和存储能力 用于国家战略服务和专项的超级数据计算4、请解释等值原理并说明其应用领域 讲义第 2 章 ppt 第 6 页是一种将字符串转换为更短长度数值的方法，广泛应用于索引、加密等领域其中一种散列算法就是进行基数转换5、二进制数 1010110、八进制数 754、十六进制数 ABC 转换为十进制后各是多少 讲义第 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 页 基本思想： 列出所有字符，赋予每个字符一个二进制字符串 要存储一个特定的字母，保存它对应的串即可 需要表示和保存的字符 英语字母，阿拉伯数字，标点符号，空格8、比较关键字编码和行程长度编码的基本思想及特点 讲义第 2 章 ppt 第 58 页关键字编码（特点：用单个字符代替常用的单词） 在文本中有一些常见词汇 the，and，which ，that ，what 如果这些单词占用更少的空间，文档就会减小 即使每个单词节省的空间有限，但是整个文档节省的总空间仍可能非常可观行程长度编码（重复字符的序列用标志字符，后面加重复字符和说明字符重复次数的数字替换