计算机科学导论——基于计算思维的思想与方法（第4版）-参考答案 ch07.docx

第七章 问题求解的算法基础 选择题 1-5ABCDA 6-10BCDAB 问答题 1.什么是算法? 算法(Algorithm)是一种求解问题的思维方式，是对事物本质的数学抽象。具体说，算法是由基本运算规则和运算顺序构成的、完整的解题方法和步骤，是程序设计的核心。 2.算法有哪些特征? (1)确定性(Certainty) (2)有效性(Effectiveness) (3)有穷性(Finiteness) (4)有零个或多个输入(Input) (5)有一个或多个输出(Output) 3.算法的复杂性是指什么? 1.时间复杂度(TimeComplexity) 算法的时间复杂度是指度量时间的复杂性，即算法的时间效率的指标。换言之，时间复杂度是与求解问题的规模、算法输入数据相关的函数，该函数表示算法运行所花费的时间。 2.空间复杂度(SpaceComplexity) 算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。 4.在问题求解过程中，算法的描述方法由哪几种? 算法是对解题过程的精确描述，描述算法的方法很多，常用的描述方法有自然语言、图形描述(流程图、N-S结构图、PAD结构图)、伪代码、程序设计语言等。 5.穷举算法的基本思想是什么? (1)确定范围：按照问题要求确定问题解的大致范围一一列举，遍历所有可能的组合值。. (2)条件约束：判断题解是否符合正解条件，避免解题结果错误。 (3)循环运算：使可能解的范围降至最小，以便提高解题效益。 6.迭代算法的基本思想是什么? 所谓迭代，就是为了逼近所需目标或结果而重复反馈，每次迭代的结果作为下次迭代的初始值。迭代与递推的区别源于问题的性质，在实际问题中可能遇到以下两种情况。. (1)可以表示成数学上明确的递推公式。 (2)无法直接写出显式递推公式：只能通过“迭代”，并且可分为精确迭代和近似迭代。 7.递归算法的基本思想是什么? 递归是一种强有力的数学工具，它可使问题的描述和求解变得简洁和清晰，它有两种形式。 (1)直接递归：重复一个或一组操作，如累加、累减、累乘、累除等运算就是直接递归，程序设计中的赋值语句“a=a+1；是累加，把a+1的值赋给a是递归计算，而不是表达式计算。 (2)间接递归：是指从1到n之间所有自然数相乘的结果，阶乘计算就是典型的间接递归，程序用到它自身的前一步或前几步。 8.递归算法和递推算法有何区别? 本质上，递归和递推都是同一种解决问题的思路，都是把问题进行分解，但递推是由小到大的推导，而递归则是由大到小的推导。 9.分治算法的基本思想是什么? 由分治算法产生的子问题往往是原问题的较小模式，最终使子问题缩小到容易直接求解，自然导致递归过程的产生，也为使用递归技术提供了方便。分治算法一般按照以下步骤求解： (1)分解：将要解决的问题划分成若干规模较小的同类问题(子问题)； (2)求解：当待解决的问题划分得足够小后，用简单的方法求得结果； (3)合并：按照原问题的要求，将子问题的解逐层合并构成原问题的整体解。 10.动态规划的基本思想什么? 为了解决某一多阶段决策过程的优化问题，而依次做出n个决策D1，D2，...Dn；如果这个决策序列是最优的，不论前面决策是怎样的，以后的最优决策取决于由前面决策所确定的当前状态。 动态规划一般按照以下步骤求解。 (1)划分：将待求解的问题划分为若干个阶段，即若干互相联系的子问题。 (2)推导：按照自底向上的顺序，推导出原问题的解。 (3)记录：记录子问题的解，避免求解过程中重复多次求解同一子问题，提高算法求解效率。 11.数据结构、数据查找与数据排序有何区别? 对于非数值数据，它不是求问题的数值解，只能采用数据结构的方式来实现对数据的处理；数据查找和排序实际上是对数组中的数据元素进行处理。 谈论题 1.你认为，研究数值数据算法、数据查找与排序、数据结构的意义在哪里? 数据元素操作通常是对数组中的元素进行查找与排序，是介于数值数据处理与非数值数据处理的一种特殊形式，是程序设计中极为重要的内容，具有重要的理论研究价值和实际应用价值。 2.问题求解的算法基础在计算机科学中的作用地位主要体现在哪些方面? 略