第1题:
此题为判断题(对,错)。
第2题:
设求解某问题的递归算法如下:
求解该算法的计算时间时,仅考虑算法Move所做的计算为主要计算,且Move为常数级算法,并设算法Move的计算时间为k,当n=5时,算法F的计算时间为(62)。
A.7k
B.15k
C.31k
D.63k
第3题:
A.分支界限算法
B.动态规划算法
C.贪心算法
D.回溯算法
第4题:
第5题:
考虑一个背包问题,共有n=5个物品,背包容量为W=10,物品的重量和价值分别为:w={2,2,6,5,4},v={6,3,5,4,6},求背包问题的最大装包价值。若此为0-1背包问题,分析该问题具有最优子结构,定义递归式为
其中c(i,j)表示i个物品、容量为j的0-1背包问题的最大装包价值,最终要求解c(n,W)。 采用自底向上的动态规划方法求解,得到最大装包价值为(62),算法的时间复杂度为(63)。 若此为部分背包问题,首先采用归并排序算法,根据物品的单位重量价值从大到小排序,然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量,则得到的最大装包价值为(64),算法的时间复杂度为(65)。
A.11
B.14
C.15
D.16.67
第6题:
不能保证求得0-1背包问题的最优解。
A.分支限界法
B.贪心算法
C.回溯法
D.动态规划策略
第7题:
设求解某问题的递归算法如下: F(int n){ if n==1{ Move(1); } else{ F(n-1); Move(n); F(n-1); } } 求解该算法的计算时间时,仅考虑算法Move所进行的计算为主要计算,且Move为常数级算法,设算法Move的计算时间为k,当n=5时,算法F的计算时间为(42)。
A.7k
B.15k
C.31k
D.63k
第8题:
A.O(n2n)
B.O(nlogn)
C.O(2n)
D.O(n)
第9题:
● (65) 不能保证求得0-1 背包问题的最优解。
(65)
A. 分支限界法
B. 贪心算法
C. 回溯法
D. 动态规划策略
第10题:
0-1背包问题的回溯算法所需的计算时间为(),用动态规划算法所需的计算时间为()。