c语言背包问题_背包问题贪心算法_背包问题 贪心算法(3)

4已知输入向量a=（1,3,4，-2），给出用FFT的蝶形操作求输出向量y的结果，并分析出FFT的计算时间复杂度。

1.采用递归算法求递归方程F(n)=F(n-1(+F(n-2)，算法描述如下（就是递归fibonacci！）

问：算法共需要进行多少次递归调用（算法中没引用F(i)一次称为一次递归调用）。有没有更好的算法来计算F(n)?若有请描述算法并分析复杂度。

2.如下算法是否产生平均分布的随即置换？为什么？

Permute-With-All(A)

n←length(A)

for i←1 to n

swap(A[i],A[RANDOM(1,n)])

注：RANDOM(1,n)随机、等可能地返回整数k，1≤k≤n

3. 能否在给定的s[n]中判断是否存在两个数的和为x，并且时间复杂度是nlgn，如果可以写出程序的伪代码，否则给出理由。

6. 活动选择问题

（1）递归的时间复杂度分析

（2）动态规划的时间复杂度分析

（3）写出一个更优的算法，并且对其进行时间复杂度分析

7. 多项式乘法问题

描述一个高效的算法来解决复数之间的多项式乘法，多项式的系数为复数，未知数也为复数。

并且对此进行时间复杂度分析。

郑55 算法2013考试题

填空：

给一系列的函数，根据渐进性，从大到小排列n^3/2,nlgn,lgn,e^n,n!,n^2

动归的两个性质

贪心的两个性质

1）NP问题： 2）P问题

面试问题 雇一个人的概率： ，雇n个人的概率：

复杂度分为： 和 ；动归是牺牲 复杂度换取 复杂度

使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（ 1 ），在最坏情况下，搜索的时间复杂性为O（ logn ）。

选择：

1摊还排序是（）情况下的（）代价

A最优B最坏C平均D最好

2动态规划的设计思想是a

(a)自底向上 (b)自上而下 (c)从左向右 (d)从右向左

3贪心算法的设计思想是b

(a)自底向上 (b)自上而下 (c)从左向右 (d)从右向左

4以下哪一个更可能描述实际一个有效的算法d

(a) (b) (c) (d)

5蝶形操作的设计思想是a

(a)分治法 (b)贪心算法 (c)动态规划 (d)回溯

6以下哪一个不是NPC问题

(a)单源最短路径 (b)巡回售货员问题 (c)布尔可满足性问题 (d)大数分解

7以下哪个不是几何研究中的基本操作

(a)+ (b)— (c)× (d)/

8哪个问题不能用贪心算法解决

(a)活动安排 (b)哈夫曼编码 (c)分数背包 (d)0-1背包

9哪个问题不能用动态规划解决c

(a)分数背包 (b)0-1背包 (c)最长简单路径 (d)最短简单路径

10插入排序的最好时间复杂度是a

(a)n (b)n^2 (c)nlgn (d)lgn

11归并排序的时间复杂度是c

(a)n (b)n^2 (c)nlgn (d)lgn

12算法分析中，记号O表示（B），记号Ω标售（A）,记号Θ表示（D）

A 渐进下界 B 渐进上界 C 非紧上界 D 紧渐进界 E 非紧下界

13.n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下 ( A ) 说法不正确？A

A 让水桶大的人先打水，可以使得每个人排队时间之和最小

B 让水桶小的人先打水，可以使得每个人排队时间之和最小

C 让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水

D 若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-23877-3.html