【正文】 14 15 19 20 21 22 56（2分）（3）、（3分）(5分，)ijv1352463374134215218558 初始關(guān)鍵字： [18] 12 25 53 18 第 一 趟：[12 18] 25 53 18第 二 趟：[12 18 25] 53 18第 三 趟：[12 18 25 53] 18第 四 趟：[12 18 18 25 53] （4分） O（n2）（1分）。L,ElemType x){ int i,j。iLlength。 if(i=Llength) return ERROR。jLlengthi1。 Llength。S,Elemtype amp。 。}（10分）voidCountLeaves(BinTree T,int amp。amp。 CountLeaves (Tlchild,n)。}}習(xí)題1一、單項選擇題1. 數(shù)據(jù)結(jié)構(gòu)是指（ ）。 3. 樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（ ）。for(i=1。 i++)for(j=i。 j++)x++。（1） （2） 6. 計算機算法指的是（1），它具備輸入，輸出和（2）等五個特性。 8. 數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程出現(xiàn)是在（ ）年。 ，后半句錯 ，后半句對10. 計算機內(nèi)部數(shù)據(jù)處理的基本單位是（ ）。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是________________、__________________、__________________和__________________。4. 一個算法的效率可分為__________________效率和__________________效率。6. 在圖型結(jié)構(gòu)中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以__________________。8. 下面程序段的時間復(fù)雜度是__________________。in。jn。9. 下面程序段的時間復(fù)雜度是__________________。while(sn){ i++。}10. 下面程序段的時間復(fù)雜度是__________________。for(i=0。i++)for(j=0。j++)s+=B[i][j]。11. 下面程序段的時間復(fù)雜度是__________________。while(i=n)i=i*3。13. 算法時間復(fù)雜度的分析通常有兩種方法，即___________和___________的方法，通常我們對算法求時間復(fù)雜度時，采用后一種方法。1. x=0。in。j=n。2. x=0。in。j=ni。3. int i,j,k。in。j=n。for(k=0。k++) c[i][j]=a[i][k]*b[k][j]}4. i=n1。amp。return (i)。 elsereturn (n*fact(n1))。13. 事后統(tǒng)計，事前估計三、算法設(shè)計題 1. O( ) 2. O( ) 3. O(n ) 4. O(n) 5. O(n) 習(xí)題2一、單項選擇題1. 線性表是________。A．ni B．ni+l C．ni1 D．i3. 線性表采用鏈?zhǔn)酱鎯r，其地址________。A．n/2 B．n C．（n+1）/2 D．（n1）/2 5. 在雙向循環(huán)鏈表中，在p所指的結(jié)點之后插入s指針?biāo)傅慕Y(jié)點，其操作是____。 sprior=p。 snext=pnext。 snext=pnext。 pnextprior=s。 pnextprior=s。 snext=pnext。 snext=pnext。 pnext=s。A．pnext=pnextnext。C．p=pnextnext。 7. 在一個長度為n的順序表中向第i個元素(0 in+l )之前插入一個新元素時，需向后移動______個元素。 pnext=sB．qnext=s。 snext=pD．pnext=s。 A．線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。C．線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。10. 線性表的順序存儲結(jié)構(gòu)是一種_______的存儲結(jié)構(gòu)。A．基地址 B．結(jié)點大小 C．向量大小 D．基地址和結(jié)點大小12. 在等概率情況下，順序表的插入操作要移動______結(jié)點。 A．插入 B．刪除 C．根據(jù)序號查找 D．根據(jù)元素值查找14. 在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并保持該表有序的時間復(fù)雜度是_______。A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A 16. 在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時，top變化為______。A．hsnext=s。 hs=s。hsnext=s。 hs=hsnext。A．rear％n= = front B．（front+l）％n= = rearC．rear％n 1= = front D．(rear+l)％n= = front 19. 在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為________。A．front=frontnext 　 B．rear=rearnextC．rear=frontnext 　D．front=rearnext二、填空題1. 線性表是一種典型的_________結(jié)構(gòu)。3. 順序表中邏輯上相鄰的元素的物理位置________。5. 在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過_______決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過_______決定的。7. 當(dāng)對一個線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時，則采用_______存儲結(jié)構(gòu)為宜。8. 順序表中邏輯上相鄰的元素，物理位置_______相鄰，單鏈表中邏輯上相鄰的元素，物理位置_______相鄰。10. 根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表可分為_________和_______；而根據(jù)指針的聯(lián)接方式，鏈表又可分為________和_________。12. 對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一個新結(jié)點的時間復(fù)雜度為______，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為_______。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的_______分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)_______時才產(chǎn)生上溢。15. 無論對于順序存儲還是鏈?zhǔn)酱鎯Φ臈：完犃衼碚f，進(jìn)行插入或刪除運算的時間復(fù)雜度均相同為__________。2. 線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點？3. 對于線性表的兩種存儲結(jié)構(gòu)，如果有n個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變，在此情況下，應(yīng)選用哪一種存儲結(jié)構(gòu)？為什么？4. 對于線性表的兩種存儲結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。7. 什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。if(Lamp。Lnext){ q=L。 p=L。　　 pnext=q。　　}　　return (L)。2. 在單鏈表上實現(xiàn)線性表的求表長ListLength(L)運算。4. 假設(shè)有一個帶表頭結(jié)點的鏈表，表頭指針為head，每個結(jié)點含三個域：data, next和prior。現(xiàn)在所有結(jié)點已經(jīng)由next域連接起來，試編一個算法，利用prior域（此域初值為NULL）把所有結(jié)點按照其值從小到大的順序鏈接起來。試編寫一個刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法。設(shè)計一個刪除表中所有值小于max但大于min的元素的算法。8. 設(shè)順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。若鏈表中附設(shè)頭結(jié)點，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。線性表的順序存儲結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，因而降低效率：而在鏈接存儲結(jié)構(gòu)中內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點的插入、刪除操作較簡單。4．應(yīng)選用順序存儲結(jié)構(gòu)，因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。5．設(shè)尾指針比設(shè)頭指針好。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。當(dāng)有元素要加入隊列（即入隊）時，若rear=maxnum，則會發(fā)生隊列的上溢現(xiàn)象，此時就不能將該元素加入隊列。 一般地，要解決隊列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費存儲空間。每當(dāng)有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。 第三種：采用循環(huán)隊列方式。8．該算法的功能是：將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。算法描述如下：delete(LinkList *q,int i){ //在無頭結(jié)點的單鏈表中刪除第i個結(jié)點 LinkList *p,*s。 if(i0) printf(Can39。 else if(i= =0) { s=q。 free(s)。 s=q。amp。 s=snext。}if (s= =NULL) printf(Cant39。 else { pnext=snext。 } }}2．由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點個數(shù)了?！?ListList *p?！?while ( pnext!=NULL ){ p=pnext?！?}　 return (len)。逆置時需將每一個結(jié)點的指針域作以修改，使其原前趨結(jié)點成為后繼。操作即可，算法描述如下：void invert(LinkList *head){ //逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist *p, *q, *s。 p=headnext。 q=p。 qnext=s。 }4．定義類型LinkList如下：typedef struct node{ int data。}LinkList。算法描述如下：insert (LinkList *head){ LinkList *p,*s,*q。 //p指向待插入的結(jié)點，初始時指向第一個結(jié)點 while(p!=NULL) { s=head。 //q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點 while((q!=NULL) amp。 (pdataqdata)) //查找插入結(jié)點p的合適的插入位置{ s=q。 } sprior=p。 //結(jié)點p插入到結(jié)點s和結(jié)點q之間 p=pnext。 if (head!=NULL) { q=head。 while((p!=NULL) amp。 (pdata=min)) { q=p。}while((p!=NULL) amp。 (pdatamax)) p=pnext?！}6．算法描述如下：delete(LinkList *head, int max, int min){ LinkList *p,*q。 p=headnext。 p=pnext。free(p)。} }7．本題是對一個循環(huán)鏈隊列做插入和刪除運算，假設(shè)不需要保留被刪結(jié)點的值和不需要回收結(jié)點，算法描述如下：（1）插入（即入隊）算法：insert(LinkList *rear, elemtype x){ //設(shè)循環(huán)鏈隊列的隊尾指針為rear,x為待插入的元素 LinkList *p。if(rear= =NULL) //如為空隊，建立循環(huán)鏈隊列的第一個結(jié)點{ rear=p。 //鏈接成循環(huán)鏈表}else //否則在隊尾插入p結(jié)點 { pnext=rearnext。 rear=p。if(rear