數(shù)據(jù)結(jié)構(gòu)習(xí)題.doc

一、單項(xiàng)選擇題1 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行_C_。A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p;C. q-next=s; s-next=p; D. p-next=s; s-next=q;2判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0）為空的條件是_C_。A. rear - front= =m0 B. rear-front-1= =m0 C. front= = rear D. front= = rear+13循環(huán)隊(duì)列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是_A_。A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front4如果某二叉樹的前序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序?yàn)開C_。 A. uwvts B. vwuts C. wuvts D. wutsv5在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊_A_。A. 只有右子樹上的所有結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn)C. 只有左子樹上的部分結(jié)點(diǎn) D. 只有左子樹上的所有結(jié)點(diǎn)6如圖所示二叉樹的中序遍歷序列是_B_。A. abcdgef B. dfebagc C. dbaefcg D. defbagcgcefdbaagedbchf 7一棵二叉樹如圖6.2所示，其中序遍歷的序列為_B _。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh8如圖所示的4棵二叉樹，_C_不是完全二叉樹。(A) (B) (C) (D)9如圖所示的4棵二叉樹，_B_是平衡二叉樹。（A）（B）（C）（D）圖8.8 4棵二叉樹(A) (B) ( C ) (D) 10對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是_D_。A. n B. (n-1)2 C. n-1 D. n2baecdf11對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為_A_；所有鄰接表中的接點(diǎn)總數(shù)是_C_。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e 12已知一個(gè)圖如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_D_；按寬度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_B_。 A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b13已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示。12345324524 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是_C_。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 根據(jù)有向圖的寬度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是_B_。A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v214對(duì)線性表進(jìn)行對(duì)分分查找時(shí)，要求線性表必須_C_。A. 以順序方式存儲(chǔ) B. 以鏈接方式存儲(chǔ)C. 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序D. 以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序15有一個(gè)有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)對(duì)分查找值82為的結(jié)點(diǎn)時(shí)，_C_次比較后查找成功。A. 1 B. 2 C. 4 D. 8二、填空題（將正確的答案填在相應(yīng)的空中）1在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)s (值為e)所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：q=head;while (q-next!=p) q=q-next;s= new Node; s-data=e;q-next=_; /填空s-next=_; /填空s, p2在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q= p-next;p-next=_; /填空delete _ /填空q-next, q 3在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s-next=_和p-next=_的操作。p-next, s 4向量、棧和隊(duì)列都是_結(jié)構(gòu)，可以在向量的_位置插入和刪除元素；對(duì)于棧只能在_插入和刪除元素；對(duì)于隊(duì)列只能在_插入元素和_刪除元素。線性、任何、棧頂、隊(duì)尾、隊(duì)首 5向一個(gè)長度為n的向量的第i個(gè)元素（1in+1）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。n-i+16向一個(gè)長度為n的向量中刪除第i個(gè)元素（1in）時(shí)，需向前移動(dòng)_個(gè)元素。n-i7向棧中壓入元素的操作是_。先移動(dòng)棧頂指針，后存入元素8對(duì)棧進(jìn)行退棧時(shí)的操作是_。先取出元素，后移動(dòng)棧頂指針9在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的_。前一個(gè)位置11一個(gè)棧的輸入序列是12345，則棧的輸出序列12345是_。可能的12已知二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A00)，則Aij的地址是_。LOC (A00)+(n*i+j)*k13二維數(shù)組A1020采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元并且A00的存儲(chǔ)地址是200，則A612的地址是_。200+（6*20+12）= 32614有一棵樹如右圖所示，回答下面的問題： 這棵樹的根結(jié)點(diǎn)是_； 這棵樹的葉子結(jié)點(diǎn)是_； 結(jié)點(diǎn)B的度是_； 這棵樹的度是_； 這棵樹的深度是_； 結(jié)點(diǎn)B的子女是_； 結(jié)點(diǎn)B的父結(jié)點(diǎn)是_； k1 k2,k5,k7,k4 2 3 4 k5,k6 k1 15深度為k的完全二叉樹至少有_個(gè)結(jié)點(diǎn)。至多有_個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從1開始），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是_。 2 k-1 、 2 k-1 、 2 k-2+116一棵二叉樹的第i（i1）層最多有_個(gè)結(jié)點(diǎn)；一棵有n（n0）個(gè)結(jié)點(diǎn)的滿二叉樹共有_個(gè)葉子和_個(gè)非終端結(jié)點(diǎn)。2 i-1 （n+1）/2取整 （n-1）/2取整17由如右圖所示的二叉樹，回答以下問題： 其中序遍歷序列為_； 其前序遍歷序列為_； 其后序遍歷序列為_；dgbaechif 、abdgcefhi 、gdbeihfca18在無向圖G的鄰接矩陣A中，若Aij等于1，則Aji 等于_。1 19已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是_。將矩陣第i行全部置為零20一個(gè)圖的_表示法是唯一的，而_表示法是不唯一的。鄰接矩陣 鄰接表21根據(jù)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點(diǎn)序列是_的。唯一Sssssss-算法題tttttt13-算法填空題hhhh11圖示表示數(shù)據(jù)結(jié)構(gòu)和算法ssssss1下面是線性鏈表的插入運(yùn)算程序算法，其中LOOKFOR(head,a,q)為在非空鏈表中尋找包含指定元素a之前的結(jié)點(diǎn)q的算法，試寫出LOOKFOR(head,a,q)函數(shù)的程序算法。INLINKST(head,a,b)1. GETNODE(p); data(p)b; /取得一個(gè)新結(jié)點(diǎn)p/2. if (head=nil) then headp;next(p)nil; return /空白情況/3. if (data(head)=a) then next(p)head; headp; return /a為頭結(jié)點(diǎn)/4. LOOKFOR(head,a,q) /尋找元素a之前的結(jié)點(diǎn)q/5. next(p)next(q); next(q)p6. return其中LOOKFOR(head,a,q)為在非空鏈表中尋找包含指定元素a之前的結(jié)點(diǎn)q的算法：LOOKFOR(head,a,q) 1. qhead2. While (next(q)nil) and (data(next(q)a) do 3. qnext(q) /如果表中無a結(jié)點(diǎn)，則q指向鏈表最后一個(gè)結(jié)點(diǎn)/刪除運(yùn)算ssssss2下面是線性鏈表的刪除運(yùn)算程序算法，其中LOOKFOR(head,a,q)為在非空鏈表中尋找包含指定元素a之前的結(jié)點(diǎn)q的算法，試寫出LOOKFOR(head,a,q)函數(shù)的程序算法。DELINKST(head,a)1. if (head=nil) then 空表 return /空表情況/2. if(data(head)=a) then snext(head); RET(head); heads; return /a為頭結(jié)點(diǎn)/3. LOOKFOR(head,a,q) 1. if (next(q)=nil) then 無此結(jié)點(diǎn) return2. pnext(q); next (q)next (p)3. RET(p)4. returnssssss3, ,tttttt1,hhhh1一元多項(xiàng)式相加A(x)=5-3x+13x5，B(x)=3x-8x4-6x5+7x8。ADD-POLY(ha ,hb )1. pnext(ha); qnext(hb)2. preha;hcha /pre指向p的前趨，為已經(jīng)算好的多項(xiàng)式的最后一項(xiàng)，為c(x)頭指針/3.while (pnil) AND (qnil) do4.case5.EXP(p)EXP(q):6.prep;pnext(p)7.EXP(p)=EXP(q):8.xCOEF(p)+COEF(q);9.if (x0) then COEF(p)x;prep10.else next(pre)next(p); RET(p)11.pnext(pre);uq;qnext(q);RET(u)12.EXP(p)EXP(q):13.unext(q);next(q)p; next(pre)q;preq;qu14.end(case)15.end(while)16.if(qnil) then next(pre)q17.RET(hb)/釋放多項(xiàng)式B(x)的頭結(jié)點(diǎn)/18.returnssssss4已知S1,m為棧的數(shù)組，top為棧頂?shù)臉?biāo)識(shí)，寫出將元素x入棧的算法程序。PUSF(s,m,top,x)/將元素x入棧/1.if (top=m) then 上溢,return2.top=top+13.stop=x4.returnssssss5已知S1,m為棧的數(shù)組，top為棧頂?shù)臉?biāo)識(shí)，寫出將棧頂元素送入y中的退棧算法程序。POP(s,top,y)/退棧，將棧頂元素送入y中/1.if (top=0) then 下溢,return2.y=stop3.top=top-14.return棧的應(yīng)用表達(dá)式求值A(chǔ)/B*C+Dssssss6 ,tttttt2,hhhh2完成下面表達(dá)式求值（不含括號(hào)）的程序算法，其中OS,NS分別為操作符和操作數(shù)的棧。EXP(OS,top O,NS,top N)/top O,top N 為OS,NS 棧頂指示器,初態(tài)為零/1.PUSH(OS,top O,;)2.t0 /t=0 表示掃描下一個(gè)符號(hào)/3.while(t2) do 4.if(t=0)then read(w) /w中存放當(dāng)前讀入符號(hào)/5.if(w為操作數(shù)) then PUSH(NS,top N,w)6.else7.top(OS,top O,q) /查看當(dāng)前OS棧頂元素q/8. if(wq) then PUSH(OS,top O,w),t05. else 6. if(q=;) and (w=;) then10. POP(NS,top N,z),t2/t=2表示處理結(jié)束/7. elsePOP(NS,top N,x) POP(NS,top N,y)13 POP(OS,top O,q);xy q x; /構(gòu)成一條機(jī)器指令/14. PUSH(NS,top N,x);t1 /t=1表示繼續(xù)處理當(dāng)前符號(hào)/15. 16. end(while)17.return其中TOP（OS,top O,q）為讀棧頂元素,算法如下:TOP(s,top,x)1.if (top=0) then ?？?return2.xstopreturnssssss7過程嵌套和遞歸調(diào)用 1 (n=1,2)Fib(n)= Fib(n-1)+ Fib(n-2) (n2)Fibonacci序列Fib(n)1. if (n=1) or (n=2) then Fib12. else FibFib(n-1)+ Fib(n-2)3. returnssssss8 ,tttttt3,hhhh3回溯求解算法設(shè)有n件體積分別w1,w2,wn的物品和一個(gè)能裝載總體積為T的背包，要求從n件物品中挑選出若干件物品，其體積之和恰好裝滿背包。W1：n存放n件物品的體積S1：n存放放入背包內(nèi)物品的序號(hào)T為背包能容納的體積，I為待選物品序號(hào)每進(jìn)棧一件物品，就從T中減去該物品的體積，若T-Wi=0,則該物品可選，若T-Win,則需退棧，若此時(shí)?？?，則說明無解。算法如下：PACK(T,n,W,S,top)1.top0;i12.while(T0) and (i=0) and (i0) then/取 出棧頂物品/ istop;toptop-1,TT+Wi ii+1/準(zhǔn)備挑選下一件物品/4.end(while)5.背包無解returnssssss0設(shè)CQ0：m-1表示最大容量的循環(huán)隊(duì)列，其中頭、尾指示器(front,rear)均按順時(shí)針方向前進(jìn)，rear=front=m-1為初態(tài)，寫出循環(huán)隊(duì)列的插入算法.ADDCQ(CQ,m,front,rear,x)/將x插入隊(duì)列CQ中/1.rear(rear+1) mod m/mod 為模除運(yùn)算,保證rear循環(huán)計(jì)數(shù)/2.if (front=rear) then 隊(duì)滿 return3.CQrearx4.returnssssss10設(shè)CQ0：m-1表示最大容量的循環(huán)隊(duì)列，其中頭、尾指示器(front,rear)均按順時(shí)針方向前進(jìn)，rear=front=m-1為初態(tài)，寫出循環(huán)隊(duì)列的刪除算法.DELCQ(CQ,m,front,rear,y)/ 刪除隊(duì)首元素送入y中/1.if(front=rear) then 隊(duì)空return2.front(front+1) mod m3.yCQfront4.returnssssss11, tttttt4,hhhh4隊(duì)的應(yīng)用劃分子集問題如運(yùn)動(dòng)會(huì)共設(shè)9個(gè)比賽項(xiàng)目，規(guī)定每個(gè)運(yùn)動(dòng)員最多可以參加三個(gè)項(xiàng)目，則A=1, 2, 3, 4, 5, 6, 7, 8, 9R=(2, 8), (9,4) , (2, 9) , (2, 1) , (2, 5) , (6, 2) , (5, 9) , (5, 6) , (5, 4) , (7, 5) , (7, 6) , (3, 7) , (6, 3)PROCEDURE DIVISION (R, n, cq, newr, Result);FOR k=0 TO n-1 cqkk+1; /n個(gè)元素存入循環(huán)隊(duì)列cq/frontn-1; rearn-1; /頭尾指針賦初值/FOR K=1 TO n newrk0 /newr向量置初值/group1; pre0; /group為當(dāng)前組號(hào)，pre為前一個(gè)出隊(duì)元素編號(hào)，初值為零/(pre9);fi=.t. WHILE rearfront.or.fi=.t. DO /隊(duì)列非空/Fi=.f. frontfront+1; IF front=n+1 THEN front1; Icqfront; /I為當(dāng)前出隊(duì)元素/ IF IpreTHEN /重新開辟新組/groupgroup+1; ResultIgroup; /記錄組號(hào)/FOR k=1 TO n newrkRI, kELSE IF newrI0 THEN /發(fā)生沖突元素，重新入隊(duì)/ rear=rear+1; IF rear=n+1 THEN rear=1; cqrearI ELSE /可以分在當(dāng)前組/ ResultIgroup; FOR k=1 TO n Newrknewrk+RI, k;preIEND(WHILE)；ssssss121. 帶輔助向量的三元組表示設(shè)兩個(gè)輔助向量POS和NUM滿足下列關(guān)系： POS(1)=1POS(i)=POS(i-1)+NUM(i-1),2imPOS(i)表示稀疏矩陣中第i行的第一個(gè)非零元素在三元組中的行號(hào)；NUM(i)表示稀疏矩陣中第i行的非零元素個(gè)數(shù)。稀疏矩陣A對(duì)應(yīng)的POS與NUM向量值如下：i1 2 3 4 5POS1 3 4 6 6NUM2 1 2 0 1構(gòu)造POS與NUM向量的算法如下：設(shè)B為稀疏矩陣的三元組，POS和NUM為該三元組的兩個(gè)輔助向量，m為稀疏矩陣的行號(hào)，tu為稀疏矩陣非零元素的個(gè)數(shù)，試寫出構(gòu)造POS與NUM向量的程序算法。POSNUM（B,tu,m,POS,NUM）/B為稀疏矩陣的三元組/1.for p=1 to m NUM(p)0 /初始化NUM向量/2.for p=1 to tu NUMBp.iNUMBp.i+1 /I為B中的行下標(biāo)/2. POS113. for p=2 to m POS(p)POS(p-1)+NUM(p-1)4. return有了POS與NUM向量后，可以高效地訪問稀疏矩陣中的任一非零元素。設(shè)對(duì)應(yīng)某稀疏矩陣的三元組為B，其中數(shù)據(jù)項(xiàng)i為行下標(biāo)，j為列下標(biāo)，v為元素值，則訪問稀疏矩陣中x行y列元素的算法為：hhhh5寫出下面稀疏矩陣的三元組表示的數(shù)組以及兩個(gè)輔助向量POS和NUM。ssssss13 ,tttttt5設(shè)對(duì)應(yīng)某稀疏矩陣的三元組為B，其中數(shù)據(jù)項(xiàng)i為行下標(biāo)，j為列下標(biāo)，v為元素值，兩個(gè)輔助向量為POS和NUM，完成下面訪問稀疏矩陣中x行y列元素的程序算法。SRPN(x,y,B,POS,NUM,s)1.s01. kPOS(x)2. while (kPOS(x)+NUM(x) and s=0 do 3. if (Bk.j=y)then sBk.v4. kk+15. end (while)6. return如果希望提高以三元組表示的稀疏矩陣轉(zhuǎn)置運(yùn)算的效率，則需增設(shè)兩個(gè)列輔助向量NUN和POT：POT1=1POTj= POTj-1+NUNj-1 (2jm)POT(i)表示稀疏矩陣中第i列的第一個(gè)非零元素在三元組中的行號(hào)；NUN(i)表示稀疏矩陣中第i列的非零元素個(gè)數(shù)。稀疏矩陣B對(duì)應(yīng)的POT與NUN向量值如下：i1 2 3 4 5POT1 3 4 5 6NUN2 1 1 1 1ssssss14 ,tttttt6稀疏矩陣轉(zhuǎn)置的算法如下：TRANSMATP(A,B)1.IF tu0 then2.for col=1 to n NUNcol0/初始化NUN向量/3for t=1 to tu NUNAt.jNUNAt.j+1 /求矩陣中每一列非零元素個(gè)數(shù)放入NUN中/4.POT115.for col=2 to n POTcolPOTcol-1+NUNcol-1 /求第col列中第一非零元素在A中序號(hào)/6.for p=1 to tu7.colAp.j;qPOTcol8.Bq.iAp.j;Bq.jAp.i9.Bq.vAp.v; POTcolPOTcol+110.end(p)11.returnPOTcol同時(shí)起到一個(gè)中間變量的作用，算出當(dāng)前A矩陣的三元組轉(zhuǎn)換成B矩陣三元組的位置。ssssss15完成下面統(tǒng)計(jì)二叉樹中的葉子結(jié)點(diǎn)數(shù)的程序算法。COUNTLEFT(p,count) /p指向根結(jié)點(diǎn),count為計(jì)數(shù)器，初值為01.if (pnil) then2.if (L child(p)=nil) and (R child=nil) 如果左葉子節(jié)點(diǎn)和右葉子節(jié)點(diǎn)都為空,3. then countcount +1則葉子節(jié)點(diǎn)數(shù)+14. COUNTLEFT(L,child(p); 繼續(xù)遞歸查找左右子節(jié)點(diǎn)5. COUNTLEFT(R,child(p);6.return(count)ssssss16 ,tttttt7INSERBET(t,b) / 將數(shù)值b插入根結(jié)點(diǎn)指針為t的二叉排序樹中,此函數(shù)返回值為指向根結(jié)點(diǎn)t的指針/1.if (t=nil) then /生成一個(gè)新結(jié)點(diǎn),其數(shù)值域?yàn)閎/2. GETNODE(t); data(t)b;L child(t)nil;R child(t)nil3.else if (bdata(t) then4. L child(t)INSERTBET(L child(t),b)/插入左子樹/5. else 6. R child(t)INSERTBET(R child(t),b) /插入右子樹/7.return(t)ssssss17 ,tttttt8刪除二叉排序樹上的結(jié)點(diǎn)算法如下：DELNODE(t,p,f)/t為根結(jié)點(diǎn)指針,p指向被刪除結(jié)點(diǎn),f指向其雙親,當(dāng)p=t時(shí) f=nil/1.fag0/fag=0需要修改F結(jié)點(diǎn)指針,fag=1不需修改/2.if (L child(p)=nil) then sR child(p)/p為葉子或左子樹為空/ s為所要替代p的子樹3.else if (R child(p)=nil) then sL child(p) /p的右子樹為空/4.else qp;sL child(p) /p的左右子樹均非空/5. while (R child(s)nil) do /s的右子樹為空 6. qs;sR child(s)/尋找s結(jié)點(diǎn)/7. if (q=p) then L child(q)L child(s) /q的左子樹為代替s的子樹8 else R child(q)L child(s) /q的右子樹為代替s的子樹9. data(p)data(s) /s值代替p值/10. RET(s); fag1 /釋放s結(jié)點(diǎn)/11.if (fag=0) then /修改F結(jié)點(diǎn)指針/12 if (f=nil) then ts /被刪除結(jié)點(diǎn)為根結(jié)點(diǎn)/13.else if (L child(f)=p) then L child(f)s14. else R child(f)s15. RET(p) /釋放結(jié)點(diǎn)p/16.returnssssss18 ,tttttt9,hhhh6date:存放結(jié)點(diǎn)權(quán)值L child:左指針R child:右指針Prnt:雙親指針?biāo)惴ㄈ缦拢?HUFFMAN(n,L child,R child,data,Prnt,w)/w1:n存放n個(gè)權(quán)值, L child1:m,R child1:m,data1:m, Prnt1:m,m=2n-1/1.for i=1 to n2. dataiwi;L child(i)0; R child(i)0 /初始化/3.end(i)4.for i=1 to (2*n-1) Prnti0/初始化/5.end(i)6for k=n+1 to (2*n-1)7. SELECT(k-1,i,j)/從data1:k-1中選出雙親為零的兩個(gè)權(quán)值最小的下標(biāo)i,j/ 8. datakdatai+datej 兩個(gè)權(quán)值最小相加生成一個(gè)新節(jié)點(diǎn)9. L childki; R childkj; 左子樹為i 右子樹為j10. Prntik; Prntjk; 雙親節(jié)點(diǎn)為k11.end(k)12.return對(duì)應(yīng)圖2.46中哈夫曼樹的存儲(chǔ)空間的初始狀態(tài)為圖2.47(a)，最終狀態(tài)為圖2.47(b)。,hhhh7寫出下面兩圖所示的鄰接矩陣和鄰接表圖的遍歷ssssss19 ,tttttt10,hhhh8深度優(yōu)先搜索DFS1(A,n,v) /A1:n,1:n為鄰接矩陣，v為起始頂點(diǎn)/1.VISIT(v) /訪問頂點(diǎn)v/2. VISITEDvtrue /置頂點(diǎn)已被訪問標(biāo)志/3.for j=1 to n4. if (Av,j=1) and (not VISTEDj) 和頂點(diǎn)連接的點(diǎn) 沒有被訪問5. then DFS1 (A,n,j)則繼續(xù)遞歸向下訪問6.end(j)7.returnssssss20,tttttt11,hhhh9廣度優(yōu)先搜索1.VISIT(v);VISITEDvtrue;/訪問起始頂點(diǎn)v/2.frontn-1;rear0 /隊(duì)列指針初始化/3.CQrearv /起始點(diǎn)入隊(duì)/4.while (rearfront) do /隊(duì)不空時(shí)/5.front(front+1) mod n; vCQfront; /訪問過的頂點(diǎn)出隊(duì)/6.pADJLISTv.firarc /p指向第1個(gè)鄰接點(diǎn)/7. while (pnil) do 8. if not VISITEDadjvex(p) /adjvex為表結(jié)點(diǎn)的鄰接域/9. then VISIT(adjvex(p);VISITEDadjvex(p)true;10. rear(rear+1) mod n; CQrearadjvex(p)11. pnextarc(p) /找下一個(gè)鄰接點(diǎn)/12. end(while)13.end(while) 14.return圖的應(yīng)用ssssss21,tttttt12,hhhh10單源最短路徑 12345610501045201550103200154200355300630SHORTPATH(AS,DIST,PATH,n,v0)1.for I=1 to n2. DISTiASv0,i3. if DISTiMAX then PATHiv04.end(i)5. S v0; /S為已找到最短路徑的終點(diǎn)集合/6.for k=1 to (n-1)7. wmMAX;uv08. for i=1 to n9. if (not I in S) and (DISTiwm)10. thenui; wmDISTi11. end(i) /在DISTi中找最小值/12. SS+u; /u為已找到最短路徑的終點(diǎn)/13. for I=1 to n14. if (not I in S) and (DISTu+ASu,iDISTi)15. then DISTiDISTu+ASu,i;16. PATHiu17. end(i) /調(diào)整S集之外各點(diǎn)最短路徑/18.end(k)19.for I=1 to n /輸出結(jié)果/20. if (i in S) then21. ki;22. while kv0 do WRITE (k,); kPATHk;23. WRITE(v0); WRITE(DISTi);/輸出v0到vi最短路徑/24. else25. WRITE(no path);WRITE(max); /v0到vi無路徑/26.end(i)27.return最后輸出PATH與DIST結(jié)果為132 352 032 15432 3052 106 nopath maxssssss22,tttttt13,hhhh11拓?fù)渑判騎OPOSORT(ADJST,n) /ADJST為鄰接向量/1.top0;m0 /top置初態(tài),m指示輸出頂點(diǎn)個(gè)數(shù)/2.for k=1 to n / 建立入度為零頂點(diǎn)鏈棧/3. if ADJSTk.indegree=0）4. then ADJSTk.indegreetop; topk5.end(k)6.while (top0) do7.itop; topADJSTtop.indegree /刪除入度為零頂點(diǎn)i/8.write(i); mm+1 /輸出頂點(diǎn)i,m 計(jì)數(shù)/9.pADJSTi.firarc10. while(pnil) do 11.jadjvex(p); ADJSTj.indegreeADJSTj.indegreee-112. /以頂點(diǎn)vi為尾的弧頭的入度減1/13. if(ADJSTj.indegree=014. then ADJSTj.indegreetop;topj15. /將新的入度為零的頂點(diǎn)入棧/16. pnextarc(p) / 找下一條弧/17. end(while)18.end(while)19. if mn /輸出頂點(diǎn)數(shù)不足n個(gè)/20.then 此圖有回路 return21.return查找對(duì)分查找Ssssss23,hhhh12對(duì)分查找算法如下：BINSERRCH(r,n,K)1.low1;highn /上下界指示器賦初值/2.while (lowrmid.key: lowmid+17.Krmid.key: highmid-18.end(case)9.end(while)10. returnssssss24二叉排序樹查找BSTSEA