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

14.哈弗曼编码的贪心算法所需的计算时间为 ( B )。

A O(n2n) B O(nlogn) C O(2n) D O(n)

15.下面关于NP问题说确的是(B )

A NP问题都是不可能解决的问题

B P类问题包含在NP类问题中

C NP完全问题是P类问题的子集

D NP类问题包含在P类问题中

大题

四路归并排序：分解时分成四个，合并等其他步骤与二路归并相似，请写出核心算法，并分析时间复杂度。

矩阵链乘积的递归算法

T（n）= 1 n=1

n>=2

请详细分析该算法的时间复杂度

给出最优二叉搜索树的程序代码和p，q概率

根据概率1）求e,w,root，2）画出二叉树的结构3）请说出root[i,j]有什么意义

（见3621大班试卷影印版的第五题）

FFt蝶形操作 见3621大班试卷的影印版第九题

字符串自动机构造，见书

2006-2007学年第二学期《计算机算法设计与分析》试题

院系：软件学院：软件工程年级：2004级

一．简答题（共10分）

略

二．计算题（35分）

１．(6分) 对下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))。

(1) f(n)=3n，g(n)=2n

(2) f(n)=log n + 5，g(n)=log n2

(3) f(n)=log n，g(n)=

答：

(1) f(n) = Ω(g(n)) (2分)

(2) f(n) = θ(g(n)) (2分)

(3) f(n) = O(g(n)) (2分)

2．（８分）采用动态规划策略，计算a=｛5,-3,7,-4,-5,9,-2,10,-3,2｝的最大子段和，并给出这个最大子段和的起始下标和终止下标。［设数组a中的元素下标从１开始。］要求给出过程。

答：

b[1]=5；

b[2]=max{b[1]+a[2]，a[2]}=max{2,-3}=2

b[3]=max{b[2]+a[3]，a[3]}=max{9,7}=9

b[4]=max{b[3]+a[4]，a[4]}=max{5,-4}=5

b[5]=max{b[4]+a[5]，a[5]}=max{0,-5}=0

b[6]=max{b[5]+a[6]，a[6]}=max{9,9}=9

b[7]=max{b[6]+a[7]，a[7]}=max{7,-2}=7

b[8]=max{b[7]+a[8]，a[8]}=max{17,10}=17

b[9]=max{b[8]+a[9]，a[9]}=max{14,-3}=14

b[10]=max{b[9]+a[10]，a[10]}=max{16,2}=16

(上述每两行１分，共５分)

最大子段和为17（1分）

（若数组下标从１开始）起始下标：６（１分），终止下标：８（１分）

（若数组下标从０开始）起始下标：５（0.5分），终止下标：7（0.5分）

３．（11分）设有３件工作分配给３个人，将工作i分配给第j个人所花的费用为Cij，现将为每一个人都分配１件不同的工作，并使总费用达到最小。设：

要求：

（1）画出该问题的解空间树；（６分）

（2）写出该问题的剪枝策略(限界条件)；（1分）

（3）按回溯法搜索解空间树，并利用剪枝策略对应该剪掉的子树打´；（２分）

（4）最终给出该问题的最优值和最优解。（２分）

答：

（1）

1 2 3

2 3 1 3 1 2

1 1 2 2 3 3

3 2 3 1 2 1

16 16 9 9 9 9

╳ ╳ ╳ ╳

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