數(shù)據(jù)結(jié)構(gòu)練習

1、數(shù)據(jù)結(jié)構(gòu)練習1填寫下面表格，對以下幾種排序方法進行比較：排序方法平均時間復雜度最壞情況空間復雜度是否穩(wěn)定選擇排序直接選擇排序O(n 2)O(n2)O(1)不穩(wěn)定堆排序O(nlog 2n)O(nlog 2n)O(1)不穩(wěn)定插入排序直接接插入排序O(n 2)O(n2)O(1)穩(wěn)定拆半接插入排序O(nlog 2n)O(n2)O(1)穩(wěn)定Shell 排序O(nlog 2n)O(nlog 2n)O(1)不穩(wěn)定冒泡排序交換排序O(n 2)O(n2)O(1)穩(wěn)定快速排序O(nlog 2n)O(n2)O(1)不穩(wěn)定歸并排序2-路歸并排序O(nlog 2習題O(nlog2n)O(n)穩(wěn)定n)一填空題O(nlog

2、 2n)O(nlog 2n)O(1)不穩(wěn)定紅黑樹1 進棧序列是 1、 2、 3、 4，進棧過程中可以出棧，則可能的出棧序列有個，不可能的出棧序列是O(N+K) 。O(N+K)O(N+K)穩(wěn)定線性排序計數(shù)排序桶排序O(N)O(N)O(N)穩(wěn)定基數(shù)排序O(d(n+rd)O(d(n+rd)O(rd)穩(wěn)定解釋：時間復雜度O(d(n+rd) ：其中分配為O（ n）；收集為O（ rd）（ r 為基、d 為“分配收集”的趟數(shù)）2 具有 N 個元素的順序存儲的循環(huán)隊列中，假定front 和 rear 分別指向隊頭元素的前一位置和隊尾元素的位置，則判斷隊空的和隊滿的條件分別是f=r和f=rmodm+1。 求 此

3、 隊 列 中 元 素 個 數(shù) 的 計 算 公 式 為 ：(r+m)-f-1) mod m +1。入隊運算：r:=r mod m+1出隊運算：f:=f mod m + 13 單鏈表是非順序線性的鏈式存儲結(jié)構(gòu)。的鏈式存儲結(jié)構(gòu)，鏈棧和鏈隊分別是和4線性表的順序存儲中，元素之間的邏輯關(guān)系是通過定的，在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過訪問決定的。元素存儲地址次序元素存儲指針地址決5深度為 5 的二叉樹至多有結(jié)點數(shù)為31。6 數(shù)據(jù)結(jié)構(gòu)即數(shù)據(jù)的邏輯結(jié)構(gòu)包括順性存儲結(jié)構(gòu)非線性結(jié)構(gòu)三種類型，樹型結(jié)構(gòu)和圖型結(jié)構(gòu)稱為？、鏈式存儲結(jié)構(gòu)非線性結(jié)構(gòu)。、四種基本存儲方法：（ 1）順序存儲方法（2）鏈接存儲方法（

4、3）索引存儲方法（4）散列存儲方法二選擇題1 有一個 10 階對稱矩陣，采用壓縮存儲方式，以行序為主序存儲，1，則 A74的地址為（C）A13B18C33D2 線性表采用鏈表存儲時其存儲地址D。A必須是連續(xù)的B部分地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)不連續(xù)都可以A0040的地址為3 下列敘述中錯誤的是C。A串是一種特殊的線性表，其特殊性體現(xiàn)在數(shù)據(jù)元素是一個字符B棧和隊列是兩種特殊的線性表，棧的特點是后進先出，隊列的特點是先進先出。C線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)D二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表4 一棵二叉樹的順序存儲結(jié)構(gòu)如題圖4-1 所示，若中序遍歷該二叉樹，則遍歷次序為A.56

5、7A.C.DBEGACFH DGEBHFCA 1 2 34B.ABDEGCFHD.ABCDEFGH567891011 12 13 14ABCDEFGH題圖4-18設(shè)一棵二叉樹的順序存儲結(jié)構(gòu)如題圖A完全二叉樹BD深度為3 的二叉樹4-2 所示，則該二叉樹是滿二叉樹C深度為C.4 的二叉樹12345678910111234567題圖4-29設(shè) T 是 Huffman 樹，它具有6 個樹葉，且各樹葉的權(quán)分別為那么該樹的非葉子結(jié)點的權(quán)之和為A。A51B21C 30D491， 2， 3， 4，5， 6。7設(shè)有一無向圖的鄰接矩陣如下所示，則該圖所有頂點的度之和為C。a b c d ea 01110b 1

6、0 1 0 1 c 1 1 0 0 0 d 1 0 0 0 0 e 0 1 0 0 0A8B9C10D 118已知二叉樹的后序遍歷序列是遍歷序列是D。A defbagcB abcdgefCfedbgca ，中序遍歷序列是dfebagc dbaefcgD abdefcg，則該二叉樹的先序9由三個結(jié)點構(gòu)成的二叉樹，共有A3B4C5D6C種不同的形態(tài)。10在一個具有A nBn 個頂點的無向圖中，要連通全部頂點至少需要 n+1 C n/2 D n-1D條邊11對線性表進行折半（二分）查找時，要求線性表必須B。A以順序方式存儲B以順序方式存儲且數(shù)據(jù)元素有序C以鏈表方式存儲D以鏈表方式存儲且數(shù)據(jù)元素有序1

7、2順序查找一個具有n 個元素的線性表，其時間復雜度為A，二分查找一個具有n 個元素的線性表，其時間復雜度為B。2A O(n)B O(log2n)CO(n)D O(nlog 2n)13. 從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列中的正確位置上，此方法稱為直接插入排序；從未排序序列中挑選元素，并將其放入已排序序列中的一端，此方法稱為直接選擇排序；依次將每兩個相臨的有序表合并成一個有序表的排序方法稱為歸并排序；當兩個元素比較出現(xiàn)反序時就相互交換位置的排序方法稱為交換排序；A歸并排序B 選擇排序C交換排序D插入排序三簡述下面的幾個概念：單鏈表， 棧、隊列，排序二叉樹。

8、A四簡述空串和空格串的區(qū)別。五一棵度為 2 的樹與二叉樹有何區(qū)別？BC六試分別畫出具有3 個結(jié)點的樹和具有3 個結(jié)點的二叉樹的所有不同形態(tài)。4-3DEF七已知一二叉樹如題圖所示，1 用二叉鏈表和順序存儲方式分別存儲此二叉樹。畫出GH相應的存儲結(jié)構(gòu)圖。圖 4-32 寫出此二叉樹的中序、先序、后序遍歷序列。八已知一無向圖如題圖4-4所示，請給出該圖的11 每個頂點的度。232 鄰接矩陣43 鄰接表4 按上述的鄰接表寫出廣度和深度遍歷序列。56九已知一組數(shù)據(jù)元素為（46， 75， 18， 54， 15， 27， 42， 39，88， 67）題圖 4-41 利用直接插入排序方法，寫出每次插入后的結(jié)果。

9、2 利用快速排序方法，寫出每趟排序后的結(jié)果。3 利用 2- 路歸并排序方法，寫出每趟歸并后的結(jié)果。4 利用冒泡排序方法，寫出每趟排序后的結(jié)果。十假定一個表為（32， 75，63， 48，94， 25，36， 18，70），散列空間為0.10 ，1 若采用除留余數(shù)法構(gòu)造表，哈希函數(shù)為H（ K） =K MOD 11，用線性探測法解決沖突，試畫出哈希表，并求在等概率情況下的平均查找長度。2 若采用除留余數(shù)法構(gòu)造表，哈希函數(shù)為H（ K） =K MOD 11，用鏈地址法解決沖突，試畫出哈希表，并求在等概率情況下的平均查找長度。十一有 8 個帶權(quán)結(jié)點，權(quán)值為（ 3， 7， 8，2， 6， 10， 14，

10、9），試以它們?yōu)槿~子結(jié)點構(gòu)造一棵哈夫曼樹（要求每個結(jié)點左子樹的權(quán)值小于等于右子樹的權(quán)值），并計算出帶權(quán)路徑長度。十二一對稱陣 A n*n，若只存儲此對稱陣的上半三角元，寫出以行為主序存儲和以列為主序存儲時計算每一元素A ij 存儲地址的公式。十三算法設(shè)計1 寫出在循環(huán)單鏈表L 中查找查找第 i 個元素的算法：SEARCH （ L ， i）。2 設(shè)有如下題圖4-3 的單鏈表，鏈表頭指針為H ，寫一個將鏈表進行逆轉(zhuǎn)的算法，逆轉(zhuǎn)以后的鏈表為題圖4-4 所示。HaaaNULL12n題圖 4-3 單鏈表示意圖HaaaNULLnn-11題圖 4-4 單鏈表示意圖3 假定用一個帶頭結(jié)點的循環(huán)單鏈表表示循環(huán)隊

11、列（循環(huán)鏈隊），該隊列只設(shè)一個隊尾指針，不設(shè)頭指針，試編寫下面的算法：A 向循環(huán)鏈隊中插入一個元素x 的算法（入隊） 。B 從循環(huán)鏈隊中刪除一個結(jié)點（出隊）。4 數(shù)組 AN 存放循環(huán)隊列中的元素， 同時設(shè)兩個變量分別存儲隊尾元素的位置和隊列中實際元素個數(shù)。A 寫出此隊列的隊滿條件。B 寫出此隊列的出、入隊算法。5 設(shè) LA 和 LB 為兩個順序存儲的線性表，且元素按非遞減排列，寫出算法將其合并為LC ，且 LC 中的元素也按非遞減排列。6 已知一個由n 個整數(shù)組成的線性表，請定義該線性表的一種存儲結(jié)構(gòu)，并用C 語言編寫算法，實現(xiàn)將 n 個元素中所有大于等于20 的整數(shù)放在所有小于等于20 的整

12、數(shù)之后，要求算法的時間復雜度為O（ n） , 空間復雜度為O（1）。7 編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。8 編寫一個按層次順序（同一層自左向右）遍歷二叉樹的算法。文中代碼見原文鏈接： 非基于比較的排序在計算機科學中， 排序是一門基礎(chǔ)的算法技術(shù)， 許多算法都要以此作為基礎(chǔ)， 不同的排序算法有著不同的時間開銷和空間開銷。 排序算法有非常多種， 如我們最常用的快速排序和堆排序等算法，這些算法需要對序列中的數(shù)據(jù)進行比較，因為被稱為 基于比較的排序 ?；诒容^的排序算法是不能突破O(NlogN)的。簡單證明如下：N 個數(shù)有 N! 個可能的排列情況，也就是說基于比較的排序算法的判定樹有比較次數(shù)至少為

13、 log(N!)=O(NlogN)( 斯特林公式 ) 。N! 個葉子結(jié)點，而非基于比較的排序，如計數(shù)排序， 桶排序，和在此基礎(chǔ)上的基數(shù)排序，則可以突破O(NlogN)時間下限。 但要注意的是， 非基于比較的排序算法的使用都是有條件限制的， 例如元素的大小限制， 相反，基于比較的排序則沒有這種限制 ( 在一定范圍內(nèi) ) 。但并非因為有條件限制就會使非基于比較的排序算法變得無用， 對于特定場合有著特殊的性質(zhì)數(shù)據(jù)， 非基于比較的排序算法則能夠非常巧妙地解決。本文著重介紹三種線性的非基于比較的排序算法：計數(shù)排序、桶排序與基數(shù)排序。 計數(shù)排序首先從 計數(shù)排序 (Counting Sort)開始介紹起，假

14、設(shè)我們有一個待排序的整數(shù)序列A，其中元素的最小值不小于0 ，最大值不超過K 。建立一個長度為K 的線性表C，用來記錄不大于每個值的元素的個數(shù)。算法思路如下：?掃描序列A，以 A 中的每個元素的值為索引，把出現(xiàn)的個數(shù)填入可以表示A 中值為 i 的元素的個數(shù)。對于 C 從頭開始累加，使Ci-Ci+Ci-1。這樣， Ci的元素的個數(shù)。C 中。此時Ci就表示 A 中值不大于i? 按照統(tǒng)計出的值，輸出結(jié)果。由線性表 C 我們可以很方便地求出排序后的數(shù)據(jù)，定義B 為目標的序列， Orderi為排名第 i 的元素在 A 中的位置，則可以用以下方法統(tǒng)計。CPP1/* Memo: 計數(shù)排序 */23#inclu

15、de 4#include 5#include 6#include 7#include 8usingnamespacestd ;9voidCountingSort( int * A, int * B, int * Order, int N, intK )10 11121314151617181920212223int* C=newint K+1 ;inti;memset ( C, 0, sizeof( int) * ( K+1) ;for( i =1; i =N; i +)/ 把 A 中的每個元素分配C A i + ;for( i =2; i =1; i - )B C A i =A i ;/按照

16、統(tǒng)計的位置，將值輸出到B24 中，將順序輸出到 Order 中2526Order C A i =i ;27C A i - ;2829 30 int main ()31 32int * A, * B, * Order,N =15 ,K =10 ,i ;33A=newint N+1;34B=newint N+1;353637383940414243444546474849Order=newint N+1 ;for( i =1; i =N; i +)A i =rand ()%K+1; /生成 1.K的隨機數(shù)printf( Before CS:/n ) ;for( i =1; i =N; i +)pr

17、intf( %d ,A i );CountingSort( A,B,Order,N,K) ;printf( /nAfter CS:/n ) ;for( i =1; i =N; i +)printf( %d ,B i );printf( /nOrder: /n ) ;for( i =1; i =N; i +)printf( %d ,Order i ) ;return0;程序運行效果如下：Before CS:After CS:Order:顯然地，計數(shù)排序的時間復雜度為 O(N+K) ，空間復雜度為 O(N+K) 。當 K 不是很大時，這是一個很有效的線性排序算法。 更重要的是， 它是一種 穩(wěn)定排序

18、算法 ，即排序后的相同值的元素原有的相對位置不會發(fā)生改變 ( 表現(xiàn)在 Order 上 ) ，這是計數(shù)排序很重要的一個性質(zhì)，就是根據(jù)這個性質(zhì)，我們才能把它應用到基數(shù)排序。桶排序可能你會發(fā)現(xiàn)， 計數(shù)排序似乎饒了點彎子，比如當我們剛剛統(tǒng)計出C，Ci 可以表示A 中值為 i 的元素的個數(shù)，此時我們直接順序地掃描C，就可以求出排序后的結(jié)果。的確是這樣，不過這種方法不再是計數(shù)排序，而是桶排序 (Bucket Sort)，確切地說，是桶排序的一種特殊情況。用這種方法，可以很容易寫出程序，比計數(shù)排序還簡單，只是不能求出穩(wěn)定的Order 。CPP12/* Memo:桶排序特殊實現(xiàn) */3 #include 4

19、#include 5 #include 6 #include 7 #include 8usingnamespacestd;9voidBucketSort( int* A, int * B, int N, int K )1011int* C=new int K+1 ;12inti,j,k;13memset ( C, 0, sizeof ( int)*(K+1) ;14for( i =1; i =N; i +) / 把 A 中的每個元素按照值放入桶中15C A i + ;1617for( i =j =1; i = K; i + ,j=k ) / 統(tǒng)計每個桶元素的個數(shù)，并輸1819出到 B2021f

20、or( k =j ; kj +C i ; k +)22B k =i ;23 24 int main ()25 26int* A, * B,N =1000 ,K =1000 ,i;27A=newint N+1 ;28B=newint N+1 ;29for( i =1; i =N; i +)30A i =rand ()%K+1; /生成 1.K的隨機數(shù)31BucketSort( A,B,N,K) ;3233for( i =1; i =N; i +)34printf ( %d ,B i );35return0;36這種特殊實現(xiàn)的方式時間復雜度為 O(N+K) 素都要在 K 的范圍內(nèi)。更一般的，如果我

21、們的，空間復雜度也為O(N+K)K 很大，無法直接開出O(K)，同樣要求每個元的空間該如何呢？首先定義桶， 桶為一個數(shù)據(jù)容器，每個桶存儲一個區(qū)間內(nèi)的數(shù)。依然有一個待排序的整數(shù)序列 A ，元素的最小值不小于0 ，最大值不超過K 。假設(shè)我們有M 個桶，第i 個桶 Bucketi存儲 i*K/M至 (i+1)*K/M之間的數(shù)，有如下桶排序的一般方法：?掃描序列A，根據(jù)每個元素的值所屬的區(qū)間，放入指定的桶中( 順序放置) 。? 對每個桶中的元素進行排序，什么排序算法都可以，例如快速排序。? 依次收集每個桶中的元素，順序放置到輸出序列中。對該算法簡單分析，如果數(shù)據(jù)是期望平均分布的，則每個桶中的元素平均個

22、數(shù)為N/M。如果對每個桶中的元素排序使用的算法是快速排序，每次排序的時間復雜度為O(N/M*log(N/M)N*log(N/M) =。則總的時間復雜度為O(N)+O(M)*O(N/M*log(N/M) = O(N+O(N + N*logN N*logM)。當 M 接近于 N 是，桶排序的時間復雜度就可以近似認為是 O(N) 的。就是桶越多，時間效率就越高，而桶越多，空間卻就越大，由此可見時間和空間是一個矛盾的兩個方面。桶中元素的順序放入和順序取出是有必要的，因為這樣可以確定桶排序是一種法，配合基數(shù)排序是很好用的。穩(wěn)定排序算CPP12/* Memo:桶排序一般實現(xiàn) */3 #include 4

23、#include 5 #include 6 #include 7 #include 8usingnamespacestd;9structlinklist10linklist* next;1112int value;13linklist( intv,linklist* n) : value( v) ,next ( n)14 ;linklist() if( next )deletenext; 1516 inlineintcmp ( constvoid* a, constvoid* b)17return* ( int* ) a -*( int* ) b;1819 20 /*21 為了方便，我把 A

24、中元素加入桶中時是倒序放入的，而收集取出時也是倒序2223 放入序列的，所以不違背穩(wěn)定排序。24 */25 void26 27282930313233343536 桶中3738394041424344BucketSort( int* A, int* B, intN, intK )linklist* Bucket 101 , * p; / 建立桶inti,j,k,M;M=K/ 100 ;memset ( Bucket,0, sizeof( Bucket) ;for( i =1; i =N; i +)k =A i / M;/ 把 A 中的每個元素按照的范圍值放入對應Bucket k =new li

25、nklist( A i ,Bucket k ) ;for( k =j =0; knext )B +j =p - value; / 把桶中每個元素取出， 排45 序并加入 B4647deleteBucket k ;48qsort( B+i +1,j- i, sizeof ( B 0) ,cmp ) ;4950 51 int main ()52 53int* A, * B,N =100 ,K =10000 ,i ;54A=newint N+1;55B=newint N+1;56for( i =1;i =N; i +)57A i =rand ()%K+1; / 生成 1.K的隨機數(shù)58BucketS

26、ort ( A,B,N,K) ;59for( i =1; i =N; i +)printf( %d return0;,B i ); 基數(shù)排序 下面說到我們的重頭戲， 基數(shù)排序 (Radix Sort)。上述的基數(shù)排序和桶排序都只是在研究一個關(guān)鍵字的排序，現(xiàn)在我們來討論有多個關(guān)鍵字的排序問題。假設(shè)我們有一些二元組 (a,b) ，要對它們進行以a 為首要關(guān)鍵字， b 的次要關(guān)鍵字的排序。我們可以先把它們先按照首要關(guān)鍵字排序，分成首要關(guān)鍵字相同的若干堆。然后，在按照次要關(guān)鍵值分別對每一堆進行單獨排序。最后再把這些堆串連到一起，使首要關(guān)鍵字較小的一堆排在上面。按這種方式的基數(shù)排序稱為MSD(Most

27、Significant Dight)排序。第二種方式是從最低有效關(guān)鍵字開始排序，稱為LSD(Least Significant Dight)排序。首先對所有的數(shù)據(jù)按照次要關(guān)鍵字排序，然后對所有的數(shù)據(jù)按照首要關(guān)鍵字排序。要注意的是，使用的排序算法必須是穩(wěn)定的，否則就會取消前一次排序的結(jié)果。由于不需要分堆對每堆單獨排序， LSD 方法往往比 MSD 簡單而開銷小。下文介紹的方法全部是基于LSD 的。通常，基數(shù)排序要用到計數(shù)排序或者桶排序。使用計數(shù)排序時，需要的是Order 數(shù)組。使用桶排序時， 可以用鏈表的方法直接求出排序后的順序。下面是一段用桶排序?qū)ΧM基數(shù)排序的程序：CPP12/* Memo

28、:基數(shù)排序結(jié)構(gòu)數(shù)組 */3 #include 4 #include 5 #include 6 #include 7 #include 8usingnamespace std ;9structdata10int key 2 ;1112 ;13structlinklist1415linklist* next;16data value;17linklist( data v,linklist* n) : value( v ) ,next ( n)18linklist() if( next)deletenext; 19 ;20void BucketSort( data* A, intN,intK,int

29、y )2122linklist* Bucket 101 , * p; / 建立桶2324inti,j,k,M;25M=K/ 100 +1;26memset ( Bucket,0, sizeof( Bucket) ;27for( i =1; i =N; i +)2829k =A i . key y / M;/把 A 中的每個元素按照的范圍值3031 放入對應桶中32Bucket k =new linklist( A i ,Bucket k ) ;3334for( k =j =0; knext ) j + ;3637for( p=Bucket k ,i=1; p; p=p- next,i+)38A j - i +1 =p - value ; / 把桶中每個元素取出39del