3. TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距
离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答下列问题。
关于TSP问题的遍历（穷举）算法和贪心算法，下列说法正确的是_____。---A|B|C|D。
(A)对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是贪心算法更快一些，而遍历算法更慢一些；
(B)对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是遍历算法更快一些，而贪心算法更慢一些；
(C)对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求近似解，执行更快一些，而遍历算法是求精确解，执行更慢一些；
(D)对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求精确解，执行更快一些，而遍历算法是求近似解，执行更慢一些；
//本题考查对贪心算法与遍历算法的简单理解
4. 关于TSP的贪心算法的求解思想，下列说法不正确的是_____。---A|B|C|D。
(A)无需对所有可能进行比较，而仅需依照某种办法确定一系列局部最优，将这样系列局部最优解组合就是一个较优解或次优解；
(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) (B) (C) (D)
5x+2y+z=1500； 5x+2y+z=1.5； 5x+2y+z=15； 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) (B) (C) (D)
12. 下面关于递归说法正确的是____________。--A|B|C|D
(A) 在能够使用递归函数的时候，尽量使用递归，因为它可以使得程序变得简洁，易于理解；
1到10； 0到9； 1到9； 0到10；
(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.
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种走法
二分搜索算法是利用______实现的算法。 ---A|B|C|D 分治法 动态规划 贪心法 回溯法
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
22. 假设有3种硬币，它们的面值分别是1元、5角、1角。现在有一个小孩买了价值6元3角的东
西，并给售货员10元钱。当售货员找给小孩零钱时，在各种硬币充足的情况下，如果按贪心算法进行找钱，1元、5角、1角的数量分别是_____。 ---A|B|C|D (A) 2、4、7 (B) 3、1、9 (C) 4、2、2 (D) 3、1、2
23. 用递归求n!, 当n=1时，f(1)=1,否则f(n)=f(n-1)*n。当n=3时，递归调用顺序正确的是________。
---A|B|C|D
(A) f(1) 、f(2) 、f(3)