算法设计与分析复习题目及答案19874.docx
- 文档编号:12372750
- 上传时间:2023-06-05
- 格式:DOCX
- 页数:36
- 大小:221.83KB
算法设计与分析复习题目及答案19874.docx
《算法设计与分析复习题目及答案19874.docx》由会员分享,可在线阅读,更多相关《算法设计与分析复习题目及答案19874.docx(36页珍藏版)》请在冰点文库上搜索。
算法设计与分析复习题目及答案19874
一。
选择题
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、 回溯法解旅行售货员问题时的解空间树就是( B )。
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 )。
A、O(n2n)ﻩﻩB、O(nlogn)ﻩC、O(2n)ﻩﻩﻩ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)ﻫANP问题都就是不可能解决的问题ﻫBP类问题包含在NP类问题中ﻫCNP完全问题就是P类问题的子集
DNP类问题包含在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 单源最短路径问题ﻩﻩBN皇后问题ﻫ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 )
A、O(n2n) B、O(nlogn) C、O(2n) 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 )。
A、O(n2n)ﻩﻩB、O(nlogn)C、O(2n)ﻩﻩﻩ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 )。
A、O(n2n)ﻩﻩﻩB、O(nlogn)ﻩC、O(2n)D、O(n)
54、以深度优先方式系统搜索问题解的算法称为( D ) 。
A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法
55、实现最长公共子序列利用的算法就是( B )。
A、分治策略ﻩﻩB、动态规划法ﻩﻩC、贪心法ﻩﻩD、回溯法
56、算法就是由若干条指令组成的有穷序列,而且满足以下性质(D )
(1)输入:
有0个或多个输入
(2)输出:
至少有一个输出
(3)确定性:
指令清晰,无歧义
(4)有限性:
指令执行次数有限,而且执行时间有限
A(1)
(2)(3) B
(1)(2)(4)C
(1)(3)(4)D
(1)
(2)(3)(4)
57、函数32n+10nlogn的渐进表达式就是(B )、
A、 2n B.32n C. nlogn D、10nlogn
58、大整数乘法算法就是( A)、算法ﻫA、分治B.贪心C、动态规划 D、穷举ﻫ59、用动态规划算法解决最大字段与问题,其时间复杂性为(B )、
A.lognB、nC、n2 D、nlognﻫ60、解决活动安排问题,最好用(B )算法ﻫA、分治 B、贪心C、动态规划D、穷举
61、设f(N),g(N)就是定义在正数集上的正函数,如果存在正的常数C与自然数N0,使
得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时有下界g(N),记作
f(N)∈○(g(N)),即f(N)的阶(A)g(N)的阶.ﻫA、不高于B、不低于C、等价于D、逼近ﻫ62、回溯法在解空间树T上的搜索方式就是(A ).ﻫA、深度优先 B、广度优先 C、最小耗费优先 D.活结点优先ﻫ63、回溯算法与分支限界法的问题的解空间树不会就是(D )、ﻫA、有序树 B、子集树C、排列树D、无序树ﻫ64、在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的就是(B)、
A、回溯法B、分支限界法C、回溯法与分支限界法D.回溯法求解子集树问题
65、从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除(C)之外都就是最常见的方式、ﻫA.队列式分支限界法B、优先队列式分支限界法ﻫC.栈式分支限界法 D、FIFO分支限界法
二、填空题
1、算法的复杂性有 时间 复杂性与 空间 复杂性之分。
2、程序就是算法 用某种程序设计语言的具体实现。
3、算法的“确定性”指的就是组成算法的每条 指令就是清晰的,无歧义的。
4.矩阵连乘问题的算法可由动态规划 设计实现。
5、拉斯维加斯算法找到的解一定就是 正确解。
6、算法就是指解决问题的一种方法或一个过程 。
7、从分治法的一般设计模式可以瞧出,用它设计出的程序一般就是递归算法 。
8、问题的 最优子结构性质 就是该问题可用动态规划算法或贪心算法求解的关键特征。
9、以深度优先方式系统搜索问题解的算法称为 回溯法。
10、数值概率算法常用于 数值问题 的求解。
11、计算一个算法时间复杂度通常可以计算循环次数 、基本操作的频率 或计算步。
12、利用概率的性质计算近似值的随机算法就是__数值概率算法,运行时以一定的概率得到正确解的随机算法就是__蒙特卡罗算法_____________________。
14、解决0/1背包问题可以使用动态规划、回溯法与分支限界法,其中不需要排序的就是 动态规划,需要排序的就是 回溯法,分支限界法。
ﻫ15、使用回溯法进行状态空间树裁剪分支时一般有两个标准:
约束条件与目标函数的界,N皇后问题与0/1背包问题正好就是两种不同的类型,其中同时使用约束条件与目标函数的界进行裁剪的就是 0/1背包问题 ,只使用约束条件进行裁剪的就是 N皇后问题 。
16、贪心选择性质就是贪心算法可行的第一个基本要素,也就是贪心算法与动态规划算法的主要区别。
17、矩阵连乘问题的算法可由 动态规划 设计实现。
18、拉斯维加斯算法找到的解一定就是正确解。
19、贪心算法的基本要素就是贪心选择 质与 最优子结构 性质。
21. 动态规划算法的基本思想就是将待求解问题分解成若干 子问题 ,先求解 子问题 ,然后从这些 子问题 的解得到原问题的解。
22、算法就是由若干条指令组成的有穷序列,且要满足输入、 输出 、确定性与 有限性 四条性质。
23、大整数乘积算法就是用 分治法来设计的。
24、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。
25、舍伍德算法总能求得问题的 一个解 。
26、贪心选择性质 就是贪心算法可行的第一个基本要素,也就是贪心算法与动态规划算法的主要区别。
27、快速排序算法就是基于 分治策略 的一种排序算法。
28、动态规划算法的两个基本要素就是. 最优子结构 性质与重叠子问题 性质。
30、回溯法就是一种既带有 系统性 又带有 跳跃性 的搜索算法。
31、分支限界法主要有 队列式(FIFO) 分支限界法与 优先队列式 分支限界法。
32、分支限界法就是一种既带有系统性 又带有 跳跃性的搜索算法。
33、回溯法搜索解空间树时,常用的两种剪枝函数为约束函数与 限界函数 。
34、任何可用计算机求解的问题所需的时间都与其规模有关。
35、快速排序算法的性能取决于 划分的对称性。
36.Prim算法利用 贪心 策略求解 最小生成树 问题,其时间复杂度就是 O(n2)。
37、图的m着色问题可用回溯 法求解,其解空间树中叶子结点个数就是 mn,解空间树中每个内结点的孩子数就是 m 。
三、算法填空
1.背包问题的贪心算法
voidKnapsack(intn,floatM,floatv[],float w[],floatx[])
{
Sort(n,v,w);
inti;
for (i=1;i<=n;i++)x[i]=0;
floatc=M;
for(i=1;i<=n;i++){
if (w[i]>c) break;
x[i]=1;
c-=w[i];
}
if (i<=n)x[i]=c/w[i];
}
2、最大子段与:
动态规划算法
intMaxSum(intn,inta[])
{
intsum=0,b=0; //sum存储当前最大的b[j], b存储b[j]
for(intj=1;j<=n; j++){
if(b>0)b+=a[j] ;
else b=a[i]; ;//一旦某个区段与为负,则从下一个位置累与
if(b>sum)sum=b;
}
return sum;
}
3.快速排序
template<classType>
voidQuickSort(Type a[],intp, int r)
{
if (p int q=Partition(a,p,r); QuickSort(a,p,q-1);//对左半段排序 QuickSort (a,q+1,r);//对右半段排序 } } 4、排列问题 Template<class Type> voidperm(Typelist[],intk, intm ) {//产生[list[k: m]的所有排列 if(k==m) { //只剩下一个元素 for(inti=0;i<=m;i++) cout<<list[i]; cout< } else //还有多个元素待排列,递归产生排列 for (inti=k;i<=m;i++) { s[k],list[i]); perm(list,k+1;m); s[k],list[i]); } } 5.给定已按升序排好序的n个元素a[0: n-1],现要在这n个元素中找出一特定元素x。 据此容易设计出二分搜索算法: template<classType> intBinarySearch(Typea[], constType&x,intl,int r) { while(l<=r){ intm =((l+r)/2); if (x ==a[m])returnm;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 复习 题目 答案 19874