1、第 1 章 緒 論課后習題講解1. 填空(1)()是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。【解答】數據元素3()是數據的最小單位，()是討論數據結構時涉及的最小數據單位。【解答】數據項，數據元素 【分析】數據結構指的是數據元素以及數據元素之間的關系。 從邏輯關系上講，數據結構主要分為( )、( )、( )和( )。【解答】集合，線性結構，樹結構，圖結構 數據的存儲結構主要有( )和( )兩種基本方法，不論哪種存儲結構，都要存儲兩方面的內容：()和( )。【解答】順序存儲結構，鏈接存儲結構，數據元素，數據元素之間的關系 算法具有五個特性，分別是( )、( )、()、( )

2、、( )。【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性 算法的描述方法通常有( )、( )、()和( )四種，其中，( )被稱為算法語言。【解答】自然語言，程序設計語言，流程圖，偽代碼，偽代碼 在一般情況下，一個算法的時間復雜度是( )的函數。【解答】問題規模設待處理問題的規模為 n,若一個算法的時間復雜度為一個常數，則表示成數量級的形式為()，若為n*log25n，則表示成數量級的形式為()。【解答】0 (1)，O (nlog2n)【分析】用大0記號表示算法的時間復雜度，需要將低次冪去掉，將最高次冪的系數去掉。2. 選擇題 順序存儲結構中數據元素之間的邏輯關系是由( )

3、表示的，鏈接存儲結構中的數據元素之間的邏輯關 系是由( )表示的。A 線性結構 B 非線性結構 C 存儲位置 D 指針【解答】 C， D【分析】順序存儲結構就是用一維數組存儲數據結構中的數據元素，其邏輯關系由存儲位置(即元素在數 組中的下標)表示；鏈接存儲結構中一個數據元素對應鏈表中的一個結點，元素之間的邏輯關系由結點中 的指針表示。假設有如下遺產繼承規則：丈夫和妻子可以相互繼承遺產；子女可以繼承父親或母親的遺產；子女間不能相互繼承。則表示該遺產繼承關系的最合適的數據結構應該是（）。A樹B圖C線性表D集合【解答】B【分析】將丈夫、妻子和子女分別作為數據元素，根據題意畫岀邏輯結構圖。團17還產繼

4、承邏輯結構圖算法指的是（）。A對特定問題求解步驟的一種描述，是指令的有限序列。B計算機程序C解決問題的計算方法 D數據處理【解答】A【分析】計算機程序是對算法的具體實現；簡單地說，算法是解決問題的方法；數據處理是通過算法完成 的。所以，只有A是算法的準確定義。下面（）不是算法所必須具備的特性。A有窮性B確切性C高效性D可行性【解答】C【分析】高效性是好算法應具備的特性。算法分析的目的是（），算法分析的兩個主要方面是（）。A找岀數據結構的合理性 B研究算法中輸入和輸岀的關系C分析算法的效率以求改進 D分析算法的易讀性和文檔性E空間性能和時間性能 F正確性和簡明性G可讀性和文檔性H數據復雜性和程序

5、復雜性【解答】C, E3.判斷題 算法的時間復雜度都要通過算法中的基本語句的執行次數來確定。【解答】錯。時間復雜度要通過算法中基本語句執行次數的數量級來確定。每種數據結構都具備三個基本操作：插入、刪除和查找。【解答】錯。如數組就沒有插入和刪除操作。此題注意是每種數據結構。所謂數據的邏輯結構指的是數據之間的邏輯關系。【解答】錯。是數據之間的邏輯關系的整體。 邏輯結構與數據元素本身的內容和形式無關。【解答】對。因此邏輯結構是數據組織的主要方面。基于某種邏輯結構之上的基本操作，其實現是唯一的。【解答】錯。基本操作的實現是基于某種存儲結構設計的，因而不是唯一的4.分析以下各程序段，并用大0記號表示其執

6、行時間 1=1； while (i<n-l) i+;(8)while (i+j<=n) if (i>i)j+.else(5) for (i=l; 1<=11, i+) far (j-1； j<，廿+) for (k<j; k+)dokMc+1 嘩 i+; while (i<=n) y=0,while (y+lJ*Cy+l)<=n)【解答】 基本語句是k=k+1O*i，共執行了 n-2次，所以T(n)=O(n)。基本語句是k=k+1O*i，共執行了 n次，所以T(n)=O(n)。分析條件語句，每循環一次，i+j整體加1，共循環n次，所以T(n)=O

7、(n)設循環體共執行T(n)次，每循環一次，循環變量y加1，最終T(n)=y，即:仃(n)+1)2 <n，所以 T(n)=O(n1/2)。咖產孔(詢x+是基本語句，所以-5設有數據結構(D, R),其中D=1,2, 3, 4, 5, 6，R=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)。試畫出其邏輯結構圖并指出屬于何種結構【解答】其邏輯結構圖如圖1-3所示，它是一種圖結構。gll-3邏揖錨構圖6. 為整數定義一個抽象數據類型，包含整數的常見運算，每個運算對應一個基本操作，每個基本操作的接口需定義前置條件、輸入、功能、輸岀和后置條件。【解答

8、】整數的抽象數據類型定義如下：ADT integerData整數a：可以是正整數(1,2, 3,)、負整數(-1,-2,-3,)和零OperationConstructor前置條件：整數a不存在輸入：一個整數 b 功能：構造一個與輸入值相同的整數 輸出：無后置條件：整數 a 具有輸入的值Set前置條件：存在一個整數 a 輸入：一個整數 b功能：修改整數 a 的值，使之與輸入的整數值相同 輸出：無后置條件：整數 a 的值發生改變Add前置條件：存在一個整數 a 輸入：一個整數 b 功能：將整數 a 與輸入的整數 b 相加 輸出：相加后的結果后置條件：整數 a 的值發生改變Sub前置條件：存在一個

9、整數 a 輸入：一個整數 b 功能：將整數 a 與輸入的整數 b 相減 輸出：相減的結果后置條件：整數 a 的值發生改變Multi前置條件：存在一個整數 a 輸入：一個整數 b 功能：將整數 a 與輸入的整數 b 相乘 輸出：相乘的結果后置條件：整數 a 的值發生改變Div 前置條件：存在一個整數 a 輸入：一個整數 b 功能：將整數 a 與輸入的整數 b 相除 輸出：若整數 b 為零，則拋出除零異常，否則輸出相除的結果 后置條件：整數 a 的值發生改變Mod前置條件：存在一個整數 a 輸入：一個整數 b 功能：求當前整數與輸入整數的模，即正的余數 輸出：若整數 b 為零，則拋出除零異常，否則

10、輸出取模的結果 后置條件：整數 a 的值發生改變Equal前置條件：存在一個整數 a輸入：一個整數b功能：判斷整數a與輸入的整數b是否相等 輸岀：若相等返回1，否則返回0后置條件：整數a的值不發生改變endADT7. 求多項式A(x)的算法可根據下列兩個公式之一來設計： A(x)=anxn+an-1xn- 1+a1x+a0 A(x)=(anx+an - 1)x+ +a1)x)+a0根據算法的時間復雜度分析比較這兩種算法的優劣。【解答】第二種算法的時間性能要好些。第一種算法需執行大量的乘法運算，而第二種算法進行了優化, 減少了不必要的乘法運算。8. 算法設計(要求：算法用偽代碼和C+描述，并分析

11、最壞情況下的時間復雜度)對一個整型數組An設計一個排序算法。【解答】下面是簡單選擇排序算法的偽代碼描述。建久對II個記錄進行趟簡單選擇排序：y 14在無序區i> n-1中選取最小記錄,設其下標為迥城； 1.2將最小記錄與第1個記錄交換;下面是簡單選擇排序算法的 C+描述。簡單選擇排序算法Sei比詣口n void Selects口mtn)(for Ci=0,i+)聞船T記錄講行片1趟簡單選揮排序(indesH;for (j=i+ln j<n; j+)曲E無序區中選取最小記錄if (ij <rmdex|) indej滬if (indenM) ririndex; J哎換無素)n-2

12、 m-1分析算法，有兩層嵌套的for循環，所以，-，-'11找岀整型數組An中元素的最大值和次最大值。【解答】算法的偽代碼描述如下：將前兩亍元素進行比糕 較大者啟到max中，較小者放到nniax中；" 2從第3個元素開皓直到最后一個元素依歡屜元素州小執行下列操作: 2.1如果血】財趣，則擁i為最犬值，原來的最大值為次最大值 2.2否則，如果Apnma祐則最大值不變，At為袂最大值；3.輸出最大值max,次最大值nmaxj算法的C+描述如下:最大值和次最大值算法P/laXNextIVlax |void Max_NextMax (int A , int n, int &m

13、axP int & nmax)( if (AO>=A1) maA0Fnmax=A 1 ;)else ma=A 1 ; ninaAfO;)for (i=2t i<n; i+)if (Ai>=max)(nma=max;mas=Ai;else if (Ai>nmax) nmaAf i Rcout«"K大值rfc最大值"«nmaz«endl, 分析算法，只有一層循環，共執行 n-2次，所以，T（n）=O（n）學習自測及答案1 順序存儲結構的特點是（），鏈接存儲結構的特點是（）。【解答】用元素在存儲器中的相對位置來表示數據

14、元素之間的邏輯關系，用指示元素存儲地址的指針表示 數據元素之間的邏輯關系。2. 算法在發生非法操作時可以作岀處理的特性稱為（）。【解答】健壯性3. 常見的算法時間復雜度用大O記號表示為：常數階（）、對數階（）、線性階（）、平方階（）和指數階（）【解答】O （1），O （Iog2n） ，O （n），O （n2），O （2n）4將下列函數按它們在n時的無窮大階數，從小到大排列。n, n-n3+7n5, nlogn, 2n/2, n3, Iog2n, n1/2+log2n, (3/2)n, n!, n2+log2n【解答】Iog2n, n1/2+Iog2n, n, nlog2n, n2+log2n,

15、 n3, n-n3+7n5, 2n/2, (3/2)n, n!5試描述數據結構和抽象數據類型的概念與程序設計語言中數據類型概念的區別。【解答】數據結構是指相互之間存在一定關系的數據元素的集合。而抽象數據類型是指一個數據結構以及 定義在該結構上的一組操作。程序設計語言中的數據類型是一個值的集合和定義在這個值集上一組操作的 總稱。抽象數據類型可以看成是對數據類型的一種抽象。6.對下列用二元組表示的數據結構，試分別畫岀對應的邏輯結構圖，并指岀屬于何種結構。 A=(D , R), 其中 D=a1, a2, a3, a4, R= B=(D ,R),其中D=a, b,c, d, e, f,R=, C=(

16、D, R)，其中D=a, b, c, d, e,f,R=, D=(D ,R),其中D=1,2,3, 4, 5, 6,R=(1,2), (1,4) ,(2, 3), (2, 4) , (3, 4), (3, 5) , (3, 6) , (4,6)【解答】 屬于集合,其邏輯結構圖如圖1-4(a)所示； 屬于線性結構,其邏輯結構圖如圖1-4(b)所示; 屬于樹結構,其邏輯結構圖如圖1-4(c)所示； 屬于圖結構,其邏輯結構圖如圖1-4(d)所示。圖Z 第？題對應的邏輯結構圖7.求下列算法的時間復雜度。count=0; x=1;while (x x*=2;count+;return count;【解答

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

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

19、析】操作示意圖如圖 2-9所示：©2-9帶尾指針的循環輕表中插入和刪除操作示意圖一個具有n個結點的單鏈表，在指針p所指結點后插入一個新結點的時間復雜度為（）；在給定值為x的結點后插入一個新結點的時間復雜度為（）。【解答】0 （1），0 （n）【分析】在p所指結點后插入一個新結點只需修改指針，所以時間復雜度為0（1）;而在給定值為x的結點后插入一個新結點需要先查找值為x的結點，所以時間復雜度為0（n）。 可由一個尾指針唯一確定的鏈表有（ ）、（ ）、（ ）。【解答】循環鏈表，循環雙鏈表，雙鏈表2. 選擇題 線性表的順序存儲結構是一種（ ）的存儲結構，線性表的鏈接存儲結構是一種（ ）的存

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

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

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

23、一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、單循環鏈 表都不合適，刪除最后一個結點需要知道終端結點的前驅結點的地址，所以，帶尾指針的單循環鏈表不合 適，而循環雙鏈表滿足條件。 在具有 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 個元素依次插入到有序單鏈表中

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

25、ext=s; s->next=p;C p->next=s->next; s->next=p; D p->next=s; s->next=q;【解答】 B【分析】注意此題是在 q 和 p 之間插入新結點，所以，不用考慮修改指針的順序。(12) 在循環雙鏈表的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-

26、>next=p->next;C s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D s->prior=p; s->next=p->next; p->next->prior=s; p->next=s【解答】 D【分析】在鏈表中，對指針的修改必須保持線性表的邏輯關系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案C和D的圖解。（0備選答案C操作示意團（第4步指針修改無法進行）（b）備選答案D操住示意團U2-10雙梃表插入操作修改捋針操作示意圉3

27、.判斷題線性表的邏輯順序和存儲順序總是一致的。【解答】錯。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。線性表的順序存儲結構優于鏈接存儲結構。【解答】錯。兩種存儲結構各有優缺點。 設p，q是指針，若p=q，則*p=*q。【解答】錯。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。 線性結構的基本特征是：每個元素有且僅有一個直接前驅和一個直接后繼。【解答】錯。每個元素最多只有一個直接前驅和一個直接后繼，第一個元素沒有前驅，最后一個元素沒有 后繼。 在單鏈表中，要取得某個元素，只要知道該元素所在結點的地址即可，因此單鏈表是隨機存取結構 【解答】錯。要找到該結點的

28、地址，必須從頭指針開始查找，所以單鏈表是順序存取結構。4 請說明順序表和單鏈表各有何優缺點，并分析下列情況下，采用何種存儲結構更好些。若線性表的總長度基本穩定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。如果n個線性表同時并存，并且在處理過程中各表的長度會動態發生變化。描述一個城市的設計和規劃。【解答】順序表的優點： 無需為表示表中元素之間的邏輯關系而增加額外的存儲空間；可以快速地存取表中任一位置的元素（即隨機存取）。順序表的缺點：插入和刪除操作需移動大量元素； 表的容量難以確定； 造成存儲空間的“碎片”。單鏈表的優點： 不必事先知道線性表的長度；插入和刪除元素時只需修改指

29、針，不用移動元素。單鏈表的缺點： 指針的結構性開銷； 存取表中任意元素不方便，只能進行順序存取。應選用順序存儲結構。因為順序表是隨機存取結構，單鏈表是順序存取結構。本題很少進行插入和刪除 操作，所以空間變化不大，且需要快速存取，所以應選用順序存儲結構。應選用鏈接存儲結構。鏈表容易實現表容量的擴充，適合表的長度動態發生變化。 應選用鏈接存儲結構。因為一個城市的設計和規劃涉及活動很多，需要經常修改、擴充和刪除各種信息，才能適應不斷發展的需要。而順序表的插入、刪除的效率低，故不合適。5 算法設計 設計一個時間復雜度為O (n)的算法，實現將數組 An中所有元素循環右移k個位置 【解答】算法思想請參見

30、主教材第一章思想火花。下面給岀具體算法。循環右移算法Convers亡void Converse (int A , int nt int k)(Reverse O.k-1),Reverse (A, k, n-1);Reverse (A, 0, n-J);void Reverse(int A , int from, int to)! 鵬數組 A 中元素從 fiom 到 8 逆置 (for (1=0, i< (to-from+l)J2; i+)A frnm+i *Atoi;膠換元素分析算法，第一次調用Reverse函數的時間復雜度為 O(k)，第二次調用Reverse函數的時間復雜度為O(n-

31、k)，第三次調用Reverse函數的時間復雜度為O(n)，所以，總的時間復雜度為 O(n)。 已知數組An中的元素為整型，設計算法將其調整為左右兩部分，左邊所有元素為奇數，右邊所有元 素為偶數，并要求算法的時間復雜度為O(n)。【解答】從數組的兩端向中間比較，設置兩個變量i和j，初始時i=0, j=n-1 ,若Ai為偶數并且Aj為奇數，則將Ai與Aj交換。具體算法如下：敎俎奇儒調蔓算法Adjustvoid Adjust (int A t n)i=0; j=nUwhile (i<j)(while (Ai2!-0) i+;while (Aj % 2=0) j- if (i<j)直因)分

32、析算法，兩層循環將數組掃描一遍，所以，時間復雜度為O(n)。試編寫在無頭結點的單鏈表上實現線性表的插入操作的算法，并和帶頭結點的單鏈表上的插入操作的實現進行比較。【解答】參見2.2.3。試分別以順序表和單鏈表作存儲結構，各寫一實現線性表就地逆置的算法。【解答】順序表的逆置，即是將對稱元素交換，設順序表的長度為length，則將表中第i個元素與第length-i-1個元素相交換。具體算法如下：丿順舟表逆置算法 RevergE template <class T> void Reversed data, mt length) for (i=0; i<=length/2, i+)t

33、anpdatap; datai=datalength-i-1; datalength-i-1 =tanp、*)單鏈表的逆置請參見 224算法2-4和算法2-6。假設在長度大于1的循環鏈表中，即無頭結點也無頭指針，s為指向鏈表中某個結點的指針，試編寫算法刪除結點s的前趨結點。【解答】利用單循環鏈表的特點，通過指針s可找到其前驅結點r以及r的前驅結點p,然后將結點r刪除，如圖2-11所示，具體算法如下：輔環槌衷間除算法Deltemplate <class T>void Del(Node<T> *s)(p=5,"工作指針p初貽化> Wife s的前弓臨點的前馳

34、結點,用P指示while (p->next->next!s)p=p_neKt,件p->ncxt;臉丸f的前馳結點* r的前號結直卩“ >nest;"刪除i所指結點delete r;12-11刪除結點s的前馳踣點操作示意圖 已知一單鏈表中的數據元素含有三類字符：字母、數字和其他字符。試編寫算法，構造三個循環鏈表，使每個循環鏈表中只含同一類字符。【解答】在單鏈表 A中依次取元素，若取岀的元素是字母，把它插入到字母鏈表B中，若取岀的元素是數字，則把它插入到數字鏈表 D中，直到鏈表的尾部，這樣表 B，D, A中分別存放字母、數字和其他字符。 具體算法如下：單璉表柝分算

35、法Adjusttemplate <class T>void Adjust (Node<T> *Ah Node<int> *D± Node<char> *B)D=new Node<int> D->next=D;"創逹空循環捱表D -存放數孚B=new Node<char> B- >next=B;"刨建空循環鏈表B存矽字符p=A, q=p>nezt,疔工作指針q初始化while (q)(if ('A'<=q->data)&& (q-&g

36、t;data>-Z*)i| | ('a' <=q->data) &&(q->data>z*) p->next=q->next; q->neKt=B->nest;B->neKt=qP."采用頭插法插在循環璉表B的頭結點的后面else if ('0,<=q>dala)&&(q*>data>-'9')(曠 >neztq- >nextp.q->neKt=D->next;H采用頭輛法播在循環靜就D的頭結點的后面els

37、e p=q;q=p->net;p->neKt=A; R=A; 瞬璉表A構造為循環鏈表,為除字陽和數字的耳他宇符) 設單鏈表以非遞減有序排列，設計算法實現在單鏈表中刪去值相同的多余結點。【解答】從頭到尾掃描單鏈表，若當前結點的元素值與后繼結點的元素值不相等，則指針后移；否則刪除 該后繼結點。具體算法如下：單粧表刪除相同值算法Purgevoid Purge(Nade<T> *firsC(pfirst->ncrt;while (p->nest) if (p->data= =p->next-> data) q=p->next;p- >n

38、ezt=q->nezt; ddele q;else pp->nsjt;判斷帶頭結點的雙循環鏈表是否對稱。【解答】設工作指針p和q分別指向循環雙鏈表的開始結點和終端結點，若結點p和結點q的數據域相等,則工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結點（循環雙鏈表中結點個數為奇數） 或結點q成為結點p的前驅（循環雙鏈表中結點個數為偶數）。如圖 2-12所示。E2-12判斷循環敦龍表對稱的操作示意圖判斷眾讎表對稱算法Equaltemplate <class T>stnxl DulNode(T data,DuINode<T> *piior, *next

39、;)；template <class T> bool Equal (DulNode<T> *firsC (p=fir st-n ext, q=first>prior; while (pq && p>priorq) if (p->data= =q- >data) p=p->next,FJ工作指針p后移q=q->prior;H工作指針q前移 else return 0,return 1,)學習自測及答案1.已知一維數組A采用順序存儲結構，每個元素占用4個存儲單元，第9個元素的地址為144，則第一個元素的地址是()。A 10

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

41、個指針域，其中一個指向（）結點，另一個指向（）結點。【解答】前驅，后繼7設A是一個線性表（a1, a2,，an ），采用順序存儲結構，則在等概率的前提下，平均每插入一個元素需要移動的元素個數為多少？若元素插在ai與ai+1之間（1<i <n）的概率為"，則平均每插入一個元素所要移動的元素個數又是多少？ 【解答】8線性表存放在整型數組 Aarrsize的前elenum個單元中，且遞增有序。編寫算法，將元素 x插入到線 性表的適當位置上，以保持線性表的有序性，并且分析算法的時間復雜度。【解答】本題是在一個遞增有序表中插入元素 x，基本思路是從有序表的尾部開始依次取元素與x比較

42、，若大于x，此元素后移一位，再取它前面一個元素重復上述步驟；否則，找到插入位置，將x插入。具體算法如下：有序咂序表插入算法Insert const int arrsize=100p class S eqList ( private:int dataarrsize ? int denum,public:Insert (ini x),void SeqList: Insert Cint z)if (elenum= irsize) throw "overflow", else (i°:elenum-' 1;while (i>=l x<datai)dat

43、ai+l=datai,datai+l=x;9.已知單鏈表中各結點的元素值為整型且遞增有序，設計算法刪除鏈表中所有大于 mink且小于maxk的所有元素，并釋放被刪結點的存儲空間。【解答】因為是在有序單鏈表上的操作，所以，要充分利用其有序性。在單鏈表中查找第一個大于mink的結點和第一個小于maxk的結點，再將二者間的所有結點刪除。有序犍表刪除算法DeleteBetwe&ntemplate <class T>void DeleteB etween (Mode<T> * first, int mink, mt mank) (p=fir5t?while (p->

44、nezt && p->neKt->data<=mink) p=p >nexirif (p->next)( q=p->neKt± while (q-> data<maxk) u=q->nezt;p->next=q- >nextP delete 山qp10.設單循環鏈表L1,對其遍歷的結果是：x1, x2, x3,xn -1, xn。請將該循環鏈表拆成兩個單循環 鏈表L1和L2,使得L1中含有原L1表中序號為奇數的結點且遍歷結果為：x1, x3,；L2中含有原L1表 中序號為偶數的結點且遍歷結果為：,x4,

45、 x2 。【解答】算法如下：循環鏈表柝芬算DePatch template <class T> Node<T> *DePatch (Node<T> *L1)(L2=n'ew Mode<T > L2->next=L2p(l=Ll->nextf Ll->next=Ll, p=Ll; i=l; while (q!=Ll) if (i % 2=1)(川巫用尾插沬 p->nexl>qP p=q, p->neit=Ll, q=q->next, i+;) else L2->next=q; qTi;i+,

46、)第 3 章 特殊線性表棧、隊列和串課后習題講解1. 填空 設有一個空棧，棧頂指針為1000H,現有輸入序列為 1、2、3、4、5,經過push , push , pop, push,pop， push， push 后，輸出序列是( )，棧頂指針為( )。【解答】 23, 1003H 棧通常采用的兩種存儲結構是( )；其判定棧空的條件分別是( ),判定棧滿的條件分別是( )。【解答】順序存儲結構和鏈接存儲結構(或順序棧和鏈棧)，棧頂指針top= -1和top=NULL,棧頂指針top等于數組的長度和內存無可用空間3()可作為實現遞歸函數調用的一種數據結構。【解答】棧【分析】遞歸函數的調用和返回

47、正好符合后進先出性。 表達式 a*(b+c)-d 的后綴表達式是( )。【解答】 abc+*d- 【分析】將中綴表達式變為后綴表達式有一個技巧：將操作數依次寫下來,再將算符插在它的兩個操作數的后面。 棧和隊列是兩種特殊的線性表,棧的操作特性是( ),隊列的操作特性是( ),棧和隊列的主要區別 在于( )。【解答】后進先出,先進先出,對插入和刪除操作限定的位置不同 循環隊列的引入是為了克服( )。【解答】假溢出 數組 Qn 用來表示一個循環隊列, front 為隊頭元素的前一個位置, rear 為隊尾元素的位置,計算隊 列中元素個數的公式為( )。【解答】( rear-front+n ) % n

48、【分析】也可以是(rear-front ) % n,但rear-front的結果可能是負整數，而對一個負整數求模，其結果在不同的編譯器環境下可能會有所不同。用循環鏈表表示的隊列長度為n,若只設頭指針，則出隊和入隊的時間復雜度分別是()和()。【解答】0,0 (n)【分析】在帶頭指針的循環鏈表中,出隊即是刪除開始結點,這只需修改相應指針；入隊即是在終端結點 的后面插入一個結點,這需要從頭指針開始查找終端結點的地址。 串是一種特殊的線性表，其特殊性體現在（ ）。【解答】數據元素的類型是一個字符 兩個串相等的充分必要條件是（ ）。【解答】長度相同且對應位置的字符相等【分析】例如"abc&q

49、uot;工"abc " , "abc"工"bca"。2. 選擇題若一個棧的輸入序列是 1, 2, 3,，n，輸出序列的第一個元素是 n,則第i個輸出元素是（）。A 不確定 B n-i C n-i-1 D n-i+1【解答】 D【分析】此時,輸出序列一定是輸入序列的逆序。設棧S和隊列Q的初始狀態為空，元素 el、e2、e3、e4、e5、e6依次通過棧S, 個元素出棧后即進 入隊列Q,若6個元素出隊的順序是 e2、e4、e3、e6、e5、el，則棧S的容量至少應該是（）。A 6B 4C 3D 2【解答】 C【分析】由于隊列具有先進先出性，

50、所以，此題中隊列形同虛設，即出棧的順序也是e2、 e4、 e3、 e6、 e5、e1 。 一個棧的入棧序列是 1， 2， 3， 4， 5，則棧的不可能的輸出序列是（）。A 54321 B 45321 C 43512 D 12345【解答】 C【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現比該元素小并且是升序（指的是元素的序 號）的兩個元素。 設計一個判別表達式中左右括號是否配對的算法，采用（）數據結構最佳A 順序表 B 棧 C 隊列 D 鏈表【解答】 B【分析】每個右括號與它前面的最后一個沒有匹配的左括號配對，因此具有后進先出性。 在解決計算機主機與打印機之間速度不匹配問題時通常設置

51、一個打印緩沖區，該緩沖區應該是一個 （ ）結構。A棧B隊列C數組D線性表【解答】 B【分析】先進入打印緩沖區的文件先被打印，因此具有先進先出性。 一個隊列的入隊順序是 1， 2， 3， 4，則隊列的輸出順序是（ ）。A 4321 B 1234 C 1432 D 3241【解答】 B【分析】隊列的入隊順序和出隊順序總是一致的。 棧和隊列的主要區別在于（ ）。A 它們的邏輯結構不一樣 B 它們的存儲結構不一樣C所包含的運算不一樣 D插入、刪除運算的限定不一樣【解答】D【分析】棧和隊列的邏輯結構都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區別，任何數據結構在針對具體問題時包

52、含的運算都可能不同。 設數組Sn作為兩個棧S1和S2的存儲空間，對任何一個棧只有當Sn全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是（）。A S1的棧底位置為0, S2的棧底位置為n-1B S1的棧底位置為0, S2的棧底位置為n/2C S1的棧底位置為0，S2的棧底位置為nD S1的棧底位置為0，S2的棧底位置為1【解答】A【分析】兩棧共享空間首先兩個棧是相向增長的，棧底應該分別指向兩個棧中的第一個元素的位置，并注 意C+中的數組下標是從0開始的。 設有兩個串p和q，求q在p中首次出現的位置的運算稱作（）。A連接B模式匹配C求子串D求串長【解答】B3. 判斷題 有n個元素依次進棧，

53、則出棧序列有（n-1）/2種。）！【解答】錯。應該有 1 '種。 棧可以作為實現過程調用的一種數據結構。【解答】對。只要操作滿足后進先岀性，都可以采用棧作為輔助數據結構。 在棧滿的情況下不能做進棧操作，否則將產生“上溢”。【解答】對。 在循環隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是front=rear 。【解答】錯。這是隊空的判定條件，在循環隊列中要將隊空和隊滿的判定條件區別開。空串與空格串是相同的。【解答】錯。空串的長度為零，而空格串的長度不為0，其長度是串中空格的個數。4. 設有一個棧，元素進棧的次序為A，B，C, D，E,能否得到如下

54、岀棧序列，若能，請寫岀操作序列，若不能，請說明原因。 C，E，A，B，D C，B，A，D, E【解答】不能，因為在 C、E出棧的情況下，A一定在棧中，而且在 B的下面，不可能先于 B出棧。可 以，設I為進棧操作，0為入棧操作，則其操作序列為1110001010。5. 舉例說明順序隊列的“假溢岀”現象。【解答】假設有一個順序隊列，如圖3-6所示，隊尾指針rear=4，隊頭指針front=1，如果再有元素入隊,就會產生“上溢”，此時的“上溢”又稱為“假溢出”，因為隊列并不是真的溢出了，存儲隊列的數組中 還有2個存儲單元空閑，其下標分別為0和1。6.在操作序列push(1)、push(2)、pop、

55、push(5)、push、pop、push(6)之后，棧頂元素和棧底元素分別是什么？ ( push(k)表示整數k入棧，pop表示棧頂元素出棧。)【解答】棧頂元素為6，棧底元素為1。其執行過程如圖 3-7所示。入棧出桟(a) push Cl) j push Q)(b) pop j push(5) j push C7)團3T棧的執行過程示意團(c) pop 9 push (67.在操作序列 EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue EnQueue(9)之后，隊頭元素和隊尾元素分別是什么？(EnQueue(k)表示整數k

56、入隊，DeQueue表示隊頭元素出隊)。【解答】隊頭元素為5，隊尾元素為9。其執行過程如圖 3-8所示。出臥入趴1 335 75 7 9(a) EnQueue Cl) jEuQtcue (3(b)jEnQueue C5) jEnQtieue (7(c) DeQueue jEnQueue (9圖!3Y隊列的執行過程示意圖&空串和空格串有何區別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的 個數。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應包括這些空格符。空 串在串處理中可作為任意串的子串。9.算法設計 假設以不帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針。試設計相應的入隊和出隊的算法。【解答】出隊操作是在循環鏈表的頭部進行，相當于刪除開始結點，而入隊操作是在循環鏈表的尾部進行，相當于在終端結點之后插入一個結點。由于循環鏈表不帶頭結點，需要處理空表的特殊情況。入隊算法如下：循環隊列入叭算法