—二三四一.單項選擇題（共12分）請將所選項的編號填入各題左邊的括號【B組成數(shù)據(jù)的基本單位數(shù)據(jù) [B]數(shù)據(jù)元 [C]數(shù)據(jù)類[D]據(jù)變【A采用鏈式結構便于實現(xiàn)對線性表插 [B]遍 [C]查[D]【A3.循環(huán)隊列用數(shù)組A[0..m-1]存放元素其頭尾指針分別為frontrear，[A](rear–front+m)% [B][C] [D](rear–front)%【=（a，b，c（d，e，f，[A] [B][C]tail(head(tail(head(A))))[D]【C5.有2000結點的二叉樹，其高度至少[A] [B] [C] [D]D6.鄰接矩陣A，第i點的入A[A]第i行非∞元素個 [B]第i列非∞元素個[C]第i行非∞且非0元素個 【B7.一個長度為12有序表進行等概率的折半查找，查找成功所需的關鍵[A] [B] [C] [D]【C8.果對下列順序表分別作快速排序，所需比較次數(shù)最少的[A] [B][C] [D]12 和基本 循環(huán)鏈表的主要優(yōu)點 從表中任一結點出發(fā)均可找到表中其他結 兩個串相等的充分必要條件 字符依次對應相同且長度相同_？？12.設有一個10階的對稱矩陣A，以行為主序其下三角中的元素，A的第一個元素a11的地址為1，每個元素占用1個單元，則a85的地址為 。13.前序和中序序列相同的二叉樹的特征 各結點均無左孩子_？？14.具有n個頂點的強連通圖至少有 15.外排序是 在排序過程中需要外 的排序方法16.直接存取文件是用雜湊 方法組織的（3617（5分）請直接在以下二叉樹中添加后序線索EEDBCKAF18.（10分）已知一個長度為12的表設哈希表長度為13，哈希函數(shù)H（k）=i/2，其中i為關鍵字k中第一個字母在4，19.（5分）假設電文中ah8個字母組成，字母在電文中出現(xiàn)的頻度依次，8個字母相應的哈夫曼編碼。20.（8分）若對序列（25，19，7，41，29，12，23，26）按升序排序，請分別給步長為4的一趟希爾排序的結果初始大根堆52 21.（8分）對于右邊的帶權圖52 畫出G的鄰接矩陣畫出G的最小生成樹（4022（6分）函數(shù)f22定義如下，其中函數(shù)調用Insert(L,i,k)在順序表L的第位置插入kvoidf22(SqList&L,inti){if(i>0){f22(L,i-for(intk=1;k<=i;k++)Insert(L,i,k);}}設有空順序表L＝（，請寫出調用遞歸函數(shù)f22(L,3)L的長度L＝（1，2，3， 23.（6分）算法f23(L)將結點的單鏈表L逆置。請在畫線處填空voidf23(LinkList&L){LinkListp=L->next;L->next=NULL while(p){LinkLists=P— p->next=L->next;L->next=p;p=}}24.OK（6分）s是一個升序靜態(tài)查找表，請簡要說明函數(shù)調用f24(s,1,s.length,k)的意義。intf24(SSTables,intlow,inthigh,KeyTypek){if(low>high)return0;intif(k==s.elem[mid].key)returnif(k>s.elem[mid].key)returnf24(s,mid+1,high,k);elsereturnf24(s,low,mid-1,k);}答：在s中遞歸折半查找25（6分）請對以下函數(shù)填空，實現(xiàn)求二叉樹T中各結點的子孫總數(shù)，并填入結點um域中的算法intf25(BiTreeT)if(!T )return-1;else{ um=f25(T->lchild)+ returnT- }}26（6分）圖的鄰接矩陣表示和算法f26描述如下#defineMaxNum5typedefstruct{charintarcs[MaxNum][MaxNum];intn,e;}intf26(MGraphG,inti){intd=0;for(intj=0;j<G.n;j++){if(G.arcs[i][j])d++;if(G.arcs[j][i])}return}已知一個圖G的鄰接矩陣如下所示 0 0G.arcs= 1 0 027（10后寫出算法的C語言描述。voidpurge(LListL){LLists,q,p=L->next;while(p){q=while(q-if(q->next->data!=p->data)q=q->next;{s=q->next;q->next