大学计算机基础练习试题第1_12讲(1)(1) 下载本文

.

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

(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

. .