數(shù)據(jù)結(jié)構(gòu)簡明教程-練習(xí)題答案（李春葆版）

數(shù)據(jù)結(jié)構(gòu)簡明教程(第2版)清華大學(xué)出版社 1.練習(xí)題1參考答案1.單項(xiàng)選擇題2.填空題(1)①邏輯結(jié)構(gòu)②存儲(chǔ)結(jié)構(gòu)③運(yùn)算(不限制順序)(2)①線性結(jié)構(gòu)②非線性結(jié)構(gòu)(不限制順序)(3)①數(shù)據(jù)元素②關(guān)系(4)①?zèng)]有②沒有(5)①前驅(qū)②一③后繼④任意多個(gè)(6)任意多個(gè)(7)①順序②鏈?zhǔn)舰鬯饕芄?不限制順序)(8)①時(shí)間②空間(不限制順序)(9)問題規(guī)模(通常用n表示)。(10)輔助或臨時(shí)空間3.簡答題(1)答：運(yùn)算描述是指邏輯結(jié)構(gòu)施加的操作，而運(yùn)算實(shí)現(xiàn)是指一個(gè)完成該運(yùn)算功能的算法。它們的相同點(diǎn)是，運(yùn)算描述和運(yùn)算實(shí)現(xiàn)都能完成對(duì)數(shù)據(jù)的“處理”或某種特定的操作。不同點(diǎn)是，運(yùn)算描述只是描述處理功能，不包括處理步驟和方法，而運(yùn)算實(shí)現(xiàn)的核心則是處理步驟。j=3,s=60。第4次循環(huán)：j=4,s=1次數(shù)為4。(4)答：語句s++的執(zhí)行次數(shù),該程序段的時(shí)間復(fù)雜度為O(n2)。32.練習(xí)題2參考答案(11)B(12)A(13)C2.填空題(2)O(1)(3)O(n)(5)①物理存儲(chǔ)位置②指針域(6)①前驅(qū)②O(n)(7)q=p->next;p->next=q->next;free(q);(8)s->next=p->next;p->next=s;(9)O(1)(1)答：順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰元素的存儲(chǔ)空間也是相鄰的，無需額外空間表示邏輯關(guān)系，所以存儲(chǔ)密度大，同時(shí)具有隨機(jī)存取特性。缺點(diǎn)是插入或刪除元素時(shí)平均需要移動(dòng)一半的元素，同時(shí)順序存儲(chǔ)結(jié)構(gòu)的初始分配空間大小難以事先確定。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰元素的存儲(chǔ)空間不一定是相鄰的，需要通過指針域需表示邏輯關(guān)系，所以存儲(chǔ)密度較小，同時(shí)不具有隨機(jī)存取特性。優(yōu)點(diǎn)是插入或刪除時(shí)不需要結(jié)點(diǎn)的移動(dòng)，僅僅修改相關(guān)指針域，由于每個(gè)結(jié)點(diǎn)都是動(dòng)態(tài)分配的，所以空間分配適應(yīng)性順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。(2)答：對(duì)于表長為n的順序表，在等概率的情況下，插入一個(gè)元素所需要移動(dòng)元素的平均次數(shù)為n/2,刪除一個(gè)元素所需要移動(dòng)元素的平均次數(shù)為(n-1)/2。(3)答：在鏈表中設(shè)置頭結(jié)點(diǎn)后，不管鏈表是否為空表，頭結(jié)點(diǎn)指針均不空；另外使得鏈表的操作(如插入和刪除)在各種情況下得到統(tǒng)一，從而簡化了算法的實(shí)現(xiàn)過程。(4)答：對(duì)于雙鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)時(shí)，需修改前驅(qū)結(jié)點(diǎn)的next域、后繼結(jié)點(diǎn)的prior域和新插入結(jié)點(diǎn)的next、prior域。所以共修改4個(gè)指針。對(duì)于單鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)時(shí)，需修改前一結(jié)點(diǎn)的next域，新插入 (5)答：在單鏈表中，刪除第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)。插入結(jié)點(diǎn)需找到前驅(qū)結(jié)點(diǎn)，所以在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)，需找到尾結(jié)點(diǎn)，對(duì)應(yīng)的時(shí)間復(fù)雜度為O(n)。刪除第一個(gè)結(jié)點(diǎn)后還要將其改為循環(huán)單鏈表；在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)的在雙鏈表中，刪除第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1);在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)，也在僅有尾指針的循環(huán)單鏈表中，通過該尾指針可一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1);在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)也就是在尾指針?biāo)附Y(jié)點(diǎn)之后(1)解：設(shè)順序表L中元素個(gè)數(shù)為n。i從0到n-2掃描順序表L:若L.data[i]大于voidReverse(SqList&L)ElemTypex;L.data[i]=L.data[L.length-i-1];L.data[L.length-i-1]=x;}}本算法的時(shí)間復(fù)雜度為O(n)。(3)解：通過掃描順序表L求出最后一個(gè)最大元素的下標(biāo)maxi。將voidInsertx(SqList&L,ElemTypex)5maxi=i;//將data[maxi+1..n-1]后移//插入元素x//順序表長度增1大于L.data[i],將兩者交換，掃描結(jié)束后最大元素移到L的最后面。對(duì)應(yīng)的算法如下：ElemTypetmp;}(5)解：用p指針遍歷整個(gè)單鏈表，pre總是指向p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)(初始時(shí)pre指向頭結(jié)點(diǎn)，p指向首結(jié)點(diǎn)),當(dāng)p指向第一個(gè)值為x的結(jié)點(diǎn)時(shí)，通過pre結(jié)點(diǎn)將其刪除，返回1;否則返回0。對(duì)應(yīng)的算法如下：intDelx(SLinkNode*&}if(p!=NULL)}//pre指向p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)//pre、p同步后移//找到值為x的結(jié)點(diǎn)//刪除p結(jié)點(diǎn)//未找到值為x的結(jié)點(diǎn)(6)解：判定鏈表L從第2個(gè)結(jié)點(diǎn)開始的每個(gè)結(jié)點(diǎn)值是否比其前驅(qū)結(jié)點(diǎn)值大。若有一個(gè)不成立，則整個(gè)鏈表便不是遞增的；否則是遞增的。對(duì)應(yīng)的算法如下：intincrease(SLinkNode*L){SLinkNode*pre=L->next,*p;//pre指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)——————-數(shù)據(jù)結(jié)構(gòu)簡明教程一//p指向pre結(jié)點(diǎn)的后繼結(jié)點(diǎn){if(p->data>=pre->data)//若正序則繼續(xù)判斷下一個(gè)結(jié)點(diǎn){}//pre、p同步后移}A、B。用p遍歷原單鏈表A的所有數(shù)據(jù)結(jié)點(diǎn)，若為偶數(shù)結(jié)點(diǎn)，將其鏈到A中，若為奇數(shù)ta=A;B=(SLinkNode*)malloc(sizeoftb=B;//ta總是指向A鏈表的尾結(jié)點(diǎn)(SLinkNode));//建立頭結(jié)點(diǎn)B//tb總是指向B鏈表的尾結(jié)點(diǎn)//偶數(shù)結(jié)點(diǎn){}{//將p結(jié)點(diǎn)鏈到A中//奇數(shù)結(jié)點(diǎn)//將p結(jié)點(diǎn)鏈到B中本算法的時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)。向頭結(jié)點(diǎn)，p指向首結(jié)點(diǎn)),當(dāng)p指向結(jié)點(diǎn)的結(jié)點(diǎn)值剛好大于x時(shí)查找結(jié)束。新創(chuàng)建一個(gè)結(jié)點(diǎn)s存放元素x,將其插入到pre結(jié)點(diǎn)之后。對(duì)應(yīng)的算法如下：7{}//pre、p同步后移s=(SLinkNode*)malloc(sizeof(SLinkNode));s->data=x;//建立一個(gè)待插入的結(jié)點(diǎn)pre->next=s;//在結(jié)點(diǎn)pre之后插入s結(jié)點(diǎn)}(9)解：掃描L的所有數(shù)據(jù)結(jié)點(diǎn)，復(fù)制產(chǎn)生L1的結(jié)點(diǎn)，采用尾插法創(chuàng)建L1。對(duì)應(yīng)L1=(SLinkNode*)malloc(sizeof(SLinkNode));//創(chuàng)建L1的頭結(jié)點(diǎn)tc=L1;{s=(SLinkNode*)malloc(sizeof(SLinkNode));s->data=p->data;//由p結(jié)點(diǎn)復(fù)制產(chǎn)生s結(jié)點(diǎn)tc->next=s;//將s結(jié)點(diǎn)鏈接到L1末尾}}(10)解：用p掃描單鏈表L,pre指向p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，minp指向最小值結(jié)點(diǎn)，minpre指向最小值結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。當(dāng)p不為L時(shí)循環(huán)：若p所指結(jié)點(diǎn)值小于等于minp指向最后一個(gè)最小結(jié)點(diǎn)，通過minpre結(jié)點(diǎn)將minp結(jié)點(diǎn)從中刪除，然后將其插入到表頭即while(p!=L)}pre=p;minpre->next=minp->next;//刪除minp結(jié)點(diǎn)minp->next=L->next;} -—數(shù)據(jù)結(jié)構(gòu)簡明教程-//將minp結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后p=q;//建立一個(gè)空循環(huán)單鏈表//掃描所有數(shù)據(jù)結(jié)點(diǎn)//臨時(shí)保存p結(jié)點(diǎn)的后繼結(jié)點(diǎn)//將p結(jié)點(diǎn)插入到前端if(p==NULL)//未找到值為x的結(jié)點(diǎn){pre=p->prior;//pre指向結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn){pre->next=p->next;//先刪除p結(jié)點(diǎn)p->prior=pre->prior;//將p結(jié)點(diǎn)插入到pre結(jié)點(diǎn)之前return0;//表示值為x的結(jié)點(diǎn)是首結(jié)點(diǎn)9中刪除p結(jié)點(diǎn)，再將p結(jié)點(diǎn)插入到pre結(jié)點(diǎn)之前。本算法需要遍歷整個(gè)雙鏈表才能找到尾{//post指向p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)pre->next=p->next;//刪除p結(jié)點(diǎn)pre->prior=p;//將p結(jié)點(diǎn)插入到pre結(jié)點(diǎn)之前(14)解：p從循環(huán)雙鏈表L的首結(jié)點(diǎn)開始掃描，當(dāng)p≠L時(shí)循環(huán)：若p結(jié)點(diǎn)值為x,post=p->next臨時(shí)保存其后繼結(jié)點(diǎn)，通過p結(jié)點(diǎn)前后指針域刪除p結(jié)點(diǎn)，并釋放其空間，置p=post繼續(xù)查找；若p結(jié)點(diǎn)值不為x,執(zhí)行p=p->next。對(duì)應(yīng)的算法如下：while(p!=L)//掃描數(shù)據(jù)結(jié)點(diǎn)pfree(p);//釋放p結(jié)點(diǎn)p=post;(15)解：通過L->prior找到尾結(jié)點(diǎn)p。pre指向p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后從鏈表中刪除p結(jié)點(diǎn)，再將p結(jié)點(diǎn)插入到pre結(jié)點(diǎn)之前。本算法不含有循環(huán)語句，所以算法的時(shí)間pre=p->prior;//pre指向p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)pre->next=p->next;//刪除p結(jié)點(diǎn)p->next->prior=pre;pre->prior->next=p;p->prior=pre->prior;pre->prior=p;3.練習(xí)題3參考答案(1)①棧頂②棧底(3)1進(jìn)棧，1出棧，2進(jìn)棧，2出棧，3進(jìn)棧，3出棧，4進(jìn)棧，4出棧，5進(jìn)棧，5(7)隊(duì)列(8)rear=(rear+1)%(m+1);A[rear]=x;(9)front=(front+1)%(m+1);x=A[front];因而是先進(jìn)先出表FIFO。②用途不同，棧用于子程調(diào)用和保護(hù)現(xiàn)場等，隊(duì)列用于多道作一個(gè)方向伸長的，如果棧底設(shè)置在中間，伸長方向的另外一(3)答：棧中元素之間的邏輯關(guān)系屬線性關(guān)系，可以采用單鏈表、循環(huán)單鏈表和雙鏈表之一來存儲(chǔ)，而棧的主要運(yùn)算是進(jìn)棧和出棧，當(dāng)采用①時(shí)，前端作為棧頂，進(jìn)棧和出棧運(yùn)算的時(shí)間復(fù)雜度為O(1)。當(dāng)采用②時(shí)，前端作為棧頂，當(dāng)進(jìn)棧和出棧時(shí)，首結(jié)點(diǎn)都發(fā)生變化，還需要找到尾結(jié)點(diǎn)，通過修改其next域使其變?yōu)檠h(huán)單鏈表，算法的時(shí)間復(fù)雜度為O(n)。當(dāng)采用③時(shí)，前端作為棧頂，進(jìn)棧和出棧運(yùn)算的時(shí)間復(fù)雜度為O(1)。但單鏈表和雙鏈表相比，其存儲(chǔ)密度更高，所以本題中最適合用作鏈棧的是帶頭結(jié)點(diǎn)(4)答：在循環(huán)隊(duì)列中插入和刪除元素時(shí)，不需要移動(dòng)隊(duì)中任何元素，只需要修改隊(duì)尾或隊(duì)頭指針，并向隊(duì)尾插入元素或從隊(duì)頭取出元素。(5)答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有進(jìn)隊(duì)操作，采用循環(huán)隊(duì)列是解決假溢出的途徑，解決循環(huán)隊(duì)列是空還是滿的辦法如下：①設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；②浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。③使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)(即隊(duì)列長度)。通常采用法②,讓隊(duì)頭指針front指向隊(duì)首元素的前一位置，隊(duì)尾指針rear指向隊(duì)尾(rear+1)%MaxSize=fro(1)解：定義一個(gè)棧st,正向掃描a的所有字符，將每個(gè)字符進(jìn)棧。再出棧所有字符，將其寫入到a[0..n-1]中。對(duì)應(yīng)的算法如下：//逆置a[0..n-1]Push(st,a[i]);}DestroyStack(st);}//定義一個(gè)順序棧st//依次將a[0..n-1]進(jìn)棧//將a[n-1]～a[0]依次存放到a[0..n-1]//銷毀棧st(2)解：算法原理與《教程》中例3.9相同，僅僅將二進(jìn)制改為八進(jìn)制。對(duì)應(yīng)的算//b用于存放d轉(zhuǎn)換成的八進(jìn)制數(shù)的字符串//定義一個(gè)順序棧st//棧初始化while(d!=0)Push(st,ch);}while(!StackEmpty(st))b[i]=ch;了b[i]=’\0';DestroyStack(st);}//求余數(shù)并轉(zhuǎn)換為字符//字符ch進(jìn)棧//繼續(xù)求更高位//出棧并存放在數(shù)組b中//添加字符串結(jié)束標(biāo)志(3)解：對(duì)于給定的棧st,設(shè)置一個(gè)臨時(shí)棧tmpst,先退棧st中所有元素并進(jìn)入到棧tmpst中，最后的一個(gè)元素即為所求，然后將臨時(shí)棧tmpst中的元素逐一出棧并進(jìn)棧到st中，這樣恢復(fù)st棧中原來的元素。對(duì)應(yīng)算法如下：intGetBottom(SqStackst,ElemType&x)//x在算法返回1時(shí)保存棧底元素{if(StackEmpty(st))//定義臨時(shí)棧//初始化臨時(shí)棧//空棧返回0}while(!StackEmpty(st))Push(tmpst,x);}while(!StackEmpty(tmpst))Push(st,e);//臨時(shí)棧tmpst中包含st棧中逆轉(zhuǎn)元素//恢復(fù)st棧中原來的內(nèi)容DestroyStack(tmpst);//返回1表示成功(4)解：由于算法要求空間復(fù)雜度為O(1),所以不能使用一個(gè)臨時(shí)隊(duì)列。先利用例3.13的算法求出隊(duì)列qu中的元素個(gè)數(shù)m。循環(huán)m次，出次一個(gè)元素x,再將元素x進(jìn)隊(duì)。最后的x即為隊(duì)尾元素。對(duì)應(yīng)的算法如下：intCount(SqQueuesq)//求循環(huán)隊(duì)列qu中元素個(gè)數(shù){return(sq.rear+MaxSize-sq.front)%MaxSize;}intLast(SqQueuequ,ElemType&x)//求解算法//隊(duì)中元素個(gè)數(shù)為0返回0{DeQueue(qu,x);EnQueue(qu,x);//出隊(duì)元素x//將元素x進(jìn)隊(duì)}return1;//成功找到隊(duì)尾元素返回1intCount(SqQueuesq)//求循環(huán)隊(duì)列qu中元素個(gè)數(shù){return(sq.rear+MaxSize-sq.front)%MaxSize;}if((e-'0')%2!=1)EnQueue(qu,e);//求解算法//將不是奇數(shù)的數(shù)字字符進(jìn)隊(duì)4.練習(xí)題4參考答案(1)①不包含任何字符(長度為0)的串②由一個(gè)或多個(gè)空格(僅由空格符)組成(3)O(n)(5)O(n)3.簡答題(1)答：由串s的特性可知，1個(gè)字符的子串有n個(gè)，2個(gè)字符的子串有n-1個(gè)，3個(gè)字符的子串有n-2個(gè)，…,n-2個(gè)字符的子串有3個(gè)，n-1個(gè)字符的子串有2個(gè)。所②s?或s?其中之一為空串③s?和s?為相同的串④若s?和s?兩串長度不等，則長串由整數(shù)個(gè)短串組成。(3)答：只要將線性表中元素類型改為char,該線性表就是串，所以將單鏈表中結(jié)點(diǎn)數(shù)據(jù)域的類型改為char,則基于單鏈表的算法設(shè)計(jì)方法都可以應(yīng)用于鏈串。4.算法設(shè)計(jì)題(1)解：因要求算法空間復(fù)雜度為O(1),所以只能對(duì)串s直接替換。從頭開始掃描順序串s,一旦找到字符x便將其替換成y。對(duì)應(yīng)算法如下：voidRepchar(SqString&s,charx,if(s.data[i]==x)}(2)解：置i、j均為0。當(dāng)i<s.length時(shí)循環(huán)：將s.data[i]復(fù)制到t.data[j]中，i增大2,j增大1。最后置串t的長度為j。對(duì)應(yīng)的算法如下：while(i<s.length)i+=2;j++;}t.length=j;}(3)解：用i用于掃描串s,j、k分別表示串s1、s2的字符個(gè)數(shù)，初值均為0。當(dāng)i<s.length時(shí)循環(huán)：若s.data[i]為數(shù)字字符，將其復(fù)制到s1中，置j++;若s.data[i]為字母字符，將其復(fù)制到s2中，置k++。循環(huán)結(jié)束后，置s1、s2的長度分別為j、k。對(duì)應(yīng)的算voidSplit(SqStrings,SqString&sl,SqStwhile(i<s.length){if(s.data[i]>=’0'&&s.data[i]<=’9’)//數(shù)字字符j++;}elseif((s.data[i]>='a'&&s.data[i]<='z')|(s.data[i]>='A’&&s.data[i]<='Z'))//字母字符k++;}}}(4)解：用pre和p指向鏈串s的兩個(gè)連續(xù)結(jié)點(diǎn)(初始時(shí)pre=s->next,否則返回0。當(dāng)所有字符都是遞增排列時(shí)返回1。對(duì)應(yīng)的算法如下：}else//逆序時(shí)返回0(5)解：用maxcount存放串s中最長等值子串的長度(初始為0)最大平臺(tái)長度。用p掃描串s,計(jì)算以p結(jié)點(diǎn)開始的等值子串的長度count(該等值子串尾結(jié)點(diǎn)的后繼結(jié)點(diǎn)為post),若count大于maxcount,則置maxcount為count。再置p=post繼續(xù)查找下一個(gè)post=p->next;———————數(shù)據(jù)結(jié)構(gòu)簡明教程一post=post->next;}if(count>maxcount)maxcount=count;p=post;returnmaxcount;5.練習(xí)題5參考答案2.填空題(2)LOC(A[0][0])+(n×i+j)×k(7)行下標(biāo)、列下標(biāo)和元素值3.簡答題(1)答：數(shù)組的主要基本運(yùn)算如下：①取值運(yùn)算：給定一組下標(biāo)，讀取其對(duì)應(yīng)的數(shù)組元素。②賦值運(yùn)算：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)組元素。(2)答：從邏輯結(jié)構(gòu)的角度看，一維數(shù)組是一種線性表；二維數(shù)組可以看成數(shù)組元素為一維數(shù)組的一維數(shù)組，所以二維數(shù)組是線性結(jié)構(gòu)，可以看成是線性表，但就二維數(shù)組的形狀而言，它又是非線性結(jié)構(gòu)，因此將二維數(shù)組看成是線性表的推廣更準(zhǔn)確。三維及以(3)答：因?yàn)閿?shù)組使用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)時(shí)需要額外占用更多的存儲(chǔ)空間，而且不具有(4)答：設(shè)數(shù)組的元素類型為ElemType,采用一種結(jié)構(gòu)體數(shù)組B來實(shí)現(xiàn)壓縮存儲(chǔ)，{ElemTypedata;intlength;//重復(fù)元素的個(gè)數(shù)如數(shù)組A[]={1,1,1,5,5,5,5,3,3,3,3,4,4,4,4,4,4},素，對(duì)應(yīng)的壓縮存儲(chǔ)B如下：共有17個(gè)元壓縮數(shù)組B中僅有8個(gè)整數(shù)。從中看出，如果重復(fù)元素越多，采用這種壓縮存儲(chǔ)方式4.算法設(shè)計(jì)題(1)解：從前向后找為零的元素A[i],從后向前找非零的元素A[j],將A[i]和A[j]進(jìn)voidmove(ElemTypeA[],intn)ElemTypetmp;while(i<j){while(A[i]!=0)i++;while(A[j]==0)j--;if(i<j)//從前向后找零元素A[i]//從后向前找非零元素A[j]//A[i]與A[j]交換A[j]=tmp;}}}(2)解：當(dāng)參數(shù)錯(cuò)誤時(shí)算法返回0;否則先置mini=i,k從i+1的j循環(huán)：比較將最小元素的下標(biāo)放在mini中。對(duì)應(yīng)的算法如下：intMinij(inta[],intn,inti,intj,int&mini)return0;//參數(shù)錯(cuò)誤返回0if(a[k]<a[mini])mini=k;return1;//成功找到返回1}(3)解：用sum記錄a中下三角和主對(duì)角部分的所有元素和(初始為0),i從0到n-1、j從0到i循環(huán)，執(zhí)行sum+=a[i][j],最后返回sum。對(duì)應(yīng)的算法如下： —數(shù)據(jù)結(jié)構(gòu)簡明教程一intLowDiag(inta[][N],intn)}對(duì)應(yīng)的算法如下：voidOutput(inta[][N],intn)}6.練習(xí)題6參考答案2.填空題(9)①a結(jié)點(diǎn)最左下結(jié)點(diǎn)②a結(jié)點(diǎn)的最右下結(jié)點(diǎn)。(1)答：度為2的樹中某個(gè)結(jié)點(diǎn)只有一個(gè)孩子時(shí)，不區(qū)分左右孩子，而二叉樹中某個(gè)結(jié)點(diǎn)只有一個(gè)孩子時(shí)，嚴(yán)格區(qū)分是左孩子還是右孩子。一棵度為2的樹至少有3個(gè)結(jié)點(diǎn)，而一棵二叉樹的結(jié)點(diǎn)個(gè)數(shù)可以為0。全二叉樹時(shí)高度最小，此時(shí)高度h=「log?(n+1)]=「log?1201=7。所以含有60個(gè)葉子結(jié)點(diǎn)的二叉樹的最小高度是7。(3)答：由二叉樹的性質(zhì)可知，n?=n?-1。設(shè)這樣的完全二叉樹中結(jié)點(diǎn)數(shù)為n,其中度為1的結(jié)點(diǎn)數(shù)n至多為1,所以n=no+(no-1)+1=2n?或n=2no-1。(4)答：按層序編號(hào)時(shí)，完全二叉樹的結(jié)點(diǎn)編號(hào)為1～n,如果已知各類結(jié)點(diǎn)個(gè)數(shù)，該完全二叉樹的形態(tài)一定是確定的。no=n?+1,n=no+n?+n?=2no-1+n?,no=(n-n?+1)/2,從而n?和n?也確定了，所以這樣的完全(5)答：設(shè)度為0、1、2的結(jié)點(diǎn)個(gè)數(shù)及總結(jié)點(diǎn)數(shù)分別為n?、n?、n?和n,則有：no=50,n=no+n?+n?,度之和=n-1=n?+2×n?由以上三式可得：n?=49。這樣n=n?+99,所以當(dāng)n?=0時(shí)，n最少，因此n至少有99個(gè)結(jié)點(diǎn)。(6)答：①該二叉樹如圖6.1所示。②結(jié)點(diǎn)D的雙親結(jié)點(diǎn)為結(jié)點(diǎn)A,其左子樹為以C為根結(jié)點(diǎn)的子樹，其右子樹為空。③由此二叉樹還原成的森林如圖6.2所示。(7)答：由這些顯示部分推出二叉樹如圖6.3所示。則先序序列為ABDFKICEHJG;中序序列為DBKFLAHEJCG;后序序列為DKIFBHJEGCA。 圖6.3一棵二叉樹(8)答：二叉樹的先序序列是NLR(N代表根結(jié)點(diǎn)，L、R分別代表左右子樹),后序序列是LRN。要使NLR=LRN成立，則L和R均為空，所以滿足條件的二叉樹只有一個(gè)(9)答：不是。如n=3,該二叉樹的先序序列為1、2、3,它的中序序列不可能是3、1、2,如果是的話，由先序序列可知1為根結(jié)點(diǎn)，由中序序列求出1的左孩子結(jié)點(diǎn)為3,右孩子結(jié)點(diǎn)為2,而先序序列中緊跟1的是結(jié)點(diǎn)2,這樣無法由先序和中序構(gòu)造出一棵二叉樹，說明該中序序列是錯(cuò)誤的。實(shí)際上，若先序遍歷序列為1、2、…、n,中序序列是1～n的出棧序列時(shí)，可以構(gòu)造出一棵唯一的二叉樹。(10)答：一棵哈夫曼樹中只有度為2和0的結(jié)點(diǎn)，沒有度為1的結(jié)點(diǎn)，由非空二叉樹(1)解：由二叉樹順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)，可得到以下求離i和j的兩個(gè)結(jié)點(diǎn)最近的公共while(p!=q)returnA[p];}A[],inti,intj)voidPreOrderl(ElemTypePreOrderl(A,2*i,n);PreOrderl(A,2*i+1,n);//不為空結(jié)點(diǎn)時(shí)//訪問根結(jié)點(diǎn)//遍歷左子樹//遍歷右子樹}f(bt)=bt->dataf(bt)=MAX{f(bt->Ichild),fbt->rchild),bt->data}只有一個(gè)結(jié)點(diǎn)時(shí)其他情況returnbt->data;{}maxl=MaxNode(bt->lchild);max2=MaxNode(bt->rchild);if(maxl>max)max=max1;if(max2>max)max=max2;//求左子樹的最大結(jié)點(diǎn)值//求右子樹的最大結(jié)點(diǎn)值//求最大值//返回最大值NULL。若當(dāng)前b所指結(jié)點(diǎn)值為x,返回b;遞歸調(diào)用p=Findx(b->Ichild,x)在左子樹中查找值為x的結(jié)點(diǎn)地址p,若p不為空，表示找到了，返回p;否則遞歸調(diào)用BTNode*Findx(BTNode*b,charx)if(b==NULL)returnb;p=Findx(b->lchild,x);if(p!=NULL)returnp;returnFindx(b->rchild,x);}f(b,x)=0f(b,x)=1+f(b->lchild,x)+f(b->rchild,x);f(b,x)=f(b->lchild,x)+f(b->rchild,x);b=NULL其他情況———————數(shù)據(jù)結(jié)構(gòu)簡明教程—-if(b==NULL)if(b->data==x)n=1;nl=FindCount(b->lchild,x);nr=FindCount(b->rchild,x);}(6)解：設(shè)計(jì)PrintLNodes(b)算法用于從左到右輸出二叉樹b中的所有葉子結(jié)點(diǎn)。當(dāng)b為空時(shí)返回。當(dāng)b所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)時(shí)輸出b->data值；遞歸調(diào)用PrintLNodes(b->Ichild)輸出左子樹中葉子結(jié)點(diǎn)值，遞歸調(diào)用PrintLNodes(b->rchild)輸出右子樹中葉子結(jié)點(diǎn)值。對(duì)應(yīng)的算法如下：printf("%c",b->data);PrintLNodes(b->lchild);PrintLNodes(b->rchild);}(7)解：設(shè)f(b1,b2)用于判斷兩個(gè)二叉樹b1和b2是否相同，對(duì)應(yīng)的遞歸模型如f(b1,b2)=f(b1->Ichild,b2->Ichild)&f(b1->rchild,b2->rchild)當(dāng)b1、b2均為空當(dāng)b1、b2中一個(gè)為空，另一個(gè)不為空其他情況}(8)解：哈夫曼樹b的帶權(quán)路徑長度(WPL)等于所有葉子結(jié)點(diǎn)權(quán)值乘以層次的總voidWPL1(HNode*b,inth,int&sum)WPL1(b->rchild,h+1,sum);}intWPL(HNode*b)WPL1(b,1,sum);//求解算法7.練習(xí)題7參考答案1.單項(xiàng)選擇題(21)A(22)A(23)C(24)D(26)D(27)A(28)D(29)A2.填空題(2)①鄰接矩陣②鄰接表(11)極小連通子圖012301234560一00(12)①O(n2)(12)①O(n2)②O(elogze)③Kruskal(13)4和5。3.簡答題(1)答：設(shè)圖的頂點(diǎn)個(gè)數(shù)和邊數(shù)分別為n和e。鄰接矩陣的存儲(chǔ)空間大小為O(n2),與e無關(guān)，因此適合于稠密圖的存儲(chǔ)。鄰接表的存儲(chǔ)空間大小為O(n+e)(有向圖)或O(n+2e)(無向圖),與e有關(guān)，因此適合于稀疏圖的存儲(chǔ)。(2)答：圖的這兩種遍歷算法對(duì)無向圖和有向圖都適用。但如果無向圖不是連通的，調(diào)用一次遍歷算法只能訪問一個(gè)連通分量中的所有頂點(diǎn)。如果有向圖不是強(qiáng)連通的，調(diào)用一次遍歷算法可能不能訪問圖中全部頂點(diǎn)。圖G對(duì)應(yīng)的鄰接表如圖7.8所示，對(duì)于該鄰接表，從頂點(diǎn)0出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列都是0、1、2、3、4。ViV?V?012343434000222(4)答：DFSTrav(G,v)算法是在頂點(diǎn)v的所有出邊相鄰點(diǎn)均訪問后才輸出該頂點(diǎn)的編號(hào)。從頂點(diǎn)0出發(fā)的深度優(yōu)先遍歷過程是：0→1,1→2,2回退到1,1→3,3→4,依次回退到0。首先輸出2(最先沒有出邊相鄰點(diǎn)),接著是4(第2個(gè)沒有出邊相鄰點(diǎn)),再是3、1、0。實(shí)際上，對(duì)于無環(huán)有向圖，該算法輸出序列的反序恰好是一個(gè)拓?fù)湫蛄小?5)答：利用普里姆算法從頂點(diǎn)0出發(fā)構(gòu)造的最小生成樹為：{(0,1),(0,3),(1,2),(2,5),(5,4)}。利用克魯斯卡爾算法構(gòu)造出的最小生成樹為：{(0,1),(0,3),01234560ooo70660006600066030065603006560300656030000700070o7070707從0到1的最短路徑長度為：22路徑為：0,6,1從0到2的最短路徑長度為：25路徑為：0,6,3,5,2從0到3的最短路徑長度為：13路徑為：0,6,3從0到4的最短路徑長度為：11路徑為：0,4從0到5的最短路徑長度為：16路徑為：0,6,3,5從0到6的最短路徑長度為：7路徑為：0,6(7)答：不一定。如圖7.9所示的圖G從頂點(diǎn)0出發(fā)的最小生成樹如圖7.10所示，而從頂點(diǎn)0到頂點(diǎn)的2的最短路徑為0→2,而不是最小生成樹中的0→1→2。圖7.9一個(gè)帶權(quán)連通無向圖圖7.10圖的一棵最小生成樹(8)答：因?yàn)镈ijkstra算法是一種貪心算法，沒有回溯能力，在求出部分最短路徑后，假設(shè)后面的頂點(diǎn)的最短路徑更長，一旦出現(xiàn)權(quán)值為負(fù)的邊，就有可能修改前面的已求如圖7.11所示，求以頂點(diǎn)0為源點(diǎn)的最短路徑，先選取頂點(diǎn)1,表示從頂點(diǎn)0到頂點(diǎn)1的最短路徑長度為2,以后不再改變，然后選取頂點(diǎn)2,因?yàn)?lt;2,1>的權(quán)值為負(fù)，需要修改0→1的最短路徑為0→2→1,而Dijkstra算法沒有這種回溯修改路徑的能力，所以要求所有邊上的權(quán)值必須大于0。圖7.11一個(gè)帶權(quán)有向圖(9)答：這樣的有向圖的拓?fù)湫蛄惺俏ㄒ坏模攵葹?的頂點(diǎn)只有一個(gè)，每次輸出一個(gè)入度為0的頂點(diǎn)后，剩余的圖中都只有一個(gè)入度為0頂點(diǎn)。(10)答：①圖G的鄰接矩陣A如圖7.12所示。②有向帶權(quán)圖G如圖7.13所示。 ——一數(shù)據(jù)結(jié)構(gòu)簡明教程一③圖7.14中粗線所標(biāo)識(shí)的4個(gè)活動(dòng)組成圖G的關(guān)鍵路徑。圖7.13圖G圖7.14圖G中的關(guān)鍵路徑ve(A)=0ve(F)=ve(D)+3=6ve(B)=1ve(C)=MAX{ve(B)=3,ve(A)+2,ve(F)+3}=7ve(E)=MAX{ve(B)+1,ve(C)+2}=9ve(G)=MAX{ve(E)+1,ve(F)+5}=11。vl(G)=11vl(E)=vl(G)-1=10vl(C)=vl(E)-2=8vl(B)=MIN{vl(E)-1,vl(C)-3}=5vl(F)=MIN{vl(G)-5,vl(C)-1}=6vl(D)=vl(F)-3=3vl(A)=MIN{vl(B)-1,vl(C)-2,vl(D)-3}=0。則I(FC)=vl(C)-1=7,所以，事件C的最早開始時(shí)間為7,活動(dòng)FC的最遲開始時(shí)間為(1)解：用sum累計(jì)出度為0的頂點(diǎn)數(shù)(初始為0)。掃描鄰接矩陣g.edges,對(duì)于頂點(diǎn)i,累計(jì)第i行中非零元素個(gè)數(shù)即為出度，若為零則sum++。最后返回sum。對(duì)應(yīng)的算法如下：intZeroOutDs(MatGraphg)//計(jì)算圖G中出度為0的頂點(diǎn)數(shù)n++;//存在i到j(luò)的一條邊時(shí)if(n==0)sum++;}(2)解：對(duì)于頂點(diǎn)v,累計(jì)G->adjlist[v]為頭結(jié)點(diǎn)的單鏈表中結(jié)點(diǎn)個(gè)數(shù)即頂點(diǎn)v的出ArcNode*p;}//求頂點(diǎn)v的出度//掃描邊表結(jié)點(diǎn)//累計(jì)出邊的數(shù)目}intInDsv(AdjGraph*G,intv)//求頂點(diǎn)v的入度while(p!=NULL)//掃描邊表結(jié)點(diǎn){if(p->adjvex==v)n++;//累計(jì)頂點(diǎn)v的入邊的數(shù)目}}}———————數(shù)據(jù)結(jié)構(gòu)簡明教程一(4)解：若以G->adjlist[i]為頭結(jié)點(diǎn)的單鏈表中存在adjvext為j的結(jié)點(diǎn)，表示頂點(diǎn)iintArc(ALGraph*G,inti,intj)//判斷圖G中是否存在邊<i,j>if(p==NULL)return0;//不存在i到j(luò)的邊return1;//存在i到j(luò)的邊上述算法的時(shí)間復(fù)雜度為O(m),其中m表示鄰接表中單鏈表結(jié)點(diǎn)個(gè)數(shù)的最大值。采用鄰接矩陣存儲(chǔ)圖時(shí)實(shí)現(xiàn)該功能的時(shí)間復(fù)雜度為O(1)。G?、G?、…、G?調(diào)用DFS(G,i)算法。調(diào)用DFS的次數(shù)即為連通分量數(shù)。對(duì)應(yīng)的算法如//全局變量，所有元素置初值0//深度優(yōu)先遍歷算法//置已訪問標(biāo)記//p指向頂點(diǎn)v的第一個(gè)相鄰點(diǎn){}if(visited[p->adjvex]==0)//若p->adjvex頂點(diǎn)未訪問，遞歸訪問它//p指向頂點(diǎn)v的下一個(gè)相鄰點(diǎn)}//求圖G的連通分量//count累計(jì)連通分量個(gè)數(shù)//從頂點(diǎn)i出發(fā)深度優(yōu)先遍歷//調(diào)用DFS的次數(shù)即為連通分量數(shù)intqu[MAXVEX],front=0,rear=0;rear=(rear+1)%MAXVEX;while(front!=rear)rear=(rear+1)%MAXVEX;qu[rear]=p->adjvex;}}}}}}//全局變量，所有元素置初值0//廣度優(yōu)先遍歷算法//定義循環(huán)隊(duì)列并初始化隊(duì)頭隊(duì)尾//置已訪問標(biāo)記//v進(jìn)隊(duì)//若隊(duì)列不空時(shí)循環(huán)//出隊(duì)并賦給w//找頂點(diǎn)w的第一個(gè)相鄰點(diǎn)//若當(dāng)前鄰接頂點(diǎn)未被訪問//置該頂點(diǎn)已被訪問的標(biāo)志//該頂點(diǎn)進(jìn)隊(duì)//找頂點(diǎn)w的下一個(gè)相鄰點(diǎn)//求圖G的連通分量//count累計(jì)連通分量個(gè)數(shù)//從頂點(diǎn)i出發(fā)廣度優(yōu)先遍歷//調(diào)用BFS的次數(shù)即為連通分量數(shù)(7)解：先置全局?jǐn)?shù)組visited[]所有元素為0,然后從頂點(diǎn)i開始進(jìn)行廣度優(yōu)先遍歷。遍歷結(jié)束之后，若visited[j]=0,說明頂點(diǎn)i到頂點(diǎn)j沒有路徑，返回0;否則說明頂intqu[MAXVEX],front=0,rear=0;//全局變量，所有元素置初值0//廣度優(yōu)先遍歷算法//定義循環(huán)隊(duì)列并初始化隊(duì)頭隊(duì)尾rear=(rear+1)%MAXVEX;while(front!=rear) —數(shù)據(jù)結(jié)構(gòu)簡明教程—//置已訪問標(biāo)記//v進(jìn)隊(duì)//若隊(duì)列不空時(shí)循環(huán){front=(front+1)%MAXVEX;p=G->adjlist[w].firstarc;rear=(rear+1)%MAXVEX;}p=p->nextarc;}//出隊(duì)并賦給w//找頂點(diǎn)w的第一個(gè)相鄰點(diǎn)//若當(dāng)前鄰接頂點(diǎn)未被訪問//置該頂點(diǎn)已被訪問的標(biāo)志//該頂點(diǎn)進(jìn)隊(duì)//找頂點(diǎn)w的下一個(gè)相鄰點(diǎn){}BFSTrave(AdjGraph*G,intBFS(G,i);//求解算法//從頂點(diǎn)i出發(fā)廣度優(yōu)先遍歷走過的邊數(shù)(初始為0),先置全局?jǐn)?shù)組visited[]所有元素為0,然后從頂點(diǎn)v開始進(jìn)行深度優(yōu)先遍歷，先訪問頂點(diǎn)v,置visited[v]=1,查找頂點(diǎn)v的一個(gè)尚未訪問的相鄰點(diǎn)w,從頂點(diǎn)w出發(fā)繼續(xù)深度優(yōu)先遍歷，這里走了邊<v,w>,所voidDFSEdges1(AdjGraph*G,int//全局變量，所有元素置初值0v,int&sum)//深度優(yōu)先遍歷算法DFSEdges1(G,p->adjvex,sum);}p=p->nextarc;//置已訪問標(biāo)記//p指向頂點(diǎn)v的第一個(gè)相鄰點(diǎn)//若p->adjvex頂點(diǎn)未訪問，遞歸訪問它//走v到p->adjvex的一條邊//p指向頂點(diǎn)v的下一個(gè)相鄰點(diǎn)}intDFSEdges(AdjGraph*G,intv)DFSEdges1(G,v,sum);//求解算法8.練習(xí)題8參考答案(5)A。查找范圍為R[0..9]=(4,6,10,12,20,30,50,70,88,100),mid=(0+9)/2=4,58>R[4](20)。查找范圍為R[5..9],mid=(5+9)/2=7,58<R[7](70)。查找范圍為R[5..6],mid=(5+6)/2=5,58>R[5](30)。查找范圍為R[6..6],mid=(6+6)/2=6,(6)C。查找失敗最多關(guān)鍵字比較次數(shù)=1og?(n+1)]=「1og?231=5。(7)D。成功時(shí)最大比較次數(shù)為[log?(n+1)Hlog?101]-7。(8)D。在折半查找的判定樹中第i層的結(jié)點(diǎn)個(gè)數(shù)最多為2i-1。(13)C。該二叉排序樹的中序序列為abcdefgh,選項(xiàng)A、B和D都不能與該中序序列構(gòu)造出正確的二叉樹，只有選項(xiàng)C可以。(17)B。設(shè)N?表示高度為h的平衡二叉樹中含有的最少結(jié)點(diǎn)數(shù)，有N?=1,N?=2,N?=N?-1+Nr-2+1,由此，求出Ns=12。(18)C。A結(jié)點(diǎn)的左子樹是平衡的，所以調(diào)整選擇右孩子B,而右孩子B的平衡因子為1,說明其左子樹高，調(diào)整應(yīng)選擇B的左孩子C,這樣A、B、C三個(gè)結(jié)點(diǎn)構(gòu)成RL調(diào)(20)B。m=3,結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)1～2個(gè)，最少結(jié)點(diǎn)的情況是每個(gè)結(jié)點(diǎn)只有1個(gè)關(guān)鍵字，此時(shí)類似一棵高度為5的滿二叉樹，其結(jié)點(diǎn)個(gè)數(shù)=2h-1=31。(24)D。這k個(gè)同義詞R?~R?在哈希表是依次相鄰排列的，存入R;需要進(jìn)行的探測(cè)次數(shù)為i,總的探測(cè)次數(shù)=1+2+…+k=k(k+1)/2。 -—數(shù)據(jù)結(jié)構(gòu)簡明教程—2.填空題(4)①索引表②主數(shù)據(jù)表。(10)①存取元素時(shí)發(fā)生沖突的可能性就越大②存取元素時(shí)發(fā)生沖突的可能性就越小3.簡答題①順序查找法：表中元素可以任意次序存放。適合順序表和鏈表的存儲(chǔ)結(jié)構(gòu)。②折半查找法：表中元素必須按關(guān)鍵字有序減排列，且更適合順序表存儲(chǔ)結(jié)構(gòu)。③分塊查找法：表中元素每塊內(nèi)的元素可以任意次序存放，但塊與塊之間必須以關(guān)鍵字的大小遞增(或遞減)排列，即前一塊內(nèi)所有元素的關(guān)鍵字都不能大(或小)于后一①順序查找法：查找成功的平均查找長度為(n+1)/2。②折半查找法：查找成功的平均查找長度為log?(n+1)-1。(2)答：折半查找不適合鏈表結(jié)構(gòu)的序列。雖然有序單排列的，但難以確定查找的區(qū)間(對(duì)應(yīng)的時(shí)間為O(n)),故不適合進(jìn)行折半查找。在一般情況下折半查找的效率更高(所需要的關(guān)鍵字比較次數(shù)更少),但在特殊情況(3)答：①按輸入順序構(gòu)造的二叉排序樹如圖8.2所示。在等概率情況下查找成功②構(gòu)造的一棵平衡二叉樹如圖8.3所示。在等概率情況下查找成功的平均查找長度：(5)答：構(gòu)造的二叉排序樹如圖8.4所示。為了刪除結(jié)點(diǎn)72,在其左子樹中找到最大結(jié)點(diǎn)54(只有一個(gè)結(jié)點(diǎn)),用其代替結(jié)點(diǎn)72。刪除之后的二叉排序樹如圖8.5所示。圖8.4二叉排序樹圖8.5刪除72后的二叉排序樹(d)插入10(b)插入6(b)插入6(7)答：依題意，m=19,線性探測(cè)法計(jì)算下一地址計(jì)算公式為：d=(d-+1)%mj=1,2,…構(gòu)造哈希表ha的過程如下：h(19)=19%13=6h(01)=01%13=1h(23)=23%13=10h(14)=14%13=1do=1,d?=(1+1)%19=2h(55)=55%13=3h(20)=20%13=7h(84)=84%13=6do=6,d?=(6+1)%19=7h(27)=27%13=1do=1,d?=(1+1)%19=2h(68)=68%13=3do=3,d=(3+1)%19=4h(11)=11%13=11h(10)=10%13=10do=10,d?=(10+1)%19=11do=12,d?=(12+1)%19=13將19存放在ha[6]中將01存放在ha[1]中將23存放在ha[10]中沖突將14存放在ha[2]中將55存放在ha[3]中將20存放在ha[7]中沖突將84存放在ha[8]中沖突仍沖突仍沖突將27存放在ha[4]中沖突仍沖突將68存放在ha[5]中將11存放在ha[11]中沖突仍沖突將10存放在ha[12]中沖突將77存放在ha[13]中因此，構(gòu)建的哈希表ha如表8.1所示。表8.1哈希表ha下標(biāo)012345678911k11探測(cè)次數(shù)121431131132ASL成功=(1+2+1+4+3+1+1+3+1+1+3+2)/12=1.92ASL不成功=(1+9+8+7+6+5+4+3+2+1+5+4+3+2+1+1+1+1+1)/19=3.42h(87)=87%13=9h(25)=25%13=12h(132)=132%13=2h(95)=95%13=4h(187)=187%13=5h(123)=123%13=6采用拉鏈法處理沖突的哈希表如圖8.7所示。成功查找的平均查找長度：ASL成功=(1×10+2×3)/10=1.6ASL不成功=(1×7+2×3)/13=1AA0123456789AAA圖8.7采用拉鏈法處理沖突的哈希表4.算法設(shè)計(jì)題(1)解：通過一趟掃描并比較，可以找出最大元素max和最小元素min。對(duì)應(yīng)的算voidMaxMin(intA[],intn,int&min,int&max) if(R[i]<min)min=R[i];max=R[i];(2)解：對(duì)應(yīng)的遞歸算法如下：{}return(-1);if(k==R[mid].key)return(BinSearchl(R,k,mid+1,high));//return(BinSearchl(R,k,low,mid-1));//在左子樹中遞歸查找在右子樹中遞歸查找(3)解：對(duì)應(yīng)的兩個(gè)算法如下：voidFindk1(SqTypeR1[],intn,KeyTypek)//無序順序表R1的查找while(i<n)}}voidFindk2(SqTypeR2[],intn,KeyTypek)//遞增有序順序表R2的查找while(i<n)printf("%d",i);break;}無序順序表R1中的查找是從頭到尾進(jìn)行的。遞增有序順序表R2中的查找是從頭開}}voidOutput(BSTNode*bt,KeyTypek)if(bt->key>=k)Output(bt->lchild,k);}intlevel(BSTNode*bt,KeyTypek)if(bt!=NULL)while(bt->data!=k)bt=bt->1child;bt=bt->rchild;h++;}//在左子樹中查找//在右子樹中查找//層數(shù)增19.練習(xí)題9參考答案(3)2。在插入60時(shí)，有序區(qū)為(4,12,23,48,96),依次與96、48進(jìn)行比較，比較次數(shù)為2。(6)①直接插入②簡單選擇排序(7)快速排序(8)①堆排序②快速排序(11)(16,12,15,10,5,7,2,8)。堆中刪除操作總是刪除根結(jié)點(diǎn)。(12)某個(gè)葉子結(jié)點(diǎn)(13)①k?②遞增(14)①生成初始?xì)w并段②對(duì)初始?xì)w并段采用多路歸并方法歸并為一個(gè)有序段。排序前：4,5,1,2,8,6,7,3,10,9排序后：1,2,3,4,5,6,7,8,9,10圖9.1希爾排序各趟排序結(jié)果(2)答：該數(shù)組一定構(gòu)成一個(gè)堆，遞增有序數(shù)組構(gòu)成一個(gè)小根堆，遞減有序數(shù)組構(gòu)以遞增有序數(shù)組為例，假設(shè)數(shù)組元素為k?、k?、…、k,是遞增有序的，從中看出下標(biāo)越大的元素值也越大，對(duì)于任一元素k,有k<k?;,k;<k?+i(i<n/2),這正好滿足小根堆的特性，所以構(gòu)成一個(gè)小根堆。(3)答：采用冒泡排序法排序的各趟的結(jié)果如下：(4)答：采用快速排序法排序的各趟的結(jié)果如下：(5)答：采用直接選擇法排序的各趟的結(jié)果如下：(6)答：采用堆排序法排序的各趟的結(jié)果如下：——————