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

1、-. z.2.3 課后習題解答2.3.2 判斷題1線性表的邏輯順序與存儲順序總是一致的。2順序存儲的線性表可以按序號隨機存取。3順序表的插入和刪除操作不需要付出很大的時間代價，因為每次操作平均只有近一半的元素需要移動。4線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有一樣的特性，因此屬于同一數(shù)據(jù)對象。5在線性表的順序存儲構(gòu)造中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。6在線性表的鏈式存儲構(gòu)造中，邏輯上相鄰的元素在物理位置上不一定相鄰。7線性表的鏈式存儲構(gòu)造優(yōu)于順序存儲構(gòu)造。8在線性表的順序存儲構(gòu)造中，插入和刪除時移動元素的個數(shù)與該元素的位置有關(guān)。9線性表的鏈式存儲構(gòu)造是用一組

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

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

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

5、)A-dataj-n=A-dataj;/*刪除多余元素*/A-last= A-last -n;i+;3寫一個算法，從一個給定的順序表A中刪除值在*y(*datai是否介于*和y之間，假設(shè)是，并不立即刪除，而是用n記錄刪除時應前移元素的位移量；假設(shè)不是，則將A-datai向前移動n位。n用來記錄當前已刪除元素的個數(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;/*否則向前移動A-datai*/i+;A-la

6、st-=n;4線性表中有n個元素，每個元素是一個字符，現(xiàn)存于向量Rn中，試寫一算法，使R中的字符按字母字符、數(shù)字字符和其它字符的順序排列。要求利用原來的存儲空間，元素移動次數(shù)最小?！咎崾尽繉€性表進展兩次掃描，第一次將所有的字母放在前面，第二次將所有的數(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線性表用順序存儲，設(shè)計一個算法，用盡可能少的輔助存儲空間將順序表中前m個元素和后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é)點的單鏈表L中的結(jié)點是按整數(shù)值遞增排列的，試寫一

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

10、inkList B)C=A;rc=C;pa=A-ne*t;/*pa指向表A的第一個結(jié)點*/pb=B-ne*t;/*pb指向表B的第一個結(jié)點*/free(B);/*釋放B的頭結(jié)點*/while(pa&pb)/*將pa、pb所指向結(jié)點中，值較小的一個插入到鏈表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è)長度大于1的循環(huán)單鏈表中，既無頭結(jié)點也無頭指針

11、，p為指向該鏈表中*一結(jié)點的指針，編寫算法刪除該結(jié)點的前驅(qū)結(jié)點。【提示】利用循環(huán)單鏈表的特點，通過s指針可循環(huán)找到其前驅(qū)結(jié)點p及p的前驅(qū)結(jié)點q，然后可刪除結(jié)點*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兩個單鏈表A和B分別表示兩個集合，其元素遞增排列，編寫算法求出A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲。【提示】交集指的是兩個單鏈表的元素值一樣的結(jié)點的集合，為了操作方便，先讓單鏈表C帶有一個頭結(jié)點，最后將其刪除掉。算法中指針p用來指向A中的當前結(jié)

12、點，指針q用來指向B中的當前結(jié)點，將其值進展比擬，兩者相等時，屬于交集中的一個元素，兩者不等時，將其較小者跳過，繼續(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è)有一個雙向鏈表，每個結(jié)點中除有prior、data和ne*t域外，還有一個訪問頻度freq域，在鏈表被起用之前，該域的值初始化為零。每當在鏈表進展一次Locata(L,*)運算后，令值為*的結(jié)點中的freq域增1，并調(diào)整表中結(jié)點的次序，使其按訪問頻度的非遞增序列排列，以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一個滿足上述要求的Locata(L,*)算法?！咎崾尽吭诙ㄎ徊僮鞯耐瑫r，需要調(diào)整鏈表中結(jié)點的次序：每次進展定位操作后，要查看所查找

14、結(jié)點的freq域，將其同前面結(jié)點的freq域進展比擬，同時進展結(jié)點次序的調(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é)點，使p指向它*/if(!p) return(NULL);/*假設(shè)查找失敗，返回空指針*/p-freq+;/*修改p的freq域*/while(p-prior!=L&p-pr

15、ior-freqfreq)/*調(diào)整結(jié)點的次序*/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é)點的地址*/3.3 課后習題解答 #3.3.1 選擇題1向一個棧頂指針為Top的鏈棧中插入一個p所指結(jié)點時，其操作步驟為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對于棧操作數(shù)據(jù)的原則是B。

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

17、edcba B decba Cdceab D abcde7在一個鏈隊列中，假設(shè)f,r分別為隊首、隊尾指針，則插入s所指結(jié)點的操作為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é)點的單鏈表存儲隊列時，在進展刪除運算時D。A僅修改頭指針B僅修改尾指針C頭、尾指針都要修改D頭、尾指針可能都要修改9遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為C的數(shù)據(jù)構(gòu)造。A隊列B靜態(tài)鏈表C棧D順序表10棧和隊都是C。A順序存儲的線性構(gòu)造B鏈式存儲的非線性構(gòu)造C限制存取點的線性構(gòu)造D限制存取點的非線性構(gòu)造3.3.2 判斷題1棧和

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

19、隊列？棧和隊列都是操作受限的線性表，棧的運算規(guī)則是后進先出，隊列的運算規(guī)則是先進先出。棧的應用如數(shù)制轉(zhuǎn)換、遞歸算法的實現(xiàn)等，隊列的應用如樹的層次遍歷等。3什么是遞歸？遞歸程序有什么優(yōu)缺點？一個函數(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，這稱為間接遞歸。在實際應用中，多為直接遞歸，也常簡稱為遞歸。遞歸程序的優(yōu)點是程序構(gòu)造簡單、清晰，易證明其正確性。缺點是執(zhí)行中占存空間較多，運行效率低。4設(shè)有編號為1,2,3,4的四輛車，順序進入一個棧式構(gòu)造的站臺，試寫出這四輛車開出車站

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

21、員是6個字符每個字符占一個存儲單元組成的串，行下標i的圍從0到8，列下標j的圍從1到10，則存放M至少需要D個字節(jié)；M的第8列和第5行共占A個字節(jié)；假設(shè)M按行優(yōu)先方式存儲，元素M85的起始地址與當M按列優(yōu)先方式存儲時的C元素的起始地址一致。1A90 B180 C240 D5402A108 B114 C54 D603AM85 BM310 CM58 DM095數(shù)組A中，每個元素的存儲占3個單元，行下標i從1到8，列下標j從1到10，從首地址SA開場連續(xù)存放在存儲器，存放該數(shù)組至少需要的單元個數(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稀疏矩陣采用壓縮存儲，一般有C兩種方法。A二維數(shù)組和三維數(shù)組 B三元組和散列C三元組表和十字鏈表 D散列和十字鏈表4.3.2 判斷題1串相等是指兩個串的長度相等。2KMP算法的特點是在模式匹配時指示主串的指針不會變小。3稀疏矩陣壓縮存儲后，必會失去隨機存取功能。4數(shù)組是線性構(gòu)造的一種推廣，因此與線性表一樣，可以對它進展插入，刪除等操作。5假設(shè)采用三元組存儲稀疏矩陣，把每個元素的行下標和列下標互換，就完成了對該矩陣的轉(zhuǎn)置運算。6假設(shè)一個廣

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

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)先存儲整數(shù)數(shù)組A9358時，第一個元素的字節(jié)地址是100，每個整數(shù)占個字節(jié)。問以下元素的存儲地址是什么？(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è)一個準對角矩陣：aa11 a12

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

27、i+j-i%2-1。5設(shè)有nn的帶寬為3的帶狀矩陣A，將其3條對角線上的元素存于數(shù)組B3n中，使得元素Buv=aij，試推導出從i,j到 (u,v)的下標變換公式?！窘獯稹縰=j-i+1v=j-16現(xiàn)有如下的稀疏矩陣A如下圖，要求畫出以下各種表示方法。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畫出以下廣義表的頭尾表示存儲構(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 課后習題解答 5.3.1 選擇題1以下說確的是C。A二叉樹中任何一個結(jié)點的度都為2 B二叉樹的度為2C一棵二叉樹的度可小于2 D任何一棵二叉樹中至少有一個結(jié)點的度為22以二叉鏈表作為二叉樹的存儲構(gòu)造，在具有n個結(jié)點的二叉鏈表中n0，空鏈域的個數(shù)為C。A2n-1Bn-1Cn+1D

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

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

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

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

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

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

35、DEFGH2二叉鏈表存儲構(gòu)造示意圖： 3三叉鏈表存儲構(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畫出圖3所示的森林經(jīng)轉(zhuǎn)換后所對應

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

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

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

39、能到達的最大值和最小值。最大值：2h-1；最小值：2h-112求表達式： ab*(cd)e/f的波蘭式前綴式和逆波蘭式后綴式。波蘭式： - + a * b c d / e f 逆波蘭式：a b c d - * + e f / -13畫出和以下序列對應的樹T：樹的先根次序訪問序列為：GFKDAIEBCHJ；樹的后根訪問次序為：DIAEKFCJHBG?！窘獯稹繉亩鏄浜蜆浞謩e如下左、右圖所示：GBGBIEADKFCHJGBIEADKFCHJ14畫出和以下序列對應的森林F：森林的先根次序訪問序列為：ABCDEFGHIJKL；森林的后根訪問次序為：CBEFDGAJIKLH。AABDGCEFHIKJ

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

41、,1為這7個字母設(shè)計哈夫曼編碼。2對這7個字母進展等長編碼，至少需要幾位二進制數(shù)？哈夫曼編碼比等長編碼使電文1.000.591.000.590.410.280.210.120.310.160.800.400.200.100.111111111哈夫曼樹：a：10b：110c：010d：1110e：011f：00g：11112對這7個字母進展等長編碼，至少需要3位二進制數(shù)。等長編碼的平均長度：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哈夫曼編碼比等長編碼使電文總長壓縮了：1 - 2.54/3=15.33%5.3.4 算法設(shè)計題1給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出求二叉樹結(jié)點的數(shù)目的算法?！咎崾尽坎捎眠f歸算法實現(xiàn)。二叉樹結(jié)點的數(shù)目二叉樹結(jié)點的數(shù)目0 當二叉樹為空左子樹結(jié)點數(shù)目右子樹結(jié)點數(shù)目1 當二叉樹非空int count(BiTree root)if (root=NULL)return (0); else return (count(root-lchild)+count(root-rchild)+1);2請設(shè)計一個算法，要求該算法把二叉樹的葉結(jié)點按從左至右的順序鏈成一個單鏈表。二叉樹按lc

43、hild-rchild方式存儲，時用葉結(jié)點的rchild域存放鏈指針?！咎崾尽窟@是一個非常典型的基于二叉樹遍歷算法，通過遍歷找到各個葉子結(jié)點，因為不管前序遍歷、中序遍歷和后序遍歷，訪問葉子結(jié)點的相對順序都是一樣的，即都是從左至右。而題目要將二叉樹中的葉子結(jié)點按從左至右順序建立一個單鏈表，因此，可以采用三種遍歷中的任意一種方法遍歷。這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點指針pre，初始為空。第一個葉子結(jié)點由指針head指向，遍歷到葉子結(jié)點時，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點的rchild為空。LinkList head,pre=NULL;/*全局變量*/LinkList InOrde

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

45、t，試寫出求二叉樹的深度的算法?！咎崾尽坎扇∵f歸算法。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給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試求二叉樹各結(jié)點的層數(shù)?！咎崾尽坎捎孟刃蜻f歸遍歷算法實現(xiàn)。二叉樹結(jié)點的層次數(shù)二叉樹結(jié)點的層次數(shù)1當結(jié)點為根結(jié)點其雙親結(jié)點的層次數(shù)1當結(jié)點非根結(jié)點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給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出將二叉樹中所有結(jié)點的左、右子樹相互交換的算法。【提示】設(shè)root 為一棵用二叉鏈表存儲的二叉樹，則交換各結(jié)點的左右子樹的運算可基于后序遍歷實現(xiàn)：交換左子樹上各結(jié)點的左右子樹；交換左子樹上各結(jié)點的左右子樹；再交換根結(jié)點的左右子樹。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個結(jié)點的完全二叉樹采用順序構(gòu)造存儲，試設(shè)計非遞歸算法對其進展先序遍歷?！咎崾尽慷鏄涞捻樞虼鎯κ前赐耆鏄涞捻樞虼鎯Ω袷桨磳哟未鎯Φ模p親結(jié)點與子女結(jié)點的下標間有確定的關(guān)系。對順序存儲構(gòu)造的二叉樹進展先序遍歷，與二叉鏈表存放二叉樹的遍歷策略類似。但是在順序存儲構(gòu)造下，判二叉樹結(jié)點為空的條件為：結(jié)點下標大于n，或結(jié)點值為0一般二叉樹中的虛結(jié)點。void PreOrder (datatype datan+1) /*0號單元未用*/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è)當前結(jié)點值為*，依次輸出棧中元素的值*/while (!Empty_Stack(S) Pop(S,q);printf(q-data); return;elsePush_Stack(S,p);/*假設(shè)當前結(jié)點值不是*，壓棧*/ p=p-lchild; if(!Empty_Stack(S) Pop_Stack(S,r);/*當棧非空，棧頂元素

49、出棧，進入右子樹*/p=r-rchild; else return; 8一棵二叉樹的后序遍歷序列和中序遍歷序列，寫出可以確定這棵二叉樹的算法。【提示】根據(jù)后序遍歷和中序遍歷的特點，采用遞歸算法實現(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編寫算法判斷一棵二叉鏈表表示的二叉樹是否是完全二叉樹?！咎崾尽扛鶕?jù)完全二叉樹的定義可知，對完全二叉樹按照從上到下，從左到右的次序遍歷應滿足：假設(shè)*結(jié)點沒有左孩子，則一定無右孩子；假設(shè)*結(jié)點缺左或右孩子，則其所有后繼一定無孩子。因此，可采用按層次遍歷二叉樹的方法依次對每個結(jié)點進展判斷。這里增加一個標志以表示所有已掃描過的結(jié)點均有左、右孩子，將局部判斷結(jié)果存入CM中，CM表示整個二叉樹是否是完全二叉樹，B為1表示到目前為止所有結(jié)點均有左右孩子。int pleteBT(BiT

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

52、隊列*/ return(CM);10有n個結(jié)點的完全二叉樹存放在一維數(shù)組A1.n中，試據(jù)此建立一棵用二叉鏈表表示的二叉樹。BiTree Create(dataype A,inti)/*n個結(jié)點的完全二叉樹存于一維數(shù)組A中，據(jù)此建立以二叉鏈表表示的完全二叉樹,初始調(diào)用時,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編寫算法判定兩棵二叉樹是否相似。所謂兩棵二

53、叉樹s和t相似，即要么它們都為空或都只有一個結(jié)點，要么它們的左右子樹都相似?！咎崾尽績煽每斩鏄浠騼H有根結(jié)點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，采用遞歸算法。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寫出用逆轉(zhuǎn)鏈方法對二叉樹進展先序遍歷的算法?！咎崾尽坑媚孓D(zhuǎn)鏈的方法遍歷二叉樹，不需要附加的?？?/p>

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

55、) return; p=bt; r= NULL: while( p) Visit(p);/*訪問p所指結(jié)點*/ if(p-lchild)/*下降進入左子樹*/ p-tag=1; q=p-lchild; q=p-lchild=r; r=p; p=q; else if(p-rchild)/*下降進入右子樹*/ 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;/*從右子樹回來*/

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

57、1=high (t-lchild );/*h1為T的第一棵子樹的深度*/h2=high(t-ne*tsibling );/*h2為t的兄弟子樹的深度*/return(ma*(h1+1,h2); 14對以孩子鏈表表示的樹編寫計算樹的深度的算法?！咎崾尽坎捎眠f歸算法實現(xiàn)。樹的深度樹的深度1 假設(shè)根結(jié)點沒有子樹ma*(所有子樹的深度)1 假設(shè)根結(jié)點有子樹#define MA*NODE 樹中結(jié)點的最大個數(shù)int high(SNode tMA*NODE,int j)if(tj.firstchild=NULL) return(1);/*假設(shè)根結(jié)點沒有子樹*/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對以雙親鏈表表示的樹編寫計算樹的深度的算法。【提示】從每一個結(jié)點開場，從下向上搜索至根結(jié)點，記錄結(jié)點的層次數(shù)，其中的最大值就是樹的深度。int high(PNodet , int n)/*求有n個結(jié)點的樹t的深度*/ ma*h=0;for (i=0 ;ima*h) ma*h=h; return(ma*h) ;6.3.1 選擇題1n條邊的無向圖的鄰接表的存儲中，邊結(jié)點的個數(shù)有A。An B2n Cn/

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

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