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