当前位置:首页 >> 理化生 >>

算法习题


算法设计与分析试卷 一、 填空题(20 分,每空 2 分) 1、 算法的性质包括输入、输出、确定性、有限性。 2、 动态规划算法的基本思想就将待求问题分解成若干个子问题、先求解子问题,然后 从这些子问题的解得到原问题的解。 3、 设计动态规划算法的 4 个步骤: (1) 找出最优解的性质,并刻画其结构特征。 (2) 递归地定义最优值。 (3) 以自底向上的方式计算出最优值。 (4) 根据计算最优值得到的信息,构造最优解。 4、 流水作业调度问题的 johnson 算法: (1) 令 N1={i|ai<bi},N2={i|ai>=bj}; (2) 将 N1 中作业依 ai 的 ai 的非减序排序;将 N2 中作业依 bi 的非增序排序。 5、对于流水作业高度问题,必存在一个最优调度 π ,使得作业 π (i)和 π (i+1)满足 Johnson 不等式 min{bπ (i),aπ (i+1)}≥min{bπ (i+1),aπ (i)}。 6、最优二叉搜索树即是最小平均查找长度的二叉搜索树。 二、综合题(50 分) 1、当(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时,最大子段和为∑ak(2<=k<=4)=20 (5 分) 2、 由流水作业调度问题的最优子结构性质可知, T (N, 0) = min{ai+T(N-{i},bi)}(1=<i<=n) (5 分) 3、最大子段和问题的简单算法(10 分) int maxsum(int n,int *a,int & bestj) { Int sum=0; for (int i=1;i<=n;i++) for (int j=i;j<=n;j++) int thissum=0; for(int k=i;k<=j;k++) this sum+=a[k]; if(thissum>sum){ sum=thissum; besti=i; bestj=j;} } return sum; } 4、设计最优二叉搜索树问题的动态规划算法 OptimalBinarysearchTree? (15 分) Void OptimalBinarysearchTree(int a,int n,int * * m, int * * w) { for(int i=0;i<=n;i++) {w[i+1][i]=a[i]; m[i+1][i]= 0;} for(int r=0;r<n;r++) for(int i=1;i<=n-r;i++){ int j=i+r;

w[i][j]=w[i][j-1]+a[j]+b[j]; m[i][j]= m[i+1][j]; s[i][j]=i; for(int k=i+1;k<=j;k++){ int t=m[i][k-1]+m[k+1][j]; if(t<m[i][j]) {m[i][j]=t; s[i][j]=k;} } m[i][j]=t; s[i][j]=k;} } 5、设 n=4, (a1,a2,a3,a4)=(3,4,8,10), (b1,b2,b3,b4)=(6,2,9,15) 用两种方法求 4 个作业的最优调度方案并计算其最优值?(15 分) 法一:min(ai,bj)<=min(aj,bi) 因为 min(a1,b2)<=min(a2,b1) 所以 1→2 (先 1 后 2) 由 min(a1,b3)<=min(a3,b1) 得 1→3 (先 1 后 3) 同理可得:最后为 1→3→4→2 法二:johnson 算法思想 N1={1,3,4} N2={2} N?1={1,3,4} N?2={2} 所以 N?1→N?2 得:1→3→4→2 三、简答题(30 分) 1、将所给定序列 a[1:n]分为长度相等的两段 a[1:n/2]和 a[n/2+1:n],分别求出这两段的 最大子段和,则 a[1:n]的最大子段和有哪三种情形?(10 分) 答: (1)a[1:n]的最大子段和与 a[1:n/2]的最大子段和相同。 (2)a[1:n]的最大子段和与的最大子段 a[n/2+1:n]和相同。 (3)a[1:n]的最大子段和为∑ak(i=<k<=J),且 1<=i<=n/2,n/2+1<=J<=n。 2、由 0——1 背包问题的最优子结构性质,可以对 m(i,j)建立怎样的递归式? (10 分) (1)m(i,j)=max{m(i+1,j),m(i+1,j-wi)+ui} (j>=wi) 或则 m(i,j)= m(i+1,j) (0<=j<wi) (2)m(n,j)=un j>=wn 或则 m(n,j)=0 0<=j<wn 3、0——1 背包求最优值的步骤分为哪几步?(10 分) (1) 、p[n+1]={(0,0)} (2) 、由 p[i+1]→q[i+1], q[i+1]=p[i+1]⊕(wi,vi) (3) 、Mij=p[i+1]∪q[i+1] Pi=Mij——其中的受控点=p[i+1]∪q[i+1]——其中的受控 (4) 、重复(2)-(3)直到求出 P[1]。 4、请说明算法的五个基本特性,并进行简要的分析(5 分) 答:算法的五个基本特性如下: ① 确定性 算法的每一种运算必须要有确切的定义,即每一种运算应该执行何种动作 必须是相当清楚的、无二义性的。 ③ 输入 一个算法有 0 个或多个输人,这些输人是在算法开始之前给出的量,它取自 特定的对象集合。

④ 输出 一个算法产生一个或多个输出,这些输出是同输人有某种特定关系的量。 ⑤ 有限性 一个算法总是在执行了有穷步的运算之后能够终止,且每一步都可在有穷 时间内完成。这里的有穷的概念不是纯数学的,而是在实际上是合理的,可以接受的。凡 是算法,都必须满足以上五条特性。

算法习题:
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. 回溯法解旅行售货员问题时的解空间树是( 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、下列随机算法中运行时有时候成功有时候失败的是(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 ) 。 n n A、O(n2 ) B、O(nlogn) C、O(2 ) D、O(n) 15.分支限界法解最大团问题时,活结点表的组织形式是( B ) 。 A、最小堆 B、最大堆 C、栈 D、数组 16.最长公共子序列算法利用的算法是( B ) 。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 17.实现棋盘覆盖算法利用的算法是( A ) 。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 18.下面是贪心算法的基本要素的是( C ) 。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 19.回溯法的效率不依赖于下列哪些因素( D ) A.满足显约束的值的个数 B. 计算约束函数的时间 C. 计算限界函数的时间 D. 确定解空间的时间 20.下面哪种函数是回溯法中为避免无效搜索采取的策略( B ) A.递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 21、下面关于 NP 问题说法正确的是(B )

A NP 问题都是不可能解决的问题 B P 类问题包含在 NP 类问题中 C NP 完全问题是 P 类问题的子集 D NP 类问题包含在 P 类问题中 22、蒙特卡罗算法是( B )的一种。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 23.下列哪一种算法不是随机化算法( C ) A. 蒙特卡罗算法 B. 拉斯维加斯算法 C.动态规划算法 D.舍伍德算法 24. ( D )是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 25. 矩阵连乘问题的算法可由( B)设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 26. 分支限界法解旅行售货员问题时,活结点表的组织形式是( A ) 。 A、最小堆 B、最大堆 C、栈 D、数组 27、Strassen 矩阵乘法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 29、使用分治法求解不需要满足的条件是(A ) 。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使 用相同的方法解 30、下面问题(B )不能使用贪心法解决。 A 单源最短路径问题 B N 皇后问题 C 最小花费生成树问题 D 背包问题 31、下列算法中不能解决 0/1 背包问题的是(A ) A 贪心法 B 动态规划 C 回溯法 D 分支限界法 32、回溯法搜索状态空间树是按照(C )的顺序。 A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历 33、下列随机算法中运行时有时候成功有时候失败的是(C ) A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 34.实现合并排序利用的算法是( A ) 。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 35.下列是动态规划算法基本要素的是( D ) 。 A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质 36.下列算法中通常以自底向下的方式求解最优解的是( B ) 。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 37.采用广度优先策略搜索的算法是( A ) 。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 38、合并排序算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 39、在下列算法中得到的解未必正确的是( B ) 。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 40、背包问题的贪心算法所需的计算时间为( B ) n n A、O(n2 ) B、O(nlogn) C、O(2 ) D、O(n) 41.实现大整数的乘法是利用的算法( C ) 。 A、贪心法 B、动态规划法 C、分治策略 D、回溯法 42.0-1 背包问题的回溯算法所需的计算时间为( A ) A、O(n2n) B、O(nlogn) C、O(2n) D、O(n) 43.采用最大效益优先搜索方式的算法是( A ) 。

A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 44.贪心算法与动态规划算法的主要区别是( B ) 。 A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解 45. 实现最大子段和利用的算法是( B ) 。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 46.优先队列式分支限界法选取扩展结点的原则是( C ) 。 A、先进先出 B、后进先出 C、结点的优先级 D、随机 47.背包问题的贪心算法所需的计算时间为( B ) 。 n n A、O(n2 ) B、O(nlogn) C、O(2 ) D、O(n) 48、广度优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 49、舍伍德算法是( B )的一种。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 50、在下列算法中有时找不到问题解的是( B ) 。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 51 下列哪一种算法是随机化算法( D ) A. 贪心算法 B. 回溯法 C.动态规划算法 D.舍伍德算法 52. 一 个 问 题 可 用 动 态 规 划 算 法 或 贪 心 算 法 求 解 的 关 键 特 征 是 问 题 的 ( B ) 。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解 53. 采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序, 故算 法的时间复杂度为 ( B ) 。 n n A、O(n2 ) B、O(nlogn) C、O(2 ) D、O(n) 54. 以深度优先方式系统搜索问题解的算法称为 ( D ) 。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 55. 实现最长公共子序列利用的算法是( B ) 。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 二、 填空题 1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。 2、程序是 算法 用某种程序设计语言的具体实现。 3、算法的“确定性”指的是组成算法的每条 指令 是清晰的,无歧义的。 4.矩阵连乘问题的算法可由 动态规划 设计实现。 5、拉斯维加斯算法找到的解一定是 正确解。 6、算法是指解决问题的 一种方法 或 一个过程 。 7、从分治法的一般设计模式可以看出,用它设计出的程序一般是 递归算法 。 8、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。 9、以深度优先方式系统搜索问题解的算法称为 回溯法 。 10、数值概率算法常用于 数值问题 的求解。 11、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步。 12、 利用概率的性质计算近似值的随机算法是数值概率算法, 运行时以一定的概率得到正确 解的随机算法是__蒙特卡罗算法_____________________。 14、 解决 0/1 背包问题可以使用动态规划、 回溯法和分支限界法, 其中不需要排序的是 动 态规划 ,需要排序的是 回溯法 ,分支限界法 。 15、使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函数的界,N

皇后问题和 0/1 背包问题正好是两种不同的类型, 其中同时使用约束条件和目标函数的界进 行裁剪的是 0/1 背包问题 ,只使用约束条件进行裁剪的是 N 皇后问题 。 17、矩阵连乘问题的算法可由 动态规划 设计实现。 18、拉斯维加斯算法找到的解一定是 正确解。 19.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。 21. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 , 先求解 子 问题 ,然后从这些 子问题 的解得到原问题的解。 算法是由若干条指令组成的有穷序列,且要满足输入,输出 、确定性和 有限性 四条性质。 23、大整数乘积算法是用 分治法 来设计的。 24、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 25、舍伍德算法总能求得问题的 一个解 。 贪心选择性质是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法主要区别。 27.快速排序算法是基于 分治策略 的一种排序算法。 28.动态规划算法的两个基本要素是. 最优子结构性质和 重叠子问题 性质 。 30.回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。 31.分支限界法主要有 队列式 (FIFO) 分支限界法和 优先队列式 分支限界法。 32.分支限界法是一种既带有 系统性 又带有 跳跃性 的搜索算法。 33. 回溯法搜索解空间树时, 常用的两种剪枝函数为 约束函数 和 限界函数 。 34.任何可用计算机求解的问题所需的时间都与其 规模 有关。 35.快速排序算法的性能取决于 划分的对称性 。 1.分治法的基本思想时将一个规模为 n 的问题分解为 k 个规模较小的子问题,这些子问题 互相独立且与原问题相同。 递归地解这些子问题, 然后将各个子问题的解合并得到原问题的 解。 2.设计动态规划算法的主要步骤为: (1)找出最优解的性质,并刻划其结构特征(2)递归 地定义最优值(3)以自底向上的方式计算出最优值(4)根据计算最优值时得到的信息,构 造最优解。 3. 分治法与动态规划法的相同点是: 将待求解的问题分解成若干个子问题, 先求解子问题, 然后从这些子问题的解得到原问题的解。 两者的不同点是:适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相 独立的。而用分治法求解的问题,经分解得到的子问题往往是互相独立的。 4.分支限界法与回溯法的相同点是:都是一种在问题的解空间树 T 中搜索问题解的算法。 不同点: (1)求解目标不同; (2)搜索方式不同; (3)对扩展结点的扩展方式不同; (4)存储空间的要求不同。 5 用回溯法搜索子集树的算法为: 6. 分治法所能解决的问题一般具有的几个特征是: (1)该问题的规模缩小到一定的程度就可以容易地解决; (2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质; (3)利用该问题分解出的子问题的解可以合并为该问题的解; (4)原问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。 7. 用分支限界法设计算法的步骤是: (1)针对所给问题,定义问题的解空间(对解进行编码) ;分 (2)确定易于搜索的解空间结构(按树或图组织解) ; (3)以广度优先或以最小耗费(最大收益)优先的方式搜索解空间,并在搜索过程中用剪 枝函数避免无效搜索。

8. 常见的两种分支限界法的算法框架 (1)队列式(FIFO)分支限界法:按照队列先进先出(FIFO)原则选取下一个节点为扩展节 点。 (2)优先队列式分支限界法:按照优先队列中规定的优先级选取优先级最高的节点成 为当前扩展节点。 9. 回溯法中常见的两类典型的解空间树是子集树和排列树。 当所给的问题是从 n 个元素的集合 S 中找出满足某种性质的子集时,相应的解空间树称 为子集树。这类子集树通常有 2n 个叶结点,遍历子集树需 O(2n)计算时间 。 当所给的问题是确定 n 个元素满足某种性质的排列时,相应的解空间树称为排列树。这 类排列树通常有 n!个叶结点。遍历排列树需要 O(n!)计算时间。 10. 分支限界法的搜索策略是: 在扩展结点处,先生成其所有的儿子结点(分支) ,然后再从当前的活结点表中选择下 一个扩展结点。为了有效地选择下一扩展结点,加速搜索的进程,在每一个活结点处,计算 一个函数值(限界) ,并根据函数值,从当前活结点表中选择一个最有利的结点作为扩展结 点,使搜索朝着解空间上有最优解的分支推进,以便尽快地找出一个最优解。


相关文章:
算法练习题-分章节-带答案
算法练习题---算法概述一、选择题 1、下面关于算法的描述,正确的是( ) A、一个算法只能有一个输入 B、算法只能用框图来表示 C、一个算法的执行步骤可以是...
基础算法习题集
基础算法习题集(李波于 2007 年 7 月收集整理) 第一章 入门试题 ... 3 EX1_1、角谷猜想:......
RSA习题
RSA习题_IT/计算机_专业资料。RSA习题 1.假设需要加密的明文信息为 m=85,选择:e=7,p=11,q=13,说明使用 RSA 算法 1.假设需要加密的明文信息为 m=85,...
简便运算的练习题和答案
(1)乘法交换律:a×b=b×a 38×25×4 42×125×8 运算定律练习题 乘法结合律: (a×b)×c=a×(b×c) 25×17×4 (25×125)×(8×4) 49×4×5...
算法第二章习题
算法第二章习题算法第二章习题隐藏>> 第2 章习题 1. 证明当 a k > 0 时,任何多项式 p (n) = a k n k + a k ?1 n k ?1 + ... + a 0 ...
算法设计练习题
算法设计练习题_工学_高等教育_教育专区。算法设计练习题 一. 计算复杂性 1. P184 10.3 设计一个多项式时间的算法判断一个无向图 G 是否是 2 可着色的 ...
算法复习题
算法习题_工学_高等教育_教育专区。不错的1.什么是算法?算法必须满足的五个特性是什么? 算法:一组有穷的规则,规定了解决某一特定类型问题的一系列运算。 (...
算法复习题(精炼版)
算法习题(精炼版)_数学_高中教育_教育专区。填空题动态规划算法的基本要素为:最优子结构性质与重叠子问题性质 1) 算法分析中,记号 O 表示渐进上界,记号 ? ...
动态规划讲解大全(含例题及答案)
动态规划算法的应用 一、动态规划的概念近年来,涉及动态规划的各种竞赛题越来越多,每一年的 NOI 几乎都至少有一道题目需要用动态 规划的方法来解决;而竞赛对选手...
C语言经典算法90题
C语言经典算法90题_计算机软件及应用_IT/计算机_专业资料。包含90到算法经典题目,适合初学者初深入学习,或者有一到两学期经验的学生学习,算法入门经典【...
更多相关标签: