數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)題

數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)題數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)題數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)題資料僅供參考文件編號：2022年4月數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)題版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：問答題：1.簡述邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系.答：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。2.在什么情況下使用順序表比鏈表好？答：若線性表的總長度基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要以最快的速度存取線性表中的元素。3.簡述二路歸并排序思想.

答：將兩個有序表合并為一個有序表。1個元素的表總是有序的，所以對n個元素的待排序列，每個元素可看成1個有序子表。對子表兩兩合并生成個子表，所得子表除最后一個子表長度可能為1外，其余子表長度均為2。再進(jìn)行兩兩合并，直到生成n個元素按關(guān)鍵碼有序的表。4.在單鏈表和雙向表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到任一結(jié)點(diǎn)

答：在單鏈表中只能由當(dāng)前結(jié)點(diǎn)訪問其后的任一結(jié)點(diǎn)，因?yàn)闆]有指向其前驅(qū)結(jié)點(diǎn)的指針。而在雙向鏈表中，既有指向后繼結(jié)點(diǎn)的指針又有指向前驅(qū)結(jié)點(diǎn)的指針，故可由當(dāng)前結(jié)點(diǎn)出發(fā)訪問鏈表中任一結(jié)點(diǎn)。5.簡述線性表，棧和隊(duì)列的異同？答：棧和隊(duì)列是操作位置受限的線性表，即對插入和刪除的位置加以限制，棧是僅允許在表的一端進(jìn)行插入和刪除的線性表，因而是后進(jìn)先出表，隊(duì)列是只允許在表的一端進(jìn)行插入，另一端進(jìn)行刪除的線性表，因而是先進(jìn)先出表。6.已知一組元素（46,25,78,62,18,34,12,40,73），試畫出按元素排列順序輸出而生成的二叉排序樹？答：46781834621240737．畫出對長度為10的有序表進(jìn)行二分查找的一棵判斷樹，并求其等概率時查找成功的平均查找長度？答：判斷樹5813694710ASL=（1+2+2+3+3+3+3+4+4+4）/10=2.98.“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義，一是操作為一門課程的名稱，二是作為一個科學(xué)的概念，作為科學(xué)概念，且目前尚無公認(rèn)定義，一般認(rèn)為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個方面，一是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲結(jié)構(gòu)，三是對數(shù)據(jù)進(jìn)行操作（運(yùn)算），而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。9.簡述順序表和鏈表存儲方式的特點(diǎn)

答：順序表可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，因而降低效率；而鏈表內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序表方便，但結(jié)點(diǎn)的插入、刪除操作較簡單。10.為什么說棧是一種后進(jìn)先出表

答：棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數(shù)為零時稱為空棧。插入一般稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進(jìn)先出表（LIFO--LastINFirstOut表）。11.判斷下列序列是否是堆。若不是堆，則把它們依次調(diào)整為堆。(1)(100，85，98，77，80，60，82，40，20，10，66)。(2)(100，98，85，82，80，77，66，60，40，20，10)。(3)(100，85，40，77，80，60，66，98，82，10，20)。(4)(10，20，40，60，66，77，80，82，85，98，100)。答：根據(jù)堆的定義可知堆中元素滿足下面中的某一個式子的關(guān)系，┌≤k2i┌≥k2i①ki或②ki└≤k2i＋1└≥k2i＋1因此(1)、(2)和(4)序列是堆。(3)不是堆。(3)調(diào)整為100,98,66,85,80,60,40,77,82,10,20后成為堆。12.有5個元素,其進(jìn)棧次序?yàn)锳、B、C、D、E,在各種可能的出棧次序中,以元素C、D最先出棧(即C第一個且D第一個出棧)的次序有哪幾個

答：三個：CDEBA，CDBEA，CDBAE13．試述棧的基本性質(zhì)

答：由棧的定義可知，這種結(jié)構(gòu)的基本性質(zhì)綜述如下：(1)集合性。棧是由若干個元素集合而成，當(dāng)沒有元素的空集合稱為空棧；(2)線性結(jié)構(gòu)。除棧底元素和棧頂元素外，棧中任一元素均有唯一的前驅(qū)元素和后繼元素；(3)受限制的運(yùn)算。只允許在棧頂實(shí)施壓入或彈出操作，且棧頂位置由棧指針?biāo)甘荆?4)數(shù)學(xué)性質(zhì)。當(dāng)多個編號元素依某種順序壓入，且可任意時刻彈出時，所獲得的編號元素排列的數(shù)目，恰好滿足卡塔南數(shù)列的計(jì)算，即：Ｃn＝Ｃn2n/(n＋1)其中，n為編號元素的個數(shù)，Cn是可能的排列數(shù)目。14.對鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么

答：(1)對帶頭結(jié)點(diǎn)的鏈表，在表的任何結(jié)點(diǎn)之前插入結(jié)點(diǎn)或刪除表中任何結(jié)點(diǎn)，所要做的都是修改前一結(jié)點(diǎn)的指針域，因?yàn)槿魏卧亟Y(jié)點(diǎn)都有前驅(qū)結(jié)點(diǎn)。若鏈表沒有頭結(jié)點(diǎn)，則首元素結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，在其前插入結(jié)點(diǎn)或刪除該結(jié)點(diǎn)時操作會復(fù)雜些。(2)對帶頭結(jié)點(diǎn)的鏈表，表頭指針是指向頭結(jié)點(diǎn)的非空指針，因此空表與非空表的處理是一樣的。算法題：設(shè)計(jì)一個算法,利用棧的基本運(yùn)算返回指定棧中的棧底元素。答：statusGetbase(Aqstacks,int&e){If(s.top==s.base)Error(‘nodata’)elsee=*s.base;returne;}利用一維數(shù)組A可以對N個整數(shù)進(jìn)行排序，其中一種排序的算法的處理思想是：將N個整數(shù)作為數(shù)組A的N個元素的值，每次（即第一次）從元素A[1]~A[N]中挑出最小的一個元素A[K]（1<=K<=N），然后將A[K]與A[1]換位，這樣反復(fù)N次完成排序，編寫實(shí)現(xiàn)上述算法的函數(shù)？答:SelectSort(sqlist&A){For(i=1;KA.length;++i);{J=selectminkey(A,i);If(i=J)A.R[i]<-->A.R[J];}}//selectsort設(shè)計(jì)一個算法,利用棧的基本運(yùn)算將指定棧中的內(nèi)容進(jìn)行逆轉(zhuǎn)。答：statusNizhuan(sqstacks,inta,intb,intt){If(s.top==s.base)error(‘nodata’);for(i=0;i<s.stacksize/2;i++){a=*--top;b=*s.base;t=b;b=a;a=t;s.base++;}}在棧項(xiàng)指針為HS的鏈棧中，編寫算法計(jì)算該鏈棧中結(jié)點(diǎn)個數(shù)？答：statussum(linkedstackHS.elemtypeN){IntN=0;While(HS!=NULL);{N++;HS=HS->next;}Return(N);}修改直接選擇排序,每趟從無序區(qū)中選擇最大元素與當(dāng)前元素進(jìn)行交換.

答：selectSort(SqList&A){for(i=1;i<A.length;++i){j=SelectMaxkey(A,i);if(i!=j)A.r[i]<-->A.r[j];}}//SelectSort用不帶頭結(jié)點(diǎn)的單鏈表存儲鏈棧,設(shè)計(jì)進(jìn)棧和出棧的算法。答：（1）入棧操作【單個鏈棧的入棧操作】intpushLstack(slStacktype*top,Elemtypex){//將元素x壓入鏈棧top中slStacktype*p;if((p=(slStacktype*)malloc(sizeof(slStacktype)))==NULL)returnFALSE;//申請一個結(jié)點(diǎn)p->data=x;p->next=top;to