【正文】 次輸出S中數(shù)據(jù)即可。 p:=bt。 WHILE NOT empty(s) DO [ WHILE NOT empty(s) AND (p^.datax) DO [ push(s,p)。 write(p^.data) ] ELSE {需要到右分枝去查x結(jié)點(diǎn)} [q:=nil。 {rend是為了在右分枝不空時(shí)就退出循環(huán)} WHILE NOT empty(s) AND rend DO [p:=pop(s)。p:=p^.rchild。第七章 圖1． 1． 圖的定義，概念、術(shù)語(yǔ)及基本操作。3． 3． 圖的遍歷。1 1 基本概念中，連通分量，生成樹(shù)，鄰接點(diǎn)是重點(diǎn)。這兩種存儲(chǔ)結(jié)構(gòu)對(duì)有向圖和無(wú)向圖均適用。鄰接多重表是無(wú)向圖鄰接表的改進(jìn)，將邊結(jié)點(diǎn)的數(shù)量減少一半（正好等于邊的數(shù)量）。4 4 在（強(qiáng)）連通圖中，主過(guò)程一次調(diào)用深（寬）度優(yōu)先遍歷過(guò)程（dfs/bfs），即可遍歷完全部頂點(diǎn)，故可以用此方法求出連通分量的個(gè)數(shù)，并能畫(huà)出遍歷中形成的深（寬）度優(yōu)先生成樹(shù)。 應(yīng)熟練掌握prim和kruscal算法，特別是手工分步模擬生成樹(shù)的生成過(guò)程。關(guān)鍵路經(jīng)是在拓?fù)溆行虻那疤嵯虑蟪鰜?lái)的，從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑。理解“減少關(guān)鍵活動(dòng)時(shí)間能縮短工期”，是指該活動(dòng)為所有關(guān)鍵路徑所共有，且減少到尚未改變關(guān)鍵路經(jīng)的前提下才有效。用鄰接多重表實(shí)現(xiàn)圖的各種運(yùn)算。這在圖的操作中，要比其他的存儲(chǔ)結(jié)構(gòu)要復(fù)雜的多。｛g 為教材中已定義的adjmulist類(lèi)型變量，本算法建立有n個(gè)結(jié)點(diǎn)e 條邊的圖的存儲(chǔ)結(jié)構(gòu)｝FOR I := 1 TO n DO 【read (g[i].data。 ｛讀兩結(jié)點(diǎn)｝i:=loc_vertex(g,vi)。 p^.ivex:=i。p^.ilink:=g[i].firstedge。｝】ENDP。否則，本算法應(yīng)添加查詢(xún)功能（即下面search過(guò)程）。FUNC search(g:adjmulist。｛本算法在圖g中查詢(xún)頂點(diǎn)vi，vj間的邊結(jié)點(diǎn)是否已建立。 found:=false WHILE (pNIL) AND NOT found DO IF p^.ivex=i {結(jié)點(diǎn)中ivel，jvex 域均可能為i} THEN IF p^.jvex=j THEN found := true ELSE p:=p^.ilink ｛順ilink下找 ｝ ELSE IF p^.ivex=j ｛p^.jvex=i｝ THEN found :=true ELSE p:=p^.jlink ｛順jlink下找｝。 {search}PROC insert_edge (VAR g:adjmulist。 ｛本算法在鄰接多重表中插入 邊（vi，vj）｝i:=loc_vertex(g,vi)。fp:=search(g , i , j )。 p^.ivex:=i。 p^.ilink:=g[i].firstedge。 p^.jlink:=g[j].firstedge。 】ENDP。PROC insert_vertex ( VAR g:adjmulist。｛本算法在鄰接多重表中插入頂點(diǎn)V。 g[m+1].firstedge:=nil。 {insert_vertex} vi,vj:vtxptr)。j:=loc_vertex(g,vj)。IF fp nil THEN 【 p:=g[i].firstedge。{修改i的鏈表邊結(jié)點(diǎn)(vi,vj)的前驅(qū)的指針} WHILE p fp DO 【q:=p。 p:=g[j].firstedge。 {修改j的鏈表邊結(jié)點(diǎn)(vi,vj)的前驅(qū)的指針} ｛從vj的邊結(jié)點(diǎn)鏈表中找到（vi，vj）邊，修改前驅(qū)指針，算法同上，故略｝ dispose(fp)。 v:vtxptr)。 p:=g[i].firstedge。 IF i=p^.ivex THEN delete_edge (g:,v,g[p^.jvex].data) ELSE delete_edge (g:,v,g[p^.ivex].data) p:=s 】ENDP。 編寫(xiě)對(duì)圖的深度優(yōu)先非遞歸遍歷算法。 v0:vtxptr)。在圖g 中進(jìn)行深度優(yōu)先遍歷。｝initstack(s)。 visited[v0]:=true。WHILE (pnil) AND NOT empty(s) DO【W(wǎng)HILE pnil DO IF visited[p^.adjvex] THEN p:=p^.nextarc ELSE 【 write ( p^.adjvex)。 visited [p^.adjvex]:=true。 】IF NOT empty (s)THEN 【p:=pop(s)。 】ENDP。一、內(nèi)容提要 動(dòng)態(tài)存儲(chǔ)管理指的是在用戶(hù)需要時(shí)給分配內(nèi)存，而在用戶(hù)結(jié)束使用時(shí)，系統(tǒng)要收回 用戶(hù)所占空間。 可利用空間表的三種結(jié)構(gòu)形式：結(jié)點(diǎn)固定大?。环謳追N規(guī)格；任意大小。 可利用空間表的兩種組織形式：目錄表，鏈表。 可利用空間表的分配方式：首次擬合法，最佳擬合法，最差擬合法。 可利用空間表的分配和回收的兩種基本實(shí)現(xiàn)方法：邊界標(biāo)識(shí)法，伙伴系統(tǒng)。 無(wú)用單元回收和緊縮存儲(chǔ)的概念。二、學(xué)習(xí)重點(diǎn)邊界表示法的分配及回收算法。設(shè)有大小為512字節(jié)的存儲(chǔ)，有6個(gè)用戶(hù)申請(qǐng)大小分別為23，45，52，100，11和19字節(jié)的存儲(chǔ)空間，然后再順序釋放大小為45，52 和 11的占用空間。1． 1．2． 2．3． 3．【解答】1． 1．因無(wú)25空閑塊，故原先29塊分裂為22225各一塊，首址依次為256，128，64，32。 （2）45〈=26=64，故將26空閑塊（64—127）給了該用戶(hù)，其首址為64。 （4）100〈=27=128，因無(wú)27空閑塊，28塊產(chǎn)生分裂，其中首址256（256—383）的一半分給用戶(hù)，其伙伴（首址384）掛到27空閑塊鏈表中。（6）19〈=32=25。 總之，6個(gè)用戶(hù)占用塊首址依次為0，64，128，256，32和192，這時(shí)可利用空間表的狀態(tài)為： 2526^2728^29^│ 0 │ 5 │ │ 0 │ 7 │ 回收（1） （1） 45〈=26=64，其首址為64，因64 MOD 26+1=26，所以其伙伴地址為6464=0（不空）其伙伴占用，故僅將此結(jié)點(diǎn)掛到26空閑塊鏈表中。（3） （3） 11〈=24=16，首址32因32 MOD 24+1=0，伙伴地址32+24=48（空閑），故合并成25（塊）。20^21^22^23^24^25│ 0 │ 6 │ 首地址64│ 0 │ 5│ 首地址224內(nèi)容提要 本章介紹的查找表是稱(chēng)為集合的數(shù)據(jù)結(jié)構(gòu)。 查找表的操作：查找，檢索，插入，刪除，成員關(guān)系判斷。 動(dòng)態(tài)查找表：二叉排序樹(shù)，平衡二叉樹(shù)，B樹(shù)，B+樹(shù)，鍵樹(shù)。查找表是稱(chēng)為集合的數(shù)據(jù)結(jié)構(gòu)。本章列舉了三種方法（靜態(tài)查找表，動(dòng)態(tài)查找表，哈希表）實(shí)現(xiàn)查找表的運(yùn) 算。有序表的平均查找長(zhǎng)度不超過(guò)樹(shù)的深度，其判定樹(shù)是唯一的。二叉排序樹(shù)的形態(tài)取決于元素的輸入順序。 沖突是不可避免的。 哈希表中關(guān)鍵字的查找只能用哈希函數(shù)來(lái)計(jì)算，不能順序、折半查找。 1．設(shè)二叉排序樹(shù)中元素均為整數(shù)，試編寫(xiě)算法從大到小輸出各元素值。 【算法】 PROC bstoutput (bst:bitreptr)； {bst是二叉排序樹(shù)根結(jié)點(diǎn)指針，本算法從大到小輸出二叉排序樹(shù)的各結(jié)點(diǎn)的值} IF bstNIL THEN [ bstoutput (bst↑.rchild)。 ]； ENDP；{bstoutput} 【討論】課本中討論了二叉樹(shù)的三種遞歸遍歷算法,另三種并非沒(méi)用。本題另一種解法是在中序遍歷　　　二叉排序樹(shù) ，訪(fǎng)問(wèn)根結(jié)點(diǎn)時(shí)將結(jié)點(diǎn)值進(jìn)棧保存，遍歷結(jié)束后依次彈出棧中元素，直至?？?，所得結(jié)果亦符合要求，但多用了一個(gè)棧，不如這里所采用的算法簡(jiǎn)單。 2． 編寫(xiě)在二叉排序樹(shù)上插入結(jié)點(diǎn)s的算法。 【算法】 PROC insert (VAR bst: bitreptr。 {本算法在二叉排序樹(shù)bst 上插入結(jié)點(diǎn)s} IF bst =NIL THEN bst:=s ELSE IF s↑.data THEN insert (bst↑.lchild,s) ELSE insert (bst↑.rchild,s)。 {insert}【討論】 這是最簡(jiǎn)潔的遞歸算法。 3．編寫(xiě)在索引順序表中查找數(shù)據(jù)k的算法。現(xiàn)設(shè)一索引表，其結(jié)構(gòu)如下：TYPE idxtb1=RECORD key: keytype。 END。記錄中三個(gè)域：key為索引所指塊中最大關(guān)鍵字，low和high指該塊中最低下標(biāo)值和最高下標(biāo)值?！舅惴ā縁UNC indxblk( r:seqlisttp: idx:index。 {本算法在索引順序表r中，查找其關(guān)鍵字值為待查元素值k的元素。high:=b；{在索引表中折半查找其值 =k的最小元素} found:=false。 CASE r[mid].key=k： low:=mid。 r[mid].keyk:：high:=mid1。 ENDC；{若查找失敗low值即為所求} IF lowb THEN low:=b。 {取待查塊在r中的最低和最高下標(biāo)} h:=idx(low).high。 WHILE (r[i].keyk) AND (i=h) DO i:=i+1。ENDF；{indxblk}請(qǐng)給出此表的一個(gè)哈希表設(shè)計(jì)方案。 【分析】（1） 根據(jù)平均查找長(zhǎng)度不超過(guò)3，確定裝填因子α； snl≈1/2(1+(1/(1α))){使用線(xiàn)性探測(cè)再散列解決沖突} 因snl=3,取α=.（2） 根據(jù)α確定表長(zhǎng) 由α=（表中添入的記錄數(shù)）/（哈希表的長(zhǎng)度） 所以 哈希表的長(zhǎng)度=100/α=125 取表長(zhǎng)=150；（3） 選取哈希函數(shù) H(key)=key MOD 149 (4) key 的選取方法。每個(gè)人的姓名取四個(gè)字　　　母（兩字姓名取首尾兩個(gè)字母，三字姓名取各字拼音第一個(gè)字母，中間字取首尾兩　　　個(gè)拼音字母）。要求姓名　　　的第一個(gè)拼音字母要大寫(xiě)，如姓名39。拼音為39。取出四個(gè)拼音字母　　　為39。,個(gè)字母序號(hào)依次為 23 38 35 39，組成關(guān)鍵字為 2338+3539=5877，該姓　　　名的哈希地址為 5877 MOD 149=66。 內(nèi)部排序一、內(nèi)容提要排序的定義，排序可以看作是線(xiàn)性表的一種操作排序的分類(lèi)，穩(wěn)定排序與不穩(wěn)定排序的定義。交換排序（冒泡排序、快速排序）。歸并排序、基數(shù)排序。二、學(xué)習(xí)要點(diǎn)2． 2．在“最好”和“最差”情況下，排序性能的分析，是否是穩(wěn)定排序的結(jié)論。從減少比較次數(shù)和移動(dòng)次數(shù)進(jìn)行了各種改進(jìn)，產(chǎn)生了折半、二路、表插入、希爾等一系列插入排序。冒泡排序和快速排序是交換排序的例子，快速排序是目前最快的內(nèi)部排序法。5． 5．簡(jiǎn)單選擇排序、樹(shù)形選擇排序、堆排序是選擇排序的例子。7． 7．對(duì)每種排序方法的學(xué)習(xí)，應(yīng)掌握其本質(zhì)（排序所基于的思想），并能舉一反三。二、例題解析　　　【分析】 將該記錄作樞軸，進(jìn)行一趟快速排序，則可將該記錄放在其排序后應(yīng)在的位置上。j:integer)。 i:=1。 rp:=r[i]。 WHILE ik DO [ WHILE (ik) AND (r[k].key≥x) DO k:=k1。i:=i+1 ]。 IF ik THEN [ r[k]:=r[i]。 ENDP。即，若將n個(gè)記錄排序后，該元素是第j個(gè)記錄。 PROC Quicksort_J(VAR r:Listype。 {求記錄序列r[1..n]中排序后第j個(gè)的記錄rp。 t: