1、數據結構習題答案習題 第 1 章解答 一、選擇題 15：dabbc 610：dccbc 二、填空題 1、數據元素，關系 2、邏輯結構，存儲結構，運算 3、線性結構，非線性結構 4、一對一，一對多 5、前驅，1，后續，1 6、前驅，1，后續，任意多個 7、任意多個 8、順序、鏈式、索引、散列 9、插入、刪除、修改、查找、排序 10、時間，效率 三、綜合題 1、答：(1)是線性結構，(2)是樹形結構，(3)圖結構。 2、答：(a)是線性結構，(b)是樹形結構，(c)是有向圖。 3、答：(a)o(mn)，(b)o(n 2 )， (c)o(log 2 n) 4、答：(1) 優點：根據 exit 報告值

2、，可以知道錯誤發生處。 缺點：每運行一次程序，至多能發現一個錯誤。 (2) 優點：利用函數返回值來提供錯誤發生情況，可以根據嚴重程度作相應的處理。 缺點：增加編程難度。 (3) 優點：利用函數參數來提供錯誤發生情況，可以根據嚴重程度作相應的處理。 缺點：增加編程難度并增加函數的參數資源。 5、答：(1) 優點：直接與外設建立聯系，可以減少存儲空間。 缺點：由于輸入輸出需要時間，程序運行效率下降。 (2) 優點：傳遞速度快。 缺點：增加存放數據的空間，增加棧的操作量。 (3) 優點：傳遞速度快。 缺點：增加存放數據的空間，影響局部化。 第 2 章解答 一、選擇題 15：cadca 610：acc

3、ad 二、填空題 1、l-prior=l-next=l 2、head-next=null 3、q-next 4、o(n) 5、100 6、n-i+1 7、n-i 8、head-next=null 9、q-next=s;s-next=p; 10、p-next=p-next-next; 三、判斷題 15：opooo 610：ooppp 第 3 章解答 一、選擇題 15：ccdba 610：abccc 1115：ddaad 二、填空題 1、3 2、(rear-front+m)%m 3、n-1 4、61 5、15 6、線性，任何，棧頂，隊尾，隊首 7、棧頂，棧底 8、隊列 9、移動棧頂指針 10、移動

4、隊首指針 三、判斷題 15： popop 610：oppoo 四、綜合題 1：（1）123，132，213，231，321 （2）不能產生 435612，可以產生 135426 因為 s1s2s3s4x4x3s5x5s6x6x2x1，只能產生 435621 s1x1s2s3x3s4s5x5x4x2s6x6，可以產生 135426 2：若進棧序列為a，b，c，d，全部可能的出棧序列是： abcd，abdc，acbd，acdb，adcb，bacd，badc，bcad，bcda， bdca，cbad，cbda，cdba，dcba。 不可能的：adbc，bdac，cdab，cadb，cadb，dabc

5、，dacb，dbac，dbca，dcab。 3：由于隊列中操作遵循的原則是先進先出，出隊元素的順序是 bdcfea，故元素進隊的順序也是 bdcfea，元素進隊的順序與元素出棧的順序相同，在棧中存取數據遵循的原則是后進先出，要得到出棧序列 bdcfea，棧的容量至少是應該存放 3 個元素的空間。 4：3 4 25 6 15+-/8*+ 5： abc+*d- 第 4 章解答 一、選擇題 15：cacab 610：abbbd 二、填空題 1、模式匹配 2、14 3、對應位置字符相同 4、不包含任何字符（長度為 0）的串；由一個或多個空格（僅由空格符）組成的串 5、20，3 6、被匹配的主串，子串

6、7、6 8、(n-m+1)*m 9、兩個串的長度相等且對應位置上的字符相同 10、'goodmorning'， 'nin'，4，'goto' 三、應用題 1：t=concat(concat(concat(substr(s,1,2),substr(s,6,1),substr(s,4,2), concat(substr(s,7,1),substr(s,3,1) 2：串 s 的長度為 n，其中的字符各不相同，所以 s='(x+z)*y'中含 1 個字符的子串有 n 個，2 個字符的子串有 n-1 個，含 n-2 個字符的子串有 3 個，

7、含 n-1 個字符的子串有 2 個，共有非平凡子串的個數是 n(n+1)/2-1。 3：串t的next和nextval函數值見下表： 下標j 1 2 3 4 5 6 7 8 9 10 11 串t a b c a a c c b a c a nextj 0 1 1 1 2 2 1 1 1 2 1 nextvalj 0 1 1 0 2 2 1 1 0 2 0 第 5 章解答 一、選擇題 15：cbbdb 610：abcdb 二、判斷題 15：oopop 610：opopp 三、填空題 1、loc(a00)+(i*n+j)*k 2、(x,y,z) 3、按行優先和按列優先 4、三元數組，十字鏈表 5、

8、288b，1282，1072，1276 6、8950 7、行下標，列下標，元素值 8、(a,b)，(c,d)，b，(d) 9、子表 10、(b),(c,(d) 四、綜合題 1、 i211v j433132332113-212 2、特殊矩陣是指具有相同值的矩陣元素或零元素的分布具有一定規律，可以將其壓縮存儲在一維數組中，矩陣元素 a ij 的下標 i 和 j 與其在一維數中存放的下標 k 之間存在一一對應關系，故不會失去隨機存取功能。 稀疏矩陣中零元素的分布沒有一定規律，可以將非零元素存于三元組表中，非零元素a ij 在三元組中的存放位置與 i、j 沒有對應關系，故失去隨機存取功能。 3、n 階

9、對稱矩陣 a 中，a ij =a ji ，可以僅存放下三角元素（或上三角元素）。 設 r=max(i,j)，c=min(i,j), k=r(r-1)/2+c-1; 例如，4階對稱矩陣a，按行優先順序存于一維數組f10中， 0 1 2 3 4 5 6 7 8 9 a11 a21 a22 a31 a32 a33 a41 a42 a43 a44 當i=3，j=2時，k=3*2/2+2-1=4; 當i=2，j=3時，k=4 (2)當對稱矩陣a按列優先順序壓縮存放，若僅存放上三角元素，則有： k=r(r-1)/2+c-1 例如，4階對稱矩陣a，按列優先順序存于一維數組f10中， 0 1 2 3 4 5

10、6 7 8 9 a11 a12 a22 a13 a23 a33 a14 a24 a34 a44 當i=1，j=3時，k=3*2/2+1-1=3；當i=3，j=1時，k=3 第 6 章解答 一、選擇題 15：cbbdb 610：cbabb 1115：dacdc 二、判斷題 15：popoo 610：ooopp 1115：pppop 三、填空題 1、ëlog 2 nû+1 2、最小 3、n2+1 4、最大值 5、5 6、51 7、98 8、2 k -1 9、31 10、不能 四、綜合題 1： （1）根結點：a （2）葉子結點：b，d，f，h，i，j，k （3）k 的祖先：a，c

11、，g （4）j 的兄弟：i （5）樹的深度為 5 2：二叉樹形態 3：答 4：二叉樹形態 5：答 afhgdecb wpl=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69 e 20 f a d c h g i k j 6511193262303 2381001710 721ahc fdbeg00011100001111a 000b 101c 10000d 1001e 11f 10001g 01h 0012 15 611187341230 6：(1)樹形態： 7：答 3 25510199 7 61332 (2)帶權路徑長度：wpl=(6+7+9)*2+5*3+(2+3)*4

12、=44+15+20=79 8：(1)樹形態： 10 答 a：011，b：10，c：00，d：010，e：11 54991834163 13064 (2)帶權路徑長度：wpl=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129 9 答： hgfdc bae 11 答：先序：fdbacegihj， 中序：abcdefghij， 后序：acbedhjigf 12 答：度為 2 的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的。即，在一般樹中若某結點只有一個孩子，就無需區分其左右次序，而在二叉樹中即使是一個孩子也有左右之分。 13 答： (1)前

13、序遍歷序列是：abcdefgh， (2)中序遍歷序列是：cbdeaghf (3)后序遍歷序列是：cedbhgfa 27 11 16 5 6 2 7 4 9 al ki hfcejgdb 第 7 章解答 一、選擇題 15：bbabb 610：bacbb 1115：aaabd 1620：bcddb 2125：cabca 2630：dbbbb 二、填空題 1、n-1條 2、極小連通子圖 3、鄰接矩陣 4、深度優先搜索 5、1 6、拓撲排序 7、圖的鄰接矩陣第i列中非零元素的個數 8、n-1 9、圖的鄰接矩陣第i行全置零 10、出度 三、判斷題 15：oopoo 610：oooop 四、綜合題 1 答

14、案：1，5，2，3，6，4 1，5，6，2，3，4 5，1，2，3，6，4 5，1，6，2，3，4 5，6，1，2，3，4 2答案：(1)最早發生時間和最遲發生時間： (2)關鍵路徑： 頂點v2v1v0vl vev5v4v3230866230866v0v13v5v4v3v222342 3 答案：(1)求 ve 和 vl (2)關鍵路徑 事件 1 2 3 4 5 6 7 8 9 ve 0 6 4 5 7 7 16 14 18 vl 0 6 6 8 7 10 16 14 18 4 答案：(1) 是強連通圖 (2) 鄰接矩陣和鄰接表為： 00000000000111 11v3v4v3v2v1v2 v

15、4v3v1 5答案： 終點 最短路徑求解過程 b 6 (a,b) 5 (a,c,b) c 3 (a,c) d ¥ 6 (a,c,d) 6 (a,c,d) e ¥ 7 (a,c,e) 7 (a,c,e) 7 (a,c,e) f ¥ ¥ ¥ 9 (a,c,d,f) 9 (a,c,d,f) vj c b d e f s a,c a,c,b a,c,d a,c,e a,c,d,f 第 9 章解答 一、選擇題 15：addaa 610：cbccc 二、填空題 1、散列地址空間大小 2、2 3、沖突 4、中序 5、大，小 6、4 7、2 8、m，é

16、;m/2ù，m-1，ém/2ù-1 9、m，ém/2ù 10、63 三、判斷題 15：oppop 四、綜合題 1 答案：(1)表形態： 0 10 9 8 7 6 5 4 3 2 141 30 53 22 13 46 013 1 1 1 2 1 1 (2)asl：asl(7)=(1*5+2*1+3*1)/7=(5+2+3)/7=10/7 2 答案：(1)表形態： 0 12 11 10 9 8 7 6 5 4 3 2 111 10 23 84 20 19 55 68 27 142 2 1 3 1 1 2 1 2 1 (2)平均查找長度：asl(10

17、)=(1*5+2*4+3*1)/10=1.6 3 答案： asl：asl(9)=(1*1+2*2+3*3+3*4)/9=26/9 4 答案：(1)表形態： (2)asl：asl(12)=(1*7+2*2+3*3)/7=(7+4+9)/12=5/3 5 答案：表形態： (2)asl：asl(8)=(1*6+2*2)/7=(6+4)/8=5/4 4 4 20 20 20 20 20 20 20 第 10 章解答 一、選擇題 15：ccbdc 610：bcdbd 二、填空題 1、遞增排列，遞減排列 2、希爾排序、選擇排序、快速排序、堆排序 3、84,79,56,38,40,46 4、冒泡排序 5、選

18、擇排序 6、希爾、快速、堆、歸并 7、歸并 8、40,30,50,80,70,60 9、選擇 10、3 三、判斷題 15： poopp 四、綜合題 1 答案：初始： 54，23，89，48，64，50，25，90，34 1：（23，54），89，48，64，50，25，90，34 2：（23，54，89），48，64，50，25，90，34 3：（23，48，54，89），64，50，25，90，34 4：（23，48，54，64，89），50，25，90，34 5：（23，48，50，54，64，89），25，90，34 6：（23，25，48，50，54，64，89），90，34 7：（23，25，48，50，54，64，89，90），34 8：（23，25，48