下载文档原格式
精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案1习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。
出生于瑞士的伟大数学家欧拉（提出并解决了该问题。
七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。
请将该问题的数据模型抽象出来，并判断此问题是否有解。
七桥问题属于一笔画问题。
输入：一个起点输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。
另一类是只有二个奇点的图形。
）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。
请用伪代码描述这个版本的欧几里德算法1.r=m-nr=0 循环直到2.m=n 2.1n=r 2.2r=m-n 2.3m输出3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。
要求分别给出伪代3++描述。
C码和采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档．精品文档#include <iostream>using namespace std;int partions(int b[],int low,int high){int prvotkey=b[low];b[0]=b[low];while (low<high){while (low<high&&b[high]>=prvotkey)--high;b[low]=b[high];while (low<high&&b[low]<=prvotkey)++low;b[high]=b[low];}b[low]=b[0];return low;}void qsort(int l[],int low,int high){int prvotloc;if(low<high){prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); //递归调用排序由low 到prvotloc-1qsort(l,prvotloc+1,high); //递归调用排序由 prvotloc+1到 high}}void quicksort(int l[],int n){qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个}int main(){int a[11]={0,2,32,43,23,45,36,57,14,27,39};int value=0;//将最小差的值赋值给valuefor (int b=1;b<11;b++)cout<<a[b]<<' ';精品文档．精品文档cout<<endl;quicksort(a,11);for(int i=0;i!=9;++i){if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) )value=a[i+1]-a[i];elsevalue=a[i+2]-a[i+1];}cout<<value<<endl;return 0;}4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。
算法分析与设计（线下作业⼆）《算法分析与设计》学习中⼼：专业：学号：姓名：作业练习⼆⼀、名词解释1、MST性质2、⼦问题的重叠性质递归算法求解问题时，每次产⽣的⼦问题并不总是新问题，有些⼦问题被反复计算多次，这种性质称为⼦问题的重叠性质。
⼆、简答题1、简述动态规划算法求解的基本要素。
答：动态规划算法求解的基本要素包括：1)最优⼦结构是问题能⽤动态规划算法求解的前提；2)动态规划算法，对每⼀个⼦问题只解⼀次，⽽后将其解保存在⼀个表格中，当再次需要解此⼦问题时，只是简单地⽤常数时间查看⼀下结果，即重叠⼦问题。
2、备忘录⽅法和动态规划算法相⽐有何异同简述之。
答：备忘录⽅法是动态规划算法的变形。
与动态规划算法⼀样，备忘录⽅法⽤表格保存已解决的⼦问题的答案，在下次需要解此问题时，只要简单地查看该⼦问题的解答，⽽不必重新计算。
备忘录⽅法与动态规划算法不同的是，备忘录⽅法的递归⽅式是⾃顶向下的，⽽动态规划算法则是⾃底向上递归的。
因此，备忘录⽅法的控制结构与直接递归⽅法的控制结构相同，区别在于备忘录⽅法为每个解过的⼦问题建⽴了备忘录以备需要时查看，避免了相同的⼦问题的重复求解，⽽直接递归⽅法没有此功能。
3、贪⼼算法求解的问题主要具有哪些性质简述之。
答：贪⼼算法求解的问题⼀般具有⼆个重要的性质：⼀是贪⼼选择性质，这是贪⼼算法可⾏的第⼀个基本要素；另⼀个是最优⼦结构性质，问题的最优⼦结构性质是该问题可⽤贪⼼算法求解的关键特征。
三、算法编写及算法应⽤分析题1、设计求解如下最⼤⼦段和问题的动态规划算法。
只需给出其递推计算公式即可。
最⼤⼦段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的⼦段和的最⼤值。
当所有整数均为负整数时定义其最⼤⼦段和为0。
依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。
2、关于多段图问题。
设G ＝(V ，E)是⼀个赋权有向图，其顶点集V 被划分成k>2个不相交的⼦集V i ：1i k ≤≤，其中，V 1和V k 分别只有⼀个顶点s （称为源）和⼀个顶点t （称为汇），图中所有的边（u,v ），i u V ∈，1i v V +∈。
算法设计与分析习题答案算法设计与分析是计算机科学中一个重要的领域，它涉及到算法的创建、优化以及评估。
以下是一些典型的算法设计与分析习题及其答案。
习题1：二分查找算法问题描述：给定一个已排序的整数数组，编写一个函数来查找一个目标值是否存在于数组中。
答案：二分查找算法的基本思想是将数组分成两半，比较中间元素与目标值的大小，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。
这个过程会不断重复，直到找到目标值或搜索范围为空。
```pythondef binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return Trueelif arr[mid] < target:low = mid + 1else:high = mid - 1return False```习题2：归并排序算法问题描述：给定一个无序数组，使用归并排序算法对其进行排序。
答案：归并排序是一种分治算法，它将数组分成两半，分别对这两半进行排序，然后将排序好的两半合并成一个有序数组。
```pythondef merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]merge_sort(left_half)merge_sort(right_half)i = j = k = 0while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]:arr[k] = left_half[i]i += 1else:arr[k] = right_half[j]j += 1k += 1while i < len(left_half):arr[k] = left_half[i]i += 1k += 1while j < len(right_half):arr[k] = right_half[j]j += 1k += 1arr = [38, 27, 43, 3, 9, 82, 10]merge_sort(arr)print("Sorted array is:", arr)```习题3：动态规划求解最长公共子序列问题问题描述：给定两个序列，找到它们的最长公共子序列。
算法分析与设计作业参考答案《算法分析与设计》作业参考答案作业⼀⼀、名词解释：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.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。
《算法分析与设计》作业( 一)本课程作业由两部分组成。
第一部分为”客观题部分”, 由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、请写出批处理作业调度的回溯算法。
算法设计与分析作业姓名：学号：专业：习题一1-1函数的渐进表达式3n2+10n=O(n2);n2/10+2n=O(2n);21+1/n=O(1);logn3=O(logn);10log3n=O(n)1-2O(1)和O(2)的区别分析与解答：根据符号O的定义可知O（1）=O（2）.用O（1）和O（2）表示同一个函数时，差别仅在于其中的常数因子。
1-3按渐进阶排列表达式分析与解答：按渐进阶从低到高，函数排列顺序如下：O(2)<O(logn)<O(n2/3)<O(20n)<O(4n2)<O(3n)<O(n!)习题二算法分析题2-2 7个二分搜索算法分析与解答：（1）与主教材中的算法BinarySearch相比，数组段左、右游标left和right的调整不正确，导致陷入死循环。
（2）数组段左、右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。
（3）数组段左、右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。
（4）数组段左、右游标left和right的调整不正确，导致陷入死循环。
（5）算法正确，且当数组中有重复元素时，返回满足条件的最右元素。
（6）数组段左、右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。
（7）数组段左、右游标left和right的调整不正确，导致当x=a[0]时陷入死循环。
2-26修改快速排序算法，使它在最坏情况下的计算时间为O（nlogn）.分析与解答：从一个无序的序列中随机取出一个值q做为支点,然后把大于q的放到一边，小于q的放到q的另一边,然后再以q为分界点，分别对q的两边进行排序（快排时直接再对q两边重新取支点，整理，再取支点，...直到支点两旁都有序。
也就是支点两旁只有一个数时）#include <stdio.h>#include <stdlib.h>int Qsort(int p[],int beg,int end){if(beg+1>=end)return 0;//退出递归int low,hight,q;low=beg;hight=end;q=p[low];//q为支点，其实q可以为随机数。
1、实验内容递归求n的二次方各项的系数。
2、程序设计代码如下：#include"stdio.h"void coeff(int a[],int n)if(n==1)a[1]=1;a[2]=1;elsecoeff(a,n-1);a[n+1]=1;for(int i=n;i>=2;i=i-1)a[i]=a[i]+a[i-1];a[1]=1;void main()int a[100],i,n;printf("输入n的值：");scanf("%d",&n);coeff(a,n);for(i=1;i<=n+1;i++)printf(" %d ",a[i]);printf("\n");1、实验内容写出计算ackerman函数ack(m,n)的递归计算函数。
2、程序设计代码如下：#include "stdio.h"int ack(int m,int n)if(m==0)return n+1;else if(n==0)return ack(m-1,1);elsereturn ack(m-1,ack(m,m-1));void main()int m,n,z;printf("input m and n:");scanf("%d %d",&m,&n);if(m<0 && n<0)printf("error input!");elsez=ack(m,n);printf("%d\n",z);第四章例15 求数列的最大子段和给定n个元素的整数列（可能为负整数）a1,a2,…..,an。
求形如：ai,ai+1,……aj i,j=1,…..,n,i<=j的子段，使其和为最大。
算法分析与设计作业及参考答案作业题目1、请分析冒泡排序算法的时间复杂度和空间复杂度，并举例说明其在实际中的应用场景。
2、设计一个算法，用于在一个未排序的整数数组中找到第二大的元素，并分析其时间复杂度。
3、比较贪心算法和动态规划算法的异同，并分别举例说明它们在解决问题中的应用。
参考答案1、冒泡排序算法时间复杂度：冒泡排序的基本思想是通过相邻元素的比较和交换，将最大的元素逐步“浮”到数组的末尾。
在最坏情况下，数组完全逆序，需要进行 n 1 轮比较和交换，每一轮比较 n i 次（i 表示当前轮数），所以总的比较次数为 n(n 1) ／ 2，时间复杂度为 O(n^2)。
在最好情况下，数组已经有序，只需要进行一轮比较，时间复杂度为 O(n)。
平均情况下，时间复杂度也为 O(n^2)。
空间复杂度：冒泡排序只在原数组上进行操作，不需要额外的存储空间，空间复杂度为 O(1)。
应用场景：冒泡排序算法简单易懂，对于规模较小的数组，或者对算法的简单性要求较高而对性能要求不是特别苛刻的场景，如对少量数据进行简单排序时，可以使用冒泡排序。
例如，在一个小型的学生成绩管理系统中，需要对一个班级的少量学生成绩进行排序展示，冒泡排序就可以满足需求。
2、找到第二大元素的算法以下是一种使用遍历的方法来找到未排序整数数组中第二大元素的算法：｀｀｀pythondef find_second_largest(arr)：largest ＝ arr0second_largest ＝ float(＇inf'）for num in arr:if num ＞ largest:second_largest ＝ largestlargest ＝ numelif num ＞ second_largest and num!＝ largest:second_largest ＝ numreturn second_largest｀｀｀时间复杂度分析：这个算法需要遍历数组一次，所以时间复杂度为O(n)。
一。
选择题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. 回溯法解旅行售货员问题时的解空间树是（ 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 ）A、分治法B、动态规划法C、贪心法D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。
A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）。
《算法分析与设计》
学习中心：
专业：
学号：
姓名：
作业练习二
一、名词解释
1、MST性质
2、子问题的重叠性质
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。
二、简答题
1、简述动态规划算法求解的基本要素。
答：动态规划算法求解的基本要素包括：
1)最优子结构是问题能用动态规划算法求解的前提；
2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。
2、备忘录方法和动态规划算法相比有何异同简述之。
答：备忘录方法是动态规划算法的变形。
与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。
备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。
因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。
3、贪心算法求解的问题主要具有哪些性质简述之。
答：贪心算法求解的问题一般具有二个重要的性质：
一是贪心选择性质，这是贪心算法可行的第一个基本要素；
另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。
三、算法编写及算法应用分析题
1、设计求解如下最大子段和问题的动态规划算法。
只需给出其递推计算公式即可。
最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。
当所有整数均为负整数时定义其最大子段和为0。
依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。
2、关于多段图问题。
设G ＝(V ，E)是一个赋权有向图，其顶点集V 被划分成k>2个不相交的子集V i ：1i k ≤≤，其中，V 1和V k 分别只有一个顶点s （称为源）和一个顶点t （称为汇），图中所有的边（u,v ），i u V ∈，1i v V +∈。
求由s 到t 的最小成本路径。
① 给出使用动态规划算法求解多段图问题的基本思想。
② 使用上述方法求解如下多段图问题。
s t
V1V2V3V4V5
3、最优二元归并问题：已知将两个分别包含a 个和b 个记录的已分类文件归并在一起得到一个分类文件需作a+b 次记录移动。
现有n 个已分类文件F1,F1,⋯,Fn，它们的记录个数分别为l1, l2,⋯, ln。
现在考虑使用二元归并模式将这n 个文件归并成一个分类文件，要求记录移动次数最少。
设计一个贪心算法来求解一种最优的二元归并（即记录移动次数最少的二元归并）。
4、带限期的作业调度问题：n 个作业需要在一台机器上处理，每个作业可在单位时间内完
成。
每个作业i 都有一个截止期限di>0(di 为整数)，当且仅当作业i 在它的截止期限之前被完成，获得pi>0 的效益。
一种可行的调度方案为n 个作业的一个子集J，其中J 中的每个作业都能在各自的截止期限内完成。
该可行调度方案的效益是J 中作业的效益之和。
试设计贪心算法求效益最大的可行调度方案（即最优调度方案）。
