《數(shù)據(jù)結(jié)構(gòu)習(xí)題集與實(shí)驗(yàn)指導(dǎo)》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)習(xí)題集與實(shí)驗(yàn)指導(dǎo)（177頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 目錄 基礎(chǔ)練習(xí)題及答案…………………………………………………………………1 第一章 緒論………………………………………………………………………1 第二章 線性表……………………………………………………………………3 第三章 棧和隊(duì)列…………………………………………………………………7 第四-五章 串和數(shù)組………………………………………………………………12 第六章 樹(shù)和二叉樹(shù)………………………………………………………………..16 第七章 圖…………………………………………………………………………..24 第八章 查找……………………………………………………………………

2、…..30 第九章 排序………………………………………………………………………..33 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)…………………………………………………………………34 實(shí)驗(yàn)一 線性表的應(yīng)用……………………………………………………………..34 實(shí)驗(yàn)二 棧和隊(duì)列的應(yīng)用…………………………………………………………..39 實(shí)驗(yàn)三 串的應(yīng)用…………………………………………………………………..47 實(shí)驗(yàn)四 數(shù)組………………………………………………………………………..48 實(shí)驗(yàn)五 二叉樹(shù)的應(yīng)用……………………………………………………………..51 實(shí)驗(yàn)六 圖的應(yīng)用……………………………………

3、……………………………..55 實(shí)驗(yàn)七 查找………………………………………………………………………..56 實(shí)驗(yàn)八 排序………………………………………………………………………..61 配套題集算法答案…………………………………………………………………64 第一章 緒論………………………………………………………………………..64 第二章 線性表……………………………………………………………………..67 第三章 棧與隊(duì)列…………………………………………………………………..79 第四章 串…………………………………………………………………………..89 第五章 數(shù)組和廣義表……

4、……………………………………………………….101 第六章 樹(shù)和二叉樹(shù)……………………………………………………………….114 第七章 圖………………………………………………………………………….133 第八章 動(dòng)態(tài)存儲(chǔ)管理…………………………………………………………….148 第九章 查找……………………………………………………………………….152 第十章 內(nèi)部排序………………………………………………………………….163 基礎(chǔ)練習(xí)題及答案 第一章 緒論 一、 填空題 1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的 操作對(duì)象 以及它們之間的 關(guān)

5、系 和運(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)系，樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。 6． 在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒(méi)有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒(méi)有 后續(xù)結(jié)點(diǎn)，

6、其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。 7. 在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有 前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有 后續(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．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序 、鏈?zhǔn)?、索引 和 散列 。 10. 數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。 11. 一個(gè)算法的效率可分為 時(shí)間 效率和 空間 效率。 12.任何一個(gè)C程序都由 一個(gè)主函數(shù)

7、 和若干個(gè)被調(diào)用的其它函數(shù)組成。 13. 變量一經(jīng)說(shuō)明，就確定該變量的取值范圍（即存儲(chǔ)單元）及 確定變量所允許的運(yùn)算 。 二、單項(xiàng)選擇題 （ C ）1. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)； A) 存儲(chǔ) B) 物理 C) 邏輯 D) 物理和存儲(chǔ) （ C ）2. 算法分析的目的是： A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 研究算法中的輸入和輸出的關(guān)系 C) 分析算法的效率以求改進(jìn) D) 分析算法的易懂性和文檔性 （ A ）3. 算法分析的兩個(gè)主要方面是： A) 空

8、間復(fù)雜性和時(shí)間復(fù)雜性 B) 正確性和簡(jiǎn)明性 C) 可讀性和文檔性 D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 （ C ）4. 計(jì)算機(jī)算法指的是： A) 計(jì)算方法 B) 排序方法 C) 解決問(wèn)題的有限運(yùn)算序列 D) 調(diào)度方法 （ B ）5. 計(jì)算機(jī)算法必須具備輸入、輸出和 等5個(gè)特性。 A) 可行性、可移植性和可擴(kuò)充性 B) 可行性、確定性和有窮性 C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安全性 三、簡(jiǎn)答題 1. 數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？ 答：簡(jiǎn)單地說(shuō)

9、，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。 2. 簡(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ì)多的。 四、閱讀下列C程序段，寫出相應(yīng)的執(zhí)行結(jié)果 2. long int fact(n) int n; {long f; if(n>1)f=n*fact(n-1); else f=1; return(f); } main() {int n; long y; n=5; y=fact(n); printf(“

10、%d,%ld\n”,n,y); } 答：運(yùn)行結(jié)果為： 5，120 1. printf(“Input x”); scanf(“%d”,&x); if (x<=30) if(x>20) y=x; else if (x>10) y=2*x; if (x>0&&x<30)printf(“x=%d,y=%d”,x,y); else printf(“輸入數(shù)據(jù)錯(cuò)！”); 試寫出當(dāng)x分別為18，8時(shí)的執(zhí)行結(jié)果。 答：運(yùn)行結(jié)果為：x=18，y=36 x=8，y=運(yùn)行前的值， 且從x＝30開(kāi)始為數(shù)據(jù)錯(cuò) 五、分析下面各程序段的時(shí)間復(fù)雜

11、度2. s=0; for i=0; i

12、 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)是開(kāi)始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn) 1. D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) } 答： d1→d2→d3→d4 d1—無(wú)直接前驅(qū)，是首結(jié)點(diǎn) d4—無(wú)直接后繼是尾結(jié)點(diǎn) 2. D={d1,d2,…,d9} R={(d1,d2),(d1,d3),(d3

13、,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) } 答： 此圖為樹(shù)形結(jié)構(gòu) d1—無(wú)直接前驅(qū)，是根結(jié)點(diǎn) d2,d5,d7,d9—無(wú)直接后繼是葉子結(jié)點(diǎn) 3. D={d1,d2,…,d9} R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)} 答： 此圖為圖形結(jié)構(gòu) d1，d2—無(wú)直接前驅(qū)，是開(kāi)始結(jié)點(diǎn) d6,d7—無(wú)直接后繼是終端結(jié)點(diǎn) 第二章 線性表 一、填空

14、1.在順序表中插入或刪除一個(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è)元素(1≤i≤n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng) n-i+1 個(gè)元素。 4. 向一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素(1≤i≤n)時(shí)，需向前移動(dòng) n-i 個(gè)元素。 5. 在順序表中訪問(wèn)任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 O(1) ，因此，順序表也稱為 隨機(jī)存取 的數(shù)據(jù)結(jié)構(gòu)。 6.順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相鄰的元

15、素的物理位置 不一定 相鄰。 7.在單鏈表中，除了首元結(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. 鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。錯(cuò)，鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無(wú)序，而鏈表的示意圖有序。 （ ）3. 鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)

16、刪除鏈中某個(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ò)，正好說(shuō)反了。順序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜” （ ）6. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。 錯(cuò)，前一半正確，但后一半說(shuō)法錯(cuò)誤，那是鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)。順序存儲(chǔ)方式插入、刪除運(yùn)算效率較低，在表長(zhǎng)

17、為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)，還可以用來(lái)存放非線性結(jié)構(gòu)，例如完全二叉樹(shù)是屬于非線性結(jié)構(gòu)，但其最佳存儲(chǔ)方式是順序存儲(chǔ)方式。（后一節(jié)介紹） （ ）

18、10. 線性表的邏輯順序與存儲(chǔ)順序總是一致的。 錯(cuò)，理由同7。鏈?zhǔn)酱鎯?chǔ)就無(wú)需一致。 三、單項(xiàng)選擇題 （ C ）1．?dāng)?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） 訪問(wèn)第

19、i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n） （B） 在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n） （C） 刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n） （D） 將n個(gè)結(jié)點(diǎn)從小到大排序 （ B ）4. 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(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

20、） 分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù) （ B ）6. 鏈表是一種采用 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表； （A）順序 （B）鏈?zhǔn)? （C）星式 （D）網(wǎng)狀 （ D ）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)行刪除插入 （Ｃ）Ｌ中含有大量的

21、結(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)稱為 P0 3 4 P0 a1 3 a2 4 A3 0 （Ａ）循環(huán)鏈表 （Ｂ）單鏈表 （Ｃ）雙向循環(huán)鏈表 （Ｄ）雙向鏈表 四、簡(jiǎn)答題 1.試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？ 答：① 順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也

22、相鄰（邏輯與物理統(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ǔ)密度?。?1），存儲(chǔ)空間利用率低。 順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。 若線性表的長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表； 若線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。 2 .描述以下三個(gè)概念的區(qū)別：頭指針、頭

23、結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？ 答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個(gè)概念對(duì)單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點(diǎn)，是不同的存儲(chǔ)結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問(wèn)題。 頭結(jié)點(diǎn)

24、 head data link 頭指針 首元結(jié)點(diǎn) 簡(jiǎn)而言之， 頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針； 頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息（內(nèi)放頭指針？那還得另配一個(gè)頭指針?。。。? 首元素結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。 五、線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五個(gè)元素的線性表L={23，17，47，05，31}，若它以鏈接方式存儲(chǔ)在下列100～119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占2個(gè)字節(jié)）和指針（占2個(gè)字節(jié)）組成

25、，如下所示： 05 U 17 X 23 V 31 Y 47 Z ^ ^ 100 120 其中指針X，Y，Z的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？ 答：X= 116 Y= 0 Z= 100 首址= 108 末址= 112 六、閱讀分析題 指出以下算法中的錯(cuò)誤和低效（即費(fèi)時(shí)）之處，并將它改寫為一個(gè)既正確又高效的算法。 Status DeleteK(SqList&a, int i

26、, int k){ //本過(guò)程從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素 if ( i<1 || k<0 || i+k> a.length ) return INFEASIBLE; //參數(shù)不合法 else{ for(count = 1; count =i+1; j--) a.elem[j-1] = a.elem[j]; a.length - -; } return OK; } // DeleteK

27、 注：上題涉及的類型定義如下： # define LIST INIT SIZE 100 # define LISTINCREMENT 10 typedef struct { Elem Type *elem; //存儲(chǔ)空間基址 Int length; //當(dāng)前長(zhǎng)度 Int listsize; //當(dāng)前分配的存儲(chǔ)容量 }SqList; 答：錯(cuò)誤有兩處： ① 參數(shù)不合法的判別條件不完整。例如表長(zhǎng)為10，若從第一位置（i=1）刪除10個(gè)元素（k=10）,要求合理但會(huì)被

28、判為非法。 合法的入口參數(shù)條件為（0 a.length ) return INFEASIBLE 改為：if (?。ǎ?=i+1; j--) a.elem[j-1] = a.elem[j]; 改為for (j>=i+1; j = a.length; j++) a.elem[j-1]

29、= a.elem[j]; 七、編程題 invsl(n,a) int n; ET a[]; {int k; ET t; for (k=1; k<=n/2; k++) {t=a[k-1]; a[k-1]=a[n-k]; a[n-k]=t;} return; } 1.寫出在順序存儲(chǔ)結(jié)構(gòu)下將線性表逆轉(zhuǎn)的算法，要求使用最少的附加空間。 解：輸入：長(zhǎng)度為n的線性表數(shù)組A(1:n) 輸出：逆轉(zhuǎn)后的長(zhǎng)度為n的線性表數(shù)組A(1:n)。 C語(yǔ)言描述如下（其中ET為數(shù)據(jù)元素的類型）： 2.已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，請(qǐng)寫出在P

30、結(jié)點(diǎn)后插入S結(jié)點(diǎn)的核心語(yǔ)句序列。 答：此題答案不唯一，但若從已給定序列中挑選，則限制頗多。 (7) Q=P; 已知P結(jié)點(diǎn)，則不必“順藤摸瓜”，直接鏈接即可。 (4) S->next=P->next; (1) P->next=S; (11) P=L; (8) while(P->next!=Q)P=P->next; (10) P=Q; (4) S->next=P->next; P->next=S; 3. 編寫程序，將若干整數(shù)從鍵盤輸入，以單鏈表形式存儲(chǔ)起來(lái)，然后計(jì)算單鏈表中結(jié)點(diǎn)的個(gè)數(shù)（其中指針P指向該鏈表的第一個(gè)結(jié)點(diǎn)）。 解：編寫C程序如下 全局變量及函數(shù)提前說(shuō)明：

31、 #include #include typedef struct liuyu{int data;struct liuyu*link;}test; liuyu *p,*q,*r,*head; int m=sizeof(test); void main () /*第一步，從鍵盤輸入整數(shù)，不斷添加到鏈表*/ {int i; head=(test*)malloc(m); /*m=sizeof(test);*/ p=head; i=0; while (i!=-9999) { printf("/ninput an int

32、eger [stop by -9999]:"); scanf("%d",&i); p->data=i; /* input data is saved */ p->link=(test*)malloc(m); /*m=sizeof(test));*/ q=p; p=p->link; } q->link=NULL; /*原先用p->link=NULL似乎太晚！*/ p=head; i=0; /*統(tǒng)計(jì)鏈表結(jié)點(diǎn)的個(gè)數(shù)并打印出來(lái)*/ while (p->link!=NULL) {printf(

33、"%d",p->data); p=p->link; i++;} printf("\n node number=%d\n", i-1); /*結(jié)點(diǎn)的個(gè)數(shù)不包括-9999*/ } 第三章 棧和隊(duì)列 一、填空題 1.向量、棧和隊(duì)列都是 線性 結(jié)構(gòu)，可以在向量的 任何 位置插入和刪除元素；對(duì)于棧只能在 棧頂 插入和刪除元素；對(duì)于隊(duì)列只能在 隊(duì)尾 插入和 隊(duì)首 刪除元素。 2. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 棧頂 。不允許插入和刪除運(yùn)算的一端稱為 棧底 。 3. 隊(duì)列 是被限定為只能在表

34、的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。 4. 在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的 前一個(gè) 位置。 5. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 n-1 個(gè)元素。 6. 向棧中壓入元素的操作是先 移動(dòng)棧頂指針 ，后 存入元素 。 7. 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是 先 移動(dòng)隊(duì)首指針 ，后 取出元素 。 8.帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于 0 。 L=head 頭結(jié)點(diǎn) R=head head 解： 二、 判斷正誤 （ ）1. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)

35、點(diǎn)可以是一個(gè)復(fù)雜類型。 錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無(wú)關(guān)。 （ ）2. 在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。 錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊(duì)列。 （ √ ）3. 棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。 （ √ ）4. 對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。 正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。 （ ）5. 棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。 錯(cuò)，棧是邏輯結(jié)構(gòu)

36、的概念，是特殊殊線性表，而鏈表是存儲(chǔ)結(jié)構(gòu)概念，二者不是同類項(xiàng)。 （ ）6. 棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。 錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。 （ √ ）7. 棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。 （ √ ）8. 兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。 （ ）9. 隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。 錯(cuò)，后半句

37、不對(duì)。 （ ）10. 一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。 錯(cuò)，有可能。 三、 單項(xiàng)選擇題 （ B ）1.棧中元素的進(jìn)出原則是 Ａ．先進(jìn)先出 Ｂ．后進(jìn)先出 Ｃ．?？談t進(jìn) Ｄ．棧滿則出 （ C ）2.若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不確定 解釋：當(dāng)p1=n，即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的（事實(shí)上題目已經(jīng)表明了），那么輸入順序必定是1

38、，2，3，…，n，則出棧的序列是n，…，3，2，1。 （若不要求順序出棧，則輸出序列不確定） （ B ）3.判定一個(gè)棧ST（最多元素為m0）為空的條件是 Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0 （ A ）4.判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是 Ａ．QU->rear － QU->front = = m0 Ｂ．QU->rear － QU->front －1= = m0 Ｃ．QU->front = = QU->rear Ｄ．QU->f

39、ront = = 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．?dāng)?shù)組Ｑ［ｎ］用來(lái)表示一個(gè)循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ?yàn)殛?duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素的公式為 （Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n 6. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，

40、把相應(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)都是空。 現(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è)。 供選擇的答案：

41、 A～D：①a1 ②a2 ③ a3 ④a4 E： ①1 ②2 ③ 3 ④ 0 答：ABCDE＝2, 4, 1, 2, 2 7.從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。 棧是一種線性表，它的特點(diǎn)是 A 。設(shè)用一維數(shù)組A[1,…,n]來(lái)表示一個(gè)棧，A[n]為棧底，用整型變量T指示當(dāng)前棧頂位置，A[T]為棧頂元素。往棧中推入（PUSH）一個(gè)新元素時(shí)，變量T的值 B ；從棧中彈出（POP）一個(gè)元素時(shí)，變量T的值 C 。設(shè)?？諘r(shí)，有輸入序列a，b，c，經(jīng)過(guò)PUSH，POP

42、，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。 供選擇的答案： A： ① 先進(jìn)先出 ②后進(jìn)先出 ③進(jìn)優(yōu)于出 ④出優(yōu)于進(jìn) ⑤ 隨機(jī)進(jìn)出 B，C： ① 加1 ②減1 ③不變 ④清0 ⑤ 加2 ⑥減2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥ a,c E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 答案：ABCDE=2, 2, 1, 6, 4 注意，向地址的高端生長(zhǎng)，稱為向上生成

43、堆棧；向地址低端生長(zhǎng)叫向下生成堆棧，本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。 8.從供選擇的答案中，選出應(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ā)生上溢，則說(shuō)明該棧的最大容量為 C 。 為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) E 時(shí)，才產(chǎn)生上溢。 供選擇的答案： A，B：①空 ② 滿

44、 ③ 上溢 ④ 下溢 C： ①n-1 ② n ③ n+1 ④ n/2 D： ① 長(zhǎng)度 ②深度 ③ 棧頂 ④ 棧底 E：①兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn) ②其中一個(gè)棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn) ③兩個(gè)棧的棧頂在達(dá)?？臻g的某一位置相遇 ④兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底 答案：ABCDE＝2, 1, 2, 4, 3 四、簡(jiǎn)答題 1.說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。 答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧

45、和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對(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.設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開(kāi)出車站的所有可能的順序。 答：至少有14種。 ① 全進(jìn)之后再出情況，只有1種：4，3，2，1 ② 進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,1 3,2,

46、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,3 3.假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’ 和‘a(chǎn)babab’則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？ 答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量（j--）從表尾開(kāi)始打印輸出； 堆棧是后進(jìn)先出，也

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

48、設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空； ② 浪費(fèi)一個(gè)元素的空間，用于區(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)%N 5.設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)從0到39），現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后，有 ① front=11，rear=19; ② front=19，rear=11；問(wèn)在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？ 答：用隊(duì)列長(zhǎng)度計(jì)算公式： (N＋r－f)% N ① L=（40＋19

49、－11）% 40=8 ② L=（40＋11－19）% 40=32 五、閱讀理解 按照四則運(yùn)算加、減、乘、除和冪運(yùn)算（↑）優(yōu)先關(guān)系的慣例，并仿照教材例3-2的格式，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程： A－BC/D+E↑F 1. 寫出下列程序段的輸出結(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

50、,’t’); Push(S,x); Pop(S,x); Push(S,’s’); while(!StackEmpty(S)){ Pop(S,y);printf(y); }; Printf(x); } 答：輸出為“stack”。 2. 寫出下列程序段的輸出結(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

51、(Q,x); DeQueue (Q,x); EnQueue (Q,’a’); while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; Printf(x); } 答：輸出為“char”。 3. 簡(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)

52、; EnQueue (Q,d); } } 六、試寫一個(gè)算法判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是“回文”。 答： int Palindrome_Test()//判別輸入的字符串是否回文序列,是則返回1,否則返回0 { InitStack(S);InitQueue(Q); while((c=getchar())!=@) { Push(S,c);EnQueue(Q,c); //同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu) } while(!StackEmpty(S)) { Pop(S,a);DeQueue(Q,b)}; if(a!=b) return ERROR; } r

53、eturn OK; }//Palindrome_Test 第四——五章 串和數(shù)組 一、填空題 1. 不包含任何字符（長(zhǎng)度為0）的串 稱為空串； 由一個(gè)或多個(gè)空格（僅由空格符）組成的串 稱為空白串。 2. 設(shè)S=“A;/document/Mary.doc”，則strlen(s)= 20 , “/”的字符定位的位置為 3 。 3. 子串的定位運(yùn)算稱為串的模式匹配； 被匹配的主串 稱為目標(biāo)串， 子串 稱為模式。 4. 設(shè)目標(biāo)T=”abccdcdccbaa”，模式P=“cdcc”，則第 6 次匹配成功。 5. 若n

54、為主串長(zhǎng)，m為子串長(zhǎng)，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數(shù)為 (n-m+1)*m 。 6. 假設(shè)有二維數(shù)組A68，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A的體積（存儲(chǔ)量）為 288 B ；末尾元素A57的第一個(gè)字節(jié)地址為 1282 ；若按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為 (8+4)6+1000=1072 ；若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為 (67＋4)6＋1000）＝1276 。 (注：數(shù)組是從0行0列還是從1行1列計(jì)算起呢？由末單元為A57可知，是從

55、0行0列開(kāi)始！) 7. 設(shè)數(shù)組a[1…60, 1…70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為 8950。 答：不考慮0行0列，利用列優(yōu)先公式： LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950 8. 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素 的 行下標(biāo) 、 列下標(biāo) 和 元素值 。 9.求

56、下列廣義表操作的結(jié)果： （1） GetHead【((a,b),(c,d))】=== (a, b) ; //頭元素不必加括號(hào) （2） GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ; （3） GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b ; （4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d） ; 二、單選題 （ B ）1. 串是一種特殊的線性表，其特殊性體現(xiàn)在： Ａ．可以順序存儲(chǔ)

57、 Ｂ．?dāng)?shù)據(jù)元素是一個(gè)字符 Ｃ．可以鏈?zhǔn)酱鎯?chǔ) Ｄ．?dāng)?shù)據(jù)元素可以是多個(gè)字符 （ B ）2. 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作： Ａ．連接 Ｂ．模式匹配 Ｃ．求子串 Ｄ．求串長(zhǎng) （ D ）3. 設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s, i, j)返回串s的從序號(hào)i開(kāi)始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的結(jié)果串是： Ａ．BCDE

58、F Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF 解：con(x,y)返回x和y串的連接串，即 con(x,y)＝‘ABCDEFGPQRST’； subs(s, i, j)返回串s的從序號(hào)i開(kāi)始的j個(gè)字符組成的子串，則 subs(s1, 2, len(s2))＝subs(s1, 2, 5)=’ BCDEF’; subs(s1, len(s2), 2)＝subs(s1, 5, 2)=’ EF’; 所以con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))＝con(’ BCDEF’, ’ EF’)之連接

59、，即BCDEFEF （ A ）4. 假設(shè)有60行70列的二維數(shù)組a[1…60, 1…70]以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a[32,58]的存儲(chǔ)地址為 。（無(wú)第0行第0列元素） Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C均不對(duì) 答：此題與填空題第8小題相似。（57列60行＋31行）2字節(jié)＋10000=16902 ( B )5. 設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分（如下圖所示）按行序存放在一維數(shù)組B[ 1, n(n-1)/2 ]中

60、，對(duì)下三角部分中任一元素ai,j(i≤j), 在一維數(shù)組B中下標(biāo)k的值是： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j 解：注意B的下標(biāo)要求從1開(kāi)始。 先用第一個(gè)元素去套用，可能有B和C； 再用第二個(gè)元素去套用B和C，B=2而C＝3（不符）； 所以選B 6. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。 有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是0到8，列下標(biāo)的范圍是1到5，每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址。假設(shè)存儲(chǔ)

61、數(shù)組元素A[0,1]的第一個(gè)字節(jié)的地址是0。 存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 A 。若按行存儲(chǔ)，則A[3,5]和A[5,3]的第一個(gè)字節(jié)的地址分別是 B 和 C 。若按列存儲(chǔ)，則A[7,1]和A[2,4]的第一個(gè)字節(jié)的地址分別是 D 和 E 。 供選擇的答案： A～E：①28 ② 44 ③ 76 ④ 92 ⑤ 108 ⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188 答案：ABCDE=8, 3, 5, 1, 6 7.有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用

62、相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是 A 個(gè)字節(jié)。假設(shè)存儲(chǔ)數(shù)組元素A[1,0]的第一個(gè)字節(jié)的地址是0，則存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 B 。若按行存儲(chǔ)，則A[2,4]的第一個(gè)字節(jié)的地址是 C 。若按列存儲(chǔ)，則A[5,7]的第一個(gè)字節(jié)的地址是 D 。 供選擇的答案 A～D：①12 ② 66 ③ 72 ④ 96 ⑤ 114 ⑥ 120 ⑦ 156 ⑧ 234 ⑨ 276 ⑩ 282 （11）283 （12）288 答案：ABCD=12, 10, 3, 9

63、三、簡(jiǎn)答題 1. KMP算法的設(shè)計(jì)思想是什么？它有什么優(yōu)點(diǎn)？ 答：其設(shè)計(jì)思想是，利用已經(jīng)部分匹配的結(jié)果來(lái)加快模式串的滑動(dòng)速度 。 主要優(yōu)點(diǎn)有二：一是在模式與主串已經(jīng)部分匹配的情況下，可以大大加快匹配速度；二是主串指針不回溯，可以使外設(shè)文件邊讀入邊匹配。 2. 已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個(gè)元素占K個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址為L(zhǎng)oc(a11)，請(qǐng)寫出求Loc(aij)的計(jì)算公式。如果采用列優(yōu)先順序存放呢？ 解：公式教材已給出，此處雖是方陣，但行列公式仍不相同； 按行存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11) +[ (i-1)*m+(j-

64、1) ] * K 按列存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11) +[ (j-1)*m+(i-1) ] * K 3.遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間，對(duì)嗎？為什么？ 答：不一定。時(shí)間復(fù)雜度與樣本個(gè)數(shù)n有關(guān)，是指最深層的執(zhí)行語(yǔ)句耗費(fèi)時(shí)間，而遞歸算法與非遞歸算法在最深層的語(yǔ)句執(zhí)行上是沒(méi)有區(qū)別的，循環(huán)的次數(shù)也沒(méi)有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來(lái)顯示循環(huán)次數(shù)而已。 四、計(jì)算題 1. 設(shè)s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’, 求Replace(s,’STUDENT’,q) 和

65、 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。 解：① Replace(s,’STUDENT’,q)＝’I AM A WORKER’ ② 因?yàn)? SubString(s,6,2)＝‘A ’；SubString(s,7,8)＝‘ STUDENT’ Concat(t,SubString(s,7,8))＝’GOOD STUDENT’ 所以Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))＝‘A GOOD STUDENT’ 2.已知主串s=’ADBADABBAABAD

66、ABBADADA’,模式串pat=’ADABBADADA’。寫出模式串的nextval函數(shù)值，并由此畫出KMP算法匹配的全過(guò)程。 解：（由演示程序得知）nextval函數(shù)值為0 1 0 2 1 0 1 0 4 0 在第12個(gè)字符處發(fā)現(xiàn)匹配！ s=’ADBADABBAABADABBADADA’ pat=’ADABBADADA’ 3.用三元組表表示下列稀疏矩陣： 解：參見(jiàn)填空題4. 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。 所以（1）可列表為： （2）可列表為： 8 8 6 6 4 1 6 -2 2 5 9 4 3 5 6 5 3 5 3 2 3 3 6 8 5 4 6 7 8 5 8 1 2 4. 下列各