期末復(fù)習(xí)題_數(shù)據(jù)結(jié)構(gòu)

1、中國(guó)石油大學(xué)（北京）遠(yuǎn)程教育學(xué)院 期 末 復(fù)習(xí)題一、選擇題（本大題共15小題，每小題2分，共30分）1. 以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（ ）A、循環(huán)隊(duì)列 B、鏈表C、哈希表 D、棧2. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（ ）A、110 B、108C、100 D、1203. 假設(shè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針為head,則該鏈表為空的判定條件是（ ）A、head= =NULL B、head>next= =NULL C、head>next= =head D、head!=NULL4. 若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源?/p>

2、插進(jìn)行，則不可能出現(xiàn)的出棧序列是（ ） A、2，4，3，1，5，6B、3，2，4，1，6，5C、4，3，2，1，5，6D、2，3，5，1，6，45. 下列關(guān)鍵字序列中，構(gòu)成小根堆的是（ ）A、12，21，49，33，81，56，69，41 B、81，69，56，49，41，33，21，12 C、81，49，69，41，21，56，12，33 D、12，21，49，33，81，41，56，696. 下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹(shù)的是（ ）A、B樹(shù) B、AVL樹(shù) C、二叉排序樹(shù) D、哈夫曼樹(shù)7. 用順序存儲(chǔ)的方法來(lái)存儲(chǔ)一棵二叉樹(shù)，存放在一維數(shù)組A1.N中，若結(jié)點(diǎn)Ai有右孩子，則其右孩子是（ ）。A、

3、A2i B、A2i-1 C、A2i+1 D、Ai/28. 設(shè)樹(shù)T的高度為4，其中度為1、2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2、1、1，則T中葉子數(shù)為（ ）A、 5 B、 6 C、7 D、 89. 有數(shù)據(jù)53，30，37，12，45，24，96，從空二叉樹(shù)開(kāi)始逐個(gè)插入數(shù)據(jù)來(lái)形成二叉排序樹(shù)，若希望高度最小，則應(yīng)選擇下面哪個(gè)序列輸入（ ）A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，5310. 對(duì)下面有向圖給出了四種可能的拓?fù)湫蛄?，其中錯(cuò)誤的是（ ）A、1，5，2，6，3，4B、

4、1，5，6，2，3，4C、5，1，6，3，4，2 D、5，1，2，6，4，311. m階B-樹(shù)中所有非終端（除根之外）結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)必須大于或等于( ) A、 m/2+1 B、m/2-1 C、m/2 D、m12. 散列文件也稱為( ) A、順序文件 B 、索引文件C、直接存取文件 D、間接存取文件13. 數(shù)據(jù)結(jié)構(gòu)是（ ）A、一種數(shù)據(jù)類型B、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C、一組性質(zhì)相同的數(shù)據(jù)元素的集合D、相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合14. 從邏輯關(guān)系來(lái)看，數(shù)據(jù)元素的直接前驅(qū)為0個(gè)或1個(gè)的數(shù)據(jù)結(jié)構(gòu)只能是（ ）A、線性結(jié)構(gòu)B、樹(shù)形結(jié)構(gòu)C、線性結(jié)構(gòu)和樹(shù)型結(jié)構(gòu) D、線性結(jié)構(gòu)和圖狀結(jié)構(gòu)15. 設(shè)p

5、為指向雙向循環(huán)鏈表中某個(gè)結(jié)點(diǎn)的指針，p所指向的結(jié)點(diǎn)的兩個(gè)鏈域分別用pllink和prlink表示，則同樣表示p指針?biāo)赶蚪Y(jié)點(diǎn)的表達(dá)式是（ ）A、pllink B、prlinkC、pllinkllink D、pllinkrlink16. 若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1.m，topi代表第i個(gè)棧( i =1,2)棧頂，棧1的底在v1，棧2的底在Vm，則棧滿的條件是（ ）A、 |top2-top1|=0 B、 top1+1=top2 C、 top1+top2=m D、 top1=top217. 若一棵二叉樹(shù)有11個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)是（ ）A、10 B、11C、12

6、D、不確定的18. 樹(shù)的先根序列等同于與該樹(shù)對(duì)應(yīng)的二叉樹(shù)的（ ）A、先序序列B、中序序列C、后序序列 D、層序序列19. 下面關(guān)于哈希(Hash，雜湊)查找的說(shuō)法正確的是( )A、哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小B、除留余數(shù)法是所有哈希函數(shù)中最好的 C、不存在特別好與壞的哈希函數(shù)，要視情況而定D、若需在哈希表中刪去一個(gè)元素，解決沖突都只要簡(jiǎn)單的將該元素刪去即可20. 下列序列中，（ ）是執(zhí)行第一趟快速排序后所得的序列。 A、 68，11，18，69 23，93，73 B、 68，11，69，23 18，93，73 C、 93，73 68，11，69，23，18 D、 68，1

7、1，69，23，18 93，7321. 下列關(guān)鍵字序列中，構(gòu)成小根堆的是( )A、 (84，46，62，41，28，58，15，37) B、 (84，62，58，46，41，37，28，15)C、 (15，28，46，37，84，41，58，62) D、 (15，28，46，37，84，58，62，41)22. ISAM文件和VASM文件屬于( ) A、索引非順序文件 B、順序文件C、索引順序文件 D、散列文件23. 下面程序段的時(shí)間復(fù)雜度為（ ）for (i=0; i<m; i+)for (j=0; j<n; j+)Aij=i*j;A、O(m2) B、 O(n2) C、O(m*n

8、) D、O(m+n)24. 已知指針p和q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。假設(shè)指針s指向另一個(gè)單鏈表中某個(gè)結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語(yǔ)句為（ ）A、q->next=s->next；s->next=p； B、s->next=p；q->next=s->next；C、p->next=s->next；s->next=q； D、s->next=q；p->next=s->next；25. 為便于判別有向圖中是否存在回路，可借助于（ ）A、廣度優(yōu)先搜索算法 B、最小生成樹(shù)算法 C、最短路徑算法 D、拓?fù)渑判?/p>

9、算法26. 若以S和X分別表示進(jìn)棧和退棧操作，則對(duì)初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作系列是（ ）A、SXSSXXXX B、SXXSXSSXC、SXSXXSSX D、SSSXXSXX27. 設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個(gè)元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是( )A、2 B、3 C、5 D、628. 假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素。已知隊(duì)列的長(zhǎng)度為length，指針rear指向隊(duì)尾元素的下一個(gè)存儲(chǔ)位置，則隊(duì)頭元素所在的存儲(chǔ)位 置為（ ）。A、(rear-length+m+1)%m B、(rear-length+m)%m

10、C、(rear-length+m-1)%m D、(rear-length)%m29. 在一個(gè)鏈隊(duì)列中，front和rear分別為頭指針和尾指針，則插入一個(gè)結(jié)點(diǎn)s的操作為（ ）。A、s->next=rear;rear=s; B、front=front->next;C、s->next=front;front=s; D、rear->next=s;rear=s;30. 對(duì)于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是（ ）A、35和41 B、 23和39 C、15和44 D、25和5131. 采用二叉鏈表存儲(chǔ)的n個(gè)結(jié)點(diǎn)的二叉樹(shù)，共有空指針（ ）個(gè)。A、n+1 B、

11、n C、n-1 D、2n-132. 連通網(wǎng)的最小生成樹(shù)是其所有生成樹(shù)中（ ）A、頂點(diǎn)集最小的生成樹(shù) B、邊集最小的生成樹(shù)C、頂點(diǎn)權(quán)值之和最小的生成樹(shù) D、邊的權(quán)值之和最小的生成樹(shù)33. 對(duì)記錄序列(314，298，508，123，486，145)依次按個(gè)位和十位進(jìn)行兩趟基數(shù)排序之后所得結(jié)果為（ ）A、123，145，298，314，486，508 B、508，314，123，145，486，298C、486，314，123，145，508，298 D、298，123，508，486，145，31434. 任何一個(gè)無(wú)向連通圖的最小生成樹(shù)( )。A、一定有多棵 B、可能不存在 C、一棵或多棵 D、

12、只有一棵35. 無(wú)向圖的鄰接矩陣是一個(gè)( )A、對(duì)角矩陣 B、上三角矩陣 C、對(duì)稱矩陣 D、零矩陣36. 設(shè)無(wú)向圖G-=(V,E)和G=(V,E),如G為G的生成樹(shù)，則下列說(shuō)法中不正確的是( )。A、G為G的無(wú)環(huán)子圖 B、G為G 連通分量C、G為G極小連通子圖且V=V D、G為G的子圖37. 以v1為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（ ）A、 v1，v2，v3，v4，v5，v6，v7 B、 v1，v2，v5，v4，v3，v7，v6C、 v1，v2，v3，v4，v7，v5，v6 D、 v1，v2，v5，v6，v7，v3，v438. 下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（ ）

13、A、0,10,110,1111 B、0,1,00,11C、00,010,0110,1000 D、b,c,aa,ac,aba,abb,abc39. 希爾排序的增量序列必須是（ ）。A、 遞增的 B、遞減的 C、隨機(jī)的 D、非遞減的40. 采用起泡排序法對(duì)n個(gè)關(guān)鍵字進(jìn)行升序排序，若要使排序過(guò)程中比較關(guān)鍵字的次數(shù)最多，則初始時(shí)的序列應(yīng)滿足條件（ ）A、關(guān)鍵字完全無(wú)序 B、關(guān)鍵字基本有序C、關(guān)鍵字從小到大排列 D、關(guān)鍵字從大到小排列41. 在下列內(nèi)部排序中( )是不穩(wěn)定的。A、希爾排序 B、起泡排序 C、直接插入排序 D、歸并排序42. 分別以下列序列構(gòu)造二叉排序樹(shù)，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的

14、是( )。A、（100，80， 90， 60， 120，110，130） B、（100，120，110，130，80， 60， 90）C、（100，60， 80， 90， 120，110，130） D、(100，80， 60， 90， 120，130，110)43. 在查找過(guò)程中，沖突指的是（ ）。A、兩個(gè)元素具有相同序號(hào) B、兩個(gè)元素的鍵值不同C、不同鍵值對(duì)應(yīng)相同的存儲(chǔ)地址 D、兩個(gè)元素的鍵值相同44. 對(duì)有14個(gè)元素的有序表A1.14作二分查找，查找元素A4時(shí)的被比較元素依次為（ ）。A、A1，A2，A3，A4 B、A1，A14，A7，A4 C、A7，A5，A3，A4 D、A7，A3，A5

15、，A445. 以v1為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行廣度度優(yōu)先遍歷，正確的遍歷序列是（ ）A、 v1，v2，v3，v4，v5，v6，v7B、v1，v2，v5，v6，v7，v3，v4C、 v1，v2，v5，v6，v7，v3，v4D、 v1，v4，v5，v7，v6，v2，v3二、填空題(本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分)1. 數(shù)據(jù)的物理結(jié)構(gòu)包括 的存儲(chǔ)和 的存儲(chǔ)。2. 若一個(gè)算法中的語(yǔ)句頻度之和為T(mén)(n)=1921n+4nlogn,則算法的時(shí)間復(fù)雜度為 。 3. 下面程序段的時(shí)間復(fù)雜度是 。 i=1； while (i<=n) i=i*3；4. 循環(huán)隊(duì)列用數(shù)組A0.m-

16、1存放其元素值，已知其頭尾指針?lè)謩e是front和rear ，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是 。5. 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 _。6. 線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_ 。7. 已知一無(wú)向圖G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開(kāi)始遍歷圖，得到的序列為abecd，則采用的是 遍歷方法。8. 如果排序過(guò)程不改變 之間的相對(duì)次序，則稱該排序方法是穩(wěn)定的。9. 從順序表中刪除一個(gè)元素時(shí)，表中所有在被刪元素之后的元素均需 一個(gè)位置

17、。 10. 當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，算法執(zhí)行時(shí)間T(n)的數(shù)量級(jí)被稱為算法的 。11. 若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個(gè)數(shù)即為頂點(diǎn)vi的 。12. 一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 。13. 假設(shè)S和X分別表示進(jìn)棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX，則由“a*b+c/d”得到“ab*cd/+”的操作序列為 。14. .如圖所示的有向無(wú)環(huán)圖可以排出 種不同的拓?fù)湫蛄小?5. 從空樹(shù)起，依次插入關(guān)鍵字1l，27，35，48，52，66和73構(gòu)造所得的二叉排序樹(shù)，在等概率查找的假設(shè)下，查找成功時(shí)的平均查找長(zhǎng)度為 。16.

18、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是 。 17. 求最小生成樹(shù)的克魯斯卡爾(Kruskal)算法耗用的時(shí)間與圖中 的數(shù)目正相關(guān)。18. 已知一棵完全二叉樹(shù)中共有768結(jié)點(diǎn)，則該樹(shù)中共有 個(gè)葉子結(jié)點(diǎn)。19. 實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了一個(gè)標(biāo)志數(shù)組標(biāo)志已訪問(wèn)的圖的結(jié)點(diǎn)外，還需要 存放被訪問(wèn)的結(jié)點(diǎn)以實(shí)現(xiàn)遍歷。20. Prim（普里姆）算法適用于求 的網(wǎng)的最小生成樹(shù)；kruskal（克魯斯卡爾）算法適用于求 的網(wǎng)的最小生成樹(shù)。21. 對(duì)長(zhǎng)度為20的有序表進(jìn)行二分查找的判定樹(shù)的高度為 。22. 設(shè)一棵完全二叉樹(shù)有128個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)的深度為 ，有_ 個(gè)葉子結(jié)點(diǎn)。23. 高度為h的完全

19、二叉樹(shù)中最少有 個(gè)結(jié)點(diǎn)，最多有 個(gè)結(jié)點(diǎn)。24. 設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對(duì)應(yīng)的最小生成樹(shù)上有 條邊。25. 構(gòu)造n個(gè)結(jié)點(diǎn)的強(qiáng)連通圖，至少有 條弧。26. 表達(dá)式求值是 應(yīng)用的一個(gè)典型例子。27. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1，則棧的容量至少應(yīng)該是 。28. 快速排序算法在最差的情況下其時(shí)間復(fù)雜度是 。29. 對(duì)序列55，46，13，05，94，17，42進(jìn)行基數(shù)排序，第一趟排序后的結(jié)果是 。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）1. 已知

20、二叉樹(shù)的先序遍歷序列ABCDEFGH，中序遍歷序列為CBEDFAGH，畫(huà)出二叉樹(shù)。2. 如圖請(qǐng)給出鄰接表、鄰接矩陣及逆鄰接表。V1V3V2V43. 由字符集s，t，a，e，I及其在電文中出現(xiàn)的頻度構(gòu)建的哈夫曼樹(shù)如圖所示。已知某段電文的哈夫曼編碼為111000010100，請(qǐng)根據(jù)該哈夫曼樹(shù)進(jìn)行譯碼，寫(xiě)出原來(lái)的電文。4. 請(qǐng)畫(huà)出下圖所示的樹(shù)所對(duì)應(yīng)的二叉樹(shù)，并寫(xiě)出對(duì)應(yīng)二叉樹(shù)的先序遍歷和中序遍歷。123456785. 設(shè)散列表為HT13, 散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突, 對(duì)下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36

21、 造表。采用線性探查法尋找下一個(gè)空位, 畫(huà)出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度。6. 已知帶權(quán)圖G如圖所示，畫(huà)出圖G的一棵最小生成樹(shù)。7. 假設(shè)用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母構(gòu)成，這8個(gè)字母在電文中出現(xiàn)的概率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。8. 試用權(quán)集合12,4,5,6,1,2構(gòu)造哈夫曼樹(shù)，并計(jì)算哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度。9. 畫(huà)出與如圖所示森林對(duì)應(yīng)的二叉樹(shù)。10. 已知一個(gè)散列表如下圖所示：3520334859 0 1 2 3 4 5 6 7 8 9 10 11

22、 12 其散列函數(shù)為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為： hi=(h(key)+*h1(key)%m =0,1,，m-1其中： h1(key)=key%11+1回答下列問(wèn)題：（1）對(duì)表中關(guān)鍵字35，20，33和48進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各為多少？（2）該散列表在等概率查找時(shí)查找成功的平均查找長(zhǎng)度為多少？11. 請(qǐng)畫(huà)出與下列二叉樹(shù)對(duì)應(yīng)的森林。12. 對(duì)于給定結(jié)點(diǎn)的關(guān)鍵字集合K=5，7，3，1，9，6，4，8，2，10，（1）試構(gòu)造一棵二叉排序樹(shù)；（2）求等概率情況下的平均查找長(zhǎng)度ASL。13. 給出下圖對(duì)應(yīng)的鄰接矩陣，并給出A，B，C三個(gè)頂點(diǎn)的出度與入度

23、 14. 已知圖5.32如下所示，求從頂點(diǎn)a到其余各頂點(diǎn)的最短路徑。（給出求解過(guò)程）543223356abdfce15. 閱讀下列算法，并回答問(wèn)題：（1）假設(shè)串由合法的英文字母和空格組成，并以0作結(jié)束符。設(shè)串s=”Iamastudent”(表示空格符)，寫(xiě)出f30（s）的返回值；（2）簡(jiǎn)述算法f30的功能。int f30 (char*s)int i, n, inword;n=inword=0;for (i=0;si!=0;i+)if (si!=&& inword=0)inword=1;n+; else if (si=&& inword=1) inword=0;r

24、eturn n;16. 閱讀下列函數(shù),并回答問(wèn)題：（1）假設(shè)隊(duì)列q中的元素為(a,b,c,d,e),其中“a”為隊(duì)頭元素。寫(xiě)出執(zhí)行函數(shù)調(diào)用Conv(&q)后的隊(duì)列q；（2）簡(jiǎn)述算法Conv的功能。void Conv (Queue *Q) Stack S; InitStack(&S); while (!QueueEmpty(Q) Push(&S, DeQueue(Q); while (! StackEmpty(&S) nQueue(Q,Pop(&S);17. 閱讀下列函數(shù),并回答問(wèn)題：已知整形數(shù)組L1.8中的元素依次為（19，18，15，17，16，13，

25、12，10），閱讀下列函數(shù)，并寫(xiě)出執(zhí)行函數(shù)調(diào)用sort(L, 8)時(shí)，對(duì)L進(jìn)行的頭兩趟（pass分別為0和1）處理結(jié)果。 void sort (int R,int n) int pass = 0, k, exchange, x; do k=pass%2+1; exchange = 0; while (k<n) if (Rk>Rk+1) x = Rk; Rk = Rk+1; Rk+1 = x; exchange =1; K+=2; pass +;while (exchange = = 1| pass <=1);keynext18. 已知帶頭結(jié)點(diǎn)的單鏈表中的關(guān)鍵字為整數(shù)，為提高查

26、找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長(zhǎng)度為m，散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點(diǎn)結(jié)構(gòu)為： 。請(qǐng)?jiān)诳杖碧幪钊脒m當(dāng)內(nèi)容，使其成為一個(gè)完整算法。void f33 (LinkList L, LinkList H, int m)/由帶頭結(jié)點(diǎn)的單鏈表L生成散列表H，散列表生成之后原鏈表不再存在 int i,j; LinkList p,q; for (i=0;i<m;i+) Hi= (1) ; p=L->next; while(p) q=p->next; j=p->key%m; (2) ; Hj=p; (3) ; free(L); 19. 下列

27、函數(shù)的功能是，對(duì)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)的兩個(gè)遞增有序表（表中不存在值相同的數(shù)據(jù)元素）進(jìn)行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La中，其中La和Lb分別為兩個(gè)鏈表的頭指針。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個(gè)完整的算法。 void union (LinkList La, LinkList Lb)/本算法的功能是將所有Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La表中LinkList pre = La, q;LinkList pa = La -> next;LinkList pb = Lb -> next;free (Lb);while (pa &&

28、amp; pb)if (pa -> data <pb -> data) pre = pa; pa = pa -> next;else if (pa -> data > pb ->data) (1) ;pre = pb;pb = pb -> next; (2) ;elseq = pb; pb = pb -> next; free (q);if (pb) (3) ;20. 閱讀算法f30，并回答問(wèn)題：下列算法為有向圖拓?fù)渑判?請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。void f30 (hdnodes graph ,int n) int

29、 i,j,k,top; node_pointer ptr ; top=-1; for (i=0; i<n; i+) if (!graphi.count)graphi.count=top; top=i; for (i=0; i<n; i+) if_ (1)_ fprintf(stderr, "ngraph has a cycle n"); exit(1); else j=top; _ (2)_; printf( "v%d, " ,j) ; for (ptr=graphj.link; ptr; ptr=ptr->link) k=ptr-&g

30、t;vertex; graphk.count-; if( (3) ) graphk.count=top; top=k; 21. 閱讀算法f31，并回答問(wèn)題：下列算法功能為在數(shù)組a的前n(n>=1)個(gè)元素中找出第k(1<=k<=n)小的值。這里假設(shè)數(shù)組a中各元素的值都不相同。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。#define MAXN 100int aMAXN,n,k;int f31(int a, int n, int k)int low, high, i, j, m, t; k-,;low=0 ;high=n-1; do i=low; j=high ; t=al

31、ow; do while (i<j && t<aj) j-; if (i<j) ai+=aj; while (i<j && t>=ai) i+ if (i<j) aj-=ai; while (i<j);ai=t;if (1) ; if (i<k) low= (2) ; else high= (3) ;while （i!=k）;return(ak); 22. 閱讀算法f33，并回答問(wèn)題：下列算法功能為奇偶交換排序，思路如下：第一趟對(duì)所有奇數(shù)的i,將ai和ai+1進(jìn)行比較,第二趟對(duì)所有偶數(shù)的i,將ai和ai+1進(jìn)行比較,每次比較時(shí)若ai>ai+1,將二者交換;以后重復(fù)上