吉林大学计算机学院2004级《算法设計与分析期末试题设计与分析》试题A 卷

第1页共2页 学年 第1学期

2004级算法设计与分析期末试题设计与分析 试题A 卷

1、 简答题(每题5分,共20分)

1. 用贪心方法解背包问题时,使用的最优量度标准是什么?对于一下问题实

2. 回溯法执行过程中状态空间树的E 节点能否超过1个?活结点能否超过1个?简述理由

3. 回溯法求解子集和数问题(n=4)的状态空间树中,采用定长元组表示,有多少个问题状态,解状态节点。

4. 求解递归关系式:

的一种排列,它使得12...k

i i i d d d ≤≤≤证明:J 昰一个可行解,当且仅当J 中的作业可以按照δ的次序处理且每个作业均能在其期限前完成。

1. 已知图的邻接矩阵

(1) 按照每对节点间的最短路径算法设计与分析期末试题ALL-PATH,求每对结点间的最短路径长度矩

(2) 求最短路径结点矩阵P 。P(i,j)表示i 到j 的最短路径上第一个经过的结点

(3) 根据P 和4A ,分别给出结點2到结点3,结点4到结点1的最短路径及长度。

时,利用作业排序的更快算法设计与分析期末试题,求解上述作业排序问题的最优解(要求按步骤运行並给出集合树的变化情况,最优解及效益值)

(1) 依次按步骤求(

(1) 给出这五个作业的非抢先最有调度序列并画出调度图。