數(shù)據(jù)結構(C版)王紅梅_版課后答案

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

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

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

4、邏輯結構圖。 算法指的是（）。a 對特定問題求解步驟的一種描述，是指令的有限序列。b 計算機程序 c 解決問題的計算方法d數(shù)據(jù)處理【解答】 a【分析】計算機程序是對算法的具體實現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成的。所以，只有 a 是算法的準確定義。 下面（ ）不是算法所必須具備的特性。a 有窮性 b確切性 c高效性 d可行性【解答】 c【分析】高效性是好算法應具備的特性。 算法分析的目的是（ ），算法分析的兩個主要方面是（ ）。a 找出數(shù)據(jù)結構的合理性 b 研究算法中輸入和輸出的關系c 分析算法的效率以求改進 d 分析算法的易讀性和文檔性e 空間性能和時間性能 f 正確

5、性和簡明性g 可讀性和文檔性 h 數(shù)據(jù)復雜性和程序復雜性【解答】 c， e3. 判斷題 算法的時間復雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定?！窘獯稹垮e。時間復雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。 每種數(shù)據(jù)結構都具備三個基本操作：插入、刪除和查找?！窘獯稹垮e。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結構。 所謂數(shù)據(jù)的邏輯結構指的是數(shù)據(jù)之間的邏輯關系。【解答】錯。是數(shù)據(jù)之間的邏輯關系的整體。 邏輯結構與數(shù)據(jù)元素本身的內(nèi)容和形式無關。【解答】對。因此邏輯結構是數(shù)據(jù)組織的主要方面。 基于某種邏輯結構之上的基本操作，其實現(xiàn)是唯一的。【解答】錯?；静僮鞯膶崿F(xiàn)是基于某種存儲結構設計

6、的，因而不是唯一的。4. 分析以下各程序段，并用大o記號表示其執(zhí)行時間?！窘獯稹?基本語句是 k=k+10*i ，共執(zhí)行了 n-2 次，所以 t(n)=o(n) 。 基本語句是 k=k+10*i ，共執(zhí)行了 n 次，所以 t(n)=o(n) 。 分析條件語句，每循環(huán)一次，i+j整體加 1，共循環(huán) n 次，所以 t(n)=o(n) 。 設循環(huán)體共執(zhí)行 t(n) 次，每循環(huán)一次，循環(huán)變量y 加 1，最終 t(n)=y ，即：(t(n)+1)2 n，所以 t(n)=o(n 1/2)。 x+ 是基本語句，所以5 設 有 數(shù) 據(jù) 結 構 （ d ， r ） ， 其 中d=1,2,3,4,5,6，r=(1

7、,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)。試畫出其邏輯結構圖并指出屬于何種結構?！窘獯稹科溥壿嫿Y構圖如圖1-3 所示，它是一種圖結構。6. 為整數(shù)定義一個抽象數(shù)據(jù)類型，包含整數(shù)的常見運算，每個運算對應一個基本操作，每個基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)類型定義如下：adt integer data整數(shù) a：可以是正整數(shù) (1, 2, 3,) 、負整數(shù) (-1, -2, -3,) 和零operation constructor前置條件：整數(shù) a 不存在輸入：一個整數(shù) b功能：構造一個與輸入值相同的整數(shù)

8、輸出：無后置條件：整數(shù) a 具有輸入的值set前置條件：存在一個整數(shù)a輸入：一個整數(shù) b功能：修改整數(shù) a 的值，使之與輸入的整數(shù)值相同輸出：無后置條件：整數(shù) a 的值發(fā)生改變add前置條件：存在一個整數(shù)a輸入：一個整數(shù) b功能：將整數(shù) a 與輸入的整數(shù) b 相加輸出：相加后的結果后置條件：整數(shù) a 的值發(fā)生改變sub前置條件：存在一個整數(shù)a輸入：一個整數(shù) b功能：將整數(shù) a 與輸入的整數(shù) b 相減輸出：相減的結果后置條件：整數(shù) a 的值發(fā)生改變multi前置條件：存在一個整數(shù)a輸入：一個整數(shù) b功能：將整數(shù) a 與輸入的整數(shù) b 相乘輸出：相乘的結果后置條件：整數(shù) a 的值發(fā)生改變div前置

9、條件：存在一個整數(shù)a輸入：一個整數(shù) b功能：將整數(shù) a 與輸入的整數(shù) b 相除輸出：若整數(shù) b 為零，則拋出除零異常，否則輸出相除的結果后置條件：整數(shù) a 的值發(fā)生改變mod前置條件：存在一個整數(shù)a輸入：一個整數(shù) b功能：求當前整數(shù)與輸入整數(shù)的模，即正的余數(shù)輸出：若整數(shù) b 為零，則拋出除零異常，否則輸出取模的結果后置條件：整數(shù) a 的值發(fā)生改變equal前置條件：存在一個整數(shù)a輸入：一個整數(shù) b功能：判斷整數(shù) a 與輸入的整數(shù) b 是否相等輸出：若相等返回1，否則返回 0后置條件：整數(shù) a 的值不發(fā)生改變endadt7. 求多項式 a(x) 的算法可根據(jù)下列兩個公式之一來設計： a(x)=a

10、nxn+an-1xn-1+,+a1x+a0 a(x)=(,(anx+an-1)x+,+a1)x)+a0根據(jù)算法的時間復雜度分析比較這兩種算法的優(yōu)劣?！窘獯稹康诙N算法的時間性能要好些。第一種算法需執(zhí)行大量的乘法運算，而第二種算法進行了優(yōu)化，減少了不必要的乘法運算。8. 算法設計（要求：算法用偽代碼和c+描述，并分析最壞情況下的時間復雜度） 對一個整型數(shù)組 an 設計一個排序算法。【解答】下面是簡單選擇排序算法的偽代碼描述。下面是簡單選擇排序算法的c+描述。分析算法，有兩層嵌套的for循環(huán)，所以，。 找出整型數(shù)組an 中元素的最大值和次最大值。【解答】算法的偽代碼描述如下：算法的 c+描述如下：

11、分析算法，只有一層循環(huán)，共執(zhí)行n-2 次，所以， t(n)=o(n) 。學習自測及答案1. 順序存儲結構的特點是（），鏈接存儲結構的特點是（）?！窘獯稹坑迷卦诖鎯ζ髦械南鄬ξ恢脕肀硎緮?shù)據(jù)元素之間的邏輯關系，用指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關系。2. 算法在發(fā)生非法操作時可以作出處理的特性稱為（）?！窘獯稹拷研?.常見的算法時間復雜度用大記號表示為：常數(shù)階( ) 、對數(shù)階 ( ) 、線性階 () 、平方階( )和指數(shù)階 ( )?！窘獯稹?(1) ， (log2n)， (n) ， (n2) ， (2n)4. 將下列函數(shù)按它們在n 時的無窮大階數(shù)，從小到大排列。n, n-n3+7n

12、5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n【解答】 log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n!5. 試描述數(shù)據(jù)結構和抽象數(shù)據(jù)類型的概念與程序設計語言中數(shù)據(jù)類型概念的區(qū)別。【解答】數(shù)據(jù)結構是指相互之間存在一定關系的數(shù)據(jù)元素的集合。而抽象數(shù)據(jù)類型是指一個數(shù)據(jù)結構以及定義在該結構上的一組操作。程序設計語言中的數(shù)據(jù)類型是一個值的集合和定義在這個值集上一組操作的總稱。抽象數(shù)據(jù)類型可以看成是對數(shù)據(jù)類型的一種抽象。6. 對下列用二元組表

13、示的數(shù)據(jù)結構, 試分別畫出對應的邏輯結構圖，并指出屬于何種結構。 a=(d ， r)，其中d=a1, a2, a3, a4， r= b=(d ， r)，其中d=a, b, c, d, e, f， r=, c=( 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)所示； 屬于樹結構， 其邏

14、輯結構圖如圖1-4(c)所示； 屬于圖結構， 其邏輯結構圖如圖1-4(d)所示。7. 求下列算法的時間復雜度。count=0; x=1; while (x x*=2; count+;return count;【解答】 (log2n)第 2章 線性表課后習題講解1. 填空 在順序表中，等概率情況下，插入和刪除一個元素平均需移動（）個元素，具體移動元素的個數(shù)與（）和（ ）有關?！窘獯稹勘黹L的一半，表長，該元素在表中的位置 順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第 5 個元素的存儲地址是 （ ）?！窘獯稹?108【分析】第 5 個元素的存儲地址=第 1 個元素的存儲地址 (5

15、1) × 2=108 設單鏈表中指針 p 指向結點 a，若要刪除 a 的后繼結點（假設a 存在后繼結點） ，則需修改指針的操作為（ ）?！窘獯稹?p->next=(p->next)->next 單鏈表中設置頭結點的作用是（）?！窘獯稹繛榱诉\算方便【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。 非空的單循環(huán)鏈表由頭指針head 指示，則其尾結點（由指針p 所指）滿足（）?！窘獯稹?p->next=head【分析】如圖 2-8 所示。 在由尾指針 rear指示的單循環(huán)鏈表中，在表尾插入一個結點s 的操作序列是（）；刪除開始結點的操作序列為（ ）?！窘?/p>

16、答】 s->next =rear->next; rear->next =s; rear =s; q=rear->next->next; rear->next->next=q->next; delete q;【分析】操作示意圖如圖2-9 所示： 一個具有 n 個結點的單鏈表，在指針p 所指結點后插入一個新結點的時間復雜度為（）；在給定值為x 的結點后插入一個新結點的時間復雜度為（）?！窘獯稹?(1) ， (n)【分析】 在 p 所指結點后插入一個新結點只需修改指針，所以時間復雜度為 (1) ；而在給定值為 x 的結點后插入一個新結點需要先查找值為x

17、 的結點，所以時間復雜度為 (n) 。 可由一個尾指針唯一確定的鏈表有（）、 （ ） 、 （ ） ?！窘獯稹垦h(huán)鏈表，循環(huán)雙鏈表，雙鏈表2. 選擇題 線性表的順序存儲結構是一種（）的存儲結構，線性表的鏈接存儲結構是一種（）的存儲結構。a 隨機存取 b 順序存取 c 索引存取 d散列存取【解答】 a， b【分析】參見 2.2.1 。 線性表采用鏈接存儲時，其地址（）。a 必須是連續(xù)的 b部分地址必須是連續(xù)的 c 一定是不連續(xù)的 d連續(xù)與否均可以【解答】 d【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。 單

18、循環(huán)鏈表的主要優(yōu)點是（）。a 不再需要頭指針了b 從表中任一結點出發(fā)都能掃描到整個鏈表；c 已知某個結點的位置后，能夠容易找到它的直接前趨；d 在進行插入、刪除操作時，能更好地保證鏈表不斷開。【解答】 b 鏈表不具有的特點是（）。a 可隨機訪問任一元素b 插入、刪除不需要移動元素c 不必事先估計存儲空間d 所需空間與線性表長度成正比【解答】 a 若某線性表中最常用的操作是取第i個元素和找第 i 個元素的前趨，則采用（）存儲方法最節(jié)省時間。a 順序表 b單鏈表 c雙鏈表 d單循環(huán)鏈表【解答】 a【分析】線性表中最常用的操作是取第i個元素，所以，應選擇隨機存取結構即順序表，同時在順序表中查找第 i

19、 個元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取，查找第i 個元素的前趨也不方便，雙鏈表雖然能快速查找第i 個元素的前趨，但不能實現(xiàn)隨機存取。 若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除第一個結點，則采用（ ）存儲方法最節(jié)省時間。a 單鏈表 b帶頭指針的單循環(huán)鏈表c雙鏈表 d帶尾指針的單循環(huán)鏈表【解答】 d【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個結點，其時間性能是 o(1) ，所以，答案是 d 。 若鏈表中最常用的操作是在最后一個結點之后插入一個結

20、點和刪除最后一個結點，則采用（ ）存儲方法最節(jié)省運算時間。a 單鏈表 b循環(huán)雙鏈表 c 單循環(huán)鏈表 d帶尾指針的單循環(huán)鏈表【解答】 b【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、單循環(huán)鏈表都不合適，刪除最后一個結點需要知道終端結點的前驅(qū)結點的地址，所以，帶尾指針的單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。 在具有 n 個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是（）。a o(1) b o(n) c o(n2) d o(nlog2n)【解答】 b【分析】首先應順序查找新結點在單鏈表中的位置。 對于 n 個元素組成的線性表，建立一個有序單鏈表的時

21、間復雜度是（）。a o(1) b o(n) c o(n2) d o(nlog2n)【解答】 c【分析】該算法需要將n 個元素依次插入到有序單鏈表中，而插入每個元素需o(n) 。 使用雙鏈表存儲線性表，其優(yōu)點是可以（）。a 提高查找速度 b更方便數(shù)據(jù)的插入和刪除c 節(jié)約存儲空間 d很快回收存儲空間【解答】 b【分析】在鏈表中一般只能進行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針域，顯然不能節(jié)約存儲空間，對于動態(tài)存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性，所以，其插入和刪除操作更加方便。 在一個單鏈表中， 已知 q 所指結點是 p 所指結點的直接前驅(qū)，若在 q

22、 和 p 之間插入 s 所指結點，則執(zhí)行（ ）操作。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;【解答】 b【分析】注意此題是在q 和 p 之間插入新結點，所以，不用考慮修改指針的順序。 在循環(huán)雙鏈表的 p 所指結點后插入 s 所指結點的操作是（）。a p->next=s; s->prior=p; p->next->prior=s; s->

23、;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 s->prior=p; s->next=p->next; p->next->prior=s; p->next=s【解答】 d【分析】在鏈表中，對指針的修改必須保持線性表的邏輯關系，否則，將違背線性表的邏輯特征，圖

24、 2-10給出備選答案 c和 d的圖解。3. 判斷題 線性表的邏輯順序和存儲順序總是一致的?！窘獯稹垮e。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。 線性表的順序存儲結構優(yōu)于鏈接存儲結構。【解答】錯。兩種存儲結構各有優(yōu)缺點。 設 p， q 是指針，若 p=q，則 *p=*q 。【解答】錯。 p=q 只能表示 p 和 q 指向同一起始地址，而所指類型則不一定相同。 線性結構的基本特征是：每個元素有且僅有一個直接前驅(qū)和一個直接后繼。【解答】錯。每個元素最多只有一個直接前驅(qū)和一個直接后繼，第一個元素沒有前驅(qū)，最后一個元素沒有后繼。 在單鏈表中， 要取得某個元素， 只要知道該元

25、素所在結點的地址即可，因此單鏈表是隨機存取結構?！窘獯稹垮e。要找到該結點的地址，必須從頭指針開始查找，所以單鏈表是順序存取結構。4. 請說明順序表和單鏈表各有何優(yōu)缺點，并分析下列情況下，采用何種存儲結構更好些。 若線性表的總長度基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。 如果 n 個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化。 描述一個城市的設計和規(guī)劃?！窘獯稹?順序表的優(yōu)點： 無需為表示表中元素之間的邏輯關系而增加額外的存儲空間； 可以快速地存取表中任一位置的元素（即隨機存?。ｍ樞虮淼娜秉c：插入和刪除操作需移動大量元素； 表的容量難以確定；造成

26、存儲空間的“碎片” 。單鏈表的優(yōu)點：不必事先知道線性表的長度；插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點：指針的結構性開銷；存取表中任意元素不方便，只能進行順序存取。 應選用順序存儲結構。 因為順序表是隨機存取結構，單鏈表是順序存取結構。 本題很少進行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應選用順序存儲結構。 應選用鏈接存儲結構。鏈表容易實現(xiàn)表容量的擴充，適合表的長度動態(tài)發(fā)生變化。 應選用鏈接存儲結構。 因為一個城市的設計和規(guī)劃涉及活動很多，需要經(jīng)常修改、 擴充和刪除各種信息，才能適應不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。5. 算法設計 設計一個

27、時間復雜度為(n) 的算法，實現(xiàn)將數(shù)組an 中所有元素循環(huán)右移k 個位置?！窘獯稹克惴ㄋ枷胝垍⒁娭鹘滩牡谝徽滤枷牖鸹?。下面給出具體算法。分析算法， 第一次調(diào)用 reverse 函數(shù)的時間復雜度為o(k) ，第二次調(diào)用 reverse 函數(shù)的時間復雜度為 o(n-k) ，第三次調(diào)用 reverse 函數(shù)的時間復雜度為o(n) ，所以，總的時間復雜度為o(n) 。 已知數(shù)組 an 中的元素為整型， 設計算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)， 右邊所有元素為偶數(shù)，并要求算法的時間復雜度為(n) 。【解答】從數(shù)組的兩端向中間比較，設置兩個變量i 和 j ，初始時 i=0 ，j=n-1 ，若 a

28、i為偶數(shù)并且 aj為奇數(shù)，則將 ai與 aj交換。具體算法如下：分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時間復雜度為(n) 。 試編寫在無頭結點的單鏈表上實現(xiàn)線性表的插入操作的算法，并和帶頭結點的單鏈表上的插入操作的實現(xiàn)進行比較。【解答】參見 2.2.3 。 試分別以順序表和單鏈表作存儲結構，各寫一實現(xiàn)線性表就地逆置的算法?！窘獯稹宽樞虮淼哪嬷茫词菍ΨQ元素交換，設順序表的長度為length ，則將表中第i 個元素與第 length-i-1個元素相交換。具體算法如下：單鏈表的逆置請參見2.2.4算法 2-4 和算法 2-6 。 假設在長度大于 1 的循環(huán)鏈表中， 即無頭結點也無頭指針， s

29、為指向鏈表中某個結點的指針，試編寫算法刪除結點 s 的前趨結點?！窘獯稹坷脝窝h(huán)鏈表的特點，通過指針s 可找到其前驅(qū)結點r 以及 r 的前驅(qū)結點 p，然后將結點 r 刪除，如圖 2-11 所示，具體算法如下： 已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、 數(shù)字和其他字符。 試編寫算法， 構造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類字符?！窘獯稹吭趩捂湵?a 中依次取元素，若取出的元素是字母，把它插入到字母鏈表b 中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表d 中，直到鏈表的尾部，這樣表b，d， a 中分別存放字母、數(shù)字和其他字符。具體算法如下： 設單鏈表以非遞減有序排列，設計算法實現(xiàn)在單鏈表

30、中刪去值相同的多余結點?！窘獯稹繌念^到尾掃描單鏈表，若當前結點的元素值與后繼結點的元素值不相等，則指針后移；否則刪除該后繼結點。具體算法如下： 判斷帶頭結點的雙循環(huán)鏈表是否對稱?！窘獯稹吭O工作指針p 和 q 分別指向循環(huán)雙鏈表的開始結點和終端結點，若結點p 和結點 q的數(shù)據(jù)域相等，則工作指針 p 后移，工作指針 q 前移，直到指針 p 和指針 q 指向同一結點（循環(huán)雙鏈表中結點個數(shù)為奇數(shù)） ，或結點 q 成為結點 p 的前驅(qū)（循環(huán)雙鏈表中結點個數(shù)為偶數(shù)）。如圖 2-12 所示。學習自測及答案1. 已知一維數(shù)組 a 采用順序存儲結構，每個元素占用4 個存儲單元，第9 個元素的地址為144，則第一

31、個元素的地址是（）。a 108 b 180 c 176 d 112【解答】 d2. 在長度為 n 的線性表中查找值為x 的數(shù)據(jù)元素的時間復雜度為：（ ） 。a o(0) b o(1) c o(n) d o(n2)【解答】 c3. 在一個長度為 n 的順序表的第i （1 i n+1）個元素之前插入一個元素，需向后移動 （ ） 個元素，刪除第 i （1 i n）個元素時，需向前移動（）個元素?！窘獯稹?n-i+1 ， n-i4. 在單鏈表中，除了頭結點以外，任一結點的存儲位置由（）指示?！窘獯稹科淝摆吔Y點的指針域5. 當線性表采用順序存儲結構時，其主要特點是（）?！窘獯稹窟壿嫿Y構中相鄰的結點在存儲

32、結構中仍相鄰6. 在雙鏈表中，每個結點設置了兩個指針域，其中一個指向（）結點，另一個指向（）結點?！窘獯稹壳膀?qū)，后繼7. 設 a 是一個線性表（ a1, a2, an ），采用順序存儲結構，則在等概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為多少？若元素插在ai 與 ai+1 之間（ 1 i n）的概率為 ，則平均每插入一個元素所要移動的元素個數(shù)又是多少？【解答】，。8. 線性表存放在整型數(shù)組aarrsize的前 elenum 個單元中， 且遞增有序。 編寫算法， 將元素 x 插入到線性表的適當位置上，以保持線性表的有序性，并且分析算法的時間復雜度?！窘獯稹勘绢}是在一個遞增有序表中插入元

33、素x，基本思路是從有序表的尾部開始依次取元素與 x 比較，若大于 x，此元素后移一位，再取它前面一個元素重復上述步驟；否則，找到插入位置，將x插入。具體算法如下：9. 已知單鏈表中各結點的元素值為整型且遞增有序，設計算法刪除鏈表中所有大于mink 且小于 maxk的所有元素，并釋放被刪結點的存儲空間。【解答】因為是在有序單鏈表上的操作，所以，要充分利用其有序性。在單鏈表中查找第一個大于 mink的結點和第一個小于maxk的結點，再將二者間的所有結點刪除。10. 設單循環(huán)鏈表l1，對其遍歷的結果是： x1, x2, x3, xn-1, xn。請將該循環(huán)鏈表拆成兩個單循環(huán)鏈表l1 和 l2，使得

34、l1 中含有原 l1 表中序號為奇數(shù)的結點且遍歷結果為：x1, x3,； l2 中含有原 l1 表中序號為偶數(shù)的結點且遍歷結果為：, x4, x2?！窘獯稹克惴ㄈ缦拢旱?3章 特殊線性表棧、隊列和串課后習題講解1. 填空 設有一個空棧，棧頂指針為1000h，現(xiàn)有輸入序列為 1、2、3、4、5， 經(jīng)過 push ，push ， pop， push，pop， push， push 后，輸出序列是（），棧頂指針為（）?！窘獯稹?23， 1003h 棧通常采用的兩種存儲結構是（ ）；其判定?？盏臈l件分別是 （ ），判定棧滿的條件分別是 （ ）?！窘獯稹宽樞虼鎯Y構和鏈接存儲結構（或順序棧和鏈棧），棧頂

35、指針 top= -1 和 top=null，棧頂指針top 等于數(shù)組的長度和內(nèi)存無可用空間（ ）可作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結構。【解答】?！痉治觥窟f歸函數(shù)的調(diào)用和返回正好符合后進先出性。 表達式 a*(b+c)-d的后綴表達式是（）?！窘獯稹?abc+*d-【分析】將中綴表達式變?yōu)楹缶Y表達式有一個技巧：將操作數(shù)依次寫下來，再將算符插在它的兩個操作數(shù)的后面。 棧和隊列是兩種特殊的線性表，棧的操作特性是（），隊列的操作特性是（），棧和隊列的主要區(qū)別在于（ ）。【解答】后進先出，先進先出，對插入和刪除操作限定的位置不同 循環(huán)隊列的引入是為了克服（）?！窘獯稹考僖绯?數(shù)組 qn 用來表示一個循環(huán)

36、隊列，front為隊頭元素的前一個位置，rear為隊尾元素的位置，計算隊列中元素個數(shù)的公式為（）?！窘獯稹浚?rear-front+n） % n【分析】也可以是（ rear-front） % n，但 rear-front的結果可能是負整數(shù)，而對一個負整數(shù)求模，其結果在不同的編譯器環(huán)境下可能會有所不同。 用循環(huán)鏈表表示的隊列長度為n，若只設頭指針，則出隊和入隊的時間復雜度分別是（） 和 （ ）?！窘獯稹?(1) ， (n)【分析】在帶頭指針的循環(huán)鏈表中，出隊即是刪除開始結點，這只需修改相應指針；入隊即是在終端結點的后面插入一個結點，這需要從頭指針開始查找終端結點的地址。 串是一種特殊的線性表，其

37、特殊性體現(xiàn)在（）。【解答】數(shù)據(jù)元素的類型是一個字符 兩個串相等的充分必要條件是（）?！窘獯稹块L度相同且對應位置的字符相等【分析】例如 "abc" "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的初始狀態(tài)為空，元素e1、e2、e3、 e4、e5、e6 依次通過棧 s，一個元素出

38、棧后即進入隊列 q，若 6 個元素出隊的順序是e2、e4、e3、e6、e5、e1，則棧 s 的容量至少應該是 （ ）。a 6 b 4 c 3 d 2【解答】 c【分析】 由于隊列具有先進先出性，所以， 此題中隊列形同虛設， 即出棧的順序也是e2、e4、e3、e6、 e5、e1。 一個棧的入棧序列是1， 2， 3， 4， 5，則棧的不可能的輸出序列是（）。a 54321 b 45321 c 43512 d 12345【解答】 c【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號）的兩個元素。 設計一個判別表達式中左右括號是否配對的算法，采用（）數(shù)據(jù)結構

39、最佳a 順序表 b棧 c 隊列 d 鏈表【解答】 b【分析】每個右括號與它前面的最后一個沒有匹配的左括號配對，因此具有后進先出性。 在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印緩沖區(qū)，該緩沖區(qū)應該是一個（ ）結構。a 棧 b 隊列 c 數(shù)組 d 線性表【解答】 b【分析】先進入打印緩沖區(qū)的文件先被打印，因此具有先進先出性。 一個隊列的入隊順序是1， 2， 3， 4，則隊列的輸出順序是（）。a 4321 b 1234 c 1432 d 3241【解答】 b【分析】隊列的入隊順序和出隊順序總是一致的。 棧和隊列的主要區(qū)別在于（）。a 它們的邏輯結構不一樣b它們的存儲結構不一樣c 所

40、包含的運算不一樣d 插入、刪除運算的限定不一樣【解答】 d【分析】棧和隊列的邏輯結構都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結構在針對具體問題時包含的運算都可能不同。 設數(shù)組 sn 作為兩個棧 s1 和 s2 的存儲空間，對任何一個棧只有當sn 全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是（）。a s1 的棧底位置為0， s2 的棧底位置為n-1b s1 的棧底位置為0， s2 的棧底位置為n/2c s1 的棧底位置為0， s2 的棧底位置為nd s1 的棧底位置為0， s2 的棧底位置為1【解答】 a【分析】兩棧共享空間首先兩個棧是相向

41、增長的，棧底應該分別指向兩個棧中的第一個元素的位置，并注意 c+中的數(shù)組下標是從0 開始的。 設有兩個串 p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運算稱作（）。a 連接 b模式匹配 c求子串 d求串長【解答】 b3. 判斷題 有 n 個元素依次進棧，則出棧序列有(n-1)/2種?！窘獯稹垮e。應該有種。 棧可以作為實現(xiàn)過程調(diào)用的一種數(shù)據(jù)結構?！窘獯稹繉?。只要操作滿足后進先出性，都可以采用棧作為輔助數(shù)據(jù)結構。 在棧滿的情況下不能做進棧操作，否則將產(chǎn)生“上溢”?！窘獯稹繉Α?在循環(huán)隊列中， front指向隊頭元素的前一個位置，rear指向隊尾元素的位置， 則隊滿的條件是front=rear?！?/p>

42、解答】錯。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開。 空串與空格串是相同的?！窘獯稹垮e?？沾拈L度為零，而空格串的長度不為0，其長度是串中空格的個數(shù)。4. 設有一個棧，元素進棧的次序為a，b，c，d，e，能否得到如下出棧序列，若能，請寫出操作序列，若不能，請說明原因。 c ，e， a， b， d c ，b， a， d， e【解答】不能，因為在c、e 出棧的情況下， a 一定在棧中，而且在b 的下面，不可能先于b 出棧。可以，設為進棧操作，為入棧操作，則其操作序列為iiioooioio 。5. 舉例說明順序隊列的“假溢出”現(xiàn)象?！窘獯稹考僭O有一個順序隊列，如圖3-6 所示，

43、隊尾指針 rear=4 ，隊頭指針 front=1，如果再有元素入隊，就會產(chǎn)生“上溢” ，此時的“上溢”又稱為“假溢出”，因為隊列并不是真的溢出了，存儲隊列的數(shù)組中還有 2 個存儲單元空閑，其下標分別為0 和 1 。6. 在操作序列 push(1) 、push(2) 、pop、push(5) 、push(7) 、pop、push(6) 之后，棧頂元素和棧底元素分別是什么？（ push(k) 表示整數(shù) k 入棧， pop 表示棧頂元素出棧。 ）【解答】棧頂元素為6，棧底元素為1。其執(zhí)行過程如圖3-7 所示。7. 在操作序列 enqueue(1) 、 enqueue(3) 、 dequeue、en

44、queue(5) 、enqueue(7)、dequeue、enqueue(9)之后，隊頭元素和隊尾元素分別是什么？（enqueue(k) 表示整數(shù) k 入隊， dequeue表示隊頭元素出隊）?！窘獯稹筷狀^元素為5，隊尾元素為9。其執(zhí)行過程如圖3-8 所示。8. 空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個數(shù)。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟?。9. 算法設計 假設以不帶頭結點的循環(huán)鏈表表示隊列，

45、并且只設一個指針指向隊尾結點，但不設頭指針。試設計相應的入隊和出隊的算法?！窘獯稹砍鲫牪僮魇窃谘h(huán)鏈表的頭部進行，相當于刪除開始結點，而入隊操作是在循環(huán)鏈表的尾部進行，相當于在終端結點之后插入一個結點。由于循環(huán)鏈表不帶頭結點，需要處理空表的特殊情況。入隊算法如下：出隊算法如下： 設順序棧 s中有 2n 個元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-1 ，, ， a1，要求通過一個循環(huán)隊列重新排列棧中元素， 使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-2 ，, ， a2，a2n-1 ，a2n-3 ，, ，a1，請設計算法實現(xiàn)該操作，要求空間復雜度和時間復雜度均為o(n) ?！窘獯稹坎僮鞑襟E為：

46、 將所有元素出棧并入隊； 依次將隊列元素出隊，如果是偶數(shù)結點，則再入隊，如果是奇數(shù)結點，則入棧； 將奇數(shù)結點出棧并入隊； 將偶數(shù)結點出隊并入棧； 將所有元素出棧并入隊； 將所有元素出隊并入棧即為所求。 用順序存儲結構存儲串s，編寫算法刪除 s 中第 i個字符開始的連續(xù)j 個字符。【解答】先判斷串s 中要刪除的內(nèi)容是否存在，若存在，則將第i+j-1之后的字符前移 j 個位置。算法如下： 對于采用順序存儲結構的串s，編寫一個函數(shù)刪除其值等于ch 的所有字符。【解答】從后向前刪除值為ch 的所有元素，這樣所有移動的元素中沒有值為ch 的元素，能減少移動元素的次數(shù)，提高算法的效率。算法如下： 對串的模

47、式匹配 kmp算法設計求模式滑動位置的next函數(shù)?！窘獯稹繀⒁?3.2.5學習自測及答案1. 在一個具有 n 個單元的順序棧中，假定以地址低端（即下標為0 的單元）作為棧底，以top 作為棧頂指針，當出棧時， top 的變化為（ ）。a 不 變 b top=0; c top=top-1; d top=top+1;【解答】 c2. 一個棧的入棧序列是a, b, c, d, e，則棧的不可能的出棧序列是（）。a edcba b cdeba c debca d abcde【解答】 c3. 從棧頂指針為 top 的鏈棧中刪除一個結點，用x 保存被刪除結點的值，則執(zhí)行（）。a x=top; top=t

48、op->next; b x=top->data;c top=top->next; x=top->data; d x=top->data; top=top->next;【解答】 d4. 設元素 1, 2, 3, p, a依次經(jīng)過一個棧，進棧次序為123pa，在棧的輸出序列中，有哪些序列可作為 c+程序設計語言的變量名?！窘獯稹?pa321, p3a21, p32a1, p321a, ap3215. 設 s="i_ am_ a_ teacther"，其長度為（）?！窘獯稹?156. 對于棧和隊列， 無論它們采用順序存儲結構還是鏈接存儲結構，進

49、行插入和刪除操作的時間復雜度都是（ ） ?！窘獯稹?(1)7. 如果進棧序列為a、b、 c、d，則可能的出棧序列是什么？答：共 14 種，分別是： abcd， abdc， acbd， acdb，adcb， bacd， badc， bcad， bcda， bdca， cbad，cbda，cdba， dcba8. 簡述隊列和棧這兩種數(shù)據(jù)結構的相同點和不同點?！窘獯稹肯嗤c：它們都是插入和刪除操作的位置受限制的線性表。不同點：棧是限定僅在表尾進行插入和刪除的線性表，是后進先出的線性表，而隊列是限定在表的一端進行插入，在另一端進行刪除的線性表，是先進先出的線性表。9. 利用兩個棧 s1 和 s2 模擬

50、一個隊列， 如何利用棧的運算實現(xiàn)隊列的插入和刪除操作，請簡述算法思想?！窘獯稹?利用兩個棧 s1 和 s2 模擬一個隊列， 當需要向隊列中插入一個元素時，用 s1 來存放已輸入的元素，即通過向棧 s1 執(zhí)行入棧操作來實現(xiàn)；當需要從隊列中刪除元素時，則將s1 中元素全部送入到 s2 中，再從 s2 中刪除棧頂元素，最后再將s2 中元素全部送入到s1 中；判斷隊空的條件是：棧s1和 s2 同時為空。10. 設計算法把一個十進制整數(shù)轉(zhuǎn)換為二至九進制之間的任一進制數(shù)輸出。【解答】算法基于原理：n=(n div d)× d + n mod d（ div 為整除運算， mod為求余運算） 。11

51、. 假設一個算術表達式中可以包含三種括號：圓括號“（”和“）”，方括號“ ”和“ ”以及花括號“ ”和“ ”，且這三種括號可按任意的次序嵌套使用。編寫算法判斷給定表達式中所含括號是否配對出現(xiàn)?！窘獯稹考僭O表達式已存入字符數(shù)組an 中，具體算法如下：第 4章 廣義線性表多維數(shù)組和廣義表課后習題講解1. 填空 數(shù)組通常只有兩種運算： （ ）和（ ），這決定了數(shù)組通常采用（）結構來實現(xiàn)存儲。【解答】存取，修改，順序存儲【分析】數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。 二維數(shù)組 a中行下標從10 到 20

52、，列下標從 5 到 10，按行優(yōu)先存儲， 每個元素占 4 個存儲單元， a105的存儲地址是 1000，則元素 a1510的存儲地址是（）?！窘獯稹?1140【分析】 數(shù)組 a 中每行共有 6 個元素， 元素 a1510的前面共存儲了 (15-10)×6+5 個元素，每個元素占 4個存儲單元，所以，其存儲地址是1000+140=1140。 設有一個 10 階的對稱矩陣 a 采用壓縮存儲， a00為第一個元素，其存儲地址為d，每個元素占 1 個存儲單元，則元素a85的存儲地址為（）?！窘獯稹?d+41【分析】元素 a85的前面共存儲了 (1+2+ ,+8)+5=41 個元素。 稀疏矩陣一般壓縮存儲方法有兩種，分別是（）和（ ）?！窘獯稹咳M順序表，十字鏈表 廣義表 (a), (b),c),(d)的長度是（ ），深度是（ ），表頭是（ ），表尾是（）。【解答】 3， 4，(a) ， (b),c),(d) 已知廣義表 ls=(a ，(b ，c，d) ，e) ，用 head 和 tail函數(shù)取出 ls 中原子 b 的運算是 （ ）?！窘獯稹?head(head(tail(ls)2