算法设计及分析

《算法设计及分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一填空题1.一个计算机算法的指令序列需要满足性质的是输入、输出、确定性、有限性。输入、输出、确定性、有限性2.的渐近表达式是O(n2)3.下面程序段的时间复杂度是O(n2)for(i=0;i

2、k=1;k<=n;k++)x+=a[i][k]*b[k][j];c[i][j]=x;}}}该算法的时间复杂度为O(n3)5．通常用来表示时间算法的有以下六种多项式：按从小到大的顺序排列6．快速排序算法是基于分治策略的一个算法。其基本思想是，对于输入的子数组a[p:r],按以下3个步骤进行排序：分解、递归求解、合并。7.合并排序算法的基本思想是将待排序的元素分成大小大致相等的2个子集合，分别对两个子集合排序，最终将排好序的子集合合并成为所要求的集合。7.最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优

3、解。8．贪心算法和动态规划算法都要求问题具有最优子结构性质。这是两类算法的一个共同点。9.动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做出一次贪心选择就将所求问题简化为规模更小的子问题。计算机的资源，最重要的是时间和空间资源。因而，算法的复杂性有时间、空间之分。10.算法的时间复杂性函数用T(n)表示，它是的函数。11.f(n)=O(g(n))表示当且仅当存在正的常数C和N0，使得对于所有的n>=No，有f(n)

4、)=C0，为常数：f(n)=O(1)f(n)=3n+2:f(n)=O(n)f(n)=6*2n+n:f(n)=O(2n)13.贪心方法是一种求最优解方法。它首先根据题意，选取一种度量标准。然后按这种度量标准对这N个输入排序，并按序一次选入一个量。如果这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。选择能产生问题最优解的度量标准是使用贪心法设计求解的核心问题。14.最优子结构性质：。15.子问题重叠性质：。16.背包问题可以获得最优解的输入排序是按价值密度排序。二选择题1．直接或间接的调用自身的算法称为A。A递归算法B贪心算法C

5、迭代算法D动态规划算法2．阶乘函数用递归定义Publicstaticintfactorial(intn){if(n==0)return1;returnB;}An*factorial(n)Bn*factorial(n-1)Cn*factorial(n-2)Dn*factorial(n+1)3．与分治法不同的是，适合于用动态规划求解的问题，DA经分解得到子问题往往是任意的B经分解得到子问题往往是互相独立的C经分解得到子问题往往是互相交叉的D经分解得到子问题往往不是互相独立的4．合并排序法的基本思想是：将待排序元素分成大小大致相同的C个子集合，

6、分别对每个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。A4B3C2D55．二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较：如果（C），则只要在数组a的右半部继续搜索x。Ax＜a[n/2]Bx=a[n/2]Cx>a[n/2]Dx>=a[n/2]6．当问题的规模n趋向无穷大时，B的数量级(阶)称为算法的渐进时间复杂度。A空间复杂度B时间复杂度C冗余度D迭代次数7．实现快速排序算法如下：privatestaticvoidquickSort(intp,intr){ if（p

7、{    intq=partition(p,r);//以确定的基准元素a[p]对//子数组a[p;r]进行划分 A//对左半段排序    quickSort(q+1,r);//对右半段排序   }}AquickSort(p,q-1)BquickSort(p+1,q-1)CquickSort(p,q+1)DquickSort(p,q-2)8．计算机算法指的是CA.计算方法B.排序方法C.解决问题的方法和过程D.调度方法9．在动态规划算法中，问题的最优子结构性质使我们能够以D的方式递归地从子问题的最优解逐步构造出整个问题的最优解。A自左向右B

8、自右向左C自上向下D自底向上10．用贪心法解最优装载问题的时候，我们采用的贪心选择的策略是CA重量大者先装B总价值大的先装C重量轻者先装D单位价值大的先装三、判断题1．从分治法的一般设计模式可