1、.課后習(xí)題解答判斷題線性表的邏輯順序與存儲順序總是一致的。順序存儲的線性表可以按序號隨機存取。一半的元素需要移動。 因此屬于同一數(shù)據(jù)對象。 在線性表的順序存儲構(gòu)造中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。在線性表的鏈?zhǔn)酱鎯?gòu)造中，邏輯上相鄰的元素在物理位置上不一定相鄰。線性表的鏈?zhǔn)酱鎯?gòu)造優(yōu)于順序存儲構(gòu)造。在線性表的順序存儲構(gòu)造中，插入和刪除時移動元素的個數(shù)與該元素的位置有關(guān)。線性表的鏈?zhǔn)酱鎯?gòu)造是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的。在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨i個元i無關(guān)。線性表的特點是每個元素都有一個前驅(qū)和一個后繼。算法設(shè)計題設(shè)線

2、性表存放在向量Aarrsize 的前elenum個分量中，且遞增有序。試寫一算法將x 插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時間復(fù)雜度。相鄰，不一定將向量和表示線性表長度的變量封裝成一個構(gòu)造體，因為是順序存儲，分配的存儲空間是固定大小的，所以首先確定是否還有存儲空間，假設(shè)有，那么根據(jù)原線性表中元的有序性，來確定插入元素的插入位置，后面的元素為它讓出位置，也可以從高低標(biāo)端開x ，最后修改表示表長的變量。intinsert(datatypeA,int*elenum,datatypex)/*elenumif(*elenum=arrsize-1)return0;/*表已滿，無法

3、插入else i=*elenum;為表的最大下標(biāo)*/*/while (i=0 & 邊找位置邊移動*/Ai+1=Ai;i-;Ai+1=x;(*elenum)+; return 1;/* 插入成功 */時間復(fù)雜度為 O(n) 。/* 找到的位置是插入位的下一位*/元素?！咎崾尽?對順序表 A ，從第一個元素開場，查找其后與之值一樣的所有元素，將它們刪除； 再對第二個元素做同樣處理，依此類推。void delete(Seqlist*A)i=0;while(ilast)*/k=i+1;/* 將第 i 個元素以后與其值一樣的元素刪除while(klast&A-datai=A-datak)/*kAi*/k

4、+;n=k-i-1;for(j=k;jlast;j+)A-dataj-n=A-dataj; A-last= A-last-n;i+;A以較高的效率來實現(xiàn)。/*n 表示要刪除元素的個數(shù) */* 刪除多余元素 */xy(xdataixynA-datai向前移n n 用來記錄當(dāng)前已刪除元素的個數(shù)。void delete(Seqlist *A,int x,int y)i=0; n=0;while (ilast)if(A-datai=x&A-dataidatai介于 x和 y之間， n自增 */elseA-datai-n=A-datai; /* i+;A-last-=n;A-datai*/線性表中有n

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

6、w+; while(lowhigh&!fch(Rhigh)if(lowhigh)k=Rlow;Rlow=Rhigh; Rhigh=k;/* 將字母放在前面 */*將數(shù)字放在字母后面，其它字符前面*/low=low+1; high=n-1; while(lowhigh)while(lowhigh&fnum(Rlow) low+; while(lowhigh&!fnum(Rhigh)if(lowhigh)k=Rlow;Rlow=Rhigh;Rhigh=k;線性表用順序存儲，設(shè)計一個算法，用盡可能少的輔助存儲空間將順序表中前m元素和后 n 個元素進展整體互換。即將線性表：a, ,改變?yōu)椋?,a2m,

7、b1,b2nb1,b2,nb,a1 ,a2, ma。mn的大小，假設(shè) mn移后移 n 次。void process(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=x;m 次；否那么 ,將表中元素依次else for(i=1;idataL-last; for(k=L-last-1;k=0;k- L-datak+1=L-datak;L-data0=x;帶頭結(jié)點的單鏈表L中的結(jié)點是按整數(shù)值遞增排列的，試寫一算法， 將值為 x的結(jié)點插入到表L 中，使得 L 仍

8、然遞增有序，并且分析算法的時間復(fù)雜度。LinkList insert(LinkList L, int x)/*尋找插入位置 */p=L;/*申請結(jié)點空間 */while(p-next & xp-next-data)/*/p=p-next;s=(LNode *)malloc(sizeof(LNode);/*將結(jié)點插入到鏈表中*/s-data=x;s-next=p-next; p-next=s; return(L);ABC 不改變其排序性。LinkList Combine(LinkList A, LinkList B)C=A;rc=C;pa=A-next; /*pa 指向表 A 的第一個結(jié)點 */

9、pb=B-next; /*pb 指向表 B 的第一個結(jié)點*/free(B); /* 釋放 B 的頭結(jié)點 */while (pa & pb) /* 將 pa 、pb 所指向結(jié)點中，值較小的一個插入到鏈表 C 的表尾 */if(pa-datadata)rc-next=pa; rc=pa;pa=pa-next;elserc-next=pb; rc=pb;pb=pb-next;if(pa)rc-next=pa;elserc-next=pb;/*A B C */return(C);假設(shè)長度大于1 的循環(huán)單鏈表中，既無頭結(jié)點也無頭指針，p 為指向該鏈表中某結(jié)點的指針，編寫算法刪除該結(jié)點的前驅(qū)結(jié)點。s 指針

10、可循環(huán)找到其前驅(qū)結(jié)點p p 的前驅(qū)結(jié)點q， 然后可刪除結(jié)點* p。viod delepre(LNodeLNode* p, *q;p=s;while (p-next!=s)q=p;p=p-next;q-next=s; free(p);兩個單鏈表A和B分別表示兩個集合，其元素遞增排列，編寫算法求出A和BCC 同樣以元素遞增的單鏈表形式存儲。【提示】 交集指的是兩個單鏈表的元素值一樣的結(jié)點的集合，為了操作方便，先讓單鏈表 Cp A q 用來B 時，將其較小者跳過，繼續(xù)后面的比擬。LinkListIntersect(LinkListA,LinkListB)LNode*q,*p,*r,*LinkList

11、 C;C= (LNode *)malloc(sizeof(LNode); C-next=NULL;r=C; p=A; q=B;while (p & q )if (p-datadata) p=p-next; else if (p-data=q-data)s=(LNode *)malloc(sizeof(LNode); s-data=p-data;r-next=s;r=s;p=p-next; q=q-next;elseq=q-next; r-next=NULL;C=C-next; returnC;設(shè)有一個雙向鏈表，每個結(jié)點中除有prior 、data和next 域外，還有一個訪問頻度freq Lo

12、cata(L,x) x freq 1Locata(L,x) 算法。【提示】在定位操作的同時，需要調(diào)整鏈表中結(jié)點的次序：每次進展定位操作后，要查看所查找結(jié)點的freq域，將其同前面結(jié)點的freq域進展比擬，同時進展結(jié)點次序的調(diào)整。typedef struct dnodedatatype data; int freq;struct DLnode*prior,*next;DLnode,*DLinkList;DlinkListLocate(DLinkListL,datatypex)p=L-next;while(p&p-data!=x) p=p-next; if(!p) return(NULL);p-f

13、req+;while(p-prior!=L&p-prior-freqfreq)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);/*查找值為x的結(jié)點，使p指向它*/* 假設(shè)查找失敗，返回空指針 */* p freq */* 調(diào)整結(jié)點的次序 */* 返回找到的結(jié)點的地址*/課后習(xí)題解答#選擇題ATop-next=p;CTop 的鏈棧中插入一個p 所指結(jié)點時，其操作步驟為Dp-next=Top;Top=Top-next;C。對于棧

14、操作數(shù)據(jù)的原那么是B。A先進先出B后進先出C后進后出D不分順序piD。1,2,3,，,n其輸出序列為p1,p2,p3，pN,假設(shè)pN是n，A iBn-i+1D不確定表達式 a*(b c)d 的后綴表達式是 B。A BCabc*-d+D+-*abcd采用順序存儲的兩個棧共享空間S1.m ，topi代表第i個棧(i=1,2) 的棧頂，棧1底在S1 ，棧2 的底在 Sm ，那么棧滿的條件是B。A top2-top1|=0 Ctop1+top2=m 6一個棧的入棧序列是B Dtop1=top2a,b,c,d,e ，那么棧的不可能的輸出序列是C。A edcbaBdecbaCdceabD abcde在一個

15、鏈隊列中， Af-next=r;f=s; Cs-next=r;r=s;f,r 分別為隊首、隊尾指針，那么插入s 所指結(jié)點的操作為B。B r-next=s;r=s; D s-next=f;f=s;用不帶頭結(jié)點的單鏈表存儲隊列時，在進展刪除運算時D。A 僅修改頭指針 B 僅修改尾指針C頭、尾指針都要修改 D 頭、尾指針可能都要修改C的數(shù)據(jù)構(gòu)造。A隊列B 靜態(tài)鏈C。 A順序存儲的線性構(gòu)C限制存取點的線性判斷題C棧D順序表B 鏈?zhǔn)酱鎯Φ姆蔷€性構(gòu)造D 限制存取點的非線性構(gòu)造棧和隊列的存儲，既可以采用順序存儲構(gòu)造，又可以采用鏈?zhǔn)酱鎯?gòu)造。任何一個遞歸過程都可以轉(zhuǎn)換成非遞歸過程。3假設(shè)輸入序列為1,2,3,

16、4,5,6 ，那么通過一個?？梢暂敵鲂蛄?3,2,5,6,4,1 。通常使用隊列來處理函數(shù)的調(diào)用。循環(huán)隊列通常用指針來實現(xiàn)隊列的頭尾相接。簡答題循環(huán)隊列的優(yōu)點是能夠克制“假溢滿現(xiàn)象。設(shè)有循環(huán)隊列 sq ，隊滿的判別條件為：（sq-rear+1 %maxsize=sq-front;或sq-num=maxsize隊空的判別條件為：sq-rear=sq-front。棧和隊列數(shù)據(jù)構(gòu)造各有什么特點，什么情況下用到棧，什么情況下用到隊列？棧和隊列都是操作受限的線性表， 棧的運算規(guī)那么是 “后進先出 ，隊列的運算規(guī)那么是“先進先出。棧的應(yīng)用如數(shù)制轉(zhuǎn)換、遞歸算法的實現(xiàn)等，隊列的應(yīng)用如樹的層次遍歷等。什么是遞歸

17、？遞歸程序有什么優(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ù)這稱為間接遞歸。在實際應(yīng)用中，多為直接遞歸，也常簡稱為遞歸。遞歸程序的優(yōu)點是程序構(gòu)造簡單、清晰，易證明其正確性。缺點是執(zhí)行中占內(nèi)存空間較多，運行效率低。設(shè)有編號為1,2,3,4的四輛車，順序進入一個棧式構(gòu)造的站臺，試寫出這四輛車開車站的所有可能的順序每輛車可能入站，可能不入站，時間也可能不等。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214

18、,3241,3421,4321#選擇題下面關(guān)于串的表達錯誤的選項是C。 A串是字符的有限序列 BC空串是由空格構(gòu)成的串 D2串的長度是指B。A 串中所含不同字母的個數(shù) B串中所含字符的個數(shù)CD3S=aaab ,Next A。A 0123B 1123C 1231 D 1211二維數(shù)組M的成員是6 個字符每個字符占一個存儲單元組成的串，行下標(biāo)X圍從0 到8，列下標(biāo)j的X圍從1 到10，那么存放M至少需要D個字節(jié)；M的第第5 行共占A個字節(jié)；假設(shè)M按行優(yōu)先方式存儲，元M85的起始地址與當(dāng)M先方式存儲時的C元素的起始地址一致。1A 90B180C 240D 5402A 108B114C 54D603A

19、 M09i8列和按列優(yōu)數(shù)組 A中，每個元素的存儲占3個單元，行下標(biāo)i從1到8，列下標(biāo)j從1到10， 從首地址SA開場連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元個數(shù)是C，假設(shè)該數(shù)組 按行存放，元素A85的起始地址是D，假設(shè)該數(shù)組按列存放，元素A85的起始地址B 。1A80B100C240D2702ASA+141BSA+144CSA+222DSA+2253ASA+141BSA+180CSA+117DSA+225稀疏矩陣采用壓縮存儲，一般有CA 二維數(shù)組和三維數(shù)組 B三元組和散列CD散列和十字鏈表判斷題串相等是指兩個串的長度相等。KMP算法的特點是在模式匹配時指示主串的指針不會變小。稀疏矩陣壓縮存

20、儲后，必會失去隨機存取功能。數(shù)組是線性構(gòu)造的一種推廣，因此與線性表一樣，可以對它進展插入，刪除等操作。該矩陣的轉(zhuǎn)置運算。 假設(shè)一個廣義表的表頭為空表，那么此廣義表亦為空表。所謂取廣義表的表尾就是返回廣義表中最后一個元素。簡答題KMP算法較樸素的模式匹配算法有哪些改良?KMP 算法主要優(yōu)點是主串指針不回溯。當(dāng)主串很大不能一次讀入內(nèi)存且經(jīng)常發(fā)生局部匹配時， KMP 算法的優(yōu)點更為突出。設(shè)字符串S=aabaabaabaac，P=aabaac 。1S P next nextval 值；2S P KMP 算法的匹配過程?！窘獯稹浚?S的next與nextval值分別為012123456789和00200

21、2002021，p的next 與nextval值分別為012123和002003。利用 KMPaabaac(i=6,j=6)2BF 第一趟匹配：aabaabaabaacaabaac(i=6,j=6)第一趟匹配：匹配過程：算aabaabaabaac法的第二趟匹配：aa(i=3,j=2)(aa)baacaabaabaabaac第二趟匹配：aabaabaabaac第三趟匹配：aabaabaabaac第三趟匹配： a(i=3,j=1)(aa)baac第四趟匹配： aabaabaabaacaabaac(i=9,j=6)第五趟匹配： aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaaba

22、abaaca(i=6,j=1)第七趟匹配： aabaabaabaac( 成功)aabaac(i=13,j=7)假設(shè)按行優(yōu)先存儲整數(shù)數(shù)組 時，第一個元素的字節(jié)地址是 100數(shù)占個字節(jié)。問以下元素的存儲地址是什么？(1)a0000(2)a1111(3)a3125(4)a8247【解答】(1)LOC(a0000 )=100(2) LOC( a 1111 )=100+(3*5*8*1+5*8*1+8*1+1)*4=776(3)LOC(a 3125)=100+(3*5*8*3+5*8*1+8*2+5)*4=1784 (4)LOC(a 8247)=100+(3*5*8*8+5*8*2+8*4+7)a11a

23、12a21 a22a33a34a43a44.aija2m-1,2m-1 a2m-1,2ma2m,2m-1 a2m,2m按以下方式存儲于一維數(shù)組B4m 中 m 為一個整數(shù)：4m-14m012356k2m-1,2ma2m,2m-1a2m,2ma 11a aa22aaa43aij寫出下標(biāo)轉(zhuǎn)換函數(shù) k=f(i,j) 。【解答】由題目可知，每一行有兩個非 0 元素。當(dāng) i 為奇數(shù)時，第 i 行的元素為： a i,i、 a i,(i+1)，此時 k=2*(i-1)+j-i=i+j-2i i a i,(i-1)a k=2*(i-1)+j-I+1=i+j-1 k=i+j-i%2-1 。nn 3 A3 B3n中

24、，使得元Buv=a i,j(u,v) 的下標(biāo)變換公式?！窘獯稹縰=j-i+1 v=j-1.A如下圖，要求畫出以下各種表示方法。（1三元組表表示法（2十字鏈表法。000220-150133000000-60000000091000000028000【解答】1三元組表表示法:ijv11422216-15322134233534-665191763282十字鏈表法：01234502213231142216-1534-6235191456328.畫出以下廣義表的頭尾表示存儲構(gòu)造示意圖。（1A=(a,b,c),d,(a,b,c)（2B=(a,(b,(c,d),e),f)（1111 1111 d（20a1

25、b1c1110a 1110f0 b110 c0 c0d課后習(xí)題解答選擇題以下說法正確的選項是C。A 二叉樹中任何一個結(jié)點的度都為 22一棵二叉樹的度可小于 2 D任何一棵二叉樹中至少有一個結(jié)點的度為2的個數(shù)為 C。n 個結(jié)點的二叉鏈表中2n0 ，空鏈域A2n-1Bn-1Cn+1D 2n+1Ap-lchild=NULL Cp-ltag=0*p沒有孩子的充要條件是BBp-ltag=1且p-rtag=1p-lchild=NULL p-ltag=1A3 ,BA,BB。A3B4C5D1某二叉樹T有n 個結(jié)點,設(shè)按某種順序?qū) 中的每個結(jié)點進展編號，編號值為1,2,.n 且有如下性質(zhì):T 中任意結(jié)點v,其

26、編號等于左子樹上的最小編號減,而v的右子樹的結(jié)點中,其最小編號等于 v 左子樹上結(jié)點的最大編號加，這是按B 編號的。A 中序遍歷序列 B 先序遍歷序列 C后序遍歷序列 D層次順序設(shè)F 是一個森林，B是由F轉(zhuǎn)換得到的二叉樹域為空的結(jié)點有C個。F中有n 個非終端結(jié)點,B中右指針An-1nn+D1Cn+2.一棵完全二叉樹上500B5011001 C490D495C。設(shè)森林F 中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為N1，N2和N3。與森林 F 對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是BN1+N2CN2D。任何一棵二叉樹的葉結(jié)點在先序、中序、后序遍歷序列中的相對次序A。A 不發(fā)生改變 B發(fā)生改

27、變假設(shè)一棵二叉樹的后序遍歷序以上都不對debac ，那么先序遍歷序為為D。dabec，中序遍歷序列為列AcbedBdecabCdeabcD11假設(shè)一棵二叉樹的先序遍歷序列為abdgcefh ，中序遍歷的序列為歷的結(jié)果為 D 。AgcefhaBgdbecfhaCbdgaechfDdgbaechf ，那么后序遍12一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，那么該二叉樹一定滿足B 。A 所有的結(jié)點均無左孩子 B 所有的結(jié)點均無右孩子C只有一個葉子結(jié)點 D 是一棵滿二叉樹13 引入線索二叉樹的目的是A。A加快查找結(jié)點的前驅(qū)或后繼的速度 B為了能在二叉樹中方便的進展插入與刪除C為了能方便的找到

28、雙親 D使二叉樹的遍歷結(jié)果唯一設(shè)高度為 h那么此類二叉樹中所包含的結(jié)B。A 2*hB 2*h-1C 2*h+1D h+1一個具有567 個結(jié)點的二叉樹的高h 為D。A9B10C9 566 D10 567 之間給一個整數(shù)集合3，5，6，7，9，與該整數(shù)集合對應(yīng)的哈夫曼樹是B。ABCD939579676676733557935判斷題二叉樹是樹的特殊形式。由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。先根遍歷一棵樹和先序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不同。.先根遍歷森林和先序遍歷與該森林對應(yīng)的二叉樹，其結(jié)果不同。完全二叉樹中，假設(shè)一個結(jié)點沒有左孩子，那么它必是葉子。對于有 Nlog 2N1。假設(shè)一個結(jié)

29、點是某二叉樹子樹的中序遍歷序列中的最后一個結(jié)點，那么它必是該子樹的.先序遍歷序列中的最后一個結(jié)點。樹的后序遍歷序列中的第一個結(jié)點。 不使用遞歸也可實現(xiàn)二叉樹的先序、中序和后序遍歷。先序遍歷二叉樹的序列中，任何結(jié)點的子樹的所有結(jié)點不一定跟在該結(jié)點之后。先序和中序遍歷用線索樹方式存儲的二叉樹，不必使用棧。在后序線索二叉樹中，在任何情況下都能夠很方便地找到任意結(jié)點的后繼。哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。在哈夫曼編碼中，出現(xiàn)頻率一樣的字符編碼長度也一定一樣。用一維數(shù)組存放二叉樹時，總是以先序遍歷存儲結(jié)點。對一棵二叉樹進展層次遍歷時，應(yīng)借助于一個棧。完全二叉樹可采用順序存儲

30、構(gòu)造實現(xiàn)存儲，非完全二叉樹那么不能。滿二叉樹一定是完全二叉樹，反之未必。簡答題2 的樹與一棵二叉樹有何區(qū)別？樹與二叉樹之間有何區(qū)別？【解答】2 2個結(jié)點最多有兩棵子樹， 樹是無序樹， 且每個結(jié)點可以有多棵子樹。A對于圖 1 所示二叉樹，試給出：1它的順序存儲構(gòu)造示意圖；BC2它的二叉鏈表存儲構(gòu)造示意圖；3它的三叉鏈表存儲構(gòu)造示意圖?！窘獯稹緿EF1順序存儲構(gòu)造示意圖：ABCDEFGH(1)HG2二叉鏈表存儲構(gòu)造示意圖：3三叉鏈表存儲構(gòu)造示意圖：AABC DEFGHBC D E F2 所示的樹，試給出：G H （1雙親數(shù)組表示法示意圖；GFEDI（2孩子鏈表表示法示意圖；HJ 圖2)（3 孩子兄

31、弟鏈表表示法示意圖?！窘獯稹浚?雙親數(shù)組表示法示意圖：2孩子鏈表表示法示意圖：ABC.2648 100A0A-10A1B01B2C02C3D23D4E24E5F15F6G16G7H57H8I28I9J49J10K410K11M311M12N812N5311973孩子兄弟鏈表表示法示意圖：ABCGFEDH JK12I3 在二叉樹中是葉子。A FJBCDGEHI(圖 3).【解答】ABF ECGJDHI.在二叉樹中某結(jié)點所對應(yīng)的森林中結(jié)點為葉子結(jié)點的條件是該結(jié)點在森林中既沒有孩子也沒有右兄弟結(jié)點。將題 5 圖所示的二叉樹轉(zhuǎn)換成相應(yīng)的森林。ABCDEFGH【解答】 森林：(題 5 圖)CAFBEHD

32、G1 1 的結(jié)點。證明：由哈夫曼樹的構(gòu)造過程可知，哈夫曼樹的每一分支結(jié)點都是由兩棵子樹合并產(chǎn)生的新結(jié)點，其度必為 2，所以哈夫曼樹中不存在度為 1 的結(jié)點。n 個葉結(jié)點，需經(jīng)2n-1 個結(jié)點。n 個葉結(jié)點，那么樹中共有 2n 1 個結(jié)點。n-1 次合并形成哈夫曼樹，而每次合并產(chǎn)生一個分支結(jié)點，所證明：由二叉樹的前序序列和中序序列可以唯一地確定一棵二叉樹。證明：給定二叉樹結(jié)點的前序序列和對稱序中序序列，可以唯一確定該二叉樹。因為前序序列的第一個元素是根結(jié)點，該元素將二叉樹中序序列分成兩局部，左邊設(shè)l個元r 個元素是右子樹，假設(shè)素表示左子樹，假設(shè)左邊無元素，那么說明左子樹為空；右邊設(shè)空，那么右子樹

33、為空。根據(jù)前序遍歷中“根 左子樹右子樹的順序，那么由從第二元素開場的l 個結(jié)點序列和中序序列根左邊的l個結(jié)點序列構(gòu)造左子樹，由前序序列最后r 個元素序列與中序序列根右邊的一棵度為r 個元素序列構(gòu)造右子樹。m 的樹中有 n1 個度為 1 的結(jié)點，n2 個度為2 的結(jié)點，nm 個度m n n0 個葉結(jié)點，那么n=n 0+n1+ +nm(1)樹中除根結(jié)點外，每個結(jié)點對應(yīng)著一個分支，而度為n=n 1+2*n 2+m*n m+1由(1)(2)n0= n2+2*n 3+3*n 4+(m -1)*n m+1k 的結(jié)點發(fā)出 k 個分支，所以：在具有 nn1個結(jié)點的樹中，深度最小的那棵樹其深度是多少？它共有多少

34、2; n-1; 1; n; 1, n-1設(shè)高度為h 的二叉樹上只有度的最大值和最小值。2h-12h-1和度為 2 .求表達式a *ab*(c d)e/f 的波蘭式前綴式和逆波蘭式后綴式。d/ef逆波蘭式： abcd*ef/-畫出和以下序列對應(yīng)的樹T ：GFKDAIEBCHJ；樹的后根訪問次序為：DIAEKFCJHBG。【解答】 對應(yīng)的二叉樹和樹分別如下左、右圖所示：GGFFBBKKCHCDDAEJAHIJIE畫出和以下序列對應(yīng)的森林F： ABCDEFGHIJKL森林的后根訪問次序為：CBEFDGAJIKLH。AHDEGIKLJ畫出和以下序列對應(yīng)的樹T ： ABCDEFGHIJ ； DBGEHJ

35、ACIF ?！窘獯稹緼BCDEFGHIJ按層次遍歷，第一個結(jié)點 假設(shè)樹不空為根，該結(jié)點在中序序列中把序列分成左右兩局部左子樹和右子樹。假設(shè)左子樹不空，層次序列中第二個結(jié)點左子樹的根；假設(shè)左子樹為空，右每個結(jié)點或是當(dāng)前情況下子樹的根或是葉子。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,1為這 7 個字母設(shè)計哈夫曼編碼。.27 總長壓縮多少？1哈夫曼樹：1.001a：100.410.59b：1100101c：0100.200.210.310.28d：11100101e：01100g：111127 0.100.11

36、0.160.1200.800.403 位二進制數(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=2.54哈夫曼編碼比等長編碼使電文總長壓縮了：1 -2.54/3=15.33%算法設(shè)計題root ，試寫出求二叉樹結(jié)點的數(shù)目的算法?！咎崾尽?采用遞歸算法實現(xiàn)。二叉樹結(jié)點的數(shù)目0 當(dāng)二叉樹為空左子樹結(jié)點數(shù)目右子樹結(jié)點數(shù)目1 當(dāng)二叉樹非空int count(BiTree root)if (root=NULL) retu

37、rn (0);elsereturn (count(root-lchild)+count(root-rchild)+1);請設(shè)計一個算法，要求該算法把二叉樹的葉結(jié)點按從左至右的順序鏈成一個單鏈表。二叉樹按lchild-rchild方式存儲，時用葉結(jié)點的【提示】 這是一個非常典型的基于二叉樹遍歷算法，rchild 域存放鏈指針。通過遍歷找到各個葉子結(jié)點，因為不管前序遍歷、中序遍歷和后序遍歷，訪問葉子結(jié)點的相對順序都是一樣的，即都是從左至右。而題目要求是將二叉樹中的葉子結(jié)點按從左至右順序建立一個單鏈表， 遍歷中的任意一種方法遍歷。這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點指針第一個葉子結(jié)點由指針head指向

38、，遍歷到葉子結(jié)點時，就將它前驅(qū)因此，可以采用三種pre ，初始為空。 rchild 指針指向它，最后葉子結(jié)點的 rchild 為空。LinkList head,pre=NULL; LinkListInOrder(BiTree/* 全局變量 */*中序遍歷二叉樹T，將葉子結(jié)點從左到右鏈成一個單鏈表，表頭指針為head*/if(T)InOrder(T-lchild);/*中序遍歷左子樹*/if(T-lchild=NULL&當(dāng)前是葉子結(jié)點*/if (pre=NULL)head=T;pre=T;/*處理第一個葉子結(jié)點*/else pre-rchild=T;.pre=T;InOrder(T-rchild

39、);/* 將葉子結(jié)點鏈入鏈表 */* 中序遍歷右子樹 */pre-rchild=NULL return(head);/*/給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出求二叉樹的深度的算法。【提示】 采取遞歸算法。intHeight(BiTreeinthl,hr;root)if (root=NULL) return(0); elsehl=Height(root-lchild);hr=Height(root-rchild); if (hlhr) return (hl+1); else return(hr+1);【提示】 采用先序遞歸遍歷算法實現(xiàn)。root ，試求二叉樹各結(jié)點的層數(shù)。二

40、叉樹結(jié)點的層次數(shù)1其雙親結(jié)點的層次數(shù)當(dāng)結(jié)點為根結(jié)點當(dāng)結(jié)點非根結(jié)點voidfun(BiTreeroot, intn)if(t=NULL)return; elseprintf( %dfun(root-lchild,n+1); fun(root-rchild,n+1);給定一棵用二叉鏈表表示的二叉樹，其根指針為 root 右子樹相互交換的算法。【提示】設(shè)root為一棵用二叉鏈表存儲的二叉樹，那么交換各結(jié)點的左右子樹的運算可基于后序遍歷實現(xiàn)： 交換左子樹上各結(jié)點的左右子樹； 交換左子樹上各結(jié)點的左右子樹； 再交換根結(jié)點的左右子樹。voidExchange(BiTreeroot)BiTNode*p;(r

41、oot)Exchange(root-lchild); Exchange(root-rchild); p=root-lchild;root-lchild=root-rchild;root-rchild=p;.n 序遍歷?！咎崾尽?二叉樹的順序存儲是按完全二叉樹的順序存儲格式按層次存儲的，雙親結(jié)點與子女結(jié)點的下標(biāo)間有確定的關(guān)系。對順序存儲構(gòu)造的二叉樹進展先序遍歷，與二叉鏈表存放二n0一般二叉樹中的“虛結(jié)點。voidPreOrder(datatypedatan+1)intstackn; int top; if(n1)return; t=1;top=0;while (t0)while(t=n&data

42、t!=0) Visite(datat); stacktop=t;top+; t=t*2; if (topdata=x)while(!Empty_Stack(S)Pop(S,q);printf(q-data);/*假設(shè)當(dāng)前結(jié)點值為x，依次輸出棧中元素的值*/return;/* 假設(shè)當(dāng)前結(jié)點值不是x*/elsePush_Stack(S,p);p=p-lchild;if(!Empty_Stack(S) p=r-rchild;else return;/* 當(dāng)棧非空，棧頂元素出棧，進入右子樹*/一棵二叉樹的后序遍歷序列和中序遍歷序列，寫出可以確定這棵二叉樹的算法?！咎崾尽?根據(jù)后序遍歷和中序遍歷的特點，

43、采用遞歸算法實現(xiàn)。voidInPost(charin,charpost,intil,intir,intpl,intpr,BiTreet)/* in post 中存放著二叉樹的中序遍歷序列和后序遍歷序列，ilir 表示中序遍歷序列的左右端*/* 點， pl 和 pr 表示后序遍歷序列的左右端點， t 表示二叉樹的根 */t=(BiTNode *)malloc(sizeof(BiTNode); t-data=postpr;m=il;while (inm!=post pr ) m+;if (m= il)t-lchild=NULL;elseInPost(in,post,il,m-1,pl,pl+m-1

44、-il,t-lchild); if(m=ir)t-rchild=NULL;elseInPost(in,post,m+1,ir,pr-ir+m,pr-1,t-rchild);編寫算法判斷一棵二叉鏈表表示的二叉樹是否是完全二叉樹?！咎崾尽?根據(jù)完全二叉樹的定義可知，對完全二叉樹按照從上到下，從左到右的次序遍歷應(yīng)后繼一定無孩子。 因此， 可采用按層次遍歷二叉樹的方法依次對每個結(jié)點進展判斷。這里增加一個標(biāo)志以表示所有已掃描過的結(jié)點均有左、右孩子，將局部判斷結(jié)果存入 CM 中， CM表示整個二叉樹是否是完全二叉樹，B 為 1 表示到目前為止所有結(jié)點均有左右孩子。int CompleteBT(BiTree

45、T)Init_Queue(Q);B=1;CM=1;if(T!=NULL) In_Queue(Q,T); while(!Empty_Queue(Q)p=Out_Queue(Q);if(p-lchild=NULL)B=0;if(rchild!=NULL) CM=0;else CM=B;In_Queue(Q,p-lchild);if(p-rchild=NULL)B=0; elseIn_Queue(Q,p-rchild);/* 初始化隊列 Q*/*當(dāng)隊列不為空時執(zhí)行循環(huán)*/*B=0表示缺少左、右孩子*/*CM=0 表示不是完全二叉樹*/*/*/return(CM);n A1.n中，試據(jù)此建立一棵用二叉

46、鏈表表示的二叉樹。BiTreeCreate(dataypeA,inti)/*n 個結(jié)點的完全二叉樹存于一維數(shù)組 A 中，據(jù)此建立以二叉鏈表表示的完全二叉樹,初始調(diào)用時 ,i=1*/BiTree T;if(idata=Ai;if (2*in)T-lchild=NULL;else T-lchild=Create(A,2*i); if (2*i+1n) T-rchild=NULL;else T-rchild=Create(A,2*i+1);return (T);s t相似，即要么它們都為空或都只有一個結(jié)點，要么它們的左右子樹都相似?！咎崾?】兩棵空二叉樹或僅有根結(jié)點的二叉樹相似； 對非空二叉樹， 可

47、判左右子樹是否相似，采用遞歸算法。int Similar(BiTree s, BiTree t)&q=NULL)return(1);if(!s&t|s&!t)return(0);else return(Similar(s-lchild,t-lchild) & Similar(s-rchild,t-rchild)寫出用逆轉(zhuǎn)鏈方法對二叉樹進展先序遍歷的算法?！咎崾?】用逆轉(zhuǎn)鏈的方法遍歷二叉樹，不需要附加的棧空間，而是在遍歷過程中沿結(jié)點的右子樹下降時，臨時改變結(jié)點lchild或者rchild的值，使之指向雙親，從而為以后的上升提供路徑，上升時再將結(jié)點的 lchild 或者 rchild 恢復(fù)。typ

48、edefstructtnodedatatype data;int tag;/*tag 0，進入左子樹時置struct tnode *lchild, *rchild;Bnode, *Btree;voidPreOrder(Btreebt)Bnode*r,*p,指向當(dāng)前結(jié)點，rpif(bt=NULL)return; p=bt; r= NULL: while( p)Visit(p); if(p-lchild)1，從左子樹回來時，再恢復(fù)為q 指向要訪問的下一結(jié)點*/* 訪問 p 所指結(jié)點 */* 下降進入左子樹 */p-tag=1;q=p-lchild;q=p-lchild=r;r=p;p=q;0*/*

49、 下降進入右子樹 */elseif(p-rchild)q=p-rchild;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;/*從右子樹回來 */elser-tag=0; q=r-lchild;r-lchild=p;p=r;r=q;/*從左子樹回來 */if (r=NULL)return;elser-tag=0; q=r-rchild;r-rchild= r-lchild; r-lchild=p; p=q;/*從左子樹回來，準(zhǔn)備進入

50、右子樹*/對以孩子兄弟鏈表表示的樹編寫計算樹的深度的算法?！咎崾?】采用遞歸算法實現(xiàn)。樹的深度0 假設(shè)樹為空Max第一棵子樹的深度1，兄弟子樹的深度假設(shè)樹非空int high(CSTreeT)if(T=NULL)return(0);/*假設(shè)樹為空，返回0*/elseh1=high(t-lchild);/* *h1T的第一棵子樹的深度*/h2=high(t-nextsibling);/*h2為t的兄弟子樹的深度*/return(max(h1+1,h2);對以孩子鏈表表示的樹編寫計算樹的深度的算法?！咎崾尽坎捎眠f歸算法實現(xiàn)。1 假設(shè)根結(jié)點沒有子樹樹的深度max( 所有子樹的深度 ) 1 假設(shè)根結(jié)點

51、有子樹#define MAXNODE high(SNode tMAXNODE,intj)if(tj.firstchild=NULL)return(1);/*假設(shè)根結(jié)點沒有子樹*/else p=ti.firstchild;max=high(t,p-data); p=p-nextchild; while(p) h=high(t,p-data); if(hmax) max=h;.p=p-nextchild;return(max+1);對以雙親鏈表表示的樹編寫計算樹的深度的算法?！咎崾?】從每一個結(jié)點開場，從下向上搜索至根結(jié)點，記錄結(jié)點的層次數(shù)， 其中的最大值就是樹的深度。int high(PNode

52、 t,intn)maxh=0;for (i=0 ;imaxh)maxh=h;return(maxh) ;選擇題n 條邊的無向圖的鄰接表的存儲中，邊結(jié)點的個數(shù)有。AnBCD n*nn條邊的無向圖的鄰接多重表的存儲中，邊結(jié)點的個數(shù)有A。AnBCD n*nA BCAOV 網(wǎng)DAOE 網(wǎng)最短路徑的生成算法可用C。A B克魯斯卡爾算法C迪杰斯特拉算D 哈夫曼算法一個無向圖的鄰接表如以下圖所示：序號vertexfirstedgev1v2v3130231v4011從頂點 v0 出發(fā)進展深度優(yōu)先搜索，經(jīng)歷的結(jié)點順序為B。.Av0,v3,v2,v1Bv0,v1,v2,v3Cv0,v2,v1,v3Dv0, v1,

53、 v3, v22V0D。Av0,v3,v2,v1Bv0,v1,v2,v3Cv0,v2,v1,v3Dv0, v1, v3, v2設(shè)有向圖n 個頂點和e 條邊，進展拓?fù)渑判驎r，總的計算時間為D。AO(nlog O(enO(elogD O (n+e)n e A。Kruskal 算法生成最小生成樹，其時間復(fù)A O(elogO(enO(elogD O(nlog 2n)關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中A 。A從源點到匯點的最長路徑B從源點到匯點的最短路徑C最長的回路D最短的回9下面關(guān)于求關(guān)鍵路徑的說法不正確的選項是。A求關(guān)鍵路徑是以拓?fù)渑判驗楦椎?B一個事件的最早開場時間與以該事件為尾的弧的活動最早開場時間一樣

54、 C時間的差D關(guān)鍵活動一定位于關(guān)鍵路徑上1010 B 條邊才能確保其是連通圖。A8B9C10D11判斷題求最小生成樹的Prim算法在邊較少、結(jié)點較多時效率較高用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。AOV-有回路的圖不能進展拓?fù)渑判?。故只存儲鄰接矩陣的?或上 )三角局部即可。任何無向圖都存在生成樹。假設(shè)一個有向圖的鄰接矩陣對角線以下元素均連通分量是無向圖中的極小連通子圖。那么該圖的拓?fù)溆行蛐蛄斜囟ù嬖?。強連通分量是有向圖中的極大強連通子圖用鄰接矩陣 A表示圖，判定任意兩個結(jié)點和vj之間是否有長度為m 的路徑相連，那么只要

55、檢查Am的第i行第j列的元素是否為0 即可?？s短關(guān)鍵路徑上活動的工期一定能夠縮短整個工程的工期。AOE網(wǎng)中一定只有一條關(guān)鍵路徑。簡答題對于如圖1 所示的有向圖，試給出：1每個頂點的入度和出度；2鄰接矩陣；3鄰接表；1.（4逆鄰接表；（5 強連通分量。【解答】（112122231，3、頂43，0523612。（2鄰接矩陣：0001000100101000000111000000110100010010302345011223344556013 144逆鄰接表：011412452313402445255625強連通分量：514623G 2 所示，試給出：1該圖的鄰接矩陣；2該圖的鄰接表；3該圖的多

56、重鄰接表；v2v5v1v4v74從出發(fā)的“深度優(yōu)先遍歷序列；5從出發(fā)的“廣度優(yōu)先遍歷序列。v3v62.【解答】1該圖的鄰接矩陣：01100001010000100100001101100001001000100100001102該圖的鄰接表：0v1121v2022v3023v432454v5365v6366v7453該圖的多重鄰接表：v1v2 v30102v4v531 32343 5v6v764 654從v1 出發(fā)的“深度優(yōu)先遍歷序列：v1v2v4v3v5v7v65v1 v1v2v3v4v5v6v7用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關(guān)？與邊的條數(shù)是否有關(guān)？【解答】n(n0)n2

57、個數(shù)與圖的邊數(shù)無關(guān)。設(shè)有向圖G 如圖3 所示，試畫出列。G 的十字鏈表構(gòu)造，并寫出圖 G 的兩個拓?fù)湫騰2v5v1v3v6圖 3.【解答】1G 的十字鏈表構(gòu)造：0 v101021 v214152 v325v4v5435 v653542G 的兩個拓?fù)湫蛄校?v1v2v3v6v5v4; 5如圖 4 AOE 網(wǎng)：（1（2v1 v3 v2v6v5v4（3找出該 AOE 網(wǎng)中的關(guān)鍵路徑，并答復(fù)完成該工程需要的最短時間。a 1=3Ba Ea 5=9a 9=5Aa3a4=7 CDaa 6=10aFHa 10 =3a 11 =2G圖 41ve(A)=0ve(B)= ve(A)+3=3ve(C)= ve(A)+

58、5=5ve(D)=max(ve(B)+6, ve(C)+7)=12ve(E)= ve(D)+9=21ve(G)=ve(D)+8=20ve(F)= max(ve(D)+10, ve(G)+6)=26ve(H)= max(ve(E)+E, ve(G)+2, ve(F)+3)=29vl(H)=29vl(E)= vl(H)vl(F)= vl(H) 3=26vl(G)= min(vl(H)2, vl(F)6)=20vl(D)= min(vl(E)9, vl(F) 10, vl(G) 8)=12.vl(B)= vl(D)6=6vl(B)= vl(D)6=6vl(C)=vl(D) 7=5vl(A)=min(

59、vl(B)3,vl(C)5)= 02e(a1)=0e(a 7)=12e(a 2 )=0e(a 8 )=20e(a 3)=3e(a 9)=21e(a4)=5e(a5)=12e(a10)=26e(a11)=20e(a6)=12l(a1)=3 (a7)=12l(a2)=0 l(a8)=20l(a3)=6 l(a9)=24l(a4)=5 l(a10 )=26l(a5)=15 l(a11 )=27l(a6)=16間：29ADFa10=3a4=7a8=6a2=5a7=8CG課后習(xí)題解答(P152)選擇題靜態(tài)查找表與動態(tài)查找表的根本區(qū)別在于A 它們的邏輯構(gòu)造不一樣 B 施加在其上的操作不一樣C所包含的數(shù)據(jù)元

60、素類型不一樣 D 存儲實現(xiàn)不一樣在表長為 nA nB 1Cn+1Dn-1A。順序查找適用于存儲構(gòu)造為CA 哈希存儲 B壓縮存儲CD索引存儲用順序查找法對具有n個結(jié)點的線性表查找一個結(jié)點的時間復(fù)雜度為CAO(logn2)BO(nlogn)CO(n)D適用于折半查找的表的存儲方式及元素排列要求為D。A方式存儲，元素?zé)o序B方式存儲，元素有序C順序方式存儲，元素?zé)o序D順序方式存儲，元素有有一個長度為12 的有序表，按折半查找法對該表進展查找，在表內(nèi)各元素等概率況下查找成功所需的平均比擬次數(shù)為B。A35/12B37/12C39/1243/1271 391232416275778295，100 上進展折半