數(shù)據(jù)結(jié)構(gòu)考研知識(shí)點(diǎn)總結(jié)

數(shù)據(jù)結(jié)構(gòu)考研真題及知識(shí)點(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章線性表一、考研知識(shí)點(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)比擬，及其各自適用的場(chǎng)合。單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針的各自好處；4．能分析所寫算法的時(shí)間和空間復(fù)雜度。分析：線性表是一種最簡(jiǎn)單的數(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í)中，其作用都是不可低估的。線性表一章小的知識(shí)點(diǎn)比擬少，一般會(huì)出一個(gè)綜合題，并且容易和第三章、第九章和第十章的內(nèi)容結(jié)合來考，注意對(duì)根本知識(shí)的理解，能夠利用書上的理論解決具體問題。學(xué)習(xí)過程中要注意多積累，多看、多寫一些相關(guān)算法。三、考研真題〔一〕選擇題近幾年第2章沒有考選擇題，只有兩個(gè)計(jì)算時(shí)間復(fù)雜度的題目，因?yàn)榇苏轮饕蔷€性表的操作，而且又是這門課的一個(gè)根底，考綜合題的可能性比擬大，可以和第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;A.O(logn)

B.O(n)

C.O(nlogn)

D.O(n2)2.〔12年〕求整數(shù)n〔n>=0〕的階乘的算法如下，其時(shí)間復(fù)雜度是〔B〕。intfact(intn){if(n<=1)return1;returnn*fact(n-1);}A.o(log2n)B.O(n)C.O(nlog2n)D.O(n2)分析：考查的是算法時(shí)間復(fù)雜度的計(jì)算?？梢苑旁诘诙?，實(shí)際這內(nèi)容貫穿每一章內(nèi)容中算法的度量?！捕尘C合題1.〔09年〕一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表結(jié)點(diǎn)結(jié)構(gòu)為(data,link)，假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)〔k為正整數(shù)〕。假設(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語言實(shí)現(xiàn)〕，關(guān)鍵之處給出簡(jiǎn)要注釋。分析：此題考查線性表的鏈?zhǔn)酱鎯?chǔ)，主要是線性表的根本操作的應(yīng)用。做此題時(shí)要把握算法的效率?！?〕算法根本思想如下：從頭到尾遍歷單鏈表，并用指針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)?！?〕詳細(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)?！?〕算法描述：intlocate(Linklistlist,intk){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-1

X0

X1……Xp-1〕要求：〔1〕給出算法的根本設(shè)計(jì)思想。〔2〕根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語言表述算法，關(guān)鍵之處給出注釋?！?〕說明你所設(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ù)組的前p個(gè)元素，b代表數(shù)組中余下的n-p個(gè)元素〕，先將a逆置得到a-1b，再將b逆置得到a-1b-1，最后將整個(gè)a-1b-1逆置得到〔a-1b-1〕-1=ba。設(shè)reverse函數(shù)執(zhí)行將數(shù)組元素逆置的操作，對(duì)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è)長(zhǎng)度為L(zhǎng)〔L>=1〕的生序列S，處在第┌L/2┐個(gè)位置的數(shù)稱為S的中位數(shù)，例如，假設(shè)序列S1=〔11,13,15,17,19〕，那么S1的中位數(shù)是15，兩個(gè)序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，假設(shè)S2=〔2,4,6,8,20〕，那么S1和S2的中位數(shù)是11?，F(xiàn)在有兩個(gè)等長(zhǎng)升序序列A和B，試設(shè)計(jì)一個(gè)在時(shí)間和空間方面都盡可能高效的算法，找出兩個(gè)序列A和B的中位數(shù)。要求：〔1〕給出算法的根本設(shè)計(jì)思想?！?〕根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語言描述算法，關(guān)鍵之處給出注釋。分析：此題考查線性表的順序存儲(chǔ)，主要是線性表的根本操作的應(yīng)用。做此題時(shí)要把握算法的效率?！?〕算法的根本設(shè)計(jì)思想如下：分別求出序列A和B的中位數(shù)，設(shè)為a和b，求序列A和B的中位數(shù)過程如下：1〕假設(shè)a=b，那么a或b即為所求中位數(shù)，算法結(jié)束；2〕假設(shè)a<b，那么舍棄序列A中較小的一半，同時(shí)舍棄序列B中較大的一半，要求舍棄的長(zhǎng)度相等；3〕假設(shè)a>b，那么舍棄序列A中較大的一半，同時(shí)舍棄序列B中較小的一半，要求舍棄的長(zhǎng)度相等；在保存的兩個(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)的單鏈表，如果有共同后綴，長(zhǎng)度分別為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〕，請(qǐng)?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)鍵之處給出注釋?！?〕說明你所設(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è)鏈表長(zhǎng)度不一定一樣，在順序遍歷兩個(gè)鏈表到尾結(jié)點(diǎn)時(shí)，并不能保證在兩個(gè)鏈表上同時(shí)到達(dá)尾結(jié)點(diǎn)。假設(shè)一個(gè)鏈表比另一個(gè)長(zhǎng)k個(gè)結(jié)點(diǎn)，我們先在長(zhǎng)的鏈表上遍歷k個(gè)結(jié)點(diǎn)，之后再同步遍歷，此時(shí)能夠保證同時(shí)到達(dá)最后一個(gè)結(jié)點(diǎn)。在遍歷中，第一個(gè)相同的結(jié)點(diǎn)就是第一個(gè)公共結(jié)點(diǎn)。〔1〕算法思想：根據(jù)兩個(gè)單鏈表的長(zhǎng)度，求出它們的長(zhǎng)度之差；在長(zhǎng)的單鏈表上先遍歷長(zhǎng)度之差個(gè)結(jié)點(diǎn)；同步遍歷兩個(gè)單鏈表，直接找到相同的結(jié)點(diǎn)，假設(shè)有相同結(jié)點(diǎn)返回該節(jié)點(diǎn)，假設(shè)沒有那么一直到鏈表結(jié)束?！?〕算法實(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)于線性表的表達(dá)中，錯(cuò)誤的選項(xiàng)是哪一個(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．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項(xiàng)E．信息項(xiàng)4．假設(shè)某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(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．假設(shè)長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為〔C〕(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)7.對(duì)于順序存儲(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ù)鏈，算法中不得申請(qǐng)新的結(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)行刪除操作?！?〕設(shè)單鏈表的表頭指針為h，結(jié)點(diǎn)結(jié)構(gòu)由data和next兩個(gè)域構(gòu)成，其中data域?yàn)樽址?。寫出算法dc(h,n),判斷該鏈表的前n個(gè)字符是否中心對(duì)稱。例如xyx,xyyx都是中心對(duì)稱。分析：判斷鏈表中數(shù)據(jù)是否中心對(duì)稱，通常使用棧。將鏈表的前一半元素依次進(jìn)棧。在處理鏈表的后一半元素時(shí)，當(dāng)訪問到鏈表的一個(gè)元素后，就從棧中彈出一個(gè)元素，兩元素比擬，假設(shè)相等，那么將鏈表中下一元素與棧中再彈出元素比擬，直至鏈表到尾。這時(shí)假設(shè)棧是空棧，那么得出鏈表中心對(duì)稱的結(jié)論；否那么，當(dāng)鏈表中一元素與棧中彈出元素不等時(shí)，結(jié)論為鏈表非中心對(duì)稱，結(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;∥假設(shè)n是奇數(shù)，后移過中心結(jié)點(diǎn)。while〔p!=null&&s[i]==p->data〕{i--;p=p->next;}∥測(cè)試是否中心對(duì)稱。if〔p==null〕return1;∥鏈表中心對(duì)稱elsereturn0;∥鏈表不中心對(duì)稱}∥算法結(jié)束?！?〕兩個(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ì)列一、考研知識(shí)點(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)系，利于對(duì)以后章節(jié)〔樹和圖〕的學(xué)習(xí)和復(fù)習(xí)。分析：棧和隊(duì)列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊(duì)列的根本概念，以及他們之間的區(qū)別。對(duì)于棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)(包括順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))要有較深的理解，對(duì)于棧和隊(duì)列的應(yīng)用，例如，排隊(duì)問題、子程序調(diào)用問題、表達(dá)式問題等，要搞清楚。此章內(nèi)容是線性表的深化，如果線性表理解的好，這一章就比擬容易。這一章小的知識(shí)點(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。假設(shè)每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)順序是bdcfeag，那么棧S的容量至少是〔〕。A.1B.2C.3D.4分析：答案是C，此題考查棧的入棧和出棧操作和隊(duì)列的入隊(duì)和出隊(duì)操作。3.〔10年〕假設(shè)元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，那么不可能得到的出棧序列是〔

〕。A.dcebfa

B.cbdaef

C.dbcaef

D.afedcb分析：答案是D，此題考查棧的入棧和出棧操作，但題目出的不是太嚴(yán)謹(jǐn)，嚴(yán)格說應(yīng)該是CD兩個(gè)答案。4.〔10年〕某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，那么不可能得到的順序是〔C〕A.bacde

B.dbace

C.dbcae

D.ecbad分析：答案是C，此題考查隊(duì)列的入隊(duì)和出隊(duì)操作。5．〔11年〕元素a，b，c，d，e依次進(jìn)入初始為空的棧中，假設(shè)元素進(jìn)棧后可停留、可進(jìn)棧，直到所有元素都出棧，那么在所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是A.3

B.4

C.5

D.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è)初始時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A[0]處，那么初始時(shí)front和rear的值分別是A.0,0

B.0，n-1

C.n-1,0

D.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)算次序的操作符，假設(shè)棧初始為空，那么轉(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，假設(shè)輸出序列的第一個(gè)元素是n，輸出第i〔1<=i<=n〕個(gè)元素是〔B〕。A.不確定B.n-i+1C.iD.n-i2.假設(shè)一個(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.假設(shè)用一個(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é)中有例題表達(dá)。第5章數(shù)組和廣義表一、考研知識(shí)點(diǎn)特殊矩陣的壓縮存儲(chǔ)二、考查重點(diǎn)一維數(shù)組屬于線性表范疇，但多維數(shù)組不屬于線性表。在這方面，主要掌握數(shù)組的存儲(chǔ)結(jié)構(gòu)，例如按行優(yōu)先、按列優(yōu)先等，某個(gè)元素存在的地址是什么。對(duì)于特殊矩陣(二維數(shù)組)的壓縮存儲(chǔ)原理也要搞清楚。重點(diǎn)考查特殊矩陣的壓縮存儲(chǔ)中矩陣中元素在存儲(chǔ)空間中地址的計(jì)算，只要掌握計(jì)算的方法就行，計(jì)算時(shí)需要特別注意矩陣首元素的下標(biāo)值以及存儲(chǔ)空間首元素的下標(biāo)值。三、考研真題近幾年此知識(shí)點(diǎn)沒有出題。四、練習(xí)題1.設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，那么a85的地址為〔B〕。A.13B.33C.18D.402.設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長(zhǎng)度為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]的三對(duì)角矩陣，按行優(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ǔ)表達(dá)中〔〕內(nèi)的正確答案。〔1〕存放A至少需要〔E〕個(gè)字節(jié)；〔2〕A的第8列和第5行共占〔A〕個(gè)字節(jié)；〔3〕假設(shè)A按行存放，元素A[8，5]的起始地址與A按列存放時(shí)的元素〔B〕的起始地址一致?！?〕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的對(duì)稱矩陣，將A的對(duì)角線及對(duì)角線上方的元素以列為主的次序存放在一維數(shù)組B[1..n(n+1)/2]中，對(duì)上述任一元素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章樹和二叉樹一、考研知識(shí)點(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ǔ)根底上，例如，二叉樹的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應(yīng)用。在特殊的二叉樹中，完全二叉樹的概念是必須要搞清楚的，其次，線索二叉樹的根本概念和構(gòu)造。多棵獨(dú)立的樹就組成了森林，樹的存儲(chǔ)結(jié)構(gòu)和遍歷、森林的遍歷、樹和二叉樹的轉(zhuǎn)換、森林和二叉樹的轉(zhuǎn)換等知識(shí)，也要了解。最后就是樹的應(yīng)用，通常會(huì)作為綜合應(yīng)用類試題出現(xiàn)，包括等價(jià)類問題、哈夫曼(Huffman)樹和哈夫曼編碼等。此章知識(shí)點(diǎn)比擬多，并且每個(gè)知識(shí)點(diǎn)都可能出題，因此要做到對(duì)每一個(gè)知識(shí)點(diǎn)的理解和掌握，選擇題和綜合題都可以出，綜合題一般會(huì)現(xiàn)在二叉樹的遍歷及其應(yīng)用、樹與二叉樹的轉(zhuǎn)換和哈夫曼樹的構(gòu)造及哈夫曼編碼。三、考研真題〔一〕選擇題1.〔09年〕給定二叉樹如下圖。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。假設(shè)遍歷后的結(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)換為對(duì)應(yīng)的二叉樹，假設(shè)在二叉樹中，結(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)，假設(shè)v是u的左子樹，那么u與v是父子關(guān)系，假設(shè)v是u的右子樹，那么u與v是兄弟關(guān)系。4.〔10年〕以下線索二叉樹中〔用虛線表示線索〕，符合后序線索樹定義的是〔

〕。分析：答案是D，此題考查二叉樹的線索化。5.〔10年〕在一棵度為4的樹T中，假設(shè)有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.41

B.82

C.113

D.122分析：答案是B，此題考查二叉樹的性質(zhì)，利用二叉樹的性質(zhì)3的證明思路進(jìn)行求解。6.〔10年〕對(duì)n(n大于等于2)個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的表達(dá)中，錯(cuò)誤的選項(xiàng)是〔〕。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年〕假設(shè)一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，那么該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)是〔〕。A.257

B.258

C.384

D.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年〕假設(shè)一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1，那么該二叉樹的中序遍歷序列不會(huì)是〔〕。A.1,2,3,4

B.2,3,4,1

C.3,2,4,1

D.4,3,2,1分析：答案是C，考查二叉樹的遍歷。此題可以用畫圖的方式進(jìn)行判斷。9．〔11年〕一棵有2011個(gè)結(jié)點(diǎn)的樹，其葉結(jié)點(diǎn)個(gè)數(shù)116，該樹對(duì)應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)個(gè)數(shù)是〔〕。A.115

B.116

C.1895

D.1896分析：答案是D，此題考查二叉樹和樹的轉(zhuǎn)換。考慮一種特殊的情況，設(shè)題意中的樹是如以下圖所示的結(jié)構(gòu)，那么對(duì)應(yīng)的二叉樹中僅有前115個(gè)葉結(jié)點(diǎn)有右孩子。10.〔年〕假設(shè)一棵二叉樹的前序遍歷序列為a,e,b,d,c，后序遍歷序列為b,c,d,e,a，那么根結(jié)點(diǎn)的孩子結(jié)點(diǎn)〔〕。A.只有eB.有e、bC.有e、cD.無法確定分析：答案為A。此題考查二叉樹的遍歷，根據(jù)我們的常識(shí)，由前序序列和后序序列不能確定二叉樹，但此題并不是確定二叉樹而是確定二叉樹的根結(jié)點(diǎn)的孩子結(jié)點(diǎn)，因?yàn)楦Y(jié)點(diǎn)可以確定，仔細(xì)分析前序和后序序列，可以判斷出孩子結(jié)點(diǎn)只有e，因此答案為A?！捕尘C合題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á)最小。請(qǐng)答復(fù)以下問題?！?〕請(qǐng)寫出合并方案，并求出最壞情況下比擬的總次數(shù)。〔2〕根據(jù)你的合并過程，描述N〔N>=2〕個(gè)不等長(zhǎng)升序表的合并策略，并說明理由。分析：根據(jù)排序中的歸并排序的思想，多個(gè)有序表通過兩兩歸并可以得到一個(gè)有序表，因?yàn)槎鄠€(gè)歸并段的長(zhǎng)度不同，在進(jìn)行兩兩歸并時(shí)要想減少比擬的次數(shù)，是先將元素少的表進(jìn)行歸并，再歸并元素多的表。這樣這個(gè)問題就轉(zhuǎn)化為最優(yōu)二叉樹的構(gòu)造問題，將6個(gè)有序表的長(zhǎng)度看做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.對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用(C)次序的遍歷實(shí)現(xiàn)編號(hào)。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.假設(shè)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)具體操作，主要對(duì)遍歷算法稍加處理就可以實(shí)現(xiàn)了。3．從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的根本目的是什么，并指出樹和二叉樹的主要區(qū)別。分析：樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹〔樹是森林的特例，即森林中只有一棵樹的特殊情況〕可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。4．如果給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和中序序列，能否構(gòu)造出此二叉樹?假設(shè)能，請(qǐng)證明之。假設(shè)不能，請(qǐng)給出反例。如果給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和后序序列，能否構(gòu)造出此二叉樹?假設(shè)能，請(qǐng)證明之。假設(shè)不能，請(qǐng)給出反例。分析：給定二叉樹結(jié)點(diǎn)的前序序列和對(duì)稱序〔中序〕序列，可以唯一確定該二叉樹。因?yàn)榍靶蛐蛄械牡谝粋€(gè)元素是根結(jié)點(diǎn)，該元素將二叉樹中序序列分成兩局部，左邊〔設(shè)l個(gè)元素〕表示左子樹，假設(shè)左邊無元素，那么說明左子樹為空；右邊〔設(shè)r個(gè)元素〕是右子樹，假設(shè)為空，那么右子樹為空。根據(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)的頻度，試表達(dá)建立哈夫曼樹的算法思想，畫出哈夫曼樹，給出各字符的編碼值，并說明這種編碼的優(yōu)點(diǎn)。分析：考查哈夫曼樹的構(gòu)造和哈夫曼編碼，過程略。編碼的優(yōu)點(diǎn)是采用前綴編碼，出現(xiàn)頻度最高的字符編碼最短，減少編碼長(zhǎng)度，減少出錯(cuò)率。第7章圖一、考研知識(shí)點(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ù)湫蛄械纳伞⒆疃搪窂胶完P(guān)鍵路徑的求解過程〕。分析：在數(shù)據(jù)結(jié)構(gòu)中，圖的結(jié)構(gòu)是最復(fù)雜的，這里的概念也是最多的。我們要掌握?qǐng)D的根本概念(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、最短路徑、關(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)容也比擬多，尤其大的知識(shí)點(diǎn)比擬多，容易出綜合題，特別是圖的應(yīng)用。在理解最小生成樹、拓?fù)渑判?、最短路徑和關(guān)鍵路徑的求解的同時(shí)要注意和具體問題結(jié)合，一般不會(huì)直接考，會(huì)和具體問題結(jié)合來考，例如09年的考研題。這一章考算法的可能性不大，但那兩個(gè)最根本的遍歷算法最好掌握。三、考研真題〔一〕選擇題1.〔09年〕以下關(guān)于無向連通圖特性的表達(dá)中，正確的選項(xiàng)是〔〕。I.所有頂點(diǎn)的度之和為偶數(shù)II.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1III.至少有一個(gè)頂點(diǎn)的度為1A.只有IB.只有IIC.I和IID.I和III分析：答案是A，此題考查無向連通圖的特性。2.〔10年〕假設(shè)無向圖G-〔V.E〕中含7個(gè)頂點(diǎn)，那么保證圖G在任何情況下都是連通的，那么需要的邊數(shù)最少是〔〕。A.6

B.15

C.16

D.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年〕對(duì)以下圖進(jìn)行拓補(bǔ)排序，可以得到不同的拓補(bǔ)序列的個(gè)數(shù)是〔〕。A.4

B.3

C.2

D.1分析：答案是B，此題考查圖的拓?fù)渑判颉?．〔11年〕以下關(guān)于圖的表達(dá)中，正確的選項(xiàng)是〔〕。I．回路是簡(jiǎn)單路徑II．存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間III．假設(shè)有向圖中存在拓?fù)湫蛄?，那么該圖不存在回路A.僅II

B.僅I、II

C.僅III

D.僅I、III分析：答案是C，此題考查圖的根本概念?；芈穼?duì)應(yīng)于路徑，簡(jiǎn)單回路對(duì)應(yīng)于簡(jiǎn)單路徑；II剛好說反了，III是拓?fù)溆行虻谋匾獥l件。5.〔12年〕對(duì)有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年〕假設(shè)用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對(duì)角線以下的元素均為零，那么關(guān)于該圖拓?fù)湫蛄械慕Y(jié)構(gòu)是〔〕。A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一D.無法確定是否存在分析：答案為C。此題考查圖的鄰接矩陣存儲(chǔ)方式和拓?fù)渑判颉?.〔12年〕如下有向帶權(quán)圖，假設(shè)采用迪杰斯特拉算法求原點(diǎn)a到其他各頂點(diǎn)的最短路徑，得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b，第二條最短路徑的目標(biāo)頂點(diǎn)是c，那么到其余各最短路徑的目標(biāo)頂點(diǎn)依次是〔〕。〔此題暫時(shí)不完整，但題目比擬簡(jiǎn)單，考察最短路徑的求解過程〕A.d,e,fB.f,e,dC.D.8.〔12年〕以下關(guān)于最小生成樹的說法中，正確的選項(xiàng)是〔〕。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è)地方表達(dá)有錯(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)為止。請(qǐng)問上述方法能否求得最短路徑？假設(shè)該方法可行，請(qǐng)證明之；否那么，請(qǐng)舉例說明。分析：此題考查最短路徑的求解思路，只是沒有直接考書上的最短路徑的求解過程，而是換個(gè)角度考查對(duì)最短路徑求解的理解。解答：該方法求得的路徑不一定是最短路徑。例如，對(duì)于以下圖所示的帶權(quán)圖，如果按照題中的原那么，從A到C的最短路徑為A->B->C，事實(shí)上其最短路徑為A->D->C。2．〔11年〕有6個(gè)頂點(diǎn)〔頂點(diǎn)編號(hào)為0-5〕的有向帶權(quán)圖G，其鄰接矩陣A為上三角矩陣，按行優(yōu)先為主序保存在如下的一維數(shù)組中。46∞∞∞5∞∞∞43∞∞33要求：〔1〕寫出圖G的鄰接矩陣A。〔2〕畫出有向帶權(quán)圖G?！?〕求圖G的關(guān)鍵路徑，并計(jì)算該關(guān)鍵路徑的長(zhǎng)度。解答：此題考查圖的鄰接矩陣的存儲(chǔ)以及關(guān)鍵路徑的求解，同時(shí)考查了特殊矩陣的壓縮存儲(chǔ)，主要是考查的圖的根本知識(shí)?！?〕圖G的鄰接矩陣A如下所示。〔2〕有向帶權(quán)圖G如以下圖所示?！?〕關(guān)鍵路徑為0->1->2->3->5〔如以下圖粗線所示〕，長(zhǎng)度為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開始對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的選項(xiàng)是〔D〕。A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,b,dC．a(chǎn),e,b,c,f,dD．a(chǎn),e,d,f,c,b2.在有向圖G的拓?fù)湫蛄兄校僭O(shè)頂點(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)鍵路徑的說法不正確的選項(xiàng)是〔C〕。A．求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)楦椎腂．一個(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è)村莊之間的交通圖，假設(shè)村莊i和j之間有道路，那么將頂點(diǎn)i和j用邊連接，邊上的Wij表示這條道路的長(zhǎng)度，現(xiàn)在要從這n個(gè)村莊中選擇一個(gè)村莊建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個(gè)村莊，才能使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短?分析：每個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑中最長(zhǎng)的有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é)最為方便〔走的總路程最短〕。分析：此問題還是歸為最短路徑問題，考慮路徑的總體狀況。解答：先求出任意兩點(diǎn)間的最短路徑下表所示：ABCDEFA0267811B204569C640125D751014E862103F1195430將每行數(shù)字分別乘以各村小學(xué)生人數(shù)得下表：ABCDEFA0100300350400550B800160200240360C360240060120300D1401002002080E560420140700210F9908104503602700按列相加其總和最小的列所對(duì)應(yīng)村子即是所求村子。4．某企業(yè)使用一臺(tái)設(shè)備，在每年年初，企業(yè)領(lǐng)導(dǎo)部門就要決定是購置新的，還是繼續(xù)使用舊的設(shè)備。假設(shè)購置新設(shè)備，就要支付一定的購置費(fèi)用；假設(shè)繼續(xù)使用舊設(shè)備，那么需支付一定的維修費(fèi)用?，F(xiàn)在的問題是如何制定一個(gè)幾年之內(nèi)的設(shè)備更新方案使得總支付費(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è)備更新方案。解答：設(shè)vi表示第i年購進(jìn)一臺(tái)新設(shè)備，〔vi，vj〕表示設(shè)備由第i年初使用到第j年初，權(quán)值表示使用費(fèi)用，得到以下圖：在圖中求由v1到v6的最短路徑得到兩條：v1-v3-v6和v1-v4-v6，因此設(shè)備的更新方案為在第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í)間.工序代號(hào)ABCDEFGHIJKLMN所需時(shí)間15105081540300151206015302040先驅(qū)工作----A,BBC,DBEG,IEIF,IH,J,KLG分析：此題考查關(guān)鍵路徑的求解過程，求解過程略。第9章查找一、考研知識(shí)點(diǎn)〔一〕查找的根本概念〔二〕順序查找法〔三〕折半查找法〔四〕二叉排序樹〔五〕平衡二叉樹〔六〕B-樹及其根本操作、B+樹的根本概念〔七〕散列〔Hash〕表〔八〕查找算法的分析及應(yīng)用二、考查重點(diǎn)1．順序表的查找及平均查找長(zhǎng)度；2．有序表的查找〔折半查找〕及平均查找長(zhǎng)度；3．二叉排序數(shù)的構(gòu)造及查找效率分析；4．平衡二叉樹的構(gòu)造；5．B-樹與B+樹的定義和特點(diǎn)；6．哈希表的構(gòu)造〔哈希函數(shù)構(gòu)造方法：除留余數(shù)法，處理沖突的方法：開放定址法和鏈地址法〕及平均查找長(zhǎng)度。分析：在給定的數(shù)據(jù)集合中查找某個(gè)關(guān)鍵值就是查找，查找的根本方法主要有順序查找法、折半查找法、B-樹、散列(Hash)表及其查找?？嫉谋葦M多的是折半查找和散列表，我們要掌握它們的根本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等；二叉排序樹、平衡二叉樹的根本概念和應(yīng)用，特別是二叉排序樹的根本性質(zhì)和特點(diǎn)要能很好地理解。另外，我們要掌握各種查找算法的分析及應(yīng)用，最好能把各種查找在查找成功、查找失敗的情況下的最好、平均、最壞的平均查找次數(shù)的計(jì)算方法搞清楚。這一章可以認(rèn)為是線性表和二叉樹在查找中的應(yīng)用，利用前面所學(xué)知識(shí)來解決新的問題，重點(diǎn)是分析各種查找方式下的時(shí)間效率，選擇題和綜合題都可以出。綜合題出哈希表的可能性比擬多，也有可能出算法題，這樣會(huì)和第2章線性表和第6章二叉樹結(jié)合來考，總之是和前面的內(nèi)容有聯(lián)系的，一定要掌握各種查找方法的思想并能進(jìn)行分析。三、考研真題〔一〕選擇題1.(09年)以下二叉排序樹中，滿足平衡二叉樹定義的是〔〕。分析：答案是B，此題考查平衡二叉樹的定義。2．〔09年〕以下表達(dá)中，不符合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è)長(zhǎng)度為16的順序表L，其元素按關(guān)鍵字有序排列，假設(shè)采用折半查找法查找一個(gè)不存在的元素，那么比擬次數(shù)最多是〔〕。A.4

B.5

C.6

D.7分析：答案是A，此題考查有序表的折半查找的思想。5．〔11年〕對(duì)于以下關(guān)