计导习题答案1_伤城文章网
计导习题答案1
计算机科学与导论-思想与方法习题答案 计算机科学与导论 思想与方法习题答案 思想与方法习题 习题一 习题一1.1 简述计算学科的定义及其根本问题。 简述计算学科的定义及其根本问题答：计算学科是对描述和变换信息的算法过程进行的系统研究，包括理论、分析、设计、效率、实现和应用等。 学科的根本问题是：什么能被（有效地）自动进行。 1.2 简述计算学科专业名称的演变。 简述计算学科专业名称的演变。 答：计算学科专业名称主要包括：计算机科学、信息系统、软件工程、计算机工程、和信息技术。 1962 年，美国普渡大学开设了最早的“计算机科学”学位课程。当时，在美国的一些高校还开设有与计算相关的两给学位课程：电子 工程和信息系统。而在我国，早在 1956 年，就开设了“计算装置与仪器”专业。 20 世纪 70 年代，在美国， “计算机工程” （也被称为“计算机系统工程” ）从电子工程学科中脱离出来，成为一个独立的二级学科，并 被人们所接受。 随着软件规模及其复杂度的增加，制造可靠软件的困难越来越大，出现了所谓的软件危机；针对这种情况，1968 年秋，北大西洋公约 组织（NATO）在当时的联邦德国召开了一次会议，提出了软件工程的概念。20 世纪 70 年代未、80 年代初，在一些计算机科学专业的学 位课程中，引入了软件工程的内容，然而，这些内容，只能让学生了解软件工程，却不能使学生明白如何成为一名软件工程师。于是，人 们开始构建单独的软件工程学位课程。20 世纪 80 年代，英国和澳大利亚，最早开设了“软件工程”这样的学位课程。 20 世纪 90 年代，计算机已成为公司各级人员使用的基本工具，而计算机网络则成为公司信息的中枢，人们相信它有助于提高生产力， 而原有的学术学位课程并不能满足社会的需求，于是，在美国等西方国家，不少大学相继开设了“信息系统”“信息技术”等学位课程。 、 至此，需要指出的是，即使在美国，5 个分支学科（专业）同时在一所大学开设的情况也是不多的，更多的高校仍然是以传统的“计 算机科学”为主；在我国，则是以“计算机科学与技术”为主。 1.3 简述计算学科主要专业培养的不同。 简述计算学科主要专业培养的不同。 答：对计算学科五个主要专业的培养侧重点简述如下。 （1）计算机科学，涉及很宽的范围，包括了计算的理论、算法和实现，以及机器人技术、计算机视觉、智能系统、生物信息学和其 他新兴的有前途的领域。 计算机科学是计算各学科的基础，计算机科学专业培养的学生，更关注计算的理论基础和算法，并能从事软件开发及其相关的理论研 究。 （2）计算机工程，是对现代计算系统和由计算机控制的有关设备上的软件与硬件的设计、构造、实施和维护进行研究的学科。 计算机工程专业培养的学生，更关注设计并实施集软件和硬件设备为一体的系统，如嵌入式系统。 （3）软件工程，是指以系统、学科、定量的方法，把工程应用于软件的开发、运行和维护；同时，展开对上述过程中各种方法和途 径进行研究的学科。 软件工程专业培养的学生，更关注以工程规范进行的大规模软件系统开发与维护的原则，并尽可能避免软件系统潜在的风险。 （4）信息系统，是指如何将信息技术的方法与企业生产和商业流通结合起来，以满足这些行业需求的学科。 信息系统培养的学生，更关注信息资源的获取、部署、管理及使用，并能分析信息的需求和相关的商业过程，能详细描述并设计那些 与目标相一致的系统。 （5）信息技术，从广义上来说，它包括了所有计算技术的各个方面，在此专指作为一门学科的信息技术。它侧重在一定组织及社会 环境下，通过选择、创造、应用、集成和管理的计算技术来满足用户的需求。 与信息系统相比，信息技术更关注于“信息技术”的技术层面，而信息系统则重于“信息技术”的“信息”层面。 信息技术专业培养的学生，更关注基于计算机的新产品及其正常的运行和维护，并能使用相关的信息技术来计划、实施和配置计算机 系统。 1.4 学科知识体由哪三个层次组成？ 学科知识体由哪三个层次组成？ 答：学科知识体依次由分枝领域、知识单元、以及知识点三个层次组成。 最高层是分支领域，它代表一个特定的学科子领域；例如， “计算机科学”知识体由 DS（离散结构） 、PF（程序设计基础） 、AL（算 法和复杂性） 、AR（体系结构和组织） 、OS（操作系统） 、NC（网络计算） 、PL（程序设计语言） 、HC（人机交互） 、GV（图形学和可视化 计算） 、IS（智能系统） 、IM（信息管理） 、SP（社会与职业问题） 、SE（软件工程） 、CN（计算科学和数值计算方法）等 14 个分枝领域组 成。 分支领域之下又分为更小的知识单元，它代表该领域中的主题模块；例如，在计算机科学知识体中，分枝领域“DS（离散结构） ”又 由 DS1（函数、关系、集合） 、DS2（基本逻辑） 、DS3（证明方法） 、DS4（计算基础） 、DS5（图和树） 、DS6（离散概率）等 6 个知识单 元组成。 知识单元又被细分为众多的知识点，这些知识点构成了知识体结构的最底层。例如，在上述例子中，知识单元“DS1（函数、关系、 1集合） ”又有函数 (满射，到内的映射，逆函数，复合函数)、关系 (自反，对称，传递，等价关系)、集合 (文氏图, 补集，笛卡尔积，幂 集)、鸽笼原理、基数性和可数性等知识点组成。 1.5 分别列出计算机科学、计算机工程、软件工程和信息技术四个专业的核心课程。 分别列出计算机科学、计算机工程、软件工程和信息技术四个专业的核心课程。 工程 答：计算机科学专业的核心课程包括：计算机导论、程序设计基础、离散结构、算法与数据结构、计算机组成基础、计算机体系结构、 操作系统、数据库系统原理、编译原理、软件工程、计算机图形学、计算机网络、人工智能、数字逻辑、社会与职业道德。 计算机工程专业的核心课程包括：计算机导论、程序设计基础、离散结构、算法与数据结构、电路与系统、模拟与数字电子技术、数 字信息处理、数字逻辑、计算机组成结构、计算机体系结构、操作系统、计算机网络、嵌入式系统、软件工程、数据库系统原理、社会与 职业道德。 软件工程专业的核心课程包括：程序设计基础、面向对象方法学、数据结构和算法、离散结构、计算机体系结构、操作系统和网络、 数据库、工程经济学、团队激励和沟通、软件工程职业实践、软件工程与计算、软件工程导论、软件代码开发技术、人机交互的软件工程 方法、大型软件系统设计与软件体系结构、软件测试、软件设计与体系结构、软件详细设计、软件工程的形式化方法、软件质量保证与测 试、软件需求分析、软件项目管理、软件过程与管理、软件工程综合实习（含毕业设计） 。 信息技术四个专业的核心课程包括：信息技术导论、信息技术应用数学入门、程序设计与问题求解、数据结构与算法、计算机系统平 台、应用集成原理与工具、Web 系统与技术、计算机网络与互联网、数据库与信息管理技术、人机交互、面向对象方法、信息保障与安全、 社会信息学、信息系统工程与实践、系统管理与维护。 1.6 为什么说“计算机导论”课程的构建是一个重大问题？ 为什么说“计算机导论”课程的构建是一个重大问题？ 答：计算已成为一个庞大的学科，它涉及了数学、科学、工程和商业等领域，并包括了专业实践所需要的大量基础知识。学科知识体， 以及核心知识单元等内容的给出，为学科专业教学计划的制定奠定了基础。然而，由于知识单元，特别是知识点的大量罗列，也为计算学 科的教学带来了挑战。要解决计算学科内容大量罗列而产生的问题，就不得不先解决计算教育面临的另一个重要问题，即“计算机导论” 课程的构建问题。 1.7 简述“计算机导论”课程构建的关键及要实现的目标。 简述“计算机导论”课程构建的关键及要实现的目标。 答： “计算作为一门学科”报告认为， “计算机导论”课程要培养学生面向学科的思维能力，使学生领会学科的力量，以及从事本学科 工作的价值之所在。报告希望该课程能用类似于数学那样严密的方式将学生引入到计算学科各个富有挑战性的领域之中。 CC2001 报告认为，不管怎样设计， “计算机导论”这门课都应该讲授学科中那些富有智慧的核心思想。CC2004 和 CC2005 则进一步 指出，该课程的关键是课程的结构设计问题，现有的浓缩版结构显然不是一种好的课程结构，期待人们在该课程的结构设计上有所突破。 1.8 简介计算学科二维定义矩阵的概念。 简介计算学科二维定义矩阵的概念。 答： “计算作为一门学科”报告给出了计算学科二维定义矩阵的概念，为我们认知学科提供了一个模型。计算学科二维定义矩阵是对 学科一个高度的概括； 其横向维由抽象、 理论、 设计等 3 个过程组成， 纵向维由离散结构 （DS） 程序设计基础 、 （PF） 算法与复杂性 、 （AL） 、 体系结构（AR） 、操作系统（OS） 、网络计算（NC） 、程序设计语言（PL） 、人机交互（HC） 、图形学和可视化计算（GV） 、智能系统（IS） 、 信息管理（IM） 、软件工程（SE） 、社会与职业问题（SP） 、科学计算（CN）等 14 个学科知识领域组成。 在该定义矩阵中，不变的是 3 个过程（也称为 3 个学科形态） ；变化的是 3 个过程的具体内容（值） ，这一维的取名可以是学科知识领 域（或学科主领域） ，也可以为分支学科等。 1.9 本书是如何对“计算机导论”课程结构进行设计的？ 本书是如何对“计算机导论”课程结构进行设计的？ 答：本书将计算学科的认知问题具体为计算学科二维定义矩阵的认知问题，从而使计算学科的认知具体化。认知学科终究是通过概 念来完成的，而学科中所有的概念都蕴含在定义矩阵中。于是，可以从定义矩阵出发介绍学科，并在学科思想、方法这个较高的层面讲授 “计算机导论”课程，为学生后续专业课程的学习提供必要的认知基础。因此，本书将焦点放在定义矩阵，将把握学科的本质问题归约为 把握定义矩阵的本质问题，即对定义矩阵的“横向”和“纵向”关系的把握。 “横向”关系，即抽象、理论和设计 3 个过程的关系，是定义矩阵中最为重要的内容。它反映的是，人们在计算领域的认识规律， 即是从感性认识（抽象）到理性认识（理论） ，再由理性认识（理论）回到实践（设计）的过程。 “横向”关系还蕴含着学科中的基本问题。 由于人们对客观世界的认识过程就是一个不断提出问题和解决问题的过程，这种过程反映的正是抽象、理论和设计 3 个过程之间的相互作 用，它与 3 个过程在本质上是一致的。因此，在“计算机导论”课程的设计上，有必要将它与 3 个过程一起列入最重要的内容。 “纵向”关系，即各分支领域中具有共性的核心概念、数学方法、系统科学方法、社会与职业问题等内容的关系。这些内容蕴含在 学科 3 个过程中，并将学科各分支领域结合成一个完整的体系，而不是互不相关的领域。 显然，在定义矩阵中， “横向”关系最重要， “纵向”关系次之。因此，在“计算机导论”课程的设计上，可以将本章列为第一章， 而将学科的基本问题，抽象、理论和设计 3 个过程，学科中的核心概念，数学方法，系统科学方法，以及社会与职业问题分别列为第二至 第七章。 沿着定义矩阵这个关于学科概念的认知模型进行导引，优点在于，对学科进行总结的系统性。这种总结是回顾性的总结，不足在于， 对学科有争论的问题以及未来探索性的展望作用有限。为此，有必要构建最后一章，即“探讨与展望” 。 21.10 阅读前言，简述计算教育面临的三个重大问题，了解三个重大问题产生的背景。 阅读前言，简述计算教育面临的三个重大问题，了解三个重大问题产生的背景。 答：计算学科的“存在性”证明问题、计算学科核心课程的设置问题、以及“计算机导论”课程的构建问题是计算教育面临的三个重 大问题。 1989 年，ACM 攻关组提交了“计算作为一门学科”报告，明确指出了计算教育面临的上述三个重大问题。 “计算作为一门学科”报告 解决了计算教育面临的第一个重大问题，即学科的“存在性”证明问题。经过十多年的发展，计算学科已经成为大学最活跃的学科；计算 教育是否列入学科的争论已经不存在了，现在的问题是如何找到一种方法来满足这种需求。 CC1991 报告与“计算作为一门学科”报告一脉相承，由于没有给出学科核心课程的详细内容，最终没有获得预期的效果。CC2001 接 受了 CC1991 的教训，给出了计算机科学（CS）核心课程的详细设计，为 CE2004、SE2004、IT2005 等报告的制定提供了模式。现在，计算 学科有了非常详细的专业核心课程。然而，学科内容的庞杂，给计算学科的教学带来了困难。要解决计算学科内容庞杂的问题，就不得不 解决“计算机导论”课程的构建问题。 “计算作为一门学科”报告希望“计算机导论”课程能用类似于数学那样严密的方式将学生引入计算学科各个富有挑战性的领域之中。 CC2001 报告介绍了该课程的构建问题，并希望这门课讲授学科中那些富有智慧的核心思想。CC2004 和 CC2005 则进一步指出，该课程的关 键是课程的结构设计问题，现有的浓缩版结构显然不是一种好的课程结构，报告期待人们在该课程的结构设计上有所突破。习题二2.1 为什么说科学研究是从问题开始的？ 为什么说科学研究是从问题开始的？ 答：科学研究从问题开始，或者说科学始于问题而非观察；尽管通过观察可以引出问题，但在观察时必定带有问题，带有预期的设想， 漫无目的的观察是不存在的。 2.2 欧拉是如何对“哥尼斯堡七桥问题”进行抽象的？ 欧拉是如何对“ 哥尼斯堡七桥问题” 进行抽象的？ 答：为了解决哥德斯堡七桥问题，欧拉用 4 个点代表 4 个城区，用关于这 4 个点的 7 条线表示 4 个城区之间的 7 座桥，从而得到一个 含有 4 个点和 7 条线的无向图。这样做是基于该问题本质考虑的，它抽象出问题最本质的东西，忽视问题非本质的东西（如桥的长度、宽 度等） 。最终将哥尼斯堡七桥问题抽象为一个数学问题，即经过图中每边一次且仅一次的回路问题。欧拉在论文中论证了这样的回路是不 存在的，后来，人们把有这样回路的图称为欧拉图。 2.3 简述“欧拉回路”与“哈密尔顿回路”的区别。 简述“欧拉回路” 哈密尔顿回路”的区别。 答： “哈密尔顿回路问题”是访问除原出发结点以外的每个结点一次且仅一次并回到出发点，而“欧拉回路问题”是访问每条边一次 且仅一次并回到出发点。对任一给定的图是否存在“欧拉回路”前面已给出充分必要条件，而对任一给定的图是否存在“哈密尔顿回路” 至今仍未找到满足该问题的充分必要条件。 2.4 判断下列图中，哪个存在欧拉路径，哪个存在欧拉回路。 判断下列图中，哪个存在欧拉路径，哪个存在欧拉回路。答：a、b、c、d 都存在欧拉路径，a 存在欧拉回路。 2.5 判断下列图中，哪个存在哈密尔顿回路 判断下列图中，3答：b 存在哈密尔顿回路。 2.6 赛纳河流经巴黎的这一段河中有两个岛，河岸与岛间架设了 15 座桥。如下图所示。问： ）能否从某地出发，经过这 15 座桥各一次 赛纳河流经巴黎的这一段河中有两个岛， 座桥。如下图所示。 （ 能否从某地出发， （l） 后再回到出发点？ 后再回到出发点？ （2）若不要求回到出发点，能否在一次散步中，穿过所有的桥各一次？若可以，请把路径写出。答： （1）不能 （2）可以，从 C 或 D 出发都能找到这样的路径。例如：C－A－C－A－C－B－C－B－A－D－A－D－A－D－B－D 2.7 以“梵天塔问题”为例，说明理论上可行的计算问题实际上并不一定能行。 梵天塔问题”为例，说明理论上可行的计算问题实际上并不一定能行。 答：对于许多问题，我们可以找到相应的算法，从而证明该问题在理论上是可计算的。例如，对于“梵天塔问题” ，可以基于递归方 法给出相应的求解算法。但是，由于该问题的复杂度过高，又使得实际上是不可行的。例如，对于“梵天塔问题” 当盘子个数为 64 时， ， 需要移动盘子的次数为 264-1=，如果每秒移动一次，也需要花费大约 5849 亿年的时间；假定计算机以每秒 1000 万 个盘子的速度进行搬迁，则需要花费大约 58490 年的时间。 2.8 什么是顺序程序？什么是并行程序？ 什么是顺序程序？什么是并行程序？ 答：略。 2.9 什么是 NP 类问题？请举例说明。 类问题？请举例说明。 答：在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为 P 类问题，而将所有在多项式时间内可以验证的问题称为 NP 类问题。例如“证比求易算法” 。 2.10 简述阿姆达尔定律。 述阿姆达尔定律。 答：设 f 为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p 为处理器的数目，Sp 为并行计算机系统最大的加 速能力（单位：倍） ，则Sp ≤1 1? f f+ p设 f=1%，p→∞，则 Sp=100。这说明在并行计算机系统中即使有无穷多个处理器，若串行执行操作占全部操作的 1%，则其解题速度 4与单处理器的计算机相比最多也只能提高 100 倍。因此，对难解性问题而言，单纯地提高计算机系统的速度是远远不够的，而降低算法复 杂度的数量级才是最关键的问题。 2.11* 对于本质上可以进行并行计算的特定问题（如 Google 的搜索引擎，其计算本质上是并行的，该引擎可以在不同的处理器上运行不 的搜索引擎，其计算本质上是并行的，该引擎可以在不同的处理器上运行不 于本质上可以进行并行计算的特定问题（ 同的查询） 阿姆达尔定律对这类问题适用吗？ ，阿姆达尔定律对这类问题适用吗 同的查询） 阿姆达尔定律对这类问题适用吗？ ， 答：适用。 2.12 简述停机问题。 简述停机问题。 答：停机问题是指：针对任意给定的图灵机和输入，寻找一个一般的算法（或图灵机） ，用于判定给定的图灵机在接收了初始输入后， 能否到达终止状态，即停机状态。若能找到这样的算法，我们说停机问题可解，否则，不可解。换句话讲说，就是我们能不能找到这样一 个测试程序，它能判断出任意的程序在接收了某个输入并执行后，能不能终止。若能，则停机问题可解，否则，不可解。 2.13 简述找零问题、背包问题与贪婪算法。 简述找零问题、背包问题与贪婪算法。 答：设有不同面值的钞票，要求用最小数量的钞票给顾客找某数额的零钱，这就是通常说的找零问题。 给定 n 种物品和一个背包，设 Wi 为物品 i 的重量，Vi 为其价值，C 为背包的重量容量，要求在重量容量的限制下，尽可能使装入的物 品总价最大，这就是背包问题。 贪婪算法是一种传统的启发式算法，它采用逐步构造最优解的方法，即在算法的每个阶段，都作出在当时看上去最好的决策，以获得 最大的“好处” ，换言之，就是在每一个决策过程中都要尽可能的“贪” 直到算法中的某一步不能继续前进时，算法才停止。在算法的 ， 过程中， “贪”的决策一旦作出，就不可再更改，作出“贪”的决策的依据称为贪婪准则。贪婪算法是从局部的最优考虑问题的解决方案， 具有简单快捷的优点。但是，这种从局部，而不是从整体最优上考虑问题的算法，并不能保证求得的最后解为最优解。 2.14 简述“两军问题” 简述“两军问题” 。 答：两军问题可以这样描述：一支白军被围困在一个山谷中，山谷的两侧是蓝军。困在山谷中的白军人数多于山谷两侧的任一支蓝军， 而少于两支蓝军的总和。若一支蓝军对白军单独发起进攻，则必败无疑；但若两支蓝军同时发起进攻，则可取胜。两支蓝军希望同时发起 进攻，这样他们就要传递信息，以确定发起攻击的具体时间。假设他们只能派谴士兵穿越白军所在的山谷（惟一的通信信道）来传递信息， 那么在穿越山谷时，士兵有可能被俘，从而造成消息的丢失。现在的问题是：如何通信，以便蓝军必胜。 2.15 简述互联网软件的分层结构。 简述互联网软件的分层结构。 答：Internet 软件有四个层次（图 2.11） ，即应用层，传输层，网络层和链路层，每层均有相应的协议进行支撑，每台 Internet 上的机 器都具有这样的软件及层次结构。一条信息在应用层产生，向下通过传输层和网络层的处理，然后通过链路层被传递。这个信息由目的地 的链路层接收，通过网络层和传输层的逆操作，最后将信息送到应用层。 2.16 “生产者－消费者问题”和“哲学家共餐问题”反映的是计算学科中的什么问题？ 生产者－消费者问题” 哲学家共餐问题”反映的是计算学科中的什么问题？ 答：反映了计算学科中的进程同步问题。 2.17 用图表示程序的 3 种基本结构。 种基本结构。 答：ATPFA AB B P F T(a) 顺序结构(b) 选择结构(c) 循环结构2.18 “GOTO 语句问题”的提出直接导致了计算学科哪一个分支领域的产生？ 语句问题”的提出直接导致了计算学科哪一个分支领域的产生？ 答：关于“GOTO 语句”问题的争论直接导致了一个新的学科分支领域，即程序设计方法学的产生。 2.19 “图灵测试”和“中文屋子”是如何从哲学的角度反映人工智能本质特征的？ 图灵测试” 中文屋子”是如何从哲学的角度反映人工智能本质特征的？ 答： “图灵测试”不要求接受测试的思维机器在内部构造上与人脑一样，它只是从功能的角度来判定机器是否能思维，也就是从行为 主义这个角度来对“机器思维”进行定义。尽管图灵对“机器思维”的定义是不够严谨的，但他关于“机器思维”定义的开创性工作对后 人的研究具有重要意义，因此，一些学者认为，图灵发表的关于“图灵测试”的论文标志着现代机器思维问题讨论的开始。 西尔勒借用语言学的术语非常形象地揭示了“中文屋子”的深刻寓意：形式化的计算机仅有语法，没有语义。因此，他认为，机器永 远也不可能代替人脑。作为以研究语言哲学问题而著称的分析哲学家西尔勒来自语言学的思考，的确给人工智能涉及的哲学和心理学问题 5提供了不少启示。 2.20 举例说明计算机中的博弈问题。 举例说明计算机中的博弈问题。 答：计算机中的博弈问题是人工智能领域研究的重点内容之一。其中最具代表性的是双人完备博弈，如国际象棋、西洋跳棋、围棋、 中国象棋等。对于任何一种双人完备博弈，都可以用一个博弈树（与或树）来描述，并通过博弈树搜索策略寻找最佳解。1997 年 5 月，由 IBM 公司研制的高性能并行计算机“深蓝”与国际象棋冠军卡斯帕罗夫交战，以两胜一负三平取得了胜利。 2.21 为什么说人要在计算能力上超过计算机是不现实的？ 为什么说人要在计算能力上超过计算机是不现实的？ 答：略。 2.22 简述计算机科学各主领域的内容。 简述计算机科学各主领域的内容。 答：计算机科学包括离散结构、程序设计基础、算法与复杂性、体系结构、操作系统、网络计算。程序设计语言、人机交互、图形 学和可视化计算、智能系统、信息系统、软件工程、社会和职业问题、科学计算等主领域。对各个主领域的内容简述如下。 离散结构包括集合论、数理逻辑、代数系统、图论和组合数学等重要内容。 程序设计基础领域的知识由程序设计实践中所需要的基本技能和概念组成，该领域的知识单元包括了基本程序设计概念、基本数据 结构、算法程序等。 算法是计算机科学和软件工程的基础。现实世界中任何软件系统的性能仅依赖于两个方面：所选择的算法、以及在各不同层次实现的 效率。算法研究能够深刻理解问题的本质和可能的求解技术，而不依赖于具体的程序设计语言、程序设计模式、计算机硬件、或其他任何 与实现有关的内容。 计算机在计算技术中处于核心地位。作为计算专业的学生，都应该对计算机系统的功能部件、功能特点、性能和相互作用有一定的理 解，而不应该只将计算机看作是一个执行程序的黑盒子。 操作系统是对计算机硬件行为的抽象，程序员用它来对硬件进行控制。操作系统还负责管理计算机用户间的共享资源（如文件等）。 网络计算包括的子领域有：计算机通信网络的概念和协议、多媒体系统、Web 标准和技术、网络安全、移动计算、以及分布式系统 等。 程序设计语言是程序员与计算机交流的主要工具。一个程序员不仅要掌握一种程序设计语言，更要了解各种程序设计语言的不同风 格。在工作中，程序员会将使用不同风格的语言，也会遇到许多不同的语言。为了迅速掌握一门新语言，程序员必须理解程序设计语言的 语义以及在不同的程序设计范式之间设计上的折中。为了理解程序设计语言实用的一面，还要求具有程序设计语言翻译和诸如存储分配等 方面的基础知识。 人机交互的重点，在于理解作为交互式对象的人的行为，知道怎样使用以人为中心的方法来开发和评价交互式软件系统。 图形学和可视化计算领域可以划分成计算机图形学、可视化、虚拟现实、计算机视觉等 4 个相互关联的领域。其中，计算机图形学是 一门以计算机产生，并在其上展示的图像进行信息交流的艺术和科学；计算机图形学的目标是对人的视觉中心及其他认知中心有进一步深 入的了解。可视化领域是为了确定并展示存在于（如计算和医学科学）和比较抽象的数据集中基本的相互关联的结构与关系；展示的主要 目标应当是发掘在数据集中替在的信息，从而有助于用户对它们的理解。虚拟现实是要让户能够经历由计算机图形学以及可能的其他感知 通道产生的三维环境，提供一种能增进用户与计算机创建的“世界”交互作用的环境。计算机视觉的目标是推导从一幅或多幅二维图像所 表示的出三维图像世界的性质和结构。 智能系统依赖于一整套关于问题求解、搜索算法以及机器学习技术的专门知识表示机制和推理机制。 信息系统包括信息获取、信息数字化、信息表示、组织、转化和信息的表现；有效地访问和更新存储信息的算法、数据建模和数据抽 象以及物理文件的存储技术、共享数据的信息安全、隐私性、完备性和保护。 软件工程是一门关于如何有效构建满足用户需求的软件系统所需的理论、知识和实践的学科。软件工程适应各种软件开发，它包含 需求分析和规格、设计、构建、测试、运行和维护等软件系统生存周期的所有阶段。软件工程使用工程化的方法、过程、技术和度量标准。 通过学习社会和职业问题主领域的知识，学生需要了解计算学科本身基本的文化、社会、法律和道德等问题，知道这个学科的过去、 现在和未来，同时也要了解在该学科的发展过程中起着重要作用的哲学问题、技术问题和美学价值观。学生应该有能力提出关于社会对信 息技术的影响问题，以及对这些问题的可能答案进行评价的能力。最后，学生需要认识到软/硬件销售商和用户的权利，还必须遵守相关 的职业道德。 科学计算领域提供了许多有价值的思想和技术，包括数值表示的精度、误差分析、数值技术、建模和仿真。 2.23 *计算机科学各主领域包括哪些基本问题？ 计算机科学各主领域包括哪些基本问题？ 计算机科学各主领域包括哪些基本问题 答：计算机科学包括离散结构、程序设计基础、算法与复杂性、体系结构、操作系统、网络计算。程序设计语言、人机交互、图形 学和可视化计算、智能系统、信息系统、软件工程、社会和职业问题、科学计算等主领域。 程序设计基础主领域的基本问题包括： （1）对给定的问题，如何进行有效的描述并给出算法？（2）如何正确选择数据结构？（3） 6如何进行设计、编码、测试和调试程序？ 算法与复杂性主领域的基本问题包括： （1）对于给定的问题类，最好的算法是什么？要求的存储空间和计算时间有多少？空间和时 间如何折衷？（2）访问数据的最好方法是什么？（3）算法最好和最坏的情况是什么？（4）算法的平均性能如何？（5）算法的通用性如 何？ 体系结构主领域的基本问题包括： （1）实现处理器、内存和机内通信的方法是什么？（2）如何设计和控制大型计算系统，而且使其 令人相信，尽管存在错误和失败，但它仍然是按照我们的意图工作的？（3）哪种类型的体系结构能有效地包含许多在一个计算中能并行 工作的处理元素？（4）如何度量性能？ 操作系统主领域的基本问题包括： （1）在计算机系统操作的每一个级别上，可见的对象和允许进行的操作各是什么？ （2）对于 每一类资源，能够对其进行有效利用的最小操作集是什么？ （3）如何组织接口才能使得用户只需与抽象的资源而非硬件的物理细节打交 道？ （4）作业调度、内存管理、通信、软件资源访问、并发任务间的通信以及可靠性与安全的控制策略是什么？（5）通过少数构造规 则的重复使用进行系统功能扩展的原则是什么？ 网络计算主领域的基本问题包括： （1）网络中的数据如何进行交换？（2）网络协议如何验证？（3）如何保证网络的安全？（4）分 布式计算的性能如何评价？（5）分布式计算如何组织才能够使通过通信网连接在一起的自主计算机参加到一项计算中，而网络协议、主 机地址、带宽和资源则具有透明性？ 程序设计语言主领域的基本问题包括： （1）语言（数据类型、操作、控制结构、引进新类型和操作的机制）表示的虚拟机的可能组 织结构是什么？（2）语言如何定义机器？机器如何定义语言？（3）什么样的表示法（语义）可以有效地用于描述计算机应该做什么？ 人―机交互主领域的基本问题包括： （1）表示物体和自动产生供阅览的照片的有效方法是什么？（2）接受输入和给出输出的有效方 法是什么？（3）怎样才能减小产生误解和由此产生的人为错误的风险？（4）图表和其他工具怎样才能通过存储在数据集中的信息去理解 物理现象？ 图形学和可视化计算主领域的基本问题包括： （1）如何选择支撑图像产生以及信息浏览的更好模型？（2）如何提取科学的（计算和 医学）和更抽象的相关数据？（3）图像形成过程的解释和分析方法。 智能系统主领域的基本问题包括： （1）基本的行为模型是什么？如何建造模拟它们的机器？（2）规则评估、推理、演绎和模式计算 在多大程度上描述了智能？ （3） 通过这些方法模拟行为的机器的最终性能如何？ （4） 传感数据如何编码才使得相似的模式有相似的代码？ （5）电机编码如何与传感编码相关联？（6）学习系统的体系结构怎样？（7）这些系统是如何表示它们对这个世界的理解的？ 信息系统主领域的基本问题包括： （1）使用什么样的建模概念来表示数据元素及其相互关系？（2）怎样把基本操作（如存储、定位、 匹配和恢复）组合成有效的事务？（3）这些事务怎样才能与用户有效地进行交互？（4）高级查询如何翻译成高质量的程序？（5）哪种 机器体系结构能够进行有效的恢复和更新？（6）怎样保护数据，以避免非授权访问、泄露和破坏？（7）如何保护大型的数据库，以避免 由于同时更新引起的不一致性？（8）当数据分布在许多机器上时如何保护数据、保证性能？（9）文本如何索引和分类才能够进行有效的 恢复？ 软件工程主领域的基本问题包括： 程序和程序设计系统发展背后的原理是什么？ （1） （2） 如何证明一个程序或系统满足其规格说明？ （3）如何编写不忽略重要情况且能用于安全分析的规格说明？（4）软件系统是如何历经不同的各代进行演化的？（5）如何从可理解性和 易修改性着手设计软件？ 社会和职业问题主领域的基本问题包括： （1）计算学科本身的文化、社会、法律和道德的问题； （2）有关计算的社会影响问题，以及 如何评价可能的一些答案的问题； （3）哲学问题； （4）技术问题以及美学问题。 科学计算主领域的基本问题包括： （1）如何精确地以有限的离散过程近似表示连续和无限的离散过程？（2）如何处理这种近似产生 的错误？（3）给定某一类方程在某精确度水平上能以多快的速度求解？（4）如何实现方程的符号操作，如积分、微分以及到最小项的归 约？（5）如何把这些问题的答案包含到一个有效的、可靠的、高质量的数学软件包中？习题三3.1 以“学生选课”为例，分析人们对客观世界的认识过程。 学生选课”为例，分析人们对客观世界的认识过程。 解： “学生选课”管理系统的研制过程蕴含了人们对客观世界从感性认识（通过 E-R 图，实现对例子的抽象）到理性认识（在关系数据理 论的指导下，通过建立更为适合的关系模型而实现对例子的理性认识） ，再由理性认识回到实践（在实现对“例子”的感性认识和理性认 识后，编写程序完成“学生选课”管理信息系统的工作）中来的科学思维方式。 3.2 请读者将所在班级若干学生（至少 10 人）以及他们选修课程的具体内容，根据以下关系模型进行填写。 请读者将所在班级若干学生（ 以及他们选修课程的具体内容，根据以下关系模型进行填写。 学生（学号，姓名，年龄，性别） ； 课程（课程号，课程名） ； 学生选课（学号，课程号，成绩） ； 7解： 学生 学号 03 06 09
学生选课 学号 04 06 09
课程号 01 05 02 07 03 09 10 01 02 01 成绩 90 88 89 80 96 92 88 76 90 86 姓名 黎明 李朋 张风 李红 王菲 周讯 刘德华 范冰冰 张艺谋 巩丽 年龄 20 19 20 20 19 20 21 19 22 20 性别 男 男 男 女 女 女 男 女 男 女 课程 课程号 01 02 03 04 05 06 07 08 09 10 课程名 计算机科学导论 高等数学 大学英语 离散数学 C 语言 操作系统 汇编语言 编译原理 数据库系统概论 离散数学3.3 请读者将所在班级若干学生（至少 10 人）的具体内容，根据以下关系模型进行填写，并分析可能出现的问题。 请读者将所在班级若干学生（ 的具体内容，根据以下关系模型进行填写，并分析可能出现的问题。 学生（学号，姓名，年龄，性别，系名，系主任） 学生（学号，姓名，年龄，性别，系名，系主任） 解： 学生 学号 03 06 09 姓名 黎明 李朋 张风 李红 王菲 周讯 刘德华 范冰冰 张艺谋 年龄 20 19 20 20 19 20 21 19 22 性别 男 男 男 女 女 女 男 女 男 系名 三院 三院 三院 三院 三院 三院 三院 三院 三院 系主任 黄廷磊 黄廷磊 黄廷磊 黄廷磊 黄廷磊 黄廷磊 黄廷磊 黄廷磊 黄廷磊该关系模式中出现了这样的传递函数依赖：学号（码）→系名，系名→系主任。因此，它不属于 3NF。会出现插入异常、删除异常和 冗余的问题。 3.4 什么是概念模型和关系模型？ 什么是概念模型和关系模型？ 8解：概念模型用于信息世界的建模，是客观世界到信息世界的抽象。最常用的描述客观世界并建立概念模型的抽象方法是Ｅ-Ｒ方法 （Entity-Relationship Approach） ，该方法也被称为实体－联系模型（或 E-R 图） 。 关系模型支持的是一种二维表结构的数据模型，它由关系数据结构、关系数据操作和关系数据的完整性约束条件三部分组成。其中关 系就是一张二维表。在关系模型中，客观世界的实体以及实体之间的各种联系均用关系来表示。 3.5 简述计算学科中 3 个学科形态的主要内容。 个学科形态的主要内容 形态的主要内容。 解：计算学科中，按客观现象的研究过程，抽象形态包括以下 4 个步骤的内容： （1）形成假设； （2）建造模型并作出预测； （3）设计实验并收集数据； （4）对结果进行分析。 计算学科中，从统一合理的理论发展过程来看，理论形态包括以下 4 个步骤的内容： （1）表述研究对象的特征（定义和公理） ； （2）假设对象之间的基本性质和对象之间可能存在的关系（定理） ； （3）确定这些关系是否为真（证明） ； （4）结论。 计算学科中，从为解决某个问题而实现系统或装置的过程来看，设计形态包括以下 4 个步骤的内容： （1）需求分析； （2）建立规格说明； （3）设计并实现该系统； （4）对系统进行测试与分析。 3.6 什么是形式语言？试举例说明。 什么是形式语言？试举例说明。 解：形式语言是进行形式化工作的元语言，它是以数学和数理逻辑为基础的科学语言。形式语言的基本特点有： （1）有一组初始的、专门的符号集； （2）有一组精确定义的，由初始的、专门的符号组成的符号串转换成另一个符号串的规则。在形式语言中，不允许出现根据形成规 则无法确定的符号串。 比如：语言 Z 定义为： 初始符号集：{a，b，c，d，e，(，)，+，?，×，÷}。形成规则：上述符号组成的有限符号串中，凡以符号“ （”开头且以“） ”结尾 的符号串，为一公式，否则不是。 Z 是一形式语言？ 3.7 图灵机有什么特点？它的工作原理是什么？ 图灵机有什么特点？它的工作原理是什么？ 解： （1）图灵机的特点 ① 图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，如下图所示。图灵机的带子被划分为一 系列均匀的方格。读写头可以沿带子方向左右移动，并可以在每个方格上进行读写。…bb10100010bbb…读－写头状态 ql 控制器图灵机 ② 写在带子上的符号为一个有穷字母表：{S0，S1，S2，…，Sp}。通常，可以认为这个有穷字母表仅有 S0、S1 两个字符，其中 S0 可以 看作是“0” 1 可以看作是“1” ，S ，它们只是两个符号。 ③ 机器的控制状态表为：{q1，q2，…，qm}。通常，将一个图灵机的初始状态设为 q1，在每一个具体的图灵机中还要确定一个结束状 态 qw。 一个给定机器的“程序”认为是机器内的五元组（qiSjSkR（或 L 或 N）ql）形式的指令集，五元组定义了机器在一个特定状态下读入 9一个特定字符时所采取的动作。5 个元素的含义如下： qi 表示机器目前所处的状态； Sj 表示机器从方格中读入的符号； Sk 表示机器用来代替 Sj 写入方格中的符号； R、L、N 分别表示向右移一格、向左移一格、不移动； ql 表示下一步机器的状态。 （2）图灵机的工作原理 机器从给定带子上的某起始点出发，其动作完全由其初始状态及机内五元组来决定。就某种意义而言，一个机器其实就是它作用于 纸带上的五元组集。 3.8 计算题：在图灵的带子机中，设 b 表示空格，q1 表示机器的初始状态，q4 表示机器的结束状态，如果带子上的输入信息是 ， 计算题：在图灵的带子机中， 表示空格， 表示机器的初始状态， 表示机器的结束状态， ， 的方格， 读入头对准最右边第一个为 1 的方格，状态为初始状态 q1。请写出执行以下命令后的计算结果。 。请写出执行以下命令后的计算结果。 q1 0 0 L q2 q1 1 0 L q3 q1 b b N q4 q2 0 0 L q2 q2 1 0 L q2 q2 b b N q4 q3 0 0 L q2 q3 1 0 L q3 q3 b b N q4 解：计算结果为
或 0。 （考试时需要写出步骤，标准见 67 页书籍） 3.9 简述冯?诺伊曼型计算机的体系结构及其特点。 简述冯?诺伊曼型计算机的体系结构及其特点。 解：冯?诺依曼计算机（单指令顺序存储程序式计算机）的体系结构由存储器、控制器、运算器、输入和输出设备等五个基本部件组成的， 如图所示：中央处理器输出 设备输入 设备控制器□□□…□□ 寄存器算术逻辑部件主 存 储 器辅助 存储 设备冯?诺依曼计算机的体系结构 冯?诺依曼计算机的体系结构，也即存储程序式计算机的体系结构的特点，是将程序与数据一样看待，对程序像数据那样进行适当的 编码，然后与数据一起共同存放在存储器中。这样，计算机就可以通过改变存储器中的内容，对数据进行操作。从原来对程序和数据的严 格区别到一样看待，这个观念上的转变是计算机史上的一场革命，它反映的正是计算的本质，即符号串的变化。 3.10 为什么说，从原来对程序和数据的严格区别到后来的一样看待，这个观念上的转变是计算机史上的一场革命。 为什么说，从原来对程序和数据的严格区别到后来的一样看待，这个观念上的转变是计算机史上的一场革命。 解：它反映的正是计算的本质，即符号串的变化。所以说从原来对程序和数据的严格区别到后来的一样看待，这个观念上的转变是计算机 史上的一场革命。 3.11 根据计算机输入设备和输出设备的定义，硬盘属于输入设备，还是输出设备？或者，既属于输入设备，又属于输出设备？ 根据计算机输入设备和输出设备的定义，硬盘属于输入设备，还是输出设备？或者，既属于输入设备，又属于输出设备？ 解：输入和输出设备是人与计算机进行交互的两大部件，一类是将信息输入计算机；一类是将信息输出计算机。 硬盘既属于输入设备，又属于输出设备。 103.12 CPU 与主存之间是用什么进行数据传递的？ 与主存之间是用什么进行数据传递的？ 解：CPU 与主存之间是用总线进行数据传递的。 3.13 现有一台计算机，它的总线宽度（也即数据电线的宽度）为 32 位，地址总线的宽度为 16 位，试问该计算机有多少不同的地址空间， 现有一台计算机，它的总线宽度（也即数据电线的宽度） 试问该计算机有多少不同的地址空间， 宽度 一次总线传送的数据位数是多少，最大值是多少？ 一次总线传送的数据位数是多少，最大值是多少？ 解：若总线宽度（也即数据电线的宽度）为 32 位，地址总线的宽度为 16 位，该计算机有 216 个不同的地址空间，一次总线传送的数据位 数是 32 位，最大值是 232-1。 3.14 在冯?诺伊曼型计算机中，运算器能否直接与主存和外存中的数据打交道？若不能，哪它只能与 CPU 中的什么储存单元打交道？ 在冯?诺伊曼型计算机中，运算器能否直接与主存和外存中的数据打交道？若不能， 中的什么储存单元打交道？ 解：在冯?诺伊曼型计算机中，运算器不能直接与主存和外存中的数据打交道；它只能与 CPU 中的控制单元打交道。 3.15 画出基于总线的计算机系统的硬件组成。 画出基于总线的计算机系统的硬件组成。 解：基于总线的计算机系统的硬件组成 3.16 如果一个指令系统有 12 条指令，请问操作码应该设置为多少位？若操作码有 5 位，那么最多可以设计多少条指令？ 条指令，请问操作码应该设置为多少位？ 那么最多可以设计多少条指令？ 解：如果一个指令系统有 12 条指令，操作码应该设置为 4 位？若操作码有 5 位，那么最多可以设计 25=32 条指令 3.17 据 Brooks hear 给出的机器指令集，指出下列指令的功能： 给出的机器指令集，指出下列指令的功能： a. C000 解： a. C000:停机； b. A205:将寄存器 2 中的数右移 5 次,每次将最低位移出的数字放在最高位的空缺处； c. 8123:将寄存器 2 和 3 中的数进行与运算,结果存入寄存器 1 中； d. 12A0:将内存 A0 单元中的数据取出,存入寄存器 2 中； e. 3312:将寄存器 3 中的数据存入主地址为 12 的内存单元中。 3.18 将下列自然语言用 Brooks hear 给出的机器指令描述： 给出的机器指令描述： a. 将十六进制数 A0 装入寄存器 0。 b. 将寄存器 1 中的值右移 3 位。 c. 将地址为 E8 内存单元的值装入寄存器 A。 d. 若寄存器 A 与寄存器 B 的值相等，则跳转到地址为 00 的内存单元所存储的指令执行。 e. 将寄存器 6 和寄存器 8 中的内容相与。 f. 将寄存器 1 的内容存入地址为 D2 的内存单元中。 11 b. A205 c. 8123 d. 12A0 e. 3312解： a. 将十六进制数 A0 装入寄存器 0。 b. 将寄存器 1 中的值右移 3 位。 c. 将地址为 E8 内存单元的值装入寄存器 A。 20A0 A103 1AE8d. 若 寄 存 器 A 与 寄 存 器 B 的 值 相 等 ， 则 跳 转 到 地 址 为 00 的 内 存 单 元 所 存 储 的 指 令 执 行 。 40B0,BA00 e. 将寄存器 6 和寄存器 8 中的内容相与。 8A68 f. 将寄存器 1 的内容存入地址为 D2 的内存单元中。31D2 3.19 问在下列哪些指令执行后 AA 单元中的值发生了改变？ 单元中的值发生了改变？ a. 13AA b. 22AA c. 3BAA d. 50AA e. B2AA 解：我们先看各条指令的功能： a. b. c. d. e. 13AA: 将内存 AA 单元中的数据取出,存如寄存器 3 22AA:将数 AA 存放到寄存器 2 中 3BAA:将寄存器 3 中的数据存入主存地址为 AA 的单元中(AA 单元中的值发生了改变) 50AA:将寄存器 A 中的用二进制补码表示的数与其自身相加,结果存入寄存器 0 B2AA:若寄存器 2 中的数与寄存器 0 中的数相同,就将内存 AA 单元中的数据存入程序计数器中;否则按原来的顺序继续执行所以 c 指令执行后 AA 单元中的值发生了改变。 3.20 Brooks hear 给出的机器指令，若执行指令 B000，程序计数器的值为多少？ 给出的机器指令， ，程序计数器的值为多少？ 解：Brooks hear 给出的机器指令，若执行指令 B000，程序计数器的值为 00。 3.21 在 Brooks hear 给出的机器中，地址 00 到 07 的内存单元中包含以下内容： 给出的机器中， 的内存单元中包含以下内容： 地址 00 01 02 03 04 05 06 07 内容 10 05 11 05 B1 00 C0 00若程序计数器置为 00，程序是否会终止，为什么？ 解：若程序计数器置为 00，程序不会终止。 因为该段指令的功能就不断地从 05 地址单元中取出数据放到寄存器 0 和寄存器 1 中，寄存器 0 和寄存器 1 中的数据始终相等，跳转 指令总是跳回到程序开始，如此反复，永不终止。 3.22 在 Brooks hear 给出的机器中，地址 00 到 07 的内存单元中包含以下内容： 给出的机器中， 的内存单元中包含以下内容： 地址 00 01 02 03 04 05 06 07 内容 11 A0 53 21 33 A0 C0 00a. 请描述程序的功能； b. 若开始时 A0 的值为 20，寄存器 1 的值 10，寄存器 2 的值 20，寄存器 3 的值 30，则程序结束时，A0 和这三个寄存器的值各是 12多少？ 解：a. 程序的功能： 地址 00 01 02 03 04 05 06 07 内容 11 A0 53 21 33 A0 C0 00 停机 将寄存器 3 中的数据存入主地址为 A0 的内存单元中，即[A0]= 40 将寄存器 2 和 1 中用补码表示的数相加，结果存入寄存器 3，即 R3=40 将地址为 A0 内存单元的值存入寄存器 1，即 R1=20若开始时 A0 的值为 20，寄存器 1 的值 10，寄存器 2 的值 20，寄存器 3 的值 30，则程序结束时，[A0]=40； R1=20；R2=20；R3=40。 3.23 在 Brooks hear 给出的机器中，地址 00 到 07 的内存单元中包含以下内容： 地址 00 01 02 03 04 05 06 07 内容 1A A0 AA 03 3A A0 C0 00若 A0 的值为 80，请问程序结束后 A0 的值为多少？ 解：若 A0 的值为 80，请问程序结束后 A0 的值为(10)16。 3.24 在 Brooks hear 给出的机器中，地址 00 到 07 的内存单元包含了以下内容： 地址 00 01 02 03 04 05 06 07 内容 2A B0 21 25 52 A1 C0 00机器从 00 开始执行，回答一下问题： a. 将执行了的指令转换成自然语言。 b. 该程序中用到哪些寄存器，在程序结束时它们的值各为多少？ 解：a. 将执行了的指令转换成自然语言。 地址 00 01 02 03 04 05 内容 2A B0 21 25 52 A1 将寄存器 A 和 1 中用补码表示的数相加,结果存入寄存器 2，即 R2= B0+25=D5 13 将十六进制数 25 装入寄存器 1 即 R1=25 将十六进制数 B0 装入寄存器 A 即 RA= B006 07C0 00 停机b. 该程序中用到寄存器 A，1，2，在程序结束时它们的值各为 RA= B0；R1=25；R2=D5。 3.25 在 Brooks hear 给出的机器中，地址 00 到 05 的内存单元中包含以下内容： 地址 00 01 02 03 04 05 11 02 31 0A C0 00 内容若开始程序计数器置为 00，然后执行，请问程序结束时，计数器的值为多少？程序完成了哪些事件序列？ 解：若开始程序计数器置为 00，然后执行，程序结束时，计数器的值为 05；程序完成了如下事件序列： （1）将 02 地址单元中数据取出，放入寄存器 1 中。 （2）将寄存器 1 中数据放入地址为 0A 的地址单元中。 （3）停机。 3.26 Brooks hear 给出的机器中，地址 A6 到 B1 的内存单元中包含以下内容： 地址 A6 A7 A8 A9 AA AB AC AD AE AF B0 B1 内容 20 A8 11 A8 22 20 53 01 85 23 C0 00机器从 00 开始执行，回答一下问题： a. 若机器每微秒执行一条指令，那么完成这个程序要多少时间？ b. 将以上指令翻译成自然语言。 c. 程序结束时，寄存器 5 的值是多少？ d. 20A8 与 31A8 的 A8 是一个意思吗？ 解： a. 若机器每微秒执行一条指令，那么完成这个程序要 6 微秒。 b. 将以上指令翻译成自然语言。 （1）将数 A8 放入到寄存器 0 中，即 R0=A8 （2）将内存 A8 单元中的数据取出，存入寄存器 1 中，即 R1=11 （2）将数 20 放入到寄存器 2 中，即 R2=20 （4）将寄存器 0 与 1 中的用二进制补码表示的数相加，将结果存入寄存器 3 中，即 R3=R0+R1=A8+11=B9 （5）将寄存器 2 与 3 中的数进行与运算，将结果存入寄存器 5 中，即 R5=R2 ∧R3=(∧(=20 （6）停机 c. 程序结束时，寄存器 5 的值是 20。 14d. 20A8 与 31A8 的 A8 不是一个意思，20A8 中的 A8 为一个 16 进制数，而 31A8 中的 A8 为内存地址单元的地址。 3.27 在 Brooks hear 给出的机器中，要将存储在地址为 A1 和 A2 内存单元中的值进行浮点相加，把结果装入地址为 A3 的内存单元，请问 给出的机器中， 内存单元中的值进行浮点相加， 的内存单元， 需要哪些步骤？ 需要哪些步骤？ 解： 11A1 将地址为 A1 内存单元的值存入寄存器 1 12A2 将地址为 A2 内存单元的值存入寄存器 2 5312 将寄存器 1 与寄存器 2 中的值进行浮点相加,结果存入寄存器 3 33A3 将寄存器 3 中的数据存入主地址为 A3 的内存单元中 3.28 Brooks hear 给出的机器中，假设内存单元地址从 00 开始，请用机器语言写一个程序，用来计算内存单元 B1，C1，D1 中的值，将 结果放入 E1。 3.29 在 Brooks hear 给出的机器中，假设内存单元地址从 00 开始，请用 Brooks hear 给出的机器指令实现以下操作。 给出的机器中， 开始， 给出的机器指令实现以下操作。 a. 将寄存器 1 与寄存器 2 中的值相加，存入内存单元 20； b. 将内存单元 25 的值，与寄存器 1 中的值相加，存入寄存器 3； c. 将寄存器 1 和寄存器 2 的内容互换； d. 比较内存单元 A0 和 A1 中值，若相同，则将其相加存入内存单元 A2，若不相同则将 其差存入内存单元 A3。 解： 地址 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 内容 50 12 30 20 10 25 53 01 40 10 40 21 40 02 10 A0 14 A1 B4 22 25 FF 96 45 25 01 54 56 57 151D 1E 1F 20 21 22 23 24 25 26 2704 37 A3 C0 00 51 04 31 A2 C0 003.30 什么是机器语言？什么是汇编语言？ 什么是机器语言？什么是汇编语言？ 解：每台数字电子计算机在设计中，都规定了一组指令，这组机器指令集合，就是所谓的机器指令系统。用机器指令形式编写的程序，称 为机器语言。 在机器指令的基础上，人们提出了采用字符和十进制数来代替二进制代码的思想，产生了将机器指令符号化的汇编语言。 3.31 简述 CISC 和 RISC 的设计思想。 的设计思想。 解：在实际机器研制的过程中，同时也要对指令系统进行设计。为了使机器具有更强的功能、更好的性能价格比，人们对机器指令系统进 行了研究：最初人们采用的是进一步增强原有指令的功能，并设置更为复杂的指令的方法，按照这种思路，机器指令系统将变得越来越庞 杂，采用这种设计思路的计算机被称为复杂指令系统计算机（CISC） 。 为了解决 CISC 中存在的问题，Patterson 等人提出了 RISC 的设计思路，这种设计思路主要是通过减少指令总数和简化指令的功能来 降低硬件设计的复杂度，从而提高指令的执行速度。按照这种思路，机器指令系统将得到进一步精简，采用这种设计思路的计算机被称为 精简指令系统计算机（RISC） 。 3.32 什么是虚拟机？引入“虚拟机”这一概念有何意义？ 什么是虚拟机？引入“虚拟机”这一概念有何意义？ 解：虚拟机（Virtual Machine，也被译为如真机）是一个抽象的计算机，它由软件实现，并与实际机器一样，都具有一个指令集并可以 使用不同的存储区域。 引入虚拟机的概念，就计算机语言而言，有以下意义和作用： （1）有助于我们正确理解各种语言的实质和实现途径 微指令、机器指令、作业控制语言主要是为支撑更高层次虚拟机所必需的解释程序和翻译程序而设计的，它们是更高层次虚拟机设 计与实现的基础。汇编语言、高级语言、应用语言主要是为应用程序员设计的，它们需通过翻译变成低级语言，或由低级语言解释来执行。 为了对上一层次语言进行较为方便的翻译和解释，相邻层次语言的语义差距不能太大。虚拟机的引入，有助于我们正确理解各种语言的实 质和实现途径，从而更好地进行语言的研究和应用。 （2）推动了计算机体系结构以及计算机语言的发展 虚拟机的引入使计算机体系结构得到了极大的发展，由于各层次虚拟机均可以识别相应层次的计算机语言，从而摆脱了这些语言必 须在同一台实际机器上执行的状况，为多处理计算机系统、分布式处理系统以及计算机网络、并行计算机系统等新的计算机体系结构的出 现奠定了基础。 （3）有助于各层次计算机语言自身的完善 虚拟机的层次之分，有助于各层次计算机语言相对独立地发展，使研制者可以将注意力主要放在本层次语言上，使之不断地得到完 善和发展。各种语言的不同升级版本就是这种不断完善的产物。 3.33 如何用虚拟机的观点来划分计算机的层次结构？ 如何用虚拟机的观点来划分计算机的层次结构？ 解：从语言的角度给出计算机系统的层次结构图（如图所示） 。 应用语言虚拟机（第五层） 1．该层次的机器语言为：应用语言 2．用应用语言编写的应用语言程序经应用程序包翻译成高级语言 ↓ 高级语言虚拟机（第四层） 1．该层次的机器语言为：高级语言或专用代码（如 Java 虚拟机中的字节码） 162．高级语言程序经编译程序翻译成汇编语言（或某种中间语言程序，或机器语言程序） ↓ 汇编语言虚拟机（第三层） 1．该层次的机器语言为：汇编语言 2．汇编语言程序经汇编程序翻译成机器语言程序 ↓ 操作系统虚拟机（第二层） 1．该层次的机器语言为：作业控制语言 2．由机器语言程序解释操作系统命令 ↓ 固件虚拟机（第一层） 1．该层次的机器语言为：机器指令 2．用微指令程序解释机器指令 ↓ 实际机器（第 0 层） 1．该层次的机器语言为：微指令 2．由硬件直接执行 计算机系统的层次结构图 3.34 为什么说自然语言的“创造性”过程的本质与计算过程的本质是一致的？ 为什么说自然语言的“创造性”过程的本质与计算过程的本质是一致的？ 解：乔姆斯基把人所具有的创造和理解正确句子的能力称为语言的“创造性” （Creativity） 。而语言“创造性”过程的本质，其实 就是由有限数量的词根据一定的规则产生正确句子的过程，进一步而言，其实质也就是一个字符串到另一个字符串的变换过程。显然，语 言“创造性”过程的本质与计算过程的本质是一致的，因此，可以将自然语言也看作是一种计算，从而自然语言能否实现形式化的争论也 就不存在了。 3.35 自然语言的计算机处理分为哪 4 个层次？ 自然语言的计算机处理分为哪 个层次？ 解：自然语言的计算机处理可以分为以下四个层次： （1）第一层次是文字和语音，即基本语言信息的构成； （2）第二层次是语法，即语言的形态结构； （3）第三层次是语义，即语言与它所指的对象之间的关系； （4）第四层次是语用，即语言与它的使用者之间的关系。 3.36 根据本章给出的自然语言形式化例子中的转换规则，给出句子“他教我学英语”的派生过程。 根据本章给出的自然语言形式化例子中的转换规则，给出句子“他教我学英语”的派生过程。 解： S NP VP N V N V N V N V N V 我 V 我 教 我 教 我 教 我 教 S NP VP N N N N N 他 他 他 VP V V V V V 学 学 NP N N N N N 汉语 根据 S-&NP VP 根据 VP-&VS 根据 S-&NP VP 根据 NP-&N 根据 VP-&V NP 根据 NP-&N 根据 N-&我 根据 V-&教 根据 N-&他 根据 V-&学 根据 N-&汉语17习题四4.1 什么是算法？算法有何特征？ 什么是算法？算法有何特征？ 解：一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型问题的运算序列。 算法的形式化定义：算法是一个四元组，即（Q，I，Ω，F） 。 其中： （1）Q 是一个包含子集 I 和Ω的集合，它表示计算的状态； （2）I 表示计算的输入集合； （3）Ω表示计算的输出集合； （4）F 表示计算的规则，它是一个由 Q 到它自身的函数，且具有自反性，即对于任何一个元素 q∈Q，有 F(q)=q。 算法的重要特性： （1）有穷性：一个算法在执行有穷步之后必须结束。也就是说，一个算法，它所包含的计算步骤是有限的。 （2）确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。 （3）输入：算法有零个或多个的输入，即在算法开始之前，对算法最初给出的量。 （4）输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。 （5）能行性：算法中有待执行的运算和操作必须是相当基本的，换言之，它们都是能够精确地进行的，算法执行者甚至不需要掌握 算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。 4.2 表示算法的语言有哪几种？ 表示算法的语言有哪几种？ 解：表示算法的语言主要有自然语言、流程图、伪代码、计算机程序设计语言等。 4.3 判定方程 3x+5y=2 是否有整数解。 (1) 3 除 5 余数为 2； (2) 2 除 3 余数为 1； (3) 1 除 2 余数为 0，算法结束，输出结果 1。 3 和 5 的最大公因子是 1，1 能整除 2，故该方程有整数解。 4.4 用欧几里德算法分别求下列自然数的最大公因子： 注意步骤） 用欧几里德算法分别求下列自然数的最大公因子： 注意步骤） （ （1）18，12 （2）21，9 （3）83，19 （4）201，81 （5）216，78 解： （1）18，12 (a) 12 除 18 余数为 6； (b) 6 除 12 余数为 0,算法结束，输出结果 6。 (2) 21,9 (a) 9 除 21 余数为 3； (b) 3 除 9 余数为 0,算法结束，输出结果 3。 (3) 83,19 (a) 19 除 83 余数为 7； (b) 7 除 19 余数为 5; (c) 5 除 7 余数为 2; (d) 2 除 5 余数为 1; (e) 1 除 2 余数为 0;算法结束，输出结果 1。 (4) 201,81 (a) 81 除 201 余数为 39； (b) 39 除 81 余数为 3; (c) 3 除 39 余数为 0.算法结束，输出结果 3。 (5) 216,78 (a) 78 除 216 余数为 60； (b) 60 除 78 余数为 18; 18 解：首先使用欧几里德算法求出系数 3 和 5 的最大公因子:(c) 18 除 60 余数为 6; (d) 6 除 18 余数为 0.算法结束，输出结果 6。 4.5 解： 自然语言描述算法如下： （1）将 1 赋值给 x； （2）将 1 赋值给 i； （3）将 1 赋给 total； （4）将 total 与 1/x 相加，然后把结果存入 total； （5）将 i+1，然后把结果存入 i； （6）将 x 与 i 相乘，然后把结果存入 x； （7）若 i 大于等于 N，算法结束，结果为 total；否则转到步骤（4）继续执行。 流程图： 设e= 1+1 1 1 1 + + + + L ，请分别用自然语言、流程图和伪代码写出求解 e 的近似值的算法。 1! 2! 3! 4!开始x=1 i=1 total=1 total=total+1/x i =i+1 x =x*iNI&=N结束4.6 根据例子 4.4、4.5、4.6 的流程图，分析它们所包含的基本结构（顺序、选择和循环） 、 、 的流程图，分析它们所包含的基本结构（顺序、选择和循环） 。 解：例子 4.4 包含的基本结构是顺序结构和循环结构。 例子 4.5 包含的基本结构是顺序结构和循环结构。 例子 4.6 包含的基本结构是选择结构和循环结构。 4.7* 分别用自然语言、流程图和伪代码写出“找零钱”问题的贪婪算法（提示：可以使用结构体的数据类型） 分别用自然语言、流程图和伪代码写出“找零钱”问题的贪婪算法（提示：可以使用结构体的数据类型） 。 4.8 就“兔子问题”而言，请问一对兔子 14 个月内可繁殖成多少对兔子？ 个月内可繁殖成多少对兔子？ 兔子问题”而言， 解： 月份 0 1 2 3 4 5 6 7 8 9 10 11 12 13 19 14兔子 01 12 35 81321345589 144233377一对兔子 14 个月内可繁殖成 377 对兔子。 4.9* 随着 N 的增大，斐波那契数列的第 N 项和第 N＋1 项的比值 将越来越接近一个著名的数值 0.618…，即黄金分割数，该数具有 的增大， ＋ 项的比值,将越来越接近一个著名的数值 … 即黄金分割数， 极大的美学价值，试述黄金分割数与大学生（特别是理工科学生）审美能力的培养。 极大的美学价值，试述黄金分割数与大学生（特别是理工科学生）审美能力的培养。 4.10 在算法分析中，一般要考虑哪几个问题？ 在算法分析中，一般要考虑哪几个问题？ 解：在算法的分析中，一般应考虑以下 3 个问题： （1）算法的时间复杂度； （2）算法的空间复杂度； （3）算法是否便于阅读、修改和测试。 4.11 什么是数据结构？数据结构的基本运算内容是什么？ 什么是数据结构？数据结构的基本运算内容是什么？ 解：数据结构是一类定性的数学模型，它由数据的逻辑结构、数据的存储结构（或称物理结构）及其运算 3 部分组成。 数据结构的基本运算内容包括： （1）建立数据结构； （2）清除数据结构； （3）插入数据元素； （4）删除数据元素； （5）更新数据元素； （6）查找数据元素； （7）按序重新排列； （8）判定某个数据结构是否为空，或是否已达到最大允许的容量； （9）统计数据元素的个数。 4.12 常用的数据结构有哪几种？ 解：常用的数据结构有线性表、数组、树和二叉树以及图等。 4.13 什么是程序？程序包括哪些基本要素？ 什么是程序？程序包括哪些基本要素？ 解： “程序”一词，从广义上讲可以认为是一种行动方案或工作步骤。计算机的程序，也是一种处理事务的时间顺序和处理步骤。由 于组成计算机程序的基本单位是指令，因此，计算机程序就是按照工作步骤事先编排好的、具有特殊功能的指令序列。 一个程序具有一个单一的、 不可分的结构， 它规定了某个数据结构上的一个算法。 瑞士著名计算机科学家尼可莱? （Nikiklaus Wirth） 沃思 在 1976 年曾提出这样一个公式： 算法+数据结构=程序 由此看来，我们前面提到的算法和数据结构是计算机程序的两个最基本的概念。算法是程序的核心，它在程序编制、软件开发，乃 至在整个计算机科学中都占据重要地位。数据结构是加工的对象，一个程序要进行计算或处理总是以某些数据为对象的，而要设计一个好 的程序就需将这些松散的数据按某种要求组成一种数据结构。然而，随着计算机科学的发展，人们现在已经意识到程序除了以上两个主要 要素外，还应包括程序的设计方法以及相应的语言工具和计算环境等内容。 4.14 什么是软件？什么是硬件？ 什么是软件？什么是硬件？ 解：现在计算机软件一般指计算机系统中的程序及其文档，也可以指在研究、开发、维护，以及使用上述含义下的软件所涉及的理 论、方法、技术所构成的分支学科。软件一般分为系统软件、支撑软件、应用软件 3 类。 计算机硬件是构成计算机系统的所有物理器件、部件、设备，以及相应的工作原理与设计、制造、检测等技术的总称。广义的硬件 包含硬件本身及其工程技术两部分。 4.15 将下列十进制数分别写成二进制、八进制、十六进制数的形式（注意步骤） 将下列十进制数分别写成二进制、八进制、十六进制数的形式（注意步骤） 25；98；124；12；42；32；16；56 126 转换成二进制、八进制、十六进制，二进制要求为八位。2021262632取余数 余数K0 =0 余数K1 =1 余数K2 =1 2 7 余数K3 =1 余数K4 =1 2 3 1 余数K5 =1 2 0 余数K6 =1(低位)31 2 15(高位)（126）10 = （ 每三位为一组，获得八进制（176）8 每四位为一组，获得十六进制（7E）16 解 (25)10＝(=(31)8=(19)16 (98) 10＝(=(142)8=(62)16 (124) 10＝(=(374)8=(7C)16 (12) 10＝(=(14)8=(0C)16 (42) 10＝(=(52)8=(2A)16 (32) 10＝(=(40)8=(20)16 (16) 10＝(=(20)8=(10)16 (56) 10＝(=(70)8=(38)16 4.16 将下面二进制的数转化为八进制数 ； =(50)8 (=(215)8 (=(235)8 () 2=(667)8(=(432)8 (=(345)84.17 将下列八进制数转化为二进制数 23；74；1；； 解： (23)8=( (221)8=( ()2 (74)8=( ()2 ()2 (1)2 (654)8=(4.18 将下列八进制数转化为十六进制数 23；210；；；2005 解： (23)8=(=(13)16 (210)8=(=(88)16 21()2=(248)16 ()2=(461)16 (42)8=(=(22)16 5；-3； 20；31；-16；0；()2=(F2C)16 (41)8=(=(21)16 ()2=(405)16 -17；-14.19 写出下列十进制数表示的数的 8 位二进制原码、反码和补码的形式（注意步骤） 位二进制原码、反码和补码的形式（注意步骤） 例如：-3：原码：（按照 4.15 步骤） 对负数而言，原码与反码的互换，只需“除符号位不变外，按位求反”。 因此，反码为：。 原码与补码的互换，只需“除符号位不变外，按位求反再加 1”。 因此，补码为： 解：[5]原= [-16]原=]反= [-16]反=]补= [-16]补= [-3]原=]原= [-3]反=]反= [-3]补=]补=]原=]原=]反=]反=]补=]补=]原= [-1]原=]反= [-1]反=]补= [-1]补=4.20 写出下列补码表示的二进制数的真值： 写出下列补码表示的二进制数的真值： 111；101110 最高位 0 为符号位，正数。 1101110 = 0*20+1*21+1*22+1*23+0*24+1*25+1*26 = 110 因此，对应的真值是：110 2： 最高位 1 代表符号位，负数。为了便于计算，负数的补码转换成十进制前先转换成原码。 原码与补码的互换，只需“除符号位不变外，按位求反再加 1” 原码为：0110 = = 0*20+1*21+1*22+0*23+0*24+1*25+1*26 =102 因此，对应的真值是：-102 4.21 写出下列符号的 ASCII 码： A； （； d.；* ；z ；= ； g.；17 解： 符号 ASCII 码 符号 ASCII 码 A
* z = g 17 01114.22根据“计”的点阵图写出它的字型码。 根据“ 的点阵图写出它的字型码。22解： 00 00 00 00 00
为什么？ 为什么？ 解：这样的说法正确。像素越多，能够显示的点越多，而每个点都占用一定的内存空间（如 24 位彩色或者 2 位黑白） ，因此点越多， 占用的内存也越多。当然，影响图像显示的因素还有很多，例如显示器本身的性能。 4.24 假如用位图技术存储一幅分辨率为
的彩色图片，它需要多大的存储空间。 × 的彩色图片，它需要多大的存储空间。 位图技术和矢量技术相比，各自的优点是什么？ 位图技术和矢量技术相比，各自的优点是什么？ 术相比 解：用位图技术存储一张
的图片就需要 3 兆字节的存储空间。 4.25 解：矢量技术不需要存储每一个像素量化的值，所以存储空间大大减小。但是由于矢量技术是用指令来描述图像的，如果涉及的图 像十分复杂，那么指令数目将会很大，调用函数的次数也随之增大，因此对于复杂的图像，矢量技术比位图耗时要大。 4.26 的音乐， 位来表示，它需要多大的存储空间？ 假设立体声系统记录了 1h 的音乐，采样频率 44100Hz，如果每次采样所得到的幅值用 32 位来表示，它需要多大的存储空间？ ， 解： 假设立体声系统记录了 1h 的音乐， 采样频率 44100Hz， 如果每次采样所得到的幅值用 32 位来表示， 它需要 600 多兆的存储空间。 *32/8 =
字节= 606 M 4.27 为什么在分析计算机内部工作时，常用 16 进制数。 解：计算机中的数据是以二进制数表示的，二进制数的每 1 位只能为 0 或 1，而人要处理一长串的 0 和 1 是非常乏味且容易出错的。 而采用十六进制可以有效的帮助我们，借助这种方法，一个 16 位的二进制数 11 1001 可以用更简单的十六进制数 4A39 来表 示。所以在分析计算机内部工作时，常用 16 进制数。 4.28 解： CC1991 报告提取了学科中的核心概念： 1．绑定（Binding） 2．大问题的复杂性（Complexity of Large Problems） 23 CC1991 报告提取了哪些核心概念？报告认为掌握这些核心概念是什么人的标志之一。 报告提取了哪些核心概念？报告认为掌握这些核心概念是什么人的标志之一 概念是什么人的标志之一。 一幅位图中，用来表示一个图像所使用的像素的数量同时影响了图像显示的清晰图和它所需的内存大小。这样的说法正确吗， 一幅位图中，用来表示一个图像所使用的像素的数量同时影响了图像显示的清晰图和它所需的内存大小。这样的说法正确吗，3．概念模型和形式模型（Conceptual and Format Models） 4．一致性和完备性（Consistency and Completeness） 5．效率（Efficiency） 6．演化（Evolution） 7．抽象层次（Levels of Abstraction） 8．按空间排序（Ordering in Space） 9．按时间排序（Ordering in Time） 10．重用（Reuse） 11．安全性（Security） 12．折衷和结论（Tradeoff and Consequences） 报告认为，熟练掌握和应用这些核心概念是一个成熟的计算机科学家和工程师的标志之一。 4.29* 在研究数字逻辑电路时，为什么计算机科学家和工作师关心的是机器电路所完成的逻辑功能，而不是电的或机械的性能。习题五5.1 在计算学科中，采用的数学方法，主要是离散数学的方法还是连续数学的方法，为什么？ 在计算学科中，采用的数学方法，主要是离散数学的方法还是连续数学的方法，为什么？ 解：在计算学科中，采用的数学方法，主要是离散数学的方法。 因为计算学科的根本问题是“能行性”问题。 “能行性”这个根本问题决定了计算机本身的结构和它处理的对象都是离散型的，而连 续型的问题只有经过“离散化”的处理后才能被计算机处理。因此，在计算学科中，采用的数学方法，主要是离散数学的方法。 5.2 在对待数学的问题上，计算机科学家与数学家各自的侧重点是什么？ 在对待数学的问题上，计算机科学家与数学家各自的侧重点是什么？ 解：在对待数学的问题上，计算机科学家与数学家的侧重点不一样：数学家关心的是“是什么（What is it） ”的问题，重点放在数 学本身的性质上；计算机科学家则不同，他们不仅要知道“是什么”的问题，更要解决“怎么做（How to do it） ”的问题。 5.3 数学有哪些基本特征？ 数学有哪些基本特征？ 解：数学具有以下 3 个基本特征： 1. 高度的抽象性。数学的抽象程度大大超过自然科学中一般的抽象，它最大的特点在于抛开现实事物的物理、化学和生物学等特性， 而仅保留其量的关系和空间的形式。 2．逻辑的严密性。数学高度的抽象性和逻辑的严密性是紧密相关的。若数学没有逻辑的严密性，在自身理论中矛盾重重，漏洞百出， 那么用数学方法对现实世界进行抽象就失去了意义。正是由于数学的逻辑严密性，我们在运用数学工具解决问题时，只有严格遵守形式逻 辑的基本法则，充分保证逻辑的可靠性，才能保证结论的正确性。 3．普遍的适用性。数学的高度抽象性决定了它的普遍适用性。数学广泛地应用于其他科学与技术，甚至人们的日常生活之中。 5.4 数学方法有什么作用？ 数学方法有什么作用？ 解：数学方法在科学技术方法论中的作用主要表现在以下 3 个方面： 1．为科学技术研究提供简洁精确的形式化语言。对于微观和宏观世界中存在的复杂的自然规律，只有借助于数学的形式化语言才能 抽象地表达。 2．为科学技术研究提供数量分析和计算的方法。一门科学要从定性分析发展到定量分析，数学方法从中起了杠杆的作用。计算机的 问世更为科学的定量分析和理论计算提供了必要条件，使一些过去无法解决的数学课题找到了解决的可能性。 3．为科学技术研究提供逻辑推理的工具。数学的逻辑严密性这一特点使它成为建立一种理论体系的手段，在这方面最有意义的就是 公理化方法。数学逻辑用数学方法研究推理过程，把逻辑推理形式加以公理化、符号化，为建立和发展科学的理论体系提供有效的工具。 5.5 什么叫集合？集合的基本运算有哪几种？ 什么叫集合？集合的基本运算有哪几种？ 解：集合是数学的基本概念，它是构造性数学方法的基础。集合就是一组无重复的对象的全体。集合中的对象称为集合的元素。 集合的基本运算有并、差、交、补和乘积等运算。 5.6 什么是函数？ 什么是函数？ 解：函数又称映射，是指把输入转变成输出的运算，该运算也可理解为从某一“定义域”的对象到某一“值域”的对象的映射。 5.7 什么是关系？等价关系要满足哪些条件？ 什么是关系？等价关系要满足哪些条件？ 解：关系是一个谓词，其定义域为 k 元组的集合。通常的关系为二元关系，其定义域为有序对的集合，在这个集合中，我们说有序 对的第一个元素和第二个元素有关系。 等价关系要满足以下 3 个条件： （1）自反性，即对集合中的每一个元素 a，都有 aRa； 24（2）对称性，即对集合中的任意元素 a，b，aRb 成立当且仅当 bRa 成立； （3）传递性，即对集合中的任意元素 a，b，c，若 aRb 和 bRc 成立，则 aRc 一定成立。 5.8 血缘关系是不是等价关系？ 血缘关系是不是等价关系？ 解：血缘关系不是等价关系。不满足传递性。 5.9 一般来说，若能分别给出满足某个概念正反两个方面的 3 个例子，我们就说，这个概念被真正的掌握了。等价关系是学科中一 一般来说， 个例子，我们就说，这个概念被真正的掌握了。 个非常重要的概念，是我们对现实世界进行“划分” 并降低问题复杂性的一个强有力工具， ， 个非常重要的概念，是我们对现实世界进行“划分” 并降低问题复杂性的一个强有力工具，请分别给出 3 个满足等价关系和 3 个不满足 等价关系的例子。 等价关系的例子。 解：满足等价关系的 3 个例子：自然数域中的等于关系；整数域中的模 3 同余关系；同姓关系。 不满足等价关系的 3 个例子：父子关系；同学关系；朋友关系。 5.10 并发关系是否是等价关系?试举例说明。 并发关系是否是等价关系 试举例说明。 试举例说明 解：并发关系不是等价关系。比如说进程 1 与进程 2 可以并发，进程 1 与进程 3 可以并发，但进程 2 与进程 3 不可以并发的时候， 并发关系就不是等价关系。 什么是代数系统？ 什么是代数系统？ 解：由集合 A 以及连同若干定义在该集合上的运算 f1，f2，…fn 所组成的系统称为代数系统，该系统可以形式化的描述为：&A，f1， f2，…，fn&。 5.11 5.12 简述二元运算的性质。 简述二元运算的性质。 解：二元运算的性质有： （1）封闭性。设*是定义在集合 A 上的二元运算，若对于任意的 x，y A，都有 x*y A，则称二元运算*在 A 上是封闭的。 （2）可交换性。设*是定义在集合 A 上的二元运算，若对于任意的 x，y A ，都有 x*y=y*x，则称该二元运算*是可交换的。 （3）可结合性。设*是定义在集合 A 上的二元运算， 若对于任意的 x，y，z A， 都有（x*y）*c=x*（y*z） ，则称该二元运算*是可结 合的。 （4）可分配性。设*， 是定义在集合 A 上的两个二元运算，若对于任意的 x，y，z，都有 x*（y z）=（x*y） （x*z）且（x y）*z=（x*z） （y*z） ，则称运算*对于运算 是可分配的。 （5）幺元。设*是集合 A 上的一个二元运算，若存在一个元素 el A，对于任意的元素 a A，都有 el*a=a，称 el 是 A 上关于运算*的左 幺元；若存在一个元素 er A 使得对于所有的 a*er=a，称 er 是 A 上关于运算*的右幺元；若存在元素 e A，它既是左幺元，又是右幺元，称 e 为幺元。这时对于任意的 a A 有 e*a=a*e=a。 （6）零元。设*是集合 A 上的二元运算，若存在一个元素 l A，使得对于所有的 a A，有 l*a= l，称 l 是 A 上关于运算*的左零元； 若存在一个元素 r A，使得对于所有的 a A，有 a* r = r，称 r 是 A 上关于运算*的右零元。若存在元素 A，它既是左零元，又是右零元， 则称 为零元。这时对于所有的 a A，有 *a=a* = 。 -1 -1 -1 （7）逆元。设*是集合 A 上的具有单位元 e 的二元运算，对于元素 a A，若存在元素 al A，使得 al *a=e，称元素 al 对于运算*是左 -1 -1 -1 -1 -1 可逆的，而 al 称为 a 的左逆元；若存在元素 ar A，使得 a*ar =e，称元素 ar 对于运算*是右可逆的，而 ar 称为 a 的右逆元。 5.13 什么是群？什么是环？ 什么是群？什么是环？ 解：设&G，*&是一个代数系统，其中 G 是非空集合，*是 G 上一个二元运算，若 （1）运算*是封闭的； （2）运算*是可结合的； （3）存在幺元 e； -1 （4）对于任一个元素 x G，存在它的逆元 x ； 则称&G,*&是一个群。 设&G，*，-&是一个代数系统，其中 G 是非空集合，*和-是 G 上的二元运算，若 （1）&G，*&是阿贝尔群； （2）&G，-&是半群； （3）运算-对于运算*是可分配的。 则称&G,*，-&是一个环。 5.14 什么是格？什么是布尔代数？ 什么是格？什么是布尔代数？ 解：设&A, &是一个偏序集，若 A 中任意两个元素都有最小上界和最小下界，则称&A, &为格。 5.15 为什么说，可以将一个具体的数字逻辑转换成抽象的代数表达式而加以分析和研究。 为什么说，可以将一个具体的数字逻辑转换成抽象的代数表达式而加以分析和研究。 解：研究数字逻辑电路，我们所关心的是电路所完成的逻辑功能，而不是电的或机械的性能。因此，一般只考虑输入变量和输出变量 之间的逻辑关系，并用数学的方式来描述。若输入为布尔变量 A，B，C，……，输出则为布尔函数 F，F=f(A，B，C，……)。 这种代数表达式是以理想的形式来表示实际的数字逻辑电路，反映了逻辑电路的特征和功能。因此，可以将一个具体的数字逻辑转 换成抽象的代数表达式而加以分析和研究。 5.16 为什么说，若能构造实现加法运算的机器，就一定可以构造出能实现其他运算的机器。 为什么说，若能构造实现加法运算的机器，就一定可以构造出能实现其他运算的机器。 解：数字计算机的运算，建立在算术四则运算的基础上。在四则运算中，加法是最基本的一种运算。若想建造一台计算机，那么， 首先必须知道如何构造一台能进行加法运算的机器。由于减法、乘法、除法，甚至乘方、开方等运算都可以用加法导出。因此，若能构造 25实现加法运算的机器，就一定可以构造出能实现其他运算的机器。 5.17 什么是字符串？什么是语言？语言、文法与自动机有何关系？ 什么是字符串？什么是语言？语言、文法与自动机有何关系？解：字符串，也称为符号串，指的是由字符组成的有限序列，常用小写希腊字母表示。字母表∑上的字符串以下列方式生成： （1）ε 为∑上的一个特殊串，称为空串，对任何 a∈∑，aε=εa = a； （2）若 σ 是∑上的符号串，且 a∈∑，则 σa 是∑上的符号串； （3）若 α 是∑上的符号串，当且仅当它由（1）和（2）导出。 语言指的是给定字母表∑上的字符串的集合。 语言、文法以及自动机有着密切的关系。语言由文法产生，第三章介绍过，文法是一种数学模型，它是建立在有限集合上的一组变 换（运算） 。因此，根据代数系统的定义，也可以将文法看作是一种代数系统，而语言正是由这种代数系统产生的。 5.18 什么是定义，其作用和规则是什么？ 什么是定义，其作用和规则是什么？ 解：定义是对一种事物的本质特征或一个概念的内涵与外延确切而简要的说明。 定义的作用： （1）综合作用：人们可以通过定义，对事物已有的认识进行总结，用文字的形式固定下来，并成为人们进行新的认识和实践活动的 基础； （2）分析作用：人们可以通过定义，分析某个语词、概念、命题的使用是否适合，是否存在逻辑方面的错误； （3）交流作用：人们可以通过定义，在理性的交谈、对话、写作、阅读中，对于所使用的语词、概念、命题有一个共同的理解，从 而避免因误解、误读而产生的无谓争论，提高成功交际的可能性。 定义的规则： （1）定义必须揭示被定义对象的区别性特征； （2）定义项和被定义项的外延必须相等； （3）定义不能恶性循环； （4）定义不可用含混、隐晦或比喻性词语来表示。 5.19* 查资料，分别给出并分析违反定义规则的 3 个实例。 查资料， 个实例。 5.20 分别给出抽象，科学和人的定义。 分别给出抽象，科学和人的定义。 解：抽象：在常用词典中，抽象一般有两个解释。一个是，从许多事物中，舍弃个别的、非本质的属性，抽出共同的、本质的属性， 叫抽象；另一个是，不能具体的，笼统的，空洞的，叫抽象。 科学：科学是反映自然、社会、思维等的客观规律的分科的知识体系。 人：人是能制造工具并使用工具进行劳动的高等动物。 5.21 用文氏图画一个至少有 6 种哺乳动物 含人和老虎） 的集合， 并从充分条件和必要条件两个方面判定人与哺乳动物之间的关系。 （含人和老虎） 的集合， 并从充分条件和必要条件两个方面判定人与哺乳动物之间的关系。 解： 哺乳动物 猫 人 猴子 狼 狗 老 虎人是哺乳动物。这一命题中， “人”是哺乳动物的充分条件， “哺乳动物”是人的必要条件。 5.22 判定下列句子，那些句子涉及必要条件，充分条件？或充分必要条件，或既不是充分条件也不是必要条件？ 判定下列句子，那些句子涉及必要条件，充分条件？或充分必要条件，或既不是充分条件也不是必要条件？ （1） 欧拉对任一连通无向图是否存在“欧拉回路”的判定； （2） 兼容并包； （3） 新上项目的讨论； （4） 让爱包容； （5） 外语水平是优秀人才的什么条件； （6） 良好的品德是成为学术大师的什么条件； （7） 海纳百川； ； （8） 不苟一格降人才（或者说，业绩是隐含在其中的什么条件？） （9） 宽以待人； 26（10）有容乃大； （11）抓大放小； （12）宽容； (13) 伟大的人格是成为伟大科学家的什么条件； （14）俗话说的大气； （15）博士学位是获得诺贝尔奖的什么条件； （16）掌握布尔代数的基础知识是完成数字逻辑电路设计的什么条件？ （17）* 数据库中并发控制的可串行化调度。 解： （1） 欧拉对任一连通无向图是否存在“欧拉回路”的判定； （充要条件） （2） 兼容并包； （必要条件） （3） 新上项目的讨论； （充分条件） （4） 让爱包容； （必要条件） （5） 外语水平是优秀人才的什么条件； （既无充分，也无必要） （6） 良好的品德是成为学术大师的什么条件； （既无充分，也无必要） （7） 海纳百川； （必要条件） （8） 不苟一格降人才（或者说，业绩是隐含在其中的什么条件？）（必要条件） ； （9） 宽以待人； （必要条件） （10）有容乃大； （必要条件） （11）抓大放小； （必要条件） （12）宽容； （必要条件） (13) 伟大的人格是成为伟大科学家的什么条件； （既无充分，也无必要） （14）俗话说的大气； （必要条件） （15）博士学位是获得诺贝尔奖的什么条件； （既无充分，也无必要） （16）掌握布尔代数的基础知识是完成数字逻辑电路设计的什么条件？（必要条件） （17）* 数据库中并发控制的可串行化调度。 （充分条件） 5.23 为什么说，必要条件，就是一种决不能少的条件，也就是一种找不到一个反例的条件？ 为什么说，必要条件，就是一种决不能少的条件，也就是一种找不到一个反例的条件 5.24* 试结合实例，用魔术的最根本理论 “人不能同时注意两件事” 惟一公理） 论述为什么约束条件多了（条件越充分） 少数必 试结合实例， 人不能同时注意两件事” 惟一公理） 论述为什么约束条件多了（条件越充分） ，论述为什么约束条件多了 ，少数必 （ ， ， 要的条件就越容易被忽视。 要的条件就越容易被忽视。 5.25* 从条件的充分性和必要性入手，分析当前激烈争论的一个社会问题。 从条件的充分性和必要性入手，分析当前激烈争论的一个社会问题。 5.26 数学方法中有哪几种主要的证明方法？ 数学方法中有哪几种主要的证明方法？ 解：数学方法中主要的证明方法有直接证明、间接证明、反证法、归纳法和构造性证明方法。 5.27 解： BEGIN（算法开始） if n = =0 { 0=&F0 Print F0 } else if n==1 { 0=&F0 1=&F1 Print F0，F1 } Else { Fn-2+Fn-1=&Fn Print Fn } END（算法结束） 27 请用伪代码给出求解斐波那契数的递归算法。 请用伪代码给出求解斐波那契数的递归算法。5.28求下列阿克曼函数值：（1）A(0,1) （2）A(1,0) （3）A(1,1) （4）A(2,1) （5）A(2,2) 解： (1) A(0,1)= 1+1=2 (2) A(1,0)= A((1-1),1)= A(0,1)=2 (3) A(1,1)= A(0, A(1,0) = A(0, A(0,1))= A(0, 2)= 3 (4) A(2,1)= A(1, A(2,0))= A(1, A(1,1))= A(1,3)= A(0, A(1,2)) =A(0, A(0, A(1,1))) = A(0, A(0, 3))= A(0,4)= 5 （5）A(2,2) = A(1, A(2,1))= A(1, 5)= A(0, A(1, 4))= A(0, A(0, A(1, 3))) = A(0, A(0, 5))= A(0, 6)=7 5.29 什么是递归和迭代？二者有何联系？ 什么是递归和迭代？二者有何联系？ 解：递归就是在过程或函数里调用自身。 递归：指直接或间接地调用自身 迭代：是反复替换的意思 迭代与递归有着密切的联系，甚至，一类如 X0=a，Xn+1=f(n)的递归关系}