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