《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程》習(xí)題及解答

《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程》習(xí)題解答

（新）1章習(xí)題解答一、填空意義，只是反映數(shù)據(jù)元素某一方面的屬性。數(shù)據(jù)是以數(shù)據(jù)元素為單位存放在內(nèi)存的，分配給它的內(nèi)存區(qū)域稱為存儲結(jié)點。每個數(shù)據(jù)元素都具有完整、確定的實際意義，是數(shù)據(jù)加工處理的對象。如果兩個數(shù)據(jù)結(jié)點之間有著邏輯上的某種關(guān)系，那么就稱這兩個結(jié)點是鄰接的。在一個存儲結(jié)點里，除了要有數(shù)據(jù)本身的內(nèi)容外，還要有體現(xiàn)數(shù)據(jù)間鄰接關(guān)系的內(nèi)容。二、選擇在常見的數(shù)據(jù)處理中，B 是最基本的處理。A．刪除 B．查找 C．讀取 D．插2．下面給出的名稱中，A不是數(shù)據(jù)元素的同義詞。A．字段 B．結(jié)點 C．頂點 D．記錄D是圖狀關(guān)系的特例。只有線性關(guān)系 B．只有樹型關(guān)系C．線性關(guān)系和樹型關(guān)系都不 D．線性關(guān)系和樹型關(guān)系D據(jù)間的邏輯關(guān)系。只能有1個 B．只能有2個 C．只能有3個 D．可以有多5．本書將采用C來描述算法。A．自然語言 B．流程圖（即框圖） C．類C語言 D．C語言6．有下面的算法段：for(i=0;i<n;i++)k++;其時間復(fù)雜度為B。2A．O(1) B．O(n) C．O(logn) D．O(n2)2-1-習(xí)題解答三、問答么樣的鄰接關(guān)系，為什么？答：是一種線性關(guān)系，因為這些姓氏之間符合關(guān)系的“有頭有尾，順序排列”的特點。什么是數(shù)據(jù)結(jié)點？什么是存儲結(jié)點？它們間有什么關(guān)系？答：數(shù)據(jù)結(jié)點即是數(shù)據(jù)集合中的一個數(shù)據(jù)元素，存儲結(jié)點是存放數(shù)據(jù)結(jié)點的內(nèi)存單位。在存儲結(jié)點里，不僅要存放數(shù)據(jù)結(jié)點的內(nèi)容，還要（顯式或隱式地）存放數(shù)據(jù)結(jié)點間的邏輯關(guān)系。為什么說鏈式存儲既提高了存儲的利用率，又降低了存儲的利用率？列舉幾個數(shù)據(jù)之間具有樹型結(jié)構(gòu)的實際例子。答：學(xué)校各級管理之間，是一種分支層次結(jié)構(gòu)；一本書的書目，是一種分支層次結(jié)構(gòu)。判斷如下除法過程是否是一個算法，為什么：開始；給變量m5，給變量n0；m=m/n；輸出結(jié)束。0不能為除數(shù)，本題第步不具有有效性，所以它不是一個算法。但如果n的初值不為0，則是一個正確的算法。四、應(yīng)用用類C語言中的do-while、2、9、10答：算法編寫如下。voidnum(){i=1;do{printf(“i=%d\n”,i);i=i+1;}while(i<=10);}用類C語言中的if-else語句，編寫算法，描述當輸入的數(shù)據(jù)大于等于00答：算法編寫如下。voidjudge(){scanf(“%d\n”,&x);if(x>=0)-2-習(xí)題解答printf(“輸入的是正數(shù)”);elseprintf(“輸入的是負數(shù)”);}1 #”和“#1 for(i=0;i<n;i++)for(j=0;j<n;j++){#1y=1;for(k=0;k<n;k++)#2y=y+1;}1 答：標有記號“#”的基本操作的執(zhí)行次數(shù)是：n2；標有記號“#”的基本操作的執(zhí)行次數(shù)是：n31 3個算法段的時間復(fù)雜度：（1）x++；（2）for(j=1;j<n;j++)x++;（3）for(j=1;j<=n;j++){printf(“j=%”,j);for(k=j;k<=n;k++)x++;}（）的時間復(fù)雜度為(1；O(n)；printf”執(zhí)行次數(shù)的數(shù)量級為nx++”執(zhí)行次數(shù)是：n+(n-1)+(n-2)+……+2+1n(n+1)/2其數(shù)量級為O(n2)，因此整個算法段的時間復(fù)雜度應(yīng)該是O(n2)。2章習(xí)題解答一、填空n稱為線性表的長度。以順序存儲結(jié)構(gòu)實現(xiàn)的線性表，被稱為順序表。在一個雙鏈表中，已經(jīng)由指針ptr指向需要刪除的存儲結(jié)點，則刪除該結(jié)點所要行的兩條操作是①ptr->Prior->Next=ptr->Next; ②ptr->Next->Prior=ptr->Prior; 。設(shè)tailtail->Next->Next。在一個不帶表頭結(jié)點的非空單鏈表中，若要在指針qtr所指結(jié)點的后面插入一個值-3-習(xí)題解答為x的結(jié)點，則需要執(zhí)行下列操作：ptr=malloc(size);ptr->Data=x;ptr->Next=qtr->Next;qtr->Next=ptr;順序表Sq=(a

w個存儲單元。1 2 3 n若m為元素a1的起始地址，那么元素an的存儲地址是m+(n-1)*w。二、選擇下面，對非空線性表特點的論述，C是正確的。A．所有結(jié)點有且只有一個直接前驅(qū)B．所有結(jié)點有且只有一個直接后繼C．每個D．結(jié)點1對多的鄰接關(guān)系來維系其邏輯關(guān)系的一般單鏈表Lk_hA。A．Lk_h==NULL B．Lk_h->Next==C．Lk_h->Next==Lk_h D．Lk_h!=NULLB帶表頭結(jié)點的單鏈表Lk_h為空的判定條件是B。A．Lk_h==NULL B．Lk_h->Next==C．Lk_h->Next==Lk_h D．BA．n B．n/2 C．n+1 D．(n+1)/2在一個單鏈表中，已知qtrptr所指結(jié)點的直接前驅(qū)?，F(xiàn)要在qtrptr所指結(jié)點之間插入一個rtrC。C．qtr->Next=rtr;rtr->Next=ptr;A．rtr->Next=ptr->Next; ptr->Next=B．C．qtr->Next=rtr;rtr->Next=ptr;D．ptr->Next=rtr; rtr->Next=qtr->Next;在一個單鏈表中，若現(xiàn)在要刪除ptrA。A．ptr->Next=ptr->Next->Next;B．ptr=ptr->Next; ptr->Next=ptr->Next->Next;C．ptr=ptr->Next->Next;D．ptr->Nextptr;ni個元素（1≤i≤n）B個元素。A．n-i B．n-i+1 C．n-i-1 D．ini個元素時，需要往前移動A個元素。A．n-i B．n-i+1 C．n-i-1 D．i99．設(shè)tail是指向一個非空帶表頭結(jié)點的循環(huán)單鏈表的尾指針。那么，刪除鏈表起始結(jié)點的操作應(yīng)該是D。A．ptr=tail; B．tail=tail->Next;-4-習(xí)題解答tail=tail->Next; free(tail)free(ptr);C．tail=tail->Next->Next; D．ptr=tail->Next->Next;Free(tail); tail->Next->Next=ptr->Next;Free(ptr); free(ptr);10．在單鏈表中，如果指針ptr所指結(jié)點不是鏈表的尾結(jié)點，那么在ptr之后插入由指針qtr所指結(jié)點的操作應(yīng)該是B。A．qtr->Next=ptr; B．qtr->Next=ptr->Nextptr->Next=qtr; ptr->Next=qtr;C．qtr->Next=ptr->Next; D．ptr->Next=qtrptr=qtr; qtr->Next=ptr;三、問答試問，如下的線性表：L=(29，25，21，17，13，11，7，5，3，1)是有序線性表還是無序線性表？答：L是一個有序線性表。線性表Li個存儲結(jié)點ai的起始地址LOC（ai）可以通過下面的公式計算得到：LOC（ai）=LOC（ai）+k-1其中k表示存儲結(jié)點的長度。這個公式對嗎？為什么？-1答：這個公式是對的，因為第i個存儲結(jié)點ai的起始地址LOi-1個存儲結(jié)點ai-1的起始地址LOC（ai）k得到。-1試說明創(chuàng)建順序表算法Create_Sq()中，Sq_maxSq_num的不同之處。4．如何判斷一個順序表是否為空？答：Sq_max順序表創(chuàng)建后，Sq_max代表的是順序表內(nèi)當前擁有的數(shù)4．如何判斷一個順序表是否為空？答：只需判定Sq_num的當前值是多少，如果Sq_num0，則表示順序表Sq則表示該順序表里有數(shù)據(jù)元素存在。2-3里，操作“Sq_num=Sq_num-Sq_num刪除了一個元素，Sq_num必須減1，這樣才能正確反映出刪除后表中元素的個數(shù)。所以，沒有這個操作是不行的。在算法2-9述，能夠保證插入后最后一個結(jié)點的Next答：能夠。因為原來ptr->NextΛ1qtr->Next=ptr->Next;后，就是把插入結(jié)點的NextΛ在一個單鏈表中，為了刪除指針ptr懂并加以理解。試問，編寫者能夠達到目的嗎？其思想是什么？x=ptr->Data;qtr=ptr->Next;ptr->Data=ptr->Next->Data;-5-習(xí)題解答ptr->Next=ptr->Next->Next;free(qtr);ptr所指結(jié)點的目的。編寫者的思想是不去直接刪除ptr所指的ptr直接后繼的Data域內(nèi)容寫入ptr所指結(jié)點的Data的設(shè)計是有其可取之處的。在一個單鏈表中，為了在指針ptr所指結(jié)點之前插入一個由指針qtr所指的結(jié)點，有人編寫了下面的操作序列，其中temp者能夠達到目的嗎？其思想是什么？qtr->Next=ptr->Next;ptr->Next=qtr;temp=ptr->Data;p->Data=qtr->Dataqtr->Data=temp;ptrqtr所指結(jié)點的目的。編寫者的思想是考慮到在單鏈表中得到一個結(jié)點的前驅(qū)信息較為困難，因此在這里先把qtr插入到ptr所指結(jié)點的后面，暫時成為它的直接后繼。然后通過臨時工作單元temp，將qtr所指結(jié)點的Data域內(nèi)容進行交換，從而達到插入的目的。Next外，它們的Prior域還都是空的。有人編寫了下面的算法，試圖完成Prior域的鏈接：Com_Cd(Cd_h){ptr=Cd_h->Next;qtr=Cd_h;while(ptr!=Cd_h){ptr->Prior=qtr;qtr=ptr;ptr=ptr->Next;}Cd_h->Prior=qtr;}讀懂并理解它，解釋為什么能夠完成各結(jié)點的Prior域的鏈接？答：算法中用兩個指針ptr和qtr配合，從頭到尾掃描這個循環(huán)雙鏈表，以達到讓每個結(jié)點的Prior域指向其直接前驅(qū)的目的。四、應(yīng)用設(shè)計一個計算表頭指針為Lk_h的單鏈表長度（即結(jié)點個數(shù)）答：算法設(shè)計如下：Length_Lk(Lk_h){n=0;ptr=Lk_h; /*ptr指向起始結(jié)點while(ptr!=NULL)-6-習(xí)題解答{ptr=ptr->Next;n=n+1;}

/*n為結(jié)點計數(shù)單元*/return(n);}用總是在表的頭部插入整數(shù)結(jié)點的方法建立一個單鏈表，當輸入為0結(jié)束。答：算法設(shè)計如下：Clink(){Lk_h=NULL;scanf(%d,while(x!=“0”){ptr=malloc(size);ptr->Data=x;ptr->Next=Lk_h;Lk_h=ptr;scanf(%d,&x);}returnLk_h;}一個不帶表頭結(jié)點的循環(huán)雙鏈表CkCk_hptr入一個rtr2-214個操作步驟：①rtr->Next=ptr;②rtr->Prior=ptr->Prior;③ptr->Prior->Next=rtr;④ptr->Prior=rtr;答：4個操作步驟的具體功能體現(xiàn)如下圖所示。試設(shè)計一個算法copy(Ck_h1,，將一個帶表頭結(jié)點的、以Ck_h1為表頭指針的單鏈表Ck1Ck_h2為表頭指針的單鏈表Ck2答：算法具體如下。Copy(Ck_h1,Ck_h2){ptr=Ck_h1->Next;-7-習(xí)題解答qtr=Ck_h2;while(ptr!=NULL){rtr=malloc(size);rtr->Data=ptr->Data;qtr->Next=rtr;qtr=rtr;ptr=ptr->Next;}qtr->Next=NULL;}、且值小于max（假定表中存在這樣的元素）答：所需算法編寫如下。Del_Sq(Lk_h,nim,max){ptr=Lk_h->Next; /*ptr指向鏈表的起始結(jié)點*/while((ptr!=NULL)&&(ptr->Data<=min))/*跳過所有值<=min的結(jié)點*/{qtr=ptr;ptr=ptr->Next;}while((ptr!=NULL)&&(ptr->Data<max))p=p->Next;

/*若結(jié)點值<max，則去除*/qtr->Next=ptr;}

/*qtr指出第1個大于max的結(jié)點位置，完成鏈接*/、且值小于max的數(shù)據(jù)元素。ptr結(jié)點的直接前驅(qū)。Del_Lk(Lk_h,min,max){ptr=Lk_h->Next;while(ptr!=NULL){

/*ptr指向單鏈表的起始結(jié)點*//*掃視直到鏈尾結(jié)點*/if((ptr->Data<=min)||(ptr->Data>=max){

/*不滿足刪除條件*/qtr=ptr;ptr=ptr->Next;}

/*qtrptr*/else{

/*ptrptr*/qtr->Next=ptr->Next;free(ptr);-8-習(xí)題解答ptr=qtr->Next;}}}一個單鏈表Lk的表頭指針為Lk_h，不同結(jié)點的Data法，功能是計算出Data域值為x的結(jié)點的個數(shù)。答：算法應(yīng)該遍歷鏈表的每一個結(jié)點，遇到一個結(jié)點的Dataxn1。最后返回計數(shù)器。Count_Lk(Lk_h){n=0;ptr=Lk_h;while(ptr!=NULL){if(ptr->Data==x)n=n+1;ptr=ptr->Next}return(n);}3章習(xí)題解答一、填空如果在順序棧滿時仍打算進行進棧操作，就稱為發(fā)生了“上溢”出錯。如果在順序?？諘r仍打算進行出棧操作，就稱為發(fā)生了“下溢”出錯。nn-1個數(shù)據(jù)元素。如果操作順序是先讓字母ABC進棧，做兩次出棧；再讓字母、、F進棧，做一次出棧；最后讓字母GDA。(a+b)-(c/(d+e))ab+cde+/-。函數(shù)的遞歸調(diào)用有兩種形式：如果一個函數(shù)是直接調(diào)用自己，就稱其為直接遞歸、23、、5，想得到、35、1的輸出順序。那pushpop的操作序列應(yīng)該是pushpushpushpushpoppushpoppop。設(shè)鏈棧的棧頂指針為Ls_topLs_top!=NULL。二、選擇一個棧的元素進棧序列是ab、、de，那么下面的C不能做為一個出棧序列。、、cb、a B．d、、c、、aC．d、、e、、b D．a(chǎn)、、cd、-9-習(xí)題解答判定一個順序隊列Qs（最多有n個元素）為空的條件是C。A．Qs_rear-Qs_front==n*size B．Qs_rear-Qs_front+1==C．Qs_front==Qs_rear D．Qs_front==Qs_rear+size判定一個順序隊列Qs（最多有n個元素）真滿的條件是A。A．Qs_rear-Qs_front==n*size B．Qs_rear-Qs_front+1==C．Qs_front==Qs_rear D．Qs_front==Qs_rear+size在一個鏈式隊列LqLq_rear分別為隊首、隊尾指針?，F(xiàn)在由指針ptr所指結(jié)點要進隊，則插入操作應(yīng)該是B。A．Lq_front->Next=ptr; Lq_front=B．Lq_rear->Next=ptr; Lq_rear=ptr;C．ptr->Next=Lq_rear; Lq_rear=ptr;D．ptr->Next=Lq_front; Lq_front=鏈棧與順序棧相比，一個較為明顯的優(yōu)點是D。A．通常不會出現(xiàn)棧空的情形 B．插入操作更加便利C．刪除操作更加便利 D．通常不會出現(xiàn)棧滿的情向鏈棧插入一個結(jié)點時，操作順序應(yīng)該是C。A．先修改棧頂指針，再插入結(jié)點 B．無須修改棧頂指針C．先插入結(jié)點，再修改棧頂指針 D．誰先誰后沒有關(guān)從鏈棧中刪除一個結(jié)點時，操作順序應(yīng)該是AA．先保存被刪結(jié)點的值，再修改棧頂指針B．先修改棧頂指針，再保存被刪結(jié)點的值C．無須修改棧頂指針的值D．誰先誰后沒有關(guān)系一個循環(huán)隊列的最大容量為m+1，frontD。A．Cq_front=(Cq_front+1)%m B．Cq_front=(Cq_front+1)%(m+1)C．Cq_rear=(Cq_rear+1)%m D．Cq_rear=(Cq_rear+1)%(m+1)在一個循環(huán)順序隊列里，隊首指針Cq_front總是指向BA．隊首元素 B．隊首元素的前一個隊位C．任意位置 D．隊首元素的后一個隊位若一個棧的進棧序列是44時，進、出棧操作的順序應(yīng)該是A（表示出棧操作）IOOOIO B．IOIOIOIO C．IIOOIOIO D．IOIIIOOO三、問答11．若元素進棧的序列是1、2、3、…、n，有一個出棧序列的第1個元素是n。那么，這個出棧序列的第i個元素是什么？答：由于棧具有“先進后出”的特性，因此只有將1、23、…、n依次都進棧后，出棧序列的第1個元素才能是n。所以，在這個出棧序列里，第個i元素應(yīng)該是n-i+1。設(shè)元素進棧的次序是a，b，c，d，e。試問，在下面所列的6可以是這個棧的出棧序列？A．c，e，a，b，d B．c，b，a，d，e D．a(chǎn)，c，b，e，d E．a(chǎn)，b，c，d，e F．e，a，b，c，d答：對A進行分析。由于是c1個出棧，因此b必須先于a-10-習(xí)題解答卻先于b出棧，故A不能是該棧的出棧序列。C進行分析。由于是d1個出棧，因此、bc三者出棧的順序必須是、b、卻先于b出棧，故C不能是該棧的出棧序列。F進行分析。由于是e1個出棧，因此、b、d四者出棧的順序必須是dc、b、a。但所給序列里，它們的出棧順序全亂了，故F不能是該棧的出棧序列。因此，所列的6種元素序列里，只有B、D、E可以是這個棧的出棧序列。有一個順序棧Ss，其棧頂指針為Ss_top，棧底指針為Ss_bottom算法，其中的兩條prinf算法中的Push_Ss(Ss_top,ch)表示將ch里的元素進棧，Pop_Ss(Ss_top,表示將棧頂元素出棧，存入ch中)print(){for(ch=‘A’;ch<=‘A’+12;ch++){Push_Ss(Ss_top,ch);printf(“%c”,ch);}while(Ss_top!=Ss_bottom){Pop_Ss(Ss_top,ch);printf(“%c”,ch);}}1條printf13個英文大寫字母ABCDEFGHIJKLM2printf出的是前面輸出的倒置，即MLKJIHGFEDCBA。1 2 3 4 5 4 3 2 6 5 6a、aa、a、aa棧順序是a、a、a、aa、a，那么應(yīng)該如何安排pushpop1 2 3 4 5 4 3 2 6 5 答：所需的push和pop操作序列如下：push，push，push，push，pop，pop，pop，push，push，pop，pop，popa/(b/(c/(d/e)))abcde////。這一轉(zhuǎn)化結(jié)果對嗎？答：轉(zhuǎn)化結(jié)果是對的。試述棧與隊列各自具有什么樣的邏輯特點？它們之間又有什么共同點？（即往棧里插入元素）的順序與數(shù)據(jù)元素離開棧（即從棧里刪除元素）堆棧的邏輯特點是后進先出LIF，或先進后出FIL。而對隊列來說，插入在一端進行，刪除在另一端進行，這就使得數(shù)據(jù)元素到達隊列（即往隊列里插入元素）元素離開隊列（即從隊列里刪除元素）先出FIF）或后進后出LIL。它們之間的共同之處是插入和刪除只能在表的端點處進行（要知道，對于線性表，可以在表的任何位置處插入和刪除。有一個順序隊列，最大容量為5。初始時有Qs_front=Qs_rear=時隊列及其首、尾指針的變化情況。若不能進隊時就停止，并簡述原因。（1）d、、b進隊 （2）d、e出隊 （3）i、j進隊（4）b出隊 （5）n、、p進隊答：隊列及其首、尾指針的變化情況如下圖所示。-11-習(xí)題解答在做5）時，由于隊滿（假溢出，故操作停止。有一個遞歸函數(shù)Write(x){if(x!=0){Write(x-1);for(j=1;j<=x;j++)printf(“%3d”,x);printf(“/n”);}}試問，Write(5)的輸出結(jié)果是什么？答：輸出結(jié)果為：12 23 3 34 4 4 45 5 5 5 5四、應(yīng)用編寫一個判順序棧空的算法。要求是如果?？?，返回1，否則返回答：算法設(shè)計如下：Empty_Ss(Ss,Ss_top){if(Ss_top==0) /*return(1);else /*棧不空*/return(0);}編寫一個算法，它能夠輸出順序隊列Qs答：算法編寫如下：Print_Qs(Qs_front,Qs_rear){if(Qs_front==Qs_rear) /*printf(“queueisempty!”);-12-習(xí)題解答else{

/*隊列非空！*/qtr=Qs_front;while(qtr<=Qs_rear){printf(“%d”,*qtr);qtr++;}}}編寫一個算法，它能夠取得鏈式隊列首元素的值。答：取得鏈式隊列首元素的值，只有在隊列非空的前途下才有意義。算法編寫如下。Getf_Lq(Lq_front,Lq_rear){if(Lq_front==Lq_rear)printf(“Thelinkedqueueiselse{

/*隊列空！*//*隊列非空！*/ptr=Lq_front->Next;x=ptr->Data;return(x);}}5424個人多少歲，回答說比第32歲；問第3個人多少歲，回答說比第22212110歲。試給出該遞歸的公式、結(jié)束條件，并編寫出相應(yīng)的遞歸算法。答：遞歸公式為：age(n)=age(n-1)+2 2<=n<=5遞歸的結(jié)束條件是：age(1)=10相應(yīng)算法為：Age(n){if(n==1)return(10);else{x=age(n-1)+2;return(x);}}將中綴表達式轉(zhuǎn)化為后綴表達式的方法類似于中綴表達式求值。具體地，要開辟一個運算符棧op和一個數(shù)組st-13-習(xí)題解答st；遇到運算符時就與op棧頂元素比較，高則進棧，不高則讓棧頂元素出棧，存入st，然后該運算符再次去與新的op棧頂元素比較。最后，在數(shù)組st試用這種方法，用圖示將中綴表達式5+8*3-2轉(zhuǎn)化成為相應(yīng)的后綴表達式。答：相應(yīng)的后綴表達式是583*+2-，其圖示如下。ob，當從左往右掃描后綴表達式時，每遇到操作數(shù)就讓其進入ob棧，每遇到運算符就從obobob棧的棧頂值就是最終結(jié)果。試用圖示計算后綴表達式583*+2-的值。答：計算結(jié)果為27，其圖示如下。4章習(xí)題解答一、填空一個概念。字符串中任意多個連續(xù)字符所組成的子序列，被稱作是這個串的“子串符串本身則稱為“主串我們說兩個字符串相等，在計算機內(nèi)部實際上是通過對相應(yīng)位置上字符ASCII碼-14-習(xí)題解答的比較而得到的結(jié)論。設(shè)有三個串：s1=“Good”，s2=“Ф”，s3=“bye!”。則s1、、s3設(shè)有三個串：s1=“Good”，s2=“Ф”，s3=“bye!”。則s1、、s3連接后的結(jié)果串應(yīng)該是“Goodbye!”。（n>1個具有相同類型的數(shù)據(jù)的有序集合。所謂“特殊矩陣ij=aji在一個n階方陣A中若所有元素都有性質(zhì)就稱其為對稱矩ij=aji陣。二、選擇設(shè)有兩個串s1。求s2s1B。A．連接 B．模式匹配 C．求子串 D．求串2．有串那么它的長度是B。A．0 B．1 C．2 D．33．設(shè)有串s1=“ABCDEFG”s2=“PQRST”。已知：算法con(x,x和y的連接串；subs(s,i,返回串s的第i個字符開始往后j返回串s的長度。那么，con(subs(s1,2,len(s2)),subs(s1,len(s2),D。A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF8階的對稱矩陣Aa1111，每個元素占一個地址空間。試問元素a85的地址是A。A．33 B．30 C．13 D．23m*mC。C．m*(m+1)/2A．m*(m-1)/2B．m*m/2 D．C．m*(m+1)/2二維數(shù)組M的每個元素含4個字符（每個字符占用一個存儲單元，行下標i從15j16。那么按行順序存儲時元素M[4][6]MB的起始地址相同。A．M[3][5] B．M[4][5] C．M[4][6] D．M[5][5]M3i18j110SA的存儲區(qū)開始存放AA[8][5]C。A．SA+141 B．SA+180 C．SA+222 D．SA+22588．設(shè)有一個5階上三角矩陣A，將其元素按列優(yōu)先順序存放在一維數(shù)組B中。已知每2100。那么A[3][4]的地址是A。A．116 B．118 C．120 D．122（分析：把一個上三角矩陣按列優(yōu)先順序存放在一個一維數(shù)組B中，元素的順序是：a11a12a22a13……A[3,4]的地址=100+a34前面的元素個數(shù)*2=100+（前3列的個數(shù)+本列a34前面的個數(shù)）*2=100+（1+2+3）+2）*2=116）-15-習(xí)題解答三、問答為什么可以把二維數(shù)組視為是一種線性結(jié)構(gòu)？視為是線性表的一種推廣（因為一維數(shù)組即是線性表，因此可以說它的數(shù)據(jù)元素間的邏輯關(guān)系呈現(xiàn)出的是一種線性結(jié)構(gòu)。55圖4-3（）所示為一個特殊矩陣A ，這種形式的矩陣被稱作是“帶狀矩陣，為它的非零元素都分布在以主對角線為中心的一個帶狀區(qū)域里，其他位置上的元素全部為0?？梢砸孕袃?yōu)先的方式，將其壓縮存儲到一個一維數(shù)組里，如圖4-34（b）所示。試找元素下標i、j與存儲序號k間的對應(yīng)關(guān)系。55圖4-34 帶狀矩陣答：壓縮存儲元素下標i、j與存儲序號k間的對應(yīng)關(guān)系是：k=2*i+j–24-35所示。試問，它對應(yīng)的三元組表是什么？圖4-35 稀疏矩陣示例答：它所對應(yīng)的三元組表如下。四、應(yīng)用-16-習(xí)題解答4-1改為用while4-1可以是如下所示。Concat_St(St1,St2){charSt3[maxsize];St3_len=0;

/*創(chuàng)建一個新的順序串為空*/if(St1_len+St2_len>maxsize+1){

/*新串放不下兩個串*/printf(“兩串長度之和超長！”);return(NULL);}else{i=1；while(i<=St1_len){St3[i]=St1[i];i++;}j=1;while(j<=St2_len){St3[j+St1_len]=St2[j];j++;}St3_Len=St1_len+St2_len;St3[St3_len+1]=“\0”;return(St3);}}算法4-24-2。答：按照這樣的設(shè)計，算法4-2的描述如下。Equal_St(St1,St2){i=1;while(St1[i]!={

/*兩串進行比較*/if(St1[i]==St2[i]) /*相等，繼續(xù)比較i++;elseblack;}

/*不等，強制退出*/-17-習(xí)題解答if(St1[i]!=St2[i])return(0);else{

/*比較是由于相應(yīng)位置上的字符不同而結(jié)束*/if(St1[i]\0||St2[i]\0”)/*比較是由于長度不同而結(jié)束*/return(0);elsereturn(1);}}算法：Trans_St(St，ch1，ch2){i=1；While(St[i]！="\0"){if(St[i]==ch1)St[i]==ch2；i++；}}是通過while循環(huán)來實現(xiàn)將順序串St中所有的字符ch1改為字符ch2循環(huán)來實現(xiàn)相同的功能。答：用for循環(huán)改寫的算法如下。Trans_St(St,ch1,ch2){for(i=1;i<=St_len;i++)if(St[i]==ch1)St[i]=ch2;}編寫一個算法，將順序串St文字母A~Z對應(yīng)的ASCII65~90，小寫英文字母a~z對應(yīng)的ASCII97~122寫字母的ASCII32，就是對應(yīng)小寫字母的ASCII碼)答：算法編寫如下。Catosm_St(St){for(i=1;i<=St_len;i++)if((A<=St[i])&&(St[i]<=Z))St[i]=St[i]+32;}ij個字符刪除（i+jj個位置，完成刪除的功能）答：算法編寫如下。-18-習(xí)題解答Moveij(St,i,j){if(i+j<=St_len){for(k=i+j;k<=St_len;k++) /*i+jj個位置St[k-j]=St[k];St_len=St_len-j;St[St_len]=“\0”;}

/*St的長度*//*安放新的串結(jié)束符*/elseprintf(“參數(shù)不合理，無法進行刪除！”);}在算法4-12ptr->Next=NULL;把由指針ptr指向的最后一個要釋放空間的結(jié)點的Next域設(shè)置為NULL，然后通過while循環(huán)完成釋放。其實，由于知道要釋放空間的結(jié)點共有mform來控制釋放空間的結(jié)點個數(shù)。請試著按照這一思路改寫那一小段算法。答：改寫一小段算法如下。for(j=1;j<=m;j++){ptr=rtr;rtr=rtr->Next;free(ptr);}編寫一個算法，功能是復(fù)制一個鏈串。答：復(fù)制一個完整的鏈串，是一件比較容易的事情。其算法起名為Copy_Lt()，參數(shù)為Lt1。具體編寫如下。Copy_Lt(Lt1){ptr=Lt1_h;rtr=malloc(size);rtr->Data=ptr->Data;Lt2_h=rtr;ptr=ptr->Next;while(ptr!={qtr=malloc(size);qtr->Data=ptr->Data;rtr->Next=qtr;ptr=ptr->Next;}rtr->Next=NULL;return(Lt2_h);}-19-習(xí)題解答while循環(huán)，不斷修改指針ptr，以便指向鏈串Lt1rtr總是指向當前已形成的新鏈串Lt2的最后一個結(jié)點；用指針qtr并把它鏈入到rtr所指結(jié)點的后面。mⅹn的矩陣A。編寫一個算法，求C=A+B。即Cmⅹn矩陣，其元素滿足條件：ijcij=aij+b（1≤i≤m，1≤j≤n）答：算法名為Add_Mt()，參數(shù)為A，B，C。ijAdd_Mt(A,B,C){for(i=1;i<=m;i++)for(j=1;j<=n;j++)C[i][j]=A[i][j]+B[i][j];}5章習(xí)題解答（此處樹的高度不計算根節(jié)點）一、填空72，最高是6。給定二叉樹的結(jié)點數(shù)，要使樹高為最矮，那么該樹應(yīng)該是完全二叉樹形狀。6，那么它共有127個結(jié)點，有64個葉結(jié)點。1518個葉結(jié)點。n2n-1個結(jié)點。將一棵完全二叉樹按層次進行編號。那么，對編號為i2i2i+1。若二叉樹共有n有2nn+1個指針域是空的。531個結(jié)點。二、選擇4C不是完全二叉樹。3D個空結(jié)點。A．10 B．8 C．6 D．4設(shè)有一棵5B-A-D-C-E，那么它的后序遍歷序列為B。A．A-B-D-E-C B．B-D-E-C-AC．D-E-C-A-B D．A-B-C-D-E-20-習(xí)題解答將一棵有50個結(jié)點的完全二叉樹按層編號，那么編號為25的結(jié)點是BA．無左、右孩子 B．有左孩子，無右孩子C．有右孩子，無左孩子 D．有左、有孩子6的二叉樹，最多可以有A個結(jié)點。A．63 B．64 C．127 D．128在一棵非空二叉樹的中序遍歷序列里，根結(jié)點的右邊D結(jié)點A．只有左子樹上的部分 B．只有左子樹上的所有C．只有右子樹上的部分 D．只有右子樹上的所有A。A．不發(fā)生變化 B．發(fā)生變化C．不能確定 D．以上都不對1、、、8D。A．18 B．28 C．19 D．29271。那么它的葉結(jié)點數(shù)是C。A．6 B．7 C．8 D．9105層上的結(jié)點數(shù)最多是CA．8 B．15 C．16 D．32三、問答試問滿二叉樹與完全二叉樹之間有何關(guān)系？滿二叉樹。這就是滿二叉樹與完全二叉樹之間的關(guān)系。335種，如下圖所示。其中，4棵樹的高度為2，1棵樹的高度為1。3的滿二叉樹有多少個葉結(jié)點？有多少個度為2結(jié)點？答：有23=8個葉結(jié)點，有度為2的結(jié)點23-1=7個，總共有23+1-1=24-1=15個結(jié)點。有人說，任何一棵非空滿二叉樹，它的葉結(jié)點數(shù)等于其分支結(jié)點數(shù)加1個結(jié)論正確嗎？請說明理由（5-3）答：在我們介紹的二叉樹性質(zhì)中，只有性質(zhì)5-3是涉及葉結(jié)點數(shù)與（度為2的）分支結(jié)25-3得出所需要的結(jié)論。所以，此人說的結(jié)論是完全正確的。有人說，有一棵結(jié)點數(shù)為n>1能的話，這樣一棵二叉樹應(yīng)該是個什么樣子呢？叉樹，如圖所示。-21-習(xí)題解答試問，什么樣的二叉樹其先序遍歷序列與中序遍歷序列相同？左孩子的非空二叉樹。5-32所示二叉樹的先序、中序、后序遍歷序列。圖5-32 二叉樹示例答：先序遍歷序列為：A-B-C-D-F-G-H-E，中序遍歷序列為：B-A-D-G-F-H-C-E，后序遍歷序列為：B-G-H-F-D-E-C-A。四、應(yīng)用對一個二叉樹進行順序存儲，各結(jié)點的編號及數(shù)據(jù)如表所示：編號i1234571011數(shù)據(jù)xABCDEFGH試畫出對應(yīng)的二叉樹，并給出先序、中序、后序遍歷該二叉樹后，所得到的各種結(jié)點序列。答：對應(yīng)的二叉樹如圖所示。其先序遍歷序列是：A-B-D-E-G-H-C-F；中序遍歷序列是：D-B-G-E-H-A-C-F；后許遍歷序列是：D-G-H-E-B-F-C-A。畫出這棵二叉樹。答：這棵二叉樹如應(yīng)用題2答案圖所示。。試畫出這棵-22-習(xí)題解答二叉樹。答：這棵二叉樹如應(yīng)用題3答案圖所示。若一棵二叉樹的左、右子樹均有3列相同，右子樹的中序遍歷序列與后序遍歷序列相同。請畫出這棵二叉樹。答：這棵二叉樹如應(yīng)用題4答案圖所示。理解算法5-105-25(b)的基礎(chǔ)上，進行下一次組合。試給出第2的情形，以及那時二叉樹的樣子。答：第2次組合后數(shù)組的情形如下圖(a)所示，那時二叉樹的樣子如下圖(b)所示。16203024答：構(gòu)造這棵哈夫曼樹的全過程如下所示。-23-習(xí)題解答113（。序號1234567891011Lchild6^7^8^5^2^^DataMFAKBLCRDSERchild^^^9^10411^^^答：二叉樹如圖所示，先序遍歷序列為：A-C-B-R-S-E-D-F-M-L-K，中序遍歷序列為：R-B-S-C-E-A-F-D-L-K-M，后序遍歷序列為：R-S-B-E-C-F-K-L-M-D-A。6章習(xí)題解答一、填空結(jié)點。結(jié)點。n（n≥0）在如圖6-21H的祖先是G。圖6-21 樹示例 圖6-22 樹示例6-22所示。它的根結(jié)點是A，葉結(jié)點是G、、J、、-24-習(xí)題解答NOPQ、R，這棵樹的度是3，這棵樹的深度是4，結(jié)點F的孩子結(jié)點是J、K，結(jié)點G的父結(jié)點是C，結(jié)點HD、A是結(jié)點R的祖先。二、選擇D。B． C． D．將一棵樹Tr轉(zhuǎn)換成相應(yīng)的二叉樹Bt，那么對Tr的先序遍歷是對Bt的A。先序遍歷 B．中序遍歷 C．后序遍歷 D．無法確定3．將一棵樹Tr轉(zhuǎn)換成相應(yīng)的二叉樹Bt，那么對Tr的后序遍歷是對Bt的BA．先序遍歷 B．中序遍歷 C．后序遍歷 D．無法確定4 F 3．設(shè)森林中有棵樹，依次有結(jié)點nnn個。把該森林轉(zhuǎn)換成對應(yīng)的二叉樹后，4 F 31 2 3該二叉樹的右子樹上的結(jié)點個數(shù)是D。A B + C D ．n ．n n ．n ．A B + C D 1 1 2 3 2 35 T T ．設(shè)有由三棵樹、、組成的森林，其結(jié)點個數(shù)分別為n、n、n5 T T 1 2 3 1 2 3應(yīng)的二叉樹為BtA個。1 1 1 1 A．n-1 B．n C．n+1 D．n+1 1 1 1 33210C。A．5 B．8 C．6 D．9注意：有n個結(jié)點的樹，樹中所有結(jié)點的度之和為n-1。現(xiàn)在這棵樹應(yīng)該滿足條件：n-1=2*3+1*2+2*1=1011個結(jié)點（加上一個根結(jié)點1132、1506個。一棵有nB個結(jié)點。A．n-2 B．n-1 C．n+1 D．n+2一棵有nA個結(jié)點。A．0 B．n C．n+1 9A。A．樹的先序遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同B．樹的先序遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同C．樹的后序遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同D．樹的后序遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同三、問答6-23所示的兩棵樹是一樣的嗎？為什么？答：從圖6-23(a)知，該樹的根結(jié)點為A，下面有兩棵子樹，其中的一棵子樹是最小樹，只有根結(jié)點為B；另一棵子樹的根結(jié)點為C，下面又有一棵最小子樹，它的根結(jié)點為D。從圖6-23(b)知，該樹的根結(jié)點也是A與圖6-23(a)里的相同。因此如果把樹的子樹視為是無序的，那么該圖所展示的兩棵樹是一-25-習(xí)題解答樣的，否則是不一樣的。

圖6-23 樹示例樹，但樹的每個結(jié)點可以有多棵子樹；第二，二叉樹的子樹有左、右之分（即是有序的，但樹的子樹通常是不分順序的。為什么對于二叉樹有中序遍歷，而對一般樹卻沒有中序遍歷？其結(jié)點可以有任意數(shù)目的子樹，因此，無法規(guī)定怎樣的訪問順序才算是“中序最右邊的結(jié)點最后訪問？1）層次遍歷和先序遍歷總是首先訪問樹的根結(jié)點（）于樹最左邊的結(jié)點（）后序遍歷總是最后訪問樹的根結(jié)點（）的最右邊的結(jié)點。2的樹與一棵二叉樹有什么區(qū)別？22的樹結(jié)點的子不能隨意換位。四、應(yīng)用已知一棵樹的孩子鏈表表示法如圖6-24所示，試畫出該樹。圖6-24 一棵樹的孩子鏈表表示法 圖6-25 樹示例答：該樹形狀如下圖所示。已知一棵樹如圖6-25所示。請畫出該樹的以下存儲結(jié)構(gòu)）雙親表示法（2）帶-26-習(xí)題解答（子鏈表表示法。望能夠把兩者結(jié)合起來（）兄弟鏈表表示法。（）(a）(b孩子/(c)所示。6-26所示的二叉樹轉(zhuǎn)換成相應(yīng)的森林。圖6-26 二叉樹示例 圖6-27 樹示例答：轉(zhuǎn)換成的森林如下圖所示。6-27所示樹的先序遍歷序列和后序遍歷序列。答：該樹的先序遍歷序列為：A-B-E-F-K-L-M-C-G-D-H-I-J；該樹的后序遍歷序列是：E-K-M-L-F-B-G-C-H-I-J-D-A。-27-習(xí)題解答6-28所示的森林轉(zhuǎn)換成對應(yīng)的二叉樹。圖6-28 森林示例 圖6-29 樹示例答：對應(yīng)的二叉樹如下圖所示。6-29答：對應(yīng)的二叉樹如下圖所示7章習(xí)題解答一、填空46條。在一個具有4個頂點的無向圖中，要連通全部頂點3條邊。vv之間有一條邊，v）vv互i j i j i j為鄰接點。圖中頂點v相鄰接的頂點的個數(shù)，并記為D(v。i i-28-習(xí)題解答ivivj的弧記為<v，vj>vjviij 的弧記為<v，v>，這是兩條不同的弧。j i行（或第i列）i個頂點vi的度。ii個頂點vi的出度；其鄰接矩陣中第i列里非零或非∞元素的個數(shù)，正好是第i個頂點vi的入度。在無向圖中，若從頂點vi到頂點vj之間有路徑存在，則稱vivj是連通的。GG連通圖。在無向圖G中，盡可能多地從集合V及E個極大的連通子圖，這個子圖就被稱為是無向圖G的一個連通分量。包含無向連通圖Gn個頂點在內(nèi)的極小連通子圖，是這個圖的生成樹。15．已知無向圖的頂點個數(shù)為n，邊數(shù)為e。那么，在其鄰接表表示法中，鏈表結(jié)點數(shù)與單鏈表表頭結(jié)點數(shù)之和是15．已知無向圖的頂點個數(shù)為n，邊數(shù)為e。那么，在其鄰接表表示法中，鏈表結(jié)點數(shù)與單鏈表表頭結(jié)點數(shù)之和是n+2e。二、選擇1．在一個有n個頂點的無向圖中，要連通全部頂點，至少需要C條邊。A．n B．n+1 C．n-1 D．n/22n個頂點的無向完全圖包含有C條邊。A．n(n-1) B．n(n+1) C．n(n-1)/2 D．n(n+1)/23nA條邊。A．n(n-1) B．n(n+1) C．n(n-1)/2 D．n(n+1)/24．在一個無向圖中，所有頂點的度數(shù)之和，是其所有邊數(shù)之和的CA．1/2 B．1 C．2 D．45．在一個有向圖中，所有頂點的入度之和BA．二分之一于 B．等于 C．兩倍于 D．四倍6．一個無向連通網(wǎng)圖的最小生成樹A。A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存7．一個無向圖有n個頂點，那么該圖擁有的邊數(shù)至少是D。A．2n B．n C．n/2 D．0nC條邊。A．4n-1 B．2n-1 C．n-1 9C。A．用鄰接表存儲圖，所用存儲空間大小只與圖中頂點個數(shù)有關(guān)，與邊數(shù)無關(guān)B．用鄰接表存儲圖，所用存儲空間大小只與圖中邊數(shù)有關(guān)，與頂點個數(shù)無關(guān)CD．用鄰接矩陣存儲圖，所用存儲空間大小只與圖中邊數(shù)有關(guān)，與頂點個數(shù)無關(guān)10．對如圖7-21所示的無向圖實施深度優(yōu)先搜索遍歷，可能的遍歷序列是B。-29-習(xí)題解答圖7-21 無向圖示例三、問答7-22所示的無向連通網(wǎng)圖的。一個無向連通網(wǎng)圖的MST唯一嗎？圖7-22 無向連通網(wǎng)圖示例 圖7-23 無向圖示例答：其MST如圖7-15(g所示。如果使用邊4,6）代替邊3,6MST。所以，MST不是唯一的。試述簡單回路、回路兩者間的聯(lián)系與不同。重復(fù)出現(xiàn)，那么這條路徑稱為簡單回路后一個頂點相同，那么這條路徑稱為回路有如圖7-23v1遍歷序列。答：它的鄰接矩陣如圖所示。從頂點v1出發(fā)的深度優(yōu)先遍歷序列為：v1->v2->v4->v5->v7->v6->v3注意，該序列是不唯一的。構(gòu)造最小生成樹的Prim算法與求單源最短路徑的Dijkstra圖中的頂點分成U和V-U兩個部分，都是在V-U里挑選出一個頂點，并將它從V-U移到U中。那么，它們的主要區(qū)別是什么？-30-習(xí)題解答算法是從V-U里挑選MST中某個頂點相距最近的頂點，而Dijkstra算法是從V-U源點最近的頂點。m個頂點的無向圖G，如何通過它的鄰接矩陣判定下列問題：圖中有多少條邊？任意兩個頂點ij之間是否有邊相連？任意一個頂點i的度是多少？（）鄰接矩陣中非零元素個數(shù)的一半，是圖中邊的數(shù)目（）元素A{,和A[,是否不為，可知頂點i和j之間是否有邊相連（3）第i行或第i列上i的度。7-24回答下列問題：（1）頂點集合V； （2）邊集合E； （3）每個頂點x的度D(x)；（4）一個長度為5的路徑； （5）一個長度為4的回路；（6）圖的一個生成樹； （7）鄰接矩陣； （8）鄰接表。圖7-24 圖示例（）頂點集合V=1,2,3,,5,6。（2）邊集合E={<v1,v2>,<v2,v3>,<v2,v4>,<v3,v4>,<v3,v5>,<v4,v5>,<v3,v6>,<v4,v6>}。（3）每個頂點的度：D(v1)=1，D(v2)=3，D(v3)=D(v4)=4，D(v5)=D(v6)=2。5（4）一個長度為5的路徑是：v1->v2->v3->v6->v4->v。524的回路是：v2v3v5v4v。2所示。所示。所示。問答5的（6）~（8）答案-31-習(xí)題解答四、應(yīng)用利用Kruskal7-14(a)所給無向連通網(wǎng)圖的最小生成樹。MSTKruskal算法時，從圖的邊E里挑選邊v,v，因為這兩個頂點分屬MST中的不同連通分量，且權(quán)6 767MSTvv(b)所示。接著，從圖67的邊E里挑選邊vv、挑選邊vv、挑選邊vv）挑選邊v,v）挑選邊v,v，1 3 1 2 4 6 5 7 3 6最終得到如圖(g)所示的最小生成樹。利用Floyd7-25所示的有向網(wǎng)圖中各頂點對的最短路徑長度。圖7-25 有向網(wǎng)圖示例答：Floyd算法基于的鄰接矩陣，以及推演出的各個矩陣、最終結(jié)果如下所示。1Dijkstra7-26v1v1 4度是；v41 4度是；v41

的最短路徑長的最短路徑長的最短路徑長-32-習(xí)題解答1度是；v11

v65 6

v36 3

v的最短路徑長度76 是；vv的最短路徑長度是。如圖所示。6 1 8圖7-26 圖示例 圖7-27 AOV網(wǎng)7-27所示的AOV網(wǎng)的拓撲排序序列。答：該網(wǎng)只有頂點v3的入度為0，所以只能從它開始進行拓撲排序，其拓撲序列為：v3->v1->v4->v5->v2->v6生成樹。答：無向連通網(wǎng)以及所對應(yīng)的最小生成樹如圖(a)、(b)所示。8章習(xí)題解答一、填空記錄的集合是實施查找的數(shù)據(jù)基礎(chǔ)。在討論查找問題時，常把T稱為查找表。有序表和分塊有序表是一種靜態(tài)查找表；二叉查找樹是一種動態(tài)查找表。1為根結(jié)點的子樹為“最小不平衡樹-33-習(xí)題解答或哈希表。二、選擇在對線性表進行折半查找時，要求線性表必須BA．以順序方式存儲B．以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列C．以鏈式方式存儲D．以鏈式方式存儲，且結(jié)點按關(guān)鍵字有序排列采用順序查找法查找長度為nC。A．n B．n/2 C．(n+1)/2 3．有一個有序表：1，3，9，12，32，41，45，62，75，77，82，95，100采用折半查找法查找值為82的記錄時，要經(jīng)C次關(guān)鍵字比較后，查找成功。A．1 B．2 C．4 D．815、38、61、84，采用二次探測法解決沖突。那么關(guān)鍵字為49的記錄的散列地址為D。A．1 B．3 C．5 D．95．在下列各種查找方法中，只有AnA．散列查找 B．二叉查找樹 C．折半查找 D．分塊查找6．在開放地址法中，由于散列到同一個地址而引起的“堆積”現(xiàn)象，是由B產(chǎn)生的A．同義詞之間發(fā)生沖突B．非同義詞之間發(fā)生沖突CD．散列表“溢出”在最壞的情況下，查找成功時二叉查找樹的平均查找長度CA．小于線性表的平均查找長度B．大于線性表的平均查找長度C．與線性表的平均查找長度相同D．無法與線性表的平均查找長度相比較C。A．必須大于、等于原散列地址B．必須小于、等于原散列地址CD．地址大小沒有具體限制三、問答（1）、if、for、while、repeat，依照創(chuàng)建二叉查找樹算法，、loopiffor找長度又是多少？-34-習(xí)題解答（）(a所示，平均查找長度是：ASLa=(1+2*2+2*3)/5=11/5=2.2(2)的二叉查找樹如圖(b)所示，平均查找長度是：ASLb=(1+2+3+4+5)/5=15/5=310需要的比較次數(shù)。答：根據(jù)折半查找算法，因此首先用給定值K與區(qū)間[1，10]5的元素比較次數(shù)為1[1，4]或[6，10]中繼續(xù)折半查找，因281、、、9的元素的比47、104。于是，所填結(jié)果為：四、應(yīng)用3527，請一步步畫出構(gòu)造二叉查找樹的過程。答：構(gòu)造二叉查找樹的過程如下：給出如圖8-21所示的一棵二叉查找樹，在其基礎(chǔ)上分別做操作（）刪除關(guān)鍵字為15）插入關(guān)鍵字為20的記錄。畫出這兩個操作完成后該樹的形態(tài)。-35-習(xí)題解答圖8-21 二叉查找樹示例答：1）刪除關(guān)鍵字為15(a)或(b)直接前驅(qū)（或左子樹根結(jié)點）取代所得，而(b)則是用待刪結(jié)點的直接后繼（或右子樹根結(jié)點）2）插入關(guān)鍵字為20(c所示。設(shè)散列函數(shù)為h(key)=key%1，散列表長為1（索引地址為0~1SUN，MON，TUE，WED，THU，F(xiàn)RI，SAT取單詞第1個字母在英語字母表中的序號為關(guān)鍵字值（比如S的關(guān)鍵字值為1址法解決散列地址沖突。請畫出對應(yīng)的散列表。答：對應(yīng)的散列表如下。4．有關(guān)鍵字序列：36、27、68、33、97、40、81、24、23、90、32、14，散列表長為h(key)=key%13，使用開放地址法的線性探測解決沖突。請完成下面散列表的填寫（13610以比較一次就存放在了地址為10的位置，求出其平均查找長度AS。-36-習(xí)題解答答：最終的散列表如圖所示。其平均查找長度ASL為：ASL（線性探測12個關(guān)鍵字組成的序列：Jan，F(xiàn)eb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec在等概率下查找成功的平均查找長度。樹查找成功的平均查找長度。（）最終形成的二叉查找樹如下圖所示，其平均查找長度為：ASL=（1+2*2+3*3+3*4+2*5+6）/12=42/12=3.5-37-習(xí)題解答（2）這時成為只有右子樹的單支樹，其平均查找長度為：ASL=（1+2+3+4+5+6+7+8+9+10+11+12）/12=78/12=6.512個關(guān)鍵字組成的序列：Jan，F(xiàn)eb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec散列表長為1（地址為0~1h(key)=i/，其中i為關(guān)鍵字中第1母表里的序號。用線性探測法解決沖突，給出所構(gòu)造的散列表以及查找成功的平均查找長度。（）用線性探測法解決沖突時，插入地址及比較次數(shù)如下：h(Jan)=10/2=5，比較1次插入；h(Feb)=6/2=3，比較1次插入；h(Mar)=13/2=6，比較1次插入；h(Apr)=1/2=3，比較1次插入；h(May)=13/2=6，比較2次插入；h(Jun)=10/2=5，比較4次插入；h(Jul)=10/2=5，比較5次插入；h(Aug)=1/2=0，比較2次插入；h(Sep)=19/2=9，比較2次插入；h(Oct)=15/2=7，比較5次插入；h(Nov)=14/2=7，比較6次插入；h(Dec)=4/2=2，比較1次插入。所以，構(gòu)造的散列表如圖所示。平均查找長度為：ASL=（1+1+1+1+2+4+5+2+2+5+6+1）/12=31/12≈2.6（2）用鏈地址法解決沖突時，構(gòu)造的散列表如圖所示。平均查找長度為：ASL=（1+2+1+1+1+2+3+1+2+1+2+1）/12=18/12=1.59章習(xí)題解答一、填空置上，以便構(gòu)成一個新堆。、38、96、23、18、7361、46、88，采用直接插入排序算-38-習(xí)題解答法。在進行到尋找第7個關(guān)鍵字61的插入位置時，需要做3次比較。（7