1、第 2 章 線性表 課后習題講解 1. 填空 在順序表中，等概率情況下，插入和刪除一個元素平均需移動（ ）個元素，具體移動元素的個數與（ ）和（ ）有關。【解答】表長的一半，表長，該元素在表中的位置 順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是（ ）。【解答】108【分析】第5個元素的存儲地址=第1個元素的存儲地址(51)×2=108 設單鏈表中指針p 指向結點A，若要刪除A的后繼結點（假設A存在后繼結點），則需修改指針的操作為（ ）。【解答】p->next=(p->next)->next 單鏈表中設置頭結點的作用是（ ）。【解

2、答】為了運算方便【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。 非空的單循環鏈表由頭指針head指示，則其尾結點（由指針p所指）滿足（ ）。【解答】p->next=head【分析】如圖2-8所示。 在由尾指針rear指示的單循環鏈表中，在表尾插入一個結點s的操作序列是（ ）；刪除開始結點的操作序列為（ ）。【解答】s->next =rear->next; rear->next =s; rear =s;q=rear->next->next; rear->next->next=q->next; delete q;【分析】操作示意圖

3、如圖2-9所示： 一個具有n個結點的單鏈表，在指針p所指結點后插入一個新結點的時間復雜度為（ ）；在給定值為x的結點后插入一個新結點的時間復雜度為（ ）。【解答】(1)，(n)【分析】在p所指結點后插入一個新結點只需修改指針，所以時間復雜度為(1)；而在給定值為x的結點后插入一個新結點需要先查找值為x的結點，所以時間復雜度為(n)。 可由一個尾指針唯一確定的鏈表有（ ）、（ ）、（ ）。【解答】循環鏈表，循環雙鏈表，雙鏈表2. 選擇題 線性表的順序存儲結構是一種（ ）的存儲結構，線性表的鏈接存儲結構是一種（ ）的存儲結構。 A 隨機存取 B 順序存取 C 索引存取 D 散列存取【解答】A，B【

4、分析】參見2.2.1。 線性表采用鏈接存儲時，其地址（ ）。A 必須是連續的 B 部分地址必須是連續的C 一定是不連續的 D 連續與否均可以【解答】D【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以連續，也可以不連續，甚至可以零散分布在內存中任意位置。 單循環鏈表的主要優點是（ ）。A 不再需要頭指針了 B 從表中任一結點出發都能掃描到整個鏈表；C 已知某個結點的位置后，能夠容易找到它的直接前趨；D 在進行插入、刪除操作時，能更好地保證鏈表不斷開。【解答】B 鏈表不具有的特點是（ ）。A 可隨機訪問任一元素 B 插入、刪除不需要移動元素C 不必事先估計存儲空

5、間 D 所需空間與線性表長度成正比【解答】A 若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨，則采用（ ）存儲方法最節省時間。A 順序表 B 單鏈表 C 雙鏈表 D 單循環鏈表【解答】A【分析】線性表中最常用的操作是取第i 個元素，所以，應選擇隨機存取結構即順序表，同時在順序表中查找第i個元素的前趨也很方便。單鏈表和單循環鏈表既不能實現隨機存取，查找第i個元素的前趨也不方便，雙鏈表雖然能快速查找第i個元素的前趨，但不能實現隨機存取。 若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除第一個結點，則采用（ ）存儲方法最節省時間。A 單鏈表 B 帶頭指針的單循環鏈表 C 雙鏈

6、表 D 帶尾指針的單循環鏈表【解答】D【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、帶頭指針的單循環鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環鏈表中刪除第一個結點，其時間性能是O(1)，所以，答案是D 。 若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用（ ）存儲方法最節省運算時間。A 單鏈表 B 循環雙鏈表 C單循環鏈表 D 帶尾指針的單循環鏈表【解答】B【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、單循環鏈表都不合適，刪除最后一個結點需要知道終端結點的前驅結點的地址，所以，帶尾指針的

7、單循環鏈表不合適，而循環雙鏈表滿足條件。 在具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是（ ）。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】B【分析】首先應順序查找新結點在單鏈表中的位置。 對于n個元素組成的線性表，建立一個有序單鏈表的時間復雜度是（ ）。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】C【分析】該算法需要將n個元素依次插入到有序單鏈表中，而插入每個元素需O(n)。 使用雙鏈表存儲線性表，其優點是可以（ ）。A 提高查找速度 B 更方便數據的插入和刪除C 節約存儲空間 D 很快回收存儲空間【解答】B【分

8、析】在鏈表中一般只能進行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針域，顯然不能節約存儲空間，對于動態存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性，所以，其插入和刪除操作更加方便。 在一個單鏈表中，已知q所指結點是p所指結點的直接前驅，若在q和p之間插入s所指結點，則執行（ ）操作。A s->next=p->next; p->next=s; B q->next=s; s->next=p; C p->next=s->next; s->next=p; D p->next=s; s->next=q;【解答】

9、B【分析】注意此題是在q和p之間插入新結點，所以，不用考慮修改指針的順序。 在循環雙鏈表的p所指結點后插入s所指結點的操作是（ ）。A p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;C s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D

10、s->prior=p; s->next=p->next; p->next->prior=s; p->next=s【解答】D【分析】在鏈表中，對指針的修改必須保持線性表的邏輯關系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案C和D的圖解。3. 判斷題 線性表的邏輯順序和存儲順序總是一致的。【解答】錯。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。 線性表的順序存儲結構優于鏈接存儲結構。【解答】錯。兩種存儲結構各有優缺點。 設p，q是指針，若p=q，則*p=*q。【解答】錯。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相

11、同。 線性結構的基本特征是：每個元素有且僅有一個直接前驅和一個直接后繼。【解答】錯。每個元素最多只有一個直接前驅和一個直接后繼，第一個元素沒有前驅，最后一個元素沒有后繼。 在單鏈表中，要取得某個元素，只要知道該元素所在結點的地址即可，因此單鏈表是隨機存取結構。【解答】錯。要找到該結點的地址，必須從頭指針開始查找，所以單鏈表是順序存取結構。4請說明順序表和單鏈表各有何優缺點，并分析下列情況下，采用何種存儲結構更好些。 若線性表的總長度基本穩定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。 如果n個線性表同時并存，并且在處理過程中各表的長度會動態發生變化。 描述一個城市的設計和

12、規劃。【解答】順序表的優點： 無需為表示表中元素之間的邏輯關系而增加額外的存儲空間； 可以快速地存取表中任一位置的元素（即隨機存取）。順序表的缺點： 插入和刪除操作需移動大量元素； 表的容量難以確定； 造成存儲空間的“碎片”。單鏈表的優點： 不必事先知道線性表的長度； 插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點： 指針的結構性開銷； 存取表中任意元素不方便，只能進行順序存取。 應選用順序存儲結構。因為順序表是隨機存取結構，單鏈表是順序存取結構。本題很少進行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應選用順序存儲結構。 應選用鏈接存儲結構。鏈表容易實現表容量的擴充，適合

13、表的長度動態發生變化。 應選用鏈接存儲結構。因為一個城市的設計和規劃涉及活動很多，需要經常修改、擴充和刪除各種信息，才能適應不斷發展的需要。而順序表的插入、刪除的效率低，故不合適。5算法設計 設計一個時間復雜度為(n)的算法，實現將數組An中所有元素循環右移k個位置。【解答】算法思想請參見主教材第一章思想火花。下面給出具體算法。分析算法，第一次調用Reverse函數的時間復雜度為O(k)，第二次調用Reverse函數的時間復雜度為O(n-k)，第三次調用Reverse函數的時間復雜度為O(n)，所以，總的時間復雜度為O(n)。 已知數組An中的元素為整型，設計算法將其調整為左右兩部分，左邊所有

14、元素為奇數，右邊所有元素為偶數，并要求算法的時間復雜度為(n)。【解答】從數組的兩端向中間比較，設置兩個變量i和j，初始時i=0，j=n-1，若Ai為偶數并且Aj為奇數，則將Ai與Aj交換。具體算法如下：分析算法，兩層循環將數組掃描一遍，所以，時間復雜度為(n)。 試編寫在無頭結點的單鏈表上實現線性表的插入操作的算法，并和帶頭結點的單鏈表上的插入操作的實現進行比較。【解答】參見2.2.3。 試分別以順序表和單鏈表作存儲結構，各寫一實現線性表就地逆置的算法。【解答】順序表的逆置，即是將對稱元素交換，設順序表的長度為length，則將表中第i個元素與第length-i-1個元素相交換。具體算法如下

15、：單鏈表的逆置請參見2.2.4算法2-4和算法2-6。 假設在長度大于1的循環鏈表中，即無頭結點也無頭指針，s為指向鏈表中某個結點的指針，試編寫算法刪除結點s的前趨結點。【解答】利用單循環鏈表的特點，通過指針s可找到其前驅結點r以及r的前驅結點p，然后將結點r刪除，如圖2-11所示，具體算法如下： 已知一單鏈表中的數據元素含有三類字符：字母、數字和其他字符。試編寫算法，構造三個循環鏈表，使每個循環鏈表中只含同一類字符。【解答】在單鏈表A中依次取元素，若取出的元素是字母，把它插入到字母鏈表B 中，若取出的元素是數字，則把它插入到數字鏈表D中，直到鏈表的尾部，這樣表B，D，A中分別存放字母、數字和

16、其他字符。具體算法如下： 設單鏈表以非遞減有序排列，設計算法實現在單鏈表中刪去值相同的多余結點。【解答】從頭到尾掃描單鏈表，若當前結點的元素值與后繼結點的元素值不相等，則指針后移；否則刪除該后繼結點。具體算法如下： 判斷帶頭結點的雙循環鏈表是否對稱。【解答】設工作指針p和q分別指向循環雙鏈表的開始結點和終端結點，若結點p和結點q的數據域相等，則工作指針p后移，工作指針q前移，直到指針p和指針 q指向同一結點（循環雙鏈表中結點個數為奇數），或結點q成為結點p的前驅（循環雙鏈表中結點個數為偶數）。如圖2-12所示。學習自測及答案 1. 已知一維數組A采用順序存儲結構，每個元素占用4個存儲單元，第9

17、個元素的地址為144，則第一個元素的地址是（ ）。A 108 B 180 C 176 D 112【解答】D2在長度為n的線性表中查找值為x的數據元素的時間復雜度為： （ ）。 A O(0) B O(1) C O(n) D O(n2)【解答】C3在一個長度為n的順序表的第i（1in+1）個元素之前插入一個元素，需向后移動（ ）個元素，刪除第i（1in）個元素時，需向前移動（ ）個元素。【解答】n-i+1，n-i 4在單鏈表中，除了頭結點以外，任一結點的存儲位置由（ ）指示。【解答】其前趨結點的指針域 5當線性表采用順序存儲結構時，其主要特點是（ ）。【解答】邏輯結構中相鄰的結點在存儲結構中仍相鄰

18、6在雙鏈表中，每個結點設置了兩個指針域，其中一個指向（ ）結點，另一個指向（ ）結點。【解答】前驅，后繼7設A是一個線性表（a1, a2, , an），采用順序存儲結構，則在等概率的前提下，平均每插入一個元素需要移動的元素個數為多少？若元素插在ai與ai+1之間（1in）的概率為 ，則平均每插入一個元素所要移動的元素個數又是多少？【解答】 ，。8線性表存放在整型數組Aarrsize的前elenum 個單元中，且遞增有序。編寫算法，將元素x插入到線性表的適當位置上，以保持線性表的有序性，并且分析算法的時間復雜度。【解答】本題是在一個遞增有序表中插入元素x，基本思路是從有序表的尾部開始依次取元素與x比較，若大于x，此元素后移一位，再取它前面一個元素重復上述步驟；否則，找到插入位置，將x插入。具體算法如下：9. 已知單鏈表中各