计算机算法与设计复习题(含答案)

1、一个算法的优劣可以用(时间复杂度)与(空间复杂度)与来衡量。

2、回溯法在问题的解空间中,按(深度优先方式)从根结点出发搜索解空间树。

3、直接或间接地调用自身的算法称为(递归算法)。

4、 记号在算法复杂性的表示法中表示(渐进确界或紧致界)。

5、在分治法中,使子问题规模大致相等的做法是出自一种(平衡(banlancing)子问题)的思想。

6、动态规划算法适用于解(具有某种最优性质)问题。

7、贪心算法做出的选择只是(在某种意义上的局部)最优选择。

8、最优子结构性质的含义是(问题的最优解包含其子问题的最优解)。

9、回溯法按(深度优先)策略从根结点出发搜索解空间树。

10、拉斯维加斯算法找到的解一定是(正确解)。

11、按照符号O的定义O(f)+O(g)等于O(max{f(n),g(n)})。

12、二分搜索技术是运用(分治)策略的典型例子。

13、动态规划算法中,通常不同子问题的个数随问题规模呈(多项式)级增长。14、(最优子结构性质)和(子问题重叠性质)是采用动态规划算法的两个基本要素。

15、(最优子结构性质)和(贪心选择性质)是贪心算法的基本要素。

16、(选择能产生最优解的贪心准则)是设计贪心算法的核心问题。

17、分支限界法常以(广度优先)或(以最小耗费(最大效益)优先)的方式搜索问题的解空间树。

18、贪心选择性质是指所求问题的整体最优解可以通过一系列(局部最优)的选择,即贪心选择达到。

19、按照活结点表的组织方式的不同,分支限界法包括(队列式(FIFO)分支限界法)和(优先队列式分支限界法)两种形式。

20、如果对于同一实例,蒙特卡洛算法不会给出两个不同的正确解答,则称该蒙特卡洛算法是(一致的)。

21、哈夫曼编码可利用(贪心法)算法实现。

22概率算法有数值概率算法,蒙特卡罗(Monte Carlo)算法,拉斯维加斯(Las Vegas)算法和舍伍德(Sherwood)算法23以自顶向下的方式求解最优解的有(贪心算法)

24、下列算法中通常以自顶向下的方式求解最优解的是(C)。A、分治法B、动态规划法C、贪心法D、回溯法

25、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是(回溯法)

26、旅行售货员问题不能用()解决可以用回溯法解决,分支限界法,NP完全性理论与近似算法

27、贪心算法不能解决(0-1背包问题N 皇后问题)。可以解决背包问题

28、投点法是(概率算法)的一种。

29、若线性规划问题存在最优解,它一定

不在(可行域内部)

30、n皇后问题可以用(回溯法)解决。

31、若L是一个NP完全问题,L经过多项

式时间变换后得到问题l,则l是( P类问

题).

32、算法与程序在性质上有所不同,下列

性质中,程序可以不满足哪个性质:()。

有限性!算法的四个性质:输入;输出;

确定性;有限性;

33、回溯法在解空间树T上的搜索方式:(分

支限界法)

34、动态规划算法的基本步骤不包括下列

哪一步:()包括:划分阶段:选择状态确

定决策并写出状态转移方程写出规划

方程(包括边界条件):

35、在调试程序过程中,下列哪一种错误

是计算机检查不出来的:(逻辑错误)

36、分治算法不包括以下哪项内容:()包

括:二分搜索技术;大整数乘法;Strassen

矩阵乘法;棋盘覆盖;合并排序和快速排

序;线性时间选择;最接近点对问题;循

环赛日程表

37、贪心算法不能解决(0-1背包问题N

皇后问题)。

38、舍伍德算法是(数值概率算法)的一

种。

39、若线性规划问题存在最优解,它一定

不在(可行域内部)

40、回溯法可以解决的问题包括(N皇后

问题;装载问题;批处理作业调度;符号

三角形问题;n后问题;0-1背包问题;最

大团问题;图的m着色问题;旅行售货员

问题;圆排列问题;电路板排列问题;连

续邮资问题)

判断题(每小题3分,共15分)

1)分支限界法类似于回溯法,也是一种在

问题的解空间树T上搜索问题解的算法,

两者的求解目标是相同的。对;

2)优先队列式的分支限界法将活结点表组

织成一个优先队列,并按优先队列中规定

的结点优先级选取优先级最高的下一个结

点称为当前扩展结点。对;

3)回溯法求解问题的所有解时,要回溯到

根,且根结点的所有子树都被搜索遍才结

束。错,搜索到一个解就可结束;

4)动态规划法用一个表来记录所有已解决

的子问题的答案。不管该子问题以后是否

被用到,只要它被计算过,就将其结果填

入表中。对;

5)一个直接或间接地调用自身的算法称为

递归算法,而一个使用函数自身给出定义

的函数称为递归函数。定义递归函数时可

以没有初始值。错,应该有初始值;

6)一个直接或间接地调用自身的算法称为

递归算法,而一个使用函数自身给出定义

的函数称为递归函数。定义递归函数时可

以没有初始值。错,应该有初始值;

7)动态规划法用一个表来记录所有已解决

的子问题的答案。不管该子问题以后是否

被用到,只要它被计算过,就将其结果填

入表中。在需要时从表中找出以求得的答

案。对;

8)动态规划算法是用于解最优化问题,采用

自顶向下的方式计算出最优解。错;

9)贪心算法和动态规划算法都要求问题必须

具有最优子结构性质和贪心选择性质。错;

10)队列式分支限界法将活结点表组织成一个

优先队列,并按队列的先进现出原则选取下一

个结点称为当前扩展结点。错;

四、算法设计

说明:任意选择所使用的算法策略;要求:说

明所使用的算法策略;写出算法实现的主要步

骤;分析算法的时间复杂性。

0-1背包问题第三章,第五章,第六章

单源最短路径问题第四章,第六章

0-1背包问题:

算法策略:动态规划算法。动态规划算法基本

思想是将待求解问题分解成若干个子问题,但

是经分解得到的子问题往往不是互相独立的。

不同子问题的数目常常只有多项式量级。

步骤:1找出最优解的性质,并刻划其结构特

征。2递归地定义最优值。3以自底向上的方

式计算出最优值。4根据计算最优值时得到的

信息,构造最优解。

时间复杂度:改进后算法的计算时间复杂

性为O(2^n)。当所给物品的重量w i(1≤i≤n)

是整数时,|p[i]|≤c+1,(1≤i≤n)。在这种情

况下,改进后算法的计算时间复杂性为

O(min{nc,2^n})

单源最短路径问题:

算法策略:贪心算法。贪心算法总是作出在当

前看来最好的选择。也就是说贪心算法并不从

整体最优考虑,它所作出的选择只是在某种意

义上的局部最优选择。当然,希望贪心算法得

到的最终结果也是整体最优的。虽然贪心算法

不能对所有问题都得到整体最优解,但对许多

问题它能产生整体最优解。如单源最短路经问

题,最小生成树问题等。在一些情况下,即使

贪心算法不能得到整体最优解,其最终结果却

是最优解的很好近似。贪心算法则通常以自顶

向下的方式进行,以迭代的方式作出相继的贪

心选择,每作一次贪心选择就将所求问题简化

为规模更小的子问题。

步骤:Dijkstra算法是解单源最短路径问题的

贪心算法。其基本思想是,设置顶点集合S

并不断地作贪心选择来扩充这个集合。一个顶

点属于集合S当且仅当从源到该顶点的最短

路径长度已知。初始时,S中仅含有源。设u

是G的某一个顶点,把从源到u且中间只经

过S中顶点的路称为从源到u的特殊路径,并

用数组dist记录当前每个顶点所对应的最短

特殊路径长度。Dijkstra算法每次从V-S中取

出具有最短特殊路长度的顶点u,将u添加到

S中,同时对数组dist作必要的修改。一旦S

包含了所有V中顶点,dist就记录了从源到所

有其它顶点之间的最短路径长度。

时间复杂度:对于具有n个顶点和e条边的带

权有向图,如果用带权邻接矩阵表示这个图,

那么Dijkstra算法的主循环体需要O(n)时间。

这个循环需要执行n-1次,所以完成循环需要

O(n^2)时间。算法的其余部分所需要时间不超

过O(n^2)。

相关推荐
相关主题
热门推荐