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

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

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

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

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

5、次序?yàn)?A .A. DBEGACFH B. ABDEGCFH C. DGEBHFCA D. ABCDEFGH 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEF GH 題圖4-1 5 設(shè)一棵二叉樹的順序存儲結(jié)構(gòu)如題圖4-2所示，則該二叉樹是 C . A完全二叉樹 B滿二叉樹 C深度為4 的二叉樹 D深度為3的二叉樹 1 2 3 4 5 6 7 8 9 10 111234567題圖4-2 6 設(shè)T是Huffman樹，它具有6個(gè)樹葉，且各樹葉的權(quán)分別為1，2，3，4，5，6。那么該樹的非葉子結(jié)點(diǎn)的權(quán)之和為 A 。A51 B21 C30 D49 7設(shè)有一無向圖的鄰接矩陣如下

6、所示，則該圖所有頂點(diǎn)的度之和為 C 。 a b c d ea 0 1 1 1 0 b 1 0 1 0 1 c 1 1 0 0 0 d 1 0 0 0 0 e 0 1 0 0 0 A8 B9 C10 D11 8已知二叉樹的后序遍歷序列是fedbgca，中序遍歷序列是dfebagc，則該二叉樹的先序遍歷序列是 D 。Adefbagc Babcdgef Cdbaefcg Dabdefcg9由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有 C 種不同的形態(tài)。A3 B 4 C 5 D 610在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要 D 條邊 A n Bn+1 Cn/2 Dn-111對線性表進(jìn)行折半（二分）查找時(shí)

7、，要求線性表必須 B 。 A以順序方式存儲 B以順序方式存儲且數(shù)據(jù)元素有序C以鏈表方式存儲 D以鏈表方式存儲且數(shù)據(jù)元素有序12順序查找一個(gè)具有n個(gè)元素的線性表，其時(shí)間復(fù)雜度為 A ，二分查找一個(gè)具有n個(gè)元素的線性表，其時(shí)間復(fù)雜度為 B 。 A O(n) B O(log2n) C O(n2) DO(nlog2n)13.從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列中的正確位置上，此方法稱為 直接插入排序 ；從未排序序列中挑選元素，并將其放入已排序序列中的一端，此方法稱為 直接選擇排序 ；依次將每兩個(gè)相臨的有序表合并成一個(gè)有序表的排序方法稱為 歸并排序 ；當(dāng)兩個(gè)元素比較

8、出現(xiàn)反序時(shí)就相互交換位置的排序方法稱為 交換排序 ；A歸并排序 B 選擇排序 C交換排序 D插入排序ABCDEFGH圖4-3三 簡述下面的幾個(gè)概念：單鏈表，棧、隊(duì)列，排序二叉樹。四 簡述空串和空格串的區(qū)別。五 一棵度為2的樹與二叉樹有何區(qū)別？六 試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和具有3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。七 已知一二叉樹如題圖4-3所示，1 用二叉鏈表和順序存儲方式分別存儲此二叉樹。畫出相應(yīng)的存儲結(jié)構(gòu)圖。2 寫出此二叉樹的中序、先序、后序遍歷序列。123456題圖4-4八 已知一無向圖如題圖4-4所示，請給出該圖的1 每個(gè)頂點(diǎn)的度。2 鄰接矩陣3 鄰接表4 按上述的鄰接表寫出廣度和深度遍歷

9、序列。九 已知一組數(shù)據(jù)元素為（46，75，18，54，15，27，42，39，88，67）1 利用直接插入排序方法，寫出每次插入后的結(jié)果。2 利用快速排序方法，寫出每趟排序后的結(jié)果。3 利用2-路歸并排序方法，寫出每趟歸并后的結(jié)果。4 利用冒泡排序方法，寫出每趟排序后的結(jié)果。十 假定一個(gè)表為（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，用鏈地址法解決沖突，試畫出哈

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

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

12、等于20的整數(shù)放在所有小于等于20的整數(shù)之后，要求算法的時(shí)間復(fù)雜度為O（n）,空間復(fù)雜度為O（1）。7 編寫算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。8 編寫一個(gè)按層次順序（同一層自左向右）遍歷二叉樹的算法。三種基于“分配”“收集”的線性排序算法-計(jì)數(shù)排序、桶排序與基數(shù)排序 文中代碼見原文鏈接：非基于比較的排序在計(jì)算機(jī)科學(xué)中，排序是一門基礎(chǔ)的算法技術(shù)，許多算法都要以此作為基礎(chǔ)，不同的排序算法有著不同的時(shí)間開銷和空間開銷。排序算法有非常多種，如我們最常用的快速排序和堆排序等算法，這些算法需要對序列中的數(shù)據(jù)進(jìn)行比較，因?yàn)楸环Q為基于比較的排序?；诒容^的排序算法是不能突破O(NlogN)的。簡單證明如下：N

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

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

15、 Code CPP 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849/* Memo: 計(jì)數(shù)排序*/#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>using namespace std;void CountingSort(int *A,int *B,int *Order,int N

16、,int K)int *C=new intK+1;int i;memset(C,0,sizeof(int)*(K+1);for (i=1;i<=N;i+) /把A中的每個(gè)元素分配CAi+;for (i=2;i<=K;i+) /統(tǒng)計(jì)不大于i的元素的個(gè)數(shù)Ci+=Ci-1;for (i=N;i>=1;i-)BCAi=Ai; /按照統(tǒng)計(jì)的位置，將值輸出到B中，將順序輸出到Order中OrderCAi=i;CAi-;int main()int *A,*B,*Order,N=15,K=10,i;A=new intN+1;B=new intN+1;Order=new intN+1;for

17、(i=1;i<=N;i+)Ai=rand()%K+1; /生成1.K的隨機(jī)數(shù)printf("Before CS:/n");for (i=1;i<=N;i+)printf("%d ",Ai);CountingSort(A,B,Order,N,K);printf("/nAfter CS:/n");for (i=1;i<=N;i+)printf("%d ",Bi);printf("/nOrder:/n");for (i=1;i<=N;i+)printf("%d &qu

18、ot;,Orderi);return 0;程序運(yùn)行效果如下：Before CS:2 8 5 1 10 5 9 9 3 5 6 6 2 8 2After CS:1 2 2 2 3 5 5 5 6 6 8 8 9 9 10Order:4 1 13 15 9 3 6 10 11 12 2 14 7 8 5 顯然地，計(jì)數(shù)排序的時(shí)間復(fù)雜度為O(N+K)，空間復(fù)雜度為O(N+K)。當(dāng)K不是很大時(shí)，這是一個(gè)很有效的線性排序算法。更重要的是，它是一種穩(wěn)定排序算法，即排序后的相同值的元素原有的相對位置不會發(fā)生改變(表現(xiàn)在Order上)，這是計(jì)數(shù)排序很重要的一個(gè)性質(zhì)，就是根據(jù)這個(gè)性質(zhì)，我們才能把它應(yīng)用到基數(shù)排序。

19、桶排序可能你會發(fā)現(xiàn)，計(jì)數(shù)排序似乎饒了點(diǎn)彎子，比如當(dāng)我們剛剛統(tǒng)計(jì)出C，Ci可以表示A中值為i的元素的個(gè)數(shù)，此時(shí)我們直接順序地掃描C，就可以求出排序后的結(jié)果。的確是這樣，不過這種方法不再是計(jì)數(shù)排序，而是桶排序(Bucket Sort)，確切地說，是桶排序的一種特殊情況。用這種方法，可以很容易寫出程序，比計(jì)數(shù)排序還簡單，只是不能求出穩(wěn)定的Order。?View Code CPP 123456789101112131415161718192021222324252627282930313233343536/* Memo: 桶排序特殊實(shí)現(xiàn)*/#include <iostream>#inclu

20、de <cstdio>#include <cstdlib>#include <cmath>#include <cstring>using namespace std;void BucketSort(int *A,int *B,int N,int K)int *C=new intK+1;int i,j,k;memset(C,0,sizeof(int)*(K+1);for (i=1;i<=N;i+) /把A中的每個(gè)元素按照值放入桶中CAi+;for (i=j=1;i<=K;i+,j=k) /統(tǒng)計(jì)每個(gè)桶元素的個(gè)數(shù)，并輸出到Bfor (k=j

21、;k<j+Ci;k+)Bk=i;int main()int *A,*B,N=1000,K=1000,i;A=new intN+1;B=new intN+1;for (i=1;i<=N;i+)Ai=rand()%K+1; /生成1.K的隨機(jī)數(shù)BucketSort(A,B,N,K);for (i=1;i<=N;i+)printf("%d ",Bi);return 0;這種特殊實(shí)現(xiàn)的方式時(shí)間復(fù)雜度為O(N+K)，空間復(fù)雜度也為O(N+K)，同樣要求每個(gè)元素都要在K的范圍內(nèi)。更一般的，如果我們的K很大，無法直接開出O(K)的空間該如何呢？首先定義桶，桶為一個(gè)數(shù)據(jù)容

22、器，每個(gè)桶存儲一個(gè)區(qū)間內(nèi)的數(shù)。依然有一個(gè)待排序的整數(shù)序列A，元素的最小值不小于0，最大值不超過K。假設(shè)我們有M個(gè)桶，第i個(gè)桶Bucketi存儲i*K/M至(i+1)*K/M之間的數(shù)，有如下桶排序的一般方法：· 掃描序列A，根據(jù)每個(gè)元素的值所屬的區(qū)間，放入指定的桶中(順序放置)。 · 對每個(gè)桶中的元素進(jìn)行排序，什么排序算法都可以，例如快速排序。 · 依次收集每個(gè)桶中的元素，順序放置到輸出序列中。 對該算法簡單分析，如果數(shù)據(jù)是期望平均分布的，則每個(gè)桶中的元素平均個(gè)數(shù)為N/M。如果對每個(gè)桶中的元素排序使用的算法是快速排序，每次排序的時(shí)間復(fù)雜度為O(N/M*log(N/M

23、)。則總的時(shí)間復(fù)雜度為O(N)+O(M)*O(N/M*log(N/M) = O(N+ N*log(N/M) = O(N + N*logN N*logM)。當(dāng)M接近于N是，桶排序的時(shí)間復(fù)雜度就可以近似認(rèn)為是O(N)的。就是桶越多，時(shí)間效率就越高，而桶越多，空間卻就越大，由此可見時(shí)間和空間是一個(gè)矛盾的兩個(gè)方面。桶中元素的順序放入和順序取出是有必要的，因?yàn)檫@樣可以確定桶排序是一種穩(wěn)定排序算法，配合基數(shù)排序是很好用的。?View Code CPP 123456789101112131415161718192021222324252627282930313233343536373839404142434

24、4454647484950515253545556575859/* Memo: 桶排序一般實(shí)現(xiàn)*/#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>using namespace std;struct linklistlinklist *next;int value;linklist(int v,linklist *n):value(v),next(n)linklist() if (next) delete n

25、ext;inline int cmp(const void *a,const void *b)return *(int *)a-*(int *)b;/*為了方便，我把A中元素加入桶中時(shí)是倒序放入的，而收集取出時(shí)也是倒序放入序列的，所以不違背穩(wěn)定排序。*/void BucketSort(int *A,int *B,int N,int K)linklist *Bucket101,*p;/建立桶int i,j,k,M;M=K/100;memset(Bucket,0,sizeof(Bucket);for (i=1;i<=N;i+)k=Ai/M; /把A中的每個(gè)元素按照的范圍值放入對應(yīng)桶中Buck

26、etk=new linklist(Ai,Bucketk);for (k=j=0;k<=100;k+)i=j;for (p=Bucketk;p;p=p->next)B+j=p->value; /把桶中每個(gè)元素取出，排序并加入Bdelete Bucketk;qsort(B+i+1,j-i,sizeof(B0),cmp);int main()int *A,*B,N=100,K=10000,i;A=new intN+1;B=new intN+1;for (i=1;i<=N;i+)Ai=rand()%K+1; /生成1.K的隨機(jī)數(shù)BucketSort(A,B,N,K);for (

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

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

29、192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263/* Memo: 基數(shù)排序 結(jié)構(gòu)數(shù)組*/#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>using namespace std;struct dataint key2;struct linklistlinklist *next;da

30、ta value;linklist(data v,linklist *n):value(v),next(n)linklist() if (next) delete next;void BucketSort(data *A,int N,int K,int y)linklist *Bucket101,*p;/建立桶int i,j,k,M;M=K/100+1;memset(Bucket,0,sizeof(Bucket);for (i=1;i<=N;i+)k=Ai.keyy/M; /把A中的每個(gè)元素按照的范圍值放入對應(yīng)桶中Bucketk=new linklist(Ai,Bucketk);for (k=j=0