太原理工大学软件学院算法设计与分析复习

算法设计与分析复习（2016）

考试题型与范围

1.单选题（10小题，10分）、判断题（10小题，10分）、填空题（15小题，15分）、简答题（5小题，20分）、分析题（1小题，10分）、计算题（4小题，35分）。

2.不含2.4、5.6、6.7、7.4、9.3-6

第1章算法问题求解基础设计与分析基础

1、算法概念、特征，与程序的区别

2、问题、问题求解、问题求解过程（理解问题、设计方案、实现方案、回顾复查）、系统

生命周期（分析、设计、编码、维护）

3、算法问题求解过程（设计、表示、确认、分析）

4、递归、递归算法、递归设计结构、归纳证明

第2章算法分析基础

1、好的算法特性（正确性、简明性、效率、最优性）

2、影响运行时间的因素（3点）

3、算法复杂度、时间复杂度、空间复杂度、最好、最坏和平均时间复杂度

4、渐进表示法：大O记号、Ω记号、θ记号

5、算法按时间复杂度分类：多项式时间算法和指数时间算法

O(1)

O(2n)

6、了解非递归算法的时间复杂性分析。

要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。

非递归算法分析的一般步骤是：

（1）决定用哪个（或哪些）参数作为算法问题规模的度量。

（2）找出算法的基本语句。

（3）检查基本语句的执行次数是否只依赖问题规模。

（4）建立基本语句执行次数的求和表达式。

（5）用渐进符号表示这个求和表达式。

7、递推关系—分析算法复杂度

（1）计算递推式三种方法：替换方法、迭代方法、主方法

（2）掌握扩展递归技术和通用分治递推式的使用。

扩展递归技术：

通用分支递归式：

第5章分治法

1、设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

2、步骤：（1）划分（2）求解子问题（3）合并

3、分治法的代表算法及时间复杂度：

求最大最小元，二分搜索，排序问题（归并排序、快速排序），选择问题，斯特拉森矩阵乘法。

第6章贪心法

1、可行解、最优解、最优量度标准、可行解判断函数

2、设计思想

贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。

3、贪心法的关键在于决定贪心策略。

4、贪心法两个基本要素：最优子结构性质和贪心选择性质

5、贪心法解决的问题（可求最优解）：

背包问题，带时限作业排序问题，最佳合并模式，单源最短路径，最小代价生成树（prim 算法和kruskal算法），磁带最优存储。

第7章动态规划法

1、设计思想：将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。

2、步骤：

（1）刻画最优解的结构特性；

（2）递归定义最优解值；

（3）以自底向上方式计算最优解；

（4）根据计算得到的信息构造一个最优解。

3、两个要素：最优子结构性质和子问题重叠性质

4、动态规划法解决的问题（可求最优解）：多段图问题，每对结点间的最短路径，矩阵连乘，最长公共子序列，最优二叉搜索树，0/1背包问题，流水作业调度。

第8章回溯法

1、设计思想：从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任

一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。

2、显约束、隐约束、解状态、约束函数、剪枝函数等

3、步骤：

（1）针对所给问题，定义问题的解空间；

（2）确定易于搜索的解空间结构；

（3）按深度优先方式搜索解空间，且在搜索过程中利用剪枝函数避免无效搜索。

从所有的可能解中确定最优解。

4、回溯法解决的问题（可求所有解、一个解、最优解）：

属于组合问题和排列问题中求最优解的问题都可以用回溯法解决，例如：八皇后问题（4皇后问题），子集合和数，图着色问题，哈密顿环问题，0/1背包问题，批处理作业调度。

第9章分支限界法

1、设计思想：

1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down,up]，并确定限界函数；

2）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；

3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表PT）中；

4）依次从表PT中选取使限界函数的值是极值的结点成为当前扩展结点；

5）重复上述过程，直到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。

2、步骤：

确定解空间树

确定限界函数

按广度优先搜索解空间树，计算限界函数的值，填入PT表

从PT表中寻找极值，继续扩展结点，直到找到限界函数值为极值的叶子结点。

3、使用分支限界法解决的问题（可求最优解）：

带时限的作业排序、旅行商问题，批处理作业调度问题，0/1背包问题。

算法设计与分析复习资料1

一 1.循环赛日程表问题的相关叙述。 2.算法运行时所需要占用的存储空间有？ 3.动态规划法的求解步骤 4.解空间树是排列树的问题有。 5.分治法的步骤 6.就会场安排问题，贪心法的最佳贪心策略 7.快速排序法基准元素的选取方法 8.满足满m叉树的问题有？ 9.分支限界法的解题步骤 10.事前分析法相关的影响因素有 11.用分治法求解的问题一般需要具备一些特征，主要有？ 二 1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。 2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n 元组。 3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。 4．一个正在生成孩子的结点称为扩展结点。 5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。 6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。 7．一个自身已生成但其孩子还没有全部生成的结点称为活结点 8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间 9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。 10．分支限界法采用的是宽度优先搜索。 11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法 12．一个所有孩子已经生成的结点称做死结点 13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。 三 1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。 2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采

太原理工大学安全系统工程复习资料

1.系统是由相互作用、相互依赖的若干组成部分结合而成的具有特定功能的有机整体。 2.系统的特征：整体性、目的性、有序性、相关性、环境适应性、动态性 3.系统学原理：整体性原理、相关性原理、有序性原理、动态性原理、分解综合原理、创造思维原理、验证性原理、反馈原理 4.系统工程是对系统进行合理规划、研究、设计和运行管理的思想、步骤、组织和技巧等的总称，它是以实现系统最优化为目的的一门基础科学，是一种对所有系统都具有普遍意义的科学方法。 5.三维结构图：①时间维。对一个具体工程，从规划起一直到更新为止，全部程序可分为规划、拟定方案、研制、生产、安装、运转和更新七个阶段。②逻辑维。对一个大型项目可分为明确目的、指标设计、系统方案组合系统分析、最优化、作出决定和制定方案七个步骤。③知识维。系统工程需使用各种专业知识，霍尔把这些知识分成工程、医药、建筑、商业、法律、管理、社会科学和艺术等，把这些专业知识成为知识维。 6.安全与危险：①安全，是指免遭不可接受危险的伤害。它是一种使伤害或损害的风险限制在可以接受的水平的状态。安全程度用安全性指标来衡量。②危险，是指存在引起人身伤亡、设备破坏或降低完成预定功能能力的状态。③安全是相对的，危险是绝对的。 7.安全标准：①安全是一个相对的主观的概念。评定状态是否安全需要一个界限、目标或标准，通过与定量化的风险率或危害程度进行比较，判定是否达到人们所期盼的安全程度。我们把这个标准称为安全标准。②受技术、资金等因素的制约，危险是不可能完全杜绝的。安全标准实际上是一个社会各方面可以接受的危险度③确定安全标准的方法有统计法和风险与收益比较法。 8.安全系统工程是指在系统思想指导下，运用先进的系统工程的理论和方法，对安全及其影响因素进行分析和评价，建立综合集成的安全防控系统并使之持续有效运行。 9.安全系统工程的任务：（1）危险源辨识（2）分析、预测危险源由触发因素作用而引发事故的类型及后果（3）设计和选用安全措施方案，进行安全决策（4）安全措施和对策的实施（5）对措施效果做出总体评价（6）不断改进，以求最佳措施效果，使系统达到最佳安全状态。10.安全系统工程的研究对象：任何一个生产系统地都包括三个部分，即从事生产活动的操作人员和管理人员，生产必需的机器设备、厂房等物质条件，以及生产活动所处的环境。这三个部分构成一个“人—机—环境”系统，每一部分就是该系统的一个子系统，称为人子系统、机器子系统和环境子系统。 11.安全系统工程的研究内容：①系统安全分析系统安全分析有五个基本要素和程序：安全目标、可选用方案、系统模式、评价标准、方案选优②系统安全评价：安全评价的目的是为决策提供依据。系统安全评价往往要以系统安全分析为基础，通过分析，了解和掌握系统存在的危险因素，但不一定要对所有危险因素采取措施。而是通过评价掌握系统的事故风险大小，以此与预定的系统安全指标相比较，如果超出指标，则应对系统的主要危险因素采取控制措施，使其降至该标准以下。③安全决策与控制：任何一项系统安全分析技术或系统安全评价技术，如果没有一种强有力的管理手段和方法，也不会发挥其应有的作用。因此，在出现系统安全分析安全评价技术的同时，也出现了系统安全决策。 12.安全分析应遵循的基本原则：（1）首先可进行初步的综合性分析，再进行详细的分析。（2）根据分析对象的不同，选择相应的分析方法3）如果对新建、改建的设计或限定目标进行分析，可选用静态的分析方法(包括初步分析和详细分析)。如果对运行状态进行分析，则可选用动态的分析方法，如程序分析和逻辑分析等。（4）如果需要对系统进行反复调整，使之达到较高的安全性水平，可以使用替换分析和逻辑分析等。（5）各种分析方法可以互为补充，使用一种方法也许不能完全分析出系统的危险性，但用其他方法可以弥补其不足的部分。（6）进行分析时并不需要使用所有的方法，应该根据实际情况，结合特定的环境和资金条件，使分析能够得出正确的评价。 13.安全检查表的特点：①系统化、科学化，为事故树的绘制和分析，做好准备②容易得出正确的评估结果③充分认识各种影响事故发生的因素的危险程度(或重要程度)④按照原因事件的重要／顺序排列，有问有答，通俗易懂⑤易于分清责任。还可以提出对改进措施的要求，并进行检验⑥符合我国现阶段的实际情况，为安全预测和决策提供坚实的基础⑦只能作定性的评价，不能给出定量评价结果 ⑧只能对已经存在的对象评价 14.预先危险性分析，又称预先危险分析。是在每项工程活动之前，如设计、施工、生产之前，或技术改造后，即制定操作规程和使用新工艺等情况之后，对系统存在的危险性类型、来源、出现条件、导致事故的后果以及有关措施等，做一概略分析。是一种定性分析系统危险因素和危险程度的方法。 15.预先危险性分析的目的：①防止操作人员直接接触对人体有害的原材料、半成品、成品和生产废弃物②防止使用危险性工艺、装置、工具和采用不安全的技术路线③如果必须使用上述技术路线时，应从工艺上或设备上采取安全措施，以保证这些危险因素不致发展成事故。 16.预先危险性分析的一般步骤：确定系统、调查收集资料、系统功能分解、分析识别危险源、确定危险等级、制订措施、措施实施 17.危险性等级的划分：①1级安全的，不会导致伤害或疾病，系统无损失，可以忽略②2级临界的，处于事故的边缘状态，暂时还不会造成人员伤亡和系统的损坏，但应予排除或控制③3级危险的，会造成人员伤亡和系统损坏，要立即采取措施控制④4级破坏性的，破坏性的，会造成死亡或系统报废，必须设法消除 18.危险性控制：①直接措施：（1）限制能量或采用安全能源代替危险能源。如限速装置、低电压设备、安全设备，限制生产能量等（2）防止能量外泄，如自动温度调节器、保险丝、气体检测器、地面装卸作业、锐利工具等（3）防止能量散逸，如放射性物质的铅储器、绝缘材料、安全带等。②间接措施：（1）在能量的放出路线上和放出的时间上采取措施，如排尘装置、安全禁止标志、防护性接地、安全连锁装置等（2）能量放出缓冲装置，如爆炸板、安全阀、保险带、冲击吸收装置等（3）在能量源上采取防护措施，如防护罩、喷水灭火装置、禁入栅栏、防火墙等 （4）在能量和人与物之间设立防护措施，如玻璃视镜、 过滤器、防噪声装置等（5）对人体采取防护措施，如防 尘眼镜、安全靴、头盔、手套、呼吸器、防护用具等（6） 提高耐受能力，选用适应性强的人和耐久性材料（7）降 低损害程度的措施，如紧急冲浴设备、配置低放射线、救 援活动和急救治疗等。 19.故障是指系统或元素在运行过程中，在规定是时间和 条件内不能达到设计规定的要求，因而不能实现预定功能 的状态 20.故障类型及影响分析的步骤：①调查情况收集资料② 危险源初步辨识③故障类型、影响、组成因素分析④故障 危险程度、发生概率、分析⑤检测方法与预防措施⑥按故 障危险程度与概率大小，分先后次序，轻重缓急地逐项采 取预防措施 21.危险性与可操作性研究分析是以关键词为引导，找出 系统中工艺过程的状态参数的变化（即偏差），然后再继 续分析造成偏差的原因、后果及可以采取的对策。 22.鱼刺图法的步骤可以概括为：针对结果，分析原因； 先主后次，层层深入 23.事件树分析法从事件的起始状态出发，用逻辑推理的 方法，设想事故发展过程；进而根据这一过程了解事故发 生的原因和条件。其实质是利用逻辑思维的规律和形式， 从宏观的角度去分析事故形成的过程。 24.事故树分析：又称故障树分析，是从结果到原因找出 与灾害事故有关的各种因素之间因果关系和逻辑关系的 作图分析法。 25.事故树分析的基本程序：（1）熟悉系统（2）调查事故 （3）确定顶上事件（4）确定目标（5）调查原因事件（6） 绘制事故树（7）定性分析（8）计算顶上事件发生概率（9） 分析比较（10）定量分析（11）制定安全对策 26.最小割集是指凡能导致顶上事件发生的最低限度的基 本事件的集合 27.最小径集是指凡不能导致顶上事件发生的最低限度的 基本事件的集合 28.最小割集和最小径集在事故树分析中的作用：（1）最 小割集表示系统的危险性。求出最小割集可以掌握事故发 生的各种可能，为事故调查和事故预防提供方便（2）最 小径集表示系统的安全性。求出最小径集我们可以知道， 要使事故不发生，有几种可能方案（3）最小割集能直观 地、概略地告诉人们，哪种事故模式最危险，哪种稍次， 哪种可以忽略（4）利用最小径集可以经济地、有效地选 择采用预防事故的方案（5）利用最小割集和最小径集可 以直接排出结构重要度顺序（6）利用最小割集和最小径 集计算顶上事件的发生概率和定量分析。 29.用最小割集或最小径集进行结构重要度分析：①频率: 当最小割集的基本事件个数不等时，基本事件少的割集中 的基本事件比基本事件多的割集中的基本事件结构重要 度大②频数：当最小割集的基本事件个数相等时，重复在 各最小割集中出现的基本事件比只在一个最小割集中出 现的基本事件结构重要度大，重复次数多的比重复次数少 的结构重要度大③看频率又看频数：在基本事件少的最小 割集中出现次数少的事件比基本事件多的最小割集中出 现次数多的相比较一般前者大于后者 30.三中重要度系数中，结构重要度系数从事故树结构上 反映进本事件的重要程度；概率重要度系数反映基本事件 概率的增减对顶上事件发生概率影响的敏感度；临界重要 度系数从敏感度和自身发生概率大小双重角度反映基本 事件的重要程度。其中，结构重要度系数反映了某一基本 事件在事故树结构中所占的地位，而临界重要度系数从结 构和概率上反映了改善某一基本事件的难易程度，概率重 要度系数则起着一种过渡作用，是计算两种重要度系数的 基础 31.安全评价原理：相关性原理、类推原理、惯性原理、 量变到质变原理。①相关性原理：在分析和处理问题时， 要恰当地分析和处理系统内外因素、各层次之间的联系 （相关性），以达到强化整体效应的目的。一个系统，其 属性、特征与事故和职业危害存在着因果的相关性，这是 系统因果评价方法的理论基础。②类推原理：类比推理是 根据两个或两类对象之间存在着某些相同或相似的属性， 从一个已知对象还具有某个属性来推出另一个对象具有 此种属性的一种推理。③惯性原理：任何事物在其发展过 程中，从其过去到现在以及延伸至将来，都具有一定的延 续性，这种延续性称为惯性。④量变到质变原理：任何一 个事物在发展变化过程中都存在着从量变到质变的规律 32.对于一个具有潜在危险性的作业条件，格雷厄姆和金 尼认为，影响危险性的主要因素有3个：①发生事故或危 险事件的可能性；②暴露于这种危险环境的情况；③事故 一旦发生可能产生的后果。用式（4-2）来表示，则为： D=L·E·C D——作业条件的危险性；L——事故或危险 事件发生的可能性；E——暴露于危险环境的频率；C—— 发生事故或危险事件的可能结果。 33.安全决策是通过对系统过去、现在发生的事故进行分 析的基础上，运用预测技术的手段，对系统未来事故变化 规律作出合理判断的过程。 34.系统安全预测就要预测造成事故后果的许多前级事 件，包括起因事件、过程事件和情况变化；随着生产的发 展以及新工艺、新技术的应用，预测会产生什么样的新危 险、新的不安全因素；随着科学的发展，预测未来的安全 生产面貌及应采取的安全对策。 35.系统安全预测同其他预测方法一样，遵循如下的基本 原理：（1）系统原则（2）类推和概率推断原则（3）惯性 原理 36.安全决策过程：（1）确定目标：从大安全观出发，安 全决策所涉及的主要问题就是保证人们的生产安全、生活 安全和生存安全。应进一步界定、分解和量化。生产安全 是一个总目标，它可以分解为预防事故发生，消除职业病 和改善劳动条件(2）确定决策方案:拟出几个可供选择的 方案。将达不到目标基本要求的方案舍弃掉，然后对各个 方案进行排序。排在第一位的方案也称为备选决策提案。 备选决策提案做进一步的慎重研究。（3）潜在问题或后果 分析:“假如采用这个方案，将要产生什么样的结果？假 如采用这个方案，可能导致哪些不良后果和错误？”① 人身安全方面②人的精神和思想方面③人的行为方面（4） 实施与反馈:实施过程中制定实施规划、落实实施机构、 人员职责，并及时检查与反馈实施情况，使决策方案在实 施过程中趋于完善并达到预期效果。 37.决策树是风险决策的基本方法之一。决策树分析方法 又称概率分析决策方法。决策树法是一种演绎性方法，即 是一种有序的概率图解法。 38.危险性与可操作性研究的成败关键：（1）对分析研究 所依据的制造过程图表及有关数据把握的正确性（2）小 组成员的专业技术和洞察能力（3）小组成员运用此方法 帮助其想象动作偏离、原因和后果的透视能力（4）小组 成员具备事故严重性分析能力，尤其是对已指出的危害， 在评估其严重性之时能对危害可能引起的严重性大小，具 有衡量其轻重之能力。 39.安全系统工程的静态构架，由抽象到具体，分别由4 个层次所构成：安全哲学，安全科学，安全技术，安全工 程 40.安全系统工程主要手段：首先，在系统的研发阶段， 安全系统工程要求设置安全工程系统管理计划。从理论上 说，在产品最初的构想阶段，安全因素就应该被充分的考 虑到。其次，安全系统通过以下几个手段来保证系统安全： 安全设计、安全预警、安全生产、安全训练 41.事故树分析法的特点：（1）结果：系统可能发生的事 故放在图的最上面，称为顶上事件。（2）原因：可能是其 他一些原因的结果，称为中间原因事件，应继续往下分析。 直到找出不能进一步往下分析的原因为止，这些原因称为 基本原因事件。（3）优点：是采用演绎方法分析事故的因 果关系。 42.事件分为事故事件和成功事件

中科院陈玉福计算机算法设计与分析期末简答题答案

1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。

算法设计与分析报告考试题(自测)

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_有穷性__,_确定性_,_可行性_,_ （0个或多个）输入__,_ （1个或多个）_输出_。 2.算法的复杂性有__时间复杂性__和__空间复杂性__之分，衡量一个 算法好坏的标准是__时间复杂度高低___。 3.某一问题可用动态规划算法求解的显著特征是___该问题具有最优 子结构性质___。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_{A,B,C,D}_。{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含_问题的一个（最优）解_。 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题_，先求解_子问题__，然后从这些_子问题_的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为__回溯法__。 8.0-1背包问题的回溯算法所需的计算时间为__O（n2n）__,用动态规划算法所需的计算时间为_O（n）__。o(min{nc,2n}) 9.动态规划算法的两个基本要素是_最优子结构_和_重叠子问题 ___。 10.二分搜索算法是利用__动态规划法__实现的算法。

二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 1、解：（1）找出最优解的性质，并刻画其结构特征； （2）递归地定义最优值； （3）以自底向上的方式计算出最优值； （4）根据计算最优值时得到的信息，构造最优解。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解 2.流水作业调度问题的johnson算法的思想。 2、解：①令N1={i|a i=b i}；②将N1中作业按a i 的非减序排序得到N1’，将N2中作业按b i的非增序排序得到N2’； ③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 3、解：步骤为：N1={1，3}，N2={2，4}； N1’={1，3}， N2’={4，2}； 最优值为：38

《算法设计与分析》复习题(汇编)

填空 1．直接或间接地调用自身的算法称为 递归 。 2．算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 3．以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。 5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题 6．算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。 7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8．快速排序算法的性能取决于 划分的对称性 。 9．计算机的资源最重要的是 内存 和 运算 资源。因而，算法的复杂性有时间 和 空间 之分。 10．贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 局部最优解 。 11．许多可以用贪心算法求解的问题一般具有2个重要的性质： 最优子结构的 性质和 贪心选择的 性质。 12．常见的两种分支限界法为 队列式 和 优先队列式 。 13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 动态规划和分支限界法 。 14．f ( n ) = 6 × 2n + n 2，f(n)的渐进性态f ( n ) = O ( 2^n )。 15．对于含有n 个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。 16．在忽略常数因子的情况下，O 、Ω和Θ三个符号中， Θ 提供了算法运行时间的一个上界。 17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。 18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。 19．多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。 21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进

算法设计与分析试卷(2010)

算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

算法设计与分析复习题目及答案

一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ）

算法设计与分析要点复习

算法设计与分析要点复习： 一、基本概念 1、什么是算法？算法是求解一类问题的人以一种特殊的方法。一个算法是对特 定问题求解步骤的一种描述，它是指令的有限序列。 2、算法有那些特性？输入、输出、确定性、能行性、有穷性。 3、评估一个算法的指标有那些（或者说分析一个算法的优劣主要考虑的因素）？ 正确性、简明性、效率、最优性。 4、算法运行的时间代价的度量不应依赖于算法运行的软件平台，算法运行的软 件包括操作系统和采用的编程语言及其编译系统。时间代价用执行基本操作（即关键操作）的次数来度量，这是进行算法分析的基础。 5、基本操作（即关键操作）是指算法运行中起主要作用且花费最多时间的操作。 6、基本操作是个概念，无法具体定义。问题的实例长度是指作为该问题的一个 实例的输入规模的大小。这个概念也很难精确定义。算法的时间（或）空间复杂度是由问题实例长度的函数来表示的。即：一个算法的时间代价由该算法用于问题长度为n的实例所需要的基本操作次数来表示。 7、算法的时间复杂度、空间复杂度。T(n)、S(n) 8、在实际的算法中T(n)是否唯一？不唯一。可能有最好、最坏、平均情形的时 间复杂度。 9、算法与程序的区别？ 10、算法按计算时间可分为两类：多项式是时间算法、指数时间算法。最常 见的多项式时间算法的渐进时间复杂度之间的关系为：O(1)

14、简述分治法是怎样的一种算法设计策略。 15、二分查找算法的实现前提？ 16、为什么要对二叉排序树进行平衡操作？ 17、什么是平衡因子？什么是二叉平衡树？二叉平衡树对平衡因子的取值有 什么要求？ 18、最优化问题：是指对于某类问题，给定某些约束条件，满足这些约束条 件的问题解称为可行解。为衡量可行解的好坏，还给出了称为目标函数的某个数值函数，使目标函数取的最大（或最小）值的可行解称为最优解。19、贪心算法总是做出在当前看来是最好的选择。也就是说贪心算法并不从 整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择，即使贪心算法不能得到整体最优解，但其最终结果也是最优解的很好的近似解。 20、贪心选择的基本要素：贪心选择性质、最优子结构性质 21、动态规划算法的基本要素：最优子结构性质、子问题重叠性质。 22、动态规划算法与分治法、贪心法比较有何特点？ 23、比较回溯算法、分枝限界算法。

太原理工大学系统分析实验报告

本科实验报告 课程名称：系统分析与设计 实验项目：《系统分析与设计》实验 实验地点：行逸楼B114 专业班级：软件学号： 学生姓名： 指导教师：孟东霞 2015年11月4日

一、实验目的 通过《系统分析与设计》实验，使学生在实际的案例中完成系统分析与系统设计中的主要步骤，并熟悉信息系统开发的有关应用软件，加深对信息系统分析与设计课程基础理论、基本知识的理解，提高分析和解决实际问题的能力，使学生在实践中熟悉信息系统分析与设计的规范，为后继的学习打下良好的基础。 二、实验要求 学生以个人为单位完成，自选题目，班内题目不重复，使用UML进行系统分析与设计，并完成实验报告。实验报告以纸质版（A4)在课程结束后二周上内提交（12周）。 三、实验主要设备：台式或笔记本计算机 四、实验内容 1 选题及项目背景 美食评价系统 背景：互联网时代下网络评论越来越随意，希望可以规范化的进行。 2 定义 美食评价系统为用户提供美食指导和参考。任何人都可注册为会员，个人资料包括姓名，性别，收藏的餐厅以及口味爱好。会员可以收藏餐馆，浏览餐馆信息以及其他会员的评价。餐厅必须向管理人员提出注册并审核通过后才能显示。管理人员需到工商局和餐厅具体审查后才能通过。会员可以提供来自餐馆提供的小票在次日来对用餐进行评价，一张小票仅可提供一次评价。餐馆则提供当日用餐小票记录给管理人员，用以核对用户提供的小票是否正确，然后系统则会审核评价有无不良信息，审核通过发布在餐厅信息上，并根据会员评价次数对给会员评星（1-5）。个人信息和餐馆信息可被所有人访问，管理员信息只能管理员访问。 3 参考资料 1．GB8567-88 《计算机软件产品文件编制规范》 2．GB/T11457-1995 《软件工程术语》 3．GB 1526—89 信息处理--数据流程图、程序流程图、系统流程图、程序网络图和系统资源图的文件编制符号及约定 4．GB8566-88 《软件开发规范》

计算机算法设计与分析期末考试复习题

1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。

2015算法设计与分析考试复习刚要习题

计算机算法设计与分析复习题一、填空题1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有时间复杂性和空间复杂性之分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O （1），在最坏情况下，搜索的时间复杂性为O（logn）。4、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程： n2O(1) T(n)2T(n/2)O(n)n2解得此递归方可得T(n)= O（）。 nlogn5、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。递归的二分查找算法在divide阶段所花的时间是 O(1) ，conquer阶段6．所花的时间是 T(n/2) ，算法的时间复杂度是 O( log n) 。7．Prim算法利用贪心策略求解最小生成树问题，其时间复杂度是 2O(n) 。8．背包问题可用贪心法，回溯法等策略求解。39．用动态规划算法计算矩阵连乘问题的最优值所花的时间是 O(n) ，子2问题空间大小是 O(n) 。10．图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是nm ，解空间树中每个内结点的孩子数是 m 。11．单源最短路径问题可用贪心法、分支限界等策略求解。12、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。 13、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。 14、直接或间接地调用自身的算法称为（递归算法）。 15、记号在算法复杂性的表示法中表示（渐进确界或紧致界）。 16、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题）的思想。 17、动态规划算法适用于解（具有

算法设计与分析复习题

一、选择题（多选） 1.算法必须满足哪些条件？ 算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足条件： (1)输入：有零个或多个由外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 2.哪些问题比较适合用递归算法？ 阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分问题、Hanoi塔问题分治策略（是高级的递归算法）：（1）二分搜索技术、（2）大整数的乘法、（3）Strassen 矩阵乘法、（4）棋盘覆盖、（5）合并排序、（6）快速排序、（7）线性时间选择、（8）最接近点对问题、（9）循环赛日程表 3. 哪些问题比较适合用贪心算法？ （1）活动安排问题（2）最优装载问题（3）哈夫曼编码（4）单源最短路径（5）最小生成树（6）多机调度问题 4. 哪些问题比较适合用回溯法？ （1）装载问题（2）批处理作业调度（3）符号三角形问题（4）n后问题（5）0-1背包问题（6）最大团问题（7）图的m着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题（11）连续邮资问题 二、概念题 1.递归的概念是什么？ 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。2.什么是0-1背包问题？ 给定n种物品和一个背包：物品i的重量是wi，其价值为vi，背包的容量为C。选择装入背包的物品，对于每种物品i只有两种选择，即装入背包或不装入背包，不能将物品i装入背包多次，也不能只装入部分的物品i，最终要使得装入背包中物品的总价值最大。该问题被称为0-1背包问题。 3.什么是哈夫曼编码，它有什么优缺点？ 由哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼编码是广泛地用于数据文件压缩。用于数据的无损耗压缩。其压缩率通常在20%～90%之间。 优点：给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 缺点：依赖于信源的统计特性，必须先统计得到信源的概率特性才能编码，而实际应用中，通常可在经验基础上预先提供Huffman码表，此时其性能有所下降。 4.什么是图的m着色问题？ 给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2的顶点着有不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称现这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。 5.什么是单源最短路径问题？

算法设计与分析期末试题答案解析

1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解；

健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一

算法设计与分析期末总复习

复习 一、简答题（每小题5分，选答2题，共10分） 1. 什么是算法？试说明算法设计分析过程的一般框架和主要步骤。 2. 简述非递归算法时间效率分析的通用方案。 3. 简述递归算法时间效率的通用方案。 4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。 二、分析题（每小题10分，共20分） 1. 考虑下面的算法。P52 算法Mystery(n) //输入：非负整数n S=0 for i ← 1 to n do S ← S + i*i Return S a.该算法求的是什么？ b.它的基本操作是什么？ c.该基本操作执行了多少次？ d.该算法的效率类型是什么？ 2. 考虑下面的递归算法。P52 算法Secret(A[0..n-1]) //输入：包含n个实数的数组A[0..n-1] minval ← A[0]; maxval ← A[0] for i ←1 to n-1 do if A[i] < minval minval ← A[i] if A[i] > maxval maxval ← A[i] return maxval – minval a.该算法求的是什么？ b.它的基本操作是什么？ c.该基本操作执行了多少次？ d.该算法的效率类型是什么？ 3. 考虑下面的递归算法P59 算法Q(n) //输入：正整数 if n=1 return 1 else return Q(n-1) + 2*n -1 a. 建立该函数值的递推关系并求解，以确定该算法计算的是什么； b. 建立该算法所做的乘法运算次数的递推关系并求解； c. 建立该算法所做的加减运算次数的递推关系并求解。 三、算法设计题（每小题10分，共20分） 1. 应用快速排序对序列E，X，A，M，P，L，E按照字母顺序排序。并画出相应的递归调