山東大學(xué)網(wǎng)絡(luò)教育數(shù)據(jù)結(jié)構(gòu)A-C

1、數(shù)據(jù)結(jié)構(gòu)模擬卷一、選擇題1 .在一個長度為n的順序表的任一位置插入一個新元素的漸進(jìn)時間復(fù)雜度為（）。A. O（n）B. O（n/2）C. O（1）D. O（n 2）2 .帶頭結(jié)點的單鏈表first 為空的判定條件是：（）。A. first = NULL;B. first->link = NULL;C. first->link = first;D. first != NULL;3 .從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D ,初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)4 .在系統(tǒng)實現(xiàn)遞歸調(diào)用時需利用遞歸工作記錄保存實際參數(shù)的值。在傳值參數(shù)

2、情形，需為對應(yīng)形式參數(shù)分配空間，以存放實際參數(shù)的副本；在引用參數(shù)情形，需保存實際參數(shù)的（）,在被調(diào)用程序中可直接操縱實際參數(shù)。A.空間B.副本 C.返回地址D.地址5 .以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（）。A.廣義表 B. 二叉樹 C. 稀疏矩陣D.串6 .以下屬于邏輯結(jié)構(gòu)的是（）。A.順序表 B. 哈希表C.有序表 D. 單鏈表7 .對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長 度為（）的值除以9。A. 20B. 18C.25D. 228 .在有向圖中每個頂點的度等于該頂點的（）。A.入度B. 出度C.入度與出度之和D.入度與出度之差9 .在基于排序碼比較的

3、排序算法中，（）算法的最壞情況下的時間復(fù)雜度不高于O（nlog 2n） 。A.起泡排序B.希爾排序C.歸并排序 D.快速排序）的查找速度。10 .當(dāng)“的值較小時，散列存儲通常比其他存儲方式具有（A.較慢B.較快C.相同 D.不同二、填空題1 .二維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個數(shù)組元素最多有 2 個直接前驅(qū)（或直接后繼）。2 .將一個n階三對角矩陣A的三條對角線上的元素按行壓縮存放于一個一維數(shù)組 B中， A00存放于B0中。對于任意給定數(shù)組元素BK,它應(yīng)是A中第【（K+1） /3】行的元素。3 .鏈表對于數(shù)據(jù)元素的插入和刪除不需移動結(jié)點，只需改變相關(guān)結(jié)點的 指針 域的值。4 .在一個鏈?zhǔn)綏?/p>

4、中，若棧頂指針等于NULL則為一空棧。5 .主程序第一次調(diào)用遞歸函數(shù)被稱為外部調(diào)用，遞歸函數(shù)自己調(diào)用自己被稱為內(nèi)部調(diào)用， 它們都需要利用棧保存調(diào)用后的返回 地址。6 .在一棵機(jī)中， 葉子結(jié)點沒有后繼結(jié)點。7 . 一棵樹的廣義表表示為a （b （c, d （e, f）, g （h） ）, i （j, k （x, y）,結(jié)點 f的層數(shù)為3。假定根結(jié)點的層數(shù)為0。8 .在一棵AVL樹（高度平衡的二叉搜索樹）中，每個結(jié)點的左子樹高度與右子樹高度之差的絕對值不超過1。9 . n （n > 0）個頂點的無向圖最多有 n（n-1）/2 條邊，最少有 0 條邊。10 .在索引存儲中，若一個索引項對應(yīng)數(shù)據(jù)

5、對象表中的一個表項（記錄），則稱此索引為 稠密 索引，若對應(yīng)數(shù)據(jù)對象表中的若干個表項，則稱此索引為 稀疏 索引。三、判斷題1 .數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的（對）2 .鏈?zhǔn)酱鎯υ诓迦牒蛣h除時需要保持物理存儲空間的順序分配，不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序（錯）3 .在用循環(huán)單鏈表表示的鏈?zhǔn)疥犃兄?，可以不設(shè)隊頭指針，僅在鏈尾設(shè)置隊尾指針（對）4 .通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高（錯）5 . 一個廣義表的表尾總是一個廣義表（對）6 .當(dāng)從一個小根堆（最小堆）中刪除一個元素時，需要把堆尾元素填補(bǔ)到堆頂位置，然后 再按條件把它逐層向下調(diào)整

6、，直到調(diào)整到合適位置為止（對）7 .對于一棵具有 n個結(jié)點，其高度為 h的二叉樹，進(jìn)行任一種次序遍歷的時間復(fù)雜度為O(h)(錯)而且與圖的邊數(shù)也有8 .存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān),關(guān)(錯)9 .直接選擇排序是一種穩(wěn)定的排序方法(錯)10 .閉散列法通常比開散列法時間效率更高(錯)四、運(yùn)算題1 .設(shè)有一個10 10的對稱矩陣A,將其下三角部分按行存放在一個一維數(shù)組 存放于B0中，那么A85存放于B中什么位置。2 .這是一個統(tǒng)計單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù)的算法，其中請重新編寫出正確的while循環(huán)。int count ( ListNode * Ha, Ele

7、mType x ) / Ha為不帶頭結(jié)點的單鏈表的頭指針int n = 0;while ( Ha->link != NULL ) Ha = Ha->link;if ( Ha->data = x ) n+;return n;3 .已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J中序序列：C, B, A, E, F, D, I, H, J, G后序序列：4 . 已知一個有序表 (15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 )于一維數(shù)組a12中，根據(jù)折半搜索過程

8、填寫成功搜索下表中所給元素94時的比較次數(shù)。B 中，A00while循環(huán)有錯,順序存儲34, 56, 58, 63,3456586394元素值 比較次數(shù)5 .設(shè)散列表為 HT17,待插入關(guān)鍵碼序列為 Jan, Feb, Mar, Apr, May, June,July, Aug, Sep, Oct, Nov, Dec ,散列函數(shù)為 H (key) = i 2 ,其中，i 是關(guān)鍵碼第一個字母在字母表中的序號?，F(xiàn)采用線性探查法解決沖突。字母ABCDEFGHIJKLM序號12345678910111213字母NOPQRSTUVWXYZ序號14151617181920212223242526(1)試畫

9、出相應(yīng)的散列表;(2)計算等概率下搜索成功的平均搜索長度；參考答案：1.根據(jù)題意，矩陣 A中當(dāng)元素下標(biāo)I與J滿足I >J時，任意元素 AIJ在一維數(shù)組B中的存放位置為I * (I + 1) / 2 + J ,因此，A85在數(shù)組B中位置為8 * (8 + 1) / 2 + 5 = 41。2 .while ( Ha != NULL ) if ( Ha->data = x ) n+;Ha = Ha->link;3 .后序序列：C, B, F, E, I, J, H, G, D, A4.3456586394021344元素值比較次數(shù)/對1個給1分，全對給8分AprAugDecFebJ

10、anMarMayJun eJulySepOctNov067(1)(2)(2)(4)(5)(2)(5)(6)1112138910123455.H(Jan)=102H(Feb) =62 = 3 ,成功.H(Mar)=132H(Apr) =1 2 = 0 ,成功.H(May)=132H(June) =10 2 = 5 , = 6 ,功.H(July)=H(Aug)=H(Sep) =19 2 = 9H(Oct)=11 ,成功.H(Nov)=11 , = 12 ,成功.H(Dec)=42 = 2 ,成功.相應(yīng)的散列表(6分)，錯一個存儲位置扣1分，最多扣6分。(2)搜索成功的平均搜索長度為1/12 *

11、(1 + 2 + 1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6) = 31 / 12(2分)五、算法設(shè)計題已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為：struct BTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中 data為結(jié)點值域，leftChild 和rightChild分別為指向左、右子女結(jié)點的指針域，根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中結(jié)點總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹的根結(jié)點。int BTreeCount ( BinTreeNode*

12、 BT );解:int BTreeCount ( BinTreeNode* BT ) if ( BT = NULL ) return 0;else return BTreeCount ( BT->leftChild ) + BTreeCount(BT->rightChild )+ 1數(shù)據(jù)結(jié)構(gòu)模擬卷、單項選擇題1 .以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（）。A.循環(huán)隊列B. 鏈表C.哈希表 D. 棧2 .以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（）。A.廣義表 B. 二叉樹 C. 稀疏矩陣D.串3 .以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（）。A.棧B.哈希表 C. 線索樹 D.雙向鏈表4 .在下

13、面的程序段中，對x的賦值語句的頻度為（）。FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A. O（2n） B . O（n）C. O（n2）D . O（log J）5 .下面關(guān)于線性表的敘述中，錯誤的是哪一個（）。A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B.線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D.線性表采用鏈接存儲，便于插入和刪除操作。6 .線性表是具有 門個（）的有限序列（n>0）。A.表元素 B .字符C.數(shù)據(jù)元素D .數(shù)據(jù)項 E .信息項則利7 .若某線性表最常用的操作是存取任一指

14、定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算,9 .下面給出的四種排序法中（）A.插入 B. 冒泡10 .下列排序算法中，其中（A.堆排序，冒泡排序C.直接選擇排序，歸并排序11 .已知一算術(shù)表達(dá)式的中綴形式為A. -A+B*C/DE B. -A+B*CD/E C-+*ABC/DED. -+A*BC/DE用（）存儲方式最節(jié)省時間。A.順序表 B .雙鏈表 C .帶頭結(jié)點的雙循環(huán)鏈表D .單循環(huán)鏈表8 .某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運(yùn)算時間。A.單鏈表 B .僅有頭指針的單循環(huán)鏈表C .雙鏈表D.僅有尾指針的單循環(huán)鏈表排序法是不穩(wěn)定性

15、排序法。C.二路歸并D.堆積）是穩(wěn)定的。B.快速排序，堆排序D.歸并排序，冒泡排序A+B*C-D/E,后綴形式為 ABC*+DE/-,其前綴形式為12.算術(shù)表達(dá)式a+b* （c+d/e ）轉(zhuǎn)為后綴表達(dá)式后為（）。A. ab+cde/*B . abcde/+*+C . abcde/*+ D . abcde*/+二、填空題，在橫線處填寫合適內(nèi)容1 .數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)包括順序、鏈接、索引和散列等四種。2 .在程序運(yùn)行過程中可以擴(kuò)充的數(shù)組是 動態(tài) 分配的數(shù)組。這種數(shù)組在聲明它時需要使用數(shù)組指針。3 .在鏈表中進(jìn)行插入和刪除操作的效率比在順序存儲結(jié)構(gòu)中進(jìn)行相同操作的效率4 .棧是一種限定在表的一端進(jìn)行

16、插入和刪除的線性表，又被稱為 后進(jìn)先出 表。5 .如果一個對象部分地包含自己，或自己定義自己，則稱這個對象是 遞歸 的對象。6 . 一棵樹的廣義表表示為a（b（c,d（e,f）,g（h）,i（j,k（x,y），結(jié)點f的層數(shù)為 3假定樹根結(jié)點的層數(shù)為0。7 . 一棵樹按照左子女-右兄弟表示法轉(zhuǎn)換成對應(yīng)的二叉樹，則該二叉樹中樹根結(jié)點肯定沒有 右 子女。8 .向一棵二叉搜索樹中插入一個元素時，若元素的值小于根結(jié)點的值，則應(yīng)把它插入到根 結(jié)點的 左子樹 上。9 .設(shè)圖 G=（V,E） , V=1,2,3,4,E=<1,2>,<1,3>,<2,4>,<3,4&g

17、t;，從頂點 1 出發(fā)，對圖 G進(jìn)行廣度優(yōu)先搜索的序列有 2 種。10 .每次直接或通過基準(zhǔn)元素間接比較兩個元素，若出現(xiàn)逆序排列就交換它們的位置，這種排序方法叫做 交換 排序。11 .快速排序在平均情況下的空間復(fù)雜度為 O （log2n） 。12 .若對長度n=10000的線性表進(jìn)行二級索引存儲，每級索引表中的索引項是下一級20個表項的索引，則一級索引表的長度為 500。三、判斷題1 .在順序表中進(jìn)行順序搜索時，若各元素的搜索概率不等，則各元素應(yīng)按照搜索概率的降序排列存放，則可得到最小的平均搜索長度（ 對）2 .在二叉搜索樹中，若各結(jié)點的搜索概率不等，使得搜索概率越小的結(jié)點離樹根越近，則得到的

18、是最優(yōu)二叉搜索樹（ 錯）3 .對于AOER絡(luò)，加速任一關(guān)鍵活動都能使整個工程提前完成（ 錯）4 .直接選擇排序是一種穩(wěn)定的排序方法（ 錯）5 .閉散列法通常比開散列法時間效率更高（ 錯）6 .數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的（對）7 .順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機(jī)（或直接）訪問（對）8 .在一個順序存儲白循環(huán)隊列中，隊頭指針指向隊頭元素的后一個位置（ 錯）9 .用非遞歸方法實現(xiàn)遞歸算法時一定要使用遞歸工作棧（ 錯）10 .在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的結(jié)果（ 對）四、運(yùn)算題1 .設(shè)有

19、一個二維數(shù)組 A1020,按行存放于一個連續(xù)的存儲空間中，A00的存儲地址是200,每個數(shù)組元素占1個存儲字，則A62的存儲字地址是多少。A62 的存儲字地址:2 .已知一棵二叉樹的中序和后序序列如下，求該二叉樹的高度(假定空樹的高度為-1)和度為2、度為1及度為0的結(jié)點個數(shù)。中序序歹 U： c,b,d,e,a,g,i,h,j,f后序序歹 U： c,e,d,b,i,j,h,g,f,a求解一下問題：高度：度為2的結(jié)點數(shù)：度為1的結(jié)點數(shù)：度為0的結(jié)點數(shù)：3 .假定一組記錄為(36,75,83,54,12,67,60,40),將按次序把每個結(jié)點插入到初始為空的一棵AVL樹中，請回答在插入時需進(jìn)行“左

20、單旋轉(zhuǎn)”、“右單旋轉(zhuǎn)”、“先左后右雙旋轉(zhuǎn)”、“先右后左雙旋轉(zhuǎn)”，“不調(diào)整”的結(jié)點數(shù)各是多少？左單旋轉(zhuǎn)結(jié)點個數(shù)：右單旋轉(zhuǎn)結(jié)點個數(shù)：先左后右雙旋轉(zhuǎn)結(jié)點個數(shù)：先右后左雙旋轉(zhuǎn)結(jié)點個數(shù)：不調(diào)整結(jié)點個數(shù)：4 .已知一個帶權(quán)圖的頂點集V和邊集G分別為：V=0,1,2,3,4,5,6;E=(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)12;試根據(jù)迪克斯特拉(Dijkstra)算法求出從頂點0到其余各頂點的最短路徑，在下面填寫對應(yīng)的路徑長度。頂點： 0123 4560路徑長度:5.已知一個數(shù)據(jù)表為

21、36,25,25*,62,40,53，請寫出在進(jìn)行快速排序的過程中每次劃分后數(shù)據(jù)表的變化。(0) 36 25 25* 62 40 53(2)參考答案：1. A62的存儲字地址：322答案說明：按行存儲時，計算 Aij地址的公式為LOC(i,j)=LOC(0,0)+(i*n+j)*d其中首地址LOC(0,0)=200,每個數(shù)組元素的存儲占用數(shù)d=1,二維數(shù)組的列數(shù) n=20,根據(jù)題意，元素A62的存儲地址為LOC(6,2)=200+(6*20+2)*1=3222.高度：4度為2的結(jié)點數(shù)：3度為1的結(jié)點數(shù)：3度為0的結(jié)點數(shù)：43.左單旋轉(zhuǎn)結(jié)點個數(shù)：1先左后右雙旋轉(zhuǎn)結(jié)點個數(shù):先右后左雙旋轉(zhuǎn)結(jié)點個數(shù)：

22、0不調(diào)整結(jié)點個數(shù)：64. 錯1個數(shù)彳1扣2分，最多扣全部 8分。0161014252131頂點： 0123 45 6路徑長度:5.(0) 36 25 25* 62 40 53(1) 25* 25 36 62 40 53(2) 25* 25 36 53 40 62(3) 25*25 36 40 53 62五、算法設(shè)計題1.設(shè)有一個表頭為first的單鏈表。試設(shè)計一個算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點按逆序鏈接。參考答案：解答1template <class Type > void List <Type>: : Tnerse() if (first= NULL )re

23、turn ;ListNode <Type >* p=first link ; , *pr =NULL ;While (p !=NULL ) First f link =pr ;Pr =first ;first =p ;p =pf link;first ->link =pr ;解答2template <class Type > void List <Type>: : Tnerse() ListNode <Type >* p , *head = new ListNode <Type > ();While (first ! = NUL

24、L ) P=first ;first = firstf link;尸 link =head f link ; head f link =p;first = head flink ; delete head ;數(shù)據(jù)結(jié)構(gòu)模擬卷、單項選擇題1 .數(shù)據(jù)結(jié)構(gòu)是（）。A. 一種數(shù)據(jù)類型B.數(shù)據(jù)的存儲結(jié)構(gòu)C. 一組性質(zhì)相同的數(shù)據(jù)元素的集合D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2 .算法分析的目的是（）。A.辨別數(shù)據(jù)結(jié)構(gòu)的合理性B.評價算法的效率C.研究算法中輸入與輸出的關(guān)系D.鑒別算法的可讀性3 .在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（）。A.插入B.刪除C.排序D.定位4

25、.若進(jìn)棧序列為1,2, 3, 4, 5, 6,且進(jìn)棧和出棧可以穿插進(jìn)行，則可能出現(xiàn)的出棧序列為（）。A. 3, 2, 6, 1, 4, 5C. 1,2, 5, 3, 4, 6B. 3, 4, 2, 1, 6, 5D. 5, 6, 4, 2, 3, 15.設(shè)串 sl= " Data Structureswith Java" ,s2= " it ",則子串定位函數(shù)index(s1,s2)值為（）。A. 15B. 16C. 17D. 186 .二維數(shù)組A89按行優(yōu)先順序存儲，若數(shù)組元素A23的存儲地址為1087, A47的存儲地址為1153,則數(shù)組元素A67的

26、存儲地址為（）。A.1207B,1209C.1211D.12137 .在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（）。A.隊列B.棧C.線性表D.有序表8 .在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系（）。A.不一定相同B,都相同C.都不相同D.互為逆序9 .若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的（）。A.層次遍歷算法B.前序遍歷算法C.中序遍歷算法D.后序遍歷算法10 .若用鄰接矩陣表示一個有向圖，則其中每一列包含的1的個數(shù)為（）。A.圖中每個頂點的入度B.圖中每個頂點的出度C.圖中弧的條數(shù)D.圖中連通分量的數(shù)目11 .圖的鄰接矩陣表

27、示法適用于表示（）。A.無向圖B.有向圖C.稠密圖D.稀疏圖12 .在對n個關(guān)鍵字進(jìn)行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元 素，則在進(jìn)行第i趟排序之前，無序區(qū)中關(guān)鍵字元素的個數(shù)為（）。A. iB. i+1C. n-iD. n-i+1二、填空題1 .棧是特殊 的線性表，其運(yùn)算遵循后進(jìn)先出 的原則。2 .棧 是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3 . 一個棧的輸入序列是：1, 2, 3則不可能的棧輸出序列是 3, 1, 2。4 .二叉樹由(1)根節(jié)點 ,(2)左子樹, (3)右子樹三個基本單元組成。5 .在二叉樹中，指針 p 所指結(jié)點為葉子結(jié)點的條件是=p->lch

28、ild=NULL&&p->rchild=NULL 。6 .具有256個結(jié)點的完全二叉樹的深度為_9。7 .已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該 樹有 12 個葉子結(jié)點。8 .若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的比較和記錄的移動 。9 .分別采用堆排序， 快速排序，冒泡排序和歸并排序，對初態(tài)為有序的表，則最省時間的是冒泡排序 算法，最費(fèi)時間的是快速排序算法。10 .不受待排序初始序列的影響，時間復(fù)雜度為O(M)的排序算法是選擇排序，在排序 算法的最后一趟開始之前， 所有元素都可能不在其最終位置上的排序算

29、法是歸并排序 C三、解答題1 .某廣義表的表頭和表尾均為(a,(b,c),畫出該廣義表的圖形表示。2 .已知二叉樹的先序序列和中序序列分別為HDACBGFE ADCBHFEG(1)畫出該二叉樹；(2)畫出與(1)求得的二叉樹對應(yīng)的森林。3 .已知帶權(quán)圖的鄰接表如下所示，其中邊表結(jié)點的結(jié)構(gòu)為：依此鄰接表從頂點 C出發(fā)進(jìn)行深度優(yōu)先遍歷。(1)畫出由此得到的深度優(yōu)先生成樹；(2)寫出遍歷過程中得到的從頂點C到其它各頂點的帶權(quán)路徑及其長度。參考答案：1.2.頂點C到頂點A的帶權(quán)路徑為（C,D,B,A）,其長度為8+20+11=39頂點C到頂點B的帶權(quán)路徑為（C,D,B）,其長度為8+20=28頂點C到頂點D的帶權(quán)路徑為（C,D）,其長度為8頂點C到頂點E的帶權(quán)路徑為（C,D,B,F,E ）,其長度為8+20+9+14=51頂點C到頂點F的帶權(quán)路徑為（C,D,B,F ）,其長度為8+20+9=37四、算法設(shè)計題1 .已知中序線索二叉樹 T右子樹不空。設(shè)計算法，將 S所指的結(jié)點作為T的右子樹中的 一個葉子結(jié)點插入進(jìn)去，并使之成為TT的右子樹的（中序序列）第一個結(jié)點（同時要修改相應(yīng)的線索關(guān)系）。2 .寫出在中序線索二叉樹里；找指定結(jié)點在后序下的前驅(qū)結(jié)點的算法。 參考答案：1 .答案：題目分析若使新插入的葉子結(jié)點 S成T右子樹中序序列的第一個結(jié)點，則應(yīng)在 T 的右子樹中最左面的結(jié)