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

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

2、時移動元素的個數(shù)與該元素的位置有關(guān)。（）9線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的。（）10在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結(jié)構(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個分量中，且遞增有序。試寫一算法，將x 插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時間復(fù)雜度?！咎崾尽恐苯佑妙}

3、目中所給定的數(shù)據(jù)結(jié)構(gòu)（順序存儲的思想是用物理上的相鄰表示邏輯上的相鄰，不一定將向量和表示線性表長度的變量封裝成一個結(jié)構(gòu)體），因為是順序存儲，分配的存儲空間是固定大小的，所以首先確定是否還有存儲空間，若有，則根據(jù)原線性表中元素的有序性，來確定插入元素的插入位置，后面的元素為它讓出位置，（也可以從高下標(biāo)端開始一邊比較，一邊移位）然后插入x ，最后修改表示表長的變量。int insert (datatype A,int *elenum,datatype x)/*設(shè)elenum為表的最大下標(biāo)*/if (*elenum=arrsize-1) return 0;/*表已滿，無法插入*/else i=*el

4、enum; while (i>=0 && Ai>x)/*邊找位置邊移動*/Ai+1=Ai;i-; Ai+1=x;/*找到的位置是插入位的下一位*/ (*elenum)+;return 1;/*插入成功*/時間復(fù)雜度為O(n)。2已知一順序表A，其元素值非遞減有序排列，編寫一個算法刪除順序表中多余的值相同的元素?！咎崾尽繉樞虮鞟，從第一個元素開始，查找其后與之值相同的所有元素，將它們刪除；再對第二個元素做同樣處理，依此類推。void delete(Seqlist *A)i=0;while(i<A->last)/*將第i個元素以后與其值相同的元素刪除*/k

5、=i+1;while(k<=A->last&&A->datai=A->datak)k+;/*使k指向第一個與Ai不同的元素*/n=k-i-1;/*n表示要刪除元素的個數(shù)*/for(j=k;j<=A->last;j+)A->dataj-n=A->dataj; /*刪除多余元素*/A->last= A->last -n; i+;3寫一個算法，從一個給定的順序表A中刪除值在xy(x<=y)之間的所有元素，要求以較高的效率來實現(xiàn)?！咎崾尽繉樞虮鞟，從前向后依次判斷當(dāng)前元素A->datai是否介于x和y之間，若是，

6、并不立即刪除，而是用n記錄刪除時應(yīng)前移元素的位移量；若不是，則將A->datai向前移動n位。n用來記錄當(dāng)前已刪除元素的個數(shù)。void delete(Seqlist *A,int x,int y)i=0;n=0;while (i<A->last)if (A->datai>=x && A->datai<=y) n+;/*若A->datai 介于x和y之間，n自增*/else A->datai-n=A->datai;/*否則向前移動A->datai*/i+;A->last-=n;4線性表中有n個元素，每個元素是

7、一個字符，現(xiàn)存于向量Rn中，試寫一算法，使R中的字符按字母字符、數(shù)字字符和其它字符的順序排列。要求利用原來的存儲空間，元素移動次數(shù)最小?！咎崾尽繉€性表進行兩次掃描，第一次將所有的字母放在前面，第二次將所有的數(shù)字放在字母之后，其它字符之前。int fch(char c)/*判斷c是否字母*/if(c>='a'&&c<='z'|c>='A'&&c<='Z')return (1);else return (0);int fnum(char c)/*判斷c是否數(shù)字*/if(c>

8、;='0'&&c<='9') return (1);else return (0);void process(char Rn)low=0;high=n-1;while(low<high)/*將字母放在前面*/while(low<high&&fch(Rlow) low+;while(low<high&&!fch(Rhigh) high-;if(low<high)k=Rlow;Rlow=Rhigh;Rhigh=k;low=low+1; high=n-1;while(low<high)

9、/*將數(shù)字放在字母后面，其它字符前面*/while(low<high&&fnum(Rlow) low+;while(low<high&&!fnum(Rhigh) high-;if(low<high) k=Rlow;Rlow=Rhigh;Rhigh=k;5線性表用順序存儲，設(shè)計一個算法，用盡可能少的輔助存儲空間將順序表中前m個元素和后n個元素進行整體互換。即將線性表：（a1, a2, , am, b1, b2, , bn）改變?yōu)椋海╞1, b2, , bn , a1, a2, , am）?！咎崾尽勘容^m和n的大小，若m<n，則將表中元素依次

10、前移m次；否則,將表中元素依次后移n次。void process(Seqlist *L,int m,int n) if(m<=n) for(i=1;i<=m;i+)x=L->data0;for(k=1;k<=L->last;k+)L->datak-1=L->datak;L->dataL->last=x;else for(i=1;i<=n;i+)x=L->dataL->last;for(k=L->last-1;k>=0;k- -)L->datak+1=L->datak;L->data0=x;6已

11、知帶頭結(jié)點的單鏈表L中的結(jié)點是按整數(shù)值遞增排列的，試寫一算法，將值為x 的結(jié)點插入到表L中，使得L仍然遞增有序，并且分析算法的時間復(fù)雜度。LinkList insert(LinkList L, int x) p=L; while(p->next && x>p->next->data) p=p->next;/*尋找插入位置*/ s=(LNode *)malloc(sizeof(LNode);/*申請結(jié)點空間*/s->data=x; /*填裝結(jié)點*/s->next=p->next; p->next=s; /*將結(jié)點插入到鏈表中*

12、/ return(L); 7假設(shè)有兩個已排序（遞增）的單鏈表A和B，編寫算法將它們合并成一個鏈表C而不改變其排序性。LinkList Combine(LinkList A, LinkList B)C=A;rc=C;pa=A->next;/*pa指向表A的第一個結(jié)點*/pb=B->next;/*pb指向表B的第一個結(jié)點*/free(B);/*釋放B的頭結(jié)點*/while (pa && pb)/*將pa、pb所指向結(jié)點中，值較小的一個插入到鏈表C的表尾*/ if(pa->data<pb->data) rc->next=pa;rc=pa;pa=pa

13、->next;elserc->next=pb;rc=pb;pb=pb->next;if(pa)rc->next=pa;elserc->next=pb;/*將鏈表A或B中剩余的部分鏈接到鏈表C的表尾*/return(C);8假設(shè)長度大于1的循環(huán)單鏈表中，既無頭結(jié)點也無頭指針，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->next!=s)q=p; p=

14、p->next;q->next=s;free(p);9已知兩個單鏈表A和B分別表示兩個集合，其元素遞增排列，編寫算法求出A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲。【提示】交集指的是兩個單鏈表的元素值相同的結(jié)點的集合，為了操作方便，先讓單鏈表C帶有一個頭結(jié)點，最后將其刪除掉。算法中指針p用來指向A中的當(dāng)前結(jié)點，指針q用來指向B中的當(dāng)前結(jié)點，將其值進行比較，兩者相等時，屬于交集中的一個元素，兩者不等時，將其較小者跳過，繼續(xù)后面的比較。LinkList Intersect(LinkList A, LinkList B)LNode *q, *p, *r, *s; LinkLis

15、t C;C= (LNode *)malloc(sizeof(LNode);C->next=NULL;r=C;p=A; q=B;while (p && q ) if (p->data<q->data) p=p->next; elseif (p->data=q->data) s=(LNode *)malloc(sizeof(LNode); s->data=p->data; r->next=s; r=s; p=p->next; q=q->next; else q=q->next;r->next=NUL

16、L; C=C->next; return C;10設(shè)有一個雙向鏈表，每個結(jié)點中除有prior、data和next域外，還有一個訪問頻度freq域，在鏈表被起用之前，該域的值初始化為零。每當(dāng)在鏈表進行一次Locata(L,x)運算后，令值為x的結(jié)點中的freq域增1，并調(diào)整表中結(jié)點的次序，使其按訪問頻度的非遞增序列排列，以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一個滿足上述要求的Locata(L,x)算法?！咎崾尽吭诙ㄎ徊僮鞯耐瑫r，需要調(diào)整鏈表中結(jié)點的次序：每次進行定位操作后，要查看所查找結(jié)點的freq域，將其同前面結(jié)點的freq域進行比較，同時進行結(jié)點次序的調(diào)整。typedef struct

17、 dnodedatatype data;int freq;struct DLnode *prior,*next;DLnode,*DLinkList;DlinkList Locate(DLinkList L, datatype x)p=L->next;while(p&&p->data!=x) p=p->next; /*查找值為x的結(jié)點，使p指向它*/if(!p) return(NULL);/*若查找失敗，返回空指針*/p->freq+;/*修改p的freq域*/while(p->prior!=L&&p->prior->fr

18、eq<p->freq)/*調(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 課后習(xí)題解答 #3.3.1 選擇題1向一個棧頂指針為Top的鏈棧中插入一個p所指結(jié)點時，其操作步驟為（C）。ATop->next=p; Bp->next=Top->n

19、ext;Top->next=p;Cp->next=Top;Top=p; Dp->next=Top;Top=Top->next;2對于棧操作數(shù)據(jù)的原則是（B）。A先進先出 B后進先出 C后進后出 D不分順序3若已知一個棧的入棧序列是1,2,3,n，其輸出序列為p1,p2,p3，pN,若pN是n，則pi是（D）。Ai Bn-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的底在S

20、m，則棧滿的條件是（B）。Atop2-top1|=0 Btop1+1=top2Ctop1+top2=m Dtop1=top26一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（C）。A edcba B decba Cdceab D abcde7在一個鏈隊列中，若f,r分別為隊首、隊尾指針，則插入s所指結(jié)點的操作為（B）。Af->next=r;f=s; Br->next=s;r=s; Cs->next=r;r=s; Ds->next=f;f=s;8用不帶頭結(jié)點的單鏈表存儲隊列時，在進行刪除運算時（D）。A僅修改頭指針 B僅修改尾指針C頭、尾指針都要修改 D頭

21、、尾指針可能都要修改9遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（C）的數(shù)據(jù)結(jié)構(gòu)。A隊列 B靜態(tài)鏈表 C棧 D順序表10棧和隊都是（C）。A順序存儲的線性結(jié)構(gòu) B鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)C限制存取點的線性結(jié)構(gòu) D限制存取點的非線性結(jié)構(gòu)3.3.2 判斷題1棧和隊列的存儲，既可以采用順序存儲結(jié)構(gòu)，又可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。（）2任何一個遞歸過程都可以轉(zhuǎn)換成非遞歸過程。（）3若輸入序列為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)隊列

22、的優(yōu)點是什么？如何判別它的空和滿？循環(huán)隊列的優(yōu)點是能夠克服“假溢滿”現(xiàn)象。設(shè)有循環(huán)隊列sq，隊滿的判別條件為：（sq->rear+1）%maxsize=sq->front;或sq->num=maxsize。隊空的判別條件為：sq->rear=sq->front。2棧和隊列數(shù)據(jù)結(jié)構(gòu)各有什么特點，什么情況下用到棧，什么情況下用到隊列？棧和隊列都是操作受限的線性表，棧的運算規(guī)則是“后進先出”，隊列的運算規(guī)則是“先進先出”。棧的應(yīng)用如數(shù)制轉(zhuǎn)換、遞歸算法的實現(xiàn)等，隊列的應(yīng)用如樹的層次遍歷等。3什么是遞歸？遞歸程序有什么優(yōu)缺點？一個函數(shù)在結(jié)束本函數(shù)之前，直接或間接調(diào)用函數(shù)自身

23、，稱為遞歸。例如，函數(shù)f在執(zhí)行中，又調(diào)用函數(shù)f自身，這稱為直接遞歸；若函數(shù)f在執(zhí)行中，調(diào)用函數(shù)g，而g在執(zhí)行中，又調(diào)用函數(shù)f，這稱為間接遞歸。在實際應(yīng)用中，多為直接遞歸，也常簡稱為遞歸。遞歸程序的優(yōu)點是程序結(jié)構(gòu)簡單、清晰，易證明其正確性。缺點是執(zhí)行中占內(nèi)存空間較多，運行效率低。4設(shè)有編號為1,2,3,4的四輛車，順序進入一個棧式結(jié)構(gòu)的站臺，試寫出這四輛車開出車站的所有可能的順序（每輛車可能入站，可能不入站，時間也可能不等）。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,43214.3 課后習(xí)題解答#4.3.1 選

24、擇題1下面關(guān)于串的敘述錯誤的是（C）。A串是字符的有限序列 B串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯空串是由空格構(gòu)成的串 D模式匹配是串的一種重要運算2串的長度是指（B）。A串中所含不同字母的個數(shù) B串中所含字符的個數(shù)C串中所含不同字符的個數(shù) D串中所含非空格字符的個數(shù)3已知串S=aaab,其Next數(shù)組值為（D）。A0123 B1123 C1231 D12114二維數(shù)組M的成員是6個字符（每個字符占一個存儲單元）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要（D）個字節(jié)；M的第8列和第5行共占（A）個字節(jié)；若M按行優(yōu)先方式存儲，元素M85的起始地址與當(dāng)M按列

25、優(yōu)先方式存儲時的（C）元素的起始地址一致。（1）A90 B180 C240 D540（2）A108 B114 C54 D60（3）AM85 BM310 CM58 DM095數(shù)組A中，每個元素的存儲占3個單元，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元個數(shù)是（C），若該數(shù)組按行存放，元素A85的起始地址是（C），若該數(shù)組按列存放，元素A85的起始地址是（C）。（1）A80 B100 C240 D270（2）ASA+141 BSA+144 CSA+222 DSA+225（3）ASA+141 BSA+180 CSA+117 DSA+2256稀疏

26、矩陣采用壓縮存儲，一般有（C）兩種方法。A二維數(shù)組和三維數(shù)組 B三元組和散列C三元組表和十字鏈表 D散列和十字鏈表4.3.2 判斷題1串相等是指兩個串的長度相等。（×）2KMP算法的特點是在模式匹配時指示主串的指針不會變小。（）3稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（）4數(shù)組是線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。（×）5若采用三元組存儲稀疏矩陣，把每個元素的行下標(biāo)和列下標(biāo)互換，就完成了對該矩陣的轉(zhuǎn)置運算。（×）6若一個廣義表的表頭為空表，則此廣義表亦為空表。（×）7所謂取廣義表的表尾就是返回廣義表中最后一個元素。（&

27、#215;）4.3.3 簡答題1KMP算法較樸素的模式匹配算法有哪些改進?KMP算法主要優(yōu)點是主串指針不回溯。當(dāng)主串很大不能一次讀入內(nèi)存且經(jīng)常發(fā)生部分匹配時，KMP算法的優(yōu)點更為突出。2設(shè)字符串S=aabaabaabaac'，P=aabaac'。（1）給出S和P的next值和nextval值； （2）若S作主串，P作模式串，試給出利用KMP算法的匹配過程。【解答】 （1）S的next與nextval值分別為和002002002009，p的next與nextval值分別為012123和002003。 （2）利用BF算法的匹配過程： 利用KMP算法的匹配過程： 第一趟匹配：aaba

28、abaabaac 第一趟匹配：aabaabaabaac aabaac(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)第五趟匹配：aabaabaabaac aa(i=6,j=2)第六趟匹配：aabaabaabaac a(i=6,j=1)第七趟匹配：aabaabaabaac(成功) aab

29、aac(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è)一個準(zhǔn)對角矩陣：a11 a12a2

30、1 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寫出下標(biāo)轉(zhuǎn)換函數(shù)k=f(i,j)。【解答】由題目可知，每一行有兩個非0元素。當(dāng)i為奇數(shù)時，第i行的元素為：ai,i、ai,(i+1)，此時k=2*(i-1)+j-i=i+j-2當(dāng)i為偶數(shù)時，第i行的元素為：ai,(i-1)、ai,i，此時k=2*(i-1)+j-I+1=i+j-1綜上所述，k=

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

32、）十字鏈表法：012345012345519123334-61422632816-1522137畫出下列廣義表的頭尾表示存儲結(jié)構(gòu)示意圖。（1）A=(a,b,c),d,(a,b,c)（2）B=(a,(b,(c,d),e),f)（1）11111 1 1 d0 a1 b1 c（2）1111 1 1 0 f0 a0 b0 c1 10 c0 d5.3 課后習(xí)題解答 5.3.1 選擇題1下列說法正確的是（C）。A二叉樹中任何一個結(jié)點的度都為2 B二叉樹的度為2C一棵二叉樹的度可小于2 D任何一棵二叉樹中至少有一個結(jié)點的度為22以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，在具有n個結(jié)點的二叉鏈表中（n>0），空鏈

33、域的個數(shù)為（C）。A2n-1 Bn-1 Cn+1 D2n+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é)點的最大編號加，這是按

34、（B）編號的。A 中序遍歷序列 B 先序遍歷序列 C 后序遍歷序列 D 層次順序 6設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)點,B中右指針域為空的結(jié)點有（C）個。An-1 B n C n+1 Dn+2 7一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（B）。A 500 B 501 C490 D4958設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為N1，N2和N3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（D）。AN1 BN1+N2 CN2 DN2+N39任何一棵二叉樹的葉結(jié)點在先序、中序、后序遍歷序列中的相對次序（A）。A不發(fā)生改變 B 發(fā)生改變

35、C 不能確定 D 以上都不對10若一棵二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則先序遍歷序列為（D）。Acbed Bdecab Cdeabc Dcedba11若一棵二叉樹的先序遍歷序列為abdgcefh，中序遍歷的序列為dgbaechf，則后序遍歷的結(jié)果為（D）。 A gcefha B gdbecfha C bdgaechf D gdbehfca12一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（AB）。A所有的結(jié)點均無左孩子 B所有的結(jié)點均無右孩子C只有一個葉子結(jié)點 D是一棵滿二叉樹13引入線索二叉樹的目的是（A）。A加快查找結(jié)點的前驅(qū)或后繼的速度

36、 B為了能在二叉樹中方便的進行插入與刪除C為了能方便的找到雙親 D使二叉樹的遍歷結(jié)果唯一 14設(shè)高度為h的二叉樹上只有度為和度為的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（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ù)集合對應(yīng)的哈夫曼樹是（B）。A B C D93765 3567979536765395.3.2 判斷題1二叉樹是樹的特殊形式。（）2由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。（）3先根遍歷一棵樹和先序遍歷與該樹對應(yīng)的二叉樹，其

37、結(jié)果不同。（×）4先根遍歷森林和先序遍歷與該森林對應(yīng)的二叉樹，其結(jié)果不同。（×）5完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是葉子。（）6對于有N個結(jié)點的二叉樹，其高度為ëlog2Nû1。（×）7若一個結(jié)點是某二叉樹子樹的中序遍歷序列中的最后一個結(jié)點，則它必是該子樹的先序遍歷序列中的最后一個結(jié)點。（）8若一個結(jié)點是某二叉樹子樹的中序遍歷序列中的第一個結(jié)點，則它必是該子樹的后序遍歷序列中的第一個結(jié)點。（）9不使用遞歸也可實現(xiàn)二叉樹的先序、中序和后序遍歷。（）10先序遍歷二叉樹的序列中，任何結(jié)點的子樹的所有結(jié)點不一定跟在該結(jié)點之后。（×）

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

39、則不能。（×）20滿二叉樹一定是完全二叉樹，反之未必。（）5.3.3 簡答題1一棵度為2的樹與一棵二叉樹有何區(qū)別？樹與二叉樹之間有何區(qū)別？【解答】二叉樹是有序樹，度為2的樹是無序樹，二叉樹的度不一定是2。ADBGEHCF(圖 1)二叉樹是有序樹，每個結(jié)點最多有兩棵子樹，樹是無序樹，且每個結(jié)點可以有多棵子樹。2對于圖1所示二叉樹，試給出：（1）它的順序存儲結(jié)構(gòu)示意圖；（2）它的二叉鏈表存儲結(jié)構(gòu)示意圖；（3）它的三叉鏈表存儲結(jié)構(gòu)示意圖。【解答】（1）順序存儲結(jié)構(gòu)示意圖：ABCDEFGH（2）二叉鏈表存儲結(jié)構(gòu)示意圖： （3）三叉鏈表存儲結(jié)構(gòu)示意圖：ABC D E F G H A BC D

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

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

42、由二叉樹的前序序列和中序序列可以唯一地確定一棵二叉樹。證明：給定二叉樹結(jié)點的前序序列和對稱序（中序）序列，可以唯一確定該二叉樹。因為前序序列的第一個元素是根結(jié)點，該元素將二叉樹中序序列分成兩部分，左邊（設(shè)l個元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（設(shè)r個元素）是右子樹，若為空，則右子樹為空。根據(jù)前序遍歷中“根左子樹右子樹”的順序，則由從第二元素開始的l個結(jié)點序列和中序序列根左邊的l個結(jié)點序列構(gòu)造左子樹，由前序序列最后r個元素序列與中序序列根右邊的r個元素序列構(gòu)造右子樹。9已知一棵度為m的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，nm個度為m的結(jié)點，問該樹中共有多少個葉子結(jié)點

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

44、：2h-112求表達式： ab*(cd)e/f的波蘭式（前綴式）和逆波蘭式（后綴式）。波蘭式： - + a * b c d / e f 逆波蘭式：a b c d - * + e f / -13畫出和下列已知序列對應(yīng)的樹T：樹的先根次序訪問序列為：GFKDAIEBCHJ；樹的后根訪問次序為：DIAEKFCJHBG?！窘獯稹繉?yīng)的二叉樹和樹分別如下左、右圖所示：GBIEADKFCHJGBIEADKFCHJ14畫出和下列已知序列對應(yīng)的森林F：森林的先根次序訪問序列為：ABCDEFGHIJKL；森林的后根訪問次序為：CBEFDGAJIKLH。ABDGCEFHIKJL15畫出和下列已知序列對應(yīng)的樹T：二

45、叉樹的層次訪問序列為：ABCDEFGHIJ；二叉樹的中序訪問次序為：DBGEHJACIF。【解答】ABCDEFGHIJ按層次遍歷，第一個結(jié)點（若樹不空）為根，該結(jié)點在中序序列中把序列分成左右兩部分左子樹和右子樹。若左子樹不空，層次序列中第二個結(jié)點左子樹的根；若左子樹為空，則層次序列中第二個結(jié)點右子樹的根。對右子樹也作類似的分析。層次序列的特點是：從左到右每個結(jié)點或是當(dāng)前情況下子樹的根或是葉子。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,（1）為這7個字母設(shè)計哈夫曼編碼。（

46、2）對這7個字母進行等長編碼，至少需要幾位二進制數(shù)？哈夫曼編碼比等長編碼使電文1.000.590.410.280.210.120.310.160.800.400.200.100.11111111總長壓縮多少？ （1）哈夫曼樹：a：10b：110c：010d：1110e：011f：00g：1111（2）對這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=2.54哈夫曼編碼比

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

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