1、
2008级软件学院《算法分析与设计分析》试题A卷
一、选择题
1. 以下是描述有关算法设计的基本步骤：
问题陈述 算法分析 模型拟制 算法表示 算法设计 算法确认 测试程序
其中正确的顺序是
A． B.
C. D.
2. 以比较为基础的分类算法在最坏情况下的时间下界是
A．Ω ( nlogn ) B. O( nlogn ) &
2、nbsp;C. O( logn ) D. Ω ( logn )
3. 若可靠性Φ可以取负数，则最优性原理对可靠性设计问题
A. 成立 B.不成立 C. Φ≥1时成立 D. Φ≤1时成立
4. 以下问题中能用贪心方法求解的是
A．0/1背包问题 B. 8皇后问题
C．最优归并模式问题 D. 子集
3、和数问题
5. 对于问题状态S，由根到S的那条路径确定了这个解空间中的一个元组，那么状态S称为
A．问题状态 B．解状态 C．解空间状态 D．答案状态
二、简答题
1. 简述回溯算法的基本思想，并举例说明。
2. 举例说明如何用分治法求解问题。
3. 请写出分治策略的抽象化控制方法，并给出必要的注释和说明。
4. 已知T(1)=1,a和b均为常数且a=b=1，求解递归关系式T(n)=aT(n-1)+bn.
三、证明题
1.证明：O(f(n))+O(g(n))=O(max{f
4、n),g(n)})
2.证明：在带有期限的作业排序中，设J是k个作业的集合，σ=i1i2…ik是J中的作业的一种排列，它使得di1≤di2≤…≤dik。J一个可行解，当且仅当J中的作业可以按照δ的次序处理且每个作业均能在期限前完成。
四、 计算题
1. 对于有a，b两台设备的流水线调度问题，设数组A(n),B(n)分别存储a，b的任务完成时间。A=（5,9,7,3,1），B=（4,6,10,8,2），
(1) 给出这五个作业的非抢先最优调度序列；
(2) 画出调度图；
(3) 求此调度的完成时间；
1. 若n=4，用（a1，a2，a3，a4）构造最优二分检索树，
5、P(1:4)=(2,2,2,3),Q(0:4)=(2,1,3,2,1)
请回答下列问题：
(1) 画表计算（W,C,R）
(2) 画出最优二分检索树（多个解情况给一个即可）
2. 已知有5个物品，物品的重量分别为（w1,w2,w3,w4,w5）=（10,15,29,25,30），效益值分别为(p1,p2,p3,p4,p5)=(20,20,30,35,30),背包可承受的重量M=45.
(1) 如果包装时可以将某一物品的一部分装包，请给出利用贪心方法求解获得最优效益值的包装策略（要求详细过程，并给出求解此问题的最优解及最优决策序列）。
(2) 如果包装时某一物品要么将物品全部装包，要
6、么不装，请给出利用动态规划方法求解获得最优效益值的包装策略（利用算法6.6（即生成序偶集合Si的方法）求解，要求详细过程并给出求解此问题的最优解及最优决策序列）。
五、 算法题
定义0/1/2背包问题如下：
已知一个容量大小为M>0的背包和n个物品，每种物品i的重量为wi>0，效益为pi>0。假定将xi个物品i放入背包就会得到效益pixi，且xi∈{0,1,2},采用怎样的装包方法才会使装入背包物品的总效益最大？
若用KNAP(l,j,X)表示0/1/2背包问题，fi（X）表示KNAP(l,j,X)最优解的值，其形式化描述如下：
极大化 l≤i≤
7、jpixi
约束条件 l≤i≤j wixi≤X
Xi=0,1或2，且l≤i≤j
请回答下列问题：
1) 给出0/1/2背包问题中最优解的递推公式（已知0/1背包问题中求最优解递推公式如下：对i>0，fi（X）=max{ fi-1（X），fi-1（X-wi）+pi}；对X≥0，f0（M）=0；对X<0，f0（M）=—∞）；
2) 假设背包容量X为整数，请编写一个算法来计算最优解，并确定每个xi的值；
3) 请简要分析你所设计的算法在最坏情况下的空间和时间复杂度。
（要求：概要描述算法的思想；在关键的地方给出简明的注释；算法可以使用c或sparks语言实现）
浙ICP备2021020529号-1 | 浙B2-20240490 
