數(shù)據(jù)結(jié)構(gòu)及算法課后習(xí)題答案

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

2、任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中數(shù)據(jù)元素的。10在單鏈表中，要取得*個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)構(gòu)造。11靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)，又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以它存取表中第i個(gè)元素的時(shí)間與i無(wú)關(guān)。12線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。2.3.3 算法設(shè)計(jì)題1設(shè)線性表存放在向量Aarrsize的前elenum個(gè)分量中，且遞增有序。試寫(xiě)一算法，將* 插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時(shí)間復(fù)雜度。【提示】直接用題目中所給定的數(shù)據(jù)構(gòu)造順序存儲(chǔ)的思想是用物理上的相鄰表示邏輯上的相鄰，不一定將向量和表示線性表長(zhǎng)度的變量封裝成一個(gè)構(gòu)造體，因

3、為是順序存儲(chǔ)，分配的存儲(chǔ)空間是固定大小的，所以首先確定是否還有存儲(chǔ)空間，假設(shè)有，則根據(jù)原線性表中元素的有序性，來(lái)確定插入元素的插入位置，后面的元素為它讓出位置，也可以從高低標(biāo)端開(kāi)場(chǎng)一邊比擬，一邊移位然后插入* ，最后修改表示表長(zhǎng)的變量。int insert (datatype A,int *elenum,datatype *)/*設(shè)elenum為表的最大下標(biāo)*/if (*elenum=arrsize-1) return 0;/*表已滿，無(wú)法插入*/else i=*elenum;while (i=0 & Ai*)/*邊找位置邊移動(dòng)*/Ai+1=Ai;i-; Ai+1=*;/*找到的位置是插入位的

4、下一位*/ (*elenum)+;return 1;/*插入成功*/時(shí)間復(fù)雜度為O(n)。2一順序表A，其元素值非遞減有序排列，編寫(xiě)一個(gè)算法刪除順序表中多余的值一樣的元素?！咎崾尽繉?duì)順序表A，從第一個(gè)元素開(kāi)場(chǎng)，查找其后與之值一樣的所有元素，將它們刪除；再對(duì)第二個(gè)元素做同樣處理，依此類推。void delete(Seqlist *A)i=0;while(ilast)/*將第i個(gè)元素以后與其值一樣的元素刪除*/k=i+1;while(klast&A-datai=A-datak)k+;/*使k指向第一個(gè)與Ai不同的元素*/n=k-i-1;/*n表示要?jiǎng)h除元素的個(gè)數(shù)*/for(j=k;jlast;j+

5、)A-dataj-n=A-dataj;/*刪除多余元素*/A-last= A-last -n;i+;3寫(xiě)一個(gè)算法，從一個(gè)給定的順序表A中刪除值在*y(*datai是否介于*和y之間，假設(shè)是，并不立即刪除，而是用n記錄刪除時(shí)應(yīng)前移元素的位移量；假設(shè)不是，則將A-datai向前移動(dòng)n位。n用來(lái)記錄當(dāng)前已刪除元素的個(gè)數(shù)。void delete(Seqlist *A,int *,int y)i=0;n=0;while(ilast)if (A-datai=*&A-dataidatai 介于*和y之間，n自增*/else A-datai-n=A-datai;/*否則向前移動(dòng)A-datai*/i+;A-la

6、st-=n;4線性表中有n個(gè)元素，每個(gè)元素是一個(gè)字符，現(xiàn)存于向量Rn中，試寫(xiě)一算法，使R中的字符按字母字符、數(shù)字字符和其它字符的順序排列。要求利用原來(lái)的存儲(chǔ)空間，元素移動(dòng)次數(shù)最小?！咎崾尽繉?duì)線性表進(jìn)展兩次掃描，第一次將所有的字母放在前面，第二次將所有的數(shù)字放在字母之后，其它字符之前。int fch(char c)/*判斷c是否字母*/if(c=a&c=A&c=0&c=9) return (1);else return (0);void process(char Rn)low=0;high=n-1;while(lowhigh)/*將字母放在前面*/while(lowhigh&fch(Rlow)

7、low+;while(lowhigh&!fch(Rhigh) high-;if(lowhigh)k=Rlow;Rlow=Rhigh;Rhigh=k;low=low+1; high=n-1;while(lowhigh)/*將數(shù)字放在字母后面，其它字符前面*/while(lowhigh&fnum(Rlow) low+;while(lowhigh&!fnum(Rhigh) high-;if(lowhigh)k=Rlow;Rlow=Rhigh;Rhigh=k;5線性表用順序存儲(chǔ)，設(shè)計(jì)一個(gè)算法，用盡可能少的輔助存儲(chǔ)空間將順序表中前m個(gè)元素和后n個(gè)元素進(jìn)展整體互換。即將線性表：a1, a2, , am,

8、b1, b2, , bn改變?yōu)椋篵1, b2, , bn , a1, a2, , am?！咎崾尽勘葦Mm和n的大小，假設(shè)mn，則將表中元素依次前移m次；否則,將表中元素依次后移n次。voidprocess(Seqlist *L,int m,int n)if(m=n)for(i=1;idata0;for(k=1;klast;k+)L-datak-1=L-datak;L-dataL-last=*;else for(i=1;idataL-last;for(k=L-last-1;k=0;k-)L-datak+1=L-datak;L-data0=*;6帶頭結(jié)點(diǎn)的單鏈表L中的結(jié)點(diǎn)是按整數(shù)值遞增排列的，試寫(xiě)一

9、算法，將值為* 的結(jié)點(diǎn)插入到表L中，使得L仍然遞增有序，并且分析算法的時(shí)間復(fù)雜度。LinkList insert(LinkList L,int *)p=L;while(p-ne*t&*p-ne*t-data)p=p-ne*t;/*尋找插入位置*/s=(LNode *)malloc(sizeof(LNode);/*申請(qǐng)結(jié)點(diǎn)空間*/s-data=*; /*填裝結(jié)點(diǎn)*/s-ne*t=p-ne*t;p-ne*t=s;/*將結(jié)點(diǎn)插入到鏈表中*/return(L); 7假設(shè)有兩個(gè)已排序遞增的單鏈表A和B，編寫(xiě)算法將它們合并成一個(gè)鏈表C而不改變其排序性。LinkList bine(LinkList A, L

10、inkList B)C=A;rc=C;pa=A-ne*t;/*pa指向表A的第一個(gè)結(jié)點(diǎn)*/pb=B-ne*t;/*pb指向表B的第一個(gè)結(jié)點(diǎn)*/free(B);/*釋放B的頭結(jié)點(diǎn)*/while(pa&pb)/*將pa、pb所指向結(jié)點(diǎn)中，值較小的一個(gè)插入到鏈表C的表尾*/if(pa-datadata)rc-ne*t=pa;rc=pa;pa=pa-ne*t;elserc-ne*t=pb;rc=pb;pb=pb-ne*t;if(pa)rc-ne*t=pa;elserc-ne*t=pb;/*將鏈表A或B中剩余的局部到鏈表C的表尾*/return(C);8假設(shè)長(zhǎng)度大于1的循環(huán)單鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針

11、，p為指向該鏈表中*一結(jié)點(diǎn)的指針，編寫(xiě)算法刪除該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)?！咎崾尽坷醚h(huán)單鏈表的特點(diǎn)，通過(guò)s指針可循環(huán)找到其前驅(qū)結(jié)點(diǎn)p及p的前驅(qū)結(jié)點(diǎn)q，然后可刪除結(jié)點(diǎn)*p。viod delepre(LNode *s)LNode *p, *q;p=s;while (p-ne*t!=s)q=p; p=p-ne*t;q-ne*t=s;free(p);9兩個(gè)單鏈表A和B分別表示兩個(gè)集合，其元素遞增排列，編寫(xiě)算法求出A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲(chǔ)。【提示】交集指的是兩個(gè)單鏈表的元素值一樣的結(jié)點(diǎn)的集合，為了操作方便，先讓單鏈表C帶有一個(gè)頭結(jié)點(diǎn)，最后將其刪除掉。算法中指針p用來(lái)指向A中的當(dāng)前結(jié)

12、點(diǎn)，指針q用來(lái)指向B中的當(dāng)前結(jié)點(diǎn)，將其值進(jìn)展比擬，兩者相等時(shí)，屬于交集中的一個(gè)元素，兩者不等時(shí)，將其較小者跳過(guò)，繼續(xù)后面的比擬。LinkList Intersect(LinkList A, LinkList B)LNode *q, *p, *r, *s; LinkList C;C= (LNode *)malloc(sizeof(LNode);C-ne*t=NULL;r=C;p=A; q=B;while (p & q )if (p-datadata) p=p-ne*t;elseif (p-data=q-data)s=(LNode *)malloc(sizeof(LNode);s-data=p-d

13、ata;r-ne*t=s;r=s;p=p-ne*t;q=q-ne*t;else q=q-ne*t;r-ne*t=NULL;C=C-ne*t;return C;10設(shè)有一個(gè)雙向鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和ne*t域外，還有一個(gè)訪問(wèn)頻度f(wàn)req域，在鏈表被起用之前，該域的值初始化為零。每當(dāng)在鏈表進(jìn)展一次Locata(L,*)運(yùn)算后，令值為*的結(jié)點(diǎn)中的freq域增1，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問(wèn)頻度的非遞增序列排列，以便使頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭。試寫(xiě)一個(gè)滿足上述要求的Locata(L,*)算法。【提示】在定位操作的同時(shí)，需要調(diào)整鏈表中結(jié)點(diǎn)的次序：每次進(jìn)展定位操作后，要查看所查找

14、結(jié)點(diǎn)的freq域，將其同前面結(jié)點(diǎn)的freq域進(jìn)展比擬，同時(shí)進(jìn)展結(jié)點(diǎn)次序的調(diào)整。typedef struct dnodedatatype data;int freq;struct DLnode *prior,*ne*t;DLnode,*DLinkList;DlinkList Locate(DLinkList L,datatype *)p=L-ne*t;while(p&p-data!=*) p=p-ne*t;/*查找值為*的結(jié)點(diǎn)，使p指向它*/if(!p) return(NULL);/*假設(shè)查找失敗，返回空指針*/p-freq+;/*修改p的freq域*/while(p-prior!=L&p-pr

15、ior-freqfreq)/*調(diào)整結(jié)點(diǎn)的次序*/k=p-prior-data;p-prior-data=p-data;p-data=k;k=p-prior-freq;p-prior-freq=p-freq;p-freq=k;p=p-prior;return(p);/*返回找到的結(jié)點(diǎn)的地址*/3.3 課后習(xí)題解答 #3.3.1 選擇題1向一個(gè)棧頂指針為T(mén)op的鏈棧中插入一個(gè)p所指結(jié)點(diǎn)時(shí)，其操作步驟為C。ATop-ne*t=p;Bp-ne*t=Top-ne*t;Top-ne*t=p;Cp-ne*t=Top;Top=p; Dp-ne*t=Top;Top=Top-ne*t;2對(duì)于棧操作數(shù)據(jù)的原則是B。

16、A先進(jìn)先出 B后進(jìn)先出 C后進(jìn)后出 D不分順序3假設(shè)一個(gè)棧的入棧序列是1,2,3,n，其輸出序列為p1,p2,p3，pN,假設(shè)pN是n，則pi是D。AiBn-i C n-i+1 D不確定4表達(dá)式a*(bc)d的后綴表達(dá)式是B。Aabcd*-+ Babc-*d+ Cabc*-d+ D+-*abcd5采用順序存儲(chǔ)的兩個(gè)棧共享空間S1.m，topi代表第i個(gè)棧( i=1,2)的棧頂，棧1的底在S1，棧2的底在Sm，則棧滿的條件是B。Atop2-top1|=0 Btop1+1=top2Ctop1+top2=m Dtop1=top26一個(gè)棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是C。A

17、edcba B decba Cdceab D abcde7在一個(gè)鏈隊(duì)列中，假設(shè)f,r分別為隊(duì)首、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為B。Af-ne*t=r;f=s;Br-ne*t=s;r=s;Cs-ne*t=r;r=s;Ds-ne*t=f;f=s;8用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，在進(jìn)展刪除運(yùn)算時(shí)D。A僅修改頭指針B僅修改尾指針C頭、尾指針都要修改D頭、尾指針可能都要修改9遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為C的數(shù)據(jù)構(gòu)造。A隊(duì)列B靜態(tài)鏈表C棧D順序表10棧和隊(duì)都是C。A順序存儲(chǔ)的線性構(gòu)造B鏈?zhǔn)酱鎯?chǔ)的非線性構(gòu)造C限制存取點(diǎn)的線性構(gòu)造D限制存取點(diǎn)的非線性構(gòu)造3.3.2 判斷題1棧和

18、隊(duì)列的存儲(chǔ)，既可以采用順序存儲(chǔ)構(gòu)造，又可以采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造。2任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程。3假設(shè)輸入序列為1,2,3,4,5,6，則通過(guò)一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1。4通常使用隊(duì)列來(lái)處理函數(shù)的調(diào)用。5循環(huán)隊(duì)列通常用指針來(lái)實(shí)現(xiàn)隊(duì)列的頭尾相接。3.3.3 簡(jiǎn)答題1循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判別它的空和滿？循環(huán)隊(duì)列的優(yōu)點(diǎn)是能夠克制假溢滿現(xiàn)象。設(shè)有循環(huán)隊(duì)列sq，隊(duì)滿的判別條件為：sq-rear+1%ma*size=sq-front;或sq-num=ma*size。隊(duì)空的判別條件為：sq-rear=sq-front。2棧和隊(duì)列數(shù)據(jù)構(gòu)造各有什么特點(diǎn)，什么情況下用到棧，什么情況下用到

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

20、的所有可能的順序每輛車(chē)可能入站，可能不入站，時(shí)間也可能不等。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,43214.3 課后習(xí)題解答#4.3.1 選擇題1下面關(guān)于串的表達(dá)錯(cuò)誤的選項(xiàng)是C。A串是字符的有限序列B串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)C空串是由空格構(gòu)成的串D模式匹配是串的一種重要運(yùn)算2串的長(zhǎng)度是指B。A串中所含不同字母的個(gè)數(shù) B串中所含字符的個(gè)數(shù)C串中所含不同字符的個(gè)數(shù) D串中所含非空格字符的個(gè)數(shù)3串S=aaab,其Ne*t數(shù)組值為A。A0123 B1123 C1231 D12114二維數(shù)組M的成

21、員是6個(gè)字符每個(gè)字符占一個(gè)存儲(chǔ)單元組成的串，行下標(biāo)i的圍從0到8，列下標(biāo)j的圍從1到10，則存放M至少需要D個(gè)字節(jié)；M的第8列和第5行共占A個(gè)字節(jié)；假設(shè)M按行優(yōu)先方式存儲(chǔ)，元素M85的起始地址與當(dāng)M按列優(yōu)先方式存儲(chǔ)時(shí)的C元素的起始地址一致。1A90 B180 C240 D5402A108 B114 C54 D603AM85 BM310 CM58 DM095數(shù)組A中，每個(gè)元素的存儲(chǔ)占3個(gè)單元，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)場(chǎng)連續(xù)存放在存儲(chǔ)器，存放該數(shù)組至少需要的單元個(gè)數(shù)是C，假設(shè)該數(shù)組按行存放，元素A85的起始地址是D，假設(shè)該數(shù)組按列存放，元素A85的起始地址是B。1A80

22、 B100 C240 D2702ASA+141 BSA+144 CSA+222 DSA+2253ASA+141 BSA+180 CSA+117 DSA+2256稀疏矩陣采用壓縮存儲(chǔ)，一般有C兩種方法。A二維數(shù)組和三維數(shù)組 B三元組和散列C三元組表和十字鏈表 D散列和十字鏈表4.3.2 判斷題1串相等是指兩個(gè)串的長(zhǎng)度相等。2KMP算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)變小。3稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。4數(shù)組是線性構(gòu)造的一種推廣，因此與線性表一樣，可以對(duì)它進(jìn)展插入，刪除等操作。5假設(shè)采用三元組存儲(chǔ)稀疏矩陣，把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算。6假設(shè)一個(gè)廣

23、義表的表頭為空表，則此廣義表亦為空表。7所謂取廣義表的表尾就是返回廣義表中最后一個(gè)元素。4.3.3 簡(jiǎn)答題1KMP算法較樸素的模式匹配算法有哪些改良KMP算法主要優(yōu)點(diǎn)是主串指針不回溯。當(dāng)主串很大不能一次讀入存且經(jīng)常發(fā)生局部匹配時(shí)，KMP算法的優(yōu)點(diǎn)更為突出。2設(shè)字符串S=aabaabaabaac，P=aabaac。1給出S和P的ne*t值和ne*tval值；2假設(shè)S作主串，P作模式串，試給出利用KMP算法的匹配過(guò)程。【解答】 1S的ne*t與ne*tval值分別為9和9，p的ne*t與ne*tval值分別為012123和002003。 2利用BF算法的匹配過(guò)程： 利用KMP算法的匹配過(guò)程：第一趟

24、匹配：aabaabaabaac 第一趟匹配：aabaabaabaacaabaac(i=6,j=6) aabaac(i=6,j=6) 第二趟匹配：aabaabaabaac 第二趟匹配：aabaabaabaac aa(i=3,j=2) (aa)baac 第三趟匹配：aabaabaabaac 第三趟匹配：aabaabaabaac a(i=3,j=1) (成功) (aa)baac第四趟匹配：aabaabaabaac aabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaac a(i=6,j=1)第七趟匹配：aabaabaabaac(成功

25、) aabaac(i=13,j=7)3假設(shè)按行優(yōu)先存儲(chǔ)整數(shù)數(shù)組A9358時(shí)，第一個(gè)元素的字節(jié)地址是100，每個(gè)整數(shù)占個(gè)字節(jié)。問(wèn)以下元素的存儲(chǔ)地址是什么？(1) a0000 (2)a1111 (3)a3125 (4)a8247【解答】(1) LOC( a0000)=100(2) LOC( a1111)=100+(3*5*8*1+5*8*1+8*1+1)*4=776(3) LOC( a3125)=100+(3*5*8*3+5*8*1+8*2+5) *4=1784(4) LOC( a8247)= 100+(3*5*8*8+5*8*2+8*4+7) *4=48164假設(shè)一個(gè)準(zhǔn)對(duì)角矩陣：aa11 a12

26、a21 a22a33 a34a43 a44 . aij a2m-1,2m-1 a2m-1,2m a2m,2m-1 a2m,2m 按以下方式存儲(chǔ)于一維數(shù)組B4m中m為一個(gè)整數(shù)：012345 6 k 4m-1 4ma 11a 12a21a22a33a34a43aija2m-1,2ma2m,2m-1a2m,2m寫(xiě)出下標(biāo)轉(zhuǎn)換函數(shù)k=f(i,j)?！窘獯稹坑深}目可知，每一行有兩個(gè)非0元素。當(dāng)i為奇數(shù)時(shí)，第i行的元素為：ai,i、ai,(i+1)，此時(shí)k=2*(i-1)+j-i=i+j-2當(dāng)i為偶數(shù)時(shí)，第i行的元素為：ai,(i-1)、ai,i，此時(shí)k=2*(i-1)+j-I+1=i+j-1綜上所述，k=

27、i+j-i%2-1。5設(shè)有nn的帶寬為3的帶狀矩陣A，將其3條對(duì)角線上的元素存于數(shù)組B3n中，使得元素Buv=aij，試推導(dǎo)出從i,j到 (u,v)的下標(biāo)變換公式?！窘獯稹縰=j-i+1v=j-16現(xiàn)有如下的稀疏矩陣A如下圖，要求畫(huà)出以下各種表示方法。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 0 091 0 0 0 0 00 0 28 0 0 0【解答】1三元組表表示法:i j v1234567 4 221 6 -152 2 132 3 33 4 -65 1 916 3 282十字鏈表法

28、：0012345012345519123334-61422632816-1522137畫(huà)出以下廣義表的頭尾表示存儲(chǔ)構(gòu)造示意圖。1A=(a,b,c),d,(a,b,c)2B=(a,(b,(c,d),e),f)1111111 1 1 d0 a1 b1 c211111 1 1 0 f0 a0 b0 c1 10 c0 d5.3 課后習(xí)題解答 5.3.1 選擇題1以下說(shuō)確的是C。A二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2 B二叉樹(shù)的度為2C一棵二叉樹(shù)的度可小于2 D任何一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為22以二叉鏈表作為二叉樹(shù)的存儲(chǔ)構(gòu)造，在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中n0，空鏈域的個(gè)數(shù)為C。A2n-1Bn-1Cn+1D

29、2n+13線索化二叉樹(shù)中，*結(jié)點(diǎn)*p沒(méi)有孩子的充要條件是B。Ap-lchild=NULL Bp-ltag=1且p-rtag=1Cp-ltag=0 Dp-lchild=NULL 且p-ltag=14如果結(jié)點(diǎn)A有3個(gè)兄弟,而且B是A的雙親,則B的度是B。A3 B4 C5 D1 5*二叉樹(shù)T有n個(gè)結(jié)點(diǎn),設(shè)按*種順序?qū)中的每個(gè)結(jié)點(diǎn)進(jìn)展編號(hào)，編號(hào)值為1,2,.n。且有如下性質(zhì):T中任意結(jié)點(diǎn)v,其編號(hào)等于左子樹(shù)上的最小編號(hào)減,而v的右子樹(shù)的結(jié)點(diǎn)中,其最小編號(hào)等于v左子樹(shù)上結(jié)點(diǎn)的最大編號(hào)加，這是按B編號(hào)的。A 中序遍歷序列B 先序遍歷序列 C 后序遍歷序列 D 層次順序6設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的

30、二叉樹(shù)，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn),B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有C個(gè)。An-1 B n C n+1 Dn+2 7一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是C。A 500 B 501 C490D4958設(shè)森林F中有三棵樹(shù)，第一，第二，第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為N1，N2和N3。與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是D。AN1 BN1+N2 CN2 DN2+N39任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序、后序遍歷序列中的相對(duì)次序A。A不發(fā)生改變 B 發(fā)生改變 C 不能確定 D 以上都不對(duì)10假設(shè)一棵二叉樹(shù)的后序遍歷序列為dabec，中序遍歷序列為debac，則先序遍歷序列為D。Acbed Bd

31、ecab Cdeabc Dcedba11假設(shè)一棵二叉樹(shù)的先序遍歷序列為abdgcefh，中序遍歷的序列為dgbaechf，則后序遍歷的結(jié)果為D。 A gcefhaB gdbecfhaC bdgaechfDgdbehfca12一棵非空二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足B。A所有的結(jié)點(diǎn)均無(wú)左孩子 B所有的結(jié)點(diǎn)均無(wú)右孩子C只有一個(gè)葉子結(jié)點(diǎn) D是一棵滿二叉樹(shù)13引入線索二叉樹(shù)的目的是A。A加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B為了能在二叉樹(shù)中方便的進(jìn)展插入與刪除C為了能方便的找到雙親D使二叉樹(shù)的遍歷結(jié)果唯一14設(shè)高度為h的二叉樹(shù)上只有度為和度為的結(jié)點(diǎn)，則此類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)

32、至少為B。A2*h B 2*h-1 C 2*h+1 Dh+115一個(gè)具有567個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為D。A9 B10 C9至566之間 D10至567之間16給一個(gè)整數(shù)集合3，5，6，7，9，與該整數(shù)集合對(duì)應(yīng)的哈夫曼樹(shù)是B。A B C D937693765 3567979536765395.3.2 判斷題1二叉樹(shù)是樹(shù)的特殊形式。2由樹(shù)轉(zhuǎn)換成二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。3先根遍歷一棵樹(shù)和先序遍歷與該樹(shù)對(duì)應(yīng)的二叉樹(shù)，其結(jié)果不同。4先根遍歷森林和先序遍歷與該森林對(duì)應(yīng)的二叉樹(shù)，其結(jié)果不同。5完全二叉樹(shù)中，假設(shè)一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是葉子。6對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為log2N1。7假設(shè)

33、一個(gè)結(jié)點(diǎn)是*二叉樹(shù)子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。8假設(shè)一個(gè)結(jié)點(diǎn)是*二叉樹(shù)子樹(shù)的中序遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的后序遍歷序列中的第一個(gè)結(jié)點(diǎn)。9不使用遞歸也可實(shí)現(xiàn)二叉樹(shù)的先序、中序和后序遍歷。10先序遍歷二叉樹(shù)的序列中，任何結(jié)點(diǎn)的子樹(shù)的所有結(jié)點(diǎn)不一定跟在該結(jié)點(diǎn)之后。11先序和中序遍歷用線索樹(shù)方式存儲(chǔ)的二叉樹(shù)，不必使用棧。12在后序線索二叉樹(shù)中，在任何情況下都能夠很方便地找到任意結(jié)點(diǎn)的后繼。13哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。14在哈夫曼編碼中，出現(xiàn)頻率一樣的字符編碼長(zhǎng)度也一定一樣。15用一維數(shù)組存放二叉樹(shù)

34、時(shí)，總是以先序遍歷存儲(chǔ)結(jié)點(diǎn)。16由先序序列和后序序列能唯一確定一棵二叉樹(shù)。17由先序序列和中序序列能唯一確定一棵二叉樹(shù)。18對(duì)一棵二叉樹(shù)進(jìn)展層次遍歷時(shí)，應(yīng)借助于一個(gè)棧。19完全二叉樹(shù)可采用順序存儲(chǔ)構(gòu)造實(shí)現(xiàn)存儲(chǔ)，非完全二叉樹(shù)則不能。20滿二叉樹(shù)一定是完全二叉樹(shù)，反之未必。5.3.3 簡(jiǎn)答題1一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別？樹(shù)與二叉樹(shù)之間有何區(qū)別？【解答】二叉樹(shù)是有序樹(shù)，度為2的樹(shù)是無(wú)序樹(shù)，二叉樹(shù)的度不一定是2。ADBADBGEHCF(圖 1)2對(duì)于圖1所示二叉樹(shù)，試給出：1它的順序存儲(chǔ)構(gòu)造示意圖；2它的二叉鏈表存儲(chǔ)構(gòu)造示意圖；3它的三叉鏈表存儲(chǔ)構(gòu)造示意圖。【解答】1順序存儲(chǔ)構(gòu)造示意圖：ABC

35、DEFGH2二叉鏈表存儲(chǔ)構(gòu)造示意圖： 3三叉鏈表存儲(chǔ)構(gòu)造示意圖：A A BC D E F G H ABC D E F G H IDIDEFGCBANMKJH(圖 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畫(huà)出圖3所示的森林經(jīng)轉(zhuǎn)換后所對(duì)應(yīng)

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

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

38、2個(gè)度為2的結(jié)點(diǎn)，nm個(gè)度為m的結(jié)點(diǎn)，問(wèn)該樹(shù)中共有多少個(gè)葉子結(jié)點(diǎn)？有多少個(gè)非終端結(jié)點(diǎn)？解：設(shè)樹(shù)中共有n個(gè)結(jié)點(diǎn)，n0個(gè)葉結(jié)點(diǎn)，則n=n0+n1+nm (1)樹(shù)中除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)著一個(gè)分支，而度為k的結(jié)點(diǎn)發(fā)出k個(gè)分支，所以： n=n1+2*n2+m*nm+1 (2)由(1)、(2)可知n0= n2+2*n3+3*n4+(m-1)*nm+110在具有nn1個(gè)結(jié)點(diǎn)的樹(shù)中，深度最小的那棵樹(shù)其深度是多少？它共有多少葉子和非葉子結(jié)點(diǎn)？深度最大的那棵樹(shù)其深度是多少？它共有多少葉子和非葉子結(jié)點(diǎn)？2; n-1; 1; n; 1, n-111設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，問(wèn)該二叉樹(shù)的結(jié)點(diǎn)數(shù)可

39、能到達(dá)的最大值和最小值。最大值：2h-1；最小值：2h-112求表達(dá)式： ab*(cd)e/f的波蘭式前綴式和逆波蘭式后綴式。波蘭式： - + a * b c d / e f 逆波蘭式：a b c d - * + e f / -13畫(huà)出和以下序列對(duì)應(yīng)的樹(shù)T：樹(shù)的先根次序訪問(wèn)序列為：GFKDAIEBCHJ；樹(shù)的后根訪問(wèn)次序?yàn)椋篋IAEKFCJHBG?！窘獯稹繉?duì)應(yīng)的二叉樹(shù)和樹(shù)分別如下左、右圖所示：GBGBIEADKFCHJGBIEADKFCHJ14畫(huà)出和以下序列對(duì)應(yīng)的森林F：森林的先根次序訪問(wèn)序列為：ABCDEFGHIJKL；森林的后根訪問(wèn)次序?yàn)椋篊BEFDGAJIKLH。AABDGCEFHIKJ

40、L15畫(huà)出和以下序列對(duì)應(yīng)的樹(shù)T：二叉樹(shù)的層次訪問(wèn)序列為：ABCDEFGHIJ；二叉樹(shù)的中序訪問(wèn)次序?yàn)椋篋BGEHJACIF?！窘獯稹緼ABCDEFGHIJ按層次遍歷，第一個(gè)結(jié)點(diǎn)假設(shè)樹(shù)不空為根，該結(jié)點(diǎn)在中序序列中把序列分成左右兩局部左子樹(shù)和右子樹(shù)。假設(shè)左子樹(shù)不空，層次序列中第二個(gè)結(jié)點(diǎn)左子樹(shù)的根；假設(shè)左子樹(shù)為空，則層次序列中第二個(gè)結(jié)點(diǎn)右子樹(shù)的根。對(duì)右子樹(shù)也作類似的分析。層次序列的特點(diǎn)是：從左到右每個(gè)結(jié)點(diǎn)或是當(dāng)前情況下子樹(shù)的根或是葉子。16假設(shè)用于通信的電文由字符集a,b,c,d,e,f,g中的字母構(gòu)成。它們?cè)陔娢闹谐霈F(xiàn)的頻度分別為0.31,0.16,0.10,0.08,0.11,0.20,0.04

41、,1為這7個(gè)字母設(shè)計(jì)哈夫曼編碼。2對(duì)這7個(gè)字母進(jìn)展等長(zhǎng)編碼，至少需要幾位二進(jìn)制數(shù)？哈夫曼編碼比等長(zhǎng)編碼使電文1.000.591.000.590.410.280.210.120.310.160.800.400.200.100.111111111哈夫曼樹(shù)：a：10b：110c：010d：1110e：011f：00g：11112對(duì)這7個(gè)字母進(jìn)展等長(zhǎng)編碼，至少需要3位二進(jìn)制數(shù)。等長(zhǎng)編碼的平均長(zhǎng)度：0.31*3+0.16*3+0.10*3+0.08*3+0.11*3+0.20*3+0.04*3=3哈夫曼編碼：0.31*2+0.16*3+0.10*3+0.08*4+0.11*3+0.20*2+0.04*4

42、=2.54哈夫曼編碼比等長(zhǎng)編碼使電文總長(zhǎng)壓縮了：1 - 2.54/3=15.33%5.3.4 算法設(shè)計(jì)題1給定一棵用二叉鏈表表示的二叉樹(shù)，其根指針為root，試寫(xiě)出求二叉樹(shù)結(jié)點(diǎn)的數(shù)目的算法?！咎崾尽坎捎眠f歸算法實(shí)現(xiàn)。二叉樹(shù)結(jié)點(diǎn)的數(shù)目二叉樹(shù)結(jié)點(diǎn)的數(shù)目0 當(dāng)二叉樹(shù)為空左子樹(shù)結(jié)點(diǎn)數(shù)目右子樹(shù)結(jié)點(diǎn)數(shù)目1 當(dāng)二叉樹(shù)非空int count(BiTree root)if (root=NULL)return (0); else return (count(root-lchild)+count(root-rchild)+1);2請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，要求該算法把二叉樹(shù)的葉結(jié)點(diǎn)按從左至右的順序鏈成一個(gè)單鏈表。二叉樹(shù)按lc

43、hild-rchild方式存儲(chǔ)，時(shí)用葉結(jié)點(diǎn)的rchild域存放鏈指針?！咎崾尽窟@是一個(gè)非常典型的基于二叉樹(shù)遍歷算法，通過(guò)遍歷找到各個(gè)葉子結(jié)點(diǎn)，因?yàn)椴还芮靶虮闅v、中序遍歷和后序遍歷，訪問(wèn)葉子結(jié)點(diǎn)的相對(duì)順序都是一樣的，即都是從左至右。而題目要將二叉樹(shù)中的葉子結(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為空。LinkList head,pre=NULL;/*全局變量*/LinkList InOrde

44、r(BiTree T)/*中序遍歷二叉樹(shù)T，將葉子結(jié)點(diǎn)從左到右鏈成一個(gè)單鏈表，表頭指針為head*/if(T)InOrder(T-lchild);/*中序遍歷左子樹(shù)*/if(T-lchild=NULL & T-rchild=NULL)/*當(dāng)前是葉子結(jié)點(diǎn)*/if(pre=NULL) head=T; pre=T;/*處理第一個(gè)葉子結(jié)點(diǎn)*/elsepre-rchild=T; pre=T; /*將葉子結(jié)點(diǎn)鏈入鏈表*/InOrder(T-rchild);/*中序遍歷右子樹(shù)*/pre-rchild=NULL;/*設(shè)置鏈表尾結(jié)點(diǎn)*/return(head);3給定一棵用二叉鏈表表示的二叉樹(shù)，其根指針為roo

45、t，試寫(xiě)出求二叉樹(shù)的深度的算法。【提示】采取遞歸算法。int Height(BiTree root)int hl,hr;if (root=NULL) return(0);else hl=Height(root-lchild); hr=Height(root-rchild);if(hlhr) return (hl+1); else return(hr+1); 4給定一棵用二叉鏈表表示的二叉樹(shù)，其根指針為root，試求二叉樹(shù)各結(jié)點(diǎn)的層數(shù)?！咎崾尽坎捎孟刃蜻f歸遍歷算法實(shí)現(xiàn)。二叉樹(shù)結(jié)點(diǎn)的層次數(shù)二叉樹(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 fun (BiTree root

46、, int n)if (t=NULL) return;else printf(%d,n);fun(root-lchild,n+1);fun(root-rchild,n+1);5給定一棵用二叉鏈表表示的二叉樹(shù)，其根指針為root，試寫(xiě)出將二叉樹(shù)中所有結(jié)點(diǎn)的左、右子樹(shù)相互交換的算法?！咎崾尽吭O(shè)root 為一棵用二叉鏈表存儲(chǔ)的二叉樹(shù)，則交換各結(jié)點(diǎn)的左右子樹(shù)的運(yùn)算可基于后序遍歷實(shí)現(xiàn)：交換左子樹(shù)上各結(jié)點(diǎn)的左右子樹(shù)；交換左子樹(shù)上各結(jié)點(diǎn)的左右子樹(shù)；再交換根結(jié)點(diǎn)的左右子樹(shù)。void E*change(BiTree root) BiTNode *p;if (root) E*change(root-lchild)

47、;E*change(root-rchild);p=root-lchild; root-lchild=root-rchild;root-rchild=p;6一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)采用順序構(gòu)造存儲(chǔ)，試設(shè)計(jì)非遞歸算法對(duì)其進(jìn)展先序遍歷?！咎崾尽慷鏄?shù)的順序存儲(chǔ)是按完全二叉樹(shù)的順序存儲(chǔ)格式按層次存儲(chǔ)的，雙親結(jié)點(diǎn)與子女結(jié)點(diǎn)的下標(biāo)間有確定的關(guān)系。對(duì)順序存儲(chǔ)構(gòu)造的二叉樹(shù)進(jìn)展先序遍歷，與二叉鏈表存放二叉樹(shù)的遍歷策略類似。但是在順序存儲(chǔ)構(gòu)造下，判二叉樹(shù)結(jié)點(diǎn)為空的條件為：結(jié)點(diǎn)下標(biāo)大于n，或結(jié)點(diǎn)值為0一般二叉樹(shù)中的虛結(jié)點(diǎn)。void PreOrder (datatype datan+1) /*0號(hào)單元未用*/in

48、t stackn ; int top; if(n1) return;t=1;top=0; while (t0)while (t=n&datat!=0)Visite(datat);stacktop=t;top+;t=t*2; if (topdata=*)/*假設(shè)當(dāng)前結(jié)點(diǎn)值為*，依次輸出棧中元素的值*/while (!Empty_Stack(S) Pop(S,q);printf(q-data); return;elsePush_Stack(S,p);/*假設(shè)當(dāng)前結(jié)點(diǎn)值不是*，壓棧*/ p=p-lchild; if(!Empty_Stack(S) Pop_Stack(S,r);/*當(dāng)棧非空，棧頂元素

49、出棧，進(jìn)入右子樹(shù)*/p=r-rchild; else return; 8一棵二叉樹(shù)的后序遍歷序列和中序遍歷序列，寫(xiě)出可以確定這棵二叉樹(shù)的算法。【提示】根據(jù)后序遍歷和中序遍歷的特點(diǎn)，采用遞歸算法實(shí)現(xiàn)。void InPost 中序遍歷序列和后序遍歷序列，t=(BiTNode *) malloc(sizeof(BiTNode); t-data=postpr;m=il;while (inm!=post pr ) m+;if (m= il)t-lchild=NULL ; else InPost ( in, post,il,m-1,pl,pl+m-1-il, t-lchild); if (m=ir)t-r

50、child=NULL;else InPost (in,post,m+1,ir,pr-ir+m,pr-1,t-rchild);9編寫(xiě)算法判斷一棵二叉鏈表表示的二叉樹(shù)是否是完全二叉樹(shù)?！咎崾尽扛鶕?jù)完全二叉樹(shù)的定義可知，對(duì)完全二叉樹(shù)按照從上到下，從左到右的次序遍歷應(yīng)滿足：假設(shè)*結(jié)點(diǎn)沒(méi)有左孩子，則一定無(wú)右孩子；假設(shè)*結(jié)點(diǎn)缺左或右孩子，則其所有后繼一定無(wú)孩子。因此，可采用按層次遍歷二叉樹(shù)的方法依次對(duì)每個(gè)結(jié)點(diǎn)進(jìn)展判斷。這里增加一個(gè)標(biāo)志以表示所有已掃描過(guò)的結(jié)點(diǎn)均有左、右孩子，將局部判斷結(jié)果存入CM中，CM表示整個(gè)二叉樹(shù)是否是完全二叉樹(shù)，B為1表示到目前為止所有結(jié)點(diǎn)均有左右孩子。int pleteBT(BiT

51、ree T) Init_Queue(Q); /*初始化隊(duì)列Q*/ B=1; CM=1; if (T!=NULL) In_Queue(Q,T); while(!Empty_Queue(Q)/*當(dāng)隊(duì)列不為空時(shí)執(zhí)行循環(huán)*/ p=Out_Queue(Q); if(p-lchild=NULL) B=0;/*B=0表示缺少左、右孩子*/ if(rchild!=NULL) CM=0;/*CM=0表示不是完全二叉樹(shù)*/ else CM=B;In_Queue(Q,p-lchild);/*左孩子入隊(duì)列*/if(p-rchild=NULL) B=0; else In_Queue(Q,p-rchild);/*右孩子入

52、隊(duì)列*/ return(CM);10有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)存放在一維數(shù)組A1.n中，試據(jù)此建立一棵用二叉鏈表表示的二叉樹(shù)。BiTree Create(dataype A,inti)/*n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)存于一維數(shù)組A中，據(jù)此建立以二叉鏈表表示的完全二叉樹(shù),初始調(diào)用時(shí),i=1*/BiTree T;if (idata=Ai;if(2*in) T-lchild=NULL;elseT-lchild=Create(A,2*i);if(2*i+1n) T-rchild=NULL;elseT-rchild=Create(A,2*i+1);return (T);11編寫(xiě)算法判定兩棵二叉樹(shù)是否相似。所謂兩棵二

53、叉樹(shù)s和t相似，即要么它們都為空或都只有一個(gè)結(jié)點(diǎn)，要么它們的左右子樹(shù)都相似。【提示】?jī)煽每斩鏄?shù)或僅有根結(jié)點(diǎn)的二叉樹(shù)相似；對(duì)非空二叉樹(shù)，可判左右子樹(shù)是否相似，采用遞歸算法。intSimilar(BiTree s, BiTree t) if(s=NULL & q=NULL) return (1);else if(!s & t | s & !t) return (0);else return(Similar(s-lchild,t-lchild) & Similar(s-rchild,t-rchild)12寫(xiě)出用逆轉(zhuǎn)鏈方法對(duì)二叉樹(shù)進(jìn)展先序遍歷的算法。【提示】用逆轉(zhuǎn)鏈的方法遍歷二叉樹(shù)，不需要附加的?？?/p>

54、間，而是在遍歷過(guò)程中沿結(jié)點(diǎn)的左右子樹(shù)下降時(shí)，臨時(shí)改變結(jié)點(diǎn)lchild或者rchild的值，使之指向雙親，從而為以后的上升提供路徑，上升時(shí)再將結(jié)點(diǎn)的lchild或者rchild恢復(fù)。typedef struct tnode datatype data; int tag; /*tag的值初始為0，進(jìn)入左子樹(shù)時(shí)置1，從左子樹(shù)回來(lái)時(shí)，再恢復(fù)為0*/ struct tnode *lchild, *rchild; Bnode, *Btree;void PreOrder(Btree bt) Bnode *r, *p, *q; /*p指向當(dāng)前結(jié)點(diǎn)，r指向p的雙親，q指向要訪問(wèn)的下一結(jié)點(diǎn)*/if(bt=NULL

55、) return; p=bt; r= NULL: while( p) Visit(p);/*訪問(wèn)p所指結(jié)點(diǎn)*/ if(p-lchild)/*下降進(jìn)入左子樹(shù)*/ p-tag=1; q=p-lchild; q=p-lchild=r; r=p; p=q; else if(p-rchild)/*下降進(jìn)入右子樹(shù)*/ q=p-rchild; p-rchild=r; r=p; p=q; else /*上升*/whle(r&t-tag=0) | (r&t-tag=1&r-rchild=NULL) if(r&t-tag=0) q=r-rchild; r-rchild=p; p=r; r=q;/*從右子樹(shù)回來(lái)*/

56、else r-tag=0; q=r-lchild; r-lchild=p; p=r; r=q;/*從左子樹(shù)回來(lái)*/ if (r=NULL) return;else r-tag=0; q=r-rchild; r-rchild= r-lchild; r-lchild=p; p=q;/*從左子樹(shù)回來(lái)，準(zhǔn)備進(jìn)入右子樹(shù)*/13對(duì)以孩子兄弟鏈表表示的樹(shù)編寫(xiě)計(jì)算樹(shù)的深度的算法?！咎崾尽坎捎眠f歸算法實(shí)現(xiàn)。樹(shù)的深度樹(shù)的深度0 假設(shè)樹(shù)為空Ma*第一棵子樹(shù)的深度1，兄弟子樹(shù)的深度 假設(shè)樹(shù)非空int high(CSTree T) if (T=NULL )return ( 0 );/*假設(shè)樹(shù)為空，返回0*/else h

57、1=high (t-lchild );/*h1為T(mén)的第一棵子樹(shù)的深度*/h2=high(t-ne*tsibling );/*h2為t的兄弟子樹(shù)的深度*/return(ma*(h1+1,h2); 14對(duì)以孩子鏈表表示的樹(shù)編寫(xiě)計(jì)算樹(shù)的深度的算法。【提示】采用遞歸算法實(shí)現(xiàn)。樹(shù)的深度樹(shù)的深度1 假設(shè)根結(jié)點(diǎn)沒(méi)有子樹(shù)ma*(所有子樹(shù)的深度)1 假設(shè)根結(jié)點(diǎn)有子樹(shù)#define MA*NODE 樹(shù)中結(jié)點(diǎn)的最大個(gè)數(shù)int high(SNode tMA*NODE,int j)if(tj.firstchild=NULL) return(1);/*假設(shè)根結(jié)點(diǎn)沒(méi)有子樹(shù)*/elsep=ti.firstchild;ma*=

58、high(t,p-data);p=p-ne*tchild;while(p)h=high(t,p-data);if(hma*) ma*=h; p=p-ne*tchild;return(ma*+1);15對(duì)以雙親鏈表表示的樹(shù)編寫(xiě)計(jì)算樹(shù)的深度的算法?！咎崾尽繌拿恳粋€(gè)結(jié)點(diǎn)開(kāi)場(chǎng)，從下向上搜索至根結(jié)點(diǎn)，記錄結(jié)點(diǎn)的層次數(shù)，其中的最大值就是樹(shù)的深度。int high(PNodet , int n)/*求有n個(gè)結(jié)點(diǎn)的樹(shù)t的深度*/ ma*h=0;for (i=0 ;ima*h) ma*h=h; return(ma*h) ;6.3.1 選擇題1n條邊的無(wú)向圖的鄰接表的存儲(chǔ)中，邊結(jié)點(diǎn)的個(gè)數(shù)有A。An B2n Cn/

59、2 Dn*n2n條邊的無(wú)向圖的鄰接多重表的存儲(chǔ)中，邊結(jié)點(diǎn)的個(gè)數(shù)有A。An B2n Cn/2 Dn*n3以下哪一種圖的鄰接矩陣是對(duì)稱矩陣？B。A有向圖B無(wú)向圖 CAOV網(wǎng) DAOE網(wǎng)4最短路徑的生成算法可用C。A普里姆算法 B克魯斯卡爾算法 C迪杰斯特拉算法 D哈夫曼算法5一個(gè)無(wú)向圖的鄰接表如以下圖所示：序號(hào)序號(hào)verte*firstedge0v11v22v33v4320310111從頂點(diǎn)v0出發(fā)進(jìn)展深度優(yōu)先搜索，經(jīng)歷的結(jié)點(diǎn)順序?yàn)锽。Av0, v3, v2, v1 Bv0, v1, v2, v3 Cv0, v2, v1, v3 Dv0, v1, v3, v22從頂點(diǎn)V0出發(fā)進(jìn)展廣度優(yōu)先搜索，經(jīng)歷

60、的結(jié)點(diǎn)順序?yàn)镈。Av0, v3, v2, v1 Bv0, v1, v2, v3 Cv0, v2, v1, v3 Dv0, v1, v3, v26設(shè)有向圖n個(gè)頂點(diǎn)和e條邊，進(jìn)展拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為D。AO (nlog2e) BO (en ) CO ( elog2n) DO (n+e)7含有n個(gè)頂點(diǎn)e條邊的無(wú)向連通圖，利用Kruskal算法生成最小生成樹(shù)，其時(shí)間復(fù)雜度為A。AO (elog2e) BO (en ) CO ( elog2n) DO (nlog2n)8關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中A。A從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B從源點(diǎn)到匯點(diǎn)的最短路徑 C最長(zhǎng)的回路 D最短的回路9下面關(guān)于求關(guān)鍵路徑的說(shuō)