數(shù)據(jù)結(jié)構(gòu)習題集與實驗指導

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

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

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

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

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

5、系 和運算等的學科。 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ù)的 存儲結(jié)構(gòu) 和數(shù)據(jù)的 運算 這三個方面的內(nèi)容。 4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。 5. 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。 6． 在線性結(jié)構(gòu)中，第一個結(jié)點 沒有 前驅(qū)結(jié)點，其余每個結(jié)點有且只有 1個前驅(qū)結(jié)點；最后一個結(jié)點 沒有 后續(xù)結(jié)點，

6、其余每個結(jié)點有且只有1個后續(xù)結(jié)點。 7. 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 前驅(qū) 結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；葉子結(jié)點沒有 后續(xù) 結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個 。 8. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以 任意多個 。 9．數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序 、鏈式 、索引 和 散列 。 10. 數(shù)據(jù)的運算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。 11. 一個算法的效率可分為 時間 效率和 空間 效率。 12.任何一個C程序都由 一個主函數(shù)

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

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

9、，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。 2. 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點。 答：線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 一對一的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是多對多的。 四、閱讀下列C程序段，寫出相應的執(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); } 答：運行結(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ù)錯！”); 試寫出當x分別為18，8時的執(zhí)行結(jié)果。 答：運行結(jié)果為：x=18，y=36 x=8，y=運行前的值， 且從x＝30開始為數(shù)據(jù)錯 五、分析下面各程序段的時間復雜

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

12、 i=1; while(i<=n) i=i*3; 答：O（log3n） 六、設有數(shù)據(jù)邏輯結(jié)構(gòu)S=（D,R），試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系R，哪些結(jié)點是開始結(jié)點，哪些結(jié)點是終端結(jié)點 1. D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) } 答： d1→d2→d3→d4 d1—無直接前驅(qū)，是首結(jié)點 d4—無直接后繼是尾結(jié)點 2. D={d1,d2,…,d9} R={(d1,d2),(d1,d3),(d3

13、,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) } 答： 此圖為樹形結(jié)構(gòu) d1—無直接前驅(qū)，是根結(jié)點 d2,d5,d7,d9—無直接后繼是葉子結(jié)點 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—無直接前驅(qū)，是開始結(jié)點 d6,d7—無直接后繼是終端結(jié)點 第二章 線性表 一、填空

14、1.在順序表中插入或刪除一個元素，需要平均移動 表中一半 元素，具體移動的元素個數(shù)與 表長和該元素在表中的位置 有關(guān)。 2. 線性表中結(jié)點的集合是 有限 的，結(jié)點間的關(guān)系是 一對一 的。 3. 向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動 n-i+1 個元素。 4. 向一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動 n-i 個元素。 5. 在順序表中訪問任意一結(jié)點的時間復雜度均為 O(1) ，因此，順序表也稱為 隨機存取 的數(shù)據(jù)結(jié)構(gòu)。 6.順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相鄰的元

15、素的物理位置 不一定 相鄰。 7.在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由 其直接前驅(qū)結(jié)點的鏈域的值 指示。 8． 在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的前驅(qū)結(jié)點的地址，其時間復雜度為O（n）。 二、判斷正誤 （ ）1. 鏈表的每個結(jié)點中都恰好包含一個指針。 答：錯誤。鏈表中的結(jié)點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結(jié)點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結(jié)點的指針。 （ ）2. 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。錯，鏈表的存儲結(jié)構(gòu)特點是無序，而鏈表的示意圖有序。 （ ）3. 鏈表的刪除算法很簡單，因為當

16、刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。錯，鏈表的結(jié)點不會移動，只是指針內(nèi)容改變。 （ ）4. 線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復雜類型。 錯，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。 （ ）5. 順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。 錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜” （ ）6. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。 錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優(yōu)點。順序存儲方式插入、刪除運算效率較低，在表長

17、為n的順序表中，插入和刪除一個數(shù)據(jù)元素，平均需移動表長一半個數(shù)的數(shù)據(jù)元素。 （ ）7. 線性表在物理存儲空間中也一定是連續(xù)的。 錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。后者不要求連續(xù)存放。 （ ）8. 線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。 錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。 （ ）9. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。 錯誤。順序存儲方式不僅能用于存儲線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二叉樹是屬于非線性結(jié)構(gòu)，但其最佳存儲方式是順序存儲方式。（后一節(jié)介紹） （ ）

18、10. 線性表的邏輯順序與存儲順序總是一致的。 錯，理由同7。鏈式存儲就無需一致。 三、單項選擇題 （ C ）1．數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為： （A）存儲結(jié)構(gòu) （B）邏輯結(jié)構(gòu) （C）順序存儲結(jié)構(gòu) （D）鏈式存儲結(jié)構(gòu) （ B ）2.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是 （A）110 （B）108 （C）100 （D）120 （ A ）3. 在n個結(jié)點的順序表中，算法的時間復雜度是O（1）的操作是： （A） 訪問第

19、i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n） （B） 在第i個結(jié)點后插入一個新結(jié)點（1≤i≤n） （C） 刪除第i個結(jié)點（1≤i≤n） （D） 將n個結(jié)點從小到大排序 （ B ）4. 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 個元素 （A）8 （B）63.5 （C）63 （D）7 （ A ）5. 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間： （A） 分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針 （B） 只有一部分，存放結(jié)點值 （C） 只有一部分，存儲表示結(jié)點間關(guān)系的指針 （D

20、） 分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù) （ B ）6. 鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表； （A）順序 （B）鏈式 （C）星式 （D）網(wǎng)狀 （ D ）7. 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址: （A）必須是連續(xù)的 （B）部分地址必須是連續(xù)的 （C）一定是不連續(xù)的 （D）連續(xù)或不連續(xù)都可以 （ B ）8． 線性表Ｌ在 情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。 （Ａ）需經(jīng)常修改Ｌ中的結(jié)點值 （Ｂ）需不斷對Ｌ進行刪除插入 （Ｃ）Ｌ中含有大量的

21、結(jié)點 （Ｄ）Ｌ中結(jié)點結(jié)構(gòu)復雜 （ C ）9． 單鏈表的存儲密度 （Ａ）大于1； （Ｂ）等于1； （Ｃ）小于1； （Ｄ）不能確定 （ B ）10． 設a1、a2、a3為3個結(jié)點，整數(shù)P0，3，4代表地址，則如下的鏈式存儲結(jié)構(gòu)稱為 P0 3 4 P0 a1 3 a2 4 A3 0 （Ａ）循環(huán)鏈表 （Ｂ）單鏈表 （Ｃ）雙向循環(huán)鏈表 （Ｄ）雙向鏈表 四、簡答題 1.試比較順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好？ 答：① 順序存儲時，相鄰數(shù)據(jù)元素的存放地址也

22、相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。 優(yōu)點：存儲密度大（＝1？），存儲空間利用率高。缺點：插入或刪除元素時不方便。 ②鏈式存儲時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針 優(yōu)點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度小（<1），存儲空間利用率低。 順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。 若線性表的長度變化不大，且其主要操作是查找，則采用順序表； 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。 2 .描述以下三個概念的區(qū)別：頭指針、頭

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

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

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

26、, int k){ //本過程從順序存儲結(jié)構(gòu)的線性表a中刪除第i個元素起的k個元素 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; //存儲空間基址 Int length; //當前長度 Int listsize; //當前分配的存儲容量 }SqList; 答：錯誤有兩處： ① 參數(shù)不合法的判別條件不完整。例如表長為10，若從第一位置（i=1）刪除10個元素（k=10）,要求合理但會被

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.寫出在順序存儲結(jié)構(gòu)下將線性表逆轉(zhuǎn)的算法，要求使用最少的附加空間。 解：輸入：長度為n的線性表數(shù)組A(1:n) 輸出：逆轉(zhuǎn)后的長度為n的線性表數(shù)組A(1:n)。 C語言描述如下（其中ET為數(shù)據(jù)元素的類型）： 2.已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，請寫出在P

30、結(jié)點后插入S結(jié)點的核心語句序列。 答：此題答案不唯一，但若從已給定序列中挑選，則限制頗多。 (7) Q=P; 已知P結(jié)點，則不必“順藤摸瓜”，直接鏈接即可。 (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ù)從鍵盤輸入，以單鏈表形式存儲起來，然后計算單鏈表中結(jié)點的個數(shù)（其中指針P指向該鏈表的第一個結(jié)點）。 解：編寫C程序如下 全局變量及函數(shù)提前說明：

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)計鏈表結(jié)點的個數(shù)并打印出來*/ while (p->link!=NULL) {printf(

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

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

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

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

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

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

39、ront = = QU->rear+1 解：隊滿條件是元素個數(shù)為m0。由于約定滿隊時隊首指針與隊尾指針相差1，所以不必再減1了，應當選A。當然，更正確的答案應該取模，即：QU->front = = (QU->rear+1)% m0 （ D ）5．數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素的公式為 （Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n 6. 從供選擇的答案中，選出應填入下面敘述 ？ 內(nèi)的最確切的解答，

40、把相應編號寫在答卷的對應欄內(nèi)。 設有4個數(shù)據(jù)元素a1、a2、a3和a4，對他們分別進行棧操作或隊操作。在進棧或進隊操作時，按a1、a2、a3、a4次序每次進入一個元素。假設?；蜿牭某跏紶顟B(tài)都是空。 現(xiàn)要進行的棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是 A ，第二次出棧得到的元素是 B 是；類似地，考慮對這四個數(shù)據(jù)元素進行的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是 C ，第二次出隊得到的元素是 D 。經(jīng)操作后，最后在棧中或隊中的元素還有 E 個。 供選擇的答案：

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

42、，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。 供選擇的答案： A： ① 先進先出 ②后進先出 ③進優(yōu)于出 ④出優(yōu)于進 ⑤ 隨機進出 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 注意，向地址的高端生長，稱為向上生成

43、堆棧；向地址低端生長叫向下生成堆棧，本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。 8.從供選擇的答案中，選出應填入下面敘述 ？ 內(nèi)的最確切的解答，把相應編號寫在答卷的對應欄內(nèi)。 在做進棧運算時，應先判別棧是否 A ；在做退棧運算時，應先判別棧是否 B 。當棧中元素為n個，做進棧運算時發(fā)生上溢，則說明該棧的最大容量為 C 。 為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應將兩棧的 D 分別設在這片內(nèi)存空間的兩端，這樣，只有當 E 時，才產(chǎn)生上溢。 供選擇的答案： A，B：①空 ② 滿

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

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

46、4,1 3,2,1,4 ③ 進2個之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 ④ 進1個之后再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3 3.假設正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’ 和‘a(chǎn)babab’則不是回文。假設一字符序列已存入計算機，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？ 答：線性表是隨機存儲，可以實現(xiàn)，靠循環(huán)變量（j--）從表尾開始打印輸出； 堆棧是后進先出，也

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

48、設置一個布爾變量以區(qū)別隊滿還是隊空； ② 浪費一個元素的空間，用于區(qū)別隊滿還是隊空。 ③ 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。 我們常采用法②，即隊頭指針、隊尾指針中有一個指向?qū)嵲?，而另一個指向空閑元素。 判斷循環(huán)隊列隊空標志是： f=rear 隊滿標志是：f=(r+1)%N 5.設循環(huán)隊列的容量為40（序號從0到39），現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有 ① front=11，rear=19; ② front=19，rear=11；問在這兩種情況下，循環(huán)隊列中各有元素多少個？ 答：用隊列長度計算公式： (N＋r－f)% N ① L=（40＋19

49、－11）% 40=8 ② L=（40＋11－19）% 40=32 五、閱讀理解 按照四則運算加、減、乘、除和冪運算（↑）優(yōu)先關(guān)系的慣例，并仿照教材例3-2的格式，畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程： 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é)果（隊列中的元素類型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. 簡述以下算法的功能（棧和隊列的元素類型均為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); } } 六、試寫一個算法判別讀入的一個以‘@’為結(jié)束符的字符序列是否是“回文”。 答： int Palindrome_Test()//判別輸入的字符串是否回文序列,是則返回1,否則返回0 { InitStack(S);InitQueue(Q); while((c=getchar())!=@) { Push(S,c);EnQueue(Q,c); //同時使用棧和隊列兩種結(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. 不包含任何字符（長度為0）的串 稱為空串； 由一個或多個空格（僅由空格符）組成的串 稱為空白串。 2. 設S=“A;/document/Mary.doc”，則strlen(s)= 20 , “/”的字符定位的位置為 3 。 3. 子串的定位運算稱為串的模式匹配； 被匹配的主串 稱為目標串， 子串 稱為模式。 4. 設目標T=”abccdcdccbaa”，模式P=“cdcc”，則第 6 次匹配成功。 5. 若n

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

55、0行0列開始！) 7. 設數(shù)組a[1…60, 1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為 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. 三元素組表中的每個結(jié)點對應于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素 的 行下標 、 列下標 和 元素值 。 9.求

56、下列廣義表操作的結(jié)果： （1） GetHead【((a,b),(c,d))】=== (a, b) ; //頭元素不必加括號 （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)在： Ａ．可以順序存儲

57、 Ｂ．數(shù)據(jù)元素是一個字符 Ｃ．可以鏈式存儲 Ｄ．數(shù)據(jù)元素可以是多個字符 （ B ）2. 設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作： Ａ．連接 Ｂ．模式匹配 Ｃ．求子串 Ｄ．求串長 （ D ）3. 設串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s, i, j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，則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的從序號i開始的j個字符組成的子串，則 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. 假設有60行70列的二維數(shù)組a[1…60, 1…70]以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為 。（無第0行第0列元素） Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C均不對 答：此題與填空題第8小題相似。（57列60行＋31行）2字節(jié)＋10000=16902 ( B )5. 設矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分（如下圖所示）按行序存放在一維數(shù)組B[ 1, n(n-1)/2 ]中

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

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

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

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

64、1) ] * K 按列存儲的元素地址公式是： Loc(aij)= Loc(a11) +[ (j-1)*m+(i-1) ] * K 3.遞歸算法比非遞歸算法花費更多的時間，對嗎？為什么？ 答：不一定。時間復雜度與樣本個數(shù)n有關(guān)，是指最深層的執(zhí)行語句耗費時間，而遞歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數(shù)也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來顯示循環(huán)次數(shù)而已。 四、計算題 1. 設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’ ② 因為 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算法匹配的全過程。 解：（由演示程序得知）nextval函數(shù)值為0 1 0 2 1 0 1 0 4 0 在第12個字符處發(fā)現(xiàn)匹配！ s=’ADBADABBAABADABBADADA’ pat=’ADABBADADA’ 3.用三元組表表示下列稀疏矩陣： 解：參見填空題4. 三元素組表中的每個結(jié)點對應于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的 行下標 、 列下標 和 元素值 。 所以（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. 下列各