新编计算机科学概论刘艺蔡敏习题与答案.docx
《新编计算机科学概论刘艺蔡敏习题与答案.docx》由会员分享，可在线阅读，更多相关《新编计算机科学概论刘艺蔡敏习题与答案.docx（21页珍藏版）》请在冰点文库上搜索。
新编计算机科学概论刘艺蔡敏习题与答案
第0章习题
（1）复习题
1、简述计算机科学的研究领域。
数值和符号计算、算法和数据结构、体系结构、操作系统、程序设计语言、软件方法学和工程、数据库和信息检索、计算理论、人工智能和机器人学等。
（P2）
2、简述现代计算机的发展简史。
计算机发展经历了算盘时代、机械时代和机电时代这些原始阶段。
自从电子计算机问世以来，计算机经历了电子管时代、晶体管时代、集成电路时代和大规模、超大规模集成电路时代等，发展速度越来越快。
（P8-16）
3、试分析计算机对社会的影响。
计算机的产生与发展使得社会对计算机产生了依赖，也改变了我们人类的生活方式，并带来了许多有关于伦理和犯罪的问题。
（P16-P17）
4、试列出与计算机科学相关的学科及技术。
计算机科学是一门实用性很强、发展极其迅速的面向广大社会的学科，它建立在数学、电子学（特别是微电子学）、磁学、光学、精密机械等多门学科的基础之上,与数学、计算机程序设计、软件工程和计算机工程等学科之间存在不同程度的交叉和覆盖。
（P2）
5、尝试到网络上搜索关于计算机学科中几个典型问题的资料。
提示本书P4-P7页列出了一些经典问题，大家可以查找相关的情况
6、简述电子数字计算机的发展趋势。
.
计算机将向更高性能、更加易用、联网更广泛和更专业的应用发展。
随着硬件技术和算法设计的进步，计算机的处理能力将进一步提高，计算机有能力处理更加复杂和规模更大的问题。
随着计算机向智能化方向发展，计算机具有人的某些智能，如学习和推理的能力。
（P14-P15）
7、谈谈你对电子计算机的印象。
提示：
可从计算机的应用、能力、社会影响等方面考虑
8、试述计算机模型与计算机的联系和区别。
图灵设想所有的计算都可能在一种特殊的机器上执行，通用图灵机是对现代计算机的首次描述，该机器只要提供了合适的程序就能做任何运算。
而计算机只是一种计算的工具。
（P4）
9、列举出你所知道的操作系统。
提示：
可从互联网上了解，或向周围的人们打听
（2）练习题
（1）填空题
1、ACM是____________组织的简称。
国际计算机组织．
第一章习题
（1）复习题
1、试述数制的概念。
位置化数字系统中，在数字中符号所占据的位置决定了其表示的值。
大多数人使用的数字系统是以10为底的，也就是十进制。
二进制数字系统是最简单的数字系统。
（P21-23）
2、列举出你所知道的数字系统。
提示：
根据本章内容和自己接触过的情况，也可以上网搜索有关资料。
3、谈谈二进制、八进制和十六进制等数字表示方法各有什么有点和缺点。
八进制就是逢8进位，十六进制就是逢16进位，2、8、16，分别是2的1次方，3次方，4次方。
这三种进制之间可以非常直接地互相转换。
八进制数或十六进制数实际上是缩短了的二进制数，但保持了二进制数的表达特点。
（P23-P25）
4、为什么使用二进制计算的时候会出现溢出？
因为存储空间大小（即存储单元的位的数量）的限制，可以表达的整数范围是有限的。
二进制补码中两个整数相加的法则是，2个位相加，将进位加到下一列。
如果最左边的列相加后还有进位，则舍弃它。
如果在最高位有进位，那就会产生溢出。
（P29-32）
5、反码和补码相对于原码有什么优点？
计算机中的数是用原码表示的还是用反码、补码表示的？
数值的反码表示法是用最高位存放符号，并将原码的其余各位逐位取反。
反码的取值空间和原码相同且一一对应。
在补码表示法中，正数的补码表示与原码相同，即最高符号位用0表示正，其余位为数值位。
而负数的补码则为它的反码、并在最低有效位（即D0位）加1所形成。
处理器内部默认采用补码表示有符号数。
（P29）
6、汉字编码有哪几种？
各自的特点是什么？
汉字的编码有国际码、机内码等。
在国标码的字符集中共收录了6763个常用汉字和682个非汉字字符，汉字机内码是与ASCII对应的，用二进制对汉字进行的编码。
由于汉字数量多，一般用2个字节来存放汉字的内码，即双字节字符集（double-bytecharacterset，简称DBCS）。
（P36-37）
7、图像是如何压缩存储的？
哪一种图像占用空间最小，为什么？
图形压缩编码的考虑主要由于位图文件体积太大，人们研究通过编码的形式，在保证图像具备一定质量的前提下，缩小图像文件的大小。
压缩编码按其对图像质量的影响可分为无损压缩和有损压缩两类。
当前最主流的图像压缩方式是JPEG，JPEG压缩技术十分先进，即能支持无损压缩，也支持大压缩比的有损压缩。
（P40-P41）
8、ASCII码是什么编码？
为什么国际上推行Unicode码？
ASCII编码是由美国国家标准学会制定的标准单字节字符编码方案，用于基于文本的数据。
ASCII扩展自Unicode码是计算机世界里最重要的标准，但它存在严重的国际化问题ASCII．
第二章习题
（1）复习题
1．简述冯?
诺依曼原理，冯?
诺依曼结构计算机包含哪几部分部件，其结构以何部件为中心？
答：
冯?
诺依曼理论的要点包括：
指令像数据那样存放在存储器中，并可以像数据那样进行处理；指令格式使用二进制机器码表示；用程序存储控制方式工作。
这3条合称冯?
诺依曼原理冯?
诺依曼计算机由五大部分组成：
运算器、控制器、存储器、输入设备、输出设备，整个结构一般以运算器为中心，也可以以控制器为中心。
（P52-P55）
2．简述计算机体系结构与组成、实现之间的关系。
答：
计算机体系结构通常是指程序设计人员所见到的计算机系统的属性，是硬件子系统的结构概念及其功能特性。
计算机组成（computerorganization）是依据计算机体系结构确定并且分配了硬件系统的概念结构和功能特性的基础上，设计计算机各部件的具体组成，它们之间的连接关系，实现机器指令级的各种功能和特性。
同时，为实现指令的控制功能，还需要设计相应的软件系统来构成一个完整的运算系统。
计算机实现，是计算机组成的物理实现,就是把完成逻辑设计的计算机组成方案转换为真实的计算机。
计算机体系结构、计算机组成和计算机实现是三个不同的概念，各自有不同的含义，但是又有着密切的联系，而且随着时间和技术的进步，这些含意也会有所改变。
在某些情况下，有时也无须特意地去区分计算机体系结构和计算机组成的不同含义。
（P48-P52）
3．根据指令系统结构划分，现代计算机包含哪两种主要的体系结构？
答：
根据指令系统结构划分，现代计算机主要包含：
CISC和RISC两种结构。
（P57）
4．简述RISC技术的特点？
答：
从指令系统结构上看，RISC体系结构一般具有如下特点：
（1）精简指令系统。
可以通过对过去大量的机器语言程序进行指令使用频度的统计，来选取其中常用的基本指令，并根据对操作系统、高级语言和应用环境等的支持增设一些最常用的指令;
（2）减少指令系统可采用的寻址方式种类，一般限制在2或3种;
（3）在指令的功能、格式和编码设计上尽可能地简化和规整，让所有指令尽可能等长;
（4）单机器周期指令，即大多数的指令都可以在一个机器周期内完成，并且允许处理器在同一时间内执行一系列的指令。
（P59-60）
5．有人认为，RISC技术将全面替代CISC，这种观点是否正确，说明理由？
答：
不正确。
与CISC架构相比较，RISC计算机具备结构简单、易于设计和程序执行效率高的特点，但并不能认为RISC架构就可以取代CISC架构。
事实上，RISC和CISC各有优势，CISC计算机功能丰富，指令执行更加灵活，这些时RISC计算机无法比拟的，当今时代，两者正在逐步融合，成为CPU设计的新趋势。
（P60-62）
6．什么是流水线技术？
答：
流水线技术，指的是允许一个机器周期内的计算机各处理步骤重叠进行。
特别是，当执行一条指令时，可以读取下一条指令，也就意味着，在任何一个时刻可以有不止一条指令在“流水线”上，每条指令处在不同的执行阶段。
这样，即便读取和执行每条指令的时间保持不变，而计算机的总的吞吐量提高了。
（P60-61）
．并行处理结构包含哪几种主要的体系结构，分别有什么特点？
7．
第三章习题
（1）复习题
1．计算机由哪几部分组成，其中哪些部分组成了中央处理器？
答：
计算机硬件系统主要由运算器、控制器、存储器、输入设备、输出设备等五部分组成
其中，运算器和控制器组成中央处理器（CPU）。
（P69）
2．试简述计算机多级存储系统的组成及其优点？
答：
多级存储系统主要包括：
高速缓存、主存储器和辅助存储器。
把存储器分为几个层次主要基于下述原因：
（1）合理解决速度与成本的矛盾，以得到较高的性能价格比。
（2）使用磁盘、磁带等作为外存，不仅价格便宜，可以把存储容量做得很大，而且在断电时它所存放的信息也不丢失，可以长久保存，且复制、携带都很方便。
（P74-P75）
3．简述Cache的工作原理，说明其作用。
答：
Cache的工作原理是基于程序访问的局部性的。
即主存中存储的程序和数据并不是CPU每时每刻都在访问的，在一段时间内，CPU只访问其一个局部。
这样只要CPU当前访问部分的速度能够与CPU匹配即可，并不需要整个主存的速度都很高。
Cache与虚拟存储器的基本原理相同，都是把信息分成基本的块并通过一定的替换策略，以块为单位，由低一级存储器调入高一级存储器，供CPU使用。
但是，虚拟存储器的替换策略主要由软件实现，而Cache的控制与管理全部由硬件实现。
因此Cache效率高并且其存在和操作对程序员和系统程序员透明，而虚拟存储器中，页面管理虽然对用户透明，但对程序员不透明；段管理对用户可透明也可不透明。
Cache的主要作用是解决了存储器速度与CPU速度不匹配的问题，提高了整个计算机系统的性能。
（P77）
4．描述摩尔定律的内容，并说明其对于计算机的发展具有怎样的指导意义？
答：
摩尔定律（Moorelaw）源于1965年戈登·摩尔（GordonMoore，时任英特尔（Intel）公司名誉董事长）的一份关于计算机存储器发展趋势的报告。
根据他对当时掌握的数据资料的整理和分析研究，发现了一个重要的趋势：
每一代新芯片大体上包含其前一代产品两倍的容量，新一代芯片的产生是在前一代产生后的18-24个月内。
随着计算机技术的发展，摩尔定律得到业界人士的公认，并产生巨大的反响，逐渐成为硬件领域最重要的规律。
许多基于未来预期的研究和预测都是以它为理论基础。
这里需要特别指出，摩尔定律并非数学、物理定律，而是对发展趋势的一种分析预测，因此，无论是它的文字表述还是定量计算，都应当容许一定的宽裕度。
从某种意义上说，摩尔定律是关于人类创造力的定律，而不是物理学定律。
摩尔定律实际上是关于人类信念的定律，当人们相信某件事情一定能做到时，就会努力去实现它。
摩尔当初提出他的观察报告时，在某种程度上是给了人们一种信念，使大家相信他预言的发展趋势一定会持续。
而所以摩尔定律在长达40多年的时间里不断被证实，正是由于人们这些年来的不懈努力。
摩尔提出的周期可以认为是英特尔公司芯片研发的基本计划周期。
（P72-P73）
5．与主存相比Cache具有哪些特点？
答：
主存相比Cache具有以下特点：
（1）Cache一般用存取速度高的SRAM元件组成，其速度已经与CPU相当。
（2）Cache与虚拟存储器的基本原理相同，都是把信息分成基本的块并通过一定的替换策略，以块为单位，由低一级存储器调入高一级存储器，供CPU使用。
但是，虚拟存储器的替换策略主要由软件实现，而Cache的控制与管理全部由硬件实现。
因此Cache效率高并且其存在和操作对程序员和系统程序员透明，而虚拟存储器中，页面管理虽然对用户透明，但对程序员不透明；段管理对用户可透明也可不透明。
（3）Cache的价格较贵，为了保持最佳的性能价格比，Cache的容量应尽量小，但太小会影响命中率，所以Cache的容量是性能价格比和命中率的折衷。
（P77）
第五章习题
（1）复习题
1、试述数据和数据结构的概念及其区别。
数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。
（P113）
2、列出算法的五个重要特征并对其进行说明。
算法具有以下五个重要的特征：
有穷性：
一个算法必须保证执行有限步之后结束。
确切性：
算法的每一步骤必须有确切的定义。
输入：
一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。
输出：
一个算法有一个或多个输出，以反映对输入数据加工后的结果。
没有输出的算法没有实际意义。
可行性：
算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
（P115）
3、算法的优劣用什么来衡量？
试述如何设计出优秀的算法。
时间复杂度空间复杂度（P117）
4、线性和非线性结构各包含哪些种类的数据结构？
线性结构和非线性结构各有什么特点？
线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。
所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。
树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。
（P118P122）
5、简述树与二叉树的区别；简述树与图的区别。
树用来描述层次结构，是一对多或多对一的关系；二叉树（BinaryTree）是个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。
二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。
图也称做网，是一种比树形结构更复杂的非线性结构。
在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。
（P121-P124）
6、请举出遍历算法在实际中使用的例子。
提示：
根据实际生活中需要逐个访问处理的情况举例。
7、编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。
用适当的测试数据来验证这个算法。
提示：
根据查找算法和串中求子串的算法，查找输入串中以单个字符形式的子串。
8、若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?
（1）搜索失败；
（2）搜索成功，且表中只有一个关键码等于给定值k的对象；
的对象，要求一次搜索找出所有对k搜索成功，且表中有若干个关键码等于给定值（3）
第4章操作系统习题
（1）复习题
1、什么是操作系统？
答：
操作系统（OperatingSystem，简称OS）是管理计算机系统资源、控制程序执行，改善人机界面，提供各种服务，合理组织计算机工作流程和为用户使用计算机提供良好运行环境的一类系统软件。
（Ｐ８９）
2、操作系统的基本功能是什么？
答：
操作系统是用户与计算机硬件之间的接口。
使得用户能够方便、可靠、安全、高效地操纵计算机硬件和运行自己的程序。
操作系统合理组织计算机的工作流程，协调各个部件有效工作，为用户提供一个良好的运行环境。
操作系统是计算机系统的资源管理者，负责管理包括处理器、存储器、I/O设备等硬件资源和程序和数据等软件资源，跟踪资源使用情况，监视资源的状态，满足用户对资源的需求，协调各程序对资源的使用冲突；为用户提供简单、有效使用资源统一的手段，最大限度地实现各类资源的共享，提高资源利用率。
（Ｐ９０－９１）
3、操作系统的基本组成有哪些？
答：
操作系统构成的基本单位包括内核和进程、线程。
内核对硬件处理器及有关资源进行管理，给进程的执行提供运行环境。
进程是程序动态执行的过程。
（Ｐ９１）
4、操作系统如何分类？
答：
根据系统运行的方式分类，操作系统的基本类型有三种：
批处理系统、分时系统和实时系统。
具备全部或兼有两者功能的系统称通用操作系统。
根据系统的运行环境分类的操作系统有：
微机操作系统、网络操作系统、分布式操作系统和嵌入式操作系统。
（Ｐ９2-94）
5、什么是进程？
它与程序是什么关系？
答：
进程是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。
程序是静态的概念，它以文件形式存在于辅助存储器中，进程是动态的概念，程序执行时创建进程，一个程序多次执行创建多个进程，这多个进程可同时存在于机器的内存中。
进行执行完成后结束，进程终止，但程序本身仍然存在，并不因进程的终止而消失。
（P91，96-98）
6、什么是死锁？
死锁产生的原因是什么？
答：
在系统运行过程中，多个进程间相互永久等待对方占用的资源而导致各进程都无法继续运行的现象称为“死锁”。
发生死锁后，实际上各进程都占有一定的资源而都不能正常使用，系统的资源实际上被罢占并空闲的，是严重的资源的浪费；若无外力作用，进程不能自己从死锁中解脱出来。
产生死锁的原因主要是：
系统资源不足，进程会因争夺有限的资源而陷入死锁；进程运行推进的顺序不合适，进程运行推进顺序与速度不同，也可能产生死锁；资源分配不当等。
（P99-100）
第六章习题
（1）复习题
1、简述自然语言与形式语言的概念以及区别、汇编语言与机器语言的概念及区别。
自然语言是某一社会发展中形成的一种民族语言，而形式语言是进行形式化工作的元语言，它是以数学和数理逻辑为基础的科学语言。
用机器指令形式编写的程序称为机器语言，
用带符号或助记符的指令和地址代替二进制代码成为语言进化的目标。
这些使用助记符语言的语言后来就被称之为汇编语言。
（P135P136）
2、什么是高级程序设计语言？
它有什么特点？
高级语言是汇编语言的一种抽象。
高级语言的设计目标就是使程序员摆脱汇编语言细节的繁琐。
高级语言同汇编语言都有一个共性，那就是：
它们必须被转化为机器语言，这个转化的过程称为解释或编译。
（1）高级语言接近算法语言，易学、易掌握；
（2）高级语言设计出来的程序可读性好，可维护性强，可靠性高；
（3）高级语言与具体的计算机硬件关系不大，其程序可移植性好，重用率高；
（4）高级语言自动化程度高，开发周期短，利于提高程序的质量。
（P138）
3、列举程序设计语言的几种范型。
程序语言大致分为命令式程序设计语言、面向对象的程序设计语言、函数式程序设计语言和逻辑型程序设计语言等范型。
（P138-140）
4、简述语言虚拟机。
提示：
语言虚拟机是某种语言的解释器。
语言虚拟机是建立在硬件和操作系统之上，针对不同的硬件和操作系统有不同的虚拟机，通过语言虚拟机屏蔽掉硬件的差异。
这样使得硬件系统能够支持这种语言编写的程序的有效执行。
目前最流行的语言虚拟机是Java虚拟机。
（P147）
5、计算机执行用高级语言编写的程序有哪些途径？
它们之间的主要区别是什么？
提示：
主要有编译、解释等方式，也有两种方式的混合使用的形式。
编译是使用编译器将高级语言编写的源程序转换成计算机可以执行的机器语言可执行程序，也可以理解为用编译器产生可执行程序的动作。
编译方式是一次编译，然后执行程序可以反复多次执行。
解释是另一种将高级语言转换为可执行程序的方式。
与编译不同，解释性语言的程序不需要编译，省了道工序，解释性语言在运行程序的时候才翻译，每个语句都是执行的时候才翻译。
这样解释性语言每执行一次就要翻译一次，效率比较低。
近来随着网络的发展，为了实现跨平台但同时又保证一定的效率，出现了编译、解释混合的方式，先用伪编译形成效率较高中间代码，再用语言虚拟机进行解释执行，以屏蔽掉硬件的差异。
．
第七章习题及解答
（1）复习题
1、关系模型由哪三部分组成？
关系模型的概念是建立在实体——关系方法基础上的。
数据模型通常由数据结构、数据操作和完整性约束三部分组成。
（P159）
2、关系的完整性分为哪三类？
关系数据模型的操作必须满足关系的完整性约束条件。
完整性是指数据的精确性和可靠性。
完整性约束是防止数据库中存在不符合语义规定的数据和防止因错误信息的输入/输出造成无效操作或错误信息而提出的。
数据完整性分为四类：
实体完整性、域完整性、参照完整性、用户定义的完整性。
（P161）
3、常见的关系数据库产品有哪些？
提示：
本书第7.2节（P159）介绍了一些产品，可以通过网络、专业报纸杂志再了解一些情况
4、什么是表？
什么是记录？
两者的区别是什么？
提示：
表和记录是关系数据库中用于记录数据的两种数据结构。
表是记录的上层结构，表示关系，记录是表的一行，表示一个关系的实例。
P160-161
5、数据模型的组成要素是什么？
提示：
数据模型是严格定义的一组概念的集合。
这些概念精确地描述了系统的静态特征、动态特性与完整性约束条件。
因此数据模型通常由数据结构、数据操作和完整性约束三部分组成。
数据结构：
数据结构是所研究的对象类型的集合。
这些对象是数据库的组成成分，它们包括两类：
一类是与数据类型、内容、性质有关的对象；另一类是与数据之间联系有关的对象。
数据结构是刻画一个数据模型性质最重要的方面。
在数据库系统中，人们通常按照其数据结构的类型来命名数据模型。
例如层次结构、网状结构和关系结构的数据模型分别命名为层次模型、网状模型和关系模型。
数据结构是对系统静态特征的描述。
数据操作：
数据操作是针对数据库中各种对象（类型）的实例（取值）允许执行的操作的集合，包括操作及有关的操作规则。
数据库主要有检索和更新（包括插入、删除、修改）两大类操作。
数据模型必须定义这些操作的确切含义、操作符号、操作规则（如优先级）以及实现操作的语言。
数据操作是对系统动态特性的描述。
数据的约束条件：
数据的约束条件是一组完整性规则的集合。
完整性规则是给定的数据模型中数据及其关系所具有的制约和依存规则，用以限定数据模型的数据库状态以及状态的变化，以保证数据的正确、有效、相容。
（P157）
6、数据字典是什么？
数据字典有几类？
是进行详细的数据收集和数据分析所获得的数据字典是系统中各类数据描述的集合，提示：
本章习题
（1）复习题
1．简述软件的特点
答：
软件相对硬件而言有许多不同特点。
了解这些特别之处能够帮助我们全面、正确地理解计算机软件。
（1）软件是一种逻辑实体，而不是具体的物理实体，具有很强的抽象性。
我们只能把它记录在介质上，或在系统上运行，但却无法直接通过我们的眼睛看到软件的形态。
（2）软件是一个逻辑上复杂而规模上庞大的系统，涉及技术、管理等多方面的问题。
如果将代码比作零件，则一个软件是由成百上千万个零件组成的复合体，而且其结构远较机械装置复杂。
应该说软件的复杂程度高于同等规模的硬件产品。
（3）软件是智力产品，其价值体现在解决问题的知识和能力，而并不体现在软件载体本身。
软件的生产方式与硬件明显不同，设计方法和制造阶段不同；软件的生成成本主要在研发设计上，而大量复制几乎没有成本。
（4）在软件的运行和使用期间，没有硬件的磨损、老化问题。
但软件维护比硬件维护要复杂得多，软件的故障主是由于对软件的改变和使用环境的变化引起的。
（5）软件的开发和运行对硬件有较强依赖关系。
在软件开发有可移植性的问题，现在通
升级会员 