專業(yè)課數(shù)據(jù)結(jié)構(gòu)考研知識點(diǎn)總結(jié)

[專業(yè)課]數(shù)據(jù)結(jié)構(gòu)考研知識點(diǎn)總結(jié)數(shù)據(jù)結(jié)構(gòu)考研真題及知識點(diǎn)解析考察目標(biāo)1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。2.掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度與空間復(fù)雜度的分析。3.能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)的基本原理和方法進(jìn)行問題的分析與求解;具備采用C、C++或Java語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。第2章線性表一、考研知識點(diǎn)(一)線性表的定義和基本操作(二)線性表的實(shí)現(xiàn)1.順序存儲(chǔ)2.鏈?zhǔn)酱鎯?chǔ)3.線性表的應(yīng)用二、考查重點(diǎn)1(線性結(jié)構(gòu)的特點(diǎn);2(線性表在順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)方式下的基本操作及其應(yīng)用;3(線性表的順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)情況下，其不同和優(yōu)缺點(diǎn)比較，及其各自適用的場合。單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針的各自好處;4(能分析所寫算法的時(shí)間和空間復(fù)雜度。分析:線性表是一種最簡單的數(shù)據(jù)結(jié)構(gòu)，在線性表方面，主要考查線性表的定義和基本操作、線性表的實(shí)現(xiàn)。在線性表實(shí)現(xiàn)方面，要掌握的是線性表的存儲(chǔ)結(jié)構(gòu)，包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，特別是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是考查的重點(diǎn)。另外，還要掌握線性表的基本應(yīng)用。線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中，其作用都是不可低估的。線性表一章小的知識點(diǎn)比較少，一般會(huì)出一個(gè)綜合題，并且容易和第三章、第九章和第十章的內(nèi)容結(jié)合來考，注意對基本知識的理解，能夠利用書上的理論解決具體問題。學(xué)習(xí)過程中要注意多積累，多看、多寫一些相關(guān)算法。三、考研真題(一)選擇題近幾年第2章沒有考選擇題，只有兩個(gè)計(jì)算時(shí)間復(fù)雜度的題目，因?yàn)榇苏轮饕蔷€性表的操作，而且又是這門課的一個(gè)基礎(chǔ)，考綜合題的可能性比較大，可以和第3章、第9章和第10章的內(nèi)容結(jié)合來出題。1((11年)設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是(A)。x=2;while(x<n/2)x=2*x;2A.O(logn)B.O(n)C.O(nlogn)D.O(n)2.(12年)求整數(shù)n(n>=0)的階乘的算法如下，其時(shí)間復(fù)雜度是(B)。intfact(intn){if(n<=1)return1;returnn*fact(n-1);}2A.o(logn)B.O(n)C.O(nlogn)D.O(n)22分析:考查的是算法時(shí)間復(fù)雜度的計(jì)算。可以放在第二章，實(shí)際這內(nèi)容貫穿每一章內(nèi)容中算法的度量。(二)綜合題1.(09年)已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表結(jié)點(diǎn)結(jié)構(gòu)為(data,link)，假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)(k為正整數(shù))。若查找成功，算法輸出該結(jié)點(diǎn)的data值，并返回1;否則，只返回0。要求:(1)描述算法的基本設(shè)計(jì)思想;(2)描述算法的詳細(xì)實(shí)現(xiàn)步驟;(3)根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語言描述算法(使用C或C++或JAVA語，關(guān)鍵之處給出簡要注釋。言實(shí)現(xiàn))分析:此題考查線性表的鏈?zhǔn)酱鎯?chǔ)，主要是線性表的基本操作的應(yīng)用。做此題時(shí)要把握算法的效率。(1)算法基本思想如下:從頭到尾遍歷單鏈表，并用指針p指向當(dāng)前結(jié)點(diǎn)的前k個(gè)結(jié)點(diǎn)。當(dāng)遍歷到鏈表的最后一個(gè)結(jié)點(diǎn)時(shí)，指針p所指向的結(jié)點(diǎn)即為所查找的結(jié)點(diǎn)。(2)詳細(xì)實(shí)現(xiàn)步驟:增加兩個(gè)指針變量和一個(gè)整型變量，從鏈表頭向后遍歷，其中指針p1指向當(dāng)前遍歷的結(jié)點(diǎn)，指針p指向p1所指向結(jié)點(diǎn)的前k個(gè)結(jié)點(diǎn)，如果p1之前沒有k個(gè)結(jié)點(diǎn)，那么p指向表頭結(jié)點(diǎn)。用整型變量i表示當(dāng)前遍歷了多少結(jié)點(diǎn)，當(dāng)i>k時(shí)，指針p隨著每次遍歷，也向前移動(dòng)一個(gè)結(jié)點(diǎn)。當(dāng)遍歷完成時(shí)，p或者指向表頭結(jié)點(diǎn)，或者指向鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)。(3)算法描述:ntlocate(Linklistlist,intk)i{p1=list->link;p=list;i=1;while(p1){p1=p1->link;i++;if(i>k)p=p->next;//如果i>k，則p也后移}if(p==list)return0;//鏈表沒有k個(gè)結(jié)點(diǎn)else{printf(“%\n”,p->data);return1;}}2.(10年)設(shè)將n(n,1)個(gè)整數(shù)存放到一維數(shù)組R中，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P(0，P，n)個(gè)位置，即將R中的數(shù)據(jù)由(X0X1??Xn-1)變換為(XpXp+1??Xn-1X0X1??Xp-1)要求:(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語言表述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析:此題考查的是數(shù)組的操作，線性表的順序存儲(chǔ)的核心就是數(shù)組，因此此題實(shí)質(zhì)上是考查的線性表的順序存儲(chǔ)的操作及其應(yīng)用。做此題時(shí)要考慮算法的時(shí)間和空間復(fù)雜度。解法一:(1)算法的基本設(shè)計(jì)思想:可以將這個(gè)問題看做是把數(shù)組ab轉(zhuǎn)化成數(shù)組ba(a代表數(shù)-1組的前p個(gè)元素，b代表數(shù)組中余下的n-p個(gè)元素)，先將a逆置得到ab，再將b逆置得-1-1-1-1-1-1-1到ab，最后將整個(gè)ab逆置得到(ab)=ba。設(shè)reverse函數(shù)執(zhí)行將數(shù)組元素逆置的操作，對abcdefgh向左循環(huán)移動(dòng)3(p=3)個(gè)位置的過程如下:reverse(0,p-1)得到cbadefgh;reverse(p,n-1)得到cbahgfde;reverse(0,n-1)得到defghabc。注:reverse中，兩個(gè)參數(shù)分別表示數(shù)組中待轉(zhuǎn)換元素的始末位置。(2)算法描述:voidreverse(intR[],intlow,inthigh){//將數(shù)組中從low到high的元素逆置inttemp;for(i=0;i<=(high-low)/2;i++){temp=R[low+i];R[l0ow+i]=R[high-i];R[high-i]=temp;}}voidconverse(intR[],intn,intp){reverse(R,0,p-1);reverse(R,p,n-1);reverse(R,0,n-1);}(3)上述算法中三個(gè)reverse函數(shù)的時(shí)間復(fù)雜度分別是O(p/2)、O((n-p)/2)、O(n/2)，故所設(shè)計(jì)算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。解法二:算法思想:創(chuàng)建大小為p的輔助數(shù)組S，將R中前p個(gè)整數(shù)依次暫存在S中，同時(shí)將R中后n-p個(gè)整數(shù)左移，然后將S中暫存的p個(gè)數(shù)依次放回到R中的后續(xù)單元。時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(p)。3.(11年)一個(gè)長度為L(L>=1)的生序列S，處在第?L/2?個(gè)位置的數(shù)稱為S的中位數(shù)，例如，若序列S1=(11,13,15,17,19)，則S1的中位數(shù)是15，兩個(gè)序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，若S2=(2,4,6,8,20)，則S1和S2的中位數(shù)是11?，F(xiàn)在有兩個(gè)等長升序序列A和B，試設(shè)計(jì)一個(gè)在時(shí)間和空間方面都盡可能高效的算法，找出兩個(gè)序列A和B的中位數(shù)。要求:(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語言描述算法，關(guān)鍵之處給出注釋。分析:此題考查線性表的順序存儲(chǔ)，主要是線性表的基本操作的應(yīng)用。做此題時(shí)要把握算法的效率。(1)算法的基本設(shè)計(jì)思想如下:分別求出序列A和B的中位數(shù)，設(shè)為a和b，求序列A和B的中位數(shù)過程如下:1)若a=b，則a或b即為所求中位數(shù)，算法結(jié)束;2)若a<b，則舍棄序列A中較小的一半，同時(shí)舍棄序列B中較大的一半，要求舍棄的長度相等;3)若a>b，則舍棄序列A中較大的一半，同時(shí)舍棄序列B中較小的一半，要求舍棄的長度相等;在保留的兩個(gè)升序序列中，重復(fù)過程1)-3)，直到兩個(gè)序列中只含一個(gè)元素時(shí)為止，較小者即為所求的中位數(shù)。(2)算法實(shí)現(xiàn)如下:intM_search(intA[],intB[].intn){ints1=0,d1=n-1,m1,s2=0,d2=n-1,m2;//分別表示序列A和B的首位數(shù)、末尾數(shù)和中位數(shù)While(s1!=d1||s2!=d2){m1=(s1+d1)/2;m2=(s2+d2)/2;if(A[m1]==B[m2])returnA[m1];elseif(A[m1<B[m2])if(s1+d1)%2==0{s1=m1;d2=m2;}else{s1=m1+1;d2=m2;}elseif(s1+d1)%2==0{d1=m1;s2=m2;}else{d1=m1+1;s2=m2;}}returnA[s1]<B[s2]?A[s1]:B[s2];}(3)算法的時(shí)間復(fù)雜度為O(logn)，空間復(fù)雜度為O(1)。4.(12年)假定采用帶頭結(jié)點(diǎn)的單鏈表，如果有共同后綴，長度分別為len1和len2(這個(gè)條件是我查了一些資料后加上的，網(wǎng)上給的資料這個(gè)題目不完整)，則可共享相同的后綴存儲(chǔ)空間，例如，“l(fā)oading”和“Beijing”，如下圖所示。設(shè)str1和str2分別指向兩個(gè)單詞所在單鏈表的頭結(jié)點(diǎn)，鏈表結(jié)點(diǎn)結(jié)構(gòu)為(data，next)，請?jiān)O(shè)計(jì)一個(gè)時(shí)間上盡可能高效的算法，找出由str1和str2所指向兩個(gè)鏈表共同后綴的起始位置(如圖中字符i所在結(jié)點(diǎn)的位置p)。要求:(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度。分析:兩個(gè)單鏈表有公共結(jié)點(diǎn)，則從公共結(jié)點(diǎn)開始，它們的next都指向同一個(gè)結(jié)點(diǎn)。由于每個(gè)單鏈表結(jié)點(diǎn)只有一個(gè)next域，因此，從第一個(gè)公共結(jié)點(diǎn)開始，之后它們所有的結(jié)點(diǎn)都是重合的，不可能再出現(xiàn)分叉。因此，我們判斷兩個(gè)鏈表是不是有重合的部分，只要分別遍歷兩個(gè)鏈表到最后一個(gè)結(jié)點(diǎn)。如果兩個(gè)尾結(jié)點(diǎn)是一樣的，說明它們有公共結(jié)點(diǎn);否則兩個(gè)鏈表沒有公共的結(jié)點(diǎn)。因?yàn)閮蓚€(gè)鏈表長度不一定一樣，在順序遍歷兩個(gè)鏈表到尾結(jié)點(diǎn)時(shí)，并不能保證在兩個(gè)鏈表上同時(shí)到達(dá)尾結(jié)點(diǎn)。假設(shè)一個(gè)鏈表比另一個(gè)長k個(gè)結(jié)點(diǎn)，我們先在長的鏈表上遍歷k個(gè)結(jié)點(diǎn)，之后再同步遍歷，此時(shí)能夠保證同時(shí)到達(dá)最后一個(gè)結(jié)點(diǎn)。在遍歷中，第一個(gè)相同的結(jié)點(diǎn)就是第一個(gè)公共結(jié)點(diǎn)。(1)算法思想:根據(jù)兩個(gè)單鏈表的長度，求出它們的長度之差;在長的單鏈表上先遍歷長度之差個(gè)結(jié)點(diǎn);同步遍歷兩個(gè)單鏈表，直接找到相同的結(jié)點(diǎn)，若有相同結(jié)點(diǎn)返回該節(jié)點(diǎn)，若沒有則一直到鏈表結(jié)束。(2)算法實(shí)現(xiàn):LinkListsearch(LinkListstr1，LinkListstr2，intlen1，int2){if(len1>len2){long=str1->next;short=str2->next;k=len1-len2;}else{long=str2->next;short=str1->next;k=len2-len1;}while(k){long=long->next;k--;}while(long){if(long==short)returnlong;else{long=long->next;short=short->next;}}returnNULL;}(3)由于每個(gè)表僅遍歷一遍，因此算法時(shí)間復(fù)雜度為O(len1+len2)，空間復(fù)雜度為O(1)。四、練習(xí)題(一)選擇題1(下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn),(A)A(存儲(chǔ)密度大B(插入運(yùn)算方便C(刪除運(yùn)算方便D(可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示2(下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè),(B)A(線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B(線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C(線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D(線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。3(線性表是具有n個(gè)(C)的有限序列(n>0)。A(表元素B(字符C(數(shù)據(jù)元素D(數(shù)據(jù)項(xiàng)E(信息項(xiàng)4(若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用(A)存儲(chǔ)方式最節(jié)省時(shí)間。A(順序表B(雙鏈表C(帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D(單循環(huán)鏈表5(某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用(D)存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A(單鏈表B(僅有頭指針的單循環(huán)鏈表C(雙鏈表D(僅有尾指針的單循環(huán)鏈表6(若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為(C)(1<=i<=n+1)。2A.O(0)B.O(1)C.O(n)D.O(n)7.對于順序存儲(chǔ)的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為(C)。A(O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)8(線性表(a1,a2,?,an)以鏈接方式存儲(chǔ)時(shí)，訪問第i位置元素的時(shí)間復(fù)雜性為(C)。A(O(i)B(O(1)C(O(n)D(O(i-1)(二)綜合題1(掌握線性表中幾個(gè)最基本的操作算法(1)鏈表的建立頭插法建表voidreatelistf(linklist&head，intn){//逆序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表linklistp;head=(linklist)malloc(sizeof(LNode));head->next=NULL;for(i=n;i>0;i--){p=(linklist)malloc(sizeof(LNode));Scanf(“%d”,&p->data);p–>next=head->next;head->next=p;}}尾插法建表voidcreater(linklist&head){charch;linklistp,r;head->next=NULL;r=head;while((ch=getchar()!=‘’){p=(linklist)malloc(sizeof(LNode));p->data=ch;p->next=r->next;r–>next=p;r=p;}}(2)逆置操作順序表的就地逆置voidreverse(SqList&A){for(i=1,j=A.length;i<j;i++,j--)A.elem[i]<->A.elem[j];//元素交換}鏈表的就地逆置voidLinkList_reverse(Linklist&L){p=L->next;q=p->next;while(q){r=q->next;q->next=p;p=q;q=r;}L->next->next=NULL;//修改第一個(gè)元素的指針值L->next=p;//修改表頭結(jié)點(diǎn)指針值}(3)線性表的合并順序表的合并:順序存儲(chǔ)的線性表la，lb的關(guān)鍵字為整數(shù)，元素非遞減有序，線性表空間足夠大，試編寫高效算法，將lb中元素合并到la中，使新的la的元素仍非遞減有序。分析:從后往前插入，避免移動(dòng)元素voidunion(Sqlistla,Sqlistlb){m=la.length;n=lb.length;k=m+n;i=m;j=n;//循環(huán)指針賦值，從后往前比較while(i>0&&j>0){if(la.elem[i]>=lb.elem[j]){la.elem[k]=la.elem[i];k--;i--;}else{la.elem[k]=lb.elem[j];k--;j--;}}if(j>0)//判斷l(xiāng)b是否為空{(diào)la.elem[k]=lb.elem[j];k--;j--;}la.length=m+n;}鏈表的合并:把元素遞增排列的鏈表A和B合并為C，且C中元素遞減排列，使用原結(jié)點(diǎn)空間。分析:本算法的思想是，按從小到大的順序依次把A和B的元素插入新表的頭部pc處，因?yàn)楹喜⒁院笫悄嫘?，因此采用頭插法，最后處理A或B的剩余元素。LinkListUnion(LinkListA,LinkListB,LinkListC){pa=A->next;pb=B->next;C=A;A->next=null;while(pa!=null&&pb!=null)if(pa->data<=pb->data){r=pa->next;pa->next=C->next;C->next=pa;pa=r;}else{r=pb->next;pb->next=C->next;C->next=pb;pb=r;while(pa!=null){r=pa->next;pa->next=C->next;C->next=pa;pa=r;}while(pb!=null){r=pb->next;pb->next=C->next;C->next=pb;pb=r;}returnC;}(4)鏈表的拆分:設(shè)L為一單鏈表的頭指針，單鏈表的每個(gè)結(jié)點(diǎn)由一個(gè)整數(shù)域data和指針域next組成，整數(shù)在單鏈表中是無序的。設(shè)計(jì)算法，將鏈表中結(jié)點(diǎn)分成一個(gè)奇數(shù)鏈和一個(gè)偶數(shù)鏈，算法中不得申請新的結(jié)點(diǎn)空間。分析:利用原鏈表空間，在原鏈表的分解過程中新建鏈表。voiddiscreat(linklistL){s=L->next;p=L;p->next=NULL;q->next=NULL;while(s!=NULL){r=s->next;if(s->data%2!=0)//奇數(shù)鏈鏈接{s->next=p->next;p->next=s;}else//偶數(shù)鏈鏈接{s->next=q->next;q->next=s;}s=r;}}2(算法練習(xí)(1)試編寫在帶頭結(jié)點(diǎn)的單鏈表中刪除最小值結(jié)點(diǎn)的高效算法。voiddelete(linklistL){p=L->next;pre=L;q=p;while(p->next!=NULL)//找最小值元素，pre指向最小值的前驅(qū){if(p->next->data<q->data){pre=p;q=p->next;}p=p->next;}pre->next=q->next;free(q);}分析:此算法的高效在于在循環(huán)過程中利用最小值結(jié)點(diǎn)的前驅(qū)指針進(jìn)行比較，比較結(jié)束后直接保留了最小值結(jié)點(diǎn)的前驅(qū)，方便進(jìn)行刪除操作。(2)設(shè)單鏈表的表頭指針為h，結(jié)點(diǎn)結(jié)構(gòu)由data和next兩個(gè)域構(gòu)成，其中data域?yàn)樽址?。寫出算法dc(h,n),判斷該鏈表的前n個(gè)字符是否中心對稱。例如xyx,xyyx都是中心對稱。分析:判斷鏈表中數(shù)據(jù)是否中心對稱，通常使用棧。將鏈表的前一半元素依次進(jìn)棧。在處理鏈表的后一半元素時(shí)，當(dāng)訪問到鏈表的一個(gè)元素后，就從棧中彈出一個(gè)元素，兩元素比較，若相等，則將鏈表中下一元素與棧中再彈出元素比較，直至鏈表到尾。這時(shí)若棧是空棧，則得出鏈表中心對稱的結(jié)論;否則，當(dāng)鏈表中一元素與棧中彈出元素不等時(shí)，結(jié)論為鏈表非中心對稱，結(jié)束算法的執(zhí)行。intdc(Linklisth,intn){?h是帶頭結(jié)點(diǎn)的n個(gè)元素單鏈表，鏈表中結(jié)點(diǎn)的數(shù)據(jù)域是字符。chars[];inti=1;?i記結(jié)點(diǎn)個(gè)數(shù)，s字符棧p=h->next;?p是鏈表的工作指針，指向待處理的當(dāng)前元素。for(i=1;i<=n/2;i++)?鏈表前一半元素進(jìn)棧。{s[i]=p->data;p=p->next;}i--;?恢復(fù)最后的i值if(n%2==1)p=p->next;?若n是奇數(shù)，后移過中心結(jié)點(diǎn)。while(p!=null&&s[i]==p->data){i--;p=p->next;}?測試是否中心對稱。if(p==null)return1;?鏈表中心對稱elsereturn0;?鏈表不中心對稱}?算法結(jié)束。(3)已知兩個(gè)單鏈表A和B,其頭指針分別為heada和headb，編寫一個(gè)過程從單鏈表A中刪除自第i個(gè)元素起的共len個(gè)元素，然后將單鏈表A插入到單鏈表B的第j個(gè)元素之前。分析:在單鏈表中刪除自第i個(gè)元素起的共len個(gè)元素，應(yīng)從第1個(gè)元素起開始計(jì)數(shù)，記到第i個(gè)時(shí)開始數(shù)len個(gè)，然后將第i-1個(gè)元素的后繼指針指向第i+len個(gè)結(jié)點(diǎn)，實(shí)現(xiàn)了在A鏈表中刪除自第i個(gè)起的len個(gè)結(jié)點(diǎn)。這時(shí)應(yīng)繼續(xù)查到A的尾結(jié)點(diǎn)，得到刪除元素后的A鏈表。再查B鏈表的第j個(gè)元素，將A鏈表插入之。插入和刪除中應(yīng)注意前驅(qū)后繼關(guān)系，不能使鏈表“斷鏈”。另外，算法中應(yīng)判斷i，len和j的合法性。LinklistDelInsert(Linklistheada,Linklistheadb,inti,j,len){?heada和headb均是帶頭結(jié)點(diǎn)的單鏈表。if(i<1||len<1||j<1){printf(“參數(shù)錯(cuò)誤\n”);exit(0);}?參數(shù)錯(cuò)，退出算法。p=heada;?p為鏈表A的工作指針，初始化為A的頭指針k=0;?計(jì)數(shù)while(p!=null&&k<i-1)?查找第i個(gè)結(jié)點(diǎn)。{k++;p=p->next;}if(p==null){printf(“給的%d太大\n”,i);exit(0);}?i太大，退出算法q=p->next;?q為工作指針，初始指向A鏈表第一個(gè)被刪結(jié)點(diǎn)。k=0;while(q!=null&&k<len){k++;u=q，q=q->next;free(u);}?刪除結(jié)點(diǎn)，后移指針。if(k<len){printf(“給的%d太大\n”,len);exit(0);}p->next=q;?A鏈表刪除了len個(gè)元素。if(heada->next!=null)?heada->next=null說明鏈表中結(jié)點(diǎn)均已刪除，無需往B表插入{while(p->next!=null)p=p->next;?找A的尾結(jié)點(diǎn)。q=headb;?q為鏈表B的工作指針。k=0;?計(jì)數(shù)while(q!=null&&k<j-1)?查找第j個(gè)結(jié)點(diǎn)。{k++;q=q->next;}?查找成功時(shí)，q指向第j-1個(gè)結(jié)點(diǎn)if(q==null){printf(“給的%d太大\n”,j);exit(0);}p->next=q->next;?將A鏈表鏈入q->next=heada->next;?A的第一元素結(jié)點(diǎn)鏈在B的第j-1個(gè)結(jié)點(diǎn)之后}//iffree(heada);?釋放A表頭結(jié)點(diǎn)。}(4)按1，3，5，...4，2的順序重排雙向循環(huán)鏈表L中的所有結(jié)點(diǎn)。分析:next鏈和pre鏈的調(diào)整分開進(jìn)行。從前往后調(diào)整奇數(shù)鏈，然后從后往前調(diào)整偶數(shù)鏈，最后修改pre指針。voidReform(DuLinkList&L){p=L->next;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;}//從前往后調(diào)整奇數(shù)鏈if(p->next==L)p->next=L->pre->pre;elsep->next=L->pre;//根據(jù)鏈表中元素個(gè)數(shù)是奇數(shù)還是偶數(shù)處理表尾結(jié)點(diǎn)p=p->next;while(p->pre->pre!=L){p->next=p->pre->pre;p=p->next;}//從后往前調(diào)整偶數(shù)鏈p->next=L;for(p=L;p->next!=L;p=p->next)p->next->pre=p;//重新修改前驅(qū)指針L->pre=p;}第3章棧和隊(duì)列一、考研知識點(diǎn)(一)棧和隊(duì)列的基本概念(二)棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)(三)棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(四)棧和隊(duì)列的應(yīng)用二、考查重點(diǎn)1(棧和隊(duì)列的特點(diǎn)，及其應(yīng)用;2(棧的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的入棧和出棧操作，以及判斷棧的空和滿的條件;3(隊(duì)列的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的入隊(duì)和出隊(duì)操作，以及判斷隊(duì)列空和滿的條件;4(理解棧與遞歸的關(guān)系，利于對以后章節(jié)(樹和圖)的學(xué)習(xí)和復(fù)習(xí)。分析:棧和隊(duì)列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊(duì)列的基本概念，以及他們之間的區(qū)別。對于棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)(包括順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))要有較深的理解，對于棧和隊(duì)列的應(yīng)用，例如，排隊(duì)問題、子程序調(diào)用問題、表達(dá)式問題等，要搞清楚。此章內(nèi)容是線性表的深化，如果線性表理解的好，這一章就比較容易。這一章小的知識點(diǎn)比較多，一般容易出選擇題，從09-12年的考研真題來看，主要是考查棧和隊(duì)列的特點(diǎn)及其應(yīng)用、棧的入棧出棧操作和隊(duì)列的入隊(duì)出隊(duì)操作、判斷棧和隊(duì)列的空與滿的條件。一般不會(huì)單獨(dú)出綜合題，如果出綜合題會(huì)將棧和隊(duì)列作為其他結(jié)構(gòu)中一個(gè)小環(huán)節(jié)出題，比如和線性表結(jié)合，作為實(shí)現(xiàn)遞歸的工具和二叉樹結(jié)合等。三、考研真題(一)選擇題1.(09年)為解決計(jì)算機(jī)和打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是()。A.棧B.隊(duì)列C.樹D.圖分析:答案是B，此題可以認(rèn)為考查隊(duì)列的特點(diǎn)，也可以看做是考查四種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)。2.(09年)設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)順序是bdcfeag，則棧S的容量至少是()。A.1B.2C.3D.4分析:答案是C，此題考查棧的入棧和出棧操作和隊(duì)列的入隊(duì)和出隊(duì)操作。3.(10年)若元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是()。A.dcebfaB.cbdaefC.dbcaefD.afedcb分析:答案是D，此題考查棧的入棧和出棧操作，但題目出的不是太嚴(yán)謹(jǐn)，嚴(yán)格說應(yīng)該是CD兩個(gè)答案。4.(10年)某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，則不可能得到的順序是(C)A.bacdeB.dbaceC.dbcaeD.ecbad分析:答案是C，此題考查隊(duì)列的入隊(duì)和出隊(duì)操作。5((11年)元素a，b，c，d，e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可進(jìn)棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是A.3B.4C.5D.6分析:答案是B，出棧序列必為d_c_b_a.e的順序不定，在任意一個(gè)“_”上都有可能。6((11年)已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A[0..n-1]中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A[0]處，則初始時(shí)front和rear的值分別是A.0,0B.0，n-1C.n-1,0D.n-1,n-1分析:答案是B，插入元素時(shí)，front不變，rear+1，而插入第一個(gè)元素之后，隊(duì)尾要指向尾元素，顯然，rear初始應(yīng)該為n-1，front為07.(12年)已知操作符包括’+’、’-’、’*’、’/’、’(’和’)’。將中綴表達(dá)式a+b-a*((c+d)/e-f)+g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式ab+acd+e/f-*-g+時(shí)，用棧來存放暫時(shí)還不能確定運(yùn)算次序的操作符，若棧初始為空，則轉(zhuǎn)換過程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是()。A.5B.7C.8D.11分析:答案是A，此題考查棧的應(yīng)用，將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，轉(zhuǎn)化過程中利用兩個(gè)棧分別存放操作符和轉(zhuǎn)化后的表達(dá)式，要明確兩個(gè)棧中元素的進(jìn)出情況。(二)綜合題10年考研綜合題的第二題如果用解法二，可以認(rèn)為考查了隊(duì)列的基本操作，因?yàn)闂：完?duì)列本身是線性結(jié)構(gòu)，所以考試時(shí)可以綜合來考，和第2章的內(nèi)容沒有太明顯的界限。四、練習(xí)題(一)選擇題1.一個(gè)棧的輸入序列為123?n，若輸出序列的第一個(gè)元素是n，輸出第i(1<=i<=n)個(gè)元素是(B)。A.不確定B.n-i+1C.iD.n-i2.若一個(gè)棧的輸入序列為1,2,3,?,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是(D)。A.i-j-1B.i-jC.j-i+1D.不確定的3.輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過的棧操作為(B)。A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop4.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為(D)。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)5.若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為(B),A.1和5B.2和4C.4和2D.5和1(二)綜合題這一章一般不會(huì)單獨(dú)出綜合題，和其他章節(jié)的結(jié)合在相關(guān)章節(jié)中有例題體現(xiàn)。第5章數(shù)組和廣義表一、考研知識點(diǎn)特殊矩陣的壓縮存儲(chǔ)二、考查重點(diǎn)一維數(shù)組屬于線性表范疇，但多維數(shù)組不屬于線性表。在這方面，主要掌握數(shù)組的存儲(chǔ)結(jié)構(gòu)，例如按行優(yōu)先、按列優(yōu)先等，某個(gè)元素存在的地址是什么。對于特殊矩陣(二維數(shù)組)的壓縮存儲(chǔ)原理也要搞清楚。重點(diǎn)考查特殊矩陣的壓縮存儲(chǔ)中矩陣中元素在存儲(chǔ)空間中地址的計(jì)算，只要掌握計(jì)算的方法就行，計(jì)算時(shí)需要特別注意矩陣首元素的下標(biāo)值以及存儲(chǔ)空間首元素的下標(biāo)值。三、考研真題近幾年此知識點(diǎn)沒有出題。四、練習(xí)題1.設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為(B)。A.13B.33C.18D.402.設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5，8]的存儲(chǔ)首地址為(B)。A.BA+141B.BA+180C.BA+222D.BA+2253.假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100，1..100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC[5，5]=(B)。A.808B.818C.1010D.10204.將一個(gè)A[1..100，1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，A中元素A6665(即該元素下標(biāo)i=66，j=65)，在B數(shù)組中的位置K為(B)。A.198B.195C.197D.1965.二維數(shù)組A的元素都是6個(gè)字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圈從1到10。從供選擇的答案中選出應(yīng)填入下列關(guān)于數(shù)組存儲(chǔ)敘述中()內(nèi)的正確答案。(1)存放A至少需要(E)個(gè)字節(jié);(2)A的第8列和第5行共占(A)個(gè)字節(jié);(3)若A按行存放，元素A[8，5]的起始地址與A按列存放時(shí)的元素(B)的起始地址一致。(1)A.90B.180C.240D.270E.540(2)A.108B.114C.54D.60E.150(3)A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]6.設(shè)A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數(shù)組B[1..n(n+1)/2]中，對上述任一元素aij(1?i，j?n，且i?j)在B中的位置為(B)。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-1第6章樹和二叉樹一、考研知識點(diǎn)(一)樹的基本概念(二)二叉樹1.二叉樹的定義及其主要特征2.二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3.二叉樹的遍歷4.線索二叉樹的基本概念和構(gòu)造(三)樹、森林1.樹的存儲(chǔ)結(jié)構(gòu)2.森林與二叉樹的轉(zhuǎn)換3.樹和森林的遍歷(四)樹與二叉樹的應(yīng)用哈夫曼(Huffman)樹和哈夫曼編碼二、考查重點(diǎn)1(二叉樹的定義與特點(diǎn);2(二叉樹的性質(zhì)及應(yīng)用;3(二叉樹的遍歷(遍歷過程及算法實(shí)現(xiàn));4(線索二叉樹的構(gòu)造;5(樹的存儲(chǔ)及樹與二叉樹的轉(zhuǎn)換;6(哈夫曼樹構(gòu)造和哈夫曼編碼。分析:二叉樹和樹是兩種不同的概念，這一點(diǎn)是必須要搞清楚的。在這個(gè)部分，我們要掌握樹的定義、二叉樹的定義及主要特征(特殊的二叉樹、二叉樹的性質(zhì))。在二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)方面，特別是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)楹芏鄳?yīng)用都是建立在鏈?zhǔn)酱鎯?chǔ)基礎(chǔ)上，例如，二叉樹的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應(yīng)用。在特殊的二叉樹中，完全二叉樹的概念是必須要搞清楚的，其次，線索二叉樹的基本概念和構(gòu)造。多棵獨(dú)立的樹就組成了森林，樹的存儲(chǔ)結(jié)構(gòu)和遍歷、森林的遍歷、樹和二叉樹的轉(zhuǎn)換、森林和二叉樹的轉(zhuǎn)換等知識，也要了解。最后就是樹的應(yīng)用，通常會(huì)作為綜合應(yīng)用類試題出現(xiàn)，包括等價(jià)類問題、哈夫曼(Huffman)樹和哈夫曼編碼等。此章知識點(diǎn)比較多，并且每個(gè)知識點(diǎn)都可能出題，因此要做到對每一個(gè)知識點(diǎn)的理解和掌握，選擇題和綜合題都可以出，綜合題一般會(huì)現(xiàn)在二叉樹的遍歷及其應(yīng)用、樹與二叉樹的轉(zhuǎn)換和哈夫曼樹的構(gòu)造及哈夫曼編碼。三、考研真題(一)選擇題1.(09年)給定二叉樹如圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3,7,5,6,1,2,4，則其遍歷方式是()。A.LRNB.NRLC.RLND.RNL分析:答案是D，此題考查二叉樹的遍歷。2.(09年)已知一棵完全二叉樹的第6層(設(shè)根為第1層)有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是()。A.39B.52C.111D.119分析:答案是C，此題考察二叉樹的性質(zhì)2以及完全二叉樹的概念。3.(09年)將森林轉(zhuǎn)換為對應(yīng)的二叉樹，若在二叉樹中，結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森林中，u和v可能具有的關(guān)系是()。I.父子關(guān)系II.兄弟關(guān)系III.u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系A(chǔ).只有IIB.I和IIC.I和IIID.I、II和III分析:答案是B，此題考查樹與二叉樹的轉(zhuǎn)換，因?yàn)閡是v的父結(jié)點(diǎn)，若v是u的左子樹，則u與v是父子關(guān)系，若v是u的右子樹，則u與v是兄弟關(guān)系。4.(10年)下列線索二叉樹中(用虛線表示線索)，符合后序線索樹定義的是()。分析:答案是D，此題考查二叉樹的線索化。5.(10年)在一棵度為4的樹T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹T的葉節(jié)點(diǎn)個(gè)數(shù)是()。A.41B.82C.113D.122分析:答案是B，此題考查二叉樹的性質(zhì)，利用二叉樹的性質(zhì)3的證明思路進(jìn)行求解。6.(10年)對n(n大于等于2)個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的是()。A.該樹一定是一棵完全二叉樹B.樹中一定沒有度為1的結(jié)點(diǎn)C.樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D.樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值分析:答案是A，此題考查哈夫曼樹的構(gòu)造，以及哈夫曼樹的特點(diǎn)。7((11年)若一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，則該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)是()。A.257B.258C.384D.385分析:答案是C，考查二叉樹的性質(zhì)，葉結(jié)點(diǎn)個(gè)數(shù)為你n則度為2的結(jié)點(diǎn)個(gè)數(shù)為n-1，總結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)，則度為1的結(jié)點(diǎn)個(gè)數(shù)為1，因此2n=768。8((11年)若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1，則該二叉樹的中序遍歷序列不會(huì)是()。A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1分析:答案是C，考查二叉樹的遍歷。此題可以用畫圖的方式進(jìn)行判斷。9((11年)已知一棵有2011個(gè)結(jié)點(diǎn)的樹，其葉結(jié)點(diǎn)個(gè)數(shù)116，該樹對應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)個(gè)數(shù)是()。A.115B.116C.1895D.1896分析:答案是D，此題考查二叉樹和樹的轉(zhuǎn)換?？紤]一種特殊的情況，設(shè)題意中的樹是如下圖所示的結(jié)構(gòu)，則對應(yīng)的二叉樹中僅有前115個(gè)葉結(jié)點(diǎn)有右孩子。10.(年)若一棵二叉樹的前序遍歷序列為a,e,b,d,c，后序遍歷序列為b,c,d,e,a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)()。A.只有eB.有e、bC.有e、cD.無法確定分析:答案為A。此題考查二叉樹的遍歷，根據(jù)我們的常識，由前序序列和后序序列不能確定二叉樹，但此題并不是確定二叉樹而是確定二叉樹的根結(jié)點(diǎn)的孩子結(jié)點(diǎn)，因?yàn)楦Y(jié)點(diǎn)可以確定，仔細(xì)分析前序和后序序列，可以判斷出孩子結(jié)點(diǎn)只有e，因此答案為A。(二)綜合題1.(12年)設(shè)有6個(gè)有序表A、B、C、D、E、F，分別含有10、35、40、50、60和200個(gè)數(shù)據(jù)元素，各表中元素按升序排列。要求通過5次兩兩合并，將6個(gè)表最終合并成一個(gè)升序表，并在最壞情況下比較的總次數(shù)達(dá)到最小。請回答下列問題。(1)請寫出合并方案，并求出最壞情況下比較的總次數(shù)。(2)根據(jù)你的合并過程，描述N(N>=2)個(gè)不等長升序表的合并策略，并說明理由。分析:根據(jù)排序中的歸并排序的思想，多個(gè)有序表通過兩兩歸并可以得到一個(gè)有序表，因?yàn)槎鄠€(gè)歸并段的長度不同，在進(jìn)行兩兩歸并時(shí)要想減少比較的次數(shù)，是先將元素少的表進(jìn)行歸并，再歸并元素多的表。這樣這個(gè)問題就轉(zhuǎn)化為最優(yōu)二叉樹的構(gòu)造問題，將6個(gè)有序表的長度看做6個(gè)葉子結(jié)點(diǎn)的權(quán)值，由此構(gòu)造最優(yōu)二叉樹。(此分析是根據(jù)個(gè)人理解做的，暫時(shí)沒有權(quán)威機(jī)構(gòu)的標(biāo)準(zhǔn)答案)四、練習(xí)題(一)選擇題1.一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為(C)。A(11B(10C(11至1025之間D(10至1024之間2(一棵二叉樹高度為h，所有結(jié)點(diǎn)的度或?yàn)?或?yàn)?，則這棵二叉樹最少有(B)結(jié)點(diǎn)。A(2hB(2h-1C(2h+1D(h+13.對二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號，要求每個(gè)結(jié)點(diǎn)的編號大于其左、右孩子的編號，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用(C)次序的遍歷實(shí)現(xiàn)編號。A(先序B(中序C(后序D(從根開始按層次遍歷4.某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是(C)的二叉樹。A(空或只有一個(gè)結(jié)點(diǎn)B(任一結(jié)點(diǎn)無左子樹C(高度等于其結(jié)點(diǎn)數(shù)D(任一結(jié)點(diǎn)無右子樹5.若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為(C)。A.X的雙親B.X的右子樹中最左的結(jié)點(diǎn)C.X的左子樹中最右結(jié)點(diǎn)D.X的左子樹中最右葉結(jié)點(diǎn)6.一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個(gè)數(shù)是(B)。A.0B.1C.2D.不確定(二)綜合題1.二叉樹的基本遍歷算法(1)二叉樹前序、中序、后序和層次遍歷的非遞歸算法前序voidPreOrder(BitreeT){InitStack(S);Push(S,T);while(!StackEmpty(S)){pop(S,p);visit(p->data);if(p->rchild!=NULL)push(S,p->rchild);if(p->lchild!=NULL)push(S,p->lchild);}}中序voidInOrder(BitreeT){InitStack(S);p=T;while(!StackEmpty(S)||p!=NULL){while(p!=NULL){push(S,p);p=p->lchild;}if(!StackEmpty(S)){pop(S,p);visit(p->data);p=p->rchild;}}}后序voidPostOrder(BitreeT){Bitreestack[],p;inttag[],top=0;p=T;while(top>0||p!=NULL){while(p!=NULL){top++;stack[top]=p;tag[top]=0;p=p->lchild;}if(top>0){p=stack[top];while(tag[top]==1){top--;visit(p->data);p=stack[to}if(top>0){p=stack[top];p=p->rchild;tag[top]=1;}}}}層次voidLayerOrder(BitreeT){InitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);visit(p->data);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}(2)二叉樹遍歷遞歸算法的應(yīng)用求二叉樹中葉子結(jié)點(diǎn)的數(shù)目intLeafCount_BiTree(BitreeT){if(!T)return0;//空樹沒有葉子elseif(!T->lchild&&!T->rchild)return1;elsereturnLeaf_Count(T->lchild)+Leaf_Count(T>rchild);}交換所有結(jié)點(diǎn)的左右子樹。voidBitree_Revolute(BitreeT){if(T!=NULL)T->lchild<->T->rchild;if(T->lchild)Bitree_Revolute(T->lchild);if(T->rchild)Bitree_Revolute(T->rchild);}求二叉樹中以值為x的結(jié)點(diǎn)為根的子樹深度。intGet_Sub_Depth(BitreeT,intx){if(T->data==x){printf("%d\n",Get_Depth(T));exit1;}else{if(T->lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)Get_Sub_Depth(T->rchild,x);}}intGet_Depth(BitreeT){if(!T)return0;else{m=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return(m>n?m:n)+1;}}判斷兩棵樹是否相似的遞歸算法。intBitree_Sim(BitreeB1,BitreeB2){if(!B1&&!B2)return1;elseif(B1&&B2)return(Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))elsereturn0;}2.二叉樹非遞歸遍歷算法的應(yīng)用(1)判斷一二叉樹是否為完全二叉樹。intFull_Bitree(BitreeT){InitQueue(Q);flag=0;EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);if(!p)flag=1;elseif(flag)return0;else{EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);}}return1;}(2)在二叉樹中查找值為x的結(jié)點(diǎn)，編寫算法輸出x的所有祖先。voidPostOrder(BitreeT，intx){Bitreestack[],p;inttag[],top=0;p=T;while(top>0||p!=NULL){while(p!=NULL&&p->data!=x){top++;stack[top]=p;tag[top]=0;p=p->lchild;}if(p->data==x){printf(“”);for(i=1;i<=top;i++)printf(stack[i]->data);return;}while(tag[top]==1&&top>1)top--;if(top>0){p=stack[top];p=p->rchild;tag[top]=1;}}}分析:二叉樹遍歷算法的應(yīng)用中關(guān)鍵的一個(gè)環(huán)節(jié)是分析要實(shí)現(xiàn)相關(guān)功能應(yīng)該選擇二叉樹的哪一種遍歷方式有利于實(shí)現(xiàn)，如以上兩個(gè)例子中分別選用二叉樹的層次遍歷和后序遍歷實(shí)現(xiàn)具體操作，主要對遍歷算法稍加處理就可以實(shí)現(xiàn)了。3(從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。分析:樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹(樹是森林的特例，即森林中只有一棵樹的特殊情況)可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。4(如果給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和中序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。如果給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和后序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。分析:給定二叉樹結(jié)點(diǎn)的前序序列和對稱序(中序)序列，可以唯一確定該二叉樹。因?yàn)榍靶蛐蛄械牡谝粋€(gè)元素是根結(jié)點(diǎn)，該元素將二叉樹中序序列分成兩部分，左邊(設(shè)l個(gè)元素)表示左子樹，若左邊無元素，則說明左子樹為空;右邊(設(shè)r個(gè)元素)是右子樹，若為空，則右子樹為空。根據(jù)前序遍歷中“根-—左子樹—右子樹”的順序，則由從第二元素開始的l個(gè)結(jié)點(diǎn)序列和中序序列根左邊的l個(gè)結(jié)點(diǎn)序列構(gòu)造左子樹，由前序序列最后r個(gè)元素序列與中序序列根右邊的r個(gè)元素序列構(gòu)造右子樹。由二叉樹的前序序列和后序序列不能唯一確定一棵二叉樹，因無法確定左右子樹兩部分。例如，任何結(jié)點(diǎn)只有左子樹的二叉樹和任何結(jié)點(diǎn)只有右子樹的二叉樹，其前序序列相同，后序序列相同，但卻是兩棵不同的二叉樹。5(給定一組數(shù)列(15,8,10,21,6,19,3)分別代表字符A,B,C,D,E,F,G出現(xiàn)的頻度，試敘述建立哈夫曼樹的算法思想，畫出哈夫曼樹，給出各字符的編碼值，并說明這種編碼的優(yōu)點(diǎn)。分析:考查哈夫曼樹的構(gòu)造和哈夫曼編碼，過程略。編碼的優(yōu)點(diǎn)是采用前綴編碼，出現(xiàn)頻度最高的字符編碼最短，減少編碼長度，減少出錯(cuò)率。第7章圖一、考研知識點(diǎn)(一)圖的基本概念(二)圖的存儲(chǔ)及基本操作1.鄰接矩陣法2.鄰接表法(三)圖的遍歷1.深度優(yōu)先搜索2.廣度優(yōu)先搜索(四)圖的基本應(yīng)用1.最小(代價(jià))生成樹2.最短路徑3.拓?fù)渑判?.關(guān)鍵路徑二、考查重點(diǎn)1(圖的基本概念及特點(diǎn);2.圖的存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表);3(圖的深度優(yōu)先和廣度優(yōu)先遍歷;4(圖的應(yīng)用(最小生成樹的構(gòu)造過程、拓?fù)湫蛄械纳?、最短路徑和關(guān)鍵路徑的求解過程)。分析:在數(shù)據(jù)結(jié)構(gòu)中，圖的結(jié)構(gòu)是最復(fù)雜的，這里的概念也是最多的。我們要掌握圖的基本概念(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、最短路徑、關(guān)鍵路徑等)。圖的存儲(chǔ)及基本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無向圖的這2種存儲(chǔ)方法，要清楚圖的連通和存儲(chǔ)方法之間的關(guān)系。例如，一個(gè)頂點(diǎn)的出度和鄰接矩陣中1的個(gè)數(shù)有什么關(guān)系，等等。圖的遍歷方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，我們要掌握這2種遍歷方法的算法實(shí)現(xiàn)。給出一個(gè)具體的圖，要能知道它的遍歷次序。在數(shù)據(jù)結(jié)構(gòu)課程中，圖的基本應(yīng)用是最多的，也是最復(fù)雜的，我們要掌握這些應(yīng)用的復(fù)雜度分析。要掌握的具體應(yīng)用主要包括最小(代價(jià))生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑。在給出的一個(gè)具體的圖中，我們要會(huì)利用已知條件，求出上述應(yīng)用的結(jié)果。這一章的內(nèi)容也比較多，尤其大的知識點(diǎn)比較多，容易出綜合題，特別是圖的應(yīng)用。在理解最小生成樹、拓?fù)渑判颉⒆疃搪窂胶完P(guān)鍵路徑的求解的同時(shí)要注意和具體問題結(jié)合，一般不會(huì)直接考，會(huì)和具體問題結(jié)合來考，例如09年的考研題。這一章考算法的可能性不大，但那兩個(gè)最基本的遍歷算法最好掌握。三、考研真題(一)選擇題1.(09年)下列關(guān)于無向連通圖特性的敘述中，正確的是()。I.所有頂點(diǎn)的度之和為偶數(shù)II.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1III.至少有一個(gè)頂點(diǎn)的度為1A.只有IB.只有IIC.I和IID.I和III分析:答案是A，此題考查無向連通圖的特性。2.(10年)若無向圖G-(V.E)中含7個(gè)頂點(diǎn)，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是()。A.6B.15C.16D.21分析:答案是C，此題考查無向連通圖的特點(diǎn)，解題時(shí)需要注意保證圖G在任何情況下都是連通的這句話，這是關(guān)鍵。因?yàn)橐ＷC圖在任何情況下都連通，先考慮6個(gè)頂點(diǎn)全連通需要15條邊，加上一個(gè)頂點(diǎn)后，加上一條邊保證第七個(gè)頂點(diǎn)與圖連通，因此至少需要16條邊。3.(10年)對下圖進(jìn)行拓補(bǔ)排序，可以得到不同的拓補(bǔ)序列的個(gè)數(shù)是()。A.4B.3C.2D.1，此題考查圖的拓?fù)渑判?。分?答案是B4((11年)下列關(guān)于圖的敘述中，正確的是()。I(回路是簡單路徑II(存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間III(若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路A.僅IIB.僅I、IIC.僅IIID.僅I、III分析:答案是C，此題考查圖的基本概念?；芈穼?yīng)于路徑，簡單回路對應(yīng)于簡單路徑;II剛好說反了，III是拓?fù)溆行虻谋匾獥l件。5.(12年)對有n個(gè)結(jié)點(diǎn)，e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是()。A.O(n)B.O(e)C.O(n+e)D.O(n*e)分析:答案為C。此題考查有向圖的遍歷，只要清楚鄰接表的存儲(chǔ)方式，答案很直接。6.(12年)若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)構(gòu)是()。A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一D.無法確定是否存在分析:答案為C。此題考查圖的鄰接矩陣存儲(chǔ)方式和拓?fù)渑判颉?.(12年)如下有向帶權(quán)圖，若采用迪杰斯特拉算法求原點(diǎn)a到其他各頂點(diǎn)的最短路徑，得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b，第二條最短路徑的目標(biāo)頂點(diǎn)是c，那么到其余各最短路徑的目標(biāo)頂點(diǎn)依次是()。(此題暫時(shí)不完整，但題目比較簡單，考察最短路徑的求解過程)A.d,e,fB.f,e,dC.D.8.(12年)下列關(guān)于最小生成樹的說法中，正確的是()。I.最小生成樹的代價(jià)唯一II.權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹中III.用普里姆算法從不同頂點(diǎn)開始得到的最小生成樹一定相同IV.普里姆算法和克魯斯卡爾算法得到的最小生成樹總不相同A.僅IB.僅IIC.僅I、IIID.僅II、IV分析:此題考查最小生成樹的概念和構(gòu)造方法，我認(rèn)為I和II正確，可是答案沒有選項(xiàng)，因?yàn)轭}目是考生回憶的，是不是某個(gè)地方敘述有錯(cuò)誤,(答案待定)(二)綜合題1.(09年)帶權(quán)圖(權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離)的最短路徑問題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問題的方法:(1)設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂點(diǎn);(2)選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v，加入到最短路徑中，修改當(dāng)前頂點(diǎn)u=v;(3)重復(fù)步驟(2)，直到u是目標(biāo)頂點(diǎn)為止。請問上述方法能否求得最短路徑,若該方法可行，請證明之;否則，請舉例說明。分析:此題考查最短路徑的求解思路，只是沒有直接考書上的最短路徑的求解過程，而是換個(gè)角度考查對最短路徑求解的理解。解答:該方法求得的路徑不一定是最短路徑。例如，對于下圖所示的帶權(quán)圖，如果按照題中的原則，從A到C的最短路徑為A->B->C，事實(shí)上其最短路徑為A->D->C。2((11年)已知有6個(gè)頂點(diǎn)(頂點(diǎn)編號為0-5)的有向帶權(quán)圖G，其鄰接矩陣A為上三角矩陣，按行優(yōu)先為主序保存在如下的一維數(shù)組中。46???5???43??33要求:(1)寫出圖G的鄰接矩陣A。(2)畫出有向帶權(quán)圖G。(3)求圖G的關(guān)鍵路徑，并計(jì)算該關(guān)鍵路徑的長度。解答:此題考查圖的鄰接矩陣的存儲(chǔ)以及關(guān)鍵路徑的求解，同時(shí)考查了特殊矩陣的壓縮存儲(chǔ)，主要是考查的圖的基本知識。(1)圖G的鄰接矩陣A如下所示。(2)有向帶權(quán)圖G如下圖所示。(3)關(guān)鍵路徑為0->1->2->3->5(如下圖粗線所示)，長度為16。四、練習(xí)題(一)選擇題1.無向圖G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，由頂點(diǎn)a開始對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是(D)。A(a,b,e,c,d,fB(a,c,f,e,b,dC(a,e,b,c,f,dD(a,e,d,f,c,b2.在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是(D)。A(G中有弧<Vi，Vj>B(G中有一條從Vi到Vj的路徑C(G中沒有弧<Vi,Vj>D(G中有一條從Vj到Vi的路徑3.用DFS遍歷一個(gè)無環(huán)有向圖，并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是(B)。A(逆拓?fù)溆行駼(拓?fù)溆行駽(無序的4.下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)(回路)(AB)。A(深度優(yōu)先遍歷B.拓?fù)渑判駽.求最短路徑D.求關(guān)鍵路徑5.下面關(guān)于求關(guān)鍵路徑的說法不正確的是(C)。A(求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的B(一個(gè)事件的最早開始時(shí)間同以該事件為尾的弧的活動(dòng)最早開始時(shí)間相同C(一個(gè)事件的最遲開始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差D(關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上(二)綜合題1(給定n個(gè)村莊之間的交通圖，若村莊i和j之間有道路，則將頂點(diǎn)i和j用邊連接，邊上的Wij表示這條道路的長度，現(xiàn)在要從這n個(gè)村莊中選擇一個(gè)村莊建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個(gè)村莊，才能使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短?分析:每個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑中最長的有n條，求這n條中最短的一條。2(設(shè)頂點(diǎn)a,b,c,d,e表示一個(gè)鄉(xiāng)的5個(gè)村莊，弧上的權(quán)值表示為兩村之間的距離;?求每個(gè)村莊到其它村莊的最短距離;?鄉(xiāng)內(nèi)要建立一所醫(yī)院，問醫(yī)院設(shè)在哪個(gè)村莊才能使各村離醫(yī)院的距離較近。分析:每個(gè)頂點(diǎn)到其余各頂點(diǎn)最短路徑之和最短的一個(gè)。3(已知有6個(gè)村子，相互間道路的距離如圖所示。擬合建一所小學(xué)，已知A處有小學(xué)生50人，B處40人，C處60人，C處20人，E處70人，F(xiàn)處90人，問小學(xué)應(yīng)該建在哪個(gè)村子，是學(xué)生上學(xué)最為方便(走的總路程最短)。6261481733分析:此問題還是歸為最短路徑問題，考慮路徑的總體狀況。解答:先求出任意兩點(diǎn)間的最短路徑下表所示:ABCDEFA0267811B204569C640125D751014E862103F1195430將每行數(shù)字分別乘以各村小學(xué)生人數(shù)得下表:ABCDEFA0100300350400550B800160200240360C360240060120300D1401002002080E560420140700210F9908104503602700按列相加其總和最小的列所對應(yīng)村子即是所求村子。4(某企業(yè)使用一臺設(shè)備，在每年年初，企業(yè)領(lǐng)導(dǎo)部門就要決定是購置新的，還是繼續(xù)使用舊的設(shè)備。若購置新設(shè)備，就要支付一定的購置費(fèi)用;若繼續(xù)使用舊設(shè)備，則需支付一定的維修費(fèi)用。現(xiàn)在的問題是如何制定一個(gè)幾年之內(nèi)的設(shè)備更新計(jì)劃使得總支付費(fèi)用最小。表1設(shè)備年初價(jià)格第1年第2年第3年第4年第5年1111121213表2維修費(fèi)用使用年數(shù)0-11-22-33-44-5維修費(fèi)用5681118分析:此問題同樣可以歸為最短路徑問題，假定每年年初都購置新設(shè)備，可以把每年年初作為一個(gè)頂點(diǎn)，任意兩個(gè)頂點(diǎn)之間的連線表示設(shè)備的使用情況，權(quán)值用使用過程中的費(fèi)用表示，這樣可以構(gòu)造一個(gè)圖，在圖中求從第一年年初到第五年末的最短路徑，路徑上的頂點(diǎn)就是設(shè)備更新計(jì)劃。解答:設(shè)vi表示第i年購進(jìn)一臺新設(shè)備，(vi，vj)表示設(shè)備由第i年初使用到第j年初，權(quán)值表示使用費(fèi)用，得到下圖:594130221817161716232223313041在圖中求由v1到v6的最短路徑得到兩條:v1-v3-v6和v1-v4-v6，因此設(shè)備的更新計(jì)劃為在第1年和第3年年初更新設(shè)備或者是在第1年和第4年年初更新設(shè)備，總費(fèi)用是53。5(下表給出了某工程各工序之間的優(yōu)先關(guān)系和各工序所需時(shí)間(1)畫出相應(yīng)的AOE網(wǎng)(2)列出各事件的最早發(fā)生時(shí)間,最遲發(fā)生時(shí)間(3)找出關(guān)鍵路徑并指明完成該工程所需最短時(shí)間.工序代號ABCDEFGHIJKLMN所需時(shí)間15105081540300151206015302040先驅(qū)工作----A,BBC,DBEG,IEIF,IH,J,KLG分析:此題考查關(guān)鍵路徑的求解過程，求解過程略。第9章查找一、考研知識點(diǎn)(一)查找的基本概念(二)順序查找法(三)折半查找法(四)二叉排序樹(五)平衡二叉樹-+(六)B樹及其基本操作、B樹的基本概念(七)散列(Hash)表(八)查找算法的分析及應(yīng)用二、考查重點(diǎn)1(順序表的查找及平均查找長度;2(有序表的查找(折半查找)及平均查找長度;3(二叉排序數(shù)的構(gòu)造及查找效率分析;4(平衡二叉樹的構(gòu)造;-+5(B樹與B樹的定義和特點(diǎn);6(哈希表的構(gòu)造(哈希函數(shù)構(gòu)造方法:除留余數(shù)法，處理沖突的方法:開放定址法和鏈地址法)及平均查找長度。分析:在給定的數(shù)據(jù)集合中查找某個(gè)關(guān)鍵值就是查找，查找的基本方法主要有順序查找法、折半查找法、B-樹、散列(Hash)表及其查找?？嫉谋容^多的是折半查找和散列表，我們要掌握它們的基本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等;二叉排序樹、平衡二叉樹的基本概念和應(yīng)用，特別是二叉排序樹的基本性質(zhì)和特點(diǎn)要能很好地理解。另外，我們要掌握各種查找算法的分析及應(yīng)用，最好能把各種查找在查找成功、查找失敗的情況下的最好、平均、最壞的平均查找次數(shù)的計(jì)算方法搞清楚。這一章可以認(rèn)為是線性表和二叉樹在查找中的應(yīng)用，利用前面所學(xué)知識來解決新的問題，重點(diǎn)是分析各種查找方式下的時(shí)間效率，選擇題和綜合題都可以出。綜合題出哈希表的可能性比較多，也有可能出算法題，這樣會(huì)和第2章線性表和第6章二叉樹結(jié)合來考，總之是和前面的內(nèi)容有聯(lián)系的，一定要掌握各種查找方法的思想并能進(jìn)行分析。三、考研真題(一)選擇題1.(09年)下列二叉排序樹中，滿足平衡二叉樹定義的是()。分析:答案是B，此題考查平衡二叉樹的定義。2((09年)下列敘述中，不符合m階B樹定義要求的是()。A.根結(jié)點(diǎn)最多有m棵子樹B.所有葉結(jié)點(diǎn)都在同一層上C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.葉結(jié)點(diǎn)之間通過指針鏈接-分析:答案是D，此題考查B樹的定義，題目出的不太嚴(yán)格，但是利用排除法可以得到答案。3.(10年)在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在節(jié)點(diǎn)的左、右結(jié)點(diǎn)中保存的關(guān)鍵字分別是()。A.13,48B.24,48C.24,53D.24,90分析:答案是C，此題考查平衡二叉樹的調(diào)整過程。4.(10年)已知一個(gè)長度為16的順序表L，其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個(gè)不存在的元素，則比較次數(shù)最多是()。A.4B.5C.6D.7分析:答案是A，此題考查有序表的折半查找的思想。5((11年)對于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是()。A.95,22,91,24,94,71B.92,20,91,34,88,35C.21,89,77,29,36,38D.12,25,71,68,33,34分析:答案為A，此題考查二叉排序樹的查找。在答案A中檔找到91后向24查找，說明后面的數(shù)都比91小，而后面序列中出現(xiàn)了94，顯然不對。6((11年)為提高散列表的查找效率，可以采取的正確措施是()。I(增大裝填(載)因子II(設(shè)計(jì)沖突(碰撞)少的散列函數(shù)III(處理沖突(碰撞)時(shí)避免產(chǎn)生聚集(堆積)現(xiàn)象A.僅IB.僅IIC.僅IIID.僅II、III分析:答案是B，此題考查哈希表的構(gòu)造和查找。I顯然不對，III中的避免是不可能的，只能是減少。7.(12年)若平衡二叉樹的深度為6，且對所有非葉結(jié)點(diǎn)的平衡因子均為1，則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為()。A.10B.20C.32D.33分析:答案為B。此題考查平衡二叉樹的定義，在深度為6的滿二叉樹中去掉相應(yīng)結(jié)點(diǎn)，滿足對所有非葉結(jié)點(diǎn)的平衡因子都為1，此時(shí)得到的二叉樹的結(jié)點(diǎn)總數(shù)為20。8.(12年)已知一棵3階B樹，如下圖所示，刪除關(guān)鍵字78得到一棵新B樹，其最右葉結(jié)點(diǎn)中的關(guān)鍵字是()。A.60B.60,62C.62,65D.65-分析:答案為D。此題考查B樹的刪除操作，只要掌握書上的刪除方法就可以得到答案。(二)綜合題1.(10年)將關(guān)鍵字序列(7、8、30、11、18、9、14)散列存儲(chǔ)到散列列表中，散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開始的一個(gè)一維數(shù)組散列函數(shù)維:H(key)=(key×3)MODT，處理沖突采用線性探測再散列法，要求裝填(載)因子為0.7。問題:(1)請畫出所構(gòu)造的散列表;(2)分別計(jì)算等概率情況下，查找成功和查找不成功的平均查找長度。分析:此題考查哈希表的構(gòu)造和沖突解決，以及裝填因子的計(jì)算。解答:(1)由裝載因子0.7，數(shù)據(jù)總數(shù)7個(gè)，得一維數(shù)組大小為7/0.7=10，存儲(chǔ)空間長度為10，哈希函數(shù)為H(key)=(key×3)MOD10，采用線性探測再散列法處理沖突，所構(gòu)造的散列表為:01234567893071411818.9..(2)查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.2四、練習(xí)題(一)選擇題1(當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，既可用折半查找，也可用順序查找，但前者比后者的查找速度(C)。A(必定快B.不一定C.在大部分情況下要快D.取決于表遞增還是遞減2.具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長度(B)。A.3.1B.4C.2.5D.53(二叉查找樹的查找效率與二叉樹的((1)A)有關(guān),在((2)C)時(shí)其查找效率最低。(1):A.高度B.結(jié)點(diǎn)的多少C.樹型D.結(jié)點(diǎn)的位置(2):A.結(jié)點(diǎn)太多B.完全二叉樹C.呈單枝樹D.結(jié)點(diǎn)太復(fù)雜。4.分別以下列序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是(C)。A.(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90)C.(100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)5(假定有k個(gè)