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

數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案總結(jié)第一章第1章作業(yè)：1.1,1.2,1.6(1)(3)1.8簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。數(shù)據(jù)：指能夠被計(jì)算機(jī)識別、存儲和加工處理的信息載體。數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)元素有時可以由若干數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計(jì)語言中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu).線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類。它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個開始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都有且只有一個直接前趨和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個結(jié)點(diǎn)可能有多個直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。試舉一個數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運(yùn)算三個方面的內(nèi)容。答：例如有一張學(xué)生體檢情況登記表，記錄了一個班的學(xué)生的身高、體重等各項(xiàng)體檢信息。這張登記表中，每個學(xué)生的各項(xiàng)體檢信息排在一行上。這個表就是一個數(shù)據(jù)結(jié)構(gòu)。每個記錄(有姓名，學(xué)號，身高和體重等字段)就是一個結(jié)點(diǎn)，對于整個表來說，只有一個開始結(jié)點(diǎn)(它的前面無記錄)和一個終端結(jié)點(diǎn)(它的后面無記錄)，其他的結(jié)點(diǎn)則各有一個也只有一個直接前趨和直接后繼(它的前面和后面均有且只有一個記錄)。這幾個關(guān)系就確定了這個表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)。這個表中的數(shù)據(jù)如何存儲到計(jì)算機(jī)里，并且如何表示數(shù)據(jù)元素之間的關(guān)系呢？即用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針進(jìn)行鏈接呢？這就是存儲結(jié)構(gòu)的問題。在這個表的某種存儲結(jié)構(gòu)基礎(chǔ)上，可實(shí)現(xiàn)對這張表中的記錄進(jìn)行查詢，修改，刪除等操作。對這個表可以進(jìn)行哪些操作以及如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算問題了。設(shè)n為正整數(shù)，利用大"O”記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。i=1;k=0;while(i<n){k=k+10*i;i++;)分析：i=1;//1k=0;//1while(i<n)//n{k=k+10*i;//n-1i++;//n-1)由以上列出的各語句的頻度，可得該程序段的時間消耗：T(n)=1+1+n+(n-1)+(n-1)=3n可表示為T(n)=O(n)(3)i=1;j=0;while(i+j<=n)(if(i>j)j++；elsei++;)分析：通過分析以上程序段，可將i+j看成一個控制循環(huán)次數(shù)的變量，且每執(zhí)行一次循環(huán)，i+j的值加1。該程序段的主要時間消耗是while循環(huán)，而while循環(huán)共做了n次，所以該程序段的執(zhí)行時間為：T(n)=O(n)1.8按增長率由小至大的順序排列下列各函數(shù)：2100,(3/2)n，(2/3)n，nn,n0.5,n!，2n，lgn川嗎答：常見的時間復(fù)雜度按數(shù)量級遞增排列，依次為:常數(shù)階0(1)、對數(shù)階0(log2n)、線性階0(n)、線性對數(shù)階0(nlog2n)、平方階0(m)、立方階0(m)、k次方階0(曲、指數(shù)階0(2n)。先將題中的函數(shù)分成如下幾類：常數(shù)階：2100對數(shù)階：lgnK次方階：n0.5、n(3/2)指數(shù)階(按指數(shù)由小到大排)：n.、(3/2)n、2n、n!、nn注意：(2/3)、由于底數(shù)小于1,所以是一個遞減函數(shù)，其數(shù)量級應(yīng)小于常數(shù)階。根據(jù)以上分析按增長率由小至大的順序可排列如下：(2/3)n<2100<lgn<n0.5<e<—<(3/2)n<2n<n!<n第二章第二章作業(yè)：2.2,2.6,2.9,2.132.2何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜？答：在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲結(jié)構(gòu)，通常有以下幾方面的考慮：.基于空間的考慮。當(dāng)要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表；反之，當(dāng)線性表長度變化大，難以估計(jì)其存儲規(guī)模時，采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。.基于時間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時，采用順序表做存儲結(jié)構(gòu)為宜；反之，若需要對線性表進(jìn)行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結(jié)構(gòu)。并且若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。.6下述算法的功能是什么？LinkListDemo(LinkListL){//L是無頭結(jié)點(diǎn)單鏈表ListNode*Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;)returnL;}//Demo答：該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來的第二個結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。.9設(shè)順序表L是一個遞增有序表，試寫一算法，將x插入1中，并使L仍是一個有序表。答：因已知順序表L是遞增有序表，所以只要從順序表終端結(jié)點(diǎn)(設(shè)為1位置元素)開始向前尋找到第一個小于或等于x的元素位置i后插入該位置即可。在尋找過程中，由于大于x的元素都應(yīng)放在x之后，所以可邊尋找，邊后移元素，當(dāng)找到第一個小于或等于x的元素位置i時，該位置也空出來了。算法如下：〃順序表存儲結(jié)構(gòu)如題2.7voidInsertIncreaseList(Seqlist*L,Datatypex)(inti;if(L->length>=ListSize)Error("overflow");for(i=L->length;i>0&&L->data[i-1]>x;i--)L->data[i]=L->data[i];//比較并移動元素L->data[i]=x;L->length++;)2.13設(shè)A和B是兩個單鏈表，其表中元素遞增有序。試寫一算法將A和B歸并成一個按元素值遞減有序的單鏈表C,并要求輔助空間為0(1),請分析算法的時間復(fù)雜度。解：根據(jù)已知條件，A和B是兩個遞增有序表，所以可以先取A表的表頭建立空的C表。然后同時掃描A表和B表，將兩表中最大的結(jié)點(diǎn)從對應(yīng)表中摘下，并作為開始結(jié)點(diǎn)插入C表中。如此反復(fù)，直到A表或B表為空。最后將不為空的A表或B表中的結(jié)點(diǎn)依次摘下并作為開始結(jié)點(diǎn)插入C表中。這時，得到的C表就是由A表和B表歸并成的一個按元素值遞減有序的單鏈表C。并且輔助空間為0(1)。算法如下：LinkListMergeSort(LinkListA,LinkListB){//歸并兩個帶頭結(jié)點(diǎn)的遞增有序表為一個帶頭結(jié)點(diǎn)遞減有序表ListNode*pa,*pb,*q,*C;pa=A->next;//pa指向A表開始結(jié)點(diǎn)C=A;C->next=NULL;//取A表的表頭建立空的C表pb=B->next;//pb指向B表開始結(jié)點(diǎn)free(B);//回收B表的頭結(jié)點(diǎn)空間while(pa&&pb){if(pb->data<=pa->data){//當(dāng)B中的元素小于等于A中當(dāng)前元素時，將pa表的開始結(jié)點(diǎn)摘下q=pa;pa=pa->next;)else{//當(dāng)B中的元素大于A中當(dāng)前元素時，將pb表的開始結(jié)點(diǎn)摘下q=pb;pb=pb->next;}q->next=C->next;C->next=q;//將摘下的結(jié)點(diǎn)q作為開始結(jié)點(diǎn)插入C表}〃若pa表非空，則處理pa表while(pa){q=pa;pa=pa->next;q->next=C->next;C->next=q;}〃若pb表非空，則處理pb表while(pb){q=pb;pa=pb->next;q->next=C->next;C->next=q;}return(C);)該算法的時間復(fù)雜度分析如下：算法中有三個while循環(huán)，其中第二個和第三個循環(huán)只執(zhí)行一個。每個循環(huán)做的工作都是對鏈表中結(jié)點(diǎn)掃描處理。整個算法完成后A表和B表中的每個結(jié)點(diǎn)都被處理了一遍。所以若A表和B表的表長分別是m和n,則該算法的時間復(fù)雜度O(m+n)練習(xí)2.1：寫出在線性表中的查找運(yùn)算算法。?即查找數(shù)據(jù)元素x在表中的位置，也就是數(shù)據(jù)元素下標(biāo)值加1。例如：若L.data[i]=x,則返回i+1;若不存在,則返回n+1練習(xí)2.2：編寫尾插法建立鏈表的算法。練習(xí)2.3：若是帶頭指針的單鏈表，算法又是怎樣？若是兩個鏈表，既知道頭結(jié)點(diǎn)，又知道尾結(jié)點(diǎn)，算法又是怎樣？練習(xí)2：按升序打印帶頭結(jié)點(diǎn)h的單鏈表中各節(jié)點(diǎn)的數(shù)?據(jù)域值，并將打印完的節(jié)點(diǎn)從表中刪除。第三章第三章作業(yè)：3.2,3.3,3.4(2)，3.6，3.11循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判別它的空和滿？答：循環(huán)隊(duì)列的優(yōu)點(diǎn)是：它可以克服順序隊(duì)列斷假上溢"現(xiàn)象，能夠使存儲隊(duì)列的向量空間得到充分的利用。判別循環(huán)隊(duì)列的"空"或"滿〃不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設(shè)一布爾變量來區(qū)別隊(duì)列的空和滿。二是少用一個元素的空間，每次入隊(duì)前測試入隊(duì)后頭尾指針是否會重合，如果會重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個數(shù)。設(shè)長度為n的鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊(duì)出隊(duì)操作的時間為何？若只設(shè)尾指針呢？答：當(dāng)只設(shè)頭指針時，出隊(duì)的時間為1，而入隊(duì)的時間需要n，因?yàn)槊看稳腙?duì)均需從頭指針開始查找，找到最后一個元素時方可進(jìn)行入隊(duì)操作。若只設(shè)尾指針，則出入隊(duì)時間均為1。因?yàn)槭茄h(huán)鏈表，尾指針?biāo)傅南乱粋€元素就是頭指針?biāo)冈?，所以出?duì)時不需要遍歷整個隊(duì)列。指出下述程序段的功能是什么？(2)SeqStackS1,S2,tmp;DataTypex;..?//假設(shè)棧tmp和S2已做過初始化while(!StackEmpty(&S1)){x=Pop(&S1);Push(&tmp,x);}while(!StackEmpty(&tmp)){x=Pop(&tmp);Push(&S1,x);Push(&S2,x);}(2)程序段的功能是利用tmp棧將一個非空棧si的所有元素按原樣復(fù)制到一個棧s2當(dāng)中去。3.6利用棧的基本操作，寫一個將棧S中所有結(jié)點(diǎn)均刪去的