數(shù)據(jù)結(jié)構(gòu)習(xí)題課7

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題數(shù)據(jù)結(jié)構(gòu)習(xí)題 第第 7 章章吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院谷方明第第7章作業(yè)章作業(yè)7-2l若對(duì)序列（若對(duì)序列（7，3，1，8，6，2，4，5）按從?。┌磸男〉酱笈判颍?qǐng)寫出冒泡排序的第一趟結(jié)果。到大排序，請(qǐng)寫出冒泡排序的第一趟結(jié)果。l參考答案 3 ，1， 7， 6，2，4，5 ， 87-3l設(shè)文件（R1，R2，Rn）以單鏈表方式表示，指針變量FIRST指向表頭結(jié)點(diǎn)，且表中的結(jié)點(diǎn)結(jié)構(gòu)為：l其中KEY為該結(jié)點(diǎn)的關(guān)鍵詞域，LINK為鏈接域。請(qǐng)給出這種線性表的直接插入排序算法，并要求算法的時(shí)間復(fù)雜度為O(n2)，且算法是穩(wěn)定的。KEYLINKl算法InsertSort(FIRST. FIRS

2、T) /*對(duì)單鏈表直接插入排序, FIRST指向表頭結(jié)點(diǎn)*/IS1邊界 IF(LINK(FIRST)=NULL OR LINK(LINK(FIRST)=NULL ) THEN RETRUN.IS2插入排序 q LINK(FIRST). q0 LINK(q). WHILE(qNULL)( p LINK(FIRST). p0 FIRST. WHILE(KEY(p)=KEY(q) AND LINK(p)q) DO (p0p.pLINK(p).). IF(KEY(p) KEY(q) ) THEN( LINK(q0)LINK(q).LINK(p0) q. LINK(q) p. q LINK(q0).).

3、 ESLE (q0 q. q LINK(q0).). ) 7-5l設(shè)計(jì)一算法，在盡可能少的時(shí)間內(nèi)重排數(shù)設(shè)計(jì)一算法，在盡可能少的時(shí)間內(nèi)重排數(shù)組，使所有取負(fù)值的關(guān)鍵詞放在所有取非組，使所有取負(fù)值的關(guān)鍵詞放在所有取非負(fù)值的關(guān)鍵詞之前，并分析算法的時(shí)間復(fù)負(fù)值的關(guān)鍵詞之前，并分析算法的時(shí)間復(fù)雜度。雜度。l基本思想：以0為基準(zhǔn)記錄，使用快速排序的一次分劃過程即可，時(shí)間復(fù)雜度為O(n).算法Part(A,n.A)/*以0為基準(zhǔn)元素一次分劃*/P1 初始化 i1 . jn.P2以0分劃 WHILE ij DO ( WHILE Ki0 AND i0 AND iRj+1)時(shí)才會(huì)發(fā)生交換，關(guān)鍵詞相同的記錄不會(huì)發(fā)生交

4、換，即相同位置不變，因此是冒泡排序算法是穩(wěn)定的。7-10l類似于冒泡過程（從下到上），與之對(duì)應(yīng)的是下沉過程（從上到下）。如果排序是冒泡和下沉的交替過程，證明如果經(jīng)過一趟冒泡和一次下沉后發(fā)現(xiàn)Rj和Rj+1（1jn1）沒有交換，則它們已經(jīng)進(jìn)入最終排序位置。參考答案參考答案l證明：l如果經(jīng)過一趟冒泡和一次下沉后發(fā)現(xiàn)Rj和Rj+1（1jn1）沒有交換，那么有 R1=R2=R3=Xi+1.key) ( Xi Xi+1. change 1.) for i 2 to n-1 step 2 /偶交換偶交換 if (Xi.keyXi+1.key) ( Xi Xi+1. change 1.) ) l(1)最好情況

5、下，比較一趟每趟中奇交換偶交換最好情況下，比較一趟每趟中奇交換偶交換比較次數(shù)共比較次數(shù)共(n-1)次，無記錄交換次，無記錄交換 /正序正序l(2)最壞情況下比較最壞情況下比較 (n/2) +1趟，總比較次數(shù)為趟，總比較次數(shù)為(n-1)*(n/2+1）次每次比較都交換，總交換次數(shù)為）次每次比較都交換，總交換次數(shù)為(n-1)*n/2 或或 (n-1)*3n/2 /逆序逆序l(3)最好時(shí)間最好時(shí)間O(n)最壞時(shí)間最壞時(shí)間O(n2)平均時(shí)間平均時(shí)間O(n2) (書上書上P201反序?qū)Φ钠骄鶖?shù)反序?qū)Φ钠骄鶖?shù))正確性證明：數(shù)學(xué)歸納法正確性證明：數(shù)學(xué)歸納法l對(duì)元素個(gè)數(shù)n進(jìn)行歸納l當(dāng)n=1是，算法正確l假設(shè)當(dāng)

6、n=k時(shí)，算法能對(duì)n個(gè)元素的數(shù)組進(jìn)行排序，則當(dāng)n=k+1時(shí)，進(jìn)行一趟分劃后,軸心元素Rs進(jìn)入了最終排序應(yīng)在的位置Ri，即Ri之前的元素RsRi-1都小于等于Ri，Ri之后的元素Ri+1Re都大于等于Ri。由于RsRi-1,Ri+1Re任意一部分最多為k個(gè)，按照假設(shè)，都能正確排序。因此，該算法能對(duì)全部k+1個(gè)元素正確排序。7-24l填充如下排序算法中的方框，并證明該算法的填充如下排序算法中的方框，并證明該算法的正確性正確性. (實(shí)質(zhì)是一趟快速排序算法實(shí)質(zhì)是一趟快速排序算法)l算法算法PartA(R,s,e)/分劃文件分劃文件(Rs,Rs+1,Re),且且Ks-1=-,Ke+1=+PA1初始化初始

7、化 i s. j . K Ks. R Rs.e+1lPA2分劃過程分劃過程 while ij do ( jj-1. while do jj-1. if (ij) then ji. else (Ri Rj. i=i+1. while KiK do i i+1. if then Rj Ri.).lPA3 KjKi=M，才會(huì)在輔助堆棧中壓入第1個(gè)元素l當(dāng)n/(22)=M，才會(huì)在輔助堆棧中壓入第2個(gè)元素l，依此類推，l當(dāng)n/(2k)=M，才會(huì)在輔助堆棧中壓入第k個(gè)元素l則 2k = n/M. k=log2(n/M)l因此最多為 floor ( log2(n/M) 個(gè)7-30l證明：用淘汰賽找n個(gè)元素的

8、最大元素正好需要n1次元素比較。 參考答案參考答案l證明：在淘汰賽中，每進(jìn)行一場(chǎng)比賽，即進(jìn)行依次比較，都恰淘汰1個(gè)元素，找到最大元素需要淘汰n-1個(gè)元素，因此需要n-1比較。7-31l證明：用淘汰賽找 n個(gè)元素的最大元素所形成的樹高為log2n . 參考答案參考答案l證明： 當(dāng)n=2K時(shí)，第1輪后剩下n/2=2K-1 ，第二輪后剩下n/4=2K-2 ,依次類推, 第k輪淘汰賽后就剩下1個(gè)選手，就是最大元素。每一輪淘汰賽都對(duì)應(yīng)比賽樹中的一層，因此當(dāng)n=2K時(shí)，比賽樹的最大層數(shù)是k，比賽樹的高度是log2n 當(dāng)n為任意數(shù)時(shí)，總可以找到一個(gè)k，使得2K-1n=2k，只需要k輪淘汰賽就可以最大元素，對(duì)

9、應(yīng)的比賽樹高為k。由2K-1n=2k ，得log2n=k1 AND Ri/21;j=1)/上浮 if(aj aj1) swap(aj, aj1); 7-36l文件(R1，R2，Rn)是一個(gè)堆，1in，請(qǐng)給出一個(gè)算法，該算法從(R1，R2，Rn)中刪除 Ri，并使刪除后的文件仍然是堆，要求算法的時(shí)間復(fù)雜度為O(log2n) .參考答案參考答案l算法Delete(R,n,i.R,n)/*在堆中刪除元素Ri，從上往下調(diào)整堆*/D1 Ri與Rn交換 Ri Rn. n n-1. D2 從上往下調(diào)整，稱下沉 ji. WHILE(2*jRj OR 2*j+1Rj ) DO( y 2*j. IF(2*j+1R

10、2*j ) THEN y y+1. Rj Ry. j y. ) C+int hMAXN;int n=0;void delete(int i)hi=hn-; while(2*i hi | 2*i+1hi ) int y=2*i; if( y+1hy) y+; swap(hi,hy); i=y; 7-49l填充如下排序算法中的方框，并討論該算法的填充如下排序算法中的方框，并討論該算法的穩(wěn)定性穩(wěn)定性. l算法算法C(R，n)/*比較計(jì)數(shù)，本算法按關(guān)鍵詞比較計(jì)數(shù)，本算法按關(guān)鍵詞K1，K2，Kn排序記排序記錄錄R1，R2，Rn . 一維數(shù)組一維數(shù)組COUNT1 : n用來記用來記錄各個(gè)記錄的排序位置錄各

11、個(gè)記錄的排序位置*/C1 FOR i=1 TO n DO . C2 FOR i=n TO 2 DO FOR j=i1 TO 1 STEP 1 DO IF THEN COUNTj COUNTj+1 ELSE 穩(wěn)定性討論穩(wěn)定性討論該算法是穩(wěn)定的該算法是穩(wěn)定的7-50l有一種簡(jiǎn)單的排序算法，叫做計(jì)數(shù)排序(Count Sorting). 這種排序算法對(duì)一個(gè)待排序的表(用數(shù)組表示)進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。必須注意的是，表中所有待排序的關(guān)鍵詞互不相同，計(jì)數(shù)排序算法針對(duì)表中的每個(gè)記錄，掃描待排序的表一趟，統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵詞比該記錄的關(guān)鍵詞小，假設(shè)針對(duì)某一個(gè)記錄，統(tǒng)計(jì)出的計(jì)數(shù)值為c，那么，這個(gè)記錄在新的有序表中的合適的存放位置即為c .l (1) 給出適用于計(jì)數(shù)排序的數(shù)據(jù)表定義。l(2) 對(duì)于有n個(gè)記錄的表，關(guān)鍵詞比較次數(shù)是多少？l(3) 與簡(jiǎn)單選擇排序相