复习题_算法分析与程序设计1

一、简答题 1. 什么是算法?算法的性质? 解决问题的方法或过程 什么是程序? 算法用某种程序设计语言的具体实现 两者有什么不同?程序可以不满足算法的有限性的性质 2. 给出 f(N)= ?(g( N)) 的定义。 如果存在正常数 c 和自然数 N0,使得当 N>=N0 时,有 f(N)>=c*g(N),则称函数 f(N)当 N 充分大时下有界,且 g(N) 是它的一个下界,记为 f(N)= ?(g( N)) 。 3. 4. 贪心算法的基本要素是什么? 最优子结构性质、贪心选择性质 问题的解空间树是表示问题解空间的一颗有序树,常见有哪两 种? 子集树、排序树 5. 什么是回溯法?是指具有限界函数的深度优先生成法 回溯法与分支限界法有什么不同? 1、求解目标不同 回溯法是找出解空间树中满足约束条件的所有解 分支限界法是找出满足约束条件的一个解,即在某 种意义下的最优解 2、搜索方式不同 回溯法的搜索方式是深度优先 分支限界法的搜索方式是广度优先 回溯法的基本思想:用深度优先搜索的方式进行搜索,当遇到一 个结点时判断以此结点为根的子树是否含有问题的解。 如果不含有则 退回到上层结点,继续按深度优先搜索方式搜索。 6.动态规划算法的基本要素?步骤?基本思想? 最优子结构性质、重复子问题性质 输入、输出、确定性、有限性

1、找出最优解的性质,并刻画其结构特征 2、递归的计算最优值 3、自底向上的计算最优解 4、根据计算最优值时得到的信息,构造最优解 基本思想:与分治法思想类似,也是将原问题分解成若干子问题 (子问题不是相互独立) ,先求出子问题的解,然后从子问题的解得 到原问题的解 7.适合于分治法求解的问题,经分解得到的子问题有什么特点?互 相独立且与原问题相同 适合于动态规划法求解的问题, 经分解得到

的子问题有什么特点?子问题不是相互独立的 8.分支限界法以哪两种方式搜索解空间树? 队列式分支限界法、优先队列式分支限界法 9. 直接或间接地调用自身的算法称为什么? 递归算法 10. 用函数自身给出定义的函数称为什么? 二、填空题
1.int unknow( int a[],int p,int r) {int i=p, j=r+1; int x=a[p]; while (true){ while (a[ ____++__ i ] < x); while (a[ --j ] __>_ x ); if (i>=j) break ; swap(a[i], a[j]); } a[p] =a[j]; a[j] = __x__ ; return ___j___ ; } 2.// 最大团回溯算法 private static void backtrack(int i)

递归函数

{ if (i ___>__ n) { //到达叶结点 for (int j=1;j<=n;j __++__ ) bestx[j]=x[j]; bestn=cn; return; } //检查顶点 i 与当前团的连接 boolean ok=true; for(int j=1;j<i;j++) if (x[j]==1 && !a[i][j]) {// i 与 j 不相连 ok= ___false____ ; break; } if (ok) { //进入左子树 x[i]=1; cn __++____ ; backtrack( ____i+1___ ); cn--; } if (cn+n-i>bestn) { //进入右子树 x[i]= __0___ ; backtrack(i+1); } } 3.private static void qSort(int p,int r) { if ( p < r ){

int q=partition( p, r ); qSort( p, q-1 ); qSort( } } 4.public static int greedySelector (int []s, int []f, boolean a[]) { int n=s.length-1; a[1]=true; int j=1; q+1 , r );

int count=1; for(int i=2;i<=n;i++) { if(s[i] >= f[j]){ a[i]= j=i; count } else a[i]=false; } return count; } 5.//装载问题的回溯算法 private static void backtrack (int i) { //搜索第 i 层洁点 if(i __>__ n) { // 到达叶洁点 for (int j=1; j<=n; j __++__ ) bestx[j] = x[j] ; bestw = cw; return ; } // 搜索子树 r - = w[ i ]; if(cw+w[i]<= ___c__ ){ // 搜索左子数 x[i] = 1; cw + = w[i]; backtrack( _i+1___ ); cw _-___ = w[i] ; } if(cw + r > bectw) { x[i]= __0___ ; //搜索右子树 backtrack( i+1 ) ; } r+=w[i] ; } ++ ; true ;

三、应用题 设有 n=4 个运动员要进行羽毛球赛, 要求设计一个满足以下要求的比

赛日程表 (1)每个选手必须与其它 3 个选手各赛一次; (2)每个选手一天只能赛一次; (3)循环赛一共进行 3 天。 4. 根据动态规划法计算矩阵链 A1 A2 A3 乘积的所有 m(i,j), 并给出
A1 A2 A3 的最佳计算次序。其中, A1 是 35*40 的矩阵, A2 是 40*20 的

矩阵, A3 是 20*10 的矩阵。 5. 对于有 n 个顶点的无向图 G 的最大团问题, (1)给出 n=3 时的该问题的解向量,并解释其含义,给出其解 空间,画出其解空间树。
(2)找出下图 G 的最大团,

1 3

2 4

6. 对于 0-1 背包问题,画出 n=3 时的解空间树,并对该问题在没有 任何约束条件下用队列式分支限界法解此问题时, 活结点表组织成 一个队列,给出这个队列的入队的顺序。并给出物品数为 n 时,用 回溯法搜索解空间树的时间复杂度。 7.设有 7 个独立作业{1,2,3,4,5,6,7}由 3 台机器 M1,M2 和 M3 加工处理,各作业所需的处理时间分别为{1,13,3,15,6,5, 2}。用贪心算法给出一种作业调度方案,使所给的 7 个作业在尽可 能短的时间内由 3 台机器加工完成。给出贪心策略,作业调度方案

及所需的总的加工处理时间。
8.求 下 赋 权 图 中 的 最 小 生 成 树 , 并 求 出 最 小 生 成 树 的 耗 费 。

9. 画出 n=4 的从城市 1 出发的旅行售货员问题的解空间树,并给出用回溯法遍 历 解 空 间 树 ( 城 市 个 数 为 n ) 需 要 的 计 算 时 间 。

1 6

30 5

2 10

4 3 4

五、设计算法,修改快速排序算法,使它在最坏情况下的计算复杂 度为 O(nlogn).
六. 根据动态规划法计算矩阵链 A1 A2 A3 乘积的所有 m(i,j),并找出 A1 A2 A3 的 最佳计算次序。其中, A1 是 35*40 的矩阵, A2 是 40*20 的矩阵, A3 是 20*10 的 矩阵。 七.用贪心策略求下列情况下背包问题的最优值和最优解 n=4, c=15 (p1,p2,p3,p4) = (12, 10, 18, 25) (w1,w2,w3,w4) = (2, 4, 6, 5 )

八.假设 n=6,[w1, w2,…, w6]=[100, 50, 90, 60, 200, 80], c=300.其中,c 是轮船的载重量,w1, w2, …, w6 分别是 6 个集装箱的重量。利用贪心算法给 出贪心策略,产生最佳装载,使尽可能多的集装箱装上轮船。 九 . 画 出 n=3 时 的 0-1 背 包 问 题 的 解 空 间 树 , 并 给 出 当 w=[16,15,15],p=[45,25,25],c=30 时该问题用队列式分支限界法解此问题时, 选择扩展结点的顺序。 并给出物品数为 n 时,用回溯法遍历解空间树的时间复杂 度。


相关文档

算法分析复习题1
算法分析复习题第一部分
算法分析复习题1(gai)
国际大学生程序设计竞赛试题与算法分析(二) 回溯算法
国际大学生程序设计竞赛试题与分析(一)模拟题
《JAVA面向对象程序设计》试题与解析库[1].
2011年1月计算机基础与程序设计试题
算法分析期末试题集答案(6套)1
5福建省2013年1月信息技术会考算法与程序设计上机试题5
国际大学生程序设计竞赛试题与算法分析_三_动态规划及其应用_最短路问题
电脑版