下载文档原格式
算法分析与设计作业参考答案《算法分析与设计》作业参考答案作业⼀⼀、名词解释：1.递归算法：直接或间接地调⽤⾃⾝的算法称为递归算法。
2.程序：程序是算法⽤某种程序设计语⾔的具体实现。
⼆、简答题：1.算法需要满⾜哪些性质？简述之。
答：算法是若⼲指令的有穷序列，满⾜性质：（1）输⼊：有零个或多个外部量作为算法的输⼊。
（2）输出：算法产⽣⾄少⼀个量作为输出。
（3）确定性：组成算法的每条指令清晰、⽆歧义。
（4）有限性：算法中每条指令的执⾏次数有限，执⾏每条指令的时间也有限。
2.简要分析分治法能解决的问题具有的特征。
答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩⼩到⼀定的程度就可以容易地解决；（2）该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质；（3）利⽤该问题分解出的⼦问题的解可以合并为该问题的解；（4）该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题。
3.简要分析在递归算法中消除递归调⽤，将递归算法转化为⾮递归算法的⽅法。
答：将递归算法转化为⾮递归算法的⽅法主要有：（1）采⽤⼀个⽤户定义的栈来模拟系统的递归调⽤⼯作栈。
该⽅法通⽤性强，但本质上还是递归，只不过⼈⼯做了本来由编译器做的事情，优化效果不明显。
（2）⽤递推来实现递归函数。
（3）通过Cooper 变换、反演变换能将⼀些递归转化为尾递归，从⽽迭代求出结果。
后两种⽅法在时空复杂度上均有较⼤改善，但其适⽤范围有限。
三、算法编写及算法应⽤分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]交换a[j]、a[j+1]；分析该算法的时间复杂性。
答：排序算法的基本运算步为元素⽐较，冒泡排序算法的时间复杂性就是求⽐较次数与n 的关系。
（1）设⽐较⼀次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。
平时作业1、给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。
a) int BinarySearch(Type a[], const Type& x, int l, int r){while (r >= l){int m = (l+r)/2;if (x == a[m]) return m;if (x < a[m]) r = m-1;else l = m+1;}return -1;}答：正确b) int BinarySearch(Type a[], const Type& x, int l, int r){while (r >= l){int m = (l+r)/2;if (x == a[m]) return m;if (x < a[m]) r = m+1;else l = m-1;}return -1;}答：错误if (x < a[m]) r = m+1; 当查找的元素在中间元素的左边时，右指针应该为m-1位置，修改成if (x < a[m]) r = m+1; else l = m+lc) int BinarySearch(Type a[], const Type& x, int l, int r){while (r > l){int m = (l+r)/2;if (x == a[m]) return m;if (x < a[m]) r = m-1;else l = m+1;}return -1;}答：错误。
while (r > l) 要考虑到数组只有一个元素的情况所以应该是r>=l ;2、O(1)空间子数组环卫算法：设a[0:n-1]是一个n维数组，k（1≤k ≤n-1）是一个非负整数。
试设计一个算法将子数组a[0 : k-1]与a[k+1 : n-1]换位。
要求算法在最坏情况下耗时O(n)，且只用O(1)的辅助空间。
一、填空题（20分）1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。
2.算法的困难性有_____________和___________之分，衡量一个算法好坏的标准是______________________。
3.某一问题可用动态规划算法求解的显著特征是____________________________________。
4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列_____________________________。
5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。
6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。
7.以深度优先方式系统搜寻问题解的算法称为_____________。
8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。
9.动态规划算法的两个基本要素是___________和___________。
10.二分搜寻算法是利用_______________实现的算法。
二、综合题（50分）1.写出设计动态规划算法的主要步骤。
2.流水作业调度问题的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个作业的最优调度方案，并计算最优值。
4.运用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根动身，左1右0），并画出其解空间树，计算其最优值及最优解。
作业1．第3题在软件工程学中，我们把一组具有相同数据结构和相同操作的对象的集合定义为（），此定义包括一组数据属性和在数据上的一组合法操作。
A.类B.属性C.对象D.消息答案:A标准答案：A您的答案：题目分数：2.0此题得分：0.02．第4题一个模块把开关量作为参数传递给另一模型，这两个模块之间的耦合是（）。
A.外部耦合B.数据耦合C.控制耦合D.内容耦合答案:C标准答案：C您的答案：题目分数：2.0此题得分：0.03．第5题在多层次的结构图中，其模块的层次数称为结构图的（）。
A.深度B.跨度C.控制域D.广度答案:A标准答案：A您的答案：题目分数：2.0此题得分：0.04．第6题下列方式中，不是由数据元素组成数据方式的是（）。
A.顺序B.层次C.选择D.重复答案:B标准答案：B您的答案：题目分数：2.0此题得分：0.05．第7题在对数据流的分析中，主要是找到中心变换，这是从（）导出结构图的关键。
A.数据结构B.实体关系C.数据流图D.Ｅ－Ｒ图答案:C标准答案：C您的答案：题目分数：1.0此题得分：0.06．第8题数据流图是用于表示软件模型的一种图示方法，在下列可采用的绘图方法中，（）是常采用的。
①自顶向下②自底向上③分层绘制④逐步求精A.全是B.①③④C.①③D.①②答案:B标准答案：B您的答案：题目分数：1.0此题得分：0.07．第11题结构化分析方法使用的描述工具（）定义了数据流图中每一个图形元素。
A.数据流图B.数据字典C.判定表D.判定树答案:B标准答案：B您的答案：题目分数：1.0此题得分：0.08．第12题程序的三种基本控制结构是（）。
A.过程、子程序和分程序B.顺序、选择和重复C.递归、堆栈和队列D.调用、返回和转移答案:B标准答案：B您的答案：题目分数：1.0此题得分：0.09．第13题Alpha测试是（）。
A.由用户在开发者的场所进行B.由软件的最终用户在开发者的一个或多个客户场所进行C.是在不受开发者控制的环境中进行的D.是软件在开发者不能控制的环境中的“真实应用答案:A标准答案：A您的答案：题目分数：1.0此题得分：0.010．第14题模块内的某成分的输出是另一成分的输入，该模块的内聚度是（）的。
《算法分析与设计》作业（一）本课程作业由两部分组成。
第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。
第二部分为“主观题部分”，由简答题和论述题组成，共15分。
作业总分30分，将作为平时成绩记入课程总成绩。
客观题部分：一、选择题（每题1分，共15题）1、递归算法：（C ）A、直接调用自身B、间接调用自身C、直接或间接调用自身D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归方式是：（C ）A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的：（A ）A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是：（A ）A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是：（B）A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是：（A）A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序可以不满足如下性质：（D ）A、零个或多个外部输入B、至少一个输出C、指令的确定性D、指令的有限性9、用分治法设计出的程序一般是：（A ）A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题：（ C ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是：（A ）A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ）A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到：（C ）A、全局最优解B、0-1背包问题的解C、背包问题的解D、无解14、能求解单源最短路径问题的算法是：（A ）A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是：（ A ）A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分：二、写出下列程序的答案（每题2.5分，共2题）1、请写出批处理作业调度的回溯算法。
PAD是（）的英文缩写。
答案:问题分析图（）是面向数据流自顶向下逐步求精进行需求分析的方法。
答案:结构化分析方法（）也称为聚合，它表示类与类之间的关系是整体与部分的关系。
答案:聚集（）模型是典型的面向对象的软件过程模型。
答案:喷泉模型Petri网的标记是在Petri网中（）的分配。
答案:权标（）是为了集中精力解决主要问题而尽量推迟对问题细节的考虑。
答案:逐步求精耦合是对一个软件结构内不同模块之间（）程度的度量。
答案:互连程度基线就是通过了正式复审的软件（）。
答案:配置项需求分析阶段得出的数据流图是（）的极好的出发点。
答案:总体设计（）就是抽出事物的本质特征而暂时不考虑它们的细节。
答案:抽象通常所说的结构化设计方法，也是基于（）流的设计方法。
答案:数据维护过程本质上是修改和压缩了的（）和（）。
答案:软件定义、开发过程软件配置管理主要有５项任务：（）、（）、（）、配置审计和报告。
答案:标识、版本控制、变化控制软件工程包括（）和（）两方面的内容，是技术与管理紧密结合所形成的工程学科。
答案:技术、管理通常把对象的操作称为（）或（）。
答案:服务、方法（）、和（）这三个方面研究每种解法的可行性。
答案:技术可行性、经济可行性、操作可行性为了估算项目的工作量和完成期限，目前常采用（）和（）两种技术估算软件规模。
答案:代码行技术、功能点技术在测试过程中，由于模块并不是一个独立的程序，因此必须为每个单元测试开发（）和（或）（）。
答案:驱动程序、存根程序人工测试源程序如果由审查小组正式地进行，则称为（）。
答案:代码审查成本／效益分析的目的正是要从（）角度分析开发一个特定的新系统是否划算，从而帮助客户组织的负责人正确地作出是否投资于这项开发工程的决定。
答案:经济当用代码行技术估算软件规模时，当程序较小时，常采用的单位是（）（LOC），当程序较大时，常用的单位是（）（KLOC）。
答案: 代码行数、千行代码数Jackson图不仅可表示程序结构，还可表示（）和（）。
华中师范大学网络教育学院《算法设计与分析》练习题库及答案《算法设计与分析》练习题库及答案(加粗红色字体为2013下新增题目) 一、概念题：请解释下列术语。
1．数据类型2．队列3．多项式复杂度4．满二叉树5． NP-难度6．算法7． SIMD(并行算法)8．连通图9．抽象数据类型10．指数复杂度11．递归12．完全二叉树13．状态空间树14． NP-完全的15．算法与过程16．有向图与无向图17．树18． P类问题19. 确定的算法20. NP问题21. 最小生成树22. 动态规划23. 数据结构24. 排序二、填空题1. 简单递选分类过程中所需进行移动存储的操作次数较少，其最大值为___________。
2. 一组有序的n个数，采用逐个查找算法查找一给定的数是否出现在序列中，其算法复杂性为_____________。
3. 动态规划实际上是研究一类__________________的算法，其应用非常广泛。
4. BFS算法的中文名称是______________________算法。
5. 一棵树中定义为该树的高度或深度。
6. 二分检索树要求树中所有结点中的元素满足。
7. 比较树的结点由称为和的两种结点组成。
8. 外结点用一个结点表示，在二分检索算法中它表示不成功检索的一种情况。
9. 由根到所有内部结点的距离之和称为 ;由根到所有外部结点的距离之和称为 .10．max和min被看成是两个内部函数，它们分别求取两个元素的大者和小者，并认为每次调用其中的一个函数都只需作次元素比较。
11．如果用分治策略来设计分类算法，则可使最坏情况时间变为o(n logn)。
这样的算法称为。
12.贪心算法可行的第一个基本要素是。
13. 当一个问题的最优解包含着它的子问题的最优解时，称此问题具有性质。
14. 二路归并模式可以用树来表示。
15. kruskal算法对于每一个无向连通图g产生一棵。
16．因为如果有环，则可去掉这个环且不增加这条路径的长度(不含有负长度的环)。
1、算法分析中，记号O表示（）•A、渐进上界•B、非紧上界•C、非紧下界•D、2、在找零钱问题中，收银员算法中所应用的贪心规则的最恰当描述是（）。
•A、总是选择面值最高的硬币•B、总是选择不超过剩余应找钱数的最大面值的硬币•C、总是选择面值是10，5的倍数的硬币•3、由边界条件出发,通过递推式求f(n)的值,从边界到求解的全过程十分清楚的是（）•A、贪心•B、递推•C、递归•4、考虑最长公共子序列问题的下述递归表达式，如果全部子问题组织在一个c[i,j]的二维表格中，则c[i,j]不依赖于下述哪个子问题：（）。
•A、同一行的上一列•B、同一列的上一行•C、上一行的上一列•5、算法的时间复杂度是指（）•A、执行算法程序所需要的时间•B、算法程序的长度•C、算法执行过程中所需要的基本运算次数•6、活动选择问题就是在所给的活动集合中，选出（）的相容活动子集。
•A、当前可选活动中结束时间最早的活动•B、当前可选活动中开始时间最早的活动•C、当前可选活动中冲突数量最少的活动•7、一个长度为n英寸的钢管的最优切割问题，总共有( )个不同的子问题。
•A、n+1•B、n2•C、nlogn•8、最优二叉搜索树的时间复杂度为（）。
•A、O(n)•B、O(n!)•C、O(n2)•9、算法的每种运算必须要有确切的定义,不能有二义性,以下符合算法确定性运算的是（）•A、5/0•B、将6或7与x相加•C、未赋值变量参与运算•10、对于三个物体的背包问题，问题相关的数据为n=3, M=20,P=(25,24,15),W(18,15,10)。
下面给出的四个可行解中，最好的是（）•A、(1/2，1/3，1/4)•B、(1，2/15，0)•C、(0，2/3，1)••A、f(0)=0•B、f(1)=1•C、f(0)=1•12、下面关于快速排序的说法，正确的是（）•A、快速排序的速度和数据无关，是一个固定的值•B、快速排序的速度在分解的均匀的时候效果最好，速度最快•C、快速排序主要的时间花在合并上面•D、•A、货郎担问题是求取具有最大成本的周游路线问题•B、货郎担问题适合使用贪心算法求问题的最优解•C、货郎担问题存在多项式时间算法•14、实现快速排序算法如下： QuickSort (A, p, r)IF p < r THENq ← Partition(A, p, r)( )QuickSort(A, q+1, r)•A、QuickSort(A,q-1,r)•B、QuickSort(A,q-1,r)•C、QuickSort(A,q+1,r)•哪个是对的（）。
1、给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。
a) int BinarySearch(Type a[], const Type& x, int l, int r){while (r >= l){int m = (l+r)/2;if (x == a[m]) return m;if (x < a[m]) r = m-1;else l = m+1;}return -1;}答：正确b) int BinarySearch(Type a[], const Type& x, int l, int r){while (r >= l){int m = (l+r)/2;if (x == a[m]) return m;if (x < a[m]) r = m+1;else l = m-1;}return -1;}答：错误，if (x < a[m]) r = m-1;else l = m+1;c) int BinarySearch(Type a[], const Type& x, int l, int r){while (r > l){int m = (l+r)/2;if (x == a[m]) return m;if (x < a[m]) r = m-1;else l = m+1;}return -1;}答：错误，while (r >= l){2、O(1)空间子数组环卫算法：设a[0:n-1]是一个n维数组，k（1≤k ≤n-1）是一个非负整数。
试设计一个算法将子数组a[0 : k-1]与a[k+1 : n-1]换位。
要求算法在最坏情况下耗时O(n)，且只用O(1)的辅助空间。
答：算法分析：当v[k]左边子数组的长度等于右边的子数组长度时，直接将两个子数组对应的元素互换即可当左边子数组长度小于右边子数组长度时，将左边子数组与右边子数组右边的等长子数组对换，再对结果递归调用对换函数当右边子数组长度小于左边子数组长度时，将右边子数组与左边子数组左边的等长子数组对换，再对结果递归调用对换函数通过分析，可知只需要利用保存元素对换时的交换空间即可，空间复杂度为O(1)，子数组对换时时间复杂度不会超过O(n)#include <stdio.h>#include <stdlib.h>#include <vector>#include <iostream>using namespace std;//对应互换v的left_low-left_high 和right_low - right_highvoid Swap(vector<int> & v,int left_low,int left_high,int right_low,int right_high){int temp;while(left_low <= left_high){temp = v[left_low];v[left_low] = v[right_low];v[right_low] = temp;++left_low;++right_low;}return;}//分治算法，每次选最小的子数组对应交换void Exchange(vector<int> & v,int k,int low,int high){if(low<high){if((k-low+1)==(high-k)){//v[k]左右两个子数组长度相等，直接互换Swap(v,low,k,k+1,high);} else if((k-low+1)<(high-k)){//v[k]左边子数组长度小于右边子数组，将左边的子数组互换到右边子数组的右边Swap(v,low,k,low+high-k,high);Exchange(v,k,low,low+high-k-1);} else{ //v[k]右边子数组换到左边子数组前部分Swap(v,low,high+low-k-1,k+1,high);Exchange(v,k,high+low-k,high);}}return;}int main(){vector<int> v;int n,k;while(scanf("%d%d",&n,&k)==2){v.resize(n);for(int i=0;i<n;++i){scanf("%d",&v[i]);}printf("Before exchange subarray:\n");for(int j=0;j<n;++j){printf("%d ",v[j]);}printf("\n");Exchange(v,k,0,n-1);printf("After exchange subarray:\n");for(int k=0;k<n;++k){printf("%d ",v[k]);}printf("\n");}return 0;}3、定义： 给定一个自然数n ，由n 开始依次产生半数集set(n)中的元素如下：1）()n set n ∈；2）在n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；3）按此规则进行处理，直至不能再添加新的自然数为止。
例如 (){6,16,26,126,36,136}set n =。
其中共有6个元素。
半数集问题：对于给定的n ，求半数集set(n) 中元素的个数。
答：#include<iostream.h>using namespace std;int a[1001];int comp(int n){int i;for( i=2;i<=n;i++){if(i%2==0) a[i]=a[i/2]+a[i-1];else a[i]=a[i-1];}return a[n];}int main(){int n;cout<<"请输入一个不大于1000的自然数：n=";cin>>n;for(int i=0;i<=n;i++)a[i]=i;if(n<=0||n>1000)cout<<endl<<"输入错误，请注意输入值n的范围."<<endl;else{cout<<endl<<"半数集set("<<n<<")中的元素个数为：";cout<<comp(n)<<endl;}return 0;}4、设计一个算法，找出由n个数组成的序列的最长单调递增子序列的长度。
答：#include<iostream.h>#define m 10//快速排序void QuickSort(int R[],int s,int t){int i=s,j=t;int tmp;if(s<t){tmp=R[s];while(i!=j){while(j>i&&R[j]>=tmp)j--;R[i]=R[j];while(i<j&&R[i]<=tmp)i++;R[j]=R[i];}R[i]=tmp;QuickSort(R,s,i-1);QuickSort(R,i+1,t);}}//找出最长公共子序列void LCSLength(int x[],int y[],int n,int c[m][m],int b[m][m]) {int i,j;for(i=0;i<n;i++){c[0][i]=0;c[i][0]=0;}for(i=0;i<n;i++)for(j=0;j<n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;} else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;} else{c[i][j]=c[i][j-1];b[i][j]=3;}}}void LCS(int i,int j,int *x,int b[m][m]){if(i<0||j<0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i]<<" ";} else if(b[i][j]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}void main(){int x[m],y[m],d;cout<<"请输入元素个数"<<endl;cin>>d;cout<<"请输入元素"<<endl;for(int i=0;i<d;i++){cin>>x[i];y[i]=x[i];}int c[m][m]={0},b[m][m]={0};QuickSort(x,0,d-1);LCSLength(x,y,d,c,b);cout<<"最长单调递增子序列为："<<endl;LCS(d-1,d-1,x,b);}5、会场安排问题：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。
设计一个有效的贪心算法进行安排。
对于给定的n个待安排的活动，计算使用最少会场的个数。
每个活动i都有一个开始时间和结束时间，分别表示为b(i)，f(i)。
答：#include<iostream>using namespace std;#define M 50 //最大活动数struct Active{int b;//开始时间int f;//结束时间int no;//预安排会场号}a[M];//两元素交换位置void swap(Active &a,Active &b){Active t;t=a;a=b;b=t;}void main(){int k;int i,j;cout<<"输入待安排活动数:"<<endl;cin>>k;cout<<"输入待安排活动的开始时间和结束时间:"<<endl;//输入活动时间for(i=1;i<=k;i++){cin>>a[i].b>>a[i].f;a[i].no=0;}//活动时间排序for(i=1;i<=k;i++){for(j=i;j<=k;j++){if(a[i].b>a[j].b)swap(a[i],a[j]);if(a[i].b==a[j].b){if(a[i].f>a[j].f)swap(a[i],a[j]);}}}int sum=1;//使用的会场数初始化int n;a[1].no=sum;for(i=2;i<=k;i++){for(n=1;n<i;n++){if(a[n].no!=0&&a[n].f<=a[i].b){a[i].no=a[n].no;a[n].no=0;//已经安排过的活动就不再比较break;}}if(n==i){sum+=1;a[i].no=sum;}}cout<<"输出最少会场数:\n"<<sum<<endl;system("pause");}6、最优分解问题：设n是一个正整数。
