《算法导论》习题答案12、13、14章

1、习题解答 排序和顺序统计学第6章 堆排序6.1-3 由大根堆性质可知，任意子树的根节点为最大元素。6.1-5 递增数组是小根堆。递减数组是大根堆。6.1-6 不是第6章 堆排序6.2-2 MIN-HEAPIFY(A,i) l-LEFT(i) r-RIGHT(i) if l=heap-sizeA and AlAi then smallest-l else smallest-I if r=heap-sizeA and ArAsmallest then smallest-r if smallest!=I then exchange AiAsmallest MIN-HEAPIFY(A,smallest

2、) 复杂度：O(logn)第6章 堆排序6.2-6 构造最坏情况，A1元素最小，以A2，A3 为根的子树均为最大堆。 则从A1至叶结点每步调用MAX-HEAPIFY，运行时间为 ，则最坏运行时间为(lgn)。6.3-3 h=0时，最后一个结点的父结点标号为 ,高度为0结点至多有 假设高度为k的节点至多有 ，则高度为k+1的节点至多有 ，由归纳假设得证。第6章 堆排序6.4-3 不论递增还是递减，时间均为O(nlgn) 6.4-4 最坏情况下，n1次调用MAX-HEAPIFY，运行时间为O(nlgn)第6章 堆排序6.5-3 HEAP-MINIMUM(A) if heap-sizeA1 then

3、 error”heap underflow” else return A1 HEAP-EXTRACT-MIN(A) if heap-sizeA1 then error”heap underflow” min-A1 A1-Aheap-sizeA heap-sizeAAi then error Ai1 and APARENT(i)Ai do exchange AiAPARENT(i) i-PARENT(i) MIN-HEAP-INSERT(A,key) heap-sizeA-heap-sizeA+1 Aheap-sizeA-+ HEAP-DECREASE-KEY(A,heap-sizeA,key)

4、第7章 快速排序7.1-1 略7.1-2 1）r 2）第7章 快速排序7.2-2 递归式为 ，时间复杂度为 。7.2-3 同上7.4-2 最优情况时递归式为 ，时间复杂度为7.4-3 略 第8章 线性时间排序8.2-1 略8.2-3 算法正确,但不稳定8.2-4 Preprocessing(A,k) for i0 to k do Ci0 for j1 to lengthA do CAj CAj+1 for i1 to k do Ci Ci+Ci-1 Query(C,k,a,b) if ba or bk return 0 if ak then b=k if a1 then return Cb-C

5、a-1 else return Cb第8章 线性时间排序8.3-1 略8.3-2 1)稳定：插入排序，合并排序 2)为每个元素增加一个域pos，值为元素在原数组中的下标，比较时遇到相等的元素就由它们的pos域的值来决定这两个元素的大小，这样最后的排序结果就是稳定的。 附加空间是O(n)，附加时间在最坏情况下是O(n2) 。8.3-4 整数用n进制表示k=n 共需位数 由引理8.3，基数排序时间复杂度为第8章 线性时间排序8.4-1 略8.4-2 1）最坏运行时间为O(n2)，即所有元素都落在同一桶内，插入排序n元素所需时间。 2）将同一桶内的排序算法改为复杂度为O(nlgn) 的稳定排序算法。

6、第9章 中位数和顺序统计学9.1-1 按照竞争树的办法求最小值需n-1次比较，然后在 个与最小值比较过的元素中求出最小值即为原来n个元素的次小值，需 次比较，所以共需 次比较。 第9章 中位数和顺序统计学9.1-2 某个元素与其它元素间的大小关系称作一条信息，最大元素包含n-1条信息，最小元素也包含n-1条信息，同时求出最大和最小元素就需要获得2n-2条信息。 未比较过的元素记为N，比较后较小的元素记为S，较大的元素记为L，则每次比较获得的信息数： 最坏情况下，只能在两个未比 较过的元素间比较才能得到两 条信息，其余的比较至多得到 一条信息，未比较过的元素至 多有n个，则为了得到2n-2条消 息至少需要 次比较。 比较元素最 多最 少NN22NS21NL21LL11LS20SS11第9章 中位数和顺序统计学9.3-1 1)大于x的元素至少为 2)同上，第9章 中位数和顺序统计学9.3-2 大于x的数至少有3n/10-6, n140时，易证3n/10-6 n/4 小于x的数同理。9.3-4 通过比较得到第i小元素，每次保留比较信息。 在比较过程中比这个元素小的元素构成的集合即为i 1个小数集合，而比较过程中比这个元素大的元素则构成了n i 个大元素集合。不需要增加比较次数。第9章 中位数和顺序统计学9.3-7 1. 找到 S的中位数i. 2. 构