中科大-算法导论作业答案.doc

第8次作业答案
16.1-1

16.1-2

16.2-2

16.2-4

16.3-2
33D:\编程开发\VS2010\myProgram\经典算法大全\练手题1_整数划分\Interger_Partition\Interger_Partition
54D:\编程开发\VS2010\myProgram\经典算法大全\练手题1_整数划分\Interger_Partition\Interger_Partition

16.3-4

第9次参考答案
16.2-5

贪心算法实现，证明不能少，
参考答案：

16.4-1

证明中要三点：1.有穷非空集合 2.遗传性 3.交换性

第10次作业参考答案
16.5-1

题目表格：
ai
1
2
3
4
5
6
7
di
4
2
4
3
1
4
6
wi
10
20
30
40
50
60
70
解答：
解法1：使用引理16.12性质（2），按wi单调递减顺序逐次将任务添加至Nt（A），每次添加一个元素后，进行计算，{计算方法：Nt（A）中有i个任务时计算N0 (A),…,Ni(A)，其中如果存在Nj (A)>j,则表示最近添加的元素是需要放弃的，从集合中删除}；最后将未放弃的元素按di递增排序，放弃的任务放在所有未放弃任务后面，放弃任务集合内部排序可随意。

解法2：设所有n个时间空位都是空的。然后按罚款的单调递减顺序对各个子任务逐个作贪心选择。在考虑任务j时，如果有一个恰处于或前于dj的时间空位仍空着，则将任务j赋与最近的这样的空位，并填入; 如果不存在这样的空位，表示放弃。

答案（a1，a2是放弃的）：
<a5, a4, a6, a3, a7,a1, a2>or <a5, a4, a6, a3, a7,a2, a1>
划线部分按上表di递增的顺序排即可，答案不唯一

16.5-2（直接给个计算例子说的不清不楚的请扣分）
题目：
本题的意思是在O(|A|)时间内确定性质2（性质2：对t=0，1，2，…，n，有Nt(A)<=t, Nt(A)表示A中期限不超过t的任务个数）是否成立。

解答示例：
思想：建立数组a[n],a[i]表示截至时间为i的任务个数，对0=<i<n，如果出现a[0]+a[1]+…+a[i]>i,则说明A不独立，否则A独立。
伪代码：
int temp=0;
for(i=0;i<n;i++) a[i]=0; ******O(n)= O(|A|)
for(i=0;i<n;i++) a[di]++; ******O(n)= O(|A|)
for(i=0;i<n;i++) ******O(n)= O(|A|)
{
temp+=a[i];//temp就是a[0]+a[1]+…+a[i]
if（temp>i）//Ni(A)>i
A不独立；
}
17.1-1（这题有歧义，不扣分）
a) 如果Stack Operations包括Push Pop MultiPush,答案是可以保持,解释和书上的Push Pop MultiPop差不多.
b) 如果是Stack Operations包括Push Pop MultiPush MultiPop,答案就是不可以保持,因为MultiPush,MultiPop交替的话,平均就是O(K).

17.1-2
本题目只要证明可能性，只要说明一种情况下结论成立即可

17.2-1

第11次作业参考答案
17.3-1
题目：

答案：

备注：最后一句话展开：采用新的势函数后对i个操作的平摊代价：

17.3-2
题目：

答案：
第一步：此题关键是定义势能函数,不管定义成什么首先要满足两个条件
对所有操作i，>=0且>=
比如令，j,k均为整数且取尽可能大，设势能函数=2k;
第二步：求平摊代价，公式是
按上面设置的势函数示例：
当k=0，=…=2
当k！=0, =…=3
显然，平摊代价为O(1)
17.3-4
题目：

答案：
结合课本p249，p250页对栈操作的分析很容易有下面结果

17.4-3
题目：

答案：
假设第i个操作是TABLE_DELETE, 考虑装载因子=(第i次循环之后的表中的entry数)/(第i次循环后的表的大小)=

第12 次参考答案
19.1.1
题目：

答案：
(1) 如果x不是根，则degree[sibling[x]]=degree[child[x]]=degree[x]-1
(2) 如果x是根，则sibling为二项堆中下一个二项树的根，因为二项堆中根链是按根的度数递增排序，因此degree[sibling[x]]>degree[x]
19.1.2
题目：

答案：
(1) 如果x是p[x]的最左子节点，则p[x]为根的子树由两个相同的二项树合并而成，以x为根的子树就是其中一个二项树，另一个以p[x]为根，所以 degree[p[x]]=degree[x]+1;
(2) 如果x不是p[x]的最左子节点，假设x是p[x]的子节点中自左至右的第i个孩子，则去掉p[x]前i-1个孩子，恰好转换成第一种情况，因而degree[p[x]]=degree[x]+1+（i-1）= degree[x]+i;
综上, degree[p[x]]> degree[x]

19.2.2
题目：

19.2.3
题目：

19.2.5

19.2.6

第13次作业参考答案
20.2-1
题目：

解答：

20.2-3
题目：

解答：

20.3-1
题目：

答案：

20.3-2
题目：

答案：

第14次作业参考答案
这一次请大家自己看书处理