1、1 .將下列愛(ài)雜度由小到大重新排序：D . 10 000 E . /?*log2(n)B . 6*log2(n) + 9nD . 5n2 + n3/2C ： O (/I4)D ： O Q?2)A.2B.nlC.Il5【答】10000</?*log2(n)<n5<2vn2 .將下列更雜度由小到大重新排序：A./7*10g2(7l)B.+J?+戶(hù)【答】24<?i05<n*log2(/1)<n+n2+n33 .用大“O”表示法描述下列復(fù)雜度:A.5.5/2+m5C.3/?4+/*log：(/?)【答】A：O(52)B:O()4 .按照增長(zhǎng)率從低到高的順序排列以下表

2、達(dá)式：4112,log3n,3n,20n,2000,log2n,n2/3o又n!應(yīng)排在第幾位？【答】按照增長(zhǎng)率從低到高依次為：2000,log3/7,log：/，產(chǎn)3,20，4n2,3"。！的增長(zhǎng)率比它們中的每一個(gè)都要大，應(yīng)排在最后一位。5 .計(jì)算下列程序片斷的時(shí)間代價(jià)：inti-1;while(i<-n)()【答】循環(huán)控制變量1從1增加到n,循環(huán)體執(zhí)行n次，第一句i的初始化執(zhí)行次數(shù)為1,第二句執(zhí)行n次，循環(huán)體中第一句pnntf執(zhí)行n次，第二句i從1循環(huán)到n,共執(zhí)行n次。所以該程序段總的時(shí)間代價(jià)為：T(n)=1+2n=3+1=。()6 .計(jì)算下列程序片斷的時(shí)間代價(jià)：inti-1

3、;while(i<-n)(while(j<-n)wlule(k<-n)pdntfGi-%d,j-%d.k-%duT,Lj,k);k*l;J-J+l;i-i+1;)【答】循環(huán)控制變量i從1增加到n,最外層循環(huán)體執(zhí)行n次，循環(huán)控制變量j從1增加到n,中間層循環(huán)體執(zhí)行n次，循環(huán)控制變量k從1增加到n,最內(nèi)層循環(huán)體執(zhí)行n次，所以該程序段總的時(shí)間代價(jià)為：T(n)=1+1+nl+n+2n+1+1+1)+1=33+3標(biāo)+4+2=。?3)精選范本2.線(xiàn)性表L試寫(xiě)一個(gè)插入算法mtinsertPost_seq(palist,p,x),在palist所指順序表中，卜標(biāo)為p的元素之后，插入一個(gè)值為x

4、的元素，返回插入成功與否的標(biāo)志。【答】數(shù)據(jù)結(jié)構(gòu)采用2.1.2節(jié)中順序表定義。mtinseitPost_seq(PseqListpalist,mtp.Datalypex)/*在palist所指順序表中下標(biāo)為p的元素之后插入元素x*/mtq;/*溢出*/if(palist->n>-palist-MAXNUM)pnntff'Oveiflow!n)return0;if (p<0 | p>palist->n-l) /*不存在下標(biāo)為p的元素/pnntfC'Notexist!n”)；renirn0:_foi(q-palist->n-1;q"p十1

5、;q-)/*插入位置及之后的元素均后移一個(gè)位置*/palist->elementq+l-palist->elementq;palist->elementp+l - x;palist->n - palist->n + 1;/*插入元素x /*元素個(gè)數(shù)加1return1;2試寫(xiě)一個(gè)刪除算法deleteV_seq(palist,x),在palist所指順序表中，刪除一個(gè)值為x的元素，返回刪除成功與否的標(biāo)志。【答】數(shù)據(jù)結(jié)構(gòu)采用2.1.2節(jié)中順序表定義。mtdeleteV_seq(PseqListpalist.p,DataTypex)/*在palist所指順序表中刪除值為x

6、的元素*/mtpqfor(p-0;pn;pH)/查找值為x的元素的下標(biāo)率/if(x-palist->elementp)for(q-p:q<pahst->n-l;q+)/*被刪除元素之后的元素均前移一個(gè)位置*/palist->elementq-palist->elementq+1;/*元素個(gè)數(shù)減1，palist->n-palist->n-1;renun1;return0;3 .設(shè)有一線(xiàn)性表e=(%,ei,e?,，ed),其逆線(xiàn)性表定義為e，=仁吐1,e2,ei,e0)o請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，將用順序表表示的線(xiàn)性表置逆，要求逆線(xiàn)性表仍占用原線(xiàn)性表的空間。【答】數(shù)

7、據(jù)結(jié)構(gòu)采用2.1.2節(jié)中)11酹表的定義。思路考慮對(duì)數(shù)組element進(jìn)行置逆，即把第一個(gè)元素和最后一個(gè)元素?fù)Q位置，把第二個(gè)元素和倒數(shù)第二個(gè)元素?fù)Q位置。它注意這種調(diào)換的工作只需對(duì)數(shù)組的前一半元素進(jìn)行，所以設(shè)置整數(shù)變量count用于存放數(shù)組長(zhǎng)度的一半的值。大家可以考慮一下：為什么不能對(duì)整個(gè)數(shù)組進(jìn)行如上的對(duì)元素"換位置”的工作？(提示：這樣會(huì)將本來(lái)已經(jīng)置逆的線(xiàn)性表又置逆回來(lái)，即又變成了原來(lái)的表。)順序表的置逆算法voidrev_seq(PSeqListpalist)DataTypex:intcount,i;if(palist->n0|palist->n1)return:/空表

8、或只有一個(gè)元素，直接返回本/count-palist->n/2;for(1-0:1<count;i+)只需調(diào)換半個(gè)表的元素亭/x-palist->elementi;palist->elementi一palist->elementpalist->n一1一口；palist->elementpalist->n-1-i-x:)代價(jià)分析該算法中包含一個(gè)f。循環(huán),其循環(huán)次數(shù)為n/2o因此，算法的時(shí)間代價(jià)為。4 .已知長(zhǎng)度為n的線(xiàn)性表A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫(xiě)一算法，找出該線(xiàn)性表中值最小的數(shù)據(jù)元素。【答】數(shù)據(jù)結(jié)構(gòu)采用2.1.2節(jié)中順序表定義。思路設(shè)置變量nun,

9、遍歷整個(gè)表，不斷更新當(dāng)前已經(jīng)經(jīng)歷過(guò)的元素的最小值即可。為方便起見(jiàn)，事先假設(shè)表不為空。算法DataType min_seq(PSeqList palist)DataType nmi;mt i;min - palist->elementO;fbi (i - 1; i< palist->n; ifif (nun > palist->elementi) min - palist->elementi;return nun:八求非空順序表中的最小數(shù)據(jù)元素*/八初始化nmi*/Onm中保存的總是當(dāng)前的最小數(shù)據(jù)可代價(jià)分析該算法訪(fǎng)問(wèn)順序表中每個(gè)元素各一次，時(shí)間代價(jià)為。()。科

10、討論讀者可以試圖對(duì)上面的算法進(jìn)行修改，使返回的值不是最小元素的值而是它的下標(biāo)。5 .已知線(xiàn)性表A的長(zhǎng)度為n,并且采用順序存儲(chǔ)結(jié)構(gòu)。寫(xiě)一算法，刪除線(xiàn)性表中所有值為x的元素。【答】數(shù)據(jù)結(jié)構(gòu)采用2.1.2節(jié)中順序表的定義。思路為了減少移動(dòng)次數(shù)，可以采用快速檢索的思想，用兩個(gè)變量"記錄順序表中被處理的兩端元素的下標(biāo)，開(kāi)始時(shí)i=O.j=n-l,邊檢索第i個(gè)元素邊增加i,直到找到一個(gè)元素值等于x,再邊檢索第J個(gè)元素邊減少J,直到找到一個(gè)元素值不等于,把下標(biāo)為，的元素移到下標(biāo)為i的位置后重復(fù)上述過(guò)程，直至IJi>jo另用一變量count記錄刪除了多少個(gè)元素。算法voiddelx_seq(PS

11、eqListp、DataTypex)/率刪除順序表中所有值為、的元素，新順序表可能不保持原有順序*/mti-0j-p->n-1,count-0;八，定位于順序表開(kāi)始處,，定位于順序表最后力while(i<j)if(p->elementi一x)尸找到了一個(gè)要?jiǎng)h除的元素while(p->elementj-x)&&(i!-j)/*從后往前找不會(huì)被刪除的元素.當(dāng)LJ相等時(shí)退出循環(huán)，count記錄從后往前找的過(guò)程中遇到了多少個(gè)要?jiǎng)h的元素*/coun;p->n-p->n-count-1;return;elsep->elementi-p->el

12、ementj：count+;j-；ifp->n-p->n-count;if(p->elementi-x)p->n;)代價(jià)分析該算法訪(fǎng)問(wèn)順序表中每個(gè)元素各一次，時(shí)間代價(jià)為。()。#討論這個(gè)算法使用了一點(diǎn)技巧使得在中間刪除元素時(shí)，避免了最后一串元素的移動(dòng)。但是，它破壞了原來(lái)線(xiàn)性表中元素之間的順序關(guān)系。如果需要保持原來(lái)的順序應(yīng)該怎樣做？這里提供一種可行的思路：從前向后遍歷表,如果元素不是X,則繼續(xù)向后；如果元素是X,則尋找其后第一個(gè)不是X的元素，將這兩個(gè)元素互換。具體算法請(qǐng)讀者自己實(shí)現(xiàn)。6.寫(xiě)一算法，在帶頭結(jié)點(diǎn)的單鏈表Ihst中，p所指結(jié)點(diǎn)前面插入值為x的新結(jié)點(diǎn)，并返回插入成

13、功與否的標(biāo)志。【答】數(shù)據(jù)結(jié)構(gòu)采用2.1.3節(jié)中單鏈表定義。思想：由于在單鏈表中，只有指向后繼結(jié)點(diǎn)的指針，所以只有首先找到p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后才能完成插入。而找p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，只能從單鏈表的第一個(gè)結(jié)點(diǎn)開(kāi)始，使用與locatejuik類(lèi)似的方式進(jìn)行搜索。算法：mtinseitPre_lmk(LmkListllist,PNodep,DataTypex)產(chǎn)在ihst帶頭結(jié)點(diǎn)的單鏈表中，P所指結(jié)點(diǎn)前面插入值為x的新結(jié)點(diǎn)*/PNodepl;if(llist-NULL)return0:pl-Hist;while(pl!-NULL&&pl>hnk!-p)pl-pl->l

14、ink;/率尋找p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)*/if(pl-NULL)return0;PNodeq-(PNode)malloc(sizeof(sunctNode);/率申請(qǐng)新結(jié)點(diǎn)if(q-NULL)prmtfC,Outofspace?return0;q->mfb-x;q->lnik-pl->lmk;pl->luik-q;renun1;7,寫(xiě)一算法，在帶頭結(jié)點(diǎn)的單鏈表Hist中，刪除p所指的結(jié)點(diǎn)，并返回刪除成功與否的標(biāo)志O【答】數(shù)據(jù)結(jié)構(gòu)采用2.1.3節(jié)中單鏈表定義。思想：由于在單鏈表中，只有指向后繼結(jié)點(diǎn)的指針，所以只有首先找到p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后才能完成刪除。而找p所指結(jié)點(diǎn)

15、的前驅(qū)結(jié)點(diǎn)，只能從單鏈表的第一個(gè)結(jié)點(diǎn)開(kāi)始，使用與locatejuik類(lèi)似的方式進(jìn)行搜索。mtdeletePJink(LinkListllist,PNodep)/*在Uist帚頭結(jié)點(diǎn)的單鏈表中，刪除p所指的結(jié)點(diǎn)*/PNodepl;if(llist-NULL)renirnNull;pl-Hist;while(p1!-NULL&&p1->hiik?-p)p1-pl->lnik;/*尋找p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)率/if(p1-NULL)retuin0;pl->link-p->liiik;free(p);/*刪除結(jié)點(diǎn)p*/return1;)8.已知list是指向無(wú)頭結(jié)

16、點(diǎn)的單鏈表的指針變量，寫(xiě)出刪除該鏈表下標(biāo)為1的(第1+1個(gè))結(jié)點(diǎn)的算法。【答】數(shù)據(jù)結(jié)構(gòu)采用2.1.3節(jié)中單鏈表定義。思路依次遍歷表中的每一個(gè)結(jié)點(diǎn)并計(jì)數(shù)，到第i+1個(gè)結(jié)點(diǎn)時(shí)實(shí)行刪除。由于鏈表是無(wú)頭結(jié)點(diǎn)的，所以在刪除第一個(gè)結(jié)點(diǎn)時(shí)要特別注意。算法mtdeletenidexJiiik_nohead(LmkList*pllist.mti)/*刪除單鏈表中下標(biāo)為i的結(jié)點(diǎn)。刪除成功返回TRUE,否則返回FALSE。*/intj;PNodep、q:if(*pllist)-NULL|i<0)returnFALSE;if(i-0)嚴(yán)如果需要?jiǎng)h除第一個(gè)結(jié)點(diǎn)本/一(*pllist)->link;free(

17、q);returnTRUE;p-(*pllist);j-O；wlule(p->lmk!-NULL1)片尋找下標(biāo)為的結(jié)點(diǎn)的地址，p-p->link;j+;if(p->link-NULL)returnFALSE;/*此元素不存在*/q-p->link;p->lnik-q->link;free(q);leturnTRUE;)代價(jià)分析該算法訪(fǎng)問(wèn)單鏈表中前面i個(gè)結(jié)點(diǎn)，時(shí)間代價(jià)為。，最大不超過(guò)。()。#討論如果函數(shù)參數(shù)不是LnikList*類(lèi)型而是LnikList類(lèi)型，在刪除/=0的結(jié)點(diǎn)時(shí)，程序不能正確實(shí)現(xiàn)，其原因請(qǐng)讀者思考(考慮C語(yǔ)言的參數(shù)傳遞方式X如果單鏈表帶表頭結(jié)

18、點(diǎn)，重寫(xiě)本題的算法。比較這兩個(gè)算法，是否能體會(huì)到表頭結(jié)點(diǎn)的作用。9.已知list是指向無(wú)頭結(jié)點(diǎn)的單鏈表的指針變量，寫(xiě)出刪除該鏈表中從下標(biāo)為1的(第計(jì)1個(gè))結(jié)點(diǎn)開(kāi)始的連續(xù)k個(gè)結(jié)點(diǎn)的算法。【答】數(shù)據(jù)結(jié)構(gòu)采用2.1.3節(jié)單鏈表定義。思路這道題與上題相似，只需要增加計(jì)數(shù)即可。要注意的是應(yīng)該判斷給出的i和k是否合理，是不是會(huì)超出鏈表長(zhǎng)度。算法intdel_link_nohead(LHikList*i.mtk)刪除單鏈表中從下標(biāo)i開(kāi)始的k個(gè)結(jié)點(diǎn)。刪除成功返回TRUE,否則返回FALSE。*/intj;PNodep、q:if(*plhst)NULL|i<0'k<-0)r

19、eturnFALSE;產(chǎn)如果需要?jiǎng)h除從第一個(gè)結(jié)點(diǎn)開(kāi)始的k個(gè)結(jié)點(diǎn)*/for(j-0;j<k&&(*pllist)!-NULL;j+)q-(*pllist);(*pllist)-(*pllist)->lmk;free(q);leturnTRUE;p-j-O；wlule(p->link!-NULL&&j<i-l)嚴(yán)尋找下標(biāo)為/-I的結(jié)點(diǎn)的地址寫(xiě)p-p->link;jfif(p->linkNULL)returnFALSE;產(chǎn)第i個(gè)結(jié)點(diǎn)不存在Vfor(j-0:j<k&&p->liiik!-NULL;j+)q-

20、p->link;p->lnik-q->link;free(q);returnTRUE;)代價(jià)分析該算法訪(fǎng)問(wèn)單鏈表中前面i+k個(gè)結(jié)點(diǎn)，時(shí)間代價(jià)為。(海),最大不超過(guò)。13.請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，求出循環(huán)表中結(jié)點(diǎn)的個(gè)數(shù)。【答】數(shù)據(jù)結(jié)構(gòu)采用不帶頭結(jié)點(diǎn)的循環(huán)鏈表。structNode;typedefstructNode*PNode;structNodeDataTypeinfb;PNodelink;typedefstructNode*LinkList;思路遍歷整個(gè)循環(huán)鏈表，同時(shí)計(jì)數(shù)即可。¥錯(cuò)誤算法mtcount(LinkListclist)intcount;PNodep、q:p-c

21、list;q-p->link;if(cHst-NULL)return0:/如果是空表率/count-1;while(q!-p)q-q->liiik:counts;returncount;)錯(cuò)誤：如果clist是一個(gè)空表，那么第5行的語(yǔ)句"q=p-Xink;"是非法的。分析：應(yīng)把第6行語(yǔ)句(用下劃線(xiàn)表示)提前1行或2行。一定要放在語(yǔ)句"q=pAlmk;"之前。缺點(diǎn)：增加局部變量p。分析：這樣做沒(méi)有必要，因?yàn)閜的初值置為chst,在程序中并沒(méi)有對(duì)p做其他修改，所以程序中不需要引入P而直接使用clist即可。算法mtcount(LinkListcl

22、ist)mtcount;PNodeq;if(cHst-NULL)return0:/亭如果是空表率/q-clist->link;count-1;while(q!-clist)q-q->link;count十十；returncount:)代價(jià)分析該算法訪(fǎng)問(wèn)循環(huán)鏈表中每個(gè)結(jié)點(diǎn)各一次，時(shí)間代價(jià)為。()。4.棧與隊(duì)列1 .寫(xiě)一個(gè)遞歸算法來(lái)把整數(shù)字符串轉(zhuǎn)換為整數(shù)。(例：“43567”-43567o)【答】思路先遞歸調(diào)用本算法轉(zhuǎn)換除去末位夕陵U余的字符串，結(jié)果乘以10。再轉(zhuǎn)換末位。將兩結(jié)果相加即為所求。算法intsumgToIntl(char*s，intstart,mtend)/*把整數(shù)字符串5

23、中從start至!Jend的部分轉(zhuǎn)換為整數(shù)率/if(start>end)return-1;產(chǎn)轉(zhuǎn)換失敗if(start-end)renirnsend-10*;/*只有一個(gè)字符f直接轉(zhuǎn)換以returnstimgToIntl(s,start,end-1)*10+send-'O'/率先轉(zhuǎn)換其他位，再轉(zhuǎn)換末位率/)intsuingToInt(char*s)，率把整數(shù)字符串s轉(zhuǎn)換為整數(shù)率/inti-0:while(si!-i;/率計(jì)算字符串的長(zhǎng)度率/returnstimgToIntl(s,0,i-1);)代價(jià)分析設(shè)為字符串的長(zhǎng)度。該算法訪(fǎng)問(wèn)每個(gè)字符各一次，時(shí)間代價(jià)為。()，計(jì)算字符串

24、的長(zhǎng)度的時(shí)間代價(jià)也為。()。故總的時(shí)間代價(jià)為。()。遞歸算法需要棧的支持，棧的大小與遞歸調(diào)用的深度成正比。所以實(shí)際空間開(kāi)銷(xiāo)為。()。2 .編寫(xiě)一個(gè)算法，對(duì)于輸入的十進(jìn)制非負(fù)整數(shù)，將它的二進(jìn)制表示打印出來(lái)。【答】數(shù)據(jù)結(jié)構(gòu)采用4.1.2節(jié)中棧的順序表小。思路將輸入的十進(jìn)制數(shù)字反復(fù)除以2,直到它變?yōu)?。將每次的數(shù)字模2的余數(shù)入棧。棧中存放的就是所要求的二進(jìn)制表示。再將棧中的元素依次彈出打印即可。算法voiddec_numbei)產(chǎn)將十進(jìn)制非負(fù)整數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)打印出來(lái)7PSeqStackpastack;mttemp-dec_numbei:if(temp<0)printfC'EnodiT

25、);return;pastack-createEmptyStack_seq();產(chǎn)建立一個(gè)空棧if(pastack-NULL)reuirn;while(temp>0)push_seq(pastack,temp%2);tempI-2;wlule(!isEmpty,Stack_seq(pastack)top_seq(pastack);pop_seq(pastack);free(pastack);)代價(jià)分析設(shè)輸入的十進(jìn)制數(shù)字為，則算法的時(shí)間代價(jià)為O(log2n)0空間代價(jià)主要是棧的大小，為O(log2w)o3 .寫(xiě)一個(gè)算法：PSeqStackcreateEmptyStack_seq(mtm)創(chuàng)

26、建一個(gè)空棧。數(shù)據(jù)結(jié)構(gòu)采用4.1.2節(jié)中棧的II頁(yè)序表示。PSegStackcreateEmptyStack_seq(mtm)/*創(chuàng)建一個(gè)空棧*/PSeqStackpastack-(PSeqStack)malloc(sizeof(stnictSeqStack);if(pastack!-NULL)pastack->s-(DataType*)malloc(sizeof(DataType)*m);if(pastack->s)pastack->MAXNUM-m;pastack/棧頂變量賦值為-1率/return(pastack);)elsefreepastack;)printfC

27、9;Outofspace!/*存儲(chǔ)分配失敗*/returnNULL;4,寫(xiě)一個(gè)算法：intisEmptyStack_seq(PSeqStackpastack)判斷pastack所指的棧是否為空棧。數(shù)據(jù)結(jié)構(gòu)采用4.1.2節(jié)中棧的II頁(yè)序表示。mtisEmptyStack_seq(PSeqStackpastack)/*判斷pastack所指的棧定否為空棧*/iftpastack->t-1)renirn1;elsereturn0:8.假設(shè)以循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)隊(duì)頭指針)，試編寫(xiě)相應(yīng)的創(chuàng)建空隊(duì)列、入隊(duì)列和出隊(duì)列的算法。【答】數(shù)據(jù)結(jié)構(gòu)采用不帶頭結(jié)點(diǎn)的循環(huán)鏈表

28、表示隊(duì)列。structNode;typedefstructNode*PNode;structNodeDataTypemfb;PNodelink;structClmkQueue產(chǎn)循環(huán)鏈表表示的隊(duì)列類(lèi)型事/PNoder;/*尾指針*/)typedefstructClmkQueuePClu±Queue:/本指向循環(huán)鏈表表示的隊(duì)列的指針類(lèi)型*/rrr隊(duì)頭一*RdIt隊(duì)尾隊(duì)列的循環(huán)鏈表表示思路與隊(duì)列的單鏈表表示相似，但節(jié)省了指向隊(duì)頭的指針變量，所以在需要找表頭結(jié)點(diǎn)時(shí)必須通過(guò)表尾指針進(jìn)行。算法PChnkQueuecieateEmptyQueujclink()產(chǎn)創(chuàng)建空隊(duì)列*/PClmkQueuep

29、cqu-(PClmkQueue)inalloc(sizeof(sti-uctClmkQueue);pcqu->r-NULL;xeturnpcqu;進(jìn)隊(duì)列*/voidenQueue_clmk(PClinkQueuepcqu.DataTypex)PNode p;p 一 (PNode)malloc(sizeof(suiict Node); p->mfb - x;if (pcqu->r NULL) pcqu->r - p;p->lmk - p;retuni;)p->lnik - pcqu->r->link;pcqu->r->link - p;

30、pcqu->r - p:)void deQueue_clmk(PClmkQueue pcqu) PNode p;if (pcqu->r NULL) printf<MUndeiflow!1nH);return;if (pcqu->r->link - pcqu->r) free(pcqu->r);pcqu->r - NULL;return;p - pcqu->r->link;pcqu->r->link - p->link;free(p);產(chǎn)進(jìn)空隊(duì)列，即往空隊(duì)列中加入第一個(gè)結(jié)點(diǎn)*/外出隊(duì)列*/產(chǎn)是空隊(duì)列*/只有一個(gè)元素的隊(duì)

31、列*/產(chǎn)指向隊(duì)頭*/代價(jià)分析上述幾個(gè)算法都不包含循環(huán)，只有常數(shù)條語(yǔ)句，因此每個(gè)算法的時(shí)間代價(jià)均為0(1)。稱(chēng)討論本題可以看成隊(duì)列的循環(huán)表實(shí)現(xiàn)。5.二叉樹(shù)與樹(shù)1 .寫(xiě)一個(gè)算法來(lái)計(jì)算給定二叉樹(shù)的葉結(jié)點(diǎn)數(shù)。【答】數(shù)據(jù)結(jié)構(gòu)采用5.1.3節(jié)中二叉樹(shù)的鏈接表示。算法intnum_of_leaves(BmTreet)/字計(jì)算二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)率/if(t-NULL)remm0;產(chǎn)空樹(shù)，返回01if(t->llHik-NULL&&-NULL)return1;產(chǎn)根結(jié)點(diǎn)是樹(shù)葉，返回1本/leturnnum_of_leaves(t->llHik)+num_oflleaves(t->

32、rlink):產(chǎn)返回左子樹(shù)的葉結(jié)點(diǎn)數(shù)十右子樹(shù)的葉結(jié)點(diǎn)數(shù)"率/)代價(jià)分析該算法訪(fǎng)問(wèn)每個(gè)結(jié)點(diǎn)各一次，時(shí)間代價(jià)為。以空間代價(jià)為。(/九2 .假設(shè)二叉樹(shù)采用鏈接方法存儲(chǔ)，編寫(xiě)一個(gè)計(jì)算一棵二叉樹(shù)f的高度的函數(shù)。【答】數(shù)據(jù)結(jié)構(gòu)采用5.1.3節(jié)中二叉樹(shù)的鏈接表示。思路對(duì)一棵二叉樹(shù)/,考察它左右子樹(shù)的高度，取其中大的一個(gè)，再加1即為/的高度。算法mtdepth(BniTreet)(PBmTreeNodepbtree;intdLdr;pbtree-t;if(pbueeNULL)(return-1;dl-ckpth(pbtiee->Hmk);dr-depth(pbtiee->rlink);r

33、eturn(dl>dr?dl:dr)+1;)代價(jià)分析設(shè)樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)為，遞歸訪(fǎng)問(wèn)次數(shù)只可能是幾所以，時(shí)間代價(jià)為。()。空間代價(jià)為。(/小h為二叉樹(shù)的高度。6 .設(shè)計(jì)一個(gè)程序，根據(jù)二叉樹(shù)的先根序列和對(duì)稱(chēng)序序列創(chuàng)建一棵用左右指針表示的二叉樹(shù)。【答】數(shù)據(jù)結(jié)構(gòu)采用5.1.3節(jié)中二叉樹(shù)的鏈接表示。思路二叉樹(shù)的先根序列和對(duì)稱(chēng)序序列，用兩個(gè)數(shù)組preoider和inorder存放。先根序列的第一個(gè)元素的值pwdei0應(yīng)為二叉樹(shù)的根上的元素值在另一個(gè)數(shù)組中查到此值設(shè)為inorderA-0此時(shí)，數(shù)組preorder中從pieordmi到preorderk的序列(長(zhǎng)度為k)和數(shù)組morder中從inoidW

34、O到inordei-1(長(zhǎng)度為k)的序列，恰好分別是根結(jié)點(diǎn)左子樹(shù)(k個(gè)結(jié)點(diǎn))的先根序列和對(duì)稱(chēng)序序列。數(shù)組preoider中從pieorder2+l到preorder-1的序列(長(zhǎng)度為n-k-l)和數(shù)組inorde中從inorde伙+1倒inoider/?-l(長(zhǎng)度為n-k-1)的序列，恰好分別是根結(jié)點(diǎn)左子樹(shù)(n-k-1個(gè)結(jié)點(diǎn))的先根序列和對(duì)稱(chēng)序序列。根據(jù)上述分析，算法先創(chuàng)建根結(jié)點(diǎn)，再遞歸調(diào)用自己兩次來(lái)分別創(chuàng)建左右子樹(shù)。算法mtcreate_BTree(PBmTreepbtree.DataType*preoider,DataType*inorder,mtn)產(chǎn)根據(jù)先根序列preoider和對(duì)稱(chēng)序

35、序列morder(長(zhǎng)度為)創(chuàng)建二叉樹(shù)pbtree0對(duì)于正確的先根序列和對(duì)稱(chēng)序序列，算法返回TRUE,否則返回FALSE。*/mti,k;mttagl.tag2;if(n0)*pbtree-NULL;returnTRUE;for(i-0;i<n;i+)if(inoideiipreoider0)break;if(in)*pbtree-NULL;returnFALSE;蘆輸入的先根序列或?qū)ΨQ(chēng)序序列有誤，創(chuàng)建失敗*/k-i;*pbtree-(PBinTieeNode)malloc(sizeof(stiiictBinTreeNode);(*pbtree)->infb-preorder0;ta

36、gl-create_BTiee(&(*pbtree)->liiiik,preorder+1,inorder,k);產(chǎn)遞歸調(diào)用本算法創(chuàng)建左子樹(shù)率/tag2-create_BTiee(&(*pbtree)->ilink,preordei+k十Lmorder+k+Ln-k-l);產(chǎn)遞歸調(diào)用本算法創(chuàng)建右子樹(shù)率/if(tagl-TRUE&&tag2TRUE)returnTRUE:returnFALSE;二叉樹(shù)創(chuàng)建成功當(dāng)且僅當(dāng)其左右子樹(shù)都創(chuàng)建成功年代價(jià)分析最壞的W況是，每t非口磔點(diǎn)只有左子樹(shù)。這時(shí)兩W眨間需要版交次。所以，該算法的時(shí)間代價(jià)為。(，空間代價(jià)主要包括

37、：存放二叉樹(shù)的空間。和用于遞歸調(diào)用的棧空間(不超過(guò)。()X7.試設(shè)計(jì)樹(shù)的子表表示法的存儲(chǔ)結(jié)構(gòu)，并給出在這種表示基礎(chǔ)上主要運(yùn)算的實(shí)現(xiàn)算法。【答】數(shù)據(jù)結(jié)構(gòu)廠(chǎng)邊表中結(jié)點(diǎn)的定義本/J*子結(jié)點(diǎn)位置*/*下一個(gè)邊的指針*/"結(jié)點(diǎn)的定義*/，*結(jié)點(diǎn)本身信息，/*到子結(jié)點(diǎn)的邊表率/樹(shù)的定義*/產(chǎn)結(jié)點(diǎn)表率/根的位置*/產(chǎn)結(jié)點(diǎn)的個(gè)數(shù)*/structEdgeNode(mtnodeposition:stmctEdgeNode*link:;structChiTreeNode(DataTypeinfb;structEdgeNode*children:;structChiTree(structChiTreeNod

38、enodelistMAXNUM;mtroot;mtn;typedefstructChiTree*PCluTree;算法創(chuàng)建空樹(shù)PChiTreeCreateNullTree_chitree(void)(PChiTreep;p一(PCliiTree)nialloc(sizeof<stiiictChiTree);if(pNULL)print.Outofspace!n");elsep->root1;returnp;)判斷樹(shù)是否為空intisNull_clutree(,PChiTreet)(returnt->n0;)返回非空樹(shù)的根結(jié)點(diǎn)的下標(biāo)DataTyperoot_chitr

39、ee(PCluTreet)(returnt->root;)返回下標(biāo)為p的結(jié)點(diǎn)的父結(jié)點(diǎn)的下標(biāo)mtpaient_chitree(PCluTreet.mtp)(mti;stmctEdgeNode*v;if(p<0|p>-t->n)return-1;for(i-0;i<t->n;if(v-t->nodelisti.children;wlule(v!-NULL)if(v->nodepositionp)returni;elsev_v->link;return-1;)返回下標(biāo)為p的結(jié)點(diǎn)的最左子結(jié)點(diǎn)的下標(biāo)mtleftChild_clutxee(PPaiTi

40、eet.mtp)(stmctEdgeNode*v;if(p<0|p>-t->n)return-1;v-t->nodelisti.cluldien;if(vNULL)return-1;leturnv->nodeposition;返回下標(biāo)為p的結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)的下標(biāo)mt nghtSiblmg_chitree(PPaiTree t. mt p) (mt i;stmct EdgeNode * v;if (p < 0 | p >- t->n) xeturn-1;for (i - 0; i < t->n; if(v - t->nodelis

41、ti.children;wlule (v!- NULL)if (v->nodeposition p) if(v->lmk NULL) return-1;/手沒(méi)有下標(biāo)為p的結(jié)點(diǎn)率/產(chǎn)for循環(huán)每次檢查結(jié)點(diǎn)下標(biāo)中一個(gè)元素率/戶(hù)每次循環(huán)檢查結(jié)點(diǎn)，的邊表中的一個(gè)元素中/產(chǎn)沒(méi)有右兄弟結(jié)點(diǎn)率/else/率返回右兄弟結(jié)點(diǎn)在結(jié)點(diǎn)表中的位置率/returnv->inik->nodeposition;v-v->link;return-1;/*沒(méi)有右兄弟結(jié)點(diǎn)*/)代價(jià)分析這是一個(gè)兩重循環(huán)程序，外層循環(huán)最多執(zhí)行次，內(nèi)層循環(huán)對(duì)每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)進(jìn)行檢查,子結(jié)點(diǎn)的個(gè)數(shù)最大可能與接近，所以表面看