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

《《算法导论》习题答案12、13、14章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题解答排序和顺序统计学第6章堆排序6.1-3由大根堆性质可知，任意子树的根节点为最大元素。6.1-5递增数组是小根堆。递减数组是大根堆。6.1-6不是第6章堆排序6.2-2MIN-HEAPIFY(A,i)l<-LEFT(i)r<-RIGHT(i)ifl<=heap-size[A]andA[l]A[s

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

3、为O(nlgn)第6章堆排序6.5-3HEAP-MINIMUM(A)ifheap-size[A]<1thenerror”heapunderflow”elsereturnA[1]HEAP-EXTRACT-MIN(A)ifheap-size[A]<1thenerror”heapunderflow”min<-A[1]A[1]<-A[heap-size[A]]heap-size[A]<-heap-size[A]-1MIN-HEAPIFY(A,1)returnminHEAP-DECREASE-KEY(A,i,key)ifkey>A[i]the

4、nerrorA[i]<-keywhilei>1andA[PARENT(i)>A[i]doexchangeA[i]<->A[PARENT(i)]i<-PARENT(i)MIN-HEAP-INSERT(A,key)heap-size[A]<-heap-size[A]+1A[heap-size[A]]<-+∞HEAP-DECREASE-KEY(A,heap-size[A],key)第7章快速排序7.1-1略7.1-21）r2）第7章快速排序7.2-2递归式为，时间复杂度为。7.2-3同上7.4-2最优情况时递归式为，时间复杂度为7.4-3

5、略第8章线性时间排序8.2-1略8.2-3算法正确,但不稳定8.2-4Preprocessing(A,k)fori←0tokdoC[i]←0forj←1tolength[A]doC[A[j]]←C[A[j]]+1fori←1tokdoC[i]←C[i]+C[i-1]Query(C,k,a,b)ifbkreturn0ifa<1thena=1ifb>kthenb=kifa≠1thenreturnC[b]-C[a-1]elsereturnC[b]第8章线性时间排序8.3-1略8.3-21)稳定：插入排序，合并排序2)

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

7、然后在个与最小值比较过的元素中求出最小值即为原来n个元素的次小值，需次比较，所以共需次比较。第9章中位数和顺序统计学9.1-2某个元素与其它元素间的大小关系称作一条信息，最大元素包含n-1条信息，最小元素也包含n-1条信息，同时求出最大和最小元素就需要获得2n-2条信息。未比较过的元素记为N，比较后较小的元素记为S，较大的元素记为L，则每次比较获得的信息数：最坏情况下，只能在两个未比较过的元素间比较才能得到两条信息，其余的比较至多得到一条信息，未比较过的元素至多有n个，则为了得到2n-2条消息至少需要次比较。比较元素最多最少N－N2

8、2N－S21N－L21L－L11L－S20S－S11第9章中位数和顺序统计学9.3-11)大于x的元素至少为2)同上，第9章中位数和顺序统计学9.3-2大于x的数至少有3n/10-6,n≥140时，易证3n/10-6≥n/4小于x的数