计算机科学导论-基于计算思维的思想与方法（第4版）-习题及答案 ch07

第七章问题求解的算法基础选择题1-5ABCDA6-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.你认为，研究数值数据算法、数据查找与排序、数据结构的意义在哪里?数据元素操作通常是对数组中的元素进行查找与排序，是介于数值数据处