《算法導(dǎo)論》習(xí)題答案12、13、14章

1、習(xí)題解答 排序和順序統(tǒng)計(jì)學(xué)第6章 堆排序6.1-3 由大根堆性質(zhì)可知，任意子樹(shù)的根節(jié)點(diǎn)為最大元素。6.1-5 遞增數(shù)組是小根堆。遞減數(shù)組是大根堆。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、) 復(fù)雜度：O(logn)第6章 堆排序6.2-6 構(gòu)造最壞情況，A1元素最小，以A2，A3 為根的子樹(shù)均為最大堆。 則從A1至葉結(jié)點(diǎn)每步調(diào)用MAX-HEAPIFY，運(yùn)行時(shí)間為 ，則最壞運(yùn)行時(shí)間為(lgn)。6.3-3 h=0時(shí)，最后一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)標(biāo)號(hào)為 ,高度為0結(jié)點(diǎn)至多有 假設(shè)高度為k的節(jié)點(diǎn)至多有 ，則高度為k+1的節(jié)點(diǎn)至多有 ，由歸納假設(shè)得證。第6章 堆排序6.4-3 不論遞增還是遞減，時(shí)間均為O(nlgn) 6.4-4 最壞情況下，n1次調(diào)用MAX-HEAPIFY，運(yùn)行時(shí)間為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 遞歸式為 ，時(shí)間復(fù)雜度為 。7.2-3 同上7.4-2 最優(yōu)情況時(shí)遞歸式為 ，時(shí)間復(fù)雜度為7.4-3 略 第8章 線性時(shí)間排序8.2-1 略8.2-3 算法正確,但不穩(wěn)定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章 線性時(shí)間排序8.3-1 略8.3-2 1)穩(wěn)定：插入排序，合并排序 2)為每個(gè)元素增加一個(gè)域pos，值為元素在原數(shù)組中的下標(biāo)，比較時(shí)遇到相等的元素就由它們的pos域的值來(lái)決定這兩個(gè)元素的大小，這樣最后的排序結(jié)果就是穩(wěn)定的。 附加空間是O(n)，附加時(shí)間在最壞情況下是O(n2) 。8.3-4 整數(shù)用n進(jìn)制表示k=n 共需位數(shù) 由引理8.3，基數(shù)排序時(shí)間復(fù)雜度為第8章 線性時(shí)間排序8.4-1 略8.4-2 1）最壞運(yùn)行時(shí)間為O(n2)，即所有元素都落在同一桶內(nèi)，插入排序n元素所需時(shí)間。 2）將同一桶內(nèi)的排序算法改為復(fù)雜度為O(nlgn) 的穩(wěn)定排序算法。

6、第9章 中位數(shù)和順序統(tǒng)計(jì)學(xué)9.1-1 按照競(jìng)爭(zhēng)樹(shù)的辦法求最小值需n-1次比較，然后在 個(gè)與最小值比較過(guò)的元素中求出最小值即為原來(lái)n個(gè)元素的次小值，需 次比較，所以共需 次比較。 第9章 中位數(shù)和順序統(tǒng)計(jì)學(xué)9.1-2 某個(gè)元素與其它元素間的大小關(guān)系稱作一條信息，最大元素包含n-1條信息，最小元素也包含n-1條信息，同時(shí)求出最大和最小元素就需要獲得2n-2條信息。 未比較過(guò)的元素記為N，比較后較小的元素記為S，較大的元素記為L(zhǎng)，則每次比較獲得的信息數(shù)： 最壞情況下，只能在兩個(gè)未比 較過(guò)的元素間比較才能得到兩 條信息，其余的比較至多得到 一條信息，未比較過(guò)的元素至 多有n個(gè)，則為了得到2n-2條消 息至少需要 次比較。 比較元素最 多最 少NN22NS21NL21LL11LS20SS11第9章 中位數(shù)和順序統(tǒng)計(jì)學(xué)9.3-1 1)大于x的元素至少為 2)同上，第9章 中位數(shù)和順序統(tǒng)計(jì)學(xué)9.3-2 大于x的數(shù)至少有3n/10-6, n140時(shí)，易證3n/10-6 n/4 小于x的數(shù)同理。9.3-4 通過(guò)比較得到第i小元素，每次保留比較信息。 在比較過(guò)程中比這個(gè)元素小的元素構(gòu)成的集合即為i 1個(gè)小數(shù)集合，而比較過(guò)程中比這個(gè)元素大的元素則構(gòu)成了n i 個(gè)大元素集合。不需要增加比較次數(shù)。第9章 中位數(shù)和順序統(tǒng)計(jì)學(xué)9.3-7 1. 找到 S的中位數(shù)i. 2. 構(gòu)