2022年《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集

1、. . . . . .c 數(shù)據(jù)結(jié)構(gòu)習(xí)題集第一章序論思考題 ：1.1 簡(jiǎn)述下列術(shù)語(yǔ)：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類(lèi)型、抽象數(shù)據(jù)類(lèi)型作業(yè)題 ：1.2 設(shè)有數(shù)據(jù)結(jié)構(gòu)（ d，r） ，其中d=d1, d2, d3, d4 r=r1, r2 r1= , , , , , r2= (d1, d2), (d1, d3), (d1, d4), (d2, d4), (d2, d3) 試?yán)L出其邏輯結(jié)構(gòu)示意圖。1.3 設(shè) n 是正整數(shù)。試寫(xiě)出下列程序段中用記號(hào)“”標(biāo)注的語(yǔ)句的頻度：(1) i=1; k=0; while(i=n-1) k+=10*i; i+; (2) i=1; k=0; do k+

2、=10*i; i+; while(i=n-1) (3)i=1; k=0; do k+ = 10*i; i+; while(i=n); (4) i=1; j=0; while(i+jn) if(i=(y+1)*(y+1) y+; (6) x=91; y=100; while ( y0 ) if(x100) x-=10; y-; else x+ ; (7) for( i=0; in; i+) for( j=i; jn; j+) for( k=j; kn; k+) x+=2; 1.4 試寫(xiě)一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)x,y 和 z的值。1.5 已知 k 階斐波那契序列的定義為：f0=0

3、, f1=0, , fk-2=0, fk-1=1；fn= fn-1+ fn-2+ + fn-k, n=k,k+1, 試編寫(xiě)求 k 階斐波那契序列的第m項(xiàng)值的函數(shù)算法， k 和 m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。第二章線性表思考題 ：2.1 描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)。2.2 描述以下幾個(gè)概念：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、順序表、有序表。作業(yè)題 ：2.3 已知順序表 la 中數(shù)據(jù)元素按非遞減有序排列。試寫(xiě)一個(gè)算法，將元素x 插到 la 的合適位置上，保持該表的有序性。2.4 已知單鏈表la 中數(shù)據(jù)元素按非遞減有序排列。按兩種不同情況，分別寫(xiě)出算法，將元素 x 插到 la

4、 的合適位置上，保持該表的有序性： （1）la 帶頭結(jié)點(diǎn)；（2）la不帶頭結(jié)點(diǎn)。2.5 試寫(xiě)一個(gè)算法，實(shí)現(xiàn)順序表的就地逆置，即在原表的存儲(chǔ)空間將線性表（a1,a2, ., an-1,an）逆置為 (an,an-1, ., a2,a1) 2.6 試寫(xiě)一個(gè)算法，對(duì)帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)就地逆置。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁(yè)，共 14 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁(yè)，共 14 頁(yè) - - - - - - - - -. . . .

5、 . .c 2.7 已知線性表 l采用順序存儲(chǔ)結(jié)構(gòu)存放。對(duì)兩種不同情況分別寫(xiě)出算法，刪除l 中值相同的多余元素， 使得 l 中沒(méi)有重復(fù)元素：(1)l 中數(shù)據(jù)元素?zé)o序排列； (2)l中數(shù)據(jù)元素非遞減有序排列。2.8 將 2.7 題中 l的存儲(chǔ)結(jié)構(gòu)改為單鏈表，寫(xiě)出相應(yīng)的實(shí)現(xiàn)算法。2.9 設(shè)有兩個(gè)非遞減有序的單鏈表a和 b。請(qǐng)寫(xiě)出算法，將a和 b“就地”歸并成一個(gè)按元素值非遞增有序的單鏈表c 。2.10 設(shè)有一個(gè)長(zhǎng)度大于1 的單向循環(huán)鏈表，表中既無(wú)頭結(jié)點(diǎn)，也無(wú)頭指針，s為指向表中某個(gè)結(jié)點(diǎn)的指針, 如圖 2-1 所示。試編寫(xiě)一個(gè)算法，刪除鏈表中指針s 所指結(jié)點(diǎn)的直接前驅(qū)。2.11 已知線性表用帶頭結(jié)點(diǎn)

6、的單鏈表表示，表中結(jié)點(diǎn)由三類(lèi)字符組成：字母、數(shù)字和其他字符。 試編寫(xiě)算法， 將該線性鏈表分割成三個(gè)循環(huán)單鏈表，每個(gè)循環(huán)單鏈表中均只含有一類(lèi)字符。2.12 已知線性表用順序存儲(chǔ)結(jié)構(gòu)表示，表中數(shù)據(jù)元素為n 個(gè)正整數(shù)。試寫(xiě)一算法，分離該表中的奇數(shù)和偶數(shù)， 使得所有奇數(shù)集中放在左側(cè)， 偶數(shù)集中放在右側(cè)。要求： (1) 不借助輔助數(shù)組 ;(2) 時(shí)間復(fù)雜度為 o(n)。2.13 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表l=(a1,a2,a3,.,an)。試寫(xiě)一時(shí)間復(fù)雜度為 o(n)的算法，將 l 改造為 l=(a1,a3,.,an,.,a4,a2) 。第三章棧和隊(duì)列思考題 ：3.1 簡(jiǎn)述棧和線性表的差別。

7、3.2 如果進(jìn)棧序列為 a、b、c、d，寫(xiě)出所有可能的出棧序列。s 待刪結(jié)點(diǎn)圖 2-1 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁(yè)，共 14 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁(yè)，共 14 頁(yè) - - - - - - - - -. . . . . .c 3.3 簡(jiǎn)述棧和隊(duì)列的相同點(diǎn)和差異。3.4 已知棧 s中存放了 8 個(gè)數(shù)據(jù)元素，自棧底至棧頂依次為 (1,2,3,4,5,6,7,8)。（1）寫(xiě)出在執(zhí)行了函數(shù)調(diào)用algo1(s) 后，s中的

8、元素序列。（2）在（ 1）的基礎(chǔ)上，又執(zhí)行了函數(shù)調(diào)用algo2(s,5) ，寫(xiě)出此時(shí) s 中的元素序列。void algo1(stack &s) int a10, i, n=0; while(!stackempty(s) n+; pop(s, an); for(i=1; i=n; i+) push(s, ai); void algo2(stack &s, int e) stack t; int d; initstack(t); while(!emptystack(s) pop(s,d); if(d!=e) push(t,d); while(!stackempty(t) pop(

9、t,d); push(s,d); 3.5 已知隊(duì)列 q 中自隊(duì)頭至隊(duì)尾依次存放著(1,2,3,4,5,6,7,8)。寫(xiě)出在執(zhí)行了函數(shù)調(diào)用 algo3(q) 后，q中的元素序列。void algo3(queue &q) stack s; int d; initstack(s); 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁(yè)，共 14 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁(yè)，共 14 頁(yè) - - - - - - - - -. . . . .

10、 .c while(!queueempty(q) dequeue(q,d); push(s,d); while(!stackempty(s) pop(s,d); enqueue(q,d); 作業(yè)題：3.6 試寫(xiě)一個(gè)算法， 識(shí)別依次讀入的一個(gè)以為結(jié)束符的字符序列是否為形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中都不包含字符 &, 且序列2是序列1的逆序。例如，“a+b&b+a ”是屬于該模式的字符序列，而“13&31”則不是。3.7 假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種符號(hào)：圓括號(hào)“(”和“) ” 、方括號(hào)“ ”和“ ” 、花括號(hào)“ ”和“ ” ，且這

11、三種括號(hào)可按任意次序嵌套使用。編寫(xiě)判別給定表達(dá)式中所含的括號(hào)是否正確配對(duì)的算法（已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中）。3.8 設(shè)表達(dá)式由單字母變量、 雙目運(yùn)算符和圓括號(hào)組成 （如:“(a*(b+c)-d)/e） ” 。試寫(xiě)一個(gè)算法，將一個(gè)書(shū)寫(xiě)正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。3.9 試用類(lèi) c寫(xiě)一個(gè)算法，對(duì)逆波蘭式求值。3.10 假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示隊(duì)列，只設(shè)一個(gè)尾指針指向隊(duì)尾元素，不設(shè)頭指針。試編寫(xiě)相應(yīng)的隊(duì)列初始化、入隊(duì)和出隊(duì)的算法。3.11 假設(shè)將循環(huán)隊(duì)列定義為： 以 rear 和 length 分別指示隊(duì)尾元素和隊(duì)列長(zhǎng)度。試給出此循環(huán)隊(duì)列的隊(duì)滿(mǎn)條件， 并寫(xiě)出相應(yīng)的入隊(duì)和出隊(duì)算法

12、 （在出隊(duì)算法中要傳遞回隊(duì)頭元素的值） 。3.12 試寫(xiě)一個(gè)算法： 判別讀入的一個(gè)以 為結(jié)束符的字符序列是否是“回文”（所謂“回文”是指正讀和反讀都相同的字符序列，如“xxyzyxx ”是回文，而“abcab”則不是回文）。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁(yè)，共 14 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁(yè)，共 14 頁(yè) - - - - - - - - -. . . . . .c 第五章多維數(shù)組5.1 已知多維數(shù)組a2233按行優(yōu)先方

13、式存儲(chǔ)。試按存儲(chǔ)位置的先后次序，列出所有數(shù)組元素aijkl序列（為了簡(jiǎn)化表達(dá)，可以只列出形如“i,j,k,l ”的序列，如元素a0021可表示為“ 0,0,2,1 ” ） 。5.2 假設(shè)有一個(gè)二維數(shù)組a0.50.7， 每個(gè)元素占 6 個(gè)字節(jié)，首元素 a00的地址為 1000，求： (1)a的體積； (2)最后一個(gè)元素 a57的地址； (3)按行主序方式存儲(chǔ)時(shí)， a24的地址； (4)按列主序方式存儲(chǔ)時(shí)， a24的地址；5.3 設(shè)有上三角矩陣 ann，nnnnnacaaaaaaaaa.333223221131211將其上三角的元素逐行存于數(shù)組b0.m-1 中（m充分大） ，使得 bk=aij且

14、kf1(i)+f2(j)+c 。試推導(dǎo)出函數(shù)f1、f2和常數(shù) c（要求 f1和 f2中不含常數(shù)項(xiàng)）。5.4 設(shè)有一個(gè)準(zhǔn)對(duì)角矩陣mmmmmmmmaaaaaaaaaaaa2,212,22, 1212,124443343322211211.按以下方式存于一維數(shù)組b4m中：0 1 2 3 4 5 6 k 4m-2 4m-1 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁(yè)，共 14 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁(yè)，共 14 頁(yè) - - - - -

15、- - - -. . . . . .c a11a12a21a22a33a34a43. aij. a2m-1,2ma2m,2m寫(xiě)出由一對(duì)下標(biāo) (i,j)求 k 的轉(zhuǎn)換公式。5.5 已知稀疏矩陣 a45如下：70040000000603250010a(1) 用三元組表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的三元組表示意圖；(2) 用十字鏈表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的十字鏈表示意圖。5.6 設(shè)稀疏矩陣 a和 b均以三元組順序表作為存儲(chǔ)結(jié)構(gòu)。試寫(xiě)出計(jì)算矩陣相加cab的算法，其中， c是另設(shè)的、存放結(jié)果的三元組表（提示：可用類(lèi)似于兩個(gè)有序順序表歸并的處理方法） 。5.7 試編寫(xiě)一個(gè)算法，實(shí)現(xiàn)以三元組的形式打印用十字鏈表表

16、示的稀疏矩陣中所有非零元素及其下標(biāo)。5.8 試編寫(xiě)一個(gè)算法，實(shí)現(xiàn)以矩形陣列的形式打印用十字鏈表表示的稀疏矩陣。第六章樹(shù)和二叉樹(shù)6.1 試分別繪出具有 3 個(gè)結(jié)點(diǎn)的樹(shù)和 3 個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。6.2 設(shè)結(jié)點(diǎn) x是二叉樹(shù)上一個(gè)度為1 的結(jié)點(diǎn)， x有幾個(gè)子樹(shù)？6.3 描述滿(mǎn)足下列條件的二叉樹(shù)形態(tài)： (1) 先序遍歷序列與中序遍歷序列相同； (2) 后序遍歷序列與中序遍歷序列相同； (3) 先序遍歷序列與后序遍歷序列相同；6.4 一個(gè)深度為 h的滿(mǎn) k 叉樹(shù)有如下性質(zhì)： 第 h層上所有結(jié)點(diǎn)都是葉子結(jié)點(diǎn)， 其余各層上每個(gè)結(jié)點(diǎn)都有k 棵非空子樹(shù)。如果從 1 開(kāi)始按自上而下、 自左向右的次序?qū)θ?/p>

17、部結(jié)點(diǎn)編號(hào)，問(wèn)：(1) 各層的結(jié)點(diǎn)數(shù)目是多少？(2) 編號(hào)為 i 的結(jié)點(diǎn)的父結(jié)點(diǎn) (若存在 ) 的編號(hào)是多少？精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁(yè)，共 14 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁(yè)，共 14 頁(yè) - - - - - - - - -. . . . . .c (3) 編號(hào)為 i 的結(jié)點(diǎn)的第 j 個(gè)孩子 ( 若存在 )的編號(hào)是多少？(4) 編號(hào)為 i 的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？6.5 已知一棵度為 k

18、的樹(shù)中有 n1 個(gè)度為 1 的結(jié)點(diǎn)， n2 個(gè)度為 2 的結(jié)點(diǎn)， . ，nk 個(gè)度為 k 的結(jié)點(diǎn)，問(wèn)該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？6.6 已知在一棵含有 n 個(gè)結(jié)點(diǎn)的樹(shù)中，只有度為 k 的分支結(jié)點(diǎn)和度為 0 的葉子結(jié)點(diǎn)。試求該樹(shù)含有的葉子結(jié)點(diǎn)的數(shù)目。6.7 設(shè) n 和 m為二叉樹(shù)中兩個(gè)結(jié)點(diǎn)，用“ 1” 、 “0” 、和“” （分別表示肯定，否定和不一定）填寫(xiě)下表：已知問(wèn)先序遍歷時(shí)n 在 m之前？中序遍歷時(shí)n 在 m之前？后序遍歷時(shí)n 在 m之前？n 在 m左方n 在 m右方n 是 m祖先n 是 m子（注：如果離n 和 m 的最近的共同祖先x 存在， 且 n 位于 x 的左子樹(shù)中， m 位于 x 的右

19、子樹(shù)中，則稱(chēng)“ n 在 m 的左方”或“ m 在 n 的右方”。 ）6.8 已知一棵樹(shù)如圖 6-1 所示，畫(huà)出與該樹(shù)對(duì)應(yīng)的二叉樹(shù)，并寫(xiě)出該樹(shù)的先根遍歷序列和后根遍歷序列。a b c d e f g h k i j 圖 6-1 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁(yè)，共 14 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁(yè)，共 14 頁(yè) - - - - - - - - -. . . . . .c 6.9 將如圖 6-2 所示的森林轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)

20、。6.10 畫(huà)出和下列二叉樹(shù)（如圖6-3 所示）相應(yīng)的森林。6.11 已知某二叉樹(shù)的中序序列為dcbgeahfijk ， 后序序列為 dcegbfhkjia 。請(qǐng)畫(huà)出該二叉樹(shù)。6.12 已知樹(shù) t 的先根遍歷訪問(wèn)序列為gfkdaiebchj ，后根遍歷訪問(wèn)序列為diaekfcjhbg 。請(qǐng)畫(huà)出樹(shù) t。圖 6-3 a b c c a b c a b a d e b c f g h j k l i k 圖 6-2 a c d e b f g h j i l m n o 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 9 頁(yè)，共 14 頁(yè) - - - -

21、- - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 9 頁(yè)，共 14 頁(yè) - - - - - - - - -. . . . . .c 圖 7-1 v5v4v2v3v1v66.13 已知森林 f 的先根遍歷訪問(wèn)序列為abcdefghijkl ，中根遍歷訪問(wèn)序列為 cbefdgajiklh 。請(qǐng)畫(huà)出這個(gè)森林f。6.14 假設(shè)某個(gè)電文由 (a,b,c,d,e,f,g,h)8個(gè)字母組成， 每個(gè)字母在電文中出現(xiàn)的次數(shù)分別為 (7,19,2,6,32,3,21,10)，試解答下列問(wèn)題： (1) 畫(huà)出出 huffman 樹(shù)； (2) 寫(xiě)出每個(gè)字母的

22、huffman 編碼； (3) 在對(duì)該電文進(jìn)行最優(yōu)二進(jìn)制編碼處理后，電文的二進(jìn)制位數(shù)。6.15 寫(xiě)出復(fù)制一棵二叉樹(shù)的算法。6.16 試編寫(xiě)算法，實(shí)現(xiàn)將二叉樹(shù)所有結(jié)點(diǎn)的左右子樹(shù)互換。6.17 寫(xiě)出按層次遍歷二叉樹(shù)的算法。6.18 寫(xiě)出判斷給定二叉樹(shù)是否為完全二叉樹(shù)的算法。6.19 寫(xiě)出判斷兩棵給定二叉樹(shù)是否相似的算法。(注：兩棵二叉樹(shù) b1 和 b2 相似是指： b1和 b2 皆空，或者皆不空且b1 的左、右子樹(shù)和 b2的左、右子樹(shù)分別相似。) 6.20 利用棧的基本操作，寫(xiě)出二叉樹(shù)先序遍歷的非遞歸算法。6.21 寫(xiě)出統(tǒng)計(jì)樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)的算法，樹(shù)用孩子兄弟鏈表表示。6.22 寫(xiě)出計(jì)算樹(shù)的深度的

23、算法，樹(shù)用孩子兄弟鏈表表示。6.23 寫(xiě)出計(jì)算二叉樹(shù)第 k層結(jié)點(diǎn)數(shù)的算法。6.24 寫(xiě)出計(jì)算二叉樹(shù)深度的算法。第七章圖7.1 已知有向圖如圖 7-1 所示，請(qǐng)給出該圖的 (1)鄰接矩陣示意圖 (2)鄰接表示意圖 (3)逆鄰接表精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 10 頁(yè)，共 14 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 10 頁(yè)，共 14 頁(yè) - - - - - - - - -. . . . . .c (4)所有強(qiáng)連通分量7.2 已知圖 g的鄰接矩陣

24、如圖 7-2 所示。 寫(xiě)出該圖從頂點(diǎn) 1 出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列，并畫(huà)出相應(yīng)的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。1 2 3 4 5 6 7 8 9 10 1 0 0 0 0 0 0 1 0 1 0 2 0 0 1 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 1 0 0 4 0 0 0 0 1 0 0 0 1 0 5 0 0 0 0 0 1 0 0 0 1 6 1 1 0 0 0 0 0 0 0 0 7 0 0 1 0 0 0 0 0 0 1 8 1 0 0 1 0 0 0 0 1 0 9 0 0 0 0 1 0 1 0 0 1 10 1 0 0 0 0 1 0

25、0 0 0 圖 7-2 7.3 無(wú)向帶權(quán)圖如圖 7-3 所示， (1)畫(huà)出它的鄰接矩陣，并按prim 算法求其最小生成樹(shù)。 (2)畫(huà)出它的鄰接表，并按kruskal 算法求其最小生成樹(shù)7.4 有向圖如圖 7-4 所示，試寫(xiě)出其所有可能的拓?fù)湫蛄?。圖 7-3 a b c e h f d g 4 3 5 5 5 5 97 4 5 6 6 2 3 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 11 頁(yè)，共 14 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 11 頁(yè)，共

26、14 頁(yè) - - - - - - - - -. . . . . .c 7.5 試?yán)?dijkstra 算法求圖 7-5 中頂點(diǎn) a 到其他各頂點(diǎn)之間的最短路徑。要求寫(xiě)出執(zhí)行算法過(guò)程中，數(shù)組d、p 和 s 各步的狀態(tài)。7.6 試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：insertvex(g,v)，insertarc(g,v,w), deletevex(g,v)和 deletearc(g,v,w)。7.7 試在鄰接表存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：insertvex(g,v)，insertarc(g,v,w), deletevex(g,v)和 deletearc(g,v,w)。7.8 設(shè)具有 n 個(gè)頂

27、點(diǎn)的有向圖用鄰接表存儲(chǔ)。試寫(xiě)出計(jì)算所有頂點(diǎn)入度的算法，可將每個(gè)頂點(diǎn)的入度值分別存入一維數(shù)組int indegreen中。7.9 假設(shè)有向圖以鄰接表作為存儲(chǔ)結(jié)構(gòu)。試基于圖的深度優(yōu)先搜索策略寫(xiě)一算法，判斷有向圖中是否存在由頂點(diǎn)vi 至頂點(diǎn) vj(i!=j)的路徑。7.10 假設(shè)有向圖以鄰接表作為存儲(chǔ)結(jié)構(gòu)。試基于圖的廣度優(yōu)先搜索策略寫(xiě)一算法，判斷有向圖中是否存在由頂點(diǎn)vi 至頂點(diǎn) vj(i!=j)的路徑。7.11 以鄰接表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)求單源最短路徑的dijkstra算法。g a b d c e f 圖 7-5 15 122 5 6 84 9 10 43 圖 7-4 v1 v5 v2 v3 v6

28、 v4 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 12 頁(yè)，共 14 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 12 頁(yè)，共 14 頁(yè) - - - - - - - - -. . . . . .c 第九章查找9.1 若對(duì)大小均為 n 的有序順序表和無(wú)序順序表分別進(jìn)行順序查找，試在下列三種情況下分別討論兩者在等概率時(shí)平均查找長(zhǎng)度是否相同？ (1)查找不成功，即表中沒(méi)有關(guān)鍵字等于給的值k的記錄； (2)查找成功，且表中只有一個(gè)關(guān)鍵字等于給定值k的記錄； (3)查找

29、成功，且表中有若干個(gè)關(guān)鍵字等于給定值k 的記錄，要求找出所有這些記錄。9.2 試分別寫(xiě)出在對(duì)有序線性表(a,b,c,d,e,f,g)中進(jìn)行折半查找， 查值等于 e、f 和 g 的元素時(shí)，先后與哪些元素進(jìn)行了比較。9.3 畫(huà)出對(duì)長(zhǎng)度為 13 的有序表進(jìn)行折半查找的判定樹(shù)，并分別求其等概率時(shí)查找成功和查找失敗的asl 。9.4 已知如下所示長(zhǎng)度為12 的表： (jan, feb, mar, apr, may, jun, july, aug, sep, oct, nov, dec) 表中，每個(gè)元素的查找概率分別為： (0.1,0.25,0.05,0.13,0.01,0.06,0.11,0.07,0.02,0.03,0.1,0.07) (1)若對(duì)該表進(jìn)行順序查找，求查找成功的平均查找長(zhǎng)度； (2)畫(huà)出從初態(tài)為空開(kāi)始，依次插入結(jié)點(diǎn)，生成的二叉排序樹(shù)； (3)計(jì)算該二叉排序樹(shù)查找成功的平均查找長(zhǎng)度； (4)將二叉排序樹(shù)中的結(jié)點(diǎn)mar 刪除，畫(huà)出經(jīng)過(guò)刪除處理后的二叉排序樹(shù)。9.5 已知關(guān)鍵字序列 10,25,33,19,06,49