算法设计与分析 试卷I

1、请给出算法的定义，并描述算法具备的基本特性（10分）

参：

⏹正确性：对于符合输入类型的任意输入数据，都产生正确的输出。

⏹有效性：每一步指令能够被有效的执行，并且规定了指令的执行效果，结果应该具有的数据类型，而且是可以预期的。

⏹确定性：每一步之后都要有确定的下一步指令。

⏹有穷性：有限步内结束

2、    请用分治法编写求解下列问题的算法，并分析算法效率。（15分）

输入：按非降序排列的n个元素的数组A[1，……，n]和元素x

输出：如果x=A[j]，责输出j；否则输出0。

参:

low1

highn;

j0

while (low<=high) and (j0)

   mid(loe+high)/2

if x=A[mid] then jmid

else if xelse lowmid+1

end while

return j

3、假设图书馆对特种图书的借阅每本每天收取的租金为元。某学生一次性借出了本特种图书，该生阅读第本图书所需要的时间为天，她连续阅读完一本图书后再开始阅读另一本，阅读完的图书及时送还。为节约租金，请你用贪婪算法设计策略为她设计一个本图书的阅读顺序，使得她付给图书馆的租金最少。要求：（15分）

1）请写出你设计的贪婪算法， 并输出图书的阅读顺序。

2）证明算法中的贪婪策略可以获得最优解。

贪婪策略：1）

2）反证法

4、请写出阵链A1  A2  An 最优相乘次数的动态规划矩算法的递归解，并求A1  A2 A3 A4的最优相乘次数和对应的括号放置位置填写在表中。其中A1 、A2、A3、A4的维数如下表。（15分）

参：

5、求下图的强连通分支，给出每个分支的发现时刻和结束时刻。（15分）

参

6、求下图的最小生成树。（15分）

参

7、某网络流图如图6所示，s为源点，t为汇点， 分子表示流量， 分母表示容量。请：（15分）

a)求其剩余流图，如有增流通路，请标出一条增流通路；

b)求st的最大网络流，并在图上面标出最小切割；

参：