數(shù)據(jù)結(jié)構(gòu)96269

1、第一章概論 自測(cè)題答案 一、填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 操作對(duì)象 以及它們之間的 關(guān)系 和運(yùn)算等的學(xué)科。2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是 數(shù)據(jù)元素 的有限集合，R是D上的 關(guān)系 有限集合。3. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 這三個(gè)方面的內(nèi)容。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。5. 線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。ABWGSAABWnrFvyPy6 在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)，其

2、余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。7. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè) 。8. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意多個(gè) 。9數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序 、 鏈?zhǔn)?、 索引 和 散列 。10. 數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。11. 一個(gè)算法的效率可分為 時(shí)間 效率和 空間 效率。二、單項(xiàng)選擇題（ B ）1. 非線性結(jié)構(gòu)是數(shù)據(jù)元素之

3、間存在一種：A）一對(duì)多關(guān)系 B）多對(duì)多關(guān)系 C）多對(duì)一關(guān)系 D）一對(duì)一關(guān)系（ C ）2. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)；A) 存儲(chǔ) B) 物理 C) 邏輯 D) 物理和存儲(chǔ)（ C ）3. 算法分析的目的是：A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改進(jìn) D) 分析算法的易懂性和文檔性（ A ）4. 算法分析的兩個(gè)主要方面是：A) 空間復(fù)雜性和時(shí)間復(fù)雜性 B) 正確性和簡(jiǎn)明性C) 可讀性和文檔性 D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（ C ）5. 計(jì)算機(jī)算法指的是：A) 計(jì)算方法 B) 排序方法 C) 解決問題的有限運(yùn)算序列 D) 調(diào)度方法

4、（ B ）6. 計(jì)算機(jī)算法必須具備輸入、輸出和 等5個(gè)特性。A) 可行性、可移植性和可擴(kuò)充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安全性三、簡(jiǎn)答題2.【嚴(yán)題集1.2】數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？答：簡(jiǎn)單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。3. 簡(jiǎn)述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對(duì)一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的。四、【嚴(yán)題集1.8】分析下面各程序段的時(shí)間復(fù)雜度2. s=0; for i=0; in;

5、i+)for(j=0; jn; j+) s+=Bij;sum=s;答：O（n2）1. for (i=0; in; i+)for (j=0; jm; j+)Aij=0;答：O（m*n）3. x=0;for(i=1; in; i+) for (j=1; j=n-i; j+)x+;解：因?yàn)閤+共執(zhí)行了n-1+n-2+1= n(n-1)/2，所以執(zhí)行時(shí)間為O（n2）4. i=1; while(i=n) i=i*3;答：O（log3n）五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=（D,R），試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系R，哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？ 1. 【嚴(yán)蔚敏習(xí)題集P7 1.

6、3】D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 答： d1d2d3d4 d1無直接前驅(qū)，是首結(jié)點(diǎn) d4無直接后繼是尾結(jié)點(diǎn)2。D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 答： 此圖為樹形結(jié)構(gòu) d1無直接前驅(qū)，是根結(jié)點(diǎn) d2,d5,d7,d9無直接后繼是葉子結(jié)點(diǎn)3D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7),

7、(d4,d6)答： 此圖為圖形結(jié)構(gòu) d1，d2無直接前驅(qū)，是開始結(jié)點(diǎn) d6,d7無直接后繼是終端結(jié)點(diǎn) (2) (3第2章 自測(cè)卷答案 一、填空1. 【嚴(yán)題集2.2】在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與 表長(zhǎng)和該元素在表中的位置 有關(guān)。2. 線性表中結(jié)點(diǎn)的集合是 有限 的，結(jié)點(diǎn)間的關(guān)系是 一對(duì)一 的。3. 向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素(1in+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng) n-i+1 個(gè)元素。4. 向一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素(1in)時(shí)，需向前移動(dòng) n-i 個(gè)元素。5. 在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 O(1) ，因此，順序

8、表也稱為 隨機(jī)存取 的數(shù)據(jù)結(jié)構(gòu)。6. 【嚴(yán)題集2.2】順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。7. 【嚴(yán)題集2.2】在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值 指示。8 在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為O（n）。二、判斷正誤（在正確的說法后面打勾，反之打叉）（ ）1. 鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。 答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分別存放多個(gè)指針。例如，雙向鏈表中的結(jié)點(diǎn)可以含有兩個(gè)指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。（ ）2. 鏈

9、表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。錯(cuò)，鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無序，而鏈表的示意圖有序。（ ）3. 鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。錯(cuò)，鏈表的結(jié)點(diǎn)不會(huì)移動(dòng)，只是指針內(nèi)容改變。（ ）4. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò)，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。（ ）5. 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。 錯(cuò)，正好說反了。順序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜”（ ）6. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。錯(cuò)，

10、前一半正確，但后一半說法錯(cuò)誤，那是鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)。順序存儲(chǔ)方式插入、刪除運(yùn)算效率較低，在表長(zhǎng)為n的順序表中，插入和刪除一個(gè)數(shù)據(jù)元素，平均需移動(dòng)表長(zhǎng)一半個(gè)數(shù)的數(shù)據(jù)元素。（ ）7. 線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。錯(cuò)，線性表有兩種存儲(chǔ)方式，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。后者不要求連續(xù)存放。（ ）8. 線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。錯(cuò)誤。線性表有兩種存儲(chǔ)方式，在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素在存儲(chǔ)的物理位置次序上也相鄰。（ ）9. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。錯(cuò)誤。順序存儲(chǔ)方式不僅能用于存儲(chǔ)線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二叉樹是屬于非線性結(jié)構(gòu)，但其

11、最佳存儲(chǔ)方式是順序存儲(chǔ)方式。（后一節(jié)介紹）（ ）10. 線性表的邏輯順序與存儲(chǔ)順序總是一致的。錯(cuò)，理由同7。鏈?zhǔn)酱鎯?chǔ)就無需一致。三、單項(xiàng)選擇題（ C ）1數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲(chǔ)結(jié)構(gòu) （B）邏輯結(jié)構(gòu) （C）順序存儲(chǔ)結(jié)構(gòu) （D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（ B ）2.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是 （A）110 （B）108 （C）100 （D）120（ A ）3. 在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（1）的操作是：（A） 訪問第i個(gè)結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2in） （B） 在第i

12、個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1in）（C） 刪除第i個(gè)結(jié)點(diǎn)（1in）（D） 將n個(gè)結(jié)點(diǎn)從小到大排序（ B ）4. 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng) 個(gè)元素（A）8 （B）63.5 （C）63 （D）7（ A ）5. 鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間：（A） 分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針（B） 只有一部分，存放結(jié)點(diǎn)值（C） 只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針（D） 分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)（ B ）6. 鏈表是一種采用 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表；（A）順序 （B）鏈?zhǔn)?（C）星式 （D）網(wǎng)狀（ D ）

13、7. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址:（A）必須是連續(xù)的 （B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的 （D）連續(xù)或不連續(xù)都可以（ B ）8 線性表在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。（）需經(jīng)常修改中的結(jié)點(diǎn)值 （）需不斷對(duì)進(jìn)行刪除插入 （）中含有大量的結(jié)點(diǎn) （）中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜（ C ）9 單鏈表的存儲(chǔ)密度（）大于1； （）等于1； （）小于1； （）不能確定（ B ）10 設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn)，整數(shù)P0，3，4代表地址，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為P034P0a13a24A30（）循環(huán)鏈表 （）單鏈表 （）雙向循環(huán)鏈表 （）雙向鏈表四、簡(jiǎn)答題1. 【嚴(yán)題集2.3】

14、試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？答： 順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)密度大（1？），存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度?。╰op0 ST-top=0 ST-topm0 ST-top=m0（ A ）4. 李春葆判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是 QU-rear QU-front = =

15、 m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1解：隊(duì)滿條件是元素個(gè)數(shù)為m0。由于約定滿隊(duì)時(shí)隊(duì)首指針與隊(duì)尾指針相差1，所以不必再減1了，應(yīng)當(dāng)選A。當(dāng)然，更正確的答案應(yīng)該取模，即：QU-front = = (QU-rear+1)% m0（ D ）5數(shù)組用來表示一個(gè)循環(huán)隊(duì)列，為當(dāng)前隊(duì)列頭元素的前一位置，為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于，計(jì)算隊(duì)列中元素的公式為（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n6. 【98初程P71】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？

16、內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。設(shè)有4個(gè)數(shù)據(jù)元素a1、a2、a3和a4，對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按a1、a2、a3、a4次序每次進(jìn)入一個(gè)元素。假設(shè)?；蜿?duì)的初始狀態(tài)都是空?，F(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是 A ，第二次出棧得到的元素是 B 是；類似地，考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是 C ，第二次出隊(duì)得到的元素是 D 。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有 E 個(gè)。供選擇的答案：AD：a1 a2 a3 a4E： 1 2 3 0答

17、：ABCDE2, 4, 1, 2, 27. 【94初程P75】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。棧是一種線性表，它的特點(diǎn)是 A 。設(shè)用一維數(shù)組A1,n來表示一個(gè)棧，An為棧底，用整型變量T指示當(dāng)前棧頂位置，AT為棧頂元素。往棧中推入（PUSH）一個(gè)新元素時(shí)，變量T的值 B ；從棧中彈出（POP）一個(gè)元素時(shí)，變量T的值 C 。設(shè)棧空時(shí)，有輸入序列a，b，c，經(jīng)過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。供選擇的答案：A： 先進(jìn)先出 后進(jìn)先出 進(jìn)優(yōu)于出 出優(yōu)于進(jìn) 隨機(jī)進(jìn)出B，C：

18、 加1 減1 不變 清0 加2 減2D： a,b b,c c,ab,a c,b a,cE： n+1 n+2 n n-1 n-2答案：ABCDE=2, 2, 1, 6, 4注意，向地址的高端生長(zhǎng)，稱為向上生成堆棧；向地址低端生長(zhǎng)叫向下生成堆棧，本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。8. 【91初程P77】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否 A ；在做退棧運(yùn)算時(shí)，應(yīng)先判別棧是否 B 。當(dāng)棧中元素為n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明該棧的最大容量為 C 。為了增加內(nèi)存空間的利用率和減少溢出的可能

19、性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) E 時(shí)，才產(chǎn)生上溢。供選擇的答案：A，B：空 滿 上溢 下溢C： n-1 n n+1 n/2D： 長(zhǎng)度 深度 棧頂 棧底E：兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn) 其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn) 兩個(gè)棧的棧頂在達(dá)?？臻g的某一位置相遇 兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答案：ABCDE2, 1, 2, 4, 3四、簡(jiǎn)答題（每小題4分，共20分）1. 【嚴(yán)題集3.2和3.11】說明線性表、棧與隊(duì)的異同點(diǎn)。劉答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩

20、種特殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。 用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。2. 【統(tǒng)考書P60 4-11，難于嚴(yán)題集3.1】設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。 全進(jìn)之后再出情況，只有1種：4，3，2，1 進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,1 3,

21、2,4,1 3,2,1,4 進(jìn)2個(gè)之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 進(jìn)1個(gè)之后再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,33. 【劉自編】假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，abba和abcba是回文，abcde 和ababab則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量（j-）從表尾開始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先

22、出，不易實(shí)現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機(jī)內(nèi)已是順序存儲(chǔ)，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動(dòng)作實(shí)現(xiàn)。（但堆棧是先減后壓還是）若正文是單鏈表形式存儲(chǔ)，則等同于隊(duì)列，需開輔助空間，可以從鏈?zhǔn)组_始入棧，全部壓入后再依次輸出。4. 【統(tǒng)考書P60 4-13】順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決隊(duì)滿隊(duì)空的辦法有三： 設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空； 浪費(fèi)一個(gè)元素的空間，

23、用于區(qū)別隊(duì)滿還是隊(duì)空。 使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）。我們常采用法，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲兀硪粋€(gè)指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是： f=rear 隊(duì)滿標(biāo)志是：f=(r+1)%N5. 【統(tǒng)考書P60 4-14】設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)從0到39），現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)運(yùn)算后，有 front=11，rear=19; front=19，rear=11；問在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？答：用隊(duì)列長(zhǎng)度計(jì)算公式： (Nrf)% N L=（401911）% 40=8 L=（401119）% 40=32五、閱讀理解（每小題5分，共20分。至少要寫出

24、思路）1. 【嚴(yán)題集3.7】按照四則運(yùn)算加、減、乘、除和冪運(yùn)算（）優(yōu)先關(guān)系的慣例，并仿照教材例3-2的格式，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程：ABC/D+EF答：2. 【嚴(yán)題集3.3】寫出下列程序段的輸出結(jié)果（棧的元素類型SElem Type為char）。void main( )Stack S;Char x,y;InitStack(S);X=c;y=k;Push(S,x); Push(S,a); Push(S,y);Pop(S,x); Push(S,t); Push(S,x);Pop(S,x); Push(S,s);while(!StackEmpty(S) Pop(S,y

25、);printf(y); ;Printf(x);答：輸出為“stack”。3. 【嚴(yán)題集3.12】寫出下列程序段的輸出結(jié)果（隊(duì)列中的元素類型QElem Type為char）。void main( )Queue Q; Init Queue (Q);Char x=e; y=c;EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q, y);DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x);答

26、：輸出為“char”。4. 【嚴(yán)題集3.13】簡(jiǎn)述以下算法的功能（棧和隊(duì)列的元素類型均為int）。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 答：該算法的功能是：利用堆棧做輔助，將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置。六、算法設(shè)計(jì)（每小題5分，共15分。至少要寫出思路）1. 【李春葆及嚴(yán)題集3.19】假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧，編寫一個(gè)判別

27、表達(dá)式中括弧是否正確配對(duì)的函數(shù)correct(exp,tag)；其中：exp為字符串類型的變量（可理解為每個(gè)字符占用一個(gè)數(shù)組元素），表示被判別的表達(dá)式，tag為布爾型變量。答：用堆棧st進(jìn)行判定，將 ( 、 或 入棧，當(dāng)遇到 、 或 ) 時(shí)，檢查當(dāng)前棧頂元素是否是對(duì)應(yīng)的( 、 或 ，若是則退棧，否則返回表示不配對(duì)。當(dāng)整個(gè)算術(shù)表達(dá)式檢查完畢時(shí)，若棧為空表示括號(hào)正確配對(duì)，否則不配對(duì)。編程后的整個(gè)函數(shù)如下（李書P3132）#define m0 100 /*m0為算術(shù)表達(dá)式中最多字符個(gè)數(shù)*/correct(exp,tag)char expm0;int tag;char stm0;int top=0,

28、i=1;tag=1;while (i0)tag=0; /*若棧不空，則不配對(duì)*/嚴(yán)題集對(duì)應(yīng)答案：3.19 Status AllBrackets_Test(char *str)/判別表達(dá)式中三種括號(hào)是否匹配 InitStack(s); for(p=str;*p;p+) if(*p=(|*p=|*p=) push(s,*p); else if(*p=)|*p=|*p=) if(StackEmpty(s) return ERROR; pop(s,c); if(*p=)&c!=() return ERROR; if(*p=&c!=) return ERROR; if(*p=&c!=) return E

29、RROR; /必須與當(dāng)前棧頂括號(hào)匹配 /for if(!StackEmpty(s) return ERROR; return OK; /AllBrackets_Test 2001級(jí)通信6班張沐同學(xué)答案（已上機(jī)通過）#include#includevoid push(char x);void pop();void correct(enum Boolean &tag);/原來的定義是void correct(struct Stack* head,enum Boolean &tag);typedef struct Stackchar data;struct Stack *next;struct St

30、ack *head,*p;enum BooleanFALSE,TRUEtag;void main()head=(struct Stack*)malloc(sizeof(struct Stack);head-data=S;head-next=NULL;/ heads data has not been initialized! correct(tag);if(tag)printf(Right!);elseprintf(Wrong!);void push(char x)p=(struct Stack*)malloc(sizeof(struct Stack);if(!p)printf(Theres no space.n);elsep-data=x;p-next=head;head=p;/ if you define the Correct function like that/Debug will show that the Push action doesnt take effectionvoid pop()if(head-next=NULL)printf(The stack is empty.n);else