发布时间 : 星期六 文章大学计算机基础练习试题第1_12讲(1)(1)更新完毕开始阅读5342b75b70fe910ef12d2af90242a8956aecaa55
.
解组合就是一个较优解或次优解；
(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
. .