《算法作业和期末复习题》由会员分享，可在线阅读，更多相关《算法作业和期末复习题（12页珍藏版）》请在金锄头文库上搜索。
1、11给出递推公式x(n)=x(n-1)+n,x(0)=0对应的通项公式计算过程？解： X(n)-X(n-1)=nX(n-1)-X(n-2)=n-1 X(1)-X(0)=1X(n)-X(0)=(n+1)n2X(n)= (n+1)n22、之间的区别与联系描述增长率的上限 上限值越低，结果越有价值。用来表示算法的精确阶描述增长率的下限 下限值越高越有价值。联系： 只要当考察问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，通常使用 3种等渐近符号。3什么是数据结构，什么是算法，两者有什么关系？数据结构：是指相互之间存在一定关系的数据元素的集合。算法：是对特定问题求解步骤的一种描述是指令的有
2、限序列。程序=算法+数据结构5举例说明分治法、动态规划法和贪心法适用范围，及三者之间的区别。答：分治法：适用于原问题可划分为子问题时如汉诺塔问题（循环赛，最近对，棋盘覆盖等）动态规划：当原问题可分解为子问题并且问题重叠并且具有最优子结构时可用动态规划法，如 TSP问题（多端最短路径问题，0/1 背包问题等）贪心：当一个问题具有最优子结构性质且具有贪心选择性时可用贪心算法，如最小生成树问题（背包问题，活动安排问题等）在分治法的基础上，满足最优子结构性质才能用动态规划，在动态规划可行的基础上满足贪心选择性才能用贪心。6简述分治法、贪心法、蛮力法、回溯法、减治法的设计思想。分治：建一个难以直接解决的
3、大问题划分成一些规模较小的子问题，以便各个2击破，分而治之。贪心把一个问题分解为一系列较简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解。 （指根据当前已有信息做出选择，不从整体最优考虑，只选择局部最优蛮力：采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解。回溯：只构造可能解的一部分，然后评估这个部分解，如果这个部分解有可能导致一个完全解，则对其进一步构造，否则，就不必继续构造这个解了。减治：把一个大问题划分为若干子问题，但些子问题不需要分别求解，只需求解其中那个一个子问题。7举例说明分治法和减治法的在设计上区别与联系。分治法是将一个大问题分解为若干
4、子问题分别求解，而减治法是只求解部分子问题。在排序问题中，分治法用用快速排序，以轴值为基准划分序列，再求每个子集递归序列，最后合并并操作。减治法则用选择问题算法，先选定轴值并划分，比轴值小的在左侧，比轴值大的在右侧，选择问题的查找区间减少一半，划分后只需处理一个子序列。8简述什么是欧拉回路，TSP 问题，哈密顿回路问题。欧拉回路：图 G的一个回路，若它恰它通过 G 中每条边一次，则称该回路为欧拉回路。TSP：从图的一个顶点出发，各个定点只能经历并访问一次，最后回到原点且使路径最短。哈密顿回路：从一个城市出发，经过每一个城市恰好一次，然后回到出发城市。1给出应用动态规划法设计算法的一般步骤，并用
5、动态规划法求下面多段图中从顶点 0到顶点 15的最短路径，写出求解过程。解：d(0,9)=minc01 +d(1,9) , c02+d(2,9) , c03 +d(3,9) d(1,9)=minc14 +d(4,9) , c15+d(5,9) d(2,9)=minc24 +d(4,9) , c25+d(5,9) , c26 +d(6,9) d(3,9)=minc35 +d(5,9) , c36+d(6,9) d(4,9)=minc47 +d(7,9) , c48+d(8,9) d(5,9)=minc57 +d(7,9) , c58+d(8,9) 3d(0,9)=minc67 +d(7,9) ,
6、 c68+d(8,9) d(7,9)= c79 =7 (79)d(8,9)= c89 =3(89)d(6,9)=min6+7,5+3=8(68)d(5,9)= min8+7,6+3=9(58)d(4,9)= min5+7,6+3=9(48)d(3,9)=min4+9,7+8=13(35)d(2,9)=min6+9,7+9,8+8=15(24)d(1,9)=min9+9,8+9=17(15)d(0,9)=min4+17,2+15,3+13=16(03)最后得最短路径为 03589 长度为 16。 2有 4个物品，其重量分别为(4, 7, 5, 3)，物品的价值分别为(40, 42, 25, 12
7、)，背包容量为 10。试设计 3种贪心策略,并给出在每种贪心策略下背包问题的解。 重量最轻：装入 143.总价值：40+12+25*3/5=67价值最大：装入 1，2。总价值：40*3/4+42=72性价比最小：装入 1，2.总价值：40+6/7*42=763给出23 13 49 6 31 19 28采用快速排序思想进行排序时一次划分的过程示意图。19 13 49 6 31 23 2819 13 23 6 31 49 2819 13 6 23 31 49 281给定数组 An，存储 n个实数，试设计一个算法，在最坏情况下用最少比较次数找出该数组中元素的最大值和最小值，并说明采用了何种算法设计思
8、想，其最坏比较多少次。求数组的最大值和最小值a)问题求给定数组 a0:n-1的最大值和最小值。要求：最坏情况下用 3n/2-2次比较b)分析4分治法，把数组分成 n/2组，每组 2个数。然后每组的两个数进行一次比较，确定出每组的最大数和最小数保存在数组 MAXi和 MINi中，这样总共进行了n/2次比较。最后从 MAXi中找出最大的数 MAX，从 MINi中找出最小的数MIN，需要 2*（n/2-1）次比较。MAX 和 MIN就是原来问题的解。总比较次数为3n/2 2次该算法在任何情况下进行的比较次数都是 3n/2 2,固最差情况也是 3n/2 2.c)编程实现Quoted from 求数组的
9、最大值和最小值:/two15.java/该算法在任何情况下的比较次数都是 3N/2 -2。所以在最差情况下也是 3N/2 -2import javax.swing.JOptionPane;public class two15public static void main(String args)int a=new int50;/int min=new int25;/int max=new int25;/int n=0,i=0,k=1;String num;String aa=new String50;num=JOptionPane.showInputDialog(enter the total
10、 num of the array);n=Integer.parseInt(num);/单个数不进行比较if(n!=1)for(i=0;imaxm) maxm=maxk;if(minkmaxm) maxm=an-1;if(an-1#include using namespace std;7int Check_out(int B,int n);int main() int n,n1;coutn;int *B=new intn;coutn1; while(n1!=0&n1!=2&n1!=1)coutn1; Bi=n1;if (B0 + B1 +B2) = (B3 +B4 + B5)if (B0 =
11、 B6)cout #include #include #define MAX_STEP 20 /index: 0 - 狼，1羊，2菜，3农夫，value：0本岸，1对岸 int aMAX_STEP4; int bMAX_STEP; char *name = 空手, 狼, 带羊, 带菜 ; void search(int iStep) int i; if (aiStep0 + aiStep1 + aiStep2 + aiStep3 = 4) for (i = 0; i #include #define N 50 /*叶子结点数*/#define M 2*N-1 /*树中结点总数*/typedef
12、 structchar data5; /*结点值*/int weight; /*权重*/int parent; /*双亲结点*/int lchild; /*左孩子结点*/int rchild; /*右孩子结点*/10 HTNode;typedef structchar cdN; /*存放哈夫曼码*/int start; HCode;void CreateHT(HTNode ht,int n)int i,k,lnode,rnode;int min1,min2;for (i=0;i2*n-1;i+) /*所有结点的相关域置初值-1*/hti.parent=hti.lchild=hti.rchild
13、=-1;for (i=n;i2*n-1;i+) /*构造哈夫曼树*/min1=min2=32767; /*lnode和 rnode为最小权重的两个结点位置*/lnode=rnode=-1;for (k=0;k=i-1;k+)if (htk.parent=-1) /*只在尚未构造二叉树的结点中查找*/ if (htk.weightmin1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k; else if (htk.weightmin2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;
14、hti.weight=htlnode.weight+htrnode.weight; hti.lchild=lnode;hti.rchild=rnode; void CreateHCode(HTNode ht,HCode hcd,int n)int i,f,c;HCode hc;for (i=0;in;i+) /*根据哈夫曼树求哈夫曼编码*/ hc.start=n;c=i;f=hti.parent;11while (f!=-1) /*循序直到树根结点*/ if (htf.lchild=c) /处理左孩子结点hc.cdhc.start-=0;else /*处理右孩子结点*/hc.cdhc.star
15、t-=1;c=f;f=htf.parent; hc.start+; /*start指向哈夫曼编码最开始字符*/hcdi=hc void DispHCode(HTNode ht,HCode hcd,int n) int i,k;int sum=0,m=0,j;printf( 输出哈夫曼编码:n); /*输出哈夫曼编码*/for (i=0;in;i+)j=0;printf( %s:t,hti.data);for (k=hcdi.start;k=n;k+)printf(%c,hcdi.cdk);j+;m+=hti.weight;sum+=hti.weight*j;printf(n);printf(n 平均长度=%gn,1.0*sum/m);void main()int n=15,i;char *s
