计算机导论课后习题答案

1、 计算机科学导论 第七章1应用程序和操作系统的不同点是什么？操作系统是一个程序，有利于应用程序的执行。2操作系统的组成是什么？内存管理器，进程管理器，设备管理器，文件管理器。3单道程序和多道程序之间有何区别？单道程序，只有一个程序在内存中。多道程序，多个程序同时在内存中，但是计算机的资源只分配给正在运行的程序。4分页调度和分区调度有什么区别？分区调度把内存分为若干个区，把程序整个的放入区中。分页调度提高了分区调度的效率，在分页调度下，内存被分为大小相等的若干部分，程序也被分为大小相等的部分。分区调度需要把程序装载到连续的内存上。分页调度可以吧把程序装载到不连续的内存当中。5为什么请求分页调度比

2、常规页面调度具有更高的效率？在常规的分页调度中，整个程序必须同时在内存中，以便为程序执行。但是在请求分页调度中，有部分页面的程序可以在内存中。这意味着，在请求分页调度中，在给定的时间中，更多的程序可以使用计算机的资源。6程序和作业之间有何联系？作业和进程之间有何联系？程序和进程之间有何联系？从一个程序被选中执行，到其运行结束并再次成为一个程序的这段过程中，该程序称为作业。7程序驻留在哪里？作业驻留在哪里？进程驻留在哪里？程序和作业驻留在磁盘上，进程驻留在内存中。8作业调度器和进程调度器有什么区别？作业调度器负责从作业中创建一个进程和终止一个进程。进程调度器将一个进程从一个状态转入另一个状态。9

3、为什么操作系统需要队列？一个操作系统需要使用队列，因为在同一时间可以有许多作业和进程同时活跃。为了共享所有的资源，队列是必要的，以确保作业和进程都得到他们需要的资源。31一个计算机装有一个单道程序的操作系统。如果内存容量为64MB，操作系统需要4MB的内存，那么该计算机执行一个程序可用的最大内存为多少？64-4=60MB33 70/(70+10)=87.5%34一个多道程序的操作系统用一个适当的分配计划把60MB内存分为10MB，12MB，18MB，20MB。第一个程序运行需要17MB内存，使用了第三分区，第二个程序运行需要8MB内存，使用了第一分区。第三个程序运行需要10.5MB，使用了第二

4、分区。最后第四个程序要20MB，使用了第四分区。那么总共使用了多少内存？浪费了多少内存？内存的浪费率是多少?总共使用17+8+10.5+20=55.5MB浪费4.5MB。36一个多道程序的操作系统使用分页调度。可用内存为60MB，分为15帧。A 4, B 3, C 7，D 1， E 4MB, F 1/1537 (100+1000)/10=110 100MB可以驻留在内存中，1000MB必须留在磁盘里。39 是 死锁的四个条件都满足 互斥 资源占有，抢先 循环等待。40 不是死锁。11-20 AABCA AAADC 21-30 CCADA BDADC 第八章1算法的正式定义是什么?算法定义为一组

5、明确步骤的有序集合，它产生结果并在有限的时间内终结。2给出用于结构化程序设计中的三种结构定义？顺序，判断，循环。3UML图与算法有什么关系？通用建模语言（UML）是一种算法的图形表示。它隐藏了一个算法的所有细节，试图给出一个大的图片，它显示了如何从开始到结束的算法流程。4伪代码与算法有什么关系？伪代码是算法的一种类似英语的表示法。5排序算法的用途是什么？一种排序算法根据其值排列数据.6本章有哪三种基本的排序算法？选择排序，冒泡排序，插入排序。7查找算法的基本用途是什么？一个数据列表中找到一个特定的项目（目标）。8本章讨论的基本查找算法主要有哪两种？顺序查找，折半查找。9给出迭代过程的定义和一个

6、例子?算法的定义没有包括算法本身。10给出递归过程的定义和一个例子？算法的定义包括算法的本身。29IterationData item Sum = 0120Sum = 0 + 20 = 20212Sum = 20 + 12 = 32 370Sum = 32 + 70 = 102481Sum = 102 + 81 = 183545Sum = 183 + 45 = 228613Sum = 228 + 13 = 241781Sum = 241 + 81 = 322After exiting the loopSum = 32231118Largest = 18212Largest = 1838Larg

7、est = 18420Largest = 20510Largest = 10632Largest = 3275Largest = 32After exiting the loopLargest = 3233PassList1472331405678921272331405678914227233140567891432793140567823144279144056782331527914235678403162791423317840567279142378407856827914237840567835PassList147233140567892171423314056789227142

8、3314056789237142331405678924714233140567892571423314056789267142331405678927791423314056782827914233140567837PassList7826441323579817813264423579827813232644579837813232644579839 firstlastmid1234567818458678781317264456889744568897889743iFactorial 1F = 12F = 1 × 2 = 23F = 2 × 3 = 64F = 6 &

9、#215; 4 = 245F = 24 × 5 = 1206F = 120 × 6 = 720After exiting the loopF = 72011-20 DCBBC ACABB 21-28DBACB ABC第九章1汇编语言和机器语言有哪些区别？机器语言只使用0和1的指令和地址。汇编语言使用符号来表示指令和地址。2汇编语言和高级语言有哪些区别？高级语言能使程序员能够集中精力在应用程序上。高级语言的设计目标就是使程序员拜托汇编语言繁缛的细节。3哪种语言和机器语言直接相关，并被计算机制及识别？机器语言是计算机硬件所理解的唯一语言。4区分编译和解释。编译在执行前把整个源程

10、序翻译成目标程序。解释一次只翻译和执行源代码中的一行。5列出编译语言翻译中的四个步骤这四个步骤是词法分析，语法分析，语义分析和代码生成。6列出四种常见的计算机语言模式。过程式，面向对象，函数式，说明式。7比较和对照过程模式和面向对象模式。在过程模式，程序是一种活性剂，操纵被动对象（数据）。面向对象的范例中，数据被设计为活动对象。对这些对象进行的操作包括在对象中。8定义面向对象语言中的类和方法，这两个概念的联系是什么？他们对于对象概念间的联系是什么？相同类型的对象需要一组方法，这些方法显示了这类对象对来自对象领地外的刺激的反应。？9定义函数模式。在函数模式中，程序设计成了一个数学函数。它允许程序

11、员将预定义的原始函数结合起来，创建新的函数。10定义说明式模式。说明式模式使用逻辑推理原则去回答问题。23 int a，int b，int c24double a=0 double b=0 doublec=025 const char name=”a” const int a=0 const float b=0.327 2次29语句执行八次（i= 5，7，9，13，15，11，17，19）。值得注意的是，在每次迭代中i的值是递增的两次：第一次在头（i+ +），在循环体中第二次（i=i+ 1）。30 5次。31A = 5; do statement; A = A 2; while (A <

12、 8); 32 i=5 do statement; i=i+2; while(i<20) 33. i = 5; while (i < 20) statement; i = i + 2;34 for(i=5;i<10;i+) Statement; 35.for (int A = 5; A < 8; A = A 2) statement; 11-15 ACBAA 16-20DBACD BC 第十章1定义软件的生命周期。软件，像许多其他的产品，经过一个周期的重复阶段，直到它变得过时。2区分瀑布模型和增量开发模型。瀑布模型开发过程只有一个方向流动。在增量模型中，软件的开发要经历

13、一系列步骤，开发者首先完成整个系统的简化版本，这个版本表示了整个系统，但不包括具体的细节。3软件开发的四个阶段是什么？分析，设计，实现，测试。4说明分析阶段的目标是什么，描述此阶段的两种趋势。这个阶段产生了规格说明文档，这个文档说明了软件要做什么而没有说怎么做。面向过程分析，面向对象分析。5说明设计阶段的目标，描述此阶段的两种趋势。设计阶段定义了系统将如何完成在分析阶段所定义的。在设计阶段，所有组件的系统被定义。在这个阶段的发展趋势是面向过程的设计，面向对象的设计。6描述模块化，说出与模块化有关的两个问题。模块化是将大程序分解成容易理解和容易处理的小程序。耦合和内聚。7描述耦合和内聚之间的区别

14、。内聚是衡量一个程序中程序的紧密程度的一个度量。耦合是一种度量，如何将两个模块互相绑定在一个模块中。8说明实现阶段的目标，描述此阶段中的质量 问题。程序员为面向过程设计中的模块编写程序或程序单元，实现面向对象设计中的类。可操作性，可维护性，可迁移性。9说明测试阶段的目标，列出两类测试。测试阶段的目标是找到错误。有2种类型的测试：玻璃箱（或白盒）和黑盒10描述白盒测试和黑盒测试间的区别。白盒测试是基于知道软件的内部内部结构。黑盒测试不知道内部是什么，也不知道他是如何工作的情况下的测试软件。23通过参考提供了两个模块之间的衔接。11-15 DBCBD 16-20 DBDAB 第十一章1给出数据结构

15、的三种类型的名称。数组记录和链表。2数组元素和记录元素的区别。数组是元素的顺序集合，通常这些元素具有相同的数据类型。记录是一组相关元素集合，它们可能是不同的类型。3数组元素和链表元素的区别。数组的元素在内存中是连续的，并且可以使用一个索引来访问数组元素。链表的元素被存储在可能分散在整个内存中的节点中，并且只能通过访问列表（即搜索功能返回的特定节点的地址）访问该功能。4为什么用索引而不是下表来标注数组元素。索引表示元素在数组中的顺序号，顺序号从数组开始处计数。5数组元素在内存中是如何储存的。数组是连续存储在内存中。大多数计算机使用行存储来存储二维数组。6记录中域的定义是什么。记录中每个元素称为域

16、。域是具有含义的最小命名数据。7在链表中节点的域是什么？在链表中的节点的域是数据和一个指向下一个节点的指针（地址）。8链表中指针的功能是什么？指明链表中的下一个元素。9如何指向链表中的第一个节点？我们用头指针指向链表中的第一个节点。10链表中最后一个节点的指针指向什么？最后一个指针为空指针。11-15 DBCBC 16-20 DAADB 第十二章1什么是抽象数据类型？，在抽象数据类型中什么是已知的，什么是隐藏的？一个抽象数据类型（ADT）是一种数据申报与数据类型有意义的操作封装在一起。在ADT，访问数据的操作是已知的，但操作的实现是隐藏的。2什么是栈？栈的四种基本操作是什么？栈是一种限制性线性

17、列表。建栈，入栈，出栈，和空。3什么是队列?队列的四种基本操作是什么？队列是一个线性表，数据只能在一个末端被插入，称为后，并从另一端删除，称为前。这些限制确保数据被处理通过在它们被接收的顺序中的队列中。换句话说，一个队列是一个先入先出（FIFO）结构。在这一章中定义了四种基本的队列操作队列的入队、出队，和空。4什么是广义线性表？他的六种基本操作是什么？广义线性表是像插入和删除等操作可以再其中任何地方进行的表，可以在表头表中间或表尾。5定义一棵树，区分树和二叉树。区分二叉树和二叉搜索树。棵树由一组有限的元素，称为节点（或顶点），和一组有限的有向线，称为弧，连接对节点。如果树不是空的，一个节点，称

18、为根，没有传入的弧。在一个树上的其他节点可以从一个独特的路径，这是一个序列的连续弧的根。二叉树是在没有节点可以有两个以上的子树的树。二进制搜索树（BST）是与一个额外的属性的二进制树：每个节点的关键值大于左子树的所有节点都小于所有节点的右子树中每个值的关键值。6二叉树的深度优先遍历和广度优先遍历有何不同？深度优先遍历有前序中序和后序遍历，分别是根左右，左根右，左右根。广度优先遍历先处理节点的所有子节点，然后进行下一层。7什么是图？有向图和无向图的区别是什么？一个图是由一组节点，称为顶点的ADT，并设置连接顶点的线，称为边或弧。图可以是有向图或无向图。在一个有向图，或图，每个边缘，连接两个顶点，

19、有一个方向（箭头）从一点到另一。在一个无向图中，没有方向。8列出栈和队列的一些应用。栈的应用有倒转数据，配对数据，数据延迟使用和回溯步骤。队列应用在电子商务应用程序。9列出二叉树和二叉搜索树的一些应用。般的线性表被用来在随机或顺序访问元素的情况下使用。例如，在一所大学，一个线性表可以用来储存信息的学生谁是在每学期参加。11-15BDABD 16-20AACCC 21-25 DCADB 第十三章1通常文件有哪两种存取方式？访问方法是顺序和随机的。2新主文件和旧主文件之间是什么关系？新的永久数据成为新主文件。新主文件包含大部分当前数据。旧主文件是需要更新的永久文件，在更新后，旧主文件作为参考继续保

20、留。3在顺序文件更新时，事务文件的作用是什么？该事务文件包含应向旧主文件的更改。4描述随机文件存取的地址函数。在散列文件中散列函数将键映射为记录地址。5在索引文件中数据文件和索引是如何关联的。该索引是一个表，该表将该数据项的键和存储在文件中的地址关联。6在文件直接散列法中键和地址之间是什么关系。键就是地址。7在文件除余散列法中键和地址之间是什么关系？在模除法散列，关键是按文件大小。其余的加1作为记录的地址在文件中。8在文件数字析取散列法中键和地址之间是什么关系？在数字析取散列法中，选择的数字是从键中析取出来的，用作地址。9给出三种冲突的解决方法。碰撞发生时，两个散列记录具有相同的地址。三种碰撞

21、方法是打开寻址，链接列表解析，和桶散列。在开放寻址，主要地区是寻找一个地址。在链接列表解析中，第一个记录被存储在家庭地址中，但它包含一个指向记录的指针。在桶散列，一组记录被存储在一个桶中，这是一个可以容纳超过一个记录的位置。10文本文件和二进制文件之间的区别是什么？文本文件是一个字符文件，在他们的储存格式中不能包含整数浮点数等其他数据结构。要储存这些数据类型必须把他们转换成对应的字符格式。二进制文件的数据可以使整型浮点型或其他数据结构。11-15 DAADC 16-20 AACDA 21-25 DBACA 26-28DDA 第十四章1数据库管理系统的五个必要组成部分是什么？数据库系统的五个必要

22、组成部分是硬件、软件、数据、用户和程序。2数据库有哪三种数据库模型？哪种是目前流行的？层次模型，网状模型，关系模型。 关系模型是目前流行的。3什么叫关系数据库中的关系。在关系模型中，关系是在一个二维表中组织的一组数据。这些表是相关联的。4在一个关系中，什么称为属性？什么称为元组？5列出关系数据库中的一些一元操作。插入，删除，更新，选择，投影。6列出关系数据库中的一些二元操作。连接，并，交，差。7什么是SQL?什么是XML？哪一个是关系数据库的查询语言？哪一个是面向对象数据库的查询语言？结构化查询语言（SQL）是一种语言，由美国国家标准协会（ANSI）和国际标准化组织（ISO）用于关系数据库。标

23、记语言（XML）是一种标记语言，目的是将标记信息添加到文本文档中，但它也在数据库中找到了它的应用程序作为查询语言。SQL是用于关系数据库和XML的面向对象的数据库27A1A221631629B124298 C 9 C 10 B 11 B 12 A 13 C 14 A 15 B 16 A 17 C 18 A 19 C 20 C 21 B 22 D 23 D 24 C 25 B 第十五章1数据压缩方法有哪两种类别？有损压缩，无损压缩。2无损压缩和有损压缩有什么不同？无损压缩在压缩过程中没有数据损失，有损压缩有数据损失。3什么是游程长度编码？运行长度编码是一种无损压缩方法，在该方法中，重复出现的符号

24、被替换为一个符号的数目，然后出现的次数。4LZ编码方法是怎样减少需要传输的位的数量？在LZ编码中，重复的字符或字以变量的形式保存。字符或字用变量的索引代替。在通信会话时产生一个字典。如果双方都有这样的字典，那么字符串可以由字典中的索引代替，以减少通信的数据传输量。5什么是赫夫曼编码？赫夫曼编码使用的字符的频率在文件建立一棵树。树，然后用于生成与更频繁的字符具有较短的代码比较不频繁的字符的每个字符的代码。6字典在LZ编码中担任什么角色？字典中存放索引。？7相对于赫夫曼编码，LZ编码的优点是什么？赫夫曼编码，无论是发送者和接收者必须复制相同的代码，解码后的文件相匹配的编码文件。在LZ编码字典是从数

25、据本身产生的。8有损压缩的三种方式是什么？JPEG.MPEG.MP39什么时候用JPEG格式？什么时候用MPEG格式？采用JPEG图像压缩的MPEG压缩视频时使用。10JPEG和MPEG有什么关系？MPEG在空间压缩时每一帧的空间压缩使用JPEG。11在JPEG中分块有什么作用分块是将图像分割成8个8块的行为，以减少计算的次数。？12在JPEG格式中为什么需要离散余弦变换？离散余弦变换改变了64个值以使相邻像素之间的关系得以保存。但同时也能揭示余。13量化对于数据压缩有什么贡献？在表中的量化减少了每个值编码所需的比特数。14在MPEG压缩中什么是帧？一个运动的图像是一系列快速帧的序列。每个帧都

26、是一幅图像。15相对于时间压缩而言空间压缩是什么？空间压缩是通过使用一个修改版的JPEG图像每帧的压缩；时间压缩的MPEG帧去除冗余。17 B 18 A 19 D 20 A 21 D 22 D 23 A 24 B 25 C 26 D 27B 28 A 29 C 30 C 第十六章1列出本章讨论的三个安全目标。三安全目标是保密性，完整性和可用性。保密是为了保护我们的机密信息，以防止恶意行为，危及它。完整性意味着变更需要通过授权的实体和通过授权机制来完成。可用性意味着由一个组织创建和存储的信息需要提供给授权的实体。2列出本章讨论的五个安全服务。数据机密性，数据完整性，验证，不可否认，访问控制。3区

27、分密码术和隐写术。密码学的加密手段隐瞒消息内容；伪装手段隐瞒信息本身，用别的东西覆盖4区分替换密码和置换密码。替换密码就是用一个符号替换另一个符号。置换密码就是符号的重新排序。5区分对称密钥和非对称密钥密码术。密码学的加密手段隐瞒消息内容；伪装手段隐瞒信息本身，用别的东西覆盖6区分非对称密钥密码术中的私钥和公钥。公钥能被私钥打开。？7区分信息完整性和信息验证。消息完整性保证消息未更改；消息验证身份验证消息的发送端。8比较通常签名和数字签名。书287.9列出数字签名提供的安全服务。数字签名可以提供三的安全服务：消息认证、消息完整性和不可否认性。10列出并说明在实体验证过程中的三中身份证据。所知道

28、的，所拥有的，所固有的。11定义会话密钥，显示KDC是如何在爱丽丝和博比间建立会话密钥的。使用一个可信的第三方是密钥分配一个实用的解决方案，称为密钥分配中心（KDC）。为了减少按键的数量，每个人建立一个共享密钥KDC。一个密钥KDC和每个成员之间建立。这就是爱丽丝发送机密信息，鲍勃。爱丽丝发送一个请求到KDC说她需要一个会话密钥（临时）她和Bob之间。KDC告诉Bob爱丽丝的要求。如果鲍勃同意，会话密钥是两者之间产生。12定义认证机构和它与公钥密码术间的联系。认证机构是一个把公钥和实体捆绑在一起并处理认证的政府机构。13 A 14 B 15 C 16 C 17 C 18 B 19 A 20 C

29、 21 A 22 A 23 B 24 C 25 D 26 A 27 A 28 A 29 B 30 C 31 A 32 D 第十七章1在简单语言中，有三种语句是其他语句的基础，说出他们的名字，并描述他们的功能。我们简单语言中的三个语句是增量语句、递减语句和循环语句。增值表增加1变；减量减去1声明变量；循环语句的重复一个动作（或一系列的动作），该变量的值不为零。2说明如何用三种基本语句把一个变量的值赋给另一个变量。3图灵机和简单语言间有何联系？一个可以用我们的简单语言解决的问题也可以用图的图。4说明图灵机的组成和每一部件的功能。磁带：保存一系列顺序字符，该字符来自计算机所能接收的字符集中。控制器：

30、他是一个有限状态的自动机，该机器有预定的有限个状态并能根据输入从一个状态转移到另一个状态，但任何时候它只能处于这些状态中的一种。读写头：它任何时候总是指向磁带上的一个符号。5图灵机磁带是如何划定数据界限的？划定的数据图灵机纸带的方法之一是使用两个空格，一个在数据和在数据结束的开始。6当读/写头完成读写一个符号后，下一步是什么？每读写完一次后，它向左移，向右移或留在原地。7状态转移图域图灵机控制器有何联系？状态转移图是一个图形表示的程序为图的图。8转移图和转移表有何联系，他们有相同的信息吗？谁包含的信息更多一点呢？9什么是哥德尔数？怎样用哥德尔数证明停机问题是不可解决的？Gödel数是一个无符号整数，分配给每个程序可以写在一个特定的语言。在中断程序，我们代表一个程序为Gödel数时，程序是另一个程序的输入。10比较并区分多项式可解决问题和非多项式可解问题的复杂性。11 A 12 C 13 B 14 D 15 A 16 D 17