.

解组合就是一个较优解或次优解；

(B)不追求最优解，只希望最快得到较为满意解的方法，即每个阶段总是做出在当前看来是最好的选择；

(C)贪心算法确定的路径，是由局部最优组合起来的路径，该路径从全局角度来看一定是最优的；

(D)对一个具体的TSP问题，每次执行贪心算法，所求得的最终解可能是不同的。

//本题考查对TSP贪心算法的理解

5. 关于穷举法，下列说法错误的是_____________。--A|B|C|D

(A) 穷举法的基本思想就是，根据问题的部分已知条件预估解的范围，并在此范围内对所有可能的情况进行逐一验证，直到找到满足已知条件的解为止； (B) 穷举范围的大小直接影响着穷举法的执行效率；

(C) 穷举法，也称蛮力法或暴力搜索法，理论上利用这种方法可破解任何一种密码； (D) 穷举范围中的判定条件直接影响着穷举法的执行效率；

6. 用1元5角钱人民币兑换5分、2分和1分的硬币（每一种都要有）共100枚，问共有几种兑

换方案？每种方案各换多少枚？这个问题可以采用穷举法求解，设5分、2分和1分的硬币各换x，y，z枚，由于每一种硬币都要有，故5分硬币最多可换29枚，2分硬币最多可换72枚，1分硬币可换100-x-y枚，x，y，z只需满足条件__________即可打印输出，对每一组满足条件的x，y，z值用计数器计数即可得到兑换方案的数目。--A|B|C|D (A) 5x+2y+z=1500； (B) 5x+2y+z=1.5； (C) 5x+2y+z=15； (D) 5x+2y+z=150；

7. 爱因斯坦曾出过这样一道数学题：有一条长阶梯，若每步跨2阶，最后剩下1阶；若每步跨3

阶，最后剩下2阶；若每步跨5阶，最后剩下4阶；若每步跨6阶，则最后剩下5阶；只有每步跨7阶，最后才正好1阶不剩。求这条阶梯最少有多少阶？这个问题适合采用_____________法求解。---A|B|C|D (A) 递推； (B) 穷举； (C) 递归 (D) 分治；

8. 分治法所能解决的问题所具有的特征，以下说法错误的是___________。---A|B|C|D

(A) 该问题可以分解为若干个规模较小的相同的子问题；

. .

.

(B) 该问题的规模足够大；

(C) 该问题的规模缩小到一定的程度就可以很容易地解决； (D) 将各个子问题的解可以合并为原问题的解；

9. 关于递归算法特点，下列说法错误的是____________。--A|B|C|D

(A) 能够找出递归关系式；

(B) 算法的关键是设置递归终止条件； (C) 通常用来解决“结构自相似”问题；

(D) 代码清晰简洁，程序可读性好，算法运行效率高。

10. “大事化小、小事化了”体现出的问题求解的思想是___________。--A|B|C|D

(A) 递推法； (B) 穷举法； (C) 归纳法； (D) 分治法；

11. 用穷举法计算并输出100-999之间所有的水仙花数。水仙花数是指各数位数字的立方和等于该

数本身的三位数。例如，153是水仙花数，因为

。设水仙花数的百位、

十位、个位数字分别为i、j、k，通过遍历i、j、k的所有可能取值，并判定i*100+j*10+k与i*i*i+j*j*j+k*k*k是否相等，即可确定该三位数是否为水仙花数。其中i的穷举范围应为_____________。--A|B|C|D (A) 1到10； (B) 0到9； (C) 1到9； (D) 0到10；

12. 下面关于递归说法正确的是____________。--A|B|C|D

(A) 在能够使用递归函数的时候，尽量使用递归，因为它可以使得程序变得简洁，易于理解； (B) 递归函数的嵌套调用次数没有限制； (C) 递归函数的执行效率优于非递归函数； (D) 递归关系式和递归结束条件是递归设计的关键；

13. 计算最小值的基本思路是：先假设这组数据中的第一个数为当前的最小值，其余的数依次与当

前最小值进行比较。一旦发现后面待比较的某个数_______当前的最小值，则用该数修改当前的最小值。---A|B|C|D

. .

.

(A) 等于； (B) 小于等于； (C) 大于等于； (D) 不等于；

14. 一个爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，

更恰当的是________。--A|B|C|D

(A) 设计算法，编写程序，提出问题，运行程序，得到答案 (B) 分析问题，编写程序，设计算法，运行程序，得到答案 (C) 分析问题，设计算法，编写程序，运行程序，得到答案 (D) 设计算法，提出问题，编写程序，运行程序，得到答案

15. 数列1，4，7，10，13，……的递推公式为_______。--A|B|C|D (A) f(1)=1;f(n)=n+3 (B) f(1)=1;f(n)=n*2-1 (C) f(1)=1;f(n)=n*2+1 (D) f(1)=1;f(n)=f(n-1)+3

16. 推销员从A城市出发到其它城市推销产品（城市路线图如上），贪心算法实现得到旅行路线为

_______。--A|B|C|D

(A) A→B→C→E→D→A (B) A→B→C→D→E→A (C) A→B→D→C→E→A (D) A→B→D→E→C→A

17. 哈夫曼编码利用的算法是________。---A|B|C|D

(A) 分治策略 (B) 动态规划 (C) 贪心法

. .

.

(D) 回溯法

18. 设有n位选手参加羽毛球循环赛，循环赛共进行n-1次，每位选手要与其他n-1 位选手比

赛一场，且每位选手每天比赛一场，不能轮空。实现循环赛日程表利用的算法是________。---A|B|C|D A. B. C. D.

19. 二分搜索算法是利用______实现的算法。 ---A|B|C|D A. 分治法 B. 动态规划 C. 贪心法 D. 回溯法

20. 上台阶：每一步只能迈上1个或2个台阶，上完10级台阶，一共有多少种走法，下面说法正

确的是_________。---A|B|C|D

(A) 用递归算法，递归关系式为f(n)=f(n-1)+2，共有231种走法 (B) 用递归算法，递归关系式为f(n)=f(n-1)+f(n-2)，共有89种走法 (C) 用递归算法，递归关系式为f(n)=f(n-1)+f(n-2)，共有231种走法 (D) 用递归算法，递归关系式为f(n)=f(n-1)*2，共有89种走法 分治法 动态规划 贪心法 回溯法

21. 使用动态规划方法计算从地点0到地点6的最短路径______。 ---A|B|C|D

(A) 0→1→4→6 (B) 0→3→4→6 (C) 0→2→3→6 (D) 0→2→5→6

. .