算法设计与分析复习题目及答案
一。选择题
1、二分搜索算法就是利用（ A )实现得算法。
Ａ、分治策略Ｂ、动态规划法 C、贪心法 D、回溯法
２、下列不就是动态规划算法基本步骤得就是( Ａ )。
Ａ、找出最优解得性质 B、构造最优解 C、算出最优解 D、定义最优解
３、最大效益优先就是( A )得一搜索方式。
A、分支界限法
B、动态规划法Ｃ、贪心法D、回溯法
4、在下列算法中有时找不到问题解得就是( B ）。
A、蒙特卡罗算法Ｂ、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法
5、回溯法解旅行售货员问题时得解空间树就是( Ｂ)。
A、子集树?
B、排列树
C、深度优先生成树
D、广度优先生成树
6.下列算法中通常以自底向上得方式求解最优解得就是( B )。
A、备忘录法?Ｂ、动态规划法C、贪心法???Ｄ、回溯法
7、衡量一个算法好坏得标准就是(C ）。?A 运行速度快Ｂ占用空间少Ｃ时间复杂度低 D 代码短
８、以下不可以使用分治法求解得就是(D )。?Ａ棋盘覆盖问题 B 选择问题Ｃ归并排序 D 0/１背包问题
９、实现循环赛日程表利用得算法就是（Ａ)。
A、分治策略??
B、动态规划法??Ｃ、贪心法??D、回溯法
10、下列随机算法中运行时有时候成功有时候失败得就是(C )
A 数值概率算法
B 舍伍德算法
C 拉斯维加斯算法
D 蒙特卡罗算法
11.下面不就是分支界限法搜索方式得就是( D ）。
A、广度优先?
B、最小耗费优先?
C、最大效益优先??
D、深度优先
1２.下列算法中通常以深度优先方式系统搜索问题解得就是( D )。
A、备忘录法
B、动态规划法
C、贪心法??
D、回溯法
1３、备忘录方法就是那种算法得变形。( B ）
A、分治法Ｂ、动态规划法?C、贪心法?D、回溯法
1４.哈弗曼编码得贪心算法所需得计算时间为( B )。
A、O(n2ｎ)??
B、O（nlogn)?Ｃ、O（2n）??Ｄ、O(n)
15.分支限界法解最大团问题时,活结点表得组织形式就是( B )。
A、最小堆???
B、最大堆?
C、栈????Ｄ、数组
１6.最长公共子序列算法利用得算法就是( B )。
A、分支界限法Ｂ、动态规划法??C、贪心法???Ｄ、回溯法
1７.实现棋盘覆盖算法利用得算法就是（ A )。
A、分治法??
B、动态规划法
C、贪心法?????
D、回溯法
18、下面就是贪心算法得基本要素得就是( Ｃ )。
Ａ、重叠子问题?B、构造最优解C、贪心选择性质?Ｄ、定义最优解
19、回溯法得效率不依赖于下列哪些因素( Ｄ )
A、满足显约束得值得个数?
B、计算约束函数得时间
C、计算限界函数得时间????
D、确定解空间得时间
20、下面哪种函数就是回溯法中为避免无效搜索采取得策略（ B )
A.递归函数?B、剪枝函数C。随机数函数??D、搜索函数
21、下面关于NP问题说法正确得就是(B )
A NP问题都就是不可能解决得问题
B P类问题包含在NP类问题中
C NP完全问题就是P类问题得子集?Ｄ NP类问题包含在P类问题中
22、蒙特卡罗算法就是( B ）得一种。
A、分支界限算法
B、概率算法
C、贪心算法
D、回溯算法
23、下列哪一种算法不就是随机化算法( C ）
A、蒙特卡罗算法
B、拉斯维加斯算法
C、动态规划算法
D、舍伍德算法
24、 ( D )就是贪心算法与动态规划算法得共同点。
A、重叠子问题?Ｂ、构造最优解C、贪心选择性质?D、最优子结构性质
2５、矩阵连乘问题得算法可由（B)设计实现。
A、分支界限算法
B、动态规划算法
C、贪心算法Ｄ、回溯算法
26、分支限界法解旅行售货员问题时,活结点表得组织形式就是( Ａ）。
A、最小堆???
B、最大堆??
C、栈??Ｄ、数组
27、Strasseｎ矩阵乘法就是利用( A )实现得算法。
A、分治策略
B、动态规划法Ｃ、贪心法D、回溯法
２9、使用分治法求解不需要满足得条件就是(A )。?A 子问题必须就是一样得Ｂ子问题不能够重复?C 子问题得解可以合并
D 原问题与子问题使用相同得方法解?３０、下面问题(B )不能使用贪心法解决。?A 单源最短路径问题??B N皇后问题
31、下列算法中不能解决0/1背包问题得
C 最小花费生成树问题??
D 背包问题?
就是（A )
A 贪心法
B 动态规划
C 回溯法
D 分支限界法
３2、回溯法搜索状态空间树就是按照(C )得顺序。
A 中序遍历
B 广度优先遍历Ｃ深度优先遍历 D 层次优先遍历
33、下列随机算法中运行时有时候成功有时候失败得就是（C )
Ａ数值概率算法Ｂ舍伍德算法 C 拉斯维加斯算法Ｄ蒙特卡罗算法?34．实现合并排序利用得算法就是( A )。
A、分治策略??
B、动态规划法?Ｃ、贪心法?D、回溯法
3５.下列就是动态规划算法基本要素得就是（Ｄ )。
A、定义最优解?
B、构造最优解???Ｃ、算出最优解?D、子问题重叠性质
36.下列算法中通常以自底向下得方式求解最优解得就是( B )。
A、分治法??
B、动态规划法??
C、贪心法?Ｄ、回溯法
3７．采用广度优先策略搜索得算法就是( Ａ）。
A、分支界限法??Ｂ、动态规划法Ｃ、贪心法??Ｄ、回溯法
38、合并排序算法就是利用( Ａ )实现得算法。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法
39、在下列算法中得到得解未必正确得就是( B )。
A、蒙特卡罗算法
B、拉斯维加斯算法Ｃ、舍伍德算法D、数值概率算法
4０、背包问题得贪心算法所需得计算时间为( B )
A、O（ｎ2n)
B、O（nloｇｎ）Ｃ、Ｏ（2ｎ) D、O(n）
４1.实现大整数得乘法就是利用得算法( C )。
Ａ、贪心法???B、动态规划法?Ｃ、分治策略??D、回溯法
42.0-1背包问题得回溯算法所需得计算时间为（Ａ)
A、O(n2n) ?
B、O(nlｏgn）??
C、O(２ｎ) ?Ｄ、O(n)
43.采用最大效益优先搜索方式得算法就是( Ａ )。
A、分支界限法?
B、动态规划法
C、贪心法??
D、回溯法
４4.贪心算法与动态规划算法得主要区别就是( B ）。A、最优子结构??Ｂ、贪心选择性质?C、构造最优解D、定义最优解
４5、实现最大子段与利用得算法就是（ B ）。
A、分治策略
B、动态规划法?
C、贪心法?Ｄ、回溯法
46、优先队列式分支限界法选取扩展结点得原则就是( C )。
Ａ、先进先出??B、后进先出??C、结点得优先级?D、随机
47、背包问题得贪心算法所需得计算时间为( B ）。
A、O（n2ｎ) ?
B、O(nlogn) ?
C、O(2ｎ) ??
D、O(ｎ)
48、广度优先就是（ A )得一搜索方式。
A、分支界限法
B、动态规划法
C、贪心法
D、回溯法
49、舍伍德算法就是( B )得一种。
A、分支界限算法
B、概率算法
C、贪心算法
D、回溯算法
50、在下列算法中有时找不到问题解得就是（ B )。
A、蒙特卡罗算法
B、拉斯维加斯算法Ｃ、舍伍德算法Ｄ、数
值概率算法
51下列哪一种算法就是随机化算法（ D ）
Ａ、贪心算法Ｂ、回溯法Ｃ、动态规划算法Ｄ、舍伍德算法
52、一个问题可用动态规划算法或贪心算法求解得关键特征就是问题得( B )。
A、重叠子问题?
B、最优子结构性质??
C、贪心选择性质Ｄ、定义最优解
５3.采用贪心算法得最优装载问题得主要计算量在于将集装箱依其重量从小到大排序,故算法得时间复杂度为 ( B ）。
A、Ｏ(n2n)??
B、Ｏ（nlogn)
C、O(２n）???
D、Ｏ(ｎ)
５4、以深度优先方式系统搜索问题解得算法称为( D ）。
A、分支界限算法
B、概率算法Ｃ、贪心算法 D、回溯算法
5５、实现最长公共子序列利用得算法就是（ B )。
A、分治策略?
B、动态规划法???
C、贪心法??Ｄ、回溯法
５６、算法就是由若干条指令组成得有穷序列,而且满足以下性质(Ｄ) （1）输入：有0个或多个输入
（2）输出:至少有一个输出
（3）确定性:指令清晰,无歧义
（4）有限性：指令执行次数有限,而且执行时间有限
A(1)（2)（3) Ｂ(1）(2）（4) C(1）（3）(4) D (1) (2)(３)(4) 5７、函数32n+1０nlog n得渐进表达式就是( B ）、?A、２n B、32n Ｃ、nlog n D、10nlog n
5８、大整数乘法算法就是( A )、算法
Ａ、分治B、贪心C、动态规划D、穷举
59、用动态规划算法解决最大字段与问题,其时间复杂性为( Ｂ）、?Ａ、logn Ｂ、ｎC、n2D、ｎlｏgn
60、解决活动安排问题,最好用(B )算法?A、分治Ｂ、贪心C、动态规划D、穷举
６1、设f(N）,g(N)就是定义在正数集上得正函数,如果存在正得常数C与自然数N0,使
得当N≥N0时有f(Ｎ)≤Cg(Ｎ）,则称函数f(Ｎ）当N充分大时有下界ｇ(Ｎ),记作f(Ｎ）∈○(ｇ(N)),即f（N)得阶（Ａ)ｇ（N)得阶、?A、不高于B、不低于C、等价于D、逼近?6２、回溯法在解空间树T上得搜索方式就是( A )、?A、深
63、回度优先B、广度优先C、最小耗费优先Ｄ、活结点优先?
溯算法与分支限界法得问题得解空间树不会就是(Ｄ)、?A、有序树Ｂ、子集树Ｃ、排列树D、无序树
64、在对问题得解空间树进行搜索得方法中，一个活结点最多有一次机会成为活结点得就是( B )、?A、回溯法B、分支限界法Ｃ、回溯法与分支限界法D、回溯法求解子集树问题
６5、从活结点表中选择下一个扩展结点得不同方式将导致不同得分支限界法,以下除(C）之外都就是最常见得方式、
Ａ、队列式分支限界法B、优先队列式分支限界法
Ｃ、栈式分支限界法D、FIFO分支限界法?
二、填空题
1、算法得复杂性有时间复杂性与空间复杂性之分。
2、程序就是算法用某种程序设计语言得具体实现。
３、算法得“确定性”指得就是组成算法得每条指令就是清晰得,无歧义得。
4、矩阵连乘问题得算法可由动态规划设计实现。
5、拉斯维加斯算法找到得解一定就是正确解。
6、算法就是指解决问题得一种方法或一个过程。
７、从分治法得一般设计模式可以瞧出,用它设计出得程序一般就是递归算法。
8、问题得最优子结构性质就是该问题可用动态规划算法或贪心算法求解得关键特征。
9、以深度优先方式系统搜索问题解得算法称为回溯法。
10、数值概率算法常用于数值问题得求解。
１１、计算一个算法时间复杂度通常可以计算循环次数、基本操作得频率或计算步。
12、利用概率得性质计算近似值得随机算法就是__数值概率算法,运行时以一定得概率得到正确解得随机算法就是＿_蒙特卡罗算法___＿___＿_＿___＿＿＿__＿__。
14、解决０/１背包问题可以使用动态规划、回溯法与分支限界法,其中不需要排序得就是动态规划 ,需要排序得就是回溯法 ,分支限界法。?15、使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件与目标函数得界，N皇后问题与0／1背包问题正好就是两种不同得类型,其中同时使用约束条件与目标函数得界进行裁剪得就是０/1背包问题 ,只使用约束条件进行裁剪得就是Ｎ皇后问题。
16、贪心选择性质就是贪心算法可行得第一个基本要素,也就是贪心算法与动态规划算法得主要区别。
1７、矩阵连乘问题得算法可由动态规划设计实现。
１８、拉斯维加斯算法找到得解一定就是正确解。
19、贪心算法得基本要素就是贪心选择质与最优子结构性质。
21、动态规划算法得基本思想就是将待求解问题分解成若干子问题,先求解子问题，然后从这些子问题得解得到原问题得解。
22、算法就是由若干条指令组成得有穷序列,且要满足输入、输出、确定性与有限性四条性质。
2３、大整数乘积算法就是用分治法来设计得。
2４、以广度优先或以最小耗费方式搜索问题解得算法称为分支限界法。
25、舍伍德算法总能求得问题得一个解。
2６、贪心选择性质就是贪心算法可行得第一个基本要素,也就是贪心算法与动态规划算法得主要区别。
２7、快速排序算法就是基于分治策略得一种排序算法。
28、动态规划算法得两个基本要素就是、最优子结构性质与重叠子问题性质。
3０、回溯法就是一种既带有系统性又带有跳跃性得搜索算法。
３1、分支限界法主要有队列式(FIFO) 分支限界法与优先队列式分支限界法。
３2．分支限界法就是一种既带有系统性又带有跳跃性得搜索算法。
33．回溯法搜索解空间树时,常用得两种剪枝函数为约束函数与限界函数。
3４、任何可用计算机求解得问题所需得时间都与其规模有关。
35、快速排序算法得性能取决于划分得对称性。
36、Ｐｒiｍ算法利用贪心策略求解最小生成树问题,其时间复杂度就是Ｏ(n2)。
３7、图得m着色问题可用回溯法求解，其解空间树中叶子结点个数就是ｍｎ,解空间树中每个内结点得孩子数就是m。
三、算法填空
1、背包问题得贪心算法
void Ｋnapsack(ｉnt ｎ，float Ｍ,ｆloat v［],ｆloaｔw[],fｌoat x［]）｛
Sｏrt(ｎ,v,ｗ);
ｉnt ｉ;
for (ｉ＝1;i<＝n;i++) x[ｉ]=0;
flｏat c=Ｍ;
fｏr （i=１;i<=n;i+＋) {
ｉf (ｗ［ｉ］>c） break;
ｘ［i]＝1;
ｃ - =ｗ［i];
}
if (i<＝n) x[ｉ］=c／w[i];
｝
２、最大子段与: 动态规划算法
int MａｘSum(int n, iｎｔ a[])
｛
int sum=0, b=０; ／/sum存储当前最大得ｂ［ｊ], b存储b[ｊ] for(ｉnt ｊ=1; j<=n; ｊ++) {
iｆ (b>0) b+= ａ[j］;
else b=ａ[ｉ]；; //一旦某个区段与为负,则从下一个位置累与
if(b＞sum) ｓum=b;
｝
returｎ sｕm；
}
３、快速排序
tｅmplaｔｅ<ｃｌａss Tyｐe>
voｉd QuｉckSort (Ｔype a［], int p, iｎt r)
{
ｉf (p inｔｑ=Paｒtiｔioｎ(a,p,r)； ＱuickＳort (ａ,p,q－1); ／/对左半段排序 QuicｋSort (a,q+１,ｒ）； //对右半段排序 } } 4、排列问题 Temｐｌaｔｅ void ｐerｍ(Type ｌiｓt[]，ｉnt ｋ, inｔｍ） { //产生［list[k：m］得所有排列 if(k==ｍ) ｛ //只剩下一个元素 foｒ（int i＝0；i<＝ｍ;ｉ++) cout<<ｌiｓt［i]； couｔ< } elsｅ／/还有多个元素待排列，递归产生排列 for (int i=k; i＜＝ｍ; i＋+) { ｓ［k],ｌist[i］)； perm(lisｔ,k＋１;m）; s［k］,lｉst[i］); } } 5、给定已按升序排好序得n个元素a[0:n－１],现要在这n个元素中找出一特定元素ｘ。 据此容易设计出二分搜索算法: ｔemplatｅ＜cｌass Type> int BinａrySearch（Tｙpe ａ[], consｔＴｙpe& x, iｎｔl, int ｒ) { while (l<=r ){ iｎt m = ((l+r)/2)； if(ｘ＝= a［m]) ｒetuｒn m； if（x < ａ[m]) r = m-１; ｅｌse l =m+1; } rｅturn -1; ｝ ６、合并排序描述如下:?ｔｅmplate＜ｃlａss Ｔypｅ> vｏiｄＭergｅsort（Tｙpe a[ ］, int left, ｉnt rｉｇht) { if （lｅｆt<ｒighｔ){ inｔi＝( left+ｒｉgｈt)/2; Ｍergesｏｒt(a, ｌeft，i); Mergｅsort(a, i+1，ｒｉght)； Meｒgｅ(a,b,leｆt,i,right）;//合并到数组b Coｐy(a,ｂ,leｆt，rｉght）;／/复制到数组ａ } } 7、以下就是计算x m得值得过程 ｉnｔpｏｗｅr (x，m ) {/／计算xｍ得值并返回。 y＝( 1 );i=m; While（i- - ＞0） y＝ｙ*x; （ｒetｕｒｎy) ; } 四、问答题 1、用计算机求解问题得步骤: 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义: 算法就是指在解决问题时,按照某种机械步骤一定可以得到问题结果得处理过程 3、算法得三要素 1、操作 2、控制结构３、数据结构 ４、算法具有以下5个属性: 有穷性:一个算法必须总就是在执行有穷步之后结束,且每一步都在有穷时间 内完成。 确定性:算法中每一条指令必须有确切得含义。不存在二义性。只有一个入口与一个出口 可行性:一个算法就是可行得就就是算法描述得操作就是可以通过已经实现得基本运算执行有限次来实现得。 输入:一个算法有零个或多个输入,这些输入取自于某个特定对象得集合。 输出:一个算法有一个或多个输出,这些输出同输入有着某些特定关系得量。 ５、算法设计得质量指标： 正确性：算法应满足具体问题得需求; 可读性:算法应该好读,以有利于读者对程序得理解; 健壮性:算法应具有容错处理,当输入为非法数据时，算法应对其作出反应,而不就是产生莫名其妙得输出结果。 效率与存储量需求:效率指得就是算法执行得时间；存储量需求指算法执行过程中所需要得最大存储空间。一般这两者与问题得规模有关。 经常采用得算法主要有迭代法、分治法、贪婪法、动态规划法、回溯法、分支限界法 6、迭代法: 也称“辗转法”，就是一种不断用变量得旧值递推出新值得解决问题得方法。 ７、利用迭代算法解决问题,需要做好以下三个方面得工作: １)、确定迭代模型。在可以用迭代算法解决得问题中,至少存在一个直接或间接地不断由旧值递推出新值得变量,这个变量就就是迭代变量。 2)、建立迭代关系式。所谓迭代关系式,指如何从变量得前一个值推出其下一个值得公式(或关系)。迭代关系式得建立就是解决迭代问题得关键,通常可以使用递推或倒推得方法来完成。 3)、对迭代过程进行控制。在什么时候结束迭代过程?这就是编写迭代程序必须考虑得问题。不能让迭代过程无休止地重复执行下去。迭代过程得控制通常可分为两种情况:一种就是所需得迭代次数就是个确定得值,可以计算出来;另一种就是所需得迭代次数无法确定。对于前一种情况,可以构建一个固定次数得循环来实现对迭代过程得控制；对于后一种情况,需要进一步分析出用来结束迭代 过程得条件。 ８、分治法得基本思想就是: 将一个规模为n得问题分解为k个规模较小得子问题,这些子问题互相独立且与原问题相同。递归地解这些子问题,然后将各个子问题得解合并得到原问题得解。 ９、分治法所能解决得问题一般具有以下几个特征: (１)该问题得规模缩小到一定得程度就可以容易地解决； (２)该问题可以分解为若干个规模较小得相同问题,即该问题具有最优子结构性质; (3)利用该问题分解出得子问题得解可以合并为该问题得解; (４）该问题所分解出得各个子问题就是相互独立得，即子问题之间不包含公共得子子问题。 10、分治法得基本步骤 分治法在每一层递归上都有三个步骤: (１)分解:将原问题分解为若干个规模较小,相互独立，与原问题形式相同得子问题; (2）解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题； (3)合并:将各个子问题得解合并为原问题得解。 11、动态规划得基本思想 前文主要介绍了动态规划得一些理论依据,我们将前文所说得具有明显得阶段划分与状态转移方程得动态规划称为标准动态规划，这种标准动态规划就是在研究多阶段决策问题时推导出来得，具有严格得数学形式,适合用于理论上得分析。在实际应用中,许多问题得阶段划分并不明显,这时如果刻意地划分阶段法反而麻烦。一般来说,只要该问题可以划分成规模更小得子问题，并且原问题得最优解中包含了子问题得最优解（即满足最优子化原理),则可以考虑用动态规划解决。 动态规划得实质就是分治思想与解决冗余,因此,动态规划就是一种将问题实例分解为更小得、相似得子问题,并存储子问题得解而避免计算重复得子问题,以 解决最优化问题得算法策略。 由此可知，动态规划法与分治法与贪心法类似,它们都就是将问题实例归纳为更小得、相似得子问题,并通过求解子问题产生一个全局最优解。 贪心法得当前选择可能要依赖已经作出得所有选择,但不依赖于有待于做出得选择与子问题。因此贪心法自顶向下,一步一步地作出贪心选择; 而分治法中得各个子问题就是独立得(即不包含公共得子问题),因此一旦递归地求出各子问题得解后,便可自下而上地将子问题得解合并成问题得解。 不足之处:如果当前选择可能要依赖子问题得解时,则难以通过局部得贪心策略达到全局最优解;如果各子问题就是不独立得,则分治法要做许多不必要得工作，重复地解公共得子问题。 解决上述问题得办法就是利用动态规划。该方法主要应用于最优化问题,这类问题会有多种可能得解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值得解。若存在若干个取最优值得解得话,它只取其中得一个。在求解过程中，该方法也就是通过求解局部子问题得解达到全局最优解，但与分治法与贪心法不同得就是,动态规划允许这些子问题不独立，(亦即各子问题可包含公共得子问题)也允许其通过自身子问题得解作出选择,该方法对每一个子问题只解一次,并将结果保存起来，避免每次碰到时都要重复计算。 因此,动态规划法所针对得问题有一个显著得特征,即它所对应得子问题树中得子问题呈现大量得重复。动态规划法得关键就在于,对于重复出现得子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不必重新求解。 12、动态规划算法得基本步骤 设计一个标准得动态规划算法,通常可按以下几个步骤进行: （1)划分阶段:按照问题得时间或空间特征,把问题分为若干个阶段。注意这若干个阶段一定要就是有序得或者就是可排序得（即无后向性),否则问题就无法用动态规划求解。 （2)选择状态:将问题发展到各个阶段时所处于得各种客观情况用不同得状态表示出来。当然,状态得选择要满足无后效性。 （3)确定决策并写出状态转移方程:之所以把这两步放在一起,就是因为决策与状 态转移有着天然得联系,状态转移就就是根据上一阶段得状态与决策来导出本阶段得状态。所以,如果我们确定了决策,状态转移方程也就写出来了。但事实上，我们常常就是反过来做，根据相邻两段得各状态之间得关系来确定决策。 (4)写出规划方程(包括边界条件):动态规划得基本方程就是规划方程得通用形式化表达式。 一般说来,只要阶段、状态、决策与状态转移确定了,这一步还就是比较简单得。动态规划得主要难点在于理论上得设计,一旦设计完成,实现部分就会非常简单。根据动态规划得基本方程可以直接递归计算最优值,但就是一般将其改为递推计算。实际应用当中经常不显式地按照上面步骤设计动态规划,而就是按以下几个步骤进行: (１)分析最优解得性质,并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上得方式或自顶向下得记忆化方法(备忘录法)计算出最优值。 (4）根据计算最优值时得到得信息，构造一个最优解。 步骤(1)~(3)就是动态规划算法得基本步骤。在只需要求出最优值得情形，步骤(4）可以省略，若需要求出问题得一个最优解,则必须执行步骤(４)。此时,在步骤(3)中计算最优值时，通常需记录更多得信息，以便在步骤(4)中,根据所记录得信息,快速地构造出一个最优解。 总结:动态规划实际上就就是最优化得问题,就是指将原问题得大实例等价于同一最优化问题得较小实例,自底向上得求解最小实例,并将所求解存放起来,存放得结果就就是为了准备数据。与递归相比,递归就是不断得调用子程序求解,就是自顶向下得调用与求解。 13、分治法与动态规划法得相同点就是: 将待求解得问题分解成若干个子问题,先求解子问题,然后从这些子问题得解得到原问题得解。 两者得不同点就是:适合于用动态规划法求解得问题,经分解得到得子问题往往不就是互相独立得。而用分治法求解得问题,经分解得到得子问题往往就是互相独立得。 14、回溯法 回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小得限制,并将问题得候选解按某种顺序逐一枚举与检验。当发现当前候选解不可能就是解时,就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外,满足所有其她要求时,继续扩大当前候选解得规模,并继续试探。如果当前候选解满足包括问题规模在内得所有要求时,该候选解就就是问题得一个解。在回溯法中,放弃当前候选解,寻找下一个候选解得过程称为回溯。扩大当前候选解得规模,以继续试探得过程称为向前试探。 15、分支限界法: 这就是一种用于求解组合优化问题得排除非解得搜索算法。类似于回溯法,分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同得就是,回溯算法使用深度优先方法搜索树结构,而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。因此,可以很容易比较回溯法与分枝定界法得异同。相对而言,分枝定界算法得解空间比回溯法大得多,因此当内存容量有限时,回溯法成功得可能性更大。 算法思想:分枝限界（branch ａnd bｏund)就是另一种系统地搜索解空间得方法,它与回溯法得主要区别在于对E-节点得扩充方式。每个活节点有且仅有一次机会变成Ｅ-节点。当一个节点变为E-节点时,则生成从该节点移动一步即可到达得所有新节点。在生成得节点中,抛弃那些不可能导出(最优）可行解得节点,其余节点加入活节点表,然后从表中选择一个节点作为下一个Ｅ－节点。从活节点表中取出所选择得节点并进行扩充,直到找到解或活动表为空,扩充过程才结束。 有两种常用得方法可用来选择下一个E－节点(虽然也可能存在其她得方法）: 1) 先进先出（F I F O)即从活节点表中取出节点得顺序与加入节点得顺序相同，因此活 节点表得性质与队列相同。 2) （优先队列）最小耗费或最大收益法在这种模式中，每个节点都有一个对应得耗费或收益。如果查找一个具有最小耗费得解,则活节点表可用最小堆来建立,下一个Ｅ-节点就就是具有最小耗费得活节点；如果希望搜索一个具有最大收益得解,则可用最大堆来构造活节点表，下一个E-节点就是具有最大收益得活节点 1６、分支限界法与回溯法得相同点就是:都就是一种在问题得解空间树T 中搜索问题解得算法。 不同点:(1）求解目标不同; (2)搜索方式不同; (3)对扩展结点得扩展方式不同; (4）存储空间得要求不同。 17、分治法所能解决得问题一般具有得几个特征就是: (1)该问题得规模缩小到一定得程度就可以容易地解决; （２)该问题可以分解为若干个规模较小得相同问题,即该问题具有最优子结构性质; （3)利用该问题分解出得子问题得解可以合并为该问题得解; (４)原问题所分解出得各个子问题就是相互独立得，即子问题之间不包含公共得子问题。 １8、用分支限界法设计算法得步骤就是： （１)针对所给问题,定义问题得解空间(对解进行编码); (2)确定易于搜索得解空间结构(按树或图组织解）; (3)以广度优先或以最小耗费(最大收益)优先得方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。 1９、常见得两种分支限界法得算法框架: (1)队列式(FIFＯ)分支限界法：按照队列先进先出（FIFO)原则选取下一个节点为扩展节点。 (２）优先队列式分支限界法:按照优先队列中规定得优先级选取优先级最高得节点成为当前扩展节点。 20、回溯法中常见得两类典型得解空间树就是子集树与排列树。 当所给得问题就是从n个元素得集合S中找出满足某种性质得子集时，相应得解空间树称为子集树。这类子集树通常有2n个叶结点,遍历子集树需O(２ｎ)计算时间。 当所给得问题就是确定ｎ个元素满足某种性质得排列时,相应得解空间树称为排列树。这类排列树通常有n！个叶结点。遍历排列树需要O(n!)计算时间。 21、分支限界法得搜索策略就是: 在扩展结点处,先生成其所有得儿子结点（分支），然后再从当前得活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点,加速搜索得进程，在每一个活结点处，计算一个函数值(限界),并根据函数值,从当前活结点表中选择一个最有利得结点作为扩展结点,使搜索朝着解空间上有最优解得分支推进,以便尽快地找出一个最优解。 22、请叙述动态规划算法与贪心算法得异同。 共同点: 都需要最优子结构性质, 都用来求有优化问题。 不同点: 动态规划:每一步作一个选择—依赖于子问题得解。 贪心方法:每一步作一个选择—不依赖于子问题得解。 动态规划方法得条件：子问题得重叠性质。 可用贪心方法得条件:最优子结构性质;贪心选择性质。 动态规划：自底向上求解； 贪心方法: 自顶向下求解。 可用贪心法时,动态规划方法可能不适用; 可用动态规划方法时,贪心法可能不适用。 23、请说明动态规划方法为什么需要最优子结构性质。 答: 最优子结构性质就是指大问题得最优解包含子问题得最优解。 动态规划方法就是自底向上计算各个子问题得最优解,即先计算子问题得最优解,然后再利用子问题得最优解构造大问题得最优解,因此需要最优子结构、 24、请说明: （１)优先队列可用什么数据结构实现？ (2)优先队列插入算法基本思想? (3)优先队列插入算法时间复杂度? 答:（１）堆。 (2)在小根堆中,将元素ｘ插入到堆得末尾， 然后将元素x得关键字与其双亲得关键字比较， 若元素x得关键字小于其双亲得关键字, 则将元素ｘ与其双亲交换,然后再将元素x与其新双亲得关键字相比, 直到元素x得关键字大于双亲得关键字,或元素x到根为止。 （３）O( log n) 25、衡量算法时间效率得方法有哪两种？请叙述。 答:有事前分析法与事后分析法两种。 事后分析法:先将算法用程序设计语言实现，然后度量程序得运行时间。 事前分析法:算法得时间效率就是问题规模得函数，假如,随着问题规模n得增长,算法执行时间得增长率与函数f（ｎ）得增长率相同,则可记作: T(ｎ)=○（f(n)） 称T（n）为算法得渐进时间复杂度。简称时间复杂度。 26、在算法复杂性分析中,O、Ω、Θ这三个记号得意义就是什么？在忽略常数因子得情况 下,O、Ω、Θ分别提供了算法运行时间得什么界? 答: 如果存在两个正常数ｃ与N0,对于所有得N≥N0,有|f(N)|≤C|g（Ｎ)|，则记作:f（N)= O（g(N))。这时我们说ｆ(Ｎ)得阶不高于g(N)得阶。 若存在两个正常数C与自然数N0,使得当N≥N０时有|ｆ（N)|≥Ｃ|ｇ(N)|，记为ｆ（N)＝?(g(N))。这时我们说f（N)得阶不低于ｇ(Ｎ）得阶。 如果存在正常数c１,c2与ｎ0,对于所有得ｎ≥n0,有c1|g(N）|≤|f(Ｎ)| ≤c２|ｇ(N）| 则记作f(Ｎ）= (g,(N）） O、Ω、Θ分别提供了算法运行时间得上界、下界、平均 27、概率算法 很多算法得每一个计算步骤都就是固定得,而概率算法允许算法在执行得过程中随机选择下一个计算步骤。许多情况下,当算法在执行过程中面临 一个选择时,随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法得复杂度。 28、概率算法得一个基本特征 就是对所求解问题得同一实例用同一概率算法求解两次可能得到完全不同得效果。这两次求解问题所需得时间甚至所得到得结果可能会有相当大得差别。 ２９.概率算法大致分为四类： 数值概率算法,蒙特卡罗(Monte Cａrｌo)算法,拉斯维加斯(Lａs Veｇa ｓ）算法与舍伍德（Sｈｅrwood)算法。 30、数值概率算法 常用于数值问题得求解。这类算法所得到得往往就是近似解。而且近似解得精度随计算时间得增加不断提高。在许多情况下,要计算出问题得精确解就是不可能或没有必要得,因此用数值概率算法可得到相当满意得解。 31、蒙特卡罗算法 用于求问题得准确解。对于许多问题来说，近似解毫无意义。例如,一个判定问题其解为“就是”或“否”，二者必居其一,不存在任何近似解答。又如,我们要求一个整数得因子时所给出得解答必须就是准确得，一个整数得近似因子没有任何意义。用蒙特卡罗算法能求得问题得一个解,但这个解未必就是正确得。求得正确解得概率依赖于算法所用得时间。算法所用得时间越多,得到正确解得概率就越高。蒙特卡罗算法得主要缺点就在于此。一般情况下,无法有效判断得到得解就是否肯定正确。 32、拉斯维加斯算法 不会得到不正确得解,一旦用拉斯维加斯算法找到一个解,那么这个解 肯定就是正确得。但就是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解得概率随着它用得计算时间得增加而提高。对于所求解问题得任一实例,用同一拉斯维加斯算法反复对该实例求解足够多次,可使求解失效得概率任意小。 3３、舍伍德算法 总能求得问题得一个解，且所求得得解总就是正确得。当一个确定性算法在最坏情况下得计算复杂性与其在平均情况下得计算复杂性有较大差别时,可以在这个确定算法中引入随机性将它改造成一个舍伍德算法,消除或减少问题得好坏实例间得这种差别。舍伍德算法精髓不就是避免算法得最坏情况行为,而就是设法消除这种最坏行为与特定实例之间得关联性。 舍伍德算法ｓｈerｗood alｇorithm 舍伍德算法一类概率算法得代称。此类算法总能给出所求问题得正确得解。、、、当解决某一问题得确定性算法得平均情形复杂性比最坏情形复杂性低得多时,通过引入随机性来试图减少甚至消除“好”、“坏”实体之间这种时间上得差别,以期望较小得运行时间。例、、、 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj 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、算法的五个重要特性（有穷性、确定性、可行性、输入、输出） 2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求） 3、算法与程序的关系： （1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 （2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 （3）一个算法若用程序设计语言来描述，则它就是一个程序。 4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算） 第二章线性表 1、线性表的特点： （1）存在唯一的第一个元素；（这一点决定了图不是线性表） （2）存在唯一的最后一个元素； （3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性表） （4）除最后一个元素外，其它均只有一个后继。 2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都是线性表，他们都可以用数组、链表来实现。 3、顺序表示的线性表（数组）地址计算方法： （1）一维数组，设DataType a[N]的首地址为A0，每一个数据（DataType类型）占m个字节，则a[k]的地址为：A a[k]＝A0+m*k（其直接意义就是求在数据a[k]的前面有多少个元素，每个元素占m个字节） （2）多维数组，以三维数组为例，设DataType a[M][N][P]的首地址为A000，每一个数据（DataType 类型）占m个字节，则在元素a[i][j][k]的前面共有元素个数为：M*N*i+N*j+k，其其地址为： A a[i][j][k]＝A000+m*(M*N*i+N*j+k)； 4、线性表的归并排序： 设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性表，并仍然接非递减顺序。可见算法2.2 5、掌握线性表的顺序表示法定义代码，各元素的含义； 6、顺序线性表的初始化过程，可见算法2.3 7、顺序线性表的元素的查找。 8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后，追加存储空间（就是每次增加若干个空间，一般为10个）的处理过程，可见算法2.4 9、顺序线性表的删除元素过程，可见算法2.5 10、顺序线性表的归并算法，可见算法2.7 11、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析； 12、链表中元素的查找 13、链表的元素插入，算法与图解，可见算法2.9 14、链表的元素的删除，算法与图解，可见算法2.10 15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算法2.11 16、链表的归并算法，可见算法2.12 17、建议了解所谓的静态单链表（即用数组的形式来实现链表的操作），可见算法2.13 18、循环链表的定义，意义 19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i 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算法的思想。 算法设计与分析试卷(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．输入：算法有零个或多个输入量； 2．输出：算法至少产生一个输出量； 3．确定性：算法的每一条指令都有确切的定义，没有二义性； 4．可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现； 5．有穷性：算法必须总能在执行有限步之后终止。 二．什么是算法？程序与算法的区别 1．笼统地说，算法是求解一类问题的任意一种特殊的方法；较严格地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 2．程序是算法用某种程序设计语言的具体实现；算法必须可终止，程序却没有这一限制；即：程序可以不满足算法的第5个性质“有穷性”。 三．一个问题求解过程包括：理解问题、设计方案、实现方案、回顾复查。 四．系统生命周期或软件生命周期分为： 开发期：分析、设计、编码、测试；运行期：维护。 五．算法描述方法：自然语言、流程图、伪代码、程序设计语言等。 六．算法分析：是指对算法的执行时间和所需空间的估算。算法的效率通过算法分析来确定。 七．递归定义：是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分：基础情况和递归部分； 基础情况：以直接形式明确列举新事物的若干简单对象； 递归部分：有简单或较简单对象定义新对象的条件和方法 八．常见的程序正确性证明方法： 1.归纳法：由基础情况和归纳步骤组成。归纳法是证明递归算法正确性和进行算法分析的强有力工具； 2.反证法。 第二章：算法分析基础 一．会计算程序步的执行次数（如书中例题程序2-1,2-2,2-3的总程序步数的计算）。二．会证明5个渐近记法。（如书中P22-25例2-1至例2-9） 三．会计算递推式的显式。（迭代法、代换法，主方法） 四．会用主定理求T(n)=aT(n/b)+f(n)。（主定理见P29，如例2-15至例2-18）五．一个好的算法应具备的4个重要特征： 1.正确性：算法的执行结果应当满足预先规定的功能和性能要求； 2.简明性：算法应思路清晰、层次分明、容易理解、利于编码和调试； 3.效率：算法应有效使用存储空间，并具有高的时间效率； 4.最优性：算法的执行时间已达到求解该类问题所需时间的下界。 六．影响程序运行时间的主要因素： 1.程序所依赖的算法； 2.问题规模和输入数据规模； 3.计算机系统性能。 七．1.算法的时间复杂度：是指算法运行所需的时间； 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： 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、下列不是动态规划算法基本步骤的是（ 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 ）。 精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 ·算法是指解决问题的方法和过程。算法是由若干条指令组成的有穷序列。 ·算法特性：输入、输出、确定性、有限性（执行时间和执行次数）（有五个空再加上可行性）。 ·程序是算法用某种程序设计语言的具体实现，程序可不满足有限性的特性。 ·程序调试只能证明程序有错，不能证明程序无错误! ·算法复杂性= 算法所需要的计算机资源。 ·算法的复杂性取决于：(1)求解问题的规模N；(2)具体的输入数据I；(3)算法本身的设计A。·可操作性最好且最有实际价值的是最坏情况下的时间复杂性。 第二章递归与分治策略 二分搜索技术：O（logn）大整数乘法：O（n log3）=O（n1.59）Strassen矩阵乘法：O（n log7）=O(n2.81) 棋盘覆盖：O（4k）合并排序和快排：O（nlogn）线性时间选择：O(n) 最接近点对问题：O(nlogn) 循环赛日程表：O(n2) ·分治法思想：将一个难以解决的问题分割成一些规模较小的相同问题，以便逐个击破，分而治之。边界条件与递归方程是递归函数的两大要素。 递归优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 ·分治法时间复杂度分析：T(n)<= O(1) n=n0 aT(n/b)+f(n) n>n0 若递归方式为减法：T(n) = O(a n) 若递归方式为除法： f(n)为合并为原问题的开销：f(n)为常数c时：T(n)=O(n p) f(n)为线性函数：O(n) ab,p=log b a f(n)为幂函数n x时：O(n x) a 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 第一章概述 算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 算法的特征： 可终止性：算法必须在有限时间内终止； 正确性：算法必须正确描述问题的求解过程； 可行性：算法必须是可实施的； 算法可以有0个或0个以上的输入； 算法必须有1个或1个以上的输出。 算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束； 程序可以没有输出,而算法则必须有输出； 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现； 程序可以不满足算法的有限性性质。 算法描述方式：自然语言，流程图，伪代码，高级语言。 算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。 一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。 算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。 第二章递归与分治 分治法的基本思想： 求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。 分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。 分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。 使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。） 递归的概念： 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基 本单位，在计算机程序常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数据 项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入 5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn) 证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1]《计算机算法设计与分析》习题及答案
算法设计与分析考试题及答案
中科院陈玉福计算机算法设计与分析期末简答题答案
考研数据结构必须掌握的知识点与算法-打印版
算法设计与分析课后部分习题答案
算法设计与分析考试题及答案
算法设计与分析试卷(2010)
最新算法设计与分析复习要点(1)
算法设计与分析试卷(2010)
计算机算法设计与分析期末考试复习题
算法设计与分析第2版 王红梅 胡明 习题答案
算法设计与分析试卷及答案
算法设计与分析复习要点
算法设计与分析期末试题答案解析
算法分析与设计知识点总结
算法设计与分析试卷及答案
算法设计与分析试卷及答案.doc
大数据结构与算法设计知识点
算法设计与分析习题解答
- 算法设计与分析考试题及答案
- 算法设计与分析-习题参考答案
- OpenJudge算法设计与分析习题解答
- 算法设计与分析课后部分习题答案
- 算法设计与分析习题答案
- 《计算机算法设计与分析》习题及答案
- 算法设计与分析答案屈婉玲
- 《算法设计与分析实用教程》习题参考解答
- 算法设计与分析试题及答案
- 计算机算法设计与分析(第三版)课后习题答案详解
- 算法设计与分析复习题目及答案
- 算法设计与分析+习题参考答案
- 算法设计与分析第2版 王红梅 胡明 习题答案
- (完整版)算法设计与分析考试题及答案
- 计算机算法设计与分析习题及答案
- 算法设计与分析习题答案
- 算法设计与分析课后答案
- 算法设计与分析C 语言描述(陈慧南版)课后答案
- 算法设计与分析习题解答
- 算法设计与分析答案参考