1、
算法分析中，记号O表示（ ）
?
A、 渐进上界
? B、 非紧上界
? C、 非紧下界
? D、 非紧下界 正确答案是 A 2、 在找零钱问题中，收银员算法中所应用的贪心规则的最恰当描述是 （ ）。
? ? ? ?
A、总是选择面值最高的硬币
B、总是选择不超过剩余应找钱数的最大面值的硬币 C、总是选择面值是10，5的倍数的硬币 D、总是选择面值最小的硬币 正确答案是 B 3、 由边界条件出发,通过递推式求f(n)的值,从边界到求解的全过程十分清楚的是（ ）
? ? ? ?
A、贪心 B、递推 C、递归 D、概率 正确答案是 B 4、
考虑最长公共子序列问题的下述递归表达式，
如果全部子问题组织在一个c[i,j]的二维表格中，则c[i,j]不依赖于下述哪个子问题 ：（ ）。
? ? ? ?
A、同一行的上一列 B、同一列的上一行 C、上一行的上一列 D、同一行的下一列 正确答案是 D 5、 算法的时间复杂度是指（）
? ? ? ?
A、执行算法程序所需要的时间 B、算法程序的长度
C、算法执行过程中所需要的基本运算次数 D、算法程序中的指令条数 正确答案是 C 6、 活动选择问题就是在所给的活动集合中，选出（ ）的相容活动子集。
? ? ? ?
A、当前可选活动中结束时间最早的活动 B、当前可选活动中开始时间最早的活动 C、当前可选活动中冲突数量最少的活动 D、当前可选活动中持续时间最长的活动 正确答案是 A 7、
一个长度为n英寸的钢管的最优切割问题，总共有( )个不同的子问题。
? ? ? ?
A、n+1 B、n2 C、nlogn D、logn 正确答案是 A 8、 最优二叉搜索树的时间复杂度为（ ）。
? ? ? ?
A、O(n) B、O(n!) C、O(n) D、O(nlogn) 2
正确答案是 D 9、 算法的每种运算必须要有确切的定义,不能有二义性,以下符合算法确定性运算的是（ ）
? ? ? ?
A、5/0
B、将6或7与x相加 C、未赋值变量参与运算
D、f(n)=f(n-1)+2,f(1)=10,n为自然数 正确答案是 D 10、 对于三个物体的背包问题，问题相关的数据为n=3, M=20,P=(25,24,15),W(18,15,10)。 下面给出的四个可行解中，最好的是（ ）
? ? ? ?
A、(1/2，1/3，1/4) B、(1，2/15，0) C、(0，2/3，1) D、(0，1，1/2) 正确答案是 D 11、 递归函数f(n)=f(n-1)+n(n>1)的递归出口是( )。 ? ? ? ?
A、f(0)=0 B、f(1)=1 C、f(0)=1 D、f(n)=n 正确答案是 B 12、
下面关于快速排序的说法，正确的是（ ）
?
A、
快速排序的速度和数据无关，是一个固定的值
? B、
快速排序的速度在分解的均匀的时候效果最好，速度最快
? C、
快速排序主要的时间花在合并上面
? D、
快速排序在分解均匀的适合速度最慢 正确答案是 B 13、 下面关于货郎担问题的描述，正确的是（ ） ?
A、货郎担问题是求取具有最大成本的周游路线问题
算法设计分析重庆大学练习题库及答案
