【正文】 ，不穩(wěn)定的方法是（ ） (A)直接插入排序 (B)冒泡排序 (C)歸并排序　(D)直接選擇排序 。( )（A）要排序的數(shù)據(jù)量太大??? （B）要排序的數(shù)據(jù)中含有多個相同值 （C）要排序的數(shù)據(jù)已基本有序（D）要排序的數(shù)據(jù)個數(shù)為奇數(shù) ,希望盡快挑選出其中前10個最大值元素,在不改變已有算法結構的前提下,以下幾種內排序算法中(?? ?)最合適。 （A）選擇排序（B）希爾排序（C）歸并排序（D）快速排序 ,平均查找長度最小的是（ ） （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 ,要求內存量最大的是（ ）。 （A）38,40,46,56,79,84（B）40,38,46,79,56,84（C）40,38,46,56,79,84（D）40,38,46,84,56,79(25,48,16,35,79,82,23,40,36,72),其中含有5個長度為2的有序表,按歸并排序的方法對該序列進行一趟歸并后的結果為（ ）。 （A）起泡排序（B）快速排序（C）堆排序（D）基數(shù)排序 ,效率最高的排序方法是（ ） （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 (46,79,56,38,40,84),則利用堆排序的方法建立的初始推為（ ）。}return(hash)。 p=pnext。qnext=pnext。amp。p=hash[t]next。else { found=0。if ( hash[t]= = null) return (infeasible)。 六、算法設計 哈希表的刪除 參考答案：一、判斷題 √二、填空題 (n+1)/2；((n+1)*log2(n+1))/n1；(s2+2s+n)/2s；log2(n/s+1)+s/2；1+α 哈希表查找 順序；有序的 索引；塊 15 小于表長的最大素數(shù) ①1 ②2 ③4 ④8 ⑤5 ⑥ ①O(n) ② O(log2n) 10 三、選擇題 1. B 3. C 4. D 5. B 8. B 六、算法設計 哈希表的刪除 hashtable del_hashtable (hashtable amp。 (D)鏈接表 (4)查找、插入和刪除速度慢,但順序存取和隨機存取第i個元素速度快。 (B)順序有序表 (2）查找、插入和刪除速度快,但不能進行順序存取。 。設計出這種鏈表結構,并求該表平均查找長度。 （A）分塊（B）順序（C）二分（D）散列 四、問答題 (38,25,74,63,52,48),假定采用H(k)=k%7計算散列地址進行散列存儲,試分別求出利用線性探測的開放定址法處理沖突和利用鏈接法處理沖突,在該散列表上進行查找的平均查找長度。 （A）8（B）3（C）5（D）9,按二分查找法對該表進行查找,在表內各元素等概率情況下查找成功所需的平均比較次數(shù)為（? ） （A）35/12（B）37/12（C）39/12（D）43/12,若線性表中共有625個元素,查找每個元素的概率相同,假設采用順序查找來確定結點所在的塊時,每塊應分（ ）個結點最佳。 （A）1（B）2（C）4（D）8=14,哈希函數(shù)H(key)=key%11。 （A）以順序方式存儲（B）以鏈接方式存儲 （C）以順序方式存儲,且結點按關鍵字有序排序 （D）以鏈接方式存儲,且結點按關鍵字有序排序 ,每個元素的平均查找長度為（ ） （A）n （B）n/2（C）(n+1)/2（D）(n1)/2,每個元素的平均查找長度為（ ） （A）O(n2)（B）O(log2n)（C）O(n)（D）O(log2n)（ ）。 三、選擇題 （ ）的線性表。 ,若進行順序查找,則時間復雜度為__________，若采用二分法查找,則時間復雜度為_________。 (key)=key%p中,p應取_______________。 ,首先查找__________,然后再查找相應的___________。( )二、填空題 ，二分查找法的平均查找長度為________，分塊查找法(以順序查找確定塊)的平均查找長度為__________，分塊查找法(以二分查找確定塊〉的平均查找長度為_________，哈希表查找法采用鏈接法處理沖突時的平均查找長度為_________。（ ） ，就越不容易發(fā)生沖突。（ ） 。 (若存在)，分析算法的時間復雜度。 。//vj入隊 }//endofwhile}//BFS ，分別寫出基于DFS和BFS遍歷的算法來判別頂點vi和vj(ij)之間是否有路徑。p=pnext)//依次搜索vi的鄰接點vj(不妨設padjvex=j)if(!visited[padjvex])//若vj沒有訪問過 EnQueue(amp。//訪問vifor(p=Gadjlist[i].firstedge。//vi出隊 visited[i]=TRUE。Q)){i=DeQueue(amp。Q,k)。Q)。若這個連通圖有n個頂點, 則它的生成樹有________條邊。 ，則圖的廣度優(yōu)先搜索類似于二叉樹的________遍歷。 4. 如果從一個頂點出發(fā)又回到該頂點，則此路徑叫做_______。 ，若存在一條從頂點i到頂點j的弧，則在頂點的拓撲序列中，頂點i與頂點j的先后次序是_________________。 （A）先序遍歷（B）中序遍歷（C）后序遍歷（D）按層遍歷 ,還可以利用（ ）.（A）求關鍵路徑的方法（B）求最短路徑的Dijkstm方法 （C）寬度優(yōu)先遍歷算法（D）深度優(yōu)先遍歷算法 ，在算法執(zhí)行的某刻，已選取的頂點集合U＝{1，2，5}，邊的集合TE＝{（1，2），（2，5）}，要選取下一條權值最小的邊，應當從（ ）組中選取。 ①（A）n （B）n+1（C）n1（D）n+e②（A）e/2（B）e（C）2e （D）n+e（ ）。 （A）5（B）6（C）7（D）8,要連通全部頂點至少需要（ ）條邊。 （A）n （B）n(n1)（C）n(n1）/2（D）2n（ ）條邊。 （A）1/2（B）1（C）2（D）4,所有頂點的入度之和等于所有頂點的出度之和的（ ）倍。（ ） 。（ ） 。else return(0)。) break。a[i]!=39。if(flagamp。\039。amp。i100。change(t,1)。change(trchild,2*i+1)。 //數(shù)組順序存儲二叉樹void change(NODE *t,int i) //將二叉樹的鏈接存儲轉換為順序存儲 {if(t!=NULL) {a[i]=tdata。like2)。return(like1amp。else{like1=like(t1lchild,t2lchild)。amp。amp。t2==NULL) return(1)。if(t1==t2amp。 }return num。 }p=s[top]。s[++top]=p。amp。amp。 //top為棧頂指針p=root。}}int onechild3(NODE *root) //非遞歸統(tǒng)計出二叉樹共有多少個度為1的結點{ NODE *p,*s[100]。if(num1num2)return(num1+1)。else{num1=depth(tlchild )。amp。if(t==NULL) return(0)。if(plchild!=NULL)q[tail++]=plchild。printf(%c,pdata)。tail=1。q[0]=T。 }}void lev_traverse(NODE *T) //按層次從上到下,每層從右到左的順序列出二叉樹所有結點的數(shù)據(jù)信息{NODE *q[100],*p。 q=p。 p=plchild。}s[++top]=p。 free(p)。pdata==k){if(qlchild==p) qlchild=NULL。prchild==NULL amp。while((p!=NULL)||(top0)){ while(p!=NULL){if(plchild==NULLamp。}p=*root。(*root)data==k) {*root=NULL。(*root)rchild==NULLamp。if((*root)lchild==NULL amp。 //q為p的雙親結點int top=0。 p=prchild。 p=plchild。while((p!=NULL)||(top0)){ while(p!=NULL){printf(%d ,pdata)。 //top為棧頂指針p=root。}void preorder1(NODE *root) //非遞歸二叉樹前序編歷{ NODE *p,*s[100],*q。trchild==NULL) return(leaf(tlchild)+leaf(trchild)+1)。else if(tlchild==NULLamp。else return(sum(tlchild)+sum(trchild)+1)。return(num1+num2)。else{num1=onechild(tlchild)。amp。amp。if(t==NULL) return(0)。count1(prchild,num1)。amp。amp。}}void count1(NODE *p,int *num1){if(p!=NULL){count1(plchild,num1)。prchild!=NULL)num++。prchild==NULL||plchild==NULLamp。if(plchild!=NULLamp。??? }? }int num=0。?? printf(%c ,pdata)。((*T)rchild))。((*T)lchild))。(*T)data=ch。) *T=NULL。if(ch==39。void create(NODE **T) //創(chuàng)建二叉樹{ char ch。}NODE。}二叉樹其他運算的算法（只作參考） include include typedef struct node{char data。parent(a,n,i)。scanf(%d,amp。input(a,n)。scanf(%d,amp。}main(){int a[MAX],n,i。 /*自身不輸出 */if(2*p=n)queue[tail++]=2*p。while(fronttail){p=queue[front++]。 /* 隊列作為輔助，存儲孩子的序號*/queue[0]=i。}Elseprintf(雙親:%d\n,a[(i1)/2])。所以 n0+n1=k*n1+1n0=(k1)*n1+1五、算法設計void parent(int a[],int n,int i){if(i==1) {printf(無雙親 \n)。 4 n+1 DGEBHJIFCA ABDEGCEH①無左子樹②無右子樹③僅一個結點的二叉樹 最大n,最小┕log2n┙+1 22 99四、問答題 1.答：（1）mk1 （2）（mh1）/（m1） （3）i=1時，該結點為根，無雙親結點；否則其雙親結點的編號為（i+m2）/m（4）編號為i的結點的第j個孩子結點(若有)的編號為i*m+（j（m1））2.證明：設樹結點為n, 則n=n0+n1因是滿k叉樹, 每個非葉子結點引 出k個分支，故有k*n1個分支。 參考答案：一、選擇題1. B 3. A 4. B 5. B A D B C 1A 1C 1A 1C 1D 1C 17 C 二、判斷題 1 2 3√ 4√三、填空題①樹的結點個數(shù)至少為1，而二叉樹的結點個數(shù)可以為0；②樹種結點的最大讀書沒有限制，而二叉樹結點的最大度數(shù)不能超過2；③樹的結點無左右之分，而二叉樹的結點有左右之分。(4)并譯出編碼系列1100011100010101的相應電文。(2)求出每個字符的晗夫曼編碼。,b,c,d,e,其出現(xiàn)頻率依次為4,7,5,2,9。(3)畫出在BT中刪除(23〉后的二叉樹。：一個滿k叉樹上的葉子結點數(shù)n0和非葉子結點數(shù)n1之間滿足以下關系： n0=（k1）n1+1(50,28,78,65,23,36,13,42,71）,請完成以下操作:(1)畫出按元素排列順序逐點插入所生成的二叉排序樹BT。(3)編號為i的結點的雙親結點的編號。若按層次從上到下,每層從左到右的順序從1開始對全部結點編號,試計算:(1)第k層結點數(shù)(1≤k≤h)。__________________________，可能達到的最大深度和最小深度各是多少？____________________，這些結點的度要么是0，要么是2。_________________________2）后序和中序遍歷，得到的結點訪問順序一樣。,中序序列為BFDGAEHC ,并寫出前序序列_________________。,樹與二叉樹是兩種不同的數(shù)據(jù)結構,將樹轉化為二叉樹的基本目的是____________(包括A本身),并且B是A的雙親結點,B的度是_______________,那么該二叉樹所有結點共有_______個空指