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

第第 8 次作业答案次作业答案 16.1-1 16.1-2 16.2-2 16.2-4 16.3-2 54 33 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 是放弃的）是放弃的） ： or 划线部分按上表 di 递增的顺序排即可，答案不唯一 16.5-2（直接给个计算例子说的不清不楚的请扣分）（直接给个计算例子说的不清不楚的请扣分） 题目：题目： 本题的意思是在本题的意思是在 O(|A|)时间内确定性质时间内确定性质 2（性质（性质 2：对：对 t=0，1，2，n，有，有 Nt(A)i,则说明 A 不独立，否则 A 独立。 伪代码： int temp=0; for(i=0;ii）/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 个操作的平摊代价： ) 1()() 1()()()( 1 DiDickDikDicDDcc iiiiii 17.3-2 题目：题目： 答案：答案： 第一步：此题关键是定义势能函数,不管定义成什么首先要满足两个条件 对所有操作 i，)(Di=0 且)(Di=)( 0 D 比如令k j 2i，j,k 均为整数且取尽可能大，设势能函数)(Di=2k; 第二步：求平摊代价，公式是) 1()( DiDicc ii 按上面设置的势函数示例： 当 k=0， i c=2 当 k！=0, i c=3 显然，平摊代价为 O(1) 17.3-4 题目：题目： 答案：答案： 结合课本 p249，p250 页对栈操作的分析很容易有下面结果 17.4-3 题目：题目： 答案：答案： 假设第 i 个操作是 TABLE_DELETE, 考虑装载因子: i =(第 i 次循环之后的表中的 entry 数)/(第 i 次循环后的表的大小)=/ ii numsize 第第 12 次参考答案次参考答案 19.1.1 题目： 答案： (1) 如果 x 不是根，则 degreesiblingx=degreechildx=degreex-1 (2) 如果 x 是根， 则 sibling 为二项堆中下一个二项树的根， 因为二项堆中根链是按根的度数 递增排序，因此 degreesiblingxdegreex 19.1.2 题目： 答案： (1) 如果 x 是 px的最左子节点，则 px为根的子树由两个相同的二项树合并而成，以 x 为 根的子树就是其中一个二项树，另一个以 px为根，所以 degreepx=degreex+1; (2) 如果 x 不是 px的最左子节点， 假设 x 是 px的子节点中自左至右的第 i 个孩子， 则去掉 px前 i-1 个孩子，恰好转换成第一种情况，因而 degreepx=degreex+1+（i-1）= degreex+i; 综上, degreepx degreex 19.2.2 题目： 19.2.3 题目： 19.2.5 19.2.6 第第 13 次