【正文】 ll))if(pkey= =K){found=1。qnext=pnext。} else{q=p。p=pnext。} if(!found)return(“infeasible”)。} return(hash)。}第九章 排序一、選擇題，關(guān)鍵字比較的次數(shù)與記錄得初始排列次序無(wú)關(guān)的是（）（A）希爾排序（B）起泡排序（C）插入排序（D）選擇排序,希望用最快的速度挑選出其中前10個(gè)最大的元素,最好（）排序法。（A）起泡排序（B）快速排序（C）堆排序（D）基數(shù)排序,效率最高的排序方法是（）（A）插入排序（B）選擇排序（C）快速排序（D）歸并排序(46,79,56,38,40,84),則利用堆排序的方法建立的初始推為（）。（A）79,46,56,38,40,80（B）84,79,56,38,40,46（C）84,79,56,46,40,38（D）84,56,79,40,46,38 (46,79,56,38,40,84),則利用快速排序的方法,以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。（A）38,40,46,56,79,84（B）40,38,46,79,56,84（C）40,38,46,56,79,84（D）40,38,46,84,56,79 (25,48,16,35,79,82,23,40,36,72),其中含有5個(gè)長(zhǎng)度為2的有序表,按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（）。（A）16,25,35,48,23,40,79,82,36,72（B）16,25,35,48,79,82,23,36,40,72（C）16,25,48,35,79,82,23,36,40,72（D）16,25,35,48,79,23,36,40,72,82 ,從未排序序列中依次取出元素與己排序序列(初始時(shí)為空)中的元素進(jìn)行比較,將其放入己排序序列的正確位置上的方法,稱為（）第二篇：數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案總結(jié)第一章第1章作業(yè)：,(1)(3) 簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)?！?數(shù)據(jù)：指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息載體?！?數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)元素有時(shí)可以由若干數(shù)據(jù)項(xiàng)組成?！?數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計(jì)語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)?！?數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個(gè)方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算?！?邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系?！?存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu).● 線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類。它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨和一個(gè)直接后繼。線性表就是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。● 非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。 試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算三個(gè)方面的內(nèi)容。答：例如有一張學(xué)生體檢情況登記表，記錄了一個(gè)班的學(xué)生的身高、體重等各項(xiàng)體檢信息。這張登記表中，每個(gè)學(xué)生的各項(xiàng)體檢信息排在一行上。這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)記錄(有姓名，學(xué)號(hào)，身高和體重等字段)就是一個(gè)結(jié)點(diǎn)，對(duì)于整個(gè)表來(lái)說(shuō)，只有一個(gè)開始結(jié)點(diǎn)(它的前面無(wú)記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無(wú)記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼(它的前面和后面均有且只有一個(gè)記錄)。這幾個(gè)關(guān)系就確定了這個(gè)表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)。這個(gè)表中的數(shù)據(jù)如何存儲(chǔ)到計(jì)算機(jī)里，并且如何表示數(shù)據(jù)元素之間的關(guān)系呢? 即用一片連續(xù)的內(nèi)存單元來(lái)存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針進(jìn)行鏈接呢? 這就是存儲(chǔ)結(jié)構(gòu)的問(wèn)題。在這個(gè)表的某種存儲(chǔ)結(jié)構(gòu)基礎(chǔ)上，可實(shí)現(xiàn)對(duì)這張表中的記錄進(jìn)行查詢，修改，刪除等操作。對(duì)這個(gè)表可以進(jìn)行哪些操作以及如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算問(wèn)題了。 設(shè)n為正整數(shù)，利用大“O”記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。(1)i=1。k=0。while(ij)j++。else i++。} 分析：通過(guò)分析以上程序段，可將i+j看成一個(gè)控制循環(huán)次數(shù)的變量，且每執(zhí)行一次循環(huán)，i+j的值加1。該程序段的主要時(shí)間消耗是while循環(huán)，而while循環(huán)共做了n次，所以該程序段的執(zhí)行時(shí)間為：T(n)=O(n) 按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：2100,(3/2)n，(2/3)n，nn , , n!，2n，lgn ,nlgn, n(3/2)答：常見的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列,依次為:常數(shù)階0(1)、對(duì)數(shù)階0(log2n)、線性階0(n)、線性對(duì)數(shù)階0(nlog2n)、平方階0(n2)、立方階0(n3)、k次方階0(nk)、指數(shù)階0(2n)。先將題中的函數(shù)分成如下幾類：常數(shù)階：2 對(duì)數(shù)階：lgn K次方階：n、(3/2)100指數(shù)階(按指數(shù)由小到大排)：nlgn、(3/2)n、2n、n!、nn注意：(2/3)^n由于底數(shù)小于1，所以是一個(gè)遞減函數(shù)，其數(shù)量級(jí)應(yīng)小于常數(shù)階。根據(jù)以上分析按增長(zhǎng)率由小至大的順序可排列如下：(2/3)n 2100 lgn n(3/2) nlgn 第二章第二章作業(yè)：，, 何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜? 答：在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問(wèn)題的要求和性質(zhì)來(lái)選擇順序表或鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)，通常有以下幾方面的考慮： 。當(dāng)要求存儲(chǔ)的線性表長(zhǎng)度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表；反之，當(dāng)線性表長(zhǎng)度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；反之，若需要對(duì)線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是無(wú)頭結(jié)點(diǎn)單鏈表 ListNode *Q,*P。if(Lamp。amp。Lnext){ Q=L。L=Lnext。P=L。while(Pnext)P=Pnext。Pnext=Q。Qnext=NULL。} return L。}// Demo 答：該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。 設(shè)線性表的n個(gè)結(jié)點(diǎn)定義為(a0,a1,...an1)，重寫順序表上實(shí)現(xiàn)的插入和刪除算法：InsertList ：算法如下: define ListSize 100 // 假定表空間大小為100 typedef int DataType。//假定DataType的類型為int型 typedef struct{ DataType data[ListSize]。// 向量data用于存放表結(jié)點(diǎn) int length。// 當(dāng)前的表長(zhǎng)度 } Seqlist。//以上為定義表結(jié)構(gòu)void InsertList(Seqlist *L, Datatype x, int i){ //將新結(jié)點(diǎn)x插入L所指的順序表的第i個(gè)結(jié)點(diǎn)ai的位置上，即插入的合法位置為：0length int j。if(i 0 || i L length)Error(“position error”)。// 非法位置，退出，if(Llength=ListSize)Error(“overflow“)。for(j=Llength1。j = i。j)Ldata[ j+1]=Ldata [ j ]。Ldata[ i ]=x。Llength++。} 設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入L中，并使L仍是一個(gè)有序表。答：因已知順序表L是遞增有序表，所以只要從順序表終端結(jié)點(diǎn)（設(shè)為i位置元素）開始向前尋找到第一個(gè)小于或等于x的元素位置i后插入該位置即可。在尋找過(guò)程中，由于大于x的元素都應(yīng)放在x之后，所以可邊尋找，邊后移元素，當(dāng)找到第一個(gè)小于或等于x的元素位置i時(shí)，該位置也空出來(lái)了。算法如下：// void InsertIncreaseList(Seqlist *L , Datatype x){ int i。if(Llength=ListSize)Error(“overflow”)。for(i=L length。i0 amp。amp。 Ldata[ i1 ] x。i)Ldata[ i ]=Ldata[ i ]。// 比較并移動(dòng)元素 Ldata[ i ] =x。L length++。} 設(shè) A和B是兩個(gè)單鏈表，其表中元素遞增有序。試寫一算法將A和B歸并成一個(gè)按元素值遞減有序的單鏈表C，并要求輔助空間為O(1)，請(qǐng)分析算法的時(shí)間復(fù)雜度。解：根據(jù)已知條件，A和B是兩個(gè)遞增有序表，所以可以先取A表的表頭建立空的C表。然后同時(shí)掃描A表和B表，將兩表中最大的結(jié)點(diǎn)從對(duì)應(yīng)表中摘下，并作為開始結(jié)點(diǎn)插入C表中。如此反復(fù)，直到A表或B表為空。最后將不為空的A表或B表中的結(jié)點(diǎn)依次摘下并作為開始結(jié)點(diǎn)插入C表中。這時(shí)，得到的C表就是由A表和B表歸并成的一個(gè)按元素值遞減有序的單鏈表C。并且輔助空間為O(1)。算法如下：LinkList MergeSort(LinkList A , LinkList B){// 歸并兩個(gè)帶頭結(jié)點(diǎn)的遞增有序表為一個(gè)帶頭結(jié)點(diǎn)遞減有序表 ListNode *pa , *pb , *q , *C。pa=Anext。//pa指向A表開始結(jié)點(diǎn)C=A。Cnext=NULL。//取A表的表頭建立空的C表 pb=Bnext。//pb指向B表開始結(jié)點(diǎn) free(B)。//回收B表的頭結(jié)點(diǎn)空間 while(pa amp。amp。 pb){ if(pbdata data){ // 當(dāng)B中的元素小于等于A中當(dāng)前元素時(shí)，將pa表的開始結(jié)點(diǎn)摘下 q=pa。pa=panext。} else {// 當(dāng)B中的元素大于A中當(dāng)前元素時(shí)，將pb表的開始結(jié)點(diǎn)摘下 q=pb。pb=pbnext。} qnext=Cnext。Cnext=q。//將摘下的結(jié)點(diǎn)q作為開始結(jié)點(diǎn)插入C表 } //若pa表非空，則處理pa表 while(pa){ q=pa。pa=panext。qnext=Cnext。Cnext=q。} //若pb表非空，則處理pb表 while(pb){ q=pb。pa=pbnext。qnext=Cnext。Cnext=q。} return(C)。} 該算法的時(shí)間復(fù)雜度分析如下：算法中有三個(gè)while 循環(huán)，其中第二個(gè)和第三個(gè)循環(huán)只執(zhí)行一個(gè)。每個(gè)循環(huán)做的工作都是對(duì)鏈表中結(jié)點(diǎn)掃描處理。整個(gè)算法完成后，A表和B表中的每個(gè)結(jié)點(diǎn)都被處理了一遍。所以若A表和B表的表長(zhǎng)分別是m和n，則該算法的時(shí)間復(fù)雜度O(m+n)●：寫出在線性表中的查找運(yùn)算算法。即查找數(shù)據(jù)元素x在表中的位置，也就是數(shù)據(jù)元素下標(biāo)值加1。例如：[i]=x,則返回i+1。若不存在，則返回n+1 ：編寫尾插法建立鏈表的算法。：若是帶頭指針的單鏈表，算法又是怎樣？若是兩個(gè)鏈表，既知道頭結(jié)點(diǎn)，又知道尾結(jié)點(diǎn)，算法又是怎樣？●練習(xí)2：按升序打印帶頭結(jié)點(diǎn)h的單鏈表中各節(jié)點(diǎn)的數(shù)據(jù)域值，并將打印完的節(jié)點(diǎn)從表中刪除。第三章第三章作業(yè)：, ，（2）， 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么? 如何判別它的空和滿? 答：循環(huán)隊(duì)列的優(yōu)點(diǎn)是：它可以克服順序隊(duì)列的“假上溢”現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分的利用。判別循環(huán)隊(duì)列的“空”或“滿”不能以頭尾指針是否相等來(lái)確定，一般是通過(guò)以下幾種方法：一是另設(shè)一布爾變量來(lái)區(qū)別隊(duì)列的空和滿。二是少用一個(gè)元素的空間,每次入隊(duì)前測(cè)試入隊(duì)后頭尾指針是否會(huì)重合，如果會(huì)重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個(gè)數(shù)。，若設(shè)頭指針，則入隊(duì)出隊(duì)操作的時(shí)間為何? 若只設(shè)尾指針呢? 答：當(dāng)只設(shè)頭指針時(shí)，出隊(duì)的時(shí)間為1，而入隊(duì)的時(shí)間需要n，因?yàn)槊看稳腙?duì)均需從頭指針開始查找，找到最后一個(gè)元素時(shí)方可進(jìn)行入隊(duì)操作。若只設(shè)尾指針，則出入隊(duì)時(shí)間均為1。因?yàn)槭茄h(huán)鏈表，尾指針?biāo)傅南乱粋€(gè)元素就是頭指針?biāo)冈?，所以出?duì)時(shí)不需要遍歷整個(gè)隊(duì)列。 指出下述程序段的功能是什么?(2)SeqStack S1, S2, tmp。DataType x。...//假設(shè)棧tmp和S2已做過(guò)初始化while(!StackEmpty(amp。S1)){x=Pop(amp。S1)。Push(amp。tmp,x)。}while(!StackEmpty(amp。tmp)){x=Pop(amp。tmp)。Push(amp。S1,x)。Push(amp。S2, x)。}(2)程序段的功能是利用tmp棧將一個(gè)非空棧s1的所有元素按原樣復(fù)制到一個(gè)棧s2當(dāng)中去。 利用棧的基本操作，寫一個(gè)將棧S中所有結(jié)點(diǎn)均刪去的算法void ClearStack(SeqStack *S)，并說(shuō)明S為何要作為指針參數(shù)解：算法如下void ClearStack(SeqStack *S){ // 刪除棧中所有結(jié)點(diǎn)STop =1。//其實(shí)只是將棧置空}因?yàn)橐每盏氖菞，如果不用指針來(lái)做參數(shù)傳遞，那么函數(shù)進(jìn)行的操作不能對(duì)原來(lái)的棧產(chǎn)生影響，系統(tǒng)將會(huì)在內(nèi)存中開辟另外的單元來(lái)對(duì)形參進(jìn)行函數(shù)操作。結(jié)果等于什么也沒有做。所以想要把函數(shù)操作的結(jié)果返回給實(shí)參的話，就只能用指針來(lái)做參數(shù)傳遞了。 設(shè)計(jì)算法判斷一個(gè)算術(shù)表達(dá)式的圓括號(hào)是否正確配對(duì)。(提示： 對(duì)表達(dá)式進(jìn)行掃描，凡遇到‘(’就進(jìn)棧，遇‘)’就退掉棧頂?shù)摹?’，表達(dá)式被掃描完畢，棧應(yīng)為空。解：根據(jù)提示，可以設(shè)計(jì)算法如下：int PairBracket(char *SR){//檢查表達(dá)式SR中括號(hào)是否配對(duì)int i