1、一个算法的优劣可以用(时间复杂度) 26、旅行售货员问题不能用()解决
与(空间复杂度)与来衡量。 以用回溯法解决,分支限界法,NP 完全性 归算法,而一个使用函数自身给出定义的函数
2、回溯法在问题的解空间中,按( 深度 理论与近似算法 称为递归函数。定义递归函数时可以没有初始
优先方式)从根结点出发搜索解空间树。 27、贪心算法不能解决(0-1 背包问题 N 值。错,应该有初始值;
3、直接或间接地调用自身的算法称为(递 皇后问题)。可以解决背包问题 7)动态规划法用一个表来记录所有已解决的
归算法)。 28、投点法是(概率算法)的一种。
4、 记号在算法复杂性的表示法中表示 29、若线性规划问题存在最优解,它一定
(渐进确界或紧致界)。 不在(可行域内部)
子问题的答案。不管该子问题以后是否被用
到,只要它被计算过,就将其结果填入表中。
在需要时从表中找出以求得的答案。对;
5、在分治法中,使子问题规模大致相等 30、n 皇后问题可以用( 回溯法)解决。 8)动态规划算法是用于解最优化问题,采用
的做法是出自一种( 平衡(banlancing)子 31、若 L 是一个 NP 完全问题,L 经过多项 自顶向下的方式计算出最优解。错;
式时间变换后得到问题 l,则l 是( P 类问 9)贪心算法和动态规划算法都要求问题必须
6、动态规划算法适用于解( 具有某种最
优性质)问题。
具有最优子结构性质和贪心选择性质。错;
10)队列式分支限界法将活结点表组织成一个
)。 优先队列,并按队列的先进现出原则选取下一
个结点称为当前扩展结点。错;
7、贪心算法做出的选择只是( 在某种意 性质中,程序可以不满足哪个性质:(
义上的局部)最优选择。 有限性!算法的四个性质:输入;输出;
8、最优子结构性质的含义是( 问题的最 确定性;有限性;
优解包含其子问题的最优解)。
9、回溯法按(深度优先)策略从根结点 支限界法)
33、回溯法在解空间树T上的搜索方式(:分 说明:任意选择所使用的算法策略;要求:说
明所使用的算法策略;写出算法实现的主要步
骤;分析算法的时间复杂性。
10、拉斯维加斯算法找到的解一定是(正 哪一步:()包括:划分阶段:选择状态
确 0-1 背包问题 第三章,第五章,第六章
写出规划 单源最短路径问题 第四章,第六章
11、按照符号 O 的定义 O(f)+O(g)等于 方程(包括边界条件):
O(max{f(n),g(n)})。
12、二分搜索技术是运用(分治)策略的 是计算机检查不出来的:(逻辑错误)
0-1 背包问题:
算法策略:动态规划算法。动态规划算法基本
典型例子。 36、分治算法不包括以下哪项内容:()包 思想是将待求解问题分解成若干个子问题,但
13、动态规划算法中,通常不同子问题的 括:二分搜索技术;大整数乘法;Strassen 是经分解得到的子问题往往不是互相独立的。
不同子问题的数目常常只有多项式量级。
步骤:1 找出最优解的性质,并刻划其结构特
征。2 递归地定义最优值。3 以自底向上的方
14、(最优子结构性质)和(子问题重叠 序;线性时间选择;最接近点对问题;循
性质)是采用动态规划算法的两个基本要 环赛日程表
素。
15、(最优子结构性质)和(贪心选择性 皇后问题)。
质)是贪心算法的基本要素。 38、舍伍德算法是( 数值概率算法)的一 时间复杂度: 改进后算法的计算时间复杂
16、(选择能产生最优解的贪心准则 )是 种。
37、贪心算法不能解决(0-1 背包问题 N 式计算出最优值。4 根据计算最优值时得到的
性为 O(2^n) 。当所给物品的重量 w (1≤i≤n)
是整数时, |p[i]|≤c+1 ,(1≤i≤n) 。在这种情
况 下 , 改 进 后 算 法 的 计 算 时 间 复 杂 性 为
17、分支限界法常以(广度优先) 或(以 不在(可行域内部)
最小耗费(最大效益)优先)的方式搜索问 40、回溯法可以解决的问题包括(N 皇后 O(min{nc,2^n})
题的解空间树。 问题;装载问题;批处理作业调度;符号 单源最短路径问题:
18、贪心选择性质是指所求问题的整体最 三角形问题;n 后问题;0-1 背包问题;最 算法策略:贪心算法。贪心算法总是作出在当
优解可以通过一系列(局部最优)的选择, 大团问题;图的 m 着色问题;旅行售货员 前看来最好的选择。也就是说贪心算法并不从
整体最优考虑,它所作出的选择只是在某种意
义上的局部最优选择。当然,希望贪心算法得
到的最终结果也是整体最优的。虽然贪心算法
19、按照活结点表的组织方式的不同,分 续邮资问题)
支限界法包括( 队列式 (FIFO)分支限界 判断题(每小题 3 分,共 15 分)
法)和(优先队列式分支限界法)两种形 1)分支限界法类似于回溯法,也是一种在 不能对所有问题都得到整体最优解,但对许多
式。 问题的解空间树 T 上搜索问题解的算法, 问题它能产生整体最优解。如单源最短路经问
20、如果对于同一实例,蒙特卡洛算法不 两者的求解目标是相同的。对; 题,最小生成树问题等。在一些情况下,即使
会给出两个不同的正确解答,则称该蒙特 2)优先队列式的分支限界法将活结点表组 贪心算法不能得到整体最优解,其最终结果却
卡洛算法是(一致的)。
21、哈夫曼编码可利用(贪心法)算法实 的结点优先级选取优先级最高的下一个结
现。 点称为当前扩展结点。对;
是最优解的很好近似。贪心算法则通常以自顶
向下的方式进行,以迭代的方式作出相继的贪
心选择,每作一次贪心选择就将所求问题简化
22 概率算法有数值概率算法,蒙特卡罗 3)回溯法求解问题的所有解时,要回溯到 为规模更小的子问题。
(Monte Carlo)算法,拉斯维加斯(Las 根,且根结点的所有子树都被搜索遍才结
Vegas)算法和舍伍德(Sherwood)算法 束。错,搜索到一个解就可结束;
步骤:Dijkstra 算法是解单源最短路径问题的
贪心算法。其基本思想是,设置顶点集合 S
23 以自顶向下的方式求解最优解的有(贪 4)动态规划法用一个表来记录所有已解决 并不断地作贪心选择来扩充这个集合。一个顶
点属于集合 S 当且仅当从源到该顶点的最短
路径长度已知。初始时,S 中仅含有源。设 u
是 G 的某一个顶点,把从源到 u 且中间只经
24、下列算法中通常以自顶向下的方式求 被用到,只要它被计算过,就将其结果填
解最优解的是(C)。 A、分治法 B、动 入表中。对;
5)一个直接或间接地调用自身的算法称为 过 S 中顶点的路称为从源到 u 的特殊路径,并
25、在对问题的解空间树进行搜索的方法 递归算法,而一个使用函数自身给出定义
用数组 dist 记录当前每个顶点所对应的最短
特殊路径长度。Dijkstra 算法每次从 V-S 中取
出具有最短特殊路长度的顶点 u,将 u 添加到
的函数称为递归函数。定义递归函数时可
以没有初始值。错,应该有初始值;