資料結構習題集

第一章緒論

1．下面是幾種資料的邏輯結構s=(d，r)，分別畫出對應的資料邏輯結構，並指出它們分別屬於何種結構。

d= r=

(a) r=

(b) r=

2．分析下列程式段的時間複雜度

(a) for(i=0；ifor(j=0；j b[i][j]=0；

(b) s=0

for(i=0；ifor(j=0；j s+=b[i][j]；

while(i i*=2；

3．在資料結構中，與所使用的計算機無關的是

a．儲存結構 b．物理結構 c．物理和儲存結構 d．邏輯結構

4．非線性結構中每個結點。

a．無直接前驅結點b．只有乙個直接前驅和直接後繼結點

c．無直接後繼結點d．可能有多個直接前驅和多個直接後繼結點

5．可以把資料的邏輯結構劃分成。

a．內部結構和外部結構 b．動態結構和靜態結構

c．緊湊結構和非緊湊結構 d．線性結構和非線性結構

第二章線性表

一、單項選擇題

1．下面關於線性表敘述中，錯誤的是_(1)_。

(1)：a．順序表必須占用一片位址連續的儲存單元

b．鍊錶不必占用一片位址連續的儲存單元

c．順序表可以隨機訪問任一元素

d．鍊錶可以隨機訪問任一元素

2．在表長為n的單鏈表中，演算法時間複雜度為o(n)的操作是 (2)。

(2)：a．查詢單鏈表中第i個結點 b．在p結點之後插入乙個結點

c．刪除表中第乙個結點d．刪除p結點的直接後繼結點

3．單鏈表的儲存密度 (3) 。

(3)：a．大於1 b．等於1 c．小於1 d．不能確定

4．在表長為n的順序表中，演算法的時間複雜度為o(1)的操作是 (4) 。

(4)：a．在第n個結點之後插入乙個結點 b．在第i個結點前插入乙個新結點

c．刪除第i個結點d．求表長

5．在下列鍊錶中不能從當前結點出發訪問到其餘各結點的是（5）。

(5)：a．單鏈表 b．單迴圈鍊錶 c．雙向鍊錶 d．雙向迴圈鍊錶

6．在設頭、尾指標的單鏈表中，與長度n有關的操作是（6）。

(6)：a．刪除第乙個結點b．刪除最後乙個結點

c.在第乙個結點之前插入乙個結點 d.在表尾結點後插入乙個結點

7.設p結點是帶表頭結點的雙迴圈鍊錶中的結點，則

(1)在p結點後插入s結點的語句序列中正確的是（7）。

（7）：>next=p->next；p->next->prior=s；

p->next=s；s->next=p->next；

>next=s；s—>next=p—>next；

p—>next—>prior=s；s—>next=p；

>next=s；p—>next—>prior=s；

s->next=p—>next；s—>next=p；

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

s->next=p->next；s->next=p；

(2)在p結點之前插入s結點的語句序列中正確的是(8)。

(8)：>prior=p->prior；p->prior->nextp->prior=s；s->next=p

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

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

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

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

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

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

8．下列關於鍊錶說法錯誤的是 (9) 。

(9)：a.靜態鍊錶中訪問每乙個元素的時間相同

b．動態鍊錶中訪問每乙個元素的時間不同

c．靜態鍊錶上插入或刪除乙個元素不必移動其他元素

d．動態鍊錶上插入或刪除乙個元素不必移動其他元素

9．在鍊錶中最常用的操作是在最後乙個資料元素之後插入乙個資料元素和刪除第乙個資料元素，則最節省運算時間的儲存方式是 (10) 。

(10)：a.僅有頭指標的單鏈表b．僅有頭指標的單迴圈鍊錶

c．僅有頭指標的雙向鍊錶 d．僅有尾指標的單迴圈鍊錶

二、填空題

1．單鏈表中每個結點需要兩個域，乙個是資料域，另乙個是 (1) 。

2．鍊錶相對於順序表的優點是 (2) 和 (3) 操作方便。

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

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

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

6．在非空的單迴圈鍊錶h中，某個p結點為尾結點的條件是 (10)。

7．在非空的雙迴圈鍊錶中，已知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的單迴圈鍊錶中，在尾結點後插入p結點的語句序列是 (18) ； (19)；刪除第乙個結點的語句序列是q=r->next； (20) ；free(q)。

三、應用題

1．簡述順序表和煉表各自的優點。

2．簡述頭指標和頭結點的作用。．

四、演算法設計題

1．請編寫乙個演算法，實現將x插入到已按資料域值從小到大排列的有序表中。

2．設計乙個演算法，計算單鏈表中資料域值為x的結點個數。

3．設計乙個用前插法建立帶表頭結點的單鏈表的演算法。

4．請編寫乙個建立單迴圈鍊錶的演算法。

5．設計乙個演算法，實現將帶頭結點的單鏈表進行逆置。

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

第三章棧和佇列

一、選擇題

1．插入和刪除只能在表的一端進行的線性表，稱為 (1) 。

(1)：a．佇列 b．迴圈佇列 c．棧 d．雙棧

2．佇列操作應遵循的原則是（2）。

(2)：a.先進先出 b．後進先出 c．先進後出 d．隨意進出

3．棧操作應遵循的原則是（3）。

(3)：a．先進先出 b．後進後出 c．後進先出 d．隨意進出

4．設隊長為n的佇列用單迴圈鍊錶表示且僅設頭指標，則進隊操作的時間複雜度為（4）。

(4)：a．o(1) b．o(log2n) c．o(n) d．o(n2)

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

(5)：a．abcd b．dcba c．bcad d．dbca

6．若用乙個大小為6的陣列來實現迴圈佇列，且當前front和rear的值分別為3和0，當從佇列中刪除乙個元素，再加入兩個元素後，front和rear的值分別為 (6) 。

(6)：a．5和1 b．4和2 c．2和4 d．1和5

7．乙個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（7）。

(7)：

二、填空題

1．**性結構中，允許插入、刪除的一端稱為 (1) ，另一端稱為 (2) 。

2．在佇列結構中，允許插入的一端稱為 (3) ，允許刪除的一端稱為 (4) 。

3．設長度為n的鏈佇列用單迴圈鍊錶表示，若只設頭指標，則進隊和出隊操作的時間複雜度分別是 (5) 和 (6) ；若只設尾指標，則進隊和出隊操作的時間複雜度分別為 (7) 和 (8) 。

4．設用少用乙個元素空間的陣列a[m]存放迴圈佇列，front指向實際隊首，rear指向新元素應存放的位置，則判斷隊空的條件是 (9) ，判斷隊滿的條件是 (10) ，當隊未滿時，迴圈佇列的長度是 (11) 。

資料結構習題集

資料結構習題集

資料結構習題集

《資料結構》習題集粹

相關推薦