杭電算法分析與設(shè)計復(fù)習(xí)提綱

杭電算法設(shè)計與分析復(fù)習(xí)提綱TOC杭電算法設(shè)計與分析復(fù)習(xí)提綱1學(xué)弟學(xué)妹求送點財富1填空題5快速排序的隨機化版本5計數(shù)排序6學(xué)弟學(xué)妹求送點財富這份答案是在2014年上半年總結(jié)，紅色部分為考到的題目，老師沒有對題目做無任何修改選擇判斷蒙一下就可以了40分。簡答題5*8=40分5.2-3求骰子期望值略7.1-4應(yīng)如何修改QUICKSORT，才能使其按非增序進行排序？在劃分子樹組時，將大于主元的元素放左邊，小于主元的元素放右邊7.2-2當(dāng)數(shù)組A的所有元素都具有相同值時，QUICKSORT的運行時間是什么？7.2-4銀行經(jīng)常按照交易時間，來記錄有關(guān)某一賬戶的交易情況，但是，很多人喜歡按照票據(jù)號來收到其銀行對賬單。因此，如何將按交易時間排序轉(zhuǎn)換成按支票編號來排序，就成為一個對幾乎排好序的輸入進行排序的問題。證明在這個問題上，過程INSERT_SORT的性能往往優(yōu)于過程QUIKSORT。 （引用自網(wǎng)絡(luò))對于QUIKSORT來說，輸入一個已排序的數(shù)組屬于最壞的情況，則每次區(qū)間劃分都是最大程度的不對稱。其算法運行的遞歸時間為T(n)=T(n-1)+Θ(n)，算法時間復(fù)雜度為Θ(n^2)；而對INSERT-SORT來說，輸入一個已排序的數(shù)組卻屬于最佳的情況，算法時間復(fù)雜度為O(n)。也就是說當(dāng)輸入一個幾乎排好序的數(shù)組，快速排序趨于最壞的情況，而插入排序卻趨于最佳的情況7.3-2在過程RANDOMIZED_QUIKSORT的運行過程中，最壞情況下對隨機排序產(chǎn)生器RANDOM調(diào)用了多少次？最佳情況下調(diào)用了多少次？以Θ記號形式個給出你的答案。 （引用自網(wǎng)絡(luò))隨機快速排序中，只要區(qū)間包含元素數(shù)目大于1，則需調(diào)用RANDOMIZED-PARTITION，選取主元（pivot）進行區(qū)間劃分，而主元的選取需調(diào)用Random。主元（pivot）一旦被選出來后，就不會在加入到后續(xù)的排序了。直白來說就是，有多少次主元（pivot）選取就有多少次隨機數(shù)生成。另一方面從算法的遞歸二叉樹樹上來看，遞歸樹二叉樹的非葉子節(jié)點可表示一個主元（pivot）；而葉子節(jié)點分為兩種，一種節(jié)點是包含0個元素，另一種節(jié)點是包含1個元素，而且該元素不是主元（pivot）。非葉子節(jié)點和包含1個元素的葉子節(jié)點的數(shù)目之和就是輸入序列的大小n。即遞歸樹的非葉子節(jié)點的數(shù)目就是調(diào)用RANDOM的次數(shù)。調(diào)用RANDOM次數(shù)T(RANDOM)≤n，即T(RANDOM)=O(n)。又根據(jù)二叉樹的性質(zhì)，對于任意一棵二叉樹，如果其葉結(jié)點數(shù)為a，而度數(shù)為2的結(jié)點（非葉子節(jié)點）總數(shù)為b，則a=b+1；對于快速排序的遞歸二叉樹中，非葉子節(jié)點度數(shù)均為2。假設(shè)含有0個元素的葉子節(jié)點數(shù)目a0（≥0），含有1個元素的葉子節(jié)點數(shù)目為a1，所以b=a-1≥a1-1；又b+a1=n，可得b≥n/2-1，即T(RANDOM)=Ω(n)。這里有錯誤8.2-4請給出一個算法，使之對給定的介于0到k之間的n個整數(shù)進行預(yù)處理，并能在O(1)時間內(nèi)回答出輸入的整數(shù)中有多少個落在[a...b]區(qū)間內(nèi)。你給出的算法的預(yù)處理時間為Θ(n+k)。略8.3-4說明如何在O(n)時間內(nèi)，對0~n^2-1之間的n個數(shù)進行排序。把整數(shù)轉(zhuǎn)換為n進制再排序，每個數(shù)有兩位，每位的取值范圍是[0..n-1]，再進行基數(shù)排序引用自/mishifangxiangdefeng/article/details/76858398.4-2桶排序的最壞情況運行時間是什么？如果要在保持其線性運行時間的同時，使最壞情況時間為O(nlgn)，要對算法做什么樣的修改？當(dāng)分布不均勻時，全部元素都分到一個桶中，則O(n^2)，當(dāng)然[算法導(dǎo)論8.4-2]也可以將插入排序換成堆排序、快速排序等，這樣最壞情況就是O(nlgn)。9.1-1證明：在最壞情況下，利用n+(lgn)-2次比較，即可得到n個元素中的第2小元素。（提示：同時找最小元素）.對所有元素，兩個一組比較大小，小的一個進入下一輪比較。一直到比較出最小的元素。此時所有比較結(jié)果構(gòu)成一棵二叉樹。比較次數(shù)為n-1。略詳情百度，懶的打了。9.2-1證明:在RANDOMIZED-SELECT中,對于長度為0的數(shù)組,不會進行遞歸調(diào)用.從RANDOMIZED-SELECT函數(shù)知，長度為0的數(shù)組p=r，那么直接返回A[p].不做下面的隨機劃分和遞歸調(diào)用。9.3-3假定元素的值不同，說明如何才能使快速排序在最壞情況下以O(shè)(nlgn)時間運行.以RANDOMIZED-SELECT作為選擇中值的算法9.3-7給出一個O(n)時間的算法，在給定一個有n個不同數(shù)字的集合S以及一個正整數(shù)k<=n后，它能確定出S中最接近其中位數(shù)的k個數(shù).step1：求出數(shù)組的中位數(shù)的值O(n)step2：計算數(shù)組每個數(shù)與中位數(shù)差的絕對值，存于另一個數(shù)組B中O(n)step3：求出數(shù)組B中第k小的數(shù)retO(n)step4：計算數(shù)組S中與ret差的絕對值小于ret的數(shù)并輸出O(n)其中，step4也可以通過劃分的方法找出數(shù)組S中與ret差的絕對值小于ret的數(shù)13.1-5證明:在一棵紅黑樹中,從某結(jié)點x到其后代葉結(jié)點的所有簡單路徑中,最長的一條是最短一條的至多兩倍.在一棵紅黑樹中，從某結(jié)點x到其后代葉結(jié)點的所有簡單路徑中，最長的一條是最短一條的至多兩倍。反證法：假設(shè)存在一條最長路徑長度是最短路徑長度的2倍多1，即L1=k，L2=2k+1。為保證從根節(jié)點到L1和L2的黑高度相同，最小黑高為k，否則L2上必然出現(xiàn)兩個紅色是父子關(guān)系。那么L2中有k個黑色，k+1個紅色，由于根節(jié)點必須是黑色，那么lL2中必定存在紅色的子節(jié)點不是黑色的情況，因此與假設(shè)矛盾，命題得證。14.1-4寫出一個遞歸過程OS-KEY-RANK(T,k)使得順序統(tǒng)計樹T和某個關(guān)鍵字k為輸入，輸出k的秩（排序）。14.1-5給定含有n個元素的順序統(tǒng)計樹中的一個元素x和一個自然數(shù)i，如何在O(lgn)的時間內(nèi)找到元素x的第i個后繼？15.2-2請給出一個遞歸算法MATRIX-CHAIN-MULTIPLY(A,s,i,j)，使之在給出矩陣序列<A1,A2,...,An>，和由MATRIX-CHAIN-ORDER計算出的表s，以及下標(biāo)i和j后，能得出一個最優(yōu)的矩陣鏈乘法。(初始調(diào)用為MATRIX-CHAIN-MULTIPLY(A,s,1,n))。MATRIX-CHAIN-MULTIPLY(A,s,i,j)if(j>i)x=MATRIX-CHAIN-MULTIPLY(A,s,i,s(i,j))y=MATRIX-CHAIN-MULTIPLY(A,s,s(i,j)+1,j)returnMATRIX_MULTIPLY(x,y)elsereturnAi15.3-2畫出2.3.1節(jié)的過程MERGE-SORT作用于一個包含16個元素的數(shù)組上的遞歸樹。請解釋在加速一個好的分治算法如MERGE-SORT方面，做備忘錄方法為什么沒有效果？沒有重疊子問題16.1-2假設(shè)不再總是選擇第一個結(jié)束的活動，而是選擇最后一個開始、且與之前選入活動兼容的活動。試說明這種方式如何成為一個信心算法，并證明它能得到一個最優(yōu)解。16.2-4Midas教授從Newark開一輛車沿著80號洲際公司到Reno。他車子的油箱在滿的時候可以存放夠跑n英里的汽油，并且他的地圖標(biāo)出子在他的路途中加油站之間的距離。教授希望在路途中盡量少加油。請給出一個高效的方法，來幫助教授決定哪一