數(shù)據(jù)結構習題集

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結構習題集第一章緒論

1．下面是幾種數(shù)據(jù)的規(guī)律結構S=(D，R)，分別畫出對應的數(shù)據(jù)規(guī)律結構，并指出它們分別屬于何種結構。

D={a，b，c，d，e，f}R={r}

(a)r={，，，，}

(b)r={，，，，}(c)r={，，，，}2．分析以下程序段的時間繁雜度(a)for(i=0；inext=p->next；p->next->prior=s；p->next=s；s->next=p->next；

B.p—>next=s；S—>next=p—>next；

p—>next—>prior=s；s—>next=p；C.p->next=s；p—>next—>prior=s；s->next=p—>next；S—>next=p；D.p->next->prior=s；p->next=s；s->next=p->next；s->next=p；

(2)在p結點之前插入s結點的語句序列中正確的是(8)。(8)：A.s->prior=p->prior；p->prior->nextp->prior=s；s->next=p；

B.p->prior=s；p->prior->next=s;s->prior=p->prior；s->next=p;

C.p->prior->next=s；p->prior=s;s->prior=p->prior；s->next=p;

D.p->prior=s；s->next=p；

p->prior->next=s；s->prior=p->prior;

8．以下關于鏈表說法錯誤的是(9)。(9)：A.靜態(tài)鏈表中存取每一個元素的時間一致B．動態(tài)鏈表中存取每一個元素的時間不同

C．靜態(tài)鏈表上插入或刪除一個元素不必移動其他元素D．動態(tài)鏈表上插入或刪除一個元素不必移動其他元素

9．在鏈表中最常用的操作是在最終一個數(shù)據(jù)元素之后插入一個數(shù)據(jù)元素和刪除第一個數(shù)據(jù)元素，則最節(jié)省運算時間的存儲方式是(10)。

(10)：A.僅有頭指針的單鏈表B．僅有頭指針的單循環(huán)鏈表

2

C．僅有頭指針的雙向鏈表D．僅有尾指針的單循環(huán)鏈表二、填空題

1．單鏈表中每個結點需要兩個域，一個是數(shù)據(jù)域，另一個是(1)。2．鏈表相對于順序表的優(yōu)點是(2)和(3)操作便利。

3．表長為n的順序表中，若在第j個數(shù)據(jù)元素(1≤i≤n+1)之前插入一個數(shù)據(jù)元素，需要向后移動(4)個數(shù)據(jù)元素；刪除第j個數(shù)據(jù)元素需要向前移動(5)個數(shù)據(jù)元素；在等概率的狀況下，插入一個數(shù)據(jù)元素平均需要移動(6)個數(shù)據(jù)元素，刪除一個數(shù)據(jù)元素平均需要移動(7)個數(shù)據(jù)元素。

4．單鏈表h為空表的條件是(8)。

5．帶表頭結點的單鏈表h為空表的條件是(9)。

6．在非空的單循環(huán)鏈表h中，某個p結點為尾結點的條件是(10)。7．在非空的雙循環(huán)鏈表中，已知p結點是表中任一結點，則(1)在p結點后插入s結點的語句序列是：

s->next=p->next；s->prior=p；(11)；(12)(2)在p結點前插入s結點的語句序列是：

s->prior=p->prior；s->next=p；(13)；(14)(3)刪除p結點的直接后繼結點的語句序列是：q=p->next；p->next=q->next；(15)；free(q)；(4)刪除p結點的直接前驅結點的語句序列是：q=p->prior；p->prior=q->prior；(16)；free(q)；(5)刪除p結點的語句序列是：

p->prior->next=p->next；(17)；free(q)；

8．在帶有尾指針r的單循環(huán)鏈表中，在尾結點后插入p結點的語句序列是(18)；(19)；刪除第一個結點的語句序列是q=r->next；(20)；free(q)。

三、應用題

1．簡述順序表和鏈表各自的優(yōu)點。2．簡述頭指針和頭結點的作用。．四、算法設計題

1．請編寫一個算法，實現(xiàn)將x插入到已按數(shù)據(jù)域值從小到大排列的有序表中。2．設計一個算法，計算單鏈表中數(shù)據(jù)域值為x的結點個數(shù)。3．設計一個用前插法建立帶表頭結點的單鏈表的算法。4．請編寫一個建立單循環(huán)鏈表的算法。

5．設計一個算法，實現(xiàn)將帶頭結點的單鏈表進行逆置。

6．編寫一個算法，實現(xiàn)以較高的效率從有序順序表A中刪除其值在x和y之間(x≤A[i]≤y)的所有元素。

3

第三章棧和隊列

一、選擇題

1．插入和刪除只能在表的一端進行的線性表，稱為(1)。(1)：A．隊列B．循環(huán)隊列C．棧D．雙棧2．隊列操作應遵循的原則是（2）。

(2)：A.先進先出B．后進先出C．先進后出D．隨意進出3．棧操作應遵循的原則是（3）。

(3)：A．先進先出B．后進后出C．后進先出D．隨意進出

4．設隊長為n的隊列用單循環(huán)鏈表表示且僅設頭指針，則進隊操作的時間繁雜度為（4）。

(4)：A．O(1)B．O(log2n)C．O(n)D．O(n)

5．設棧s和隊列q均為空，先將a，b，c，d依次進隊列q，再將隊列q中順次出隊的元素進棧s，直至隊空。再將棧s中的元素逐個出棧，并將出棧元素順次進隊列q，則隊列q的狀態(tài)是(5)。

(5)：A．a(chǎn)bcdB．dcbaC．bcadD．dbca

6．若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前front和rear的值分別為3和0，當從隊列中刪除一個元素，再參與兩個元素后，front和rear的值分別為(6)。

(6)：A．5和1B．4和2C．2和4D．1和5

7．一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（7）。(7)：A.edcbaB.decbaC.dceabD.abcde二、填空題

1．在棧結構中，允許插入、刪除的一端稱為(1)，另一端稱為(2)。2．在隊列結構中，允許插入的一端稱為(3)，允許刪除的一端稱為(4)。3．設長度為n的鏈隊列用單循環(huán)鏈表表示，若只設頭指針，則進隊和出隊操作的時間繁雜度分別是(5)和(6)；若只設尾指針，則進隊和出隊操作的時間繁雜度分別為(7)和(8)。

4．設用少用一個元素空間的數(shù)組A[m]存放循環(huán)隊列，front指向實際隊首，rear指向新元素應存放的位置，則判斷隊空的條件是(9)，判斷隊滿的條件是(10)，當隊未滿時，循環(huán)隊列的長度是(11)。

5.兩個棧共享一個向量空間時，可將兩個棧底分別設在(12)。三、應用題．

1．簡述線性表、棧和隊列有什么異同?

2．循環(huán)隊列的優(yōu)點是什么?設用數(shù)組A[m]來存放循環(huán)隊列，如何判斷隊滿和隊空。3．若進棧序列為abcd，請給出全部可能的出棧序列和不可能的出棧序列。

4．設棧s和隊列q初始狀態(tài)為空，元素a，b，c，d，e和f，依次通過棧s，一個元素出棧后即進人隊列，若6個元素出隊的序列是bdcfea，則棧s的容量至少應當存多少個元素?5．已知一個中綴算術表達式為3+4/(25-(6+15))*8寫出對應的后綴算術表達式（逆

4

2

波蘭表達式）。

四、算法設計題

1.已知q是一個非空順序隊列，s是一個順序棧，請設計一個算法，實現(xiàn)將隊列q中所有元素逆置。

2．已知遞歸函數(shù)：1當n=0時F(n)=

n·F(n/2)當n>0時

(1)寫出求F(n)遞歸算法；(2)寫出求F(n)的非遞歸算法。

3．假設以帶頭結點的循環(huán)鏈表表示隊列，并且僅設一個指針指向隊尾元素結點（注意不設頭指針），試編寫相應的隊列初始化、入隊列和出隊列的算法。

第四章串、數(shù)組和廣義表

一、選擇題

1．串的模式匹配是指(1)。(1)：A.判斷兩個串是否相等B．對兩個串進行大小比較

C．找某字符在主串中第一次出現(xiàn)的位置

D．找某子串在主串中第一次出現(xiàn)的第一個字符位置

2．設二維數(shù)組A[m][n]，每個數(shù)組元素占用d個存儲單元，第一個數(shù)組元素的存儲地址是如Loc(a[0][0])，求按行優(yōu)先順序存放的數(shù)組元素a[j][j](0≤i≤m-1，0≤j≤n-1)的存儲地址(2)。

(2)：A．Loc(a[0][0]+[(i-1)*n+j-1]*dB．Loc(a[0][0])+[i*n+j]*dC．Loc(a[0][0]+[j*m+i]*dD．Loc(a[0][0])+[(j-1)*m+i-1]*d

3．設二維數(shù)組A[m][n]，每個數(shù)組元素占d個存儲單元，第1個數(shù)組元素的存儲地址是Loc(a[0][0])，求按列優(yōu)先順序存放的數(shù)組元素a[j][j](0≤i≤m-1，0≤j≤n-1)的存儲地址(3)。

(3)：A．Loc(a[0][