數(shù)據(jù)結(jié)構(gòu)預(yù)算法第2版課后習(xí)題答案張曉莉編1

1、2.3 課后習(xí)習(xí)題解答2.3.2 判判斷題1線性表的邏邏輯順序與存存儲(chǔ)順序總是是一致的。（）2順序存儲(chǔ)的的線性表可以以按序號(hào)隨機(jī)機(jī)存取。（）3順序表的插插入和刪除操操作不需要付付出很大的時(shí)時(shí)間代價(jià)，因因?yàn)槊看尾僮髯髌骄挥薪话氲脑厮匦枰苿?dòng)。（）4線性表中的的元素可以是是各種各樣的的，但同一線線性表中的數(shù)數(shù)據(jù)元素具有有相同的特性性，因此屬于于同一數(shù)據(jù)對(duì)對(duì)象。（）5在線性表的的順序存儲(chǔ)結(jié)結(jié)構(gòu)中，邏輯輯上相鄰的兩兩個(gè)元素在物物理位置上并并不一定相鄰鄰。（）6在線性表的的鏈?zhǔn)酱鎯?chǔ)結(jié)結(jié)構(gòu)中，邏輯輯上相鄰的元元素在物理位位置上不一定定相鄰。（）7線性表的鏈鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)構(gòu)優(yōu)于順序存存儲(chǔ)結(jié)構(gòu)。（）8在

2、線性表的的順序存儲(chǔ)結(jié)結(jié)構(gòu)中，插入入和刪除時(shí)移移動(dòng)元素的個(gè)個(gè)數(shù)與該元素素的位置有關(guān)關(guān)。（）9線性表的鏈鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)構(gòu)是用一組任任意的存儲(chǔ)單單元來存儲(chǔ)線線性表中數(shù)據(jù)據(jù)元素的。（）10在單鏈表表中，要取得得某個(gè)元素，只只要知道該元元素的指針即即可，因此，單單鏈表是隨機(jī)機(jī)存取的存儲(chǔ)儲(chǔ)結(jié)構(gòu)。（）11靜態(tài)鏈表表既有順序存存儲(chǔ)的優(yōu)點(diǎn)，又又有動(dòng)態(tài)鏈表表的優(yōu)點(diǎn)。所所以它存取表表中第i個(gè)元素的時(shí)時(shí)間與i無關(guān)。（）12線性表的的特點(diǎn)是每個(gè)個(gè)元素都有一一個(gè)前驅(qū)和一一個(gè)后繼。（）2.3.3 算算法設(shè)計(jì)題1設(shè)線性表存存放在向量AAarrsiize的前前elenuum個(gè)分量中中，且遞增有有序。試寫一一算法，將xx 插入到線

3、線性表的適當(dāng)當(dāng)位置上，以以保持線性表表的有序性，并并且分析算法法的時(shí)間復(fù)雜雜度。【提示】直接用用題目中所給給定的數(shù)據(jù)結(jié)結(jié)構(gòu)（順序存存儲(chǔ)的思想是是用物理上的的相鄰表示邏邏輯上的相鄰鄰，不一定將將向量和表示示線性表長度度的變量封裝裝成一個(gè)結(jié)構(gòu)構(gòu)體），因?yàn)闉槭琼樞虼鎯?chǔ)儲(chǔ)，分配的存存儲(chǔ)空間是固固定大小的，所所以首先確定定是否還有存存儲(chǔ)空間，若若有，則根據(jù)據(jù)原線性表中中元素的有序序性，來確定定插入元素的的插入位置，后后面的元素為為它讓出位置置，（也可以以從高下標(biāo)端端開始一邊比比較，一邊移移位）然后插插入x ，最后修修改表示表長長的變量。int inssert (datatype AA,int *elen

4、uum,dattatypee x)/*設(shè)elennum為表的的最大下標(biāo)*/if (*eelenumm=arrrsize-1) rreturnn 0;/*表已滿滿，無法插入入*/else ii=*eleenum; whiile (ii=0 & Aiix)/*邊找位置置邊移動(dòng)*/Ai+1=Ai;i-; Ai+1=x;/*找到的位位置是插入位位的下一位*/ (*eelenumm)+;return 1;/*插入成成功*/時(shí)間復(fù)雜度為OO(n)。2已知一順序序表A，其元素值值非遞減有序序排列，編寫寫一個(gè)算法刪刪除順序表中中多余的值相相同的元素。【提示】對(duì)順序序表A，從第第一個(gè)元素開開始，查找其其后與之值

5、相相同的所有元元素，將它們們刪除；再對(duì)對(duì)第二個(gè)元素素做同樣處理理，依此類推推。void deelete(Seqlisst *A)i=0;while(iillast)/*將第i個(gè)個(gè)元素以后與與其值相同的的元素刪除*/k=ii+1;whiile(kllast&A-daatai=A-datak)k+;/*使k指向第一個(gè)個(gè)與Ai不同的元素素*/n=kk-i-1;/*n表示要?jiǎng)h除除元素的個(gè)數(shù)數(shù)*/forr(j=k;jlastt;j+)A-dataaj-n=A-ddatajj; /*刪除多余余元素*/A-last= A-llast -n; ii+;3寫一個(gè)算法法，從一個(gè)給給定的順序表表A中刪除值在在xy(

6、xxdataai是否否介于x和y之間，若是是，并不立即即刪除，而是是用n記錄刪除時(shí)時(shí)應(yīng)前移元素素的位移量；若不是，則則將A-ddataii向前移動(dòng)動(dòng)n位。n用來記錄當(dāng)當(dāng)前已刪除元元素的個(gè)數(shù)。void deelete(Seqlisst *A,int xx,int y)i=0;n=0;while (ilast)if (A-ddataii=x & A-daataiddataii 介于x和y之間，n自增*/else A-daatai-n=A-dataai;/*否則向向前移動(dòng)A-dataai*/i+;A-lastt-=n;4線性表中有有n個(gè)元素，每每個(gè)元素是一一個(gè)字符，現(xiàn)現(xiàn)存于向量RRn中，試試寫一算法

7、，使使R中的字符按按字母字符、數(shù)數(shù)字字符和其其它字符的順順序排列。要要求利用原來來的存儲(chǔ)空間間，元素移動(dòng)動(dòng)次數(shù)最小?！咎崾尽繉?duì)線性性表進(jìn)行兩次次掃描，第一一次將所有的的字母放在前前面，第二次次將所有的數(shù)數(shù)字放在字母母之后，其它它字符之前。int fchh(charr c)/*判斷c是否字母*/if(c=a&c=A&c=0&c=99) returrn (1);else retuurn (00);void prrocesss(charr Rn)low=0;high=n-1;while(llowhiigh)/*將字母放放在前面*/whille(lowwhighh&fchh(Rloow) low+;w

8、hile(llowhiigh&!fch(RRhighh) highh-;if(lowhigh)k=Rloow;Rlow=Rhiggh;Rhigh=k;low=loww+1; high=n-1;while(llowhiigh)/*將數(shù)字放放在字母后面面，其它字符符前面*/whille(lowwhighh&fnuum(Rllow) low+;while(lowhhigh&!fnumm(Rhiigh) highh-;if(lowwhighh) kk=Rloow;Rlow=Rhiggh;Rhigh=k;5線性表用順順序存儲(chǔ)，設(shè)設(shè)計(jì)一個(gè)算法法，用盡可能能少的輔助存存儲(chǔ)空間將順順序表中前mm個(gè)元素和后后n

9、個(gè)元素進(jìn)行行整體互換。即即將線性表：（a1, a22, , am, b1, b2, , bn）改變?yōu)椋海╞1, b22, , bn , a1, a2, , am）?！咎崾尽勘容^mm和n的大小，若若mn，則將將表中元素依依次前移m次；否則,將表中元素素依次后移nn次。void prrocesss(Seqlisst *L,int mm,int n) if(m=n) forr(i=1;idaata0;foor(k=11;klasst;k+)L-dataak-1=L-ddatakk;L-dataaL-llast=x;else for(ii=1;idaataL-lastt;foor(k=LL-lasst

10、-1;kk=0;kk- -)L-dataak+1=L-ddatakk;L-dataa0=xx;6已知帶頭結(jié)結(jié)點(diǎn)的單鏈表表L中的結(jié)點(diǎn)是是按整數(shù)值遞遞增排列的，試試寫一算法，將將值為x 的結(jié)點(diǎn)插插入到表L中，使得L仍然遞增有有序，并且分分析算法的時(shí)時(shí)間復(fù)雜度。LinkLisst inssert(LLinkList LL, int xx) p=L; whille(p-next & xp-next-dataa) p=pp-nexxt;/*尋找插入入位置*/ s=(LLNode *)mallloc(ssizeoff(LNode);/*申請(qǐng)結(jié)點(diǎn)點(diǎn)空間*/s-datta=x; /*填裝結(jié)點(diǎn)點(diǎn)*/s-neex

11、t=p-nextt; p-nnext=ss; /*將結(jié)點(diǎn)點(diǎn)插入到鏈表表中*/ retuurn(L); 7假設(shè)有兩個(gè)個(gè)已排序（遞遞增）的單鏈鏈表A和B，編寫算法法將它們合并并成一個(gè)鏈表表C而不改變其其排序性。LinkLisst Combinne(LinkList AA, LinkList BB)C=A;rc=C;pa=A-nnext;/*pa指向表AA的第一個(gè)結(jié)結(jié)點(diǎn)*/pb=B-nnext;/*pb指向表BB的第一個(gè)結(jié)結(jié)點(diǎn)*/free(B);/*釋放B的頭結(jié)點(diǎn)*/while (pa & pb)/*將pa、pb所指向結(jié)結(jié)點(diǎn)中，值較較小的一個(gè)插插入到鏈表CC的表尾*/ iff(pa-dataddat

12、a) rc-neext=paa;rc=pa;pa=pa-next;elserc-neext=pbb;rc=pb;pb=pb-next;if(pa)rc-nnext=ppa;elsercc-nexxt=pb;/*將鏈表AA或B中剩余的部部分鏈接到鏈鏈表C的表尾尾*/return(C);8假設(shè)長度大大于1的循環(huán)環(huán)單鏈表中，既既無頭結(jié)點(diǎn)也也無頭指針，p為指向該鏈表中某一結(jié)點(diǎn)的指針，編寫算法刪除該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)?！咎崾尽坷醚h(huán)單鏈表的的特點(diǎn)，通過過s指針可循環(huán)環(huán)找到其前驅(qū)驅(qū)結(jié)點(diǎn)p及p的前驅(qū)結(jié)點(diǎn)點(diǎn)q，然后可刪刪除結(jié)點(diǎn)*p。viod deelepree(LNodde *s)LNode *p, *q;p

13、=s;while (p-neext!=s)q=p; p=p-neext;q-nextt=s;free(p);9已知兩個(gè)單單鏈表A和B分別表示兩兩個(gè)集合，其其元素遞增排排列，編寫算算法求出A和B的交集C，要求C同樣以元素素遞增的單鏈鏈表形式存儲(chǔ)儲(chǔ)。【提示】交集指指的是兩個(gè)單單鏈表的元素素值相同的結(jié)結(jié)點(diǎn)的集合，為為了操作方便便，先讓單鏈鏈表C帶有一個(gè)頭頭結(jié)點(diǎn)，最后后將其刪除掉掉。算法中指指針p用來指向A中的當(dāng)前結(jié)結(jié)點(diǎn)，指針qq用來指向B中的當(dāng)前結(jié)結(jié)點(diǎn)，將其值值進(jìn)行比較，兩兩者相等時(shí)，屬屬于交集中的的一個(gè)元素，兩兩者不等時(shí)，將將其較小者跳跳過，繼續(xù)后后面的比較。LinkLisst Inttersec

14、ct(LinnkListt A, LiinkLisst B)LNode *q, *p, *r, *s; LinkLisst C;C= (LNoode *)mallooc(sizzeof(LLNode);C-nextt=NULLL;r=C;p=A; q=B;while (p & q ) iff (p-datadaata) pp=p-nnext; elseif (pp-datta=q-dataa) s=(LNode *)mallloc(ssizeoff(LNode); s-data=p-daata; r-next=s; r=ss; p=pp-nexxt; q=qq-nexxt; else qq=q

15、-nnext;r-nextt=NULLL; C=C-nextt; retuurn C;10設(shè)有一個(gè)個(gè)雙向鏈表，每每個(gè)結(jié)點(diǎn)中除除有prioor、data和next域外外，還有一個(gè)個(gè)訪問頻度ffreq域，在在鏈表被起用用之前，該域域的值初始化化為零。每當(dāng)當(dāng)在鏈表進(jìn)行行一次Loccata(LL,x)運(yùn)算算后，令值為為x的結(jié)點(diǎn)中的的freq域增增1，并調(diào)整整表中結(jié)點(diǎn)的的次序，使其其按訪問頻度度的非遞增序序列排列，以以便使頻繁訪訪問的結(jié)點(diǎn)總總是靠近表頭頭。試寫一個(gè)個(gè)滿足上述要要求的Loccata(LL,x)算法法?！咎崾尽吭诙ㄎ晃徊僮鞯耐瑫r(shí)時(shí)，需要調(diào)整整鏈表中結(jié)點(diǎn)點(diǎn)的次序：每每次進(jìn)行定位位操作后，要要查

16、看所查找找結(jié)點(diǎn)的frreq域，將將其同前面結(jié)結(jié)點(diǎn)的freeq域進(jìn)行比比較，同時(shí)進(jìn)進(jìn)行結(jié)點(diǎn)次序序的調(diào)整。typedeff struuct dnnodedatatyype daata;int ffreq;strucct DLnodee *priior,*nnext;DLnodee,*DLiinkList;DlinkLiist Locatte(DLiinkList LL, datattype xx)p=L-nnext;while(pp&p-data!=x) pp=p-nnext; /*查找值為為x的結(jié)點(diǎn)，使使p指向它*/if(!p) returrn(NULLL);/*若查找失失敗，返回空空指針*/p

17、-freqq+;/*修改p的freq域*/while(pp-priior!=LL&p-priorr-freeqfreq)/*調(diào)整結(jié)點(diǎn)點(diǎn)的次序*/ kk=p-pprior-dataa;p-prioor-daata=p-dataa;p-dataa=k;k=p-prrior-freq;p-prioor-frreq=p-freqq;p-freqq=k;p=p-prrior; returrn(p);/*返回找到到的結(jié)點(diǎn)的地地址*/3.3 課后習(xí)習(xí)題解答 #3.3.1 選選擇題1向一個(gè)棧頂頂指針為Toop的鏈棧中中插入一個(gè)pp所指結(jié)點(diǎn)時(shí)時(shí)，其操作步步驟為（C）。ATop-next=p; Bp-next=T

18、op-next;Top-next=p;Cp-nnext=TTop;Toop=p; Dp-next=Top;TTop=Toop-next;2對(duì)于棧操作作數(shù)據(jù)的原則則是（B）。A先進(jìn)先出 B后進(jìn)先出 C后進(jìn)后后出 D不分分順序3若已知一個(gè)個(gè)棧的入棧序序列是1,22,3,n，其輸出出序列為p1,p2,p3，pN,若pN是n，則pi是（D）。Ai Bn-i C n-i+1 D不確定定4表達(dá)式a*(bc)d的后綴表達(dá)達(dá)式是（B）。Aabcd*-+ Babc-*d+ Cabc*-d+ D+-*abbcd5采用順序存存儲(chǔ)的兩個(gè)棧棧共享空間SS1.mm，topii代表第i個(gè)棧( i=1,2)的的棧頂，棧11的

19、底在S11，棧2的底在Smm，則棧滿滿的條件是（BB）。Atop22-topp1|=0 Btop11+1=ttop2Ctop11+topp2=mm Dtop11=topp26一個(gè)棧的入入棧序列是aa,b,c,d,e，則則棧的不可能能的輸出序列列是（C）。A edcbba B deecba Cdceabb D abbcde7在一個(gè)鏈隊(duì)隊(duì)列中，若ff,r分別為為隊(duì)首、隊(duì)尾尾指針，則插插入s所指結(jié)點(diǎn)的的操作為（BB）。Af-neext=r;f=s; Br-next=s;r=ss; Cs-neext=r;r=s; Ds-next=f;f=ss;8用不帶頭結(jié)結(jié)點(diǎn)的單鏈表表存儲(chǔ)隊(duì)列時(shí)時(shí)，在進(jìn)行刪刪除運(yùn)算時(shí)

20、（D）。A僅修改頭指指針 B僅修改尾指指針C頭、尾指針針都要修改 D頭、尾指針針可能都要修修改9遞歸過程或或函數(shù)調(diào)用時(shí)時(shí)，處理參數(shù)數(shù)及返回地址址，要用一種種稱為（C）的的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B靜態(tài)鏈表 C棧 D順序表10棧和隊(duì)都都是（C）。A順序存儲(chǔ)的的線性結(jié)構(gòu) B鏈?zhǔn)酱鎯?chǔ)儲(chǔ)的非線性結(jié)結(jié)構(gòu)C限制存取點(diǎn)點(diǎn)的線性結(jié)構(gòu)構(gòu) D限制存取取點(diǎn)的非線性性結(jié)構(gòu)3.3.2 判判斷題1棧和隊(duì)列的的存儲(chǔ)，既可可以采用順序序存儲(chǔ)結(jié)構(gòu)，又又可以采用鏈鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)構(gòu)。（）2任何一個(gè)遞遞歸過程都可可以轉(zhuǎn)換成非非遞歸過程。（）3若輸入序列列為1,2,3,4,55,6，則通通過一個(gè)?？煽梢暂敵鲂蛄辛?,2,55,6,4,1。（）

21、4通常使用隊(duì)隊(duì)列來處理函函數(shù)的調(diào)用。（）5循環(huán)隊(duì)列通通常用指針來來實(shí)現(xiàn)隊(duì)列的的頭尾相接。（）3.3.3 簡簡答題1循環(huán)隊(duì)列的的優(yōu)點(diǎn)是什么么？如何判別別它的空和滿滿？循環(huán)隊(duì)列的優(yōu)點(diǎn)點(diǎn)是能夠克服服“假溢滿”現(xiàn)象。設(shè)有循環(huán)隊(duì)列ssq，隊(duì)滿的的判別條件為為：（sq-reear+1）%maxsiize=ssq-frront;或或sq-num=mmaxsizze。隊(duì)空的判別條件件為：sq-reaar=sqq-froont。2棧和隊(duì)列數(shù)數(shù)據(jù)結(jié)構(gòu)各有有什么特點(diǎn)，什什么情況下用用到棧，什么么情況下用到到隊(duì)列？棧和隊(duì)列都是操操作受限的線線性表，棧的的運(yùn)算規(guī)則是是“后進(jìn)先出”，隊(duì)列的運(yùn)運(yùn)算規(guī)則是“先進(jìn)先出”。棧的應(yīng)

22、用用如數(shù)制轉(zhuǎn)換換、遞歸算法法的實(shí)現(xiàn)等，隊(duì)隊(duì)列的應(yīng)用如如樹的層次遍遍歷等。3什么是遞歸歸？遞歸程序序有什么優(yōu)缺缺點(diǎn)？一個(gè)函數(shù)在結(jié)束束本函數(shù)之前前，直接或間間接調(diào)用函數(shù)數(shù)自身，稱為為遞歸。例如如，函數(shù)f在執(zhí)行中，又又調(diào)用函數(shù)ff自身，這稱稱為直接遞歸歸；若函數(shù)ff在執(zhí)行中，調(diào)調(diào)用函數(shù)g，而g在執(zhí)行中，又又調(diào)用函數(shù)ff，這稱為間間接遞歸。在在實(shí)際應(yīng)用中中，多為直接接遞歸，也常常簡稱為遞歸歸。遞歸程序的優(yōu)點(diǎn)點(diǎn)是程序結(jié)構(gòu)構(gòu)簡單、清晰晰，易證明其其正確性。缺缺點(diǎn)是執(zhí)行中中占內(nèi)存空間間較多，運(yùn)行行效率低。4設(shè)有編號(hào)為為1,2,33,4的四輛輛車，順序進(jìn)進(jìn)入一個(gè)棧式式結(jié)構(gòu)的站臺(tái)臺(tái)，試寫出這這四輛車開出出車站的

23、所有有可能的順序序（每輛車可可能入站，可可能不入站，時(shí)時(shí)間也可能不不等）。1234,12243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,43214.3 課后習(xí)習(xí)題解答#4.3.1 選選擇題1下面關(guān)于串串的敘述錯(cuò)誤誤的是（C）。A串是字符的的有限序列 B串既可以采采用順序存儲(chǔ)儲(chǔ)，也可以采采用鏈?zhǔn)酱鎯?chǔ)儲(chǔ)C空串是由空空格構(gòu)成的串串 D模式匹配是是串的一種重重要運(yùn)算2串的長度是是指（B）。A串中所含不不同字母的個(gè)個(gè)數(shù) B串串中所含字符符的個(gè)數(shù)C串中所含不不同字符的個(gè)個(gè)數(shù) D串串中所含非空空格字符的個(gè)個(gè)數(shù)3已知串S=aaab,其Next

24、數(shù)組組值為（A）。A0123 B1123 C1231 D12114二維數(shù)組MM的成員是66個(gè)字符（每每個(gè)字符占一一個(gè)存儲(chǔ)單元元）組成的串串，行下標(biāo)ii的范圍從00到8，列下下標(biāo)j的范圍圍從1到100，則存放MM至少需要（DD）個(gè)字節(jié)；M的第8列列和第5行共共占（A）個(gè)個(gè)字節(jié)；若MM按行優(yōu)先方方式存儲(chǔ)，元元素M85的起起始地址與當(dāng)當(dāng)M按列優(yōu)先先方式存儲(chǔ)時(shí)時(shí)的（C）元元素的起始地地址一致。（1）A900 B1880 C2440 D5440（2）A1008 B1114 C544 D600（3）AM85 BM3310 CM558 DDM095數(shù)組A中，每每個(gè)元素的存存儲(chǔ)占3個(gè)單單元，行下標(biāo)標(biāo)i從1到8

25、8，列下標(biāo)jj從1到100，從首地址址SA開始連連續(xù)存放在存存儲(chǔ)器內(nèi)，存存放該數(shù)組至至少需要的單單元個(gè)數(shù)是（CC），若該數(shù)數(shù)組按行存放放，元素A85的起始地址址是（D），若若該數(shù)組按列列存放，元素素A85的起始始地址是（BB）。（1）A800 BB100 C2440 D2270（2）ASAA+141 BSA+1444 CSA+222 DSSA+2255（3）ASAA+141 BSA+1880 CSA+117 DSSA+22556稀疏矩陣采采用壓縮存儲(chǔ)儲(chǔ)，一般有（CC）兩種方法法。A二維數(shù)組和和三維數(shù)組 B三元組和散散列C三元組表和和十字鏈表 D散散列和十字鏈鏈表4.3.2 判判斷題1串相等是指

26、指兩個(gè)串的長長度相等。（）2KMP算法法的特點(diǎn)是在在模式匹配時(shí)時(shí)指示主串的的指針不會(huì)變變小。（）3稀疏矩陣壓壓縮存儲(chǔ)后，必必會(huì)失去隨機(jī)機(jī)存取功能。（）4數(shù)組是線性性結(jié)構(gòu)的一種種推廣，因此此與線性表一一樣，可以對(duì)對(duì)它進(jìn)行插入入，刪除等操操作。（）5若采用三元元組存儲(chǔ)稀疏疏矩陣，把每每個(gè)元素的行行下標(biāo)和列下下標(biāo)互換，就就完成了對(duì)該該矩陣的轉(zhuǎn)置置運(yùn)算。（）6若一個(gè)廣義義表的表頭為為空表，則此此廣義表亦為為空表。（）7所謂取廣義義表的表尾就就是返回廣義義表中最后一一個(gè)元素。（）4.3.3 簡簡答題1KMP算法法較樸素的模模式匹配算法法有哪些改進(jìn)進(jìn)?KMP算法主要要優(yōu)點(diǎn)是主串串指針不回溯溯。當(dāng)主串很很大

27、不能一次次讀入內(nèi)存且且經(jīng)常發(fā)生部部分匹配時(shí)，KMP算法的優(yōu)點(diǎn)更為突出。2設(shè)字符串SS=aabaaabaabaaac，P=aabaaac。（1）給出S和和P的next值和和nextvval值； （2）若S作主主串，P作模式串，試試給出利用KKMP算法的的匹配過程?！窘獯稹?（1）S的neext與nextvval值分別別為01211234566789和00200020020009，p的next與nextvval值分別別為0121123和0020003。 （2）利利用BF算法的匹匹配過程： 利利用KMP算法的的匹配過程： 第一趟匹配：aabaaabaabaaac 第一趟匹匹配：aabbaabaaab

28、aac aaabaacc(i=6,j=6) aabbaac(ii=6,j=6) 第二趟匹配配：aabaaabaabbaac 第二趟趟匹配：aaabaabaaabaacc aaa(i=33,j=2) (aaa)baacc 第三趟匹配：aabaaabaabaaac 第三趟匹匹配：aabbaabaaabaac a(i=3,jj=1) (成功) (aaa)baaac第四趟匹配：aaabaabbaabaaac aaabaacc(i=9,j=6)第五趟匹配：aaabaabbaabaaac aa(i=6,j=22)第六趟匹配：aaabaabbaabaaac a(i=66,j=1)第七趟匹配：aaabaabb

29、aabaaac(成功) aaabaacc(i=133,j=7)3假設(shè)按行優(yōu)優(yōu)先存儲(chǔ)整數(shù)數(shù)數(shù)組A99358時(shí)，第一個(gè)個(gè)元素的字節(jié)節(jié)地址是1000，每個(gè)整整數(shù)占個(gè)字字節(jié)。問下列列元素的存儲(chǔ)儲(chǔ)地址是什么么？(1) a00000 (2)a11111 (3)aa3125 (4)a88247【解答】(1) LOC( a00000)= 100 (2) LOCC( a11111)=1000+(3*55*8*1+5*8*11+8*1+1)*4=776 (3) LOCC( a31255)=1000+(3*55*8*3+5*8*11+8*2+5) *44=17844 (4) LOCC( a82477)= 1000+

30、(3*5*8*88+5*8*2+8*44+7) *4=481164假設(shè)一個(gè)準(zhǔn)準(zhǔn)對(duì)角矩陣：aa11 a12a21 a22a33 a34a43 a44 . aij a2m-1,2m-1 a2m-1,2m a2m,2m-1 a2m,2m 按以下方式存儲(chǔ)儲(chǔ)于一維數(shù)組組B4m中（m為一一個(gè)整數(shù)）：012345 6 kk 4m-1 44ma 11a 12a21a22a33a34a43aija2m-1,22ma2m,2m-1a2m,2m寫出下標(biāo)轉(zhuǎn)換函函數(shù)k=f(i,j)?！窘獯稹坑深}目可知，每每一行有兩個(gè)個(gè)非0元素。當(dāng)i為奇數(shù)時(shí)，第第i行的元素素為：ai,i、ai,(i+1)，此時(shí)時(shí)k=2*(i-1)+j-

31、i=ii+j-2當(dāng)i為偶數(shù)時(shí)，第第i行的元素素為：ai,(i-1)、ai,i，此時(shí)時(shí)k=2*(i-1)+j-I+1=i+j-1綜上所述，k=i+j-ii%2-1。5設(shè)有nnn的帶寬為33的帶狀矩陣陣A，將其33條對(duì)角線上上的元素存于于數(shù)組B33n中中，使得元素素Buv=aiij，試推導(dǎo)導(dǎo)出從（i,j）到 (u,v)的下標(biāo)標(biāo)變換公式?！窘獯稹縰=j-i+11v=j-16現(xiàn)有如下的的稀疏矩陣AA（如圖所示示），要求畫畫出以下各種種表示方法。（1）三元組表表表示法（2）十字鏈表表法。0 0 0 22 0 -150 0 0 22 0 -150 13 3 0 0 00 0 0 -6 0 00 0 0 0

32、 0 091 0 0 0 0 00 0 28 0 0 0【解答】（1）三元組表表表示法:i j v1234567 4 2221 6 -152 2 132 3 33 4 -65 1 916 3 28（2）十字鏈表表法：0012345012345519123334-61422632816-1522137畫出下列廣廣義表的頭尾尾表示存儲(chǔ)結(jié)結(jié)構(gòu)示意圖。（1）A=(a,b,cc),d,(a,b,cc)（2）B=(aa,(b,(c,d),e),f)（1）111111 1 1 d0 a1 b1 c（2）11111 1 1 0 f0 a0 b0 c1 10 c0 d5.3 課后習(xí)習(xí)題解答 5.3.1 選選擇題

33、1下列說法正正確的是（CC）。A二叉樹中任任何一個(gè)結(jié)點(diǎn)點(diǎn)的度都為22 B二叉樹的度度為2C一棵二叉樹樹的度可小于于2 D任何一棵二二叉樹中至少少有一個(gè)結(jié)點(diǎn)點(diǎn)的度為22以二叉鏈表表作為二叉樹樹的存儲(chǔ)結(jié)構(gòu)構(gòu)，在具有nn個(gè)結(jié)點(diǎn)的二二叉鏈表中（n0），空鏈域的個(gè)數(shù)為（C）。A2n-1 BBn-1 Cn+11 D2n+13線索化二叉叉樹中，某結(jié)結(jié)點(diǎn)*p沒有有孩子的充要要條件是（BB）。Ap-lcchild=NULL Bpp-ltaag=1且p-rtag=11Cp-lttag=0 Dp-llchildd=NULLL 且p-lttag=14如果結(jié)點(diǎn)AA有3個(gè)兄弟,而且B是A的雙親,則B的度是（BB）。 A3

34、 B4 C5 D1 5某二叉樹TT有n個(gè)結(jié)點(diǎn),設(shè)按某種順順序?qū)中的每個(gè)結(jié)結(jié)點(diǎn)進(jìn)行編號(hào)號(hào)，編號(hào)值為為1,2,.n。且且有如下性質(zhì)質(zhì):T中任意結(jié)結(jié)點(diǎn)v,其編號(hào)等等于左子樹上上的最小編號(hào)號(hào)減,而v的右子樹的的結(jié)點(diǎn)中,其最小編號(hào)號(hào)等于v左子樹上結(jié)結(jié)點(diǎn)的最大編編號(hào)加，這這是按（B）編編號(hào)的。A 中序遍歷歷序列 B 先序遍遍歷序列 C 后序序遍歷序列 D 層次順序 6設(shè)F是一個(gè)個(gè)森林，B是由F轉(zhuǎn)換得到的的二叉樹，F(xiàn)F中有n個(gè)非終端結(jié)結(jié)點(diǎn),B中右指針針域?yàn)榭盏慕Y(jié)結(jié)點(diǎn)有（C）個(gè)個(gè)。An-1 B n C n+1 Dn+2 7一棵完全二二叉樹上有11001個(gè)結(jié)結(jié)點(diǎn)，其中葉葉子結(jié)點(diǎn)的個(gè)個(gè)數(shù)是（C）。A 500 B

35、 501 CC490 D4958設(shè)森林F中中有三棵樹，第第一，第二，第第三棵樹的結(jié)結(jié)點(diǎn)個(gè)數(shù)分別別為N1，N2和N3。與森林F對(duì)應(yīng)的二叉叉樹根結(jié)點(diǎn)的的右子樹上的的結(jié)點(diǎn)個(gè)數(shù)是是（D）。AN1 BN1+N2 CN2 DNN2+N39任何一棵二二叉樹的葉結(jié)結(jié)點(diǎn)在先序、中中序、后序遍遍歷序列中的的相對(duì)次序（AA）。A不發(fā)生改變變 B 發(fā)生改變變 C 不能確確定 D 以上都都不對(duì)10若一棵二二叉樹的后序序遍歷序列為為dabecc，中序遍歷歷序列為deebac，則則先序遍歷序序列為（D）。Acbed Bdeecab Cdeaabc DDcedbba11若一棵二二叉樹的先序序遍歷序列為為abdgccefh，中

36、中序遍歷的序序列為dgbbaechff，則后序遍遍歷的結(jié)果為為（D）。 A gceffha B gdbeccfha C bbdgaecchf D gdbehhfca12一棵非空空二叉樹的先先序遍歷序列列與后序遍歷歷序列正好相相反，則該二二叉樹一定滿滿足（B）。A所有的結(jié)點(diǎn)點(diǎn)均無左孩子子 B所有的結(jié)結(jié)點(diǎn)均無右孩孩子C只有一個(gè)葉葉子結(jié)點(diǎn) D是一棵滿滿二叉樹13引入線索索二叉樹的目目的是（A）。A加快查找結(jié)結(jié)點(diǎn)的前驅(qū)或或后繼的速度度 B為了能在二二叉樹中方便便的進(jìn)行插入入與刪除C為了能方便便的找到雙親親 D使二叉樹的的遍歷結(jié)果唯唯一 14設(shè)高度為為h的二叉樹上上只有度為和度為的的結(jié)點(diǎn)，則此此類二叉樹

37、中中所包含的結(jié)結(jié)點(diǎn)數(shù)至少為為（B）。A2*h B 22*h-1 C 2*hh+1 Dh+115一個(gè)具有有567個(gè)結(jié)結(jié)點(diǎn)的二叉樹樹的高h(yuǎn)為（D）。A9 B10 C9至5566之間 D10至5677之間16給一個(gè)整整數(shù)集合33，5，6，7，9，與該整數(shù)集合對(duì)應(yīng)的哈夫曼樹是（B）。A B CC D937693765 3567979536765395.3.2 判判斷題1二叉樹是樹樹的特殊形式式。（）2由樹轉(zhuǎn)換成成二叉樹，其其根結(jié)點(diǎn)的右右子樹總是空空的。（）3先根遍歷一一棵樹和先序序遍歷與該樹樹對(duì)應(yīng)的二叉叉樹，其結(jié)果果不同。（）4先根遍歷森森林和先序遍遍歷與該森林林對(duì)應(yīng)的二叉叉樹，其結(jié)果果不同。（）5完

38、全二叉樹樹中，若一個(gè)個(gè)結(jié)點(diǎn)沒有左左孩子，則它它必是葉子。（）6對(duì)于有N個(gè)個(gè)結(jié)點(diǎn)的二叉叉樹，其高度度為log2N1。（）7若一個(gè)結(jié)點(diǎn)點(diǎn)是某二叉樹樹子樹的中序序遍歷序列中中的最后一個(gè)個(gè)結(jié)點(diǎn)，則它它必是該子樹樹的先序遍歷歷序列中的最最后一個(gè)結(jié)點(diǎn)點(diǎn)。（）8若一個(gè)結(jié)點(diǎn)點(diǎn)是某二叉樹樹子樹的中序序遍歷序列中中的第一個(gè)結(jié)結(jié)點(diǎn)，則它必必是該子樹的的后序遍歷序序列中的第一一個(gè)結(jié)點(diǎn)。（）9不使用遞歸歸也可實(shí)現(xiàn)二二叉樹的先序序、中序和后后序遍歷。（）10先序遍歷歷二叉樹的序序列中，任何何結(jié)點(diǎn)的子樹樹的所有結(jié)點(diǎn)點(diǎn)不一定跟在在該結(jié)點(diǎn)之后后。（）11先序和中中序遍歷用線線索樹方式存存儲(chǔ)的二叉樹樹，不必使用用棧。（）12在后

39、序線線索二叉樹中中，在任何情情況下都能夠夠很方便地找找到任意結(jié)點(diǎn)點(diǎn)的后繼。（）13哈夫曼樹樹是帶權(quán)路徑徑長度最短的的樹，路徑上上權(quán)值較大的的結(jié)點(diǎn)離根較較近。（）14在哈夫曼曼編碼中，出出現(xiàn)頻率相同同的字符編碼碼長度也一定定相同。（）15用一維數(shù)數(shù)組存放二叉叉樹時(shí)，總是是以先序遍歷歷存儲(chǔ)結(jié)點(diǎn)。（）16由先序序序列和后序序序列能唯一確確定一棵二叉叉樹。（）17由先序序序列和中序序序列能唯一確確定一棵二叉叉樹。（）18對(duì)一棵二二叉樹進(jìn)行層層次遍歷時(shí)，應(yīng)應(yīng)借助于一個(gè)個(gè)棧。（）19完全二叉叉樹可采用順順序存儲(chǔ)結(jié)構(gòu)構(gòu)實(shí)現(xiàn)存儲(chǔ)，非非完全二叉樹樹則不能。（）20滿二叉樹樹一定是完全全二叉樹，反反之未必。（）5

40、.3.3 簡簡答題1一棵度為22的樹與一棵棵二叉樹有何何區(qū)別？樹與與二叉樹之間間有何區(qū)別？【解答】二叉樹是有序序樹，度為22的樹是無序序樹，二叉樹樹的度不一定定是2。ADBGEHCF(圖 1)二叉樹是有序序樹，每個(gè)結(jié)結(jié)點(diǎn)最多有ADBGEHCF(圖 1)2對(duì)于圖1所所示二叉樹，試試給出：（1）它的順序序存儲(chǔ)結(jié)構(gòu)示示意圖；（2）它的二叉叉鏈表存儲(chǔ)結(jié)結(jié)構(gòu)示意圖；（3）它的三叉叉鏈表存儲(chǔ)結(jié)結(jié)構(gòu)示意圖。【解答】（1）順序存儲(chǔ)儲(chǔ)結(jié)構(gòu)示意圖圖：ABCDEFGH（2）二叉鏈表表存儲(chǔ)結(jié)構(gòu)示示意圖： （3）三三叉鏈表存儲(chǔ)儲(chǔ)結(jié)構(gòu)示意圖圖：A A BC D E F G H ABC D E F G H IDEFGCID

41、EFGCBANMKJH(圖 2)（1）雙親數(shù)組組表示法示意意圖；（2）孩子鏈表表表示法示意意圖；（3）孩子兄弟弟鏈表表示法法示意圖?！窘獯稹浚?）雙親數(shù)組組表示法示意意圖： （2）孩孩子鏈表表示示法示意圖：00A-11B02C03D24E25F16G17H58I29J410K411M312N82 6410 15311 97 12 0A1B2C3D4E5F6G7H8I9J10K11M12N8 （3）孩子兄弟弟鏈表表示法法示意圖：A A B N H C GF EDI J K M 4畫出圖3所所示的森林經(jīng)經(jīng)轉(zhuǎn)換后所對(duì)對(duì)應(yīng)的二叉樹樹，并指出森森林中滿足什什么條件的結(jié)結(jié)點(diǎn)在二叉樹樹中是葉子。DDBCIG

42、 HAFE J(圖 3)【解答】HHFGIJABCED在二叉樹中某結(jié)結(jié)點(diǎn)所對(duì)應(yīng)的的森林中結(jié)點(diǎn)點(diǎn)為葉子結(jié)點(diǎn)點(diǎn)的條件是該該結(jié)點(diǎn)在森林林中既沒有孩孩子也沒有右右兄弟結(jié)點(diǎn)。5將題5圖所所示的二叉樹樹轉(zhuǎn)換成相應(yīng)應(yīng)的森林。HHGDE FBACC(題5圖)【解答】森林：AABHEGDCF6證明：在結(jié)結(jié)點(diǎn)數(shù)多于11的哈夫曼樹樹中不存在度度為1的結(jié)點(diǎn)點(diǎn)。證明：由哈夫曼曼樹的構(gòu)造過過程可知，哈哈夫曼樹的每每一分支結(jié)點(diǎn)點(diǎn)都是由兩棵棵子樹合并產(chǎn)產(chǎn)生的新結(jié)點(diǎn)點(diǎn)，其度必為為2，所以哈夫夫曼樹中不存存在度為1的結(jié)點(diǎn)。7證明：若哈哈夫曼樹中有有n個(gè)葉結(jié)點(diǎn)點(diǎn)，則樹中共共有2n11個(gè)結(jié)點(diǎn)。證明：n個(gè)葉結(jié)結(jié)點(diǎn)，需經(jīng)nn-1次合并并

43、形成哈夫曼曼樹，而每次次合并產(chǎn)生一一個(gè)分支結(jié)點(diǎn)點(diǎn)，所以樹中中共有2n-1個(gè)結(jié)點(diǎn)。8證明：由二二叉樹的前序序序列和中序序序列可以唯唯一地確定一一棵二叉樹。證明：給定二叉叉樹結(jié)點(diǎn)的前前序序列和對(duì)對(duì)稱序（中序序）序列，可可以唯一確定定該二叉樹。因因?yàn)榍靶蛐蛄辛械牡谝粋€(gè)元元素是根結(jié)點(diǎn)點(diǎn)，該元素將將二叉樹中序序序列分成兩兩部分，左邊邊（設(shè)l個(gè)元素）表表示左子樹，若若左邊無元素素，則說明左左子樹為空；右邊（設(shè)rr個(gè)元素）是是右子樹，若若為空，則右右子樹為空。根根據(jù)前序遍歷歷中“根左子樹右子樹”的順序，則則由從第二元元素開始的ll個(gè)結(jié)點(diǎn)序列列和中序序列列根左邊的ll個(gè)結(jié)點(diǎn)序列列構(gòu)造左子樹樹，由前序序序列最后

44、r個(gè)元素序列列與中序序列列根右邊的rr個(gè)元素序列列構(gòu)造右子樹樹。9已知一棵度度為m的樹中中有n1個(gè)度為1的的結(jié)點(diǎn)，n22個(gè)度為2的的結(jié)點(diǎn)，nm個(gè)度為m的的結(jié)點(diǎn)，問該該樹中共有多多少個(gè)葉子結(jié)結(jié)點(diǎn)？有多少少個(gè)非終端結(jié)結(jié)點(diǎn)？解：設(shè)樹中共有有n個(gè)結(jié)點(diǎn)，n0個(gè)葉結(jié)點(diǎn)，那那么n=n0+n11+nm (1)樹中除根結(jié)點(diǎn)外外，每個(gè)結(jié)點(diǎn)點(diǎn)對(duì)應(yīng)著一個(gè)個(gè)分支，而度度為k的結(jié)點(diǎn)發(fā)出出k個(gè)分支，所所以： n=n1+2*n2+m*nm+1 (2)由(1)、(22)可知n0= n2+2*n3+3*n4+(mm-1)*nnm+110在具有nn（n1）個(gè)個(gè)結(jié)點(diǎn)的樹中中，深度最小小的那棵樹其其深度是多少少？它共有多多少葉子和非非

45、葉子結(jié)點(diǎn)？深度最大的的那棵樹其深深度是多少？它共有多少少葉子和非葉葉子結(jié)點(diǎn)？2; n-1; 1; nn; 1, n-111設(shè)高度為為h的二叉樹樹上只有度為為0和度為22的結(jié)點(diǎn)，問問該二叉樹的的結(jié)點(diǎn)數(shù)可能能達(dá)到的最大大值和最小值值。最大值：2h-1； 最小值：2hh-112求表達(dá)式式： abb*(cdd)e/ff的波蘭式（前前綴式）和逆逆波蘭式（后后綴式）。波蘭式： - + a * b c d / e f 逆波蘭式：a b cc d - * + ee f / -13畫出和下下列已知序列列對(duì)應(yīng)的樹TT：樹的先根次序訪訪問序列為：GFKDAAIEBCHHJ；樹的后根訪問次次序?yàn)椋篋IIAEKFCCJ

46、HBG?！窘獯稹繉?duì)應(yīng)的的二叉樹和樹樹分別如下左左、右圖所示示：GBGBIEADKFCHJGBIEADKFCHJ14畫出和下下列已知序列列對(duì)應(yīng)的森林林F：森林的先根次序序訪問序列為為：ABCDDEFGHIIJKL；森林的后根訪問問次序?yàn)椋篊CBEFDGGAJIKLLH。AABDGCEFHIKJL15畫出和下下列已知序列列對(duì)應(yīng)的樹TT：二叉樹的層次訪訪問序列為：ABCDEEFGHIJJ；二叉樹的中序訪訪問次序?yàn)椋篋BGEHHJACIFF?！窘獯稹緼ABCDEFGHIJ按層次遍歷，第第一個(gè)結(jié)點(diǎn)（若若樹不空）為為根，該結(jié)點(diǎn)點(diǎn)在中序序列列中把序列分分成左右兩部部分左子樹和右右子樹。若左左子樹不空，層層次

47、序列中第第二個(gè)結(jié)點(diǎn)左左子樹的根；若左子樹為為空，則層次次序列中第二二個(gè)結(jié)點(diǎn)右子子樹的根。對(duì)對(duì)右子樹也作作類似的分析析。層次序列列的特點(diǎn)是：從左到右每每個(gè)結(jié)點(diǎn)或是是當(dāng)前情況下下子樹的根或或是葉子。16假設(shè)用于于通信的電文文由字符集a,b,cc,d,e,f,g中中的字母構(gòu)成成。它們?cè)陔婋娢闹谐霈F(xiàn)的的頻度分別為為0.311,0.166,0.100,0.088,0.111,0.200,0.044,（1）為這7個(gè)個(gè)字母設(shè)計(jì)哈哈夫曼編碼。（2）對(duì)這7個(gè)個(gè)字母進(jìn)行等等長編碼，至至少需要幾位位二進(jìn)制數(shù)？哈夫曼編碼碼比等長編碼碼使電文1.000.590.410.280.210.121.000.590.410.2

48、80.210.120.310.160.800.400.200.100.11111111（1）哈夫曼樹樹：a：10b：110c：010d：1110e：011f：00g：1111（2）對(duì)這7個(gè)個(gè)字母進(jìn)行等等長編碼，至至少需要3位位二進(jìn)制數(shù)。等長編碼的平均均長度：0.31*3+0.166*3+0.100*3+0.088*3+0.111*3+0.200*3+0.044*3=3哈夫曼編碼：00.31*22+0.166*3+0.100*3+0.088*4+0.111*3+0.200*2+0.044*4=2.54哈夫曼編碼比等等長編碼使電電文總長壓縮縮了：1 - 2.544/3=155.33%5.3.4 算

49、算法設(shè)計(jì)題1給定一棵用用二叉鏈表表表示的二叉樹樹，其根指針針為roott，試寫出求求二叉樹結(jié)點(diǎn)點(diǎn)的數(shù)目的算算法?！咎崾尽坎捎眠f遞歸算法實(shí)現(xiàn)現(xiàn)。二叉樹結(jié)點(diǎn)的數(shù)目二叉樹結(jié)點(diǎn)的數(shù)目0 當(dāng)二叉樹為空左子樹結(jié)點(diǎn)數(shù)目右子樹結(jié)點(diǎn)數(shù)目1 當(dāng)二叉樹非空int couunt(BiiTree root) iff (rooot=NUULL)returrn (0); elsee returrn (coount(rroot-lchilld)+coount(rroot-rchilld)+1);2請(qǐng)?jiān)O(shè)計(jì)一個(gè)個(gè)算法，要求求該算法把二二叉樹的葉結(jié)結(jié)點(diǎn)按從左至至右的順序鏈鏈成一個(gè)單鏈鏈表。二叉樹樹按lchiild-rcchild方

50、方式存儲(chǔ)，鏈鏈接時(shí)用葉結(jié)結(jié)點(diǎn)的rchhild域存存放鏈指針?！咎崾尽窟@是一一個(gè)非常典型型的基于二叉叉樹遍歷算法法，通過遍歷歷找到各個(gè)葉葉子結(jié)點(diǎn)，因因?yàn)椴徽撉靶蛐虮闅v、中序序遍歷和后序序遍歷，訪問問葉子結(jié)點(diǎn)的的相對(duì)順序都都是相同的，即即都是從左至至右。而題目目要求是將二二叉樹中的葉葉子結(jié)點(diǎn)按從從左至右順序序建立一個(gè)單單鏈表，因此此，可以采用用三種遍歷中中的任意一種種方法遍歷。這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點(diǎn)指針pre，初始為空。第一個(gè)葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時(shí)，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。LinkLisst heaad,pree=NUL

51、LL;/*全局變量量*/LinkLisst InOOrder(BiTreee T) /*中序遍歷歷二叉樹T，將將葉子結(jié)點(diǎn)從從左到右鏈成成一個(gè)單鏈表表，表頭指針針為headd*/ if(TT) InOrdder(T-lchhild);/*中序遍歷歷左子樹*/if (T-lchilld=NUULL & T-rchhild=NULL)/*當(dāng)前是葉葉子結(jié)點(diǎn)*/if (pree=NULLL) head=T; pre=T; /*處理第一一個(gè)葉子結(jié)點(diǎn)點(diǎn)*/else pre-rchilld=T; pre=T; /*將葉子結(jié)結(jié)點(diǎn)鏈入鏈表表*/InOrderr(T-rchhild);/*中序遍歷歷右子樹*/pre

52、-rcchild=NULL;/*設(shè)置鏈表表尾結(jié)點(diǎn)*/return(head); 3給定一棵用用二叉鏈表表表示的二叉樹樹，其根指針針為roott，試寫出求求二叉樹的深深度的算法。【提示】采取遞遞歸算法。int Heiight(BBiTreee rooot) intt hl,hhr;if (rooot=NULLL) retturn(00);else hl=Heeight(root-lchilld); hr=Heigght(rooot-rrchildd);if (hlhr) rreturnn (hl+1); else reeturn(hr+1); 4給定一棵用用二叉鏈表表表示的二叉樹樹，其根指針針為

53、roott，試求二叉叉樹各結(jié)點(diǎn)的的層數(shù)?！咎崾尽坎捎孟认刃蜻f歸遍歷歷算法實(shí)現(xiàn)。二叉樹結(jié)點(diǎn)的層次數(shù)二叉樹結(jié)點(diǎn)的層次數(shù)1當(dāng)結(jié)點(diǎn)為根結(jié)點(diǎn)其雙親結(jié)點(diǎn)的層次數(shù)1當(dāng)結(jié)點(diǎn)非根結(jié)點(diǎn)void ffun (BBiTreee rooot, innt n) if (t=NUULL) retuurn;else printtf(“%d”,n);fun(rooot-lcchild,n+1);fun(rooot-rcchild,n+1); 5給定一棵用用二叉鏈表表表示的二叉樹樹，其根指針針為roott，試寫出將將二叉樹中所所有結(jié)點(diǎn)的左左、右子樹相相互交換的算算法?！咎崾尽吭O(shè)rooot 為一棵用用二叉鏈表存存儲(chǔ)的二叉樹樹，則交

54、換各各結(jié)點(diǎn)的左右右子樹的運(yùn)算算可基于后序序遍歷實(shí)現(xiàn)：交換左子樹樹上各結(jié)點(diǎn)的的左右子樹；交換左子樹樹上各結(jié)點(diǎn)的的左右子樹；再交換根結(jié)結(jié)點(diǎn)的左右子子樹。void EExchannge(BiTree rooot) BiTTNode *p;if (rooot) Exchannge(roott-lchhild);Exchangge(root-rchilld);p=root-lchiild; rooot-llchildd=root-rchilld;root-rrchildd=p;6一棵具有nn個(gè)結(jié)點(diǎn)的完完全二叉樹采采用順序結(jié)構(gòu)構(gòu)存儲(chǔ)，試設(shè)設(shè)計(jì)非遞歸算算法對(duì)其進(jìn)行行先序遍歷?！咎崾尽慷鏄錁涞捻樞虼鎯?chǔ)儲(chǔ)是按

55、完全二二叉樹的順序序存儲(chǔ)格式按按層次存儲(chǔ)的的，雙親結(jié)點(diǎn)點(diǎn)與子女結(jié)點(diǎn)點(diǎn)的下標(biāo)間有有確定的關(guān)系系。對(duì)順序存存儲(chǔ)結(jié)構(gòu)的二二叉樹進(jìn)行先先序遍歷，與與二叉鏈表存存放二叉樹的的遍歷策略類類似。但是在在順序存儲(chǔ)結(jié)結(jié)構(gòu)下，判二二叉樹結(jié)點(diǎn)為為空的條件為為：結(jié)點(diǎn)下標(biāo)標(biāo)大于n，或結(jié)點(diǎn)值值為0（一般二叉叉樹中的“虛結(jié)點(diǎn)”）。void PPreOrdder (ddatatyype ddatann+1) /*0號(hào)單元元未用*/int stackkn ; int ttop; if(n1) rreturnn;t=1;top=00; whilee (t0) whhile (t=n&dataat!=0) Visitte(datt

56、at); sttackttop=tt; top+; t=t*22; iff (toppdaata=xx)/*若當(dāng)前結(jié)結(jié)點(diǎn)值為x，依次輸出出棧中元素的的值*/ whille (!EEmpty_Stackk(S) Pop(S,q); printtf(q-data); returrn; elsePPush_SStack(S,p);/*若當(dāng)前結(jié)結(jié)點(diǎn)值不是xx，壓棧*/ pp=p-llchildd; iff(!Emppty_Sttack(SS) Pop_SStack(S,r);/*當(dāng)棧非空空，棧頂元素素出棧，進(jìn)入入右子樹*/ p=rr-rchhild; else returrn; 8已知一棵二二叉樹的后

57、序序遍歷序列和和中序遍歷序序列，寫出可可以確定這棵棵二叉樹的算算法?！咎崾尽扛鶕?jù)后后序遍歷和中中序遍歷的特特點(diǎn)，采用遞遞歸算法實(shí)現(xiàn)現(xiàn)。void IInPostt cp iirt e和s著中中序遍歷序列列和后序遍歷歷序列，l序的/l后列點(diǎn)樹 t=(BiTNoode *) mallooc(sizzeof(BBiTNodde); t-ddata=ppostppr;m=il;whilee (inm!=ppost pr ) m+;if (mm= ill)t-lcchild=NULL ; elsee InPPost ( in, post,il,m-1,pl,pl+m-1-il, t-llchildd);

58、if (m=irr)t-rcchild=NULL; else InPoost (iin,posst,m+11,ir,ppr-ir+m,pr-1,t-rchilld);9編寫算法判判斷一棵二叉叉鏈表表示的的二叉樹是否否是完全二叉叉樹?！咎崾尽扛鶕?jù)完完全二叉樹的的定義可知，對(duì)對(duì)完全二叉樹樹按照從上到到下，從左到到右的次序遍遍歷應(yīng)滿足：若某結(jié)點(diǎn)沒沒有左孩子，則則一定無右孩孩子；若某結(jié)點(diǎn)缺缺（左或右）孩孩子，則其所所有后繼一定定無孩子。因因此，可采用用按層次遍歷歷二叉樹的方方法依次對(duì)每每個(gè)結(jié)點(diǎn)進(jìn)行行判斷。這里里增加一個(gè)標(biāo)標(biāo)志以表示所所有已掃描過過的結(jié)點(diǎn)均有有左、右孩子子，將局部判判斷結(jié)果存入入CM中，

59、CCM表示整個(gè)個(gè)二叉樹是否否是完全二叉叉樹，B為11表示到目前前為止所有結(jié)結(jié)點(diǎn)均有左右右孩子。int CommpleteeBT(BiiTree T) Iniit_Queeue(Q); /*初始化化隊(duì)列Q*/ B=1; CM=1; if (TT!=NULLL) In_Queuee(Q,T); whiile(!EEmpty_Queuee(Q)/*當(dāng)隊(duì)列列不為空時(shí)執(zhí)執(zhí)行循環(huán)*/ p=Ouut_Queeue(Q); iff(p-llchildd=NULLL) B=0;/*B=00表示缺少左左、右孩子*/ if(rrchildd!=NULLL) CM=00;/*CM=0表示不是是完全二叉樹樹*/ els

60、se CMM=B;In_Queuue(Q,pp-lchhild);/*左孩子子入隊(duì)列*/if(p-rrchildd=NULLL) BB=0; eelse In_QQueue(Q,p-rchilld);/*右孩子子入隊(duì)列*/ reeturn(CM);10有n個(gè)結(jié)結(jié)點(diǎn)的完全二二叉樹存放在在一維數(shù)組AA1.nn中，試據(jù)據(jù)此建立一棵棵用二叉鏈表表表示的二叉叉樹。BiTree Creatte(datayppe A,int i)/*n個(gè)結(jié)點(diǎn)的的完全二叉樹樹存于一維數(shù)數(shù)組A中，據(jù)此建建立以二叉鏈鏈表表示的完完全二叉樹,初始調(diào)用時(shí)時(shí),i=1*/ BiTTree TT;if (idataa=Ai;if (2*i