北京航空航天大学算法设计与分析试题答案(软件).pdf

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

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

一.简答题（共10分）略

二.计算题(35分)

1.(6分)对下列各组函数f(n)和g(n),确定f(n)=O(g(n))或f(n)=Q(g(n))或

f(n)=

8(g(n))。

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

2

(2)f(n)=logn+5,g(n)=logn

(3)f(n)=logn,g(n尸Jn

咨：

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

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

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

2.(8分)采用动态规划策略，计算a={5,-37-4,-5,9,-2,10,-3,2}的最大子段和,并

给出这个最大子段和的起始下标和终止下标。[设数组中的元素下标从1开始。]

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

(上述每两行1分，共5分)

最大子段和为17(1分)

(若数组下标从1开始)起始下标：6(1分)，终止下标：8(1分)

(若数组下标从0开始)起始下标：5(0.5分)，终止下标：7(0.5分)

3.（分）设有3件工作分配给3个人，将工作分配给第个人所花的费用为

11ij

ij,现将为每一个人都分配1件不同的工作，并使总费用达到最小。设：

C

345

1

823

C234

3C

2

要求：

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

（1）6

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

2））1

（3）按回溯法有哪些信誉好的足球投注网站解空间树，并利用剪枝策略对应该剪掉的子树打（2分）

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

答：

（1）

1616