第7章算法程序与计算系统之灵魂练习题答案解析

《大学计算机基础与计算思维》课后习题参考答案第1章计算、计算机与计算思维............................. 第2章数据的计算基础计算机硬件系统第4章操作系统基础 (11)第5章算法与数据结构 (13)第6章程序设计及软件工程基础 (17)第7章数据库技术 (19)第8章计算机网络 (22)第9章信息安全与职业道德 (24)第10章计算软件第11章办公软件Office 2010算机科学与技术学院计算机基础教学部28 292015年9月第1章计算、计算机与计算思维1.1举例说明可计算性和计算复杂性的概念。

答：对于给定的一个输入，如果计算机器能在有限的步骤内给出答案，这个问题就是可计算的。

数值计算、能够转化为数值计算的非数值问题（如语咅、图形、图像等）都是可计算的。

汁算复杂性从数学上提出计算问题难度大小的模型，判断哪些问题的讣算是简单的，哪些是困难的，研究计算过程屮时间和空间等资源的耗费情况，从而寻求更为优越的求解复杂问题的有效规则，例如著名的汉诺塔问题。

1.2列举3种电子计算机岀现之前的计算工具，并简述其主要特点。

答:（1）算盘通过算法口诀化，加快了计算速度。

（2）帕斯卡加法器通过齿轮旋转解决了自动进位的问题。

（3）机电式计算机Z・l,全部采用继电器，第一次实现了浮点记数法、二进制运算、带存储地址的指令等设计思想。

1.3简述电子计算机的发展历程及各时代的主要特征。

答：第一代一一电子管计算机（1946—1954年）。

这个时期的计算机主要釆用电子管作为运算和逻辑元件。

主存储器采用汞延迟线、磁鼓、磁芯，外存储器采用磁带。

在软件方面，用机器语言和汇编语言编写程序。

程序的编写与修改都非常繁琐。

计算机主要用于科学和工程计算。

第二代一一晶体管计算机（1954—1964年）。

计算机逻辑元件逐步由电子管改为晶体管, 体积与功耗都有所降低。

主存储器采用铁脸氧磁芯器，外存储器釆用先进的磁盘，汁算机的速度和可靠性有所提高。

习题答案习题1（参考答案）1．计算的本质是什么？计算的本质就是基于规则的符号串变换。

2．三大科学思维是指什么？理论思维、实验思维、计算思维3．什么是计算思维？计算思维的基本特征有哪些？计算思维是指运用计算机科学的思想、方法和技术进行问题求解、系统设计，以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。

从计算科学的角度分析，计算思维包括6个方面的特征：抽象性、数字化、构造性、系统化、虚拟化和网络化。

4．什么是算法？算法的基本特征有哪些？算法（Algorithm）是在有限步骤内求解某一问题所使用的一组定义明确的规则。

通俗地讲，就是计算机解题的步骤。

一个算法应该具有以下五个重要特征。

（1）有穷性：一个算法必须保证执行有限步之后结束。

（2）确定性：算法的每一步骤必须有确定的定义。

（3）输入：一个算法有0个或多个输入，以刻画运算对象的初始情况。

0个输入是指算法本身给定了初始条件。

（4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。

（5）可行性：算法上描述的操作在计算机上都是可以实现的。

5．算法的复杂度分为哪两种？算法的复杂性用复杂度来说明，分为时间复杂度和空间复杂度。

时间复杂度：执行该算法所需要的计算工作量，一般用所需基本运算的执行次数来度量。

空间复杂度：执行该算法所需的内存空间，一般用算法程序本身占的空间+输入的初始数据占的空间+算法执行过程中所需的额外空间的总和来表示。

6．什么是程序？程序与算法的区别是什么程序是为了实现特定目标或解决特定问题而用计算机语言编写的指令序列，它由算法和数据结构组成。

算法与程序的区别：计算机程序是算法的一个实例，同一个算法可以用不同的计算机语言来表达。

7．简述程序设计语言发展的过程。

计算机程序设计语言从最初的机器代码到今天接近自然语言的表达，经过了四代演变。

一般认为机器语言是第一代，符号语言即汇编语言为第二代，面向过程的高级语言为第三代，面向对象的高级语言为第四代。

第1章计算机系统结构的基本概念1.1 解释下列术语层次机构：按照计算机语言从低级到高级的次序，把计算机系统按功能划分成多级层次结构，每一层以一种不同的语言为特征。

这些层次依次为：微程序机器级，传统机器语言机器级，汇编语言机器级，高级语言机器级，应用语言机器级等。

虚拟机：用软件实现的机器。

翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序，然后再在这低一级机器上运行，实现程序的功能。

解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效程序。

执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复，直到解释执行完整个程序。

计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。

在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。

计算机组成：计算机系统结构的逻辑实现，包含物理机器级中的数据流和控制流的组成以及逻辑设计等。

计算机实现：计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、底板的划分与连接，信号传输，电源、冷却及整机装配技术等。

系统加速比：对系统中某部分进行改进时，改进后系统性能提高的倍数。

Amdahl定律：当对一个系统中的某个部件进行改进后，所能获得的整个系统性能的提高，受限于该部件的执行时间占总执行时间的百分比。

程序的局部性原理：程序执行时所访问的存储器地址不是随机分布的，而是相对地簇聚。

包括时间局部性和空间局部性。

CPI：每条指令执行的平均时钟周期数。

测试程序套件：由各种不同的真实应用程序构成的一组测试程序，用来测试计算机在各个方面的处理性能。

存储程序计算机：冯·诺依曼结构计算机。

其基本点是指令驱动。

程序预先存放在计算机存储器中，机器一旦启动，就能按照程序指定的逻辑顺序执行这些程序，自动完成由程序所描述的处理工作。

系列机：由同一厂家生产的具有相同系统结构、但具有不同组成和实现的一系列不同型号的计算机。

7.1假设有如图7.1所示的交通死锁。

a.证明这个例子中实际上包括了死锁的四个必要条件。

b.给出一个简单的规则用来在这个系统中避免死锁。

a.死锁的四个必要条件: (1)互斥；（2）占有并等待；（3）非抢占；（4）循环等待。

互斥的条件是只有一辆车占据道路上的一个空间位置。

占有并等待表示一辆车占据道路上的位置并且等待前进。

一辆车不能从道路上当前的位置移动开（就是非抢占）。

最后就是循环等待，因为每个车正等待着随后的汽车向前发展。

循环等待的条件也很容易从图形中观察到。

b.一个简单的避免这种的交通死锁的规则是，汽车不得进入一个十字路口如果明确地规定，这样就不会产生相交。

7.2考虑如下的死锁可能发生在哲学家进餐中，哲学家在同个时间获得筷子。

讨论此种情况下死锁的四个必要条件的设置。

讨论如何在消除其中任一条件来避免死锁的发生。

死锁是可能的，因为哲学家进餐问题是以以下的方式满足四个必要条件：1）相斥所需的筷子， 2 ）哲学家守住的筷子在手，而他们等待其他筷子， 3 ）没有非抢占的筷子，一个筷子分配给一个哲学家不能被强行拿走，4 ）有可能循环等待。

死锁可避免克服的条件方式如下： 1 ）允许同时分享筷子， 2 ）有哲学家放弃第一双筷子如果他们无法获得其他筷子，3 ）允许筷子被强行拿走如果筷子已经被一位哲学家了占有了很长一段时间4 ）实施编号筷子，总是获得较低编号的筷子，之后才能获得较高的编号的筷子。

7.3一种可能以防止死锁的解决办法是要有一个单一的，优先于任何其他资源的资源。

例如，如果多个线程试图访问同步对象A•…E，那么就可能发生死锁。

（这种同步对象可能包括互斥体，信号量，条件变量等），我们可以通过增加第六个对象来防止死锁。

每当一个线程希望获得同步锁定给对象A•••E，它必须首先获得对象F的锁.该解决方案被称为遏制：对象A•••E的锁内载对象F的锁。

对比此方案的循环等待和Section7.4.4的循环等待。

这很可能不是一个好的解决办法，因为它产生过大的范围。

1.1什么是计算机一、计算机包括硬件和软件。

硬件包括嵌入式和移动式1.2为什么学习计算机一、计算思维：运用计算机科学的基础概念去求解问题、设计系统和理解人类行为，其本质是抽象和自动化。

二、思维是创新的源头，技术与知识是创新的支撑1.3计算与自动计算一、什么是计算1.简单计算2.复杂计算（便于人计算的计算）3.复杂计算（规则简单但计算量很大，人很难完成的计算）二、计算机计算特点：1.规则简单。

但计算量大2.只要人为设计，计算机也能采用人使用的计算规则3.针对性较弱，使用的的是一般性规则，可以解决更多问题三、自动计算的前提条件1.“数据”的表示2.程序（“计算规则”的表示）3.数据与程序的“自动存储”4.程序的“自动执行”即表示——存储——执行三过程另：能否自动执行程序是判断是不是计算机的标准四、计算机的探索过程计算辅助工具（算盘不是计算机，是计算辅助工具）帕斯卡——帕斯卡机（准第一台机械计算机）意义：告诉人们可以用纯机械代替人的思维和记忆，从而开辟了自动计算的道路莱布尼茨——莱布尼茨机意义：实现了连续重复自动执行他本人提出二进制数及其计算规则，是数理逻辑的创始人其他重要工作巴贝奇——分析机的概念（可执行程序的机器）差分机（可以在一定程度上变化计算规则，自动处理不同函数的计算过程）阿达·奥古斯塔——为差分机编制了人类历史上第一批程序杰卡德——打孔卡意义：实践了输入手段问题希尔——希尔代数意义：为数字计算机的电路设计提供了理论基础现代计算机（可执行任意可变的计算规则）五、差分机的原理迭代原理1.4 电子自动计算——元器件十进制二进制（复杂简单）元器件系统一、电子管时代电子管（存储0和1的元器件）的发明：1895年发明了第一只真空二极管第一台电子计算机：1946 ENIAC冯·诺依曼提出运算与存储分离，解决了存储与读取速度与计算速度不匹配的问题，提升了计算性能，这是结构上的创新（冯诺依曼计算机）二、晶体管时代晶体管的发明：1947发明了第一只点接触晶体管（可制成集成电路）第一台晶体管计算机：1953 TRADIC三、集成电路时代集成电路的发明：1959 由J.Kilby发明四、超大规模集成电路时代摩尔定律----每18个月芯片能力增长一倍软件包括应用软件和系统软件计算系统的探索过程一、计算机需要解决的问题1、数据的存取与表示2、计算规则的自动执行3、信息的表达与存储4、基本流程：输入→控制与计算→输出→储存二、计算系统的发展历程1、微处理器的发展（1）定义：微处理器由一片或少数几片大规模集成电路组成的中央处理器。

第1章计算机的基本知识习题答案1．计算机是由哪几部分组成的？计算机系统的组成:硬件和软件硬件是指有形的物理设备，是计算机系统中物理装置的总称。

包括运算器、存储器、控制器、输入设备、输出设备五大部分。

软件是指为了运行、管理、维护和使用计算机所编制的各种程序。

软件在很大程度上决定计算机整体功能的发挥。

硬件和软件共同组成计算机系统。

2．简述计算机的工作原理。

计算机的基本工作原理，是由美籍匈牙利科学家冯·诺依曼于1946年首先提出来的。

他的基本思想可以概括为三条:（1）计算机由运算器、控制器、存储器、输入设备、输出设备五大组成部分。

（2）程序和数据在计算机中用二进制数表示。

（3）计算机的工作过程是由存储程序控制的。

计算机把程序和数据通过输入设备输入到存储器，启动计算时，控制器将程序指令逐条取出，并分析指令要求做什么，例如将存储器中某单元的数据取到运算器，进行规定的运算，并将运算结果送回存储器。

，最后将运算结果由存储器送到输出设备，完成了一个完整的工作过程。

3. 简述计算机软硬件之间的关系。

只有硬件的计算机称为裸机，计算机硬件本身不能工作，只有在计算机中安装了软件系统后才能正常工作。

硬件是软件的工作基础，软件是硬件功能的扩充和完善。

两者相互依存，相互促进。

软件与硬件的结合，构成完整的计算机系统。

实现计算机硬件与软件连接功能的是BIOS（Basic Input System基本输入输出系统）系统，它存储于固化在计算机主板上的一块ROM（只读存储器）中。

在基本输入输出系统的上层是操作系统，下层是计算机硬件系统，在操作系统之上的是各种应用软件。

计算机硬件系统、基本输入输出系统、操作系统、各种应用软件的层次关系如下图所示。

4．计算机有哪些主要性能指标。

(1)运算速度(2)字长(3)内存储器的容量(4)外存储器的容量(5)指令系统第2章主板习题答案1．简述计算机主板的分类。

1．按主板的结构分类按主板的结构标准不同可分为AT、Baby-AT、Micro-ATX、ATX、NLX和BTX六种：（1）AT主板（2）Baby-AT主板（3）ATX和Micro ATX主板（4）NLX主板（5）BTX主板2．按主板上的CPU架构分类（1）SLOT 1/ SLOT 2主板（2）Socket 939主板（3）Socket 775主板3.按主板逻辑芯片组分类芯片组（Chipset）是主板的核心组成部分,对于主板而言，芯片组几乎决定了这块主板的功能，进而影响到整个电脑系统性能的发挥，芯片组是主板的灵魂。

计算机章节测试题及答案1. 在计算机科学中，什么是算法？请给出一个简短的定义，并举一个例子说明。

算法是一组解决问题或执行特定任务的明确指令序列。

它是将输入转换为输出的步骤的有序集合。

算法可以在计算机科学的各个领域中使用，例如排序、搜索、图形处理等。

举例：冒泡排序算法是一种简单的排序算法。

它通过比较相邻的元素并交换它们的位置，将较大的元素逐渐向右移动到列表的末尾，同时将较小的元素逐渐向左移动到列表的开头。

这个过程迭代进行，直到整个列表按照升序排列。

2. 什么是编程语言？请简要解释编程语言的作用和分类。

编程语言是一种用于编写计算机程序的形式化语言。

它是程序员与计算机之间进行交流的媒介，用于描述和实现算法和逻辑。

编程语言根据其设计和用途可以分为多种类型，包括低级语言和高级语言。

低级语言如汇编语言更接近计算机硬件的原始指令，而高级语言如Java和Python则更加人类可读和易于理解。

3. 请解释什么是面向对象编程（OOP）以及面向对象编程的基本概念。

面向对象编程（OOP）是一种编程范式，它将程序中的数据和功能组织为对象的集合，这些对象通过相互传递消息来进行交互。

面向对象编程的基本概念包括封装、继承和多态。

- 封装（Encapsulation）：将相关的数据和方法封装在对象中，以实现数据的保护和安全性。

对象通过暴露有限的接口来与外部进行交互。

- 继承（Inheritance）：定义对象之间的层次结构，子类可以继承父类的属性和方法，并可以通过重写和扩展来进行自定义。

- 多态（Polymorphism）：不同对象对相同的消息作出不同的响应。

同一个方法名可以根据调用对象的不同而表现出不同的行为。

4. 简要说明数据库的概念和作用，并列举常见的数据库管理系统（DBMS）。

数据库是一个有组织的数据集合，它以结构化的方式存储、管理和检索数据。

数据库可以用于存储企业的各种数据，如客户信息、订单记录、产品目录等。

常见的数据库管理系统（DBMS）包括：- Oracle- MySQL- Microsoft SQL Server- PostgreSQL- MongoDB这些DBMS提供了数据管理、查询和安全性等方面的功能，并可根据需求进行扩展和定制。

第1章计算机概述一、单项选择题A B D B C C D B A D二、简答题1. 根据计算机所采用的电子逻辑元件可将计算机的发展划分为4个发展阶段，每个阶段所采用的元器件分别为：电子管，晶体管，中、小规模集成电路，大规模、超大规模集成电路。

2. 冯·诺依曼计算机主要由4部分组成：运算器、存储器、控制器、输入/输出设备。

3. 衡量计算机性能的指标主要有5个，分别为：字长、主频、存储容量、运算速度和存取周期。

4. 计算机的特点：1）能自动连续、高速度地运算；2）运算速度快；3）运算精度高；4）具有超常的记忆能力；5）具有可靠的逻辑判断能力。

按运算规模，计算机可分为巨型机、大型机、中型机、小型机、微型机和工作站。

第2章计算机中的数据一、单项选择题A ABC B二、计算题1．（1）7 （2）511 （3）40762．（1）766O （2）201O （3）265O3．（1）251O （2）6272O （3）64361363O4．（1）0.1B （2）≈101.01B （3）110011B三、简答题1. 计算机采用二进制表示数据主要有以下4个原因：1）二进制物理上易于实现；2）二进制运算法则简单；3）二进制编码机器可靠性高；4）二进制通用性和逻辑性强。

2. 在计算机中，所有数值型数据都用二进制编码来表示，这串二进制编码称为该数据的机器数，数据原来的表现形式称为“真值”。

一个进制中数码的个数称为“基数”。

3. 带符号整数常用的编码形式有3种，分别为原码、反码和补码。

1）原码表示法为：最高位是符号位（0表示正，1表示负），其余各位表示数的绝对值大小。

2）反码表示法为：最高位是符号位（0表示正，1表示负），正数的反码与原码相同，负数的反码是在其原码的基础上，除符号位外各位求反。

3）补码表示法为：最高位是符号位（0表示正，1表示负），正数的补码与原码相同，负数的补码是在该数反码的最低位加1。

4. 要表示文本，必须先对每个可能出现的字符进行表示。

第7章软件工程习题(答案)一、选择题1. D2. B3. C4. B5. A6. C7. A8. D9.C 10. B11. C 12.C 13.D二、简答题1．什么叫软件危机？答：随着计算机应用的普及和深化，计算机软件的数量、规模、复杂程度和开发所需的人力、物力等都在急剧增加，计算机发展初期个人编写小程序的传统方法，已不再适合现代大型软件的开发，用传统方法开发出来的许多大型软件甚至无法投入运行。

同时，由于计算机应用领域和硬件技术得到丁飞速发展，软件的生产速度、质量和规模远远适应不了对软件的需求，造成大量人力、物力、财力的浪费，在软件开发和维护过程中出现了巨大的困难。

计算机领域把大型软件开发和维护过程中遇到的一系列严重问题称为“软件危机”(Software Crisis)。

2．软件危机的表现形式是什么？答：软件危机的表现形式：(1) 软件的质量难以保证开发的软件可靠性差。

由于在开发过程中，没有确保软件质量的体系和措施，在软件测试时，又没有严格的、充分的、完全的测试，提交给用户的软件质量差，在运行中暴露出大量的问题。

这种不可靠的软件，轻者会影响系统正常工作，重者会发生事故，造成生命财产的重大损失。

(2) 软件开发成本和开发进度难以控制经费预算经常突破，完成时间一再拖延。

由于缺乏软件开发的经验和软件开发数据的积累，使得开发工作的计算很难制定。

主观盲目制定的计算，执行起来和实际情况有很大差距，使得开发经费一再突破。

由于对工作量和开发难度估计不足，进度计划无法按时完成，开发时间一再拖延。

(3) 软件的维护非常困难开发的软件可维护性差。

开发过程没有统一的、公认的规范，软件开发人员按各自的风格工作，各行其事。

开发过程无完整、规范的文档，发现问题后进行杂乱无章的修改。

程序结构不好，运行进发现错误也很难修改，导致维护性差。

(4) 用户对“已完成”的软件系统不满意开发的软件不能满足用户要求。

开发初期对用户的要求了解不够明确，未能得到明确表达。

习题11-1 单向选择题1-5 B D A B B 6-10 B B C D A1-2 填空题1. 1946，ENIAC2. 四，电子管、晶体管、中小规模集成电路、大规模和超大规模集成电路3. 计算机硬件系统计算机软件系统4. 运算器、控制器、存储器、输入设备和输出设备1-3 思考题1. 计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。

计算思维具有以下特性：1)计算思维是概念化的，而不是程序化的。

2)计算思维是每个人需掌握的根本技能，而不是刻板的重复性工作。

3)计算思维不是计算机的思维方式，而是人类解决问题的一种思维方式。

4)计算思维是数学和工程思维的互补与融合5)计算思维是思想，不是产品6)计算思维面向所有的人，所有的地方2. 可以模拟那些不容易观察到的现象，可以求解用理论和实验手段无法解决的重大科学技术问题。

计算方法突破了实验和理论科学方法的局限，并进一步提高了人们对自然和社会的洞察力，为科学研究与技术创新提供了新的重要手段和理论基础。

计算已和理论、实验一起，被公认为科学的第三大支柱3. 计算机（computer）俗称电脑，是一种用于高速计算的电子计算机器，可以进行数值计算，又可以进行逻辑计算，还具有存储记忆功能。

是能够按照程序运行，自动、高速处理海量数据的现代化智能电子设备。

其主要特点有：1)运算速度快2)运算精度高3)可靠性高4)具有逻辑判断功能，逻辑性强5)存储容量大6)自动化程度高4. 存储程序的工作原理是：在计算机中设置存储器，将程序和数据存放到存储器中，计算机按照程序指定的逻辑顺序依次取出存储器中的内容进行处理，直到得出结果。

习题22-1 选择题1-5 D C B C B 6-10 D B D A B 11-15 B A B B C2-2 填空题1.13075O = 163DH= 5693D2.10101001.1B= 251.4O = a9.8H3.1110111111B= 1677O= 959 D4.原码：11000011 反码：10111100 补码：101111015.F4E8H6.位图矢量图2-3 思考题1.所谓信息是人们用于表示具有一定意义的符号的集合。