【正文】 ，若 [i]=e,則找到該元素，并返回i+1，若找不到，則返回“1” ，請(qǐng)?zhí)羁胀晟浦?。int Locate(SeqList L，int e){ i=0 。 /*i為掃描計(jì)數(shù)器，初值為0，即從第一個(gè)元素開(kāi)始比較*/ while ((i=)amp。amp。([i]!=e) ) i++。 /*順序掃描表，直到找到值為key的元素,或掃描到表尾而沒(méi)找到*/ if ( i= ) return(i+1)。 /*若找到值為e的元素，則返回其序號(hào)*/ else return(1)。 /*若沒(méi)找到，則返回空序號(hào)*/ }(240) 下列算法在順序表L中第i個(gè)數(shù)據(jù)元素之前插入一個(gè)元素e。 插入前表長(zhǎng)n=Llast+1，i的合法取值范圍是 1≤i≤Llast+2，請(qǐng)?zhí)羁胀晟浦oid InsList(SeqList *L, int i, int e){ int k。if((i1) || (iLlast+2)) printf(“插入位置i值不合法”)； if(Llast=maxsize1) printf(“表已滿無(wú)法插入”)；for(k=Llast。k=i1。k) /*為插入元素而移動(dòng)位置*/ Lelem[k+1]=Lelem[k] 。 Lelem[i1]=e 。 /*在C語(yǔ)言數(shù)組中，第i個(gè)元素的下標(biāo)為i1*/ Llast++ 。 }(241) 下列算法是在順序表L中刪除第i個(gè)數(shù)據(jù)元素，并用指針參數(shù)e返回其值。i的合法取值為1≤i≤+1，請(qǐng)?zhí)羁胀晟浦?。int DelList(SeqList *L, int i, int *e){ int k。if((i1)||(i Llast+1 )) printf(“刪除位置不合法！”)； *e= Lelem[i1] 。 /* 將刪除的元素存放到e所指向的變量中*/for(k=i。i=Llast。k++) Lelem[k1]= Lelem[k] 。 /*將后面的元素依次前移*/ Llast 。}四、解答題(242) 假設(shè)以數(shù)組seqn［m］存放循環(huán)隊(duì)列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和元素的個(gè)數(shù)?！　?1) 寫(xiě)出隊(duì)滿的條件表達(dá)式；　　(2) 寫(xiě)出隊(duì)空的條件表達(dá)式；　　(3) 設(shè)m=40,rear=13,quelen=19,求隊(duì)頭元素的位置；　　(4) 寫(xiě)出一般情況下隊(duì)頭元素位置的表達(dá)式?！　?1) quelen == m(2) quelen == 0(3) ( 13 19 + 40 ) % 40 = 34(4) ( rear quelen + m ) % m(243) 已知一棵二叉樹(shù)的中序序列為ABCDEFG，層序序列為BAFEGCD，請(qǐng)畫(huà)出該二叉樹(shù)?！? B / \ A F / \ E G / C \ D(244) 已知一棵二叉樹(shù)的前序序列為ABCDEFGH，中序序列為CBEDFAGH，請(qǐng)畫(huà)出該二叉樹(shù)。 A / \ B G / \ \ C D H / \ E FABECFHDG(245) 已知一棵二叉樹(shù)如圖所示。請(qǐng)分別寫(xiě)出按前序、中序、后序和層次遍歷是得到的頂點(diǎn)序列。前序：A,B,D,G,C,E,F,H中序：D,G,B,A,E,C,H,F后序：G,D,B,E,H,F,C,A層次：A,B,C,D,E,F,G,H(246) 已知一棵二叉樹(shù)的前序序列為：A,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H, A,C,K,I,L,F。(1) 寫(xiě)出該二叉樹(shù)的后序序列；(2) 畫(huà)出該二叉樹(shù)；(3) 求該二叉樹(shù)的高度(假定空樹(shù)的高度為－1)和度為度為及度為0的結(jié)點(diǎn)個(gè)數(shù)。該二叉樹(shù)的后序序列為：J,G,D,H,E,B,K,L,I,F,C,A。該二叉樹(shù)的形式如圖所示：ABJKIFCGEDLH該二叉樹(shù)高度為：5。度為2的結(jié)點(diǎn)的個(gè)數(shù)為：3。度為1的結(jié)點(diǎn)的個(gè)數(shù)為：5。度為0的結(jié)點(diǎn)個(gè)數(shù)為：4。(247) 有一份電文中共使用 6個(gè)字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構(gòu)造一棵哈夫曼樹(shù)，并求其加權(quán)路徑長(zhǎng)度WPL，字符c的編碼。WPL＝80 字符c：001（不唯一）(4) 下圖是帶權(quán)的有向圖G的鄰接表表示法。從結(jié)點(diǎn)V1出發(fā)，求出：a) 深度遍歷圖G；b) G的一個(gè)拓?fù)湫蛄?；c) 從結(jié)點(diǎn)V1到結(jié)點(diǎn)V8的最短路徑。題29圖2635011128433811212624V1V3V4V6V71V2V8V5參考答案：v1,v2,v3,v8,v4,v5,v7,v6 (2分) v1,v2,v4,v6,v5,v3,v7,v8 (2分)V1到結(jié)點(diǎn)V8的最短路徑為：v1,v2,v3,v8 (2分) (248) 已知如圖所示的有向圖，請(qǐng)給出該圖的：（1） 每個(gè)頂點(diǎn)的入度、出度；（2） 鄰接矩陣；（3） 鄰接表；V1V3V4V6V71V2V8V5(249) 對(duì)下面的有向圖，從頂點(diǎn)V1開(kāi)始進(jìn)行遍歷，試畫(huà)出遍歷得到的DFS生成森林和BFS生成森林。圖全對(duì)給4分，錯(cuò)一個(gè)頂點(diǎn)扣1分，扣完為止。遍歷得到的DFS生成森林和BFS生成森林如下圖：V1V3V4V6V7V2V8V5DFS生成森林V1V3V4V6V7V2V8V5BFS生成森林(250) 采用哈希函數(shù)Ｈ(k)=3*k mod 13并用線性探測(cè)開(kāi)放地址法處理沖突，在數(shù)列地址空間［0..12］中對(duì)關(guān)鍵字序列22,41,53,46,30,13,1,67,51（1）構(gòu)造哈希表（畫(huà)示意圖）；（2）裝填因子；等概率下（3）成功的和（4）不成功的平均查找長(zhǎng)度1）散列地址0123456789101112關(guān)鍵字13225314167465130比較次數(shù)111212111（2）裝填因子=9/13= （3）ASLsucc =11/9 （4）ASLunsucc =29/13(251) 設(shè)有一組關(guān)鍵字{9,01,23,14,55,20,84,27}，采用哈希函數(shù)：H（key）=key mod 7 ，表長(zhǎng)為10，用開(kāi)放地址法的二次探測(cè)再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,…,)解決沖突。要求：對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長(zhǎng)度。散列地址0123456789關(guān)鍵字140192384275520比較次數(shù)1112 3 412平均查找長(zhǎng)度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以關(guān)鍵字27為例：H（27）=27%7=6（沖突） H1=（6+1）%10=7（沖突） H2=（6+22）%10=0（沖突） H3=（6+33）%10=5 所以比較了4次。(252) 對(duì)于給定的一組記錄的關(guān)鍵字{ 23,13,17,21,30,60,58,28,30,90},試分別寫(xiě)出冒泡排序、快速排序、堆排序、歸并排序第一趟排序后的結(jié)果。冒泡排序13,23,17,21,28,30,60,58,30*, 90快速排序：(21,13,17,) 13,( 30,60,58,28,30*,90 )堆排序： 13,21,17,23,30,60,58,28,30*,90,歸并排序按層遍歷：(13 23) (17 21 ) (30 60 ) ( 28 58 ) (30* 90) (253) 采用哈希函數(shù)Ｈ(k)=2*k mod 13并用鏈地址法處理沖突，在數(shù)列地址空間［0..12］中對(duì)關(guān)鍵字序列22,41,53,46,30,13,1,67,51進(jìn)行下列工作：（a）構(gòu)造哈希表（畫(huà)示意圖）；（b）等概率下成功的和不成功的平均查找長(zhǎng)度。參考答案：鏈地址表全對(duì)給8分。錯(cuò)一個(gè)結(jié)點(diǎn)扣1分，扣完為止。0→13^1→46^2→53→1^3^4→41→67^5→22^6^7^8→30^9^10^11→51^12^ASLsucc=(7+4)/13=11/9（1分） ASLunsucc=(5+4)/13=9/13（1分）　　四、算法設(shè)計(jì)題(10分)(254) 閱讀下列遞歸算法，寫(xiě)出非遞歸方法實(shí)現(xiàn)相同功能的C程序。void test(int amp。sum) { int x； scanf(x)； if(x=0) sum=0 else {test(sum)。 sum+=x。} printf(sum)； }＃include (1分)void main() (1分){ int x,sum=0,top=0,s[]。 (1分) scanf(“%d”,amp。x) while (x0) { s[++top]:=a。 scanf(“%d”,amp。x)。 }(3分) while (top) sum+=s[top]。 (3分)printf(“%d”,sum)。 (1分) }(255) 試寫(xiě)出把圖的鄰接矩陣表示轉(zhuǎn)換為鄰接表表示的算法。設(shè)圖的鄰接矩陣為g[n][n]（針對(duì)無(wú)向圖），定義鄰接表節(jié)點(diǎn)的類型為struct edgenode { int adjvex。 edgenode next。}typedef edgenode *adjlist[n]。void matritolist (int g[][], adjlist gl, int n ){ edgenode *p, *q。 for (int i=0 in。 i++) gl[i]=null。 for (int i=0。 in。 i++)for ( int j=0。 jn。 j++) { if (g[i][j]!=0 ) p = ( edgenode *) malloc(sizeof (edgenode))。 padjvex=j。 pnext=null。 if (gl[i]=null) { gl[i]==p。