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

1、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ǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定相鄰。（×）6在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。（）7線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（×）8在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除

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

3、目中所給定的數(shù)據(jù)結(jié)構(gòu)（順序存儲(chǔ)的思想是用物理上的相鄰表示邏輯上的相鄰，不一定將向量和表示線性表長(zhǎng)度的變量封裝成一個(gè)結(jié)構(gòu)體），因?yàn)槭琼樞虼鎯?chǔ)，分配的存儲(chǔ)空間是固定大小的，所以首先確定是否還有存儲(chǔ)空間，若有，則根據(jù)原線性表中元素的有序性，來確定插入元素的插入位置，后面的元素為它讓出位置，（也可以從高下標(biāo)端開始一邊比較，一邊移位）然后插入x ，最后修改表示表長(zhǎng)的變量。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)/*邊找位置邊移動(dòng)*/Ai+1=Ai;i-; Ai+1=x;/*找到的位置是插入位的下一位*/ (*elenum)+;return 1;/*插入成功*/時(shí)間復(fù)雜度為O(n)。2已知一順序表A，其元素值非遞減有序排列，編寫一個(gè)算法刪除順序表中多余的值相同的元素。【提示】對(duì)順序表A，從第一個(gè)元素開始，查找其后與之值相同的所有元素，將它們刪除；再對(duì)第二個(gè)元素做同樣處理，依此類推。void delete(Seqlist *A)i=0;while(i<A->last)/*將第i個(gè)元素以后與其值相同的元素刪除*/k

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

6、并不立即刪除，而是用n記錄刪除時(shí)應(yīng)前移元素的位移量；若不是，則將A->datai向前移動(dòng)n位。n用來記錄當(dāng)前已刪除元素的個(gè)數(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;/*否則向前移動(dòng)A->datai*/i+;A->last-=n;4線性表中有n個(gè)元素，每個(gè)元素是

7、一個(gè)字符，現(xiàn)存于向量Rn中，試寫一算法，使R中的字符按字母字符、數(shù)字字符和其它字符的順序排列。要求利用原來的存儲(chǔ)空間，元素移動(dòng)次數(shù)最小。【提示】對(duì)線性表進(jìn)行兩次掃描，第一次將所有的字母放在前面，第二次將所有的數(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線性表用順序存儲(chǔ)，設(shè)計(jì)一個(gè)算法，用盡可能少的輔助存儲(chǔ)空間將順序表中前m個(gè)元素和后n個(gè)元素進(jì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é)點(diǎn)的單鏈表L中的結(jié)點(diǎn)是按整數(shù)值遞增排列的，試寫一算法，將值為x 的結(jié)點(diǎn)插入到表L中，使得L仍然遞增有序，并且分析算法的時(shí)間復(fù)雜度。LinkList insert(LinkList L, int x) p=L; while(p->next && x>p->next->data) p=p->next;/*尋找插入位置*/ s=(LNode *)malloc(sizeof(LNode);/*申請(qǐng)結(jié)點(diǎn)空間*/s->data=x; /*填裝結(jié)點(diǎn)*/s->next=p->next; p->next=s; /*將結(jié)點(diǎn)插入到鏈表中*

12、/ return(L); 7假設(shè)有兩個(gè)已排序（遞增）的單鏈表A和B，編寫算法將它們合并成一個(gè)鏈表C而不改變其排序性。LinkList Combine(LinkList A, LinkList B)C=A;rc=C;pa=A->next;/*pa指向表A的第一個(gè)結(jié)點(diǎn)*/pb=B->next;/*pb指向表B的第一個(gè)結(jié)點(diǎn)*/free(B);/*釋放B的頭結(jié)點(diǎn)*/while (pa && pb)/*將pa、pb所指向結(jié)點(diǎn)中，值較小的一個(gè)插入到鏈表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è)長(zhǎng)度大于1的循環(huán)單鏈表中，既無頭結(jié)點(diǎn)也無頭指針，p為指向該鏈表中某一結(jié)點(diǎn)的指針，編寫算法刪除該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)?！咎崾尽坷醚h(huán)單鏈表的特點(diǎn)，通過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->next!=s)q=p; p=

14、p->next;q->next=s;free(p);9已知兩個(gè)單鏈表A和B分別表示兩個(gè)集合，其元素遞增排列，編寫算法求出A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲(chǔ)?！咎崾尽拷患傅氖莾蓚€(gè)單鏈表的元素值相同的結(jié)點(diǎn)的集合，為了操作方便，先讓單鏈表C帶有一個(gè)頭結(jié)點(diǎn)，最后將其刪除掉。算法中指針p用來指向A中的當(dāng)前結(jié)點(diǎn)，指針q用來指向B中的當(dāng)前結(jié)點(diǎn)，將其值進(jìn)行比較，兩者相等時(shí)，屬于交集中的一個(gè)元素，兩者不等時(shí)，將其較小者跳過，繼續(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è)有一個(gè)雙向鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和next域外，還有一個(gè)訪問頻度freq域，在鏈表被起用之前，該域的值初始化為零。每當(dāng)在鏈表進(jìn)行一次Locata(L,x)運(yùn)算后，令值為x的結(jié)點(diǎn)中的freq域增1，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問頻度的非遞增序列排列，以便使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。試寫一個(gè)滿足上述要求的Locata(L,x)算法?！咎崾尽吭诙ㄎ徊僮鞯耐瑫r(shí)，需要調(diào)整鏈表中結(jié)點(diǎn)的次序：每次進(jìn)行定位操作后，要查看所查找結(jié)點(diǎn)的freq域，將其同前面結(jié)點(diǎn)的freq域進(jìn)行比較，同時(shí)進(jìn)行結(jié)點(diǎn)次序的調(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é)點(diǎn)，使p指向它*/if(!p) return(NULL);/*若查找失敗，返回空指針*/p->freq+;/*修改p的freq域*/while(p->prior!=L&&p->prior->fr

18、eq<p->freq)/*調(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è)棧頂指針為Top的鏈棧中插入一個(gè)p所指結(jié)點(diǎn)時(shí)，其操作步驟為（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對(duì)于棧操作數(shù)據(jù)的原則是（B）。A先進(jìn)先出 B后進(jìn)先出 C后進(jìn)后出 D不分順序3若已知一個(gè)棧的入棧序列是1,2,3,n，其輸出序列為p1,p2,p3，pN,若pN是n，則pi是（D）。Ai Bn-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的底在S

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

21、、尾指針可能都要修改9遞歸過程或函數(shù)調(diào)用時(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ǔ)的非線性結(jié)構(gòu)C限制存取點(diǎn)的線性結(jié)構(gòu) D限制存取點(diǎn)的非線性結(jié)構(gòu)3.3.2 判斷題1棧和隊(duì)列的存儲(chǔ)，既可以采用順序存儲(chǔ)結(jié)構(gòu)，又可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（）2任何一個(gè)遞歸過程都可以轉(zhuǎn)換成非遞歸過程。（）3若輸入序列為1,2,3,4,5,6，則通過一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1。（）4通常使用隊(duì)列來處理函數(shù)的調(diào)用。（×）5循環(huán)隊(duì)列通常用指針來實(shí)現(xiàn)隊(duì)列的頭尾相接。（×）3.3.3 簡(jiǎn)答題1循環(huán)隊(duì)列

22、的優(yōu)點(diǎn)是什么？如何判別它的空和滿？循環(huán)隊(duì)列的優(yōu)點(diǎn)是能夠克服“假溢滿”現(xiàn)象。設(shè)有循環(huán)隊(duì)列sq，隊(duì)滿的判別條件為：（sq->rear+1）%maxsize=sq->front;或sq->num=maxsize。隊(duì)空的判別條件為：sq->rear=sq->front。2棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)各有什么特點(diǎn)，什么情況下用到棧，什么情況下用到隊(duì)列？棧和隊(duì)列都是操作受限的線性表，棧的運(yùn)算規(guī)則是“后進(jìn)先出”，隊(duì)列的運(yùn)算規(guī)則是“先進(jìn)先出”。棧的應(yīng)用如數(shù)制轉(zhuǎn)換、遞歸算法的實(shí)現(xiàn)等，隊(duì)列的應(yīng)用如樹的層次遍歷等。3什么是遞歸？遞歸程序有什么優(yōu)缺點(diǎn)？一個(gè)函數(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，這稱為間接遞歸。在實(shí)際應(yīng)用中，多為直接遞歸，也常簡(jiǎn)稱為遞歸。遞歸程序的優(yōu)點(diǎn)是程序結(jié)構(gòu)簡(jiǎn)單、清晰，易證明其正確性。缺點(diǎn)是執(zhí)行中占內(nèi)存空間較多，運(yùn)行效率低。4設(shè)有編號(hào)為1,2,3,4的四輛車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，試寫出這四輛車開出車站的所有可能的順序（每輛車可能入站，可能不入站，時(shí)間也可能不等）。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,43214.3 課后習(xí)題解答#4.3.1 選

24、擇題1下面關(guān)于串的敘述錯(cuò)誤的是（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,其Next數(shù)組值為（D）。A0123 B1123 C1231 D12114二維數(shù)組M的成員是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é)；若M按行優(yōu)先方式存儲(chǔ)，元素M85的起始地址與當(dāng)M按列

25、優(yōu)先方式存儲(chǔ)時(shí)的（C）元素的起始地址一致。（1）A90 B180 C240 D540（2）A108 B114 C54 D60（3）AM85 BM310 CM58 DM095數(shù)組A中，每個(gè)元素的存儲(chǔ)占3個(gè)單元，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元個(gè)數(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、矩陣采用壓縮存儲(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ù)組是線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對(duì)它進(jìn)行插入，刪除等操作。（×）5若采用三元組存儲(chǔ)稀疏矩陣，把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算。（×）6若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。（×）7所謂取廣義表的表尾就是返回廣義表中最后一個(gè)元素。（&

27、#215;）4.3.3 簡(jiǎn)答題1KMP算法較樸素的模式匹配算法有哪些改進(jìn)?KMP算法主要優(yōu)點(diǎn)是主串指針不回溯。當(dāng)主串很大不能一次讀入內(nèi)存且經(jīng)常發(fā)生部分匹配時(shí)，KMP算法的優(yōu)點(diǎn)更為突出。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)先存儲(chǔ)整數(shù)數(shù)組A9358時(shí)，第一個(gè)元素的字節(jié)地址是100，每個(gè)整數(shù)占個(gè)字節(jié)。問下列元素的存儲(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ì)角矩陣：a11 a12a2

30、1 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寫出下標(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=

31、i+j-i%2-1。5設(shè)有n×n的帶寬為3的帶狀矩陣A，將其3條對(duì)角線上的元素存于數(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畫出下列廣義表的頭尾表示存儲(chǔ)結(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二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2 B二叉樹的度為2C一棵二叉樹的度可小于2 D任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為22以二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中（n>0），空鏈

33、域的個(gè)數(shù)為（C）。A2n-1 Bn-1 Cn+1 D2n+13線索化二叉樹中，某結(jié)點(diǎn)*p沒有孩子的充要條件是（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某二叉樹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)等于左子樹上的最小編號(hào)減,而v的右子樹的結(jié)點(diǎn)中,其最小編號(hào)等于v左子樹上結(jié)點(diǎn)的最大編號(hào)加，這是按

34、（B）編號(hào)的。A 中序遍歷序列 B 先序遍歷序列 C 后序遍歷序列 D 層次順序 6設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，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一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（B）。A 500 B 501 C490 D4958設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(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 DN2+N39任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序、后序遍歷序列中的相對(duì)次序（A）。A不發(fā)生改變 B 發(fā)生改變

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

36、 B為了能在二叉樹中方便的進(jìn)行插入與刪除C為了能方便的找到雙親 D使二叉樹的遍歷結(jié)果唯一 14設(shè)高度為h的二叉樹上只有度為和度為的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（B）。A2*h B 2*h-1 C 2*h+1 Dh+115一個(gè)具有567個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（D）。A9 B10 C9至566之間 D10至567之間16給一個(gè)整數(shù)集合3，5，6，7，9，與該整數(shù)集合對(duì)應(yīng)的哈夫曼樹是（B）。A B C D93765 3567979536765395.3.2 判斷題1二叉樹是樹的特殊形式。（）2由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的。（）3先根遍歷一棵樹和先序遍歷與該樹對(duì)應(yīng)的二叉樹，其

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

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

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

40、E F G H IDEFGCBANMKJH(圖 2)3對(duì)于圖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)換后所對(duì)應(yīng)的二叉樹，并指出森林中滿足什么條件的結(jié)點(diǎn)在二叉樹中是葉子。DBCIG

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

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

43、？有多少個(gè)非終端結(jié)點(diǎn)？解：設(shè)樹中共有n個(gè)結(jié)點(diǎn)，n0個(gè)葉結(jié)點(diǎn)，那么n=n0+n1+nm (1)樹中除根結(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在具有n（n>1）個(gè)結(jié)點(diǎn)的樹中，深度最小的那棵樹其深度是多少？它共有多少葉子和非葉子結(jié)點(diǎn)？深度最大的那棵樹其深度是多少？它共有多少葉子和非葉子結(jié)點(diǎn)？2; n-1; 1; n; 1, n-111設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，問該二叉樹的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值和最小值。最大值：2h-1； 最小值

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

45、叉樹的層次訪問序列為：ABCDEFGHIJ；二叉樹的中序訪問次序?yàn)椋篋BGEHJACIF?！窘獯稹緼BCDEFGHIJ按層次遍歷，第一個(gè)結(jié)點(diǎn)（若樹不空）為根，該結(jié)點(diǎn)在中序序列中把序列分成左右兩部分左子樹和右子樹。若左子樹不空，層次序列中第二個(gè)結(jié)點(diǎn)左子樹的根；若左子樹為空，則層次序列中第二個(gè)結(jié)點(diǎn)右子樹的根。對(duì)右子樹也作類似的分析。層次序列的特點(diǎn)是：從左到右每個(gè)結(jié)點(diǎn)或是當(dāng)前情況下子樹的根或是葉子。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,（1）為這7個(gè)字母設(shè)計(jì)哈夫曼編碼。（

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

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

48、d方式存儲(chǔ)，鏈接時(shí)用葉結(jié)點(diǎn)的rchild域存放鏈指針?！咎崾尽窟@是一個(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為空。LinkList head,pre=NULL;/*全局變量*/LinkList InOrder(BiTree T) /*中序遍歷二叉樹T，將葉子結(jié)點(diǎn)從左到右鏈成一個(gè)單鏈表，表頭指針為he