算法第四章擬考試題

1、算法分析第四章電信1306班試題知識點分布 時間復(fù)雜度分析證明：基于比較的排序算法平均時間復(fù)雜度=O(nlogn) 與=O(nlogn) 。歸并排序的復(fù)雜度分析及優(yōu)化措施時間復(fù)雜度3. 快速排序算法時間復(fù)雜度分析及優(yōu)化措施二排序算法的具體應(yīng)用4.n個數(shù)據(jù)元素，設(shè)計算法輸出其中不相同的數(shù)據(jù)元素，并說明你的算法有多快？要求：輸出時，不改變輸入的順序。（用到了歸并排序知識點）5. 給出情況下，只需7次比較的5個元素排序算法。輸入n個不同元素，輸出其和為m的全部整數(shù)對。給出一個 C ( A B) (B A)的算法給出n個正整數(shù)數(shù)組，將偶數(shù)排在奇數(shù)前邊，并說明算法的比較次數(shù)和移動次數(shù)。（類似快速排序中的

2、一趟比較）9 對一個數(shù)值在(1,100)之間的正整數(shù)數(shù)組進行排序，假設(shè)共有n個元素。三np問題10 用馬步圖判斷回路1.證明：基于比較的排序算法平均時間復(fù)雜時間復(fù)雜度=O(nlogn) 。度=O(nlogn) 與比較排序可以被抽象的視為判定樹。要使排序算 法正確地工作，其必要條件是，n個元素的n!種排列中的每一種都要作為判定樹的一個葉子而出現(xiàn)。對于n個元素來說，判定樹的葉子樹為n!，其高度對應(yīng)最深葉子的深度，而最深葉子的深度對應(yīng)最壞時間，即若要證明就要證明判定樹高度時間復(fù)雜度= O(nlogn)， nlogn)。=由二叉樹的性質(zhì)，深度為h的二叉樹，最多有2h個葉子節(jié)點，因而葉子數(shù)為n!的判定樹

3、高度= log(n!)。所以比較排序的大高度 log(n!)。時間W(n) 判定樹的最即W(n)= log(n!)= log(n) + log(n1)+log(n2)+.+log2+log1=log(n)+log(n1)+log(n2)+.+log(n/2)=(n/2)log(n/2)=(n/2)log(n)n/2=O(nlogn)比較排序的平均時間A(n) 判定樹的平均葉子深度。判定樹的平均葉子深度：葉子數(shù)為n!,高度=log(n!)Logn!1高度，其葉子數(shù)至多為2logn!1=n!/2縮放： 將高度logn!的葉子節(jié)點（n!/2個）的高度都縮放為0剩余n!/2個葉子的高度均為log(n!

4、)2歸并排序的復(fù)雜度分析及優(yōu)化措施1.復(fù)雜度分析在次的情況下，n個元素合并，比較次數(shù)為n1因此W(n)=Wn/2+Wn/2+n1 其中W(1)=0W(n) = 2W(n/2)+n1= 2(2W(n/4)+n/21)+n1= 4W(n/4)+2n21 遞歸迭代K次其中k=logn W(n)=2k W(n/ 2k)+kn(1+2+3+ 2k1) W(n)=nW(1)+nlogn(n1)W(n)=nlogn(n1)因此歸并排序的時間復(fù)雜度為O(nlogn)(n= 2k )歸并排序的優(yōu)化措施1.不回寫2.不遞歸3.與相結(jié)合4.無逆序（對相對有序的序列來說，可以將有序的部分合為一個集合，減少比較次數(shù)）具

5、體改進的算法描述：A.將原數(shù)據(jù)集合分成若干組，分組策略如下：第一組：從第1個元素a1 開始到第20個元素a20 ，用插入排序排成有序集，從第21個元素起，按無逆序原則向后找到第一個出現(xiàn)逆序的元素ak 為止。那么第一組的元素為,a1 a20 ak .（雜度為O(n2/4)當(dāng)n=16時，排序平均時間復(fù)優(yōu)于歸并）第二組：從ak開始按照找第一組的方法，找出第二組;第三組、第四組依次類推。按此方出與數(shù)據(jù)集分成若干組，在分組的過程中體現(xiàn)排序相結(jié)合和無逆序的改進。B.對劃分的組進行如下處理：假定初始的元素存放在數(shù)組A中，申請同樣大存儲空間的數(shù)組B。奇數(shù)趟歸并排序時（此時元素在數(shù)組A中），B。偶數(shù)趟歸并排序時

6、（此時元素在數(shù)組B中），兩兩相鄰的分組歸并后存放到數(shù)組A。重復(fù)上述操作，直到最后歸并到成一個集合為止。按此方法對組進行歸并排序，體現(xiàn)了不回寫和不遞歸的改進。3.快速排序算法時間復(fù)雜度分析及優(yōu)化措施快速排序選取E時間復(fù)雜度為O(n2)作為軸元素pivot，在調(diào)用partition時讓軸元素與其余各元素比較，以此確定軸元素的位置，在的情況下，每次選取的pivot都是最大或最小，所以關(guān)鍵字比較的次數(shù)為k=2.n(k1)=n(n1)/2 =O(n2)快速排序平均時間復(fù)雜度為O(nlogn)假定序列的每個元素被選為參考元素的可能性相等A(1)=A(0)=0n11A(n)n ( 1 (A)k A(n1k)

7、nk 0n11 2 nA(k )nk 0假設(shè)A(k)=klogknn21121A (n)n 1 kknlogklnknn ln 2k 1k 1n1nk ln k x ln xdx1k 112n ln(n) 114nx ln xdx 2n2412111 A(n) n 12n2(nln(n) 4nln2241(n2 ln(n) 11 n 1n2) 2nln2121nO(logn (1)n 21 2lnnlnnlogn )快速排序的改進方法 與法結(jié)合使用，當(dāng)分割集a4,a3和a4對換；若a1a2,a1和a2對換；若a2a4,a2和a4對換 且a1和a3對換.生成序列為a1a2a4a3a42)將a5以

8、上序列（用折半查找，共需2次比較）結(jié)果可能為：3）.將a3可，用折半查找，最多需要2次比較由1、2、3得，此方法只需7次比較。6.輸入n個元素，輸出其和為m的全部整數(shù)對。首先進行排序，對排好序元素設(shè)置首尾兩個指針low hih,當(dāng)lowhigh時進行如下運算：如果Elow+Ehigh=m,則; low+;high,輸出數(shù)對如果Elow+Ehighm, high當(dāng)Low=high時，程序結(jié)束。7.給出一個的算法C ( A B) (B A)即把A與B中所有不相同的元素組成一個集合解.假設(shè)A中元素個數(shù)為n,B中元素個數(shù)為m.算法：輸入兩個序列A、B分別對A、B進行歸并排序同時掃描A、B,設(shè)兩個指針分

9、別指向A、B的當(dāng)前掃描元素。初始時i、j分別指向A0、B0若AiBj 則將若Bi存入C中，j后移若Ai= Bj 則同時將i、j后移，直到分別出現(xiàn)與其前一個元素值不同的元素為止。d 重復(fù)c直至A、B同時掃描完或某一個掃描完，此時將另一個序列所有剩余元素直接C中即可。歸并排序的時間復(fù)雜度O為(nlog2n lomg) m2掃描的時間復(fù)雜度為O(nm)總的時間復(fù)雜度為Olog2n (nlomg) m28.給出n個正整數(shù)內(nèi)置分奇偶的算法，偶數(shù)排在奇數(shù)前邊，并說明算法的比較次數(shù)和移動次數(shù)。（類似快速排序中的一趟比較）答算法描述第一個元素放入temp中， low指向第一個元素，high指向最后一個元素先從

10、右向左依次掃描判斷high指向的元素的奇偶，Void partion (* a ,n)low=0,high=n1;temp=a0; While(lowE(low+)While(ahigh是奇數(shù)&high=0) high;然后再從右向左掃描判斷l(xiāng)ow指向的元素的奇偶性若E(low)為偶數(shù) low +If(high!=0)alow+=ahigh;While a low 是偶數(shù)&lowE(high)3 若lowE(low)中 程序結(jié)束。If(high!=0&low!=n1)Alow=temp;本算法在比較次數(shù)上：因為第一個元素沒有參加比較，故為n1次在移動元素次數(shù)上，是來回移動的，情況下，n1個元素

11、都要相互移動，為n1次，還要將首位置元素移動到temp和從temp移入最終空位 2次，共需要n1+2次。9 對一個數(shù)值在(1,100)之間的數(shù)組進行排序，假設(shè)共有n個元素。試給出基數(shù)排序的空間消耗，桶數(shù)，總需要時間。給出在基數(shù)排序過程中找出n個元素（n10）前10個最大的算法?？臻g復(fù)雜度：桶的個數(shù)m(如m取100),此時只需一次裝桶倒桶完成排序。n個元素需要n個空間存放，還需要n個鏈表(2n)空間，因此總共需要(3n+m)個空間.時間復(fù)雜度：在元素鏈表時，將元素鏈頭，這樣的時間為O(n)，然后將m個桶中的元素鏈接到一起所需要的時間為O(m) ，所以基數(shù)排序所需的時間為O(m+n) 。（2）算法：1 清桶2 把a0，a2，an1依次裝桶，不考慮相同元素被選出的前后順序。3從最大的桶開始，依桶的序號遞減依次倒桶，直至夠10個元素為止。馬步圖判斷回路10n,m)/構(gòu)建gijvoid GetGraph(for( i = 0;il;i+) for(j = 0;jl;j+)gij = 0;for(i= 0;il1;i+)ri = i/n; ci = i%n;for(j=i+1