算法设计与分析(python版)-作业二

参考教材：算法设计与分析（Python版）         作者：王秋芬

1 . 普通 （5分）求递推方程

得到的解是___

O(nlogn)

2 . 普通 （5分）求递推方程

得到的解是___

O(logn)

3 . 普通 （5分）求

递推方程的解是___

O(n^2)

4 . 普通 （5分）求递推方程

得到的解是（）

O(logn)

5 . 普通 （5分）求

递推方程的解是（）

O(n^2)

6 . 普通 （5分）物品可以切割的背包问题的最佳贪心策略不一定能保证装入背包的物品总价值最大。

错误

7 . 普通 （5分）对下图分别用Kruskal算法和Prim算法求最小生成树。

8 . 普通 （5分）磁带最优存储问题：设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li， 1≤i≤n。这n 个程序的读取概率分别是p1,p2,...,pn,且p1+p2+...+pn = 1。如果将这n 个程序按 1,2,....,n 的次序存放，则读取程序i所需的时间tr=c*(P1×L1+P2×L2+...+Pr×Lr)。这n 个程序的平均读取时间为 t1+t2+...+tn。实际上第k个程序的读取概率为ak/(a1+a2+...+an)。对所有输入均假定c=1。磁带最优存储问题要求确定这n个程序在磁带上的一个存储次序，使平均读取时间达到最小。试设计一个解此问题的算法,并分析算法的正确性和计算复杂性。

def MinTime(n,l,p):

t = []

a = 0

for i in range(n):

a=a+p[i] #计算概率和

for i in range(n):

t.append(l[i]*p[i]/a)#存放i个程序的⻓度与读取概率的积

t.sort()#由⼩到⼤到排序

sum_time=0

for i in range(n):

sum_time=sum_time+(n-i) * t[i] #计算n个程序的平均读取时间 sum_time = n*t[0]+(n-1)*t[1]+...+t[n-1]

return round(sum_time,4)#四舍五⼊，保留4位⼩数

if __name__=="__main__":

n = 5

l = [71,46,9,73,35]

p = [872,452,265,120,85]

print(MinTime(n,l,p))

输出结果为： 85.6193

贪心策略：平均读取时间最小的优先

9 . 普通 （5分）设字符m1，m2，…m10的查阅频率依次为：0.05，0.01，0.01，0.10，0.03，0.17，0.0 2，0.24，0.31，0.06。试构造对应的哈夫曼(Haffman)编码，并画出相应的编码树，同时写出ml,m2,…m10的编码。

每个字符的编码为从根节点到该字符所在叶子结点的路径上的0,1组成的串。

10 . 普通 （5分）在10000个元素中找到前100个最大的元素，如果使用以下某个数据结构作为辅助，比较合适的是()

A. 堆

B. 并查集

C. 循环链表

D. 哈希表

11 . 普通 （5分）给定下面的有向、连通带权图

用dijkstra算法，找从源点1到其他各个顶点的最短路径。算法运行若干步以后，得到各数据结构的数据如下（数组下标从1开始，表示顶点编号）： 下标 11 22 3 4 5 6 7 88 S 1 1 0 1 0 1 1 0 dist 0 2 8 1 6 3 3 11 pre 0 1 2 1 7 1 4 7 根据当前状态，可判断从初始状态到当前状态已经做了（）次贪心选择。

A. 1

B. 2

C. 3

D. 4

12 . 普通 （5分）

用Prim算法求解上图的最小生成树，初始时，集合S={a}，集合V-S={b,c,d,e,f,g}，第六步贪心选择的边是（）。

A. （a,b）

B. （c,d）

C. （b,c）

D. （c,f）

13 . 普通 （4分）

用Prim算法求解上图的最小生成树，初始时，集合S={a}，集合V-S={b,c,d,e,f,g}，第三步贪心选择的边是（）。

A. （a,b）

B. （b,c）

C. （c,d）

D. （c,f）

14 . 容易 （4分）

用Prim算法求解上图的最小生成树，初始时，集合S={a}，集合V-S={b,c,d,e,f,g}，第一步贪心选择的边是（）。

A. （a,b）

B. （b,c）

C. （c,d）

D. （c,f）

15 . 容易 （4分）

用Kurskal算法求解上图的最小生成树，第一步贪心选择的边是（）。

A. （a,b）

B. （b,c）

C. （c,g）

D. （c,f）

16 . 普通 （4分）给定一个有向连通带权图G=(V,E),n个顶点,e条边,Dijsktra算法的时间复杂度为()

A. O(n 2)

B. O(n 3)

C. O(eloge)

D. O(nlogn)

17 . 容易 （4分）背包问题: n个物品和1个背包。对物品i,其价值为vi,重量为wi,背包的容量为W。如何选取物品装入背包,使背包中所装入的物品的总价值最大?物品可以分割。该问题的贪心策略是()。

A. 重量小的优先装入背包

B. 体积小的优先装入背包

C. 价值大的优先装入背包

D. 单位重量的价值大的优先装入背包

18 . 普通 （4分）调度问题:有n个客户带来n项任务,每项加工时间已知,设为ti,i=1,2,…,n。从0时刻开始,陆续安排到一台机器上加工。每个任务的完成时间是从0时刻到该任务加工完成的时间。为了使尽可能多的客户满意,我们希望找到是的总等待时间最少的调度方案。该问题的贪心策略是()

A. 加工时间长的优先安排

B. 加工时间短的优先安排

C. 完成时间早的优先安排

D. 等待时间长的优先安排

19 . 容易 （4分）找零钱问题的贪心策略是()

A. 面值大的钱币优先找出

B. 面值小的钱币优先找出

C. 面值小于待找钱数且面值最大的优先找出

D. 以上都不对

20 . 容易 （4分）物品不可拆开的最优装载问题的贪心策略是()

A. 体积大的集装箱优先装

B. 体积小的集装箱优先装

C. 重量大的集装箱优先装

D. 重量小的集装箱优先装

21 . 容易 （4分）会场安排问题的最好的贪心策略是()

A. 在不冲突的情况下，开始时间早的优先安排

B. 在不冲突的情况下，使用时间短的优先安排

C. 在不冲突的情况下，使用时间长的优先安排

D. 在不冲突的情况下，结束时间早的优先安排

22 . 容易 （4分）调度问题的算法设计策略是（）

A. 加工时间短的优先安排

B. 加工时间长的优先安排

C. 等待时间短的优先安排

D. 以上都不对