思考與練習(xí)

一、單項(xiàng)選擇題

1. 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（　）的存儲(chǔ)結(jié)構(gòu)，線性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種（　）的存儲(chǔ)結(jié)構(gòu)。

A. 順序存取

B. 隨機(jī)存取

C. 索引存取

D. 散列存取

2. 順序表中邏輯上相鄰的元素的物理位置（　）。單鏈表中邏輯上相鄰的元素的物理位置（　）。

A. 一定是連續(xù)的

B. 部分是連續(xù)的

C. 一定不連續(xù)

D. 不一定連續(xù)

3. 鏈表不具有的特點(diǎn)是（　）。

A. 插入、刪除不需要移動(dòng)元素

B. 不需要事先估計(jì)存儲(chǔ)空間

C. 所需空間與線性表長(zhǎng)度成正比

D. 可以隨機(jī)訪問(wèn)任一個(gè)元素

4. 判斷不帶頭結(jié)點(diǎn)的單鏈表head指針是否為空的條件是（　）。

A. head==NULL

B. head-＞next==NULL

C. head-＞next==head

D. head！=NULL

5. 判斷帶頭結(jié)點(diǎn)的單鏈表head指針為空的條件是（　）。

A. head==NULL

B. head-＞next=NULL

C. head-＞next==head

D. head！=NULL

6. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足（　）。

A. p-＞next=NULL

B. p=NULL

C. p-＞next=head

D. p=head

7. 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行（　）。

A. s-＞next=p-＞next；p-＞next=s；

B. p-＞next=s-＞next；s-＞next=p；

C. q-＞next=s；s-＞next=p；

D. p-＞next=s；s-＞next=q；

8. 在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行（　）。

A. s-＞next=p；p-＞next=s；

B. s-＞next=p-＞next；p-＞next=s；

C. s-＞next=p-＞next；p=s；

D. p-＞next=s；s-＞next=p；

9. 在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（　）。

A. p-＞next=p-＞next-＞next；

B. p=p-＞next；p-＞next=p-＞next-＞next；

C. p-＞next=p-＞next；

D. p=p-＞next-＞next；

10. 對(duì)于n個(gè)元素建立一個(gè)有序單鏈表的最好時(shí)間復(fù)雜度是（　）。

A. O（1）

B. O（n）

C. O（n²）

D. O（nlog₂n）

二、填空題

1. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)__________個(gè)元素，具體移動(dòng)的元素個(gè)數(shù)與__________有關(guān)。

2. 對(duì)一個(gè)線性表分別進(jìn)行遍歷和逆置運(yùn)算，其最好的時(shí)間復(fù)雜度分別為_(kāi)_________和__________。

3. 線性表的兩種存儲(chǔ)結(jié)構(gòu)分別是__________和__________。

4. 在雙向鏈表中，每個(gè)結(jié)點(diǎn)有__________個(gè)指針域，一個(gè)指向__________，一個(gè)指向__________。

5. 在一個(gè)非空單鏈表中，p指針?biāo)附Y(jié)點(diǎn)既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)，在p指針?biāo)附Y(jié)點(diǎn)之后插入結(jié)點(diǎn)s可執(zhí)行如下操作：

s-＞next=__________；p-＞next=s；

6. 在一個(gè)非空單鏈表中，p指針?biāo)附Y(jié)點(diǎn)既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)，在p指針?biāo)附Y(jié)點(diǎn)之前插入結(jié)點(diǎn)s可執(zhí)行如下操作：

提示：仿照上一題完成插入，然后交換兩個(gè)節(jié)點(diǎn)的值即可。

s-＞next=__________；p-＞next=s；

t=p-＞data；p-＞data=__________；s-＞data=t；

7. 在一個(gè)非空單鏈表中，p指針?biāo)附Y(jié)點(diǎn)既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)，刪除p指針指向的結(jié)點(diǎn)可執(zhí)行如下操作：

提示：題目中只給出了一個(gè)結(jié)點(diǎn)指針。

q=p-＞next；

p-＞data=p-＞next-＞data；

p-＞next=__________；

free（q）；

三、簡(jiǎn)答題

1. 線性表可用順序表或鏈表存儲(chǔ)。試問(wèn)：

（1）兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)？

（2）如果有n個(gè)表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，表的總數(shù)也可能自動(dòng)改變，在此情況下，應(yīng)選用哪種存儲(chǔ)表示？為什么？

（3）若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)應(yīng)采用哪種存儲(chǔ)表示？為什么？

2. 描述以下3個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)。

3. 下面的C語(yǔ)言函數(shù)實(shí)現(xiàn)從一個(gè)無(wú)頭結(jié)點(diǎn)的單鏈表中刪除首元結(jié)點(diǎn)，找出并修改函數(shù)中的錯(cuò)誤。

四、算法設(shè)計(jì)題

1. 從順序表中刪除具有最小值的元素并由函數(shù)返回最小值，空出的位置由最后一個(gè)元素填補(bǔ)，若順序表為空，則顯示出錯(cuò)信息并退出運(yùn)行。

2. 從順序表中刪除具有給定值x的所有元素。

3. 從順序表中刪除所有值在給定值s和t（要求s小于t）之間的元素。

4. 從順序表中刪除所有重復(fù)的元素，使所有元素的值均不同。如對(duì)于線性表（2，8，9，2，5，5，6，8，7，2），則執(zhí)行此算法后變?yōu)椋?，8，9，5，6，7）。注意：表中元素未必是排好序的，且每個(gè)值的第一次出現(xiàn)應(yīng)當(dāng)保留。

5. 將元素為整數(shù)的順序表（a₁，a₂，…，a_n）重新排列為以a₁為界的兩部分：a₁前面的值均比a₁小，a₁后面的值都比a₁大，要求時(shí)間復(fù)雜度為O（n）。

6. 用尾部插入法來(lái)創(chuàng)建單鏈表，即每次生成的新結(jié)點(diǎn)均插入在鏈表的尾部。

7. 根據(jù)一個(gè)元素類型為整型的單鏈表生成兩個(gè)單鏈表，使得第一個(gè)單鏈表中包含原單鏈表中所有元素值為奇數(shù)的結(jié)點(diǎn)，使得第二個(gè)單鏈表中包含原單鏈表中所有元素值為偶數(shù)的結(jié)點(diǎn)，原有單鏈表保持不變。

8. 設(shè)表La和Lb中各元素值均遞增有序。試寫(xiě)一算法，使得La和Lb合并后的新表中的元素仍保持遞增有序。

9. 求循環(huán)鏈表中結(jié)點(diǎn)的個(gè)數(shù)。

10. 已知一個(gè)單鏈表，設(shè)計(jì)一個(gè)復(fù)制單鏈表的算法。

11. 已知一個(gè)無(wú)序單鏈表，表中結(jié)點(diǎn)的data字段為正整數(shù)。設(shè)計(jì)一個(gè)算法按遞增次序打印表中結(jié)點(diǎn)的值。

12. 已知一個(gè)單鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)的元素。

提示：考慮算法的效率，考慮鏈表為空、k=0等特殊情況。

13. 已知一個(gè)單鏈表，判斷在該單鏈表中是否存在一個(gè)環(huán)。