重庆大学网院算法设计分析第3次作业答案
第3次作业一、填空题（本大题共40分，共 10 小题，每小题 4 分）
1. 程序的性能一般指程序的空间复杂性和 ______ 复杂性。
2. 算法的时间复杂度随着问题规模n的增大而 ______ 。
3. 最优子结构性质的含义是_____。
4. 在n加倍的情况下，一个O(2n)的算法计算时间增长 ______ 倍。
5. 下列关于算法的说法正确的是______ . (填上正确的序号)①某算法可以无止境地运算下去 ②一个问题的算法步骤不能超过1万次 ③完成一件事情的算法有且只有一种④设计算法要本着简单方便可操作的原则。
6. Edmonds-Karp算法规定，在剩余网络中采用 ______寻找______路径作为增广路径
7. 对于01背包问题，如果物品5的重量为12，价值为10，则OPT(5,10)= _____。
8. 常见的指数时间限界函数：O(2n)、O(nn)、O(n！)按从小到大排列： ______。
9. 三数取中划分法的快速排序比基本的快速排序的实际计算效率高，是因为________________。
10. Edmonds&Karp算法相对于Ford-Fulkerson算法的优点是______。
二、简答题（本大题共20分，共 5 小题，每小题 4 分）
1. 下面程序段的所需要的计算时间为___________
int MaxSum(int n, int *a, int &besti, int &bestj) {
int sum=0;
for(int i=1;i<=n;i++){
int thissum=0;
for(int j=i;j<=n;j++){
thissum+=a;
if(thissum>sum) {
sum=thissum;
besti=i;
bestj=j;
}
}
}
return sum;
}
2. 为什么一般情况下，讨论的时间复杂度均是最坏情况下的时间复杂度？
3. 设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; j=0;
while(i<=n)
{
if (i>j) j++;
else i++;
}
(2)x=n;y=0
while (x>=(y+1)*(y+1)) y++;
(3) x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++;
4. 设file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.gif是一个流网络，f为G的流，(S,T)为G的一个割，证明|f|=f(S,T)。
5. 举反例证明0/1背包问题若使用的算法是按照单位重量价值的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解。
三、问答题（本大题共40分，共 5 小题，每小题 8 分）
1. 简述什么是贪心选择性质？
2. 描述Ford-Fulkerson算法基本步骤。
3. file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image004.gif
该递推方程可用递推法展开求解
4. 分治法与递归法的联系与区别？
5. 具体解释算法的五个特性？
在做作业，求解题参考资料。
页:
[1]