【復(fù)習(xí)】離散數(shù)學(xué)課后練習(xí)

數(shù)據(jù)結(jié)構(gòu)與算法2012年秋季（一）線性結(jié)構(gòu)1、給定一個有n個元素的線性表。若采用順序存儲結(jié)構(gòu)，則在等概率前提下，向其插入一個元素需要移動的元素個數(shù)平均為（）。A．nB．n/2C．(n-1)/2D．(n+1)/22、已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半搜索90時，需進(jìn)行

次搜索可確定搜索成功；搜索40時需進(jìn)行

次搜索才能確定不成功。一、單選題、填空B2，43、以下程序中劃線語句的執(zhí)行次數(shù)是（）。intsum(intn){intsum=0,i,j;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++)

p*=j;

sum+=p;}returnsum;}

A．n(n+1)/2 B．n(n+1) C．n(n-1)/2 D．n(n-1)A4、計(jì)算機(jī)執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為

。

for(i=1;i<n-1;i++)for(j=1;j<=i;j++)s;5、下面關(guān)于線性表的敘述中，錯誤的是哪一個？（）A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B．線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。B6、在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時須修改指針（）。A．p->llink->rlink=p->rlink;p->rlink->llink=p->llink;B．p->llink=p->llink->llink;p->llink->rlink=p;C．p->rlink->llink=p;p->rlink=p->rlink->rlinkD．p->rlink=p->llink->llink;p->llink=p->rlink->rlink;7、遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。A．隊(duì)列B．多維數(shù)組C．棧D.線性表AC8、用I表示入棧操作，O表示出棧操作，若元素入棧順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的I和O操作串為（）。

A．IIOOIIOOB．IOIOIIOOC．IOIIOIOOD．IOIIOOIO9、若用一個大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？（）A．1和5B．2和4C．4和2D．5和1CB10、數(shù)組A[0..5,0..6]的每個元素占5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A[5，5]的地址是（）。

A．1175B．1180C．1205D．121011、算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（）。

A．a(chǎn)b+cde/*B．a(chǎn)bcde/+*+C．a(chǎn)bcde/*++D．a(chǎn)bcde*/++AB13、設(shè)有一組關(guān)鍵碼{19，01，23，14，55，20，84，27，68，11，10，77}，采用散列函數(shù)H（key）=key%13，處理沖突的方法是線性探測再散列的方法（即dj+1=（dj+1）%m）若在0~18（即m=19）的散列地址空間中對該關(guān)鍵碼構(gòu)造散列表，則關(guān)鍵碼14對應(yīng)的地址是（）。

A．1B．2C．3D．14B12、散列技術(shù)中的沖突指的是（）。A．兩個元素具有相同的序號B．兩個元素的關(guān)鍵碼不同，而其他屬性相同C．?dāng)?shù)據(jù)元素過多D．不同關(guān)鍵碼的元素對應(yīng)于相同的存儲地址D二、解答題1、設(shè)有三對角矩陣，如上圖所示，將帶狀區(qū)域中的元素ai,j(|i-j|≤1)放在一維數(shù)組B中，則（1）B的大小為多少？（2）元素ai,j在B中的位置是什么？（B的下標(biāo)從0開始計(jì)，以行優(yōu)先方式存儲）參考解答（1）B的大?。?n-2（2）解：用除留余數(shù)法，H(k)=k%p，p=13，各元素的散列地址如下：H(65)=0，H(23)=10，H(31)=5，H(26)=0，H(7)=7，H(91)=0，H(53)=1，H(15)=2，H(72)=7，H(52)=0，H(49)=10，H(68)=3，參考解答三、算法閱讀1、已知一帶表頭節(jié)點(diǎn)的單鏈表L為（5，7，0，9，4，2，8），first指針指向表頭節(jié)點(diǎn)，data為鏈表的值域，link為指針域。閱讀以下程序，回答問題。template<classType>voidChain<Type>::fun(Typemin,Typemax){ChainNode<Type>*pr=first,*p=first->link;while(p){if(p->data>min&&p->data<max){pr->link=p->link;deletep;p=pr->link;}else{pr=p;p=pr->link;}}}（1）說明該程序的功能；（2）試畫出執(zhí)行L.fun(3,7);調(diào)用后的L鏈表的邏輯示意圖。參考解答（1）刪除單鏈表中所有大于min且小于max的元素。（2）first->7->0->9->2->8。算法閱讀voidfun(SListTable&list){ inti=1; intj=0; while(i<list.size) { if(list.elem[i]!=list.elem[j]) { j++; list.elem[j]=list.elem[i]; } i++; } size=j;}structSListTable{int*elem;intsize;};2、list是一個順序存儲的線性表的非遞減序列，閱讀算法，說明其功能。閱讀示例【算法功能】刪除非遞減有序順序表中值相等的多余元素。ijlist四、算法填空？1、【算法功能】從一個順序存儲在線性表的非遞減序列刪除值相等的多余元素。structSListTable{ int*elem; intsize;};voiddeleteDuplicate(SListTable&list){ inti=1; intj=0; while(i<list.size) { if(list.elem[i]!=list.elem[j]) {

（1）

（2） } i++; }

（3）}參考解答（1）j++;（2）list.elem[j]=list.elem[i];（3）list.size=j;

（1）Fibonacci序列0,1,1,2,3,5,8,13,21,34..，其中每個元素是前兩個元素之和，可遞歸定義為：

試?yán)脳砟M計(jì)算的遞歸調(diào)用，編寫一個非遞歸實(shí)現(xiàn)的算法代碼，并給出必要的注釋。【注明】已知棧的三個運(yùn)算定義如下（可直接使用）：Push（S，x）：元素x入S棧；Pop（S，x）：S棧頂元素出棧；S_IsEmpty（S）：判斷?？眨瑃rue為空，false不為空。另外，top為棧頂指針。5、算法設(shè)計(jì)與實(shí)現(xiàn)inti,x1,x2;for(i=0;i<2;i++){cout<<i<<”,”;Push(S,i);}for(i=2;i<=n;++){Pop(S,x1);Pop(S,x2);x1+=x2;cout<<x1<<“,“;Push(S,x2);Push(S,x1);}荷蘭國旗問題（2）【荷蘭國旗問題】設(shè)有紅、白、藍(lán)三種顏色的條塊組成的條塊數(shù)組（顏色隨機(jī)排列），請編寫一個時間復(fù)雜度為O(n)的算法，使得這些條塊按紅、白、藍(lán)的順序排好，即排成荷蘭國旗圖案?！舅惴ㄋ枷搿坷眠x擇排序的思想。首先從序列中選擇所有的紅色條塊，依次放到序列的前面，然后再從剩余的序列中選擇所有的白色條塊，依次放到紅色條塊后面。這樣經(jīng)過兩趟選擇，時間復(fù)雜度為O(n)。設(shè)這些條塊顏色依次存放在L[0,…,n-1]中，voidSort(intL[],intn){ inti,j; i=0; for(j=i;j<n;j++) { if(L[j]==0) { if(j!=i) Swap(L[i],L[j]); i++; } } for(j=i;j<n;j++) { if(L[j]==1) { if(j!=i) Swap(L[i],L[j]); i++; } }}雞尾酒排序（3）【雞尾酒排序】是冒泡排序的輕微變形。

【雞尾酒排序】相鄰兩趟方向相反的冒泡，例如第一趟排序?qū)⒆畲笥涗浢芭莸綌?shù)組底部，而在第二趟排序中將最小記錄冒泡到數(shù)組的頂部，請按上述算法思想實(shí)現(xiàn)雞尾酒排序。template<classT>voidSwap(T&a,T&b){ Ttemp; temp=a; a=b; b=temp;}函數(shù)原型：template<classT>voidCocktail_sort(Tlist[],intlist_length)；請每位同學(xué)寫在紙上交上來（請寫上班學(xué)號和姓名）。雞尾酒排序示例參考解答template<classT>voidcocktail_sort(Tlist[],intlist_length){//thefirstelementoflisthasindex0intbottom=0;inttop=list_length-1;boolswapped=true;while(swapped==true)//ifnoelementshavebeenswapped,thenthelistissorted{swapped=false;for(inti=bottom;i<top;i++){if(list[i]>list[i+1])//testwhetherthetwoelementsareinthecorrectorder{Swap(list[i],list[i+1]);//letthetwoelementschangeplacesswapped=true;}}

//decreasestopthebecausetheelementwiththelargestvalueintheunsorted//partofthelistisnowonthepositiontoptop=top-1;for(inti=top;i>bottom;i--){if(list[i]<list[i-1]){Swap(list[i],list[i-1]);swapped=true;}}//increasesbottombecausetheelementwiththesmallestvalueintheunsorted//partofthelistisnowonthepositionbottom

bottom=bottom+1;}}線性表合并與拆分順序表的合并順序表的拆分單鏈表的合并單鏈表的拆分1、順序表的合并將Merge函數(shù)設(shè)計(jì)成為LinearList類的成員函數(shù)；寫main()函數(shù)測試Merge的正確性。【題目及要求】如果順序表A，B的數(shù)據(jù)元素按非遞減有序排列，現(xiàn)要求將A和B表中的數(shù)據(jù)元素合并為一個新的線性表C，且C中的數(shù)據(jù)元素仍按非遞減有序排列。算法演示

Merge函數(shù)235670346789LALBi=0j=0LC比較LA[0]與LB[0]LA[0]>LB[0];則LC[0]=LB[0]同時j++;235670346789LALBi=0j=10LC接下來LB[1]與LA[0]比較，以后都一樣比較，直至其中一個表到達(dá)表尾當(dāng)其中一個順序表到末尾時，直接將另一個表的剩余元素移到新表中。235670346789LALBi=4j=0067798233456LC

【算法思想】1、設(shè)三個指針（實(shí)際是整型變量）i，j，k分別指向A，B和C中某個元素，初值：i，j為1，k為0；2、分別從A和B中取得i，j所指向的兩個元素；3、比較兩元素的大小，誰小就把誰先插入到C中k所指的位置；4、A或B中剩余部分直接插入C中即可。順序表合并算法思想LinearList<T>&LinearList<T>::Merge(constLinearList<T>&A,constLinearList<T>&B){ inti=1,j=1,k=0; intn=A.Length(); intm=B.Length();/* if(MaxSize<m+n) { MaxSize=m+n; delete[]element; element=newT[MaxSize+1]; length=0; }*/

TgetI; TgetJ;

while(i<=n&&j<=m) {getI=A.Get(i);getJ=B.Get(j);if(getI<=getJ){ Insert(k,getI); k++; i++; } else { Insert(k,getJ); k++; j++; } }

//剩余部分處理 while(i<=n) { getI=A.Get(i); Insert(k,getI); k++; i++; } while(j<=m) { getJ=B.Get(j); Insert(k,getJ); k++; j++; } return*this;}函數(shù)的不同形式classLinearList{private：

……public：

LinearList&Merge(constLinearList&A,constLinearList&B);LinearListMerge(constLinearList&A,constLinearList&B);voidMerge(constLinearList&A,constLinearList&B,LinearList&C);}；2、單鏈表合并將Merge函數(shù)設(shè)計(jì)成為Chain類的成員函數(shù)；寫main()函數(shù)測試Merge的正確性。【題目及要求】設(shè)A和B分別表示兩個不帶表頭結(jié)點(diǎn)的非遞減有序單鏈表，試設(shè)計(jì)一個算法，將這兩個有序鏈表合并成一個非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間，不另外占用其他存儲空間。表中允許有重復(fù)的數(shù)據(jù)。函數(shù)的不同形式template<classT>classChain{public：Chain<T>&Merge(Chain<T>&hb);voidMerge(Chain<T>&hb);voidMerge(Chain<T>&ha,Chain<T>&hb);};template<classT>Chain<T>&Chain<T>::Merge(Chain<T>&hb){//將當(dāng)前鏈表this與鏈表hb按逆序合并，結(jié)果放在當(dāng)前鏈表this中。 ChainNode<T>*pa,*pb,*q,*p; pa=first; pb=hb.first;//檢測指針pa,pb first=NULL; //結(jié)果鏈表初始化 while(pa!=NULL&&pb!=NULL)//當(dāng)兩鏈表都未結(jié)束時 { if(pa->data<=pb->data)//從pa鏈中摘下 { q=pa; pa=pa->link; } else //從pb鏈中摘下 { q=pb; pb=pb->link; } q->link=first; first=q; //鏈入結(jié)果鏈的鏈頭 } p=(pa!=NULL)?pa:pb;//處理未完鏈的剩余部分 while(p!=NULL) { q=p; p=p->link; q->link=first; first=q; } hb.first=NULL;//【注意】如果不將hb.first置空，析構(gòu)的時候會出問題 return*this;}1、一棵高度為h的滿二叉樹共有n個結(jié)點(diǎn)，其中有m個葉子結(jié)點(diǎn)，則有

成立。

A、n=h+mB、h+m=2nC、m=h-1D、n=2m-1

D2、已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有_____個葉子結(jié)點(diǎn)。384

3、已知一棵完全二叉樹中共有767結(jié)點(diǎn)，則該樹中共有_____個葉子結(jié)點(diǎn)。（軟考真題）384完全二叉樹中度為1的節(jié)點(diǎn)數(shù)只有兩種可能：要么為0個（奇數(shù)個結(jié)點(diǎn)），要么為1個（偶數(shù)個結(jié)點(diǎn)）。

4、設(shè)節(jié)點(diǎn)x和y是二叉樹中任意兩個節(jié)點(diǎn)，在該二叉樹的前序遍歷序列中x在y之前，而在后序遍歷序列中x在y之后，則x和y的關(guān)系是：

A、x是y的左兄弟B、x是y的右兄弟

C、x是y的祖先D、x是y的后裔C軟考真題5、已知某二叉樹的中序遍歷序列是dgbaechf，后序遍歷序列是gdbehfca，則其前序遍歷序列是（）。

A．a(chǎn)bdgcefhB．a(chǎn)gdbecfh C．a(chǎn)bdgechfD．a(chǎn)dbgcefhA6、若從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是（）。

A．二叉搜索樹B．哈夫曼樹

C．堆D．AVL樹7、用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHI，寫出中序遍歷該二叉樹時訪問節(jié)點(diǎn)的順序

。HDIBEAFCGC8、初始關(guān)鍵碼序列為{E，D，X，K，H，L，M，C，P}，用篩選法所建的最大堆得到的序列是

。9、給定14個字母，假設(shè)它們的權(quán)值都相等。采用Huffman編碼，則每個字母的平均編碼長度是

。XPMKHLECD54/14（或3.857）D

11、有組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始最大堆為：A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，38B

12、在數(shù)據(jù)壓縮編碼應(yīng)用中，Huffman算法可以用來構(gòu)造具有

（1）的二叉樹，這是一種采用了（2）算法的算法。（1）A、前綴碼B、最優(yōu)前綴碼C、后綴碼D、最優(yōu)后綴碼（2）A、貪心B、分治C、遞推D、回溯解答：（1）B（2）A13、假設(shè)用于通信的電文僅由a，b，c，d，e，f，g，h，8個字母組成，各字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。（1）試為這8個字母設(shè)計(jì)Huffman編碼（需畫出相應(yīng)的Huffman樹）。（2）使用0-7的二進(jìn)制表示形式是另一種編碼方案。對于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。（提示：試從兩種編碼的帶權(quán)路徑長度上進(jìn)行比較說明）WPLHF=2.61，WPLEQ=3提高通信信道的利用率，提高報文發(fā)送速度或/和節(jié)省存儲空間。課堂練習(xí)B

14、有數(shù)據(jù){53，30，37，12，45，24，96}，從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉搜索樹，若希望高度最小，則應(yīng)選擇下面哪個序列輸入

。

A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，53

15、一棵二叉搜索樹，其節(jié)點(diǎn)A、B、C、D、E、F依次存放在一個起始地址為n（假定地址以字節(jié)為單位順序編號）的連續(xù)區(qū)域中，每個節(jié)點(diǎn)占4個字節(jié)：前2個字節(jié)存放節(jié)點(diǎn)值，后2個字節(jié)依次存放左指針、右指針。若該二叉搜索樹的根節(jié)點(diǎn)為E，則它的一種可能的前序遍歷為

(1)，相應(yīng)的層序遍歷為

(2)。在以上兩種遍歷的情況下，節(jié)點(diǎn)C的左指針Lc的存放地址為

(3)，Lc的內(nèi)容為

(4)。節(jié)點(diǎn)A的右指針Ra的內(nèi)容為

(5)。（1）A.EAFCBDB.EFACDBC.EABCFDD.EACBDF（2）A.EAFCBDB.EFACDBC.EABCFDD.EACBDF（3）A.n+9B.n+10C.n+12D.n+13（4）A.n+4B.n+8C.n+12D.n+16（5）A.n+4B.n+8C.n+12D.n+16解答：（1）D；（2）A；（3）B；（4）A；（5）B16、已知一長度為12的表（Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sept，Oct，Nov，Dec）。（1）依次取表中各元素構(gòu)造一棵二叉搜索樹（按照在英文字典中的先后順序比較元素值的大?。?；并求其在等概率情況下搜索成功時的平均搜索長度。（2）若對表中元素進(jìn)行排序構(gòu)成有序表，求在等概率情況下對此有序表進(jìn)行折半搜索成功的平均搜索長度。（3）按表中元素順序構(gòu)造一棵AVL樹，并求其在等概率情況下搜索成功的平均搜索長度。解答：（1）42/12；（2）37/12；（3）38/12JanFebJulyNovSeptMarJuneMayOctAprAugDec二叉搜索樹JanFebJulyNovSeptMarJuneMayOctAprAugDec折半搜索MarJanAprJulyNovOctJuneMaySeptAugFebDecAVL樹17、下圖為一棵AVL樹（關(guān)鍵碼按字典順序排列）。要求繪制出加入一個新結(jié)點(diǎn)時二叉樹的形態(tài)；若發(fā)生不平衡，需要指明相應(yīng)的平衡化旋轉(zhuǎn)類型。（1）畫出插入關(guān)鍵碼cow后的AVL樹。（3分）（2）畫出在插入關(guān)鍵碼cow后繼續(xù)插入關(guān)鍵碼him后的AVL樹。（3分）（3）計(jì)算經(jīng)過（1）和（2）結(jié)點(diǎn)插入后，該AVL樹在等概率情況下搜索成功的平均搜索長度（ASL）。（2分）參考解答

hi

cup

cutcat

cop

copy

his

hit

homehoe

cow

hi

cup

cutcat

cop

copy

hmihishomehoe

cowhit課后練習(xí)

18、假定一組數(shù)據(jù)對象為(40,28,16,56,50,32,30,63），按次序插入每個對象生成一棵AVL樹，根據(jù)插入過程畫出相應(yīng)旋轉(zhuǎn)過程和最終結(jié)果。19、假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是

。

A.樹B.圖C.線性表D.集合B

20、在含n個頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為

。

A．e

B．2e

C．n2-e

D．n2-2eD軟考真題21、設(shè)一個包含N個頂點(diǎn)、E條邊的簡單有向圖采用鄰接矩陣存儲結(jié)構(gòu)（矩陣元素A[i][j]等于0/1分別表示頂點(diǎn)i與頂點(diǎn)j之間有/無弧），則該矩陣的元素數(shù)目為（1），其中非零元素數(shù)目為為（2）。

A.E2B.N2C.N2-E2D.N2+E2A.NB.N+EC.ED.N-E軟考真題解答：（1）B；（2）C

22、若采用鄰接矩陣來存儲簡單有向圖，則某個頂點(diǎn)i的入度等于該矩陣

。

A、第i行中值為1的元素個數(shù)

B、所有值為1的元素總數(shù)

C、第i行及第i列中值為1的元素總個數(shù)

D、第i列中值為1的元素個數(shù)D軟考真題23、假設(shè)一個有n個頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個頂點(diǎn)vi相關(guān)的所有弧的時間復(fù)雜度是

。

A．O(n)

B．O(e)

C．O(n+e)

D．O(n*e)C24、若G是一個具有36條邊的非連通無向圖（不含自回路和多重邊），則圖G至少有

個頂點(diǎn)。

A、11B、10C、9D、8B有n個頂點(diǎn)的無向圖至多有n(n-1)/2條邊。軟考真題25、無向圖G=(V,E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）。 A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,b,d C．a(chǎn),e,b,c,f,dD．a(chǎn),e,d,f,c,b

D26、已知帶權(quán)的無向圖G如左圖所示（1）畫出G的鄰接表結(jié)構(gòu)（要求：頂點(diǎn)的各鄰接邊的鏈接順序按照頂點(diǎn)序號由小到大的順序鏈接）；（2）基于上述鄰接表結(jié)構(gòu)，從頂點(diǎn)A出發(fā)，分別寫出按深度優(yōu)先和寬度優(yōu)先遍歷圖G的頂點(diǎn)序列。12AB720152430108CED深度優(yōu)先遍歷序列：ABDCE寬度優(yōu)先遍歷序列：ABCED12AB720152430108CED算法設(shè)計(jì)27、設(shè)二叉樹節(jié)點(diǎn)表示的數(shù)據(jù)元素類型為T，二叉樹以二叉鏈表表示。一棵二叉樹的最大枝長和最小枝長分別定義如下：最大枝長就是二叉樹層次；最小枝長就是離根節(jié)點(diǎn)距離最近的葉節(jié)點(diǎn)距離根路徑上的邊數(shù)。例如，節(jié)點(diǎn)數(shù)目n=1的二叉樹其最大最小枝長都為0，n=2的二叉樹其最大最小枝長都為1.請?jiān)O(shè)計(jì)一個算法，同時求出一棵二叉樹的最大和最小枝長。請從以下幾個方面來闡述和表達(dá)此算法：（1）（3分）請給出二叉鏈表表示的二叉樹節(jié)點(diǎn)BinaryTreeNode的定義，該定義只是服務(wù)于（3）中所需要實(shí)現(xiàn)的算法，夠用即可；（2）（3分）請概要說明此算法思想；（3）（12分）編寫算法：函數(shù)頭建議定義為：template<T>voidFarNearleaf(BinaryTreeNode*root,int&Far,int&Near);（4）（2分）請?jiān)谒惴P(guān)鍵的地方給出必要的注釋。參考解答（1）二叉鏈表表示的二叉樹節(jié)點(diǎn)BinaryTreeNode的定義:template<T>classBinaryTreeNode{public: voidFarNearleaf(BinaryTreeNode*root,int&Far,int&Near);private: Tdata; BinaryTreeNode<T>*leftPtr; BinaryTreeNode<T>*rightPtr;};參考解答（2）算法思想【方法一】DFS深度優(yōu)先遍歷解法按照后序遍歷方式求樹的最大/小枝長在左右子樹最大/最小枝長確定的條件下：根root的最大枝長是左右子樹較大的最大枝長+1最小枝長為左右子樹較小的最小枝長+1注意區(qū)分單支樹或給出遞推公式NearLeaf(T:B,L,R)=min(NearLeaf(L),NearLeaf(R))+1FarLeaf(T:B,L,R)=max(FarrLeaf(L),FarLeaf(R))+1參考解答（2）算法思想【方法二】BFS廣度優(yōu)先遍歷（層次遍歷）解法層次遍歷時，遇到的第一個葉節(jié)點(diǎn)必有最小枝長，遇到的而最后一個葉節(jié)點(diǎn)必有最大枝長。3、算法實(shí)現(xiàn)【方法一】template<T>voidFarNearLeaf(BinaryTreeNode<T>*root,int&Far,int&Near){//按后續(xù)遍歷方式求二叉樹的最大/最小枝長

intrightFar,leafFar,rightNear,leafNear;

if(root==NULL)//空樹（1分）

{Far=0;Near=0; retrun;}if((root->leftPtr==NULL)&&(root->rightPtr==NULL))//獨(dú)根

{Far=0;Near=0;return;}

//求左子樹最大/最小枝長（2分）

FarNearLeaf(root->leftPtr,leftPtr,leftNear);

//求右子樹最大/最小枝長（2分）

FarNearLeaf(root->rightPtr,rightPtr,rightNear);

Far=(leftFar>rightfar?leftFar:rightFar)+1;if(!root->leftPtr||!root->rightPtr)//單枝樹，最小枝長為非空子樹最小枝長+1 Near=(root->leftPtr?leftNear:rightNear)+1;else//左右子樹均存在，最小枝長為左右子樹較小的最小枝長+1Near=(leftNear<rightNear?leftNear:rightNear)+1;}28、二叉樹采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，試設(shè)計(jì)一個算法計(jì)算一棵二叉樹的所有結(jié)點(diǎn)數(shù)。f(b)=0若b==NULLf(b)=1若b->leftChild==NULL且b->rightChild==NULLf(b)=f(b->leftChild)+f(b->rightChild)+1其他template<classType>intBinaryTree::nodes(BinTreeNode<Type>*t){if(t==NULL)return0;if(t->leftChild==NULL&&t->rightChild==NULL)return1;returnnodes(t->leftChild)+nodes(t->rightChild)+1;}二叉樹采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，試設(shè)計(jì)一個算法計(jì)算一棵二叉樹的所有葉結(jié)點(diǎn)數(shù)。二叉樹采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，試設(shè)計(jì)一個算法計(jì)算一棵二叉樹的所有非葉結(jié)點(diǎn)數(shù)。二叉樹采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，試設(shè)計(jì)一個算法計(jì)算一棵二叉樹的所有度為1的結(jié)點(diǎn)數(shù)。1、在文件“局部有序”或文件長度較小的情況下，最佳的內(nèi)部排序方法是（）

A、插入排序B、堆排序

C、歸并排序D、快速排序A最不合適的是？2、在有向圖G的拓?fù)湫蛄兄校繇旤c(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是

。A、G中有弧<Vi,Vj>B、G中有一條從Vj到Vi的路徑C、G中沒有弧<Vi,Vj>D、G中有一條從Vi到Vj的路徑B3、設(shè)有向圖G的頂點(diǎn)集合為{v1,v2,v3,v4,v5}，邊的集合為{<v1,v2>，<v2,v4>，<v3,