數(shù)據(jù)結構考研知識點總結

數(shù)據(jù)結構考研真題及知識點解析考察目標1.

掌握數(shù)據(jù)結構的根本概念、根本原理和根本方法。2.

掌握數(shù)據(jù)的邏輯結構、存儲結構及根本操作的實現(xiàn)，能夠對算法進行根本的時間復雜度與空間復雜度的分析。3.

能夠運用數(shù)據(jù)結構的根本原理和方法進行問題的分析與求解；具備采用C、C++或Java語言設計與實現(xiàn)算法的能力。第2章線性表一、考研知識點〔一〕線性表的定義和根本操作〔二〕線性表的實現(xiàn)1.順序存儲2.鏈式存儲3.線性表的應用二、考查重點1．線性結構的特點；2．線性表在順序存儲及鏈式存儲方式下的根本操作及其應用；3．線性表的順序存儲及鏈式存儲情況下，其不同和優(yōu)缺點比擬，及其各自適用的場合。單鏈表中設置頭指針、循環(huán)鏈表中設置尾指針而不設置頭指針的各自好處；4．能分析所寫算法的時間和空間復雜度。分析：線性表是一種最簡單的數(shù)據(jù)結構，在線性表方面，主要考查線性表的定義和根本操作、線性表的實現(xiàn)。在線性表實現(xiàn)方面，要掌握的是線性表的存儲結構，包括順序存儲結構和鏈式存儲結構，特別是鏈式存儲結構，是考查的重點。另外，還要掌握線性表的根本應用。線性表一章在線性結構的學習乃至整個數(shù)據(jù)結構學科的學習中，其作用都是不可低估的。線性表一章小的知識點比擬少，一般會出一個綜合題，并且容易和第三章、第九章和第十章的內容結合來考，注意對根本知識的理解，能夠利用書上的理論解決具體問題。學習過程中要注意多積累，多看、多寫一些相關算法。三、考研真題〔一〕選擇題近幾年第2章沒有考選擇題，只有兩個計算時間復雜度的題目，因為此章主要是線性表的操作，而且又是這門課的一個根底，考綜合題的可能性比擬大，可以和第3章、第9章和第10章的內容結合來出題。1．〔11年〕設n是描述問題規(guī)模的非負整數(shù)，下面程序片段的時間復雜度是〔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〕的階乘的算法如下，其時間復雜度是〔B〕。intfact(intn){if(n<=1)return1;returnn*fact(n-1);}A.o(log2n)B.O(n)C.O(nlog2n)D.O(n2)分析：考查的是算法時間復雜度的計算。可以放在第二章，實際這內容貫穿每一章內容中算法的度量?！捕尘C合題1.〔09年〕一個帶有表頭結點的單鏈表結點結構為(data,link)，假設該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數(shù)第k個位置上的結點〔k為正整數(shù)〕。假設查找成功，算法輸出該結點的data值，并返回1；否那么，只返回0。要求：〔1〕描述算法的根本設計思想；〔2〕描述算法的詳細實現(xiàn)步驟；〔3〕根據(jù)設計思想和實現(xiàn)步驟，采用程序設計語言描述算法〔使用C或C++或JAVA語言實現(xiàn)〕，關鍵之處給出簡要注釋。分析：此題考查線性表的鏈式存儲，主要是線性表的根本操作的應用。做此題時要把握算法的效率?！?〕算法根本思想如下：從頭到尾遍歷單鏈表，并用指針p指向當前結點的前k個結點。當遍歷到鏈表的最后一個結點時，指針p所指向的結點即為所查找的結點?！?〕詳細實現(xiàn)步驟：增加兩個指針變量和一個整型變量，從鏈表頭向后遍歷，其中指針p1指向當前遍歷的結點，指針p指向p1所指向結點的前k個結點，如果p1之前沒有k個結點，那么p指向表頭結點。用整型變量i表示當前遍歷了多少結點，當i>k時，指針p隨著每次遍歷，也向前移動一個結點。當遍歷完成時，p或者指向表頭結點，或者指向鏈表中倒數(shù)第k個位置上的結點。〔3〕算法描述：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個結點else{printf(“%\n”,p->data);return1;}}2.〔10年〕設將n(n,1)個整數(shù)存放到一維數(shù)組R中，試設計一個在時間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P〔0﹤P﹤n〕個位置，即將R中的數(shù)據(jù)由〔X0X1……Xn-1〕變換為〔XpXp+1……Xn-1

X0

X1……Xp-1〕要求：〔1〕給出算法的根本設計思想。〔2〕根據(jù)設計思想，采用C或C++或JAVA語言表述算法，關鍵之處給出注釋?！?〕說明你所設計算法的時間復雜度和空間復雜度分析：此題考查的是數(shù)組的操作，線性表的順序存儲的核心就是數(shù)組，因此此題實質上是考查的線性表的順序存儲的操作及其應用。做此題時要考慮算法的時間和空間復雜度。解法一：〔1〕算法的根本設計思想：可以將這個問題看做是把數(shù)組ab轉化成數(shù)組ba〔a代表數(shù)組的前p個元素，b代表數(shù)組中余下的n-p個元素〕，先將a逆置得到a-1b，再將b逆置得到a-1b-1，最后將整個a-1b-1逆置得到〔a-1b-1〕-1=ba。設reverse函數(shù)執(zhí)行將數(shù)組元素逆置的操作，對abcdefgh向左循環(huán)移動3〔p=3〕個位置的過程如下：reverse(0,p-1)得到cbadefgh；reverse(p,n-1)得到cbahgfde；reverse(0,n-1)得到defghabc。注：reverse中，兩個參數(shù)分別表示數(shù)組中待轉換元素的始末位置?！?〕算法描述：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〕上述算法中三個reverse函數(shù)的時間復雜度分別是O(p/2)、O((n-p)/2)、O(n/2)，故所設計算法的時間復雜度為O(n)，空間復雜度為O(1)。解法二：算法思想：創(chuàng)立大小為p的輔助數(shù)組S，將R中前p個整數(shù)依次暫存在S中，同時將R中后n-p個整數(shù)左移，然后將S中暫存的p個數(shù)依次放回到R中的后續(xù)單元。時間復雜度為O(n)，空間復雜度為O(p)。3.〔11年〕一個長度為L〔L>=1〕的生序列S，處在第┌L/2┐個位置的數(shù)稱為S的中位數(shù)，例如，假設序列S1=〔11,13,15,17,19〕，那么S1的中位數(shù)是15，兩個序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，假設S2=〔2,4,6,8,20〕，那么S1和S2的中位數(shù)是11?，F(xiàn)在有兩個等長升序序列A和B，試設計一個在時間和空間方面都盡可能高效的算法，找出兩個序列A和B的中位數(shù)。要求：〔1〕給出算法的根本設計思想?！?〕根據(jù)設計思想，采用C或C++或JAVA語言描述算法，關鍵之處給出注釋。分析：此題考查線性表的順序存儲，主要是線性表的根本操作的應用。做此題時要把握算法的效率?！?〕算法的根本設計思想如下：分別求出序列A和B的中位數(shù)，設為a和b，求序列A和B的中位數(shù)過程如下：1〕假設a=b，那么a或b即為所求中位數(shù)，算法結束；2〕假設a<b，那么舍棄序列A中較小的一半，同時舍棄序列B中較大的一半，要求舍棄的長度相等；3〕假設a>b，那么舍棄序列A中較大的一半，同時舍棄序列B中較小的一半，要求舍棄的長度相等；在保存的兩個升序序列中，重復過程1〕-3〕，直到兩個序列中只含一個元素時為止，較小者即為所求的中位數(shù)。〔2〕算法實現(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〕算法的時間復雜度為O(logn)，空間復雜度為O(1)。4.〔12年〕假定采用帶頭結點的單鏈表，如果有共同后綴，長度分別為len1和len2〔這個條件是我查了一些資料后加上的，網(wǎng)上給的資料這個題目不完整〕，那么可共享相同的后綴存儲空間，例如，“l(fā)oading”和“Beijing”，如以下圖所示。設str1和str2分別指向兩個單詞所在單鏈表的頭結點，鏈表結點結構為〔data，next〕，請設計一個時間上盡可能高效的算法，找出由str1和str2所指向兩個鏈表共同后綴的起始位置〔如圖中字符i所在結點的位置p〕。要求：〔1〕給出算法的根本設計思想。 〔2〕根據(jù)設計思想，采用C或C++或JAVA語言描述算法，關鍵之處給出注釋?！?〕說明你所設計算法的時間復雜度。分析：兩個單鏈表有公共結點，那么從公共結點開始，它們的next都指向同一個結點。由于每個單鏈表結點只有一個next域，因此，從第一個公共結點開始，之后它們所有的結點都是重合的，不可能再出現(xiàn)分叉。因此，我們判斷兩個鏈表是不是有重合的局部，只要分別遍歷兩個鏈表到最后一個結點。如果兩個尾結點是一樣的，說明它們有公共結點；否那么兩個鏈表沒有公共的結點。因為兩個鏈表長度不一定一樣，在順序遍歷兩個鏈表到尾結點時，并不能保證在兩個鏈表上同時到達尾結點。假設一個鏈表比另一個長k個結點，我們先在長的鏈表上遍歷k個結點，之后再同步遍歷，此時能夠保證同時到達最后一個結點。在遍歷中，第一個相同的結點就是第一個公共結點?！?〕算法思想：根據(jù)兩個單鏈表的長度，求出它們的長度之差；在長的單鏈表上先遍歷長度之差個結點；同步遍歷兩個單鏈表，直接找到相同的結點，假設有相同結點返回該節(jié)點，假設沒有那么一直到鏈表結束?！?〕算法實現(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〕由于每個表僅遍歷一遍，因此算法時間復雜度為O(len1+len2)，空間復雜度為O(1)。四、練習題〔一〕選擇題1．下述哪一條是順序存儲結構的優(yōu)點？〔A〕A．存儲密度大B．插入運算方便C．刪除運算方便D．可方便地用于各種邏輯結構的存儲表示2．下面關于線性表的表達中，錯誤的選項是哪一個？〔B〕A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B．線性表采用順序存儲，便于進行插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。3．線性表是具有n個〔C〕的有限序列〔n>0〕。A．表元素B．字符C．數(shù)據(jù)元素D．數(shù)據(jù)項E．信息項4．假設某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，那么利用〔A〕存儲方式最節(jié)省時間。A．順序表B．雙鏈表C．帶頭結點的雙循環(huán)鏈表D．單循環(huán)鏈表5．某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，那么采用〔D〕存儲方式最節(jié)省運算時間。A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表6．假設長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為〔C〕(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)7.對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為〔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〕以鏈接方式存儲時，訪問第i位置元素的時間復雜性為〔C〕。A．O〔i〕B．O〔1〕C．O〔n〕D．O〔i-1〕〔二〕綜合題1．掌握線性表中幾個最根本的操作算法〔1〕鏈表的建立頭插法建表voidreatelistf(linklist&head，intn){//逆序輸入n個數(shù)據(jù)元素，建立帶頭結點的單鏈表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;//修改第一個元素的指針值L->next=p;//修改表頭結點指針值}〔3〕線性表的合并順序表的合并：順序存儲的線性表la，lb的關鍵字為整數(shù)，元素非遞減有序，線性表空間足夠大，試編寫高效算法，將lb中元素合并到la中，使新的la的元素仍非遞減有序。分析：從后往前插入，防止移動元素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是否為空{la.elem[k]=lb.elem[j];k--;j--;}la.length=m+n;}鏈表的合并：把元素遞增排列的鏈表A和B合并為C，且C中元素遞減排列，使用原結點空間。分析：本算法的思想是，按從小到大的順序依次把A和B的元素插入新表的頭部pc處，因為合并以后是逆序，因此采用頭插法，最后處理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〕鏈表的拆分：設L為一單鏈表的頭指針，單鏈表的每個結點由一個整數(shù)域data和指針域next組成，整數(shù)在單鏈表中是無序的。設計算法，將鏈表中結點分成一個奇數(shù)鏈和一個偶數(shù)鏈，算法中不得申請新的結點空間。分析：利用原鏈表空間，在原鏈表的分解過程中新建鏈表。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．算法練習〔1〕試編寫在帶頭結點的單鏈表中刪除最小值結點的高效算法。voiddelete(linklistL){p=L->next;pre=L;q=p;while(p->next!=NULL)//找最小值元素，pre指向最小值的前驅{if(p->next->data<q->data){pre=p;q=p->next;}p=p->next;}pre->next=q->next;free(q);}分析：此算法的高效在于在循環(huán)過程中利用最小值結點的前驅指針進行比擬，比擬結束后直接保存了最小值結點的前驅，方便進行刪除操作?！?〕設單鏈表的表頭指針為h，結點結構由data和next兩個域構成，其中data域為字符型。寫出算法dc(h,n),判斷該鏈表的前n個字符是否中心對稱。例如xyx,xyyx都是中心對稱。分析：判斷鏈表中數(shù)據(jù)是否中心對稱，通常使用棧。將鏈表的前一半元素依次進棧。在處理鏈表的后一半元素時，當訪問到鏈表的一個元素后，就從棧中彈出一個元素，兩元素比擬，假設相等，那么將鏈表中下一元素與棧中再彈出元素比擬，直至鏈表到尾。這時假設棧是空棧，那么得出鏈表中心對稱的結論；否那么，當鏈表中一元素與棧中彈出元素不等時，結論為鏈表非中心對稱，結束算法的執(zhí)行。intdc〔Linklisth,intn〕{∥h是帶頭結點的n個元素單鏈表，鏈表中結點的數(shù)據(jù)域是字符。chars[];inti=1;∥i記結點個數(shù)，s字符棧p=h->next;∥p是鏈表的工作指針，指向待處理的當前元素。for〔i=1;i<=n/2;i++〕∥鏈表前一半元素進棧。{s[i]=p->data;p=p->next;}i--;∥恢復最后的i值if〔n%2==1〕p=p->next;∥假設n是奇數(shù)，后移過中心結點。while〔p!=null&&s[i]==p->data〕{i--;p=p->next;}∥測試是否中心對稱。if〔p==null〕return1;∥鏈表中心對稱elsereturn0;∥鏈表不中心對稱}∥算法結束?！?〕兩個單鏈表A和B,其頭指針分別為heada和headb，編寫一個過程從單鏈表A中刪除自第i個元素起的共len個元素，然后將單鏈表A插入到單鏈表B的第j個元素之前。分析：在單鏈表中刪除自第i個元素起的共len個元素，應從第1個元素起開始計數(shù)，記到第i個時開始數(shù)len個，然后將第i-1個元素的后繼指針指向第i+len個結點，實現(xiàn)了在A鏈表中刪除自第i個起的len個結點。這時應繼續(xù)查到A的尾結點，得到刪除元素后的A鏈表。再查B鏈表的第j個元素，將A鏈表插入之。插入和刪除中應注意前驅后繼關系，不能使鏈表“斷鏈”。另外，算法中應判斷i，len和j的合法性。LinklistDelInsert〔Linklistheada,Linklistheadb,inti,j,len〕{∥heada和headb均是帶頭結點的單鏈表。if〔i<1||len<1||j<1〕{printf〔“參數(shù)錯誤\n”〕；exit〔0〕；}∥參數(shù)錯，退出算法。p=heada；∥p為鏈表A的工作指針，初始化為A的頭指針k=0；∥計數(shù)while〔p!=null&&k<i-1〕∥查找第i個結點。{k++；p=p->next；}if〔p==null〕{printf〔“給的%d太大\n”,i〕；exit〔0〕；}∥i太大，退出算法q=p->next；∥q為工作指針，初始指向A鏈表第一個被刪結點。k=0；while〔q!=null&&k<len〕{k++；u=q，q=q->next；free〔u〕；}∥刪除結點，后移指針。if〔k<len〕{printf〔“給的%d太大\n”,len〕；exit〔0〕；}p->next=q；∥A鏈表刪除了len個元素。if(heada->next!=null)∥heada->next=null說明鏈表中結點均已刪除，無需往B表插入{while〔p->next!=null〕p=p->next；∥找A的尾結點。q=headb；∥q為鏈表B的工作指針。k=0；∥計數(shù)while〔q!=null&&k<j-1〕∥查找第j個結點。{k++；q=q->next；}∥查找成功時，q指向第j-1個結點if〔q==null〕{printf〔“給的%d太大\n”,j〕；exit〔0〕；}p->next=q->next；∥將A鏈表鏈入q->next=heada->next；∥A的第一元素結點鏈在B的第j-1個結點之后}//iffree〔heada〕；∥釋放A表頭結點。}〔4〕按1，3，5，...4，2的順序重排雙向循環(huán)鏈表L中的所有結點。分析：next鏈和pre鏈的調整分開進行。從前往后調整奇數(shù)鏈，然后從后往前調整偶數(shù)鏈，最后修改pre指針。voidReform(DuLinkList&L)

{

p=L->next;

while(p->next!=L&&p->next->next!=L)

{

p->next=p->next->next;

p=p->next;

}//從前往后調整奇數(shù)鏈

if(p->next==L)p->next=L->pre->pre;

elsep->next=L->pre;//根據(jù)鏈表中元素個數(shù)是奇數(shù)還是偶數(shù)處理表尾結點

p=p->next;

while(p->pre->pre!=L)

{

p->next=p->pre->pre;

p=p->next;

}//從后往前調整偶數(shù)鏈

p->next=L;

for(p=L;p->next!=L;p=p->next)p->next->pre=p;//重新修改前驅指針

L->pre=p;

}第3章棧和隊列一、考研知識點〔一〕棧和隊列的根本概念〔二〕棧和隊列的順序存儲結構〔三〕棧和隊列的鏈式存儲結構〔四〕棧和隊列的應用二、考查重點1．棧和隊列的特點，及其應用；2．棧的順序存儲和鏈式存儲的入棧和出棧操作，以及判斷棧的空和滿的條件；3．隊列的順序存儲和鏈式存儲的入隊和出隊操作，以及判斷隊列空和滿的條件；4．理解棧與遞歸的關系，利于對以后章節(jié)〔樹和圖〕的學習和復習。分析：棧和隊列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊列的根本概念，以及他們之間的區(qū)別。對于棧和隊列的存儲結構(包括順序存儲結構、鏈式存儲結構)要有較深的理解，對于棧和隊列的應用，例如，排隊問題、子程序調用問題、表達式問題等，要搞清楚。此章內容是線性表的深化，如果線性表理解的好，這一章就比擬容易。這一章小的知識點比擬多，一般容易出選擇題，從09-12年的考研真題來看，主要是考查棧和隊列的特點及其應用、棧的入棧出棧操作和隊列的入隊出隊操作、判斷棧和隊列的空與滿的條件。一般不會單獨出綜合題，如果出綜合題會將棧和隊列作為其他結構中一個小環(huán)節(jié)出題，比方和線性表結合，作為實現(xiàn)遞歸的工具和二叉樹結合等。三、考研真題〔一〕選擇題1.〔09年〕為解決計算機和打印機之間速度不匹配的問題，通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)，而打印機那么依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結構應該是〔〕。A.棧B.隊列C.樹D.圖分析：答案是B，此題可以認為考查隊列的特點，也可以看做是考查四種數(shù)據(jù)結構的特點。2.〔09年〕設棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進入棧S。假設每個元素出棧后立即進入隊列Q，且7個元素出隊順序是bdcfeag，那么棧S的容量至少是〔〕。A.1B.2C.3D.4分析：答案是C，此題考查棧的入棧和出棧操作和隊列的入隊和出隊操作。3.〔10年〕假設元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行。但不允許連續(xù)三次進行退棧工作，那么不可能得到的出棧序列是〔

〕。A.dcebfa

B.cbdaef

C.dbcaef

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

B.dbace

C.dbcae

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

B.4

C.5

D.6分析：答案是B，出棧序列必為d_c_b_a.e的順序不定，在任意一個“_”上都有可能。6．〔11年〕循環(huán)隊列存儲在一維數(shù)組A[0..n-1]中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。假設初始時隊列為空，且要求第1個進入隊列的元素存儲在A[0]處，那么初始時front和rear的值分別是A.0,0

B.0，n-1

C.n-1,0

D.n-1,n-1分析：答案是B，插入元素時，front不變，rear+1，而插入第一個元素之后，隊尾要指向尾元素，顯然，rear初始應該為n-1，front為07.〔12年〕操作符包括’+’、’-’、’*’、’/’、’(’和’)’。將中綴表達式a+b-a*((c+d)/e-f)+g轉換為等價的后綴表達式ab+acd+e/f-*-g+時，用棧來存放暫時還不能確定運算次序的操作符，假設棧初始為空，那么轉換過程中同時保存在棧中的操作符的最大個數(shù)是〔〕。A.5B.7C.8D.11分析：答案是A，此題考查棧的應用，將中綴表達式轉化為后綴表達式，轉化過程中利用兩個棧分別存放操作符和轉化后的表達式，要明確兩個棧中元素的進出情況。〔二〕綜合題10年考研綜合題的第二題如果用解法二，可以認為考查了隊列的根本操作，因為棧和隊列本身是線性結構，所以考試時可以綜合來考，和第2章的內容沒有太明顯的界限。四、練習題〔一〕選擇題1.一個棧的輸入序列為123…n，假設輸出序列的第一個元素是n，輸出第i〔1<=i<=n〕個元素是〔B〕。A.不確定B.n-i+1C.iD.n-i2.假設一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，那么第j個輸出元素是〔D〕。A.i-j-1B.i-jC.j-i+1D.不確定的3.輸入序列為ABC，可以變?yōu)镃BA時，經(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)隊列存儲在數(shù)組A[0..m]中，那么入隊時的操作為〔D〕。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)5.假設用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再參加兩個元素后，rear和front的值分別為〔B〕？A.1和5B.2和4C.4和2D.5和1〔二〕綜合題這一章一般不會單獨出綜合題，和其他章節(jié)的結合在相關章節(jié)中有例題表達。第5章數(shù)組和廣義表一、考研知識點特殊矩陣的壓縮存儲二、考查重點一維數(shù)組屬于線性表范疇，但多維數(shù)組不屬于線性表。在這方面，主要掌握數(shù)組的存儲結構，例如按行優(yōu)先、按列優(yōu)先等，某個元素存在的地址是什么。對于特殊矩陣(二維數(shù)組)的壓縮存儲原理也要搞清楚。重點考查特殊矩陣的壓縮存儲中矩陣中元素在存儲空間中地址的計算，只要掌握計算的方法就行，計算時需要特別注意矩陣首元素的下標值以及存儲空間首元素的下標值。三、考研真題近幾年此知識點沒有出題。四、練習題1.設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，那么a85的地址為〔B〕。A.13B.33C.18D.402.設有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內存首地址BA開始順序存放，當用以列為主存放時，元素A[5，8]的存儲首地址為(B)。A.BA+141B.BA+180C.BA+222D.BA+2253.假設以行序為主序存儲二維數(shù)組A=array[1..100，1..100]，設每個數(shù)據(jù)元素占2個存儲單元，基地址為10，那么LOC[5，5]=〔B〕。A.808B.818C.1010D.10204.將一個A[1..100，1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，A中元素A6665〔即該元素下標i=66，j=65〕，在B數(shù)組中的位置K為〔B〕。A.198B.195C.197D.1965.二維數(shù)組A的元素都是6個字符組成的串，行下標i的范圍從0到8，列下標j的范圈從1到10。從供選擇的答案中選出應填入以下關于數(shù)組存儲表達中〔〕內的正確答案?！?〕存放A至少需要〔E〕個字節(jié)；〔2〕A的第8列和第5行共占〔A〕個字節(jié)；〔3〕假設A按行存放，元素A[8，5]的起始地址與A按列存放時的元素〔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.設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章樹和二叉樹一、考研知識點〔一〕樹的根本概念〔二〕二叉樹1.二叉樹的定義及其主要特征2.二叉樹的順序存儲結構和鏈式存儲結構3.二叉樹的遍歷4.線索二叉樹的根本概念和構造〔三〕樹、森林1.樹的存儲結構2.森林與二叉樹的轉換3.樹和森林的遍歷〔四〕樹與二叉樹的應用哈夫曼〔Huffman〕樹和哈夫曼編碼二、考查重點1．二叉樹的定義與特點；2．二叉樹的性質及應用；3．二叉樹的遍歷〔遍歷過程及算法實現(xiàn)〕；4．線索二叉樹的構造；5．樹的存儲及樹與二叉樹的轉換；6．哈夫曼樹構造和哈夫曼編碼。分析：二叉樹和樹是兩種不同的概念，這一點是必須要搞清楚的。在這個局部，我們要掌握樹的定義、二叉樹的定義及主要特征(特殊的二叉樹、二叉樹的性質)。在二叉樹的順序存儲結構和鏈式存儲結構方面，特別是鏈式存儲結構，因為很多應用都是建立在鏈式存儲根底上，例如，二叉樹的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應用。在特殊的二叉樹中，完全二叉樹的概念是必須要搞清楚的，其次，線索二叉樹的根本概念和構造。多棵獨立的樹就組成了森林，樹的存儲結構和遍歷、森林的遍歷、樹和二叉樹的轉換、森林和二叉樹的轉換等知識，也要了解。最后就是樹的應用，通常會作為綜合應用類試題出現(xiàn)，包括等價類問題、哈夫曼(Huffman)樹和哈夫曼編碼等。此章知識點比擬多，并且每個知識點都可能出題，因此要做到對每一個知識點的理解和掌握，選擇題和綜合題都可以出，綜合題一般會現(xiàn)在二叉樹的遍歷及其應用、樹與二叉樹的轉換和哈夫曼樹的構造及哈夫曼編碼。三、考研真題〔一〕選擇題1.〔09年〕給定二叉樹如下圖。設N代表二叉樹的根，L代表根結點的左子樹，R代表根結點的右子樹。假設遍歷后的結點序列為3,7,5,6,1,2,4，那么其遍歷方式是〔〕。A.LRNB.NRLC.RLND.RNL分析：答案是D，此題考查二叉樹的遍歷。2.〔09年〕一棵完全二叉樹的第6層〔設根為第1層〕有8個葉結點，那么完全二叉樹的結點個數(shù)最多是〔〕。A.39B.52C.111D.119分析：答案是C，此題考察二叉樹的性質2以及完全二叉樹的概念。3.〔09年〕將森林轉換為對應的二叉樹，假設在二叉樹中，結點u是結點v的父結點的父結點，那么在原來的森林中，u和v可能具有的關系是〔〕。I.父子關系II.兄弟關系III.u的父結點與v的父結點是兄弟關系A.只有IIB.I和IIC.I和IIID.I、II和III分析：答案是B，此題考查樹與二叉樹的轉換，因為u是v的父結點，假設v是u的左子樹，那么u與v是父子關系，假設v是u的右子樹，那么u與v是兄弟關系。4.〔10年〕以下線索二叉樹中〔用虛線表示線索〕，符合后序線索樹定義的是〔

〕。分析：答案是D，此題考查二叉樹的線索化。5.〔10年〕在一棵度為4的樹T中，假設有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，那么樹T的葉節(jié)點個數(shù)是〔〕。A.41

B.82

C.113

D.122分析：答案是B，此題考查二叉樹的性質，利用二叉樹的性質3的證明思路進行求解。6.〔10年〕對n(n大于等于2)個權值均不相同的字符構成哈夫曼樹，關于該樹的表達中，錯誤的選項是〔〕。A.該樹一定是一棵完全二叉樹

B.樹中一定沒有度為1的結點C.樹中兩個權值最小的結點一定是兄弟結點

D.樹中任一非葉結點的權值一定不小于下一層任一結點的權值分析：答案是A，此題考查哈夫曼樹的構造，以及哈夫曼樹的特點。7．〔11年〕假設一棵完全二叉樹有768個結點，那么該二叉樹中葉結點的個數(shù)是〔〕。A.257

B.258

C.384

D.385分析：答案是C，考查二叉樹的性質，葉結點個數(shù)為你n那么度為2的結點個數(shù)為n-1，總結點個數(shù)為偶數(shù)，那么度為1的結點個數(shù)為1，因此2n=768。8．〔11年〕假設一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1，那么該二叉樹的中序遍歷序列不會是〔〕。A.1,2,3,4

B.2,3,4,1

C.3,2,4,1

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

B.116

C.1895

D.1896分析：答案是D，此題考查二叉樹和樹的轉換。考慮一種特殊的情況，設題意中的樹是如以下圖所示的結構，那么對應的二叉樹中僅有前115個葉結點有右孩子。10.〔年〕假設一棵二叉樹的前序遍歷序列為a,e,b,d,c，后序遍歷序列為b,c,d,e,a，那么根結點的孩子結點〔〕。A.只有eB.有e、bC.有e、cD.無法確定分析：答案為A。此題考查二叉樹的遍歷，根據(jù)我們的常識，由前序序列和后序序列不能確定二叉樹，但此題并不是確定二叉樹而是確定二叉樹的根結點的孩子結點，因為根結點可以確定，仔細分析前序和后序序列，可以判斷出孩子結點只有e，因此答案為A?！捕尘C合題1.〔12年〕設有6個有序表A、B、C、D、E、F，分別含有10、35、40、50、60和200個數(shù)據(jù)元素，各表中元素按升序排列。要求通過5次兩兩合并，將6個表最終合并成一個升序表，并在最壞情況下比擬的總次數(shù)到達最小。請答復以下問題?！?〕請寫出合并方案，并求出最壞情況下比擬的總次數(shù)。〔2〕根據(jù)你的合并過程，描述N〔N>=2〕個不等長升序表的合并策略，并說明理由。分析：根據(jù)排序中的歸并排序的思想，多個有序表通過兩兩歸并可以得到一個有序表，因為多個歸并段的長度不同，在進行兩兩歸并時要想減少比擬的次數(shù)，是先將元素少的表進行歸并，再歸并元素多的表。這樣這個問題就轉化為最優(yōu)二叉樹的構造問題，將6個有序表的長度看做6個葉子結點的權值，由此構造最優(yōu)二叉樹?！泊朔治鍪歉鶕?jù)個人理解做的，暫時沒有權威機構的標準答案〕四、練習題〔一〕選擇題1.一個具有1025個結點的二叉樹的高h為〔C〕。A．11B．10C．11至1025之間D．10至1024之間2．一棵二叉樹高度為h，所有結點的度或為0或為2，那么這棵二叉樹最少有(B)結點。A．2hB．2h-1C．2h+1D．h+13.對二叉樹的結點從1開始進行連續(xù)編號，要求每個結點的編號大于其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用(C)次序的遍歷實現(xiàn)編號。A．先序B．中序C．后序D．從根開始按層次遍歷4.某二叉樹的前序序列和后序序列正好相反，那么該二叉樹一定是〔C〕的二叉樹。A．空或只有一個結點B．任一結點無左子樹C．高度等于其結點數(shù)D．任一結點無右子樹5.假設X是二叉中序線索樹中一個有左孩子的結點，且X不為根，那么X的前驅為(C)。A.X的雙親B.X的右子樹中最左的結點C.X的左子樹中最右結點D.X的左子樹中最右葉結點6.一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(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〕二叉樹遍歷遞歸算法的應用求二叉樹中葉子結點的數(shù)目intLeafCount_BiTree(BitreeT){if(!T)return0;//空樹沒有葉子

elseif(!T->lchild&&!T->rchild)return1;elsereturnLeaf_Count(T->lchild)+Leaf_Count(T>rchild);}交換所有結點的左右子樹。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的結點為根的子樹深度。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.二叉樹非遞歸遍歷算法的應用〔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的結點，編寫算法輸出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;}

}}分析：二叉樹遍歷算法的應用中關鍵的一個環(huán)節(jié)是分析要實現(xiàn)相關功能應該選擇二叉樹的哪一種遍歷方式有利于實現(xiàn)，如以上兩個例子中分別選用二叉樹的層次遍歷和后序遍歷實現(xiàn)具體操作，主要對遍歷算法稍加處理就可以實現(xiàn)了。3．從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結構，將樹，森林轉化為二叉樹的根本目的是什么，并指出樹和二叉樹的主要區(qū)別。分析：樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質是一樣的，只是解釋不同，也就是說樹〔樹是森林的特例，即森林中只有一棵樹的特殊情況〕可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。4．如果給出了一個二叉樹結點的前序序列和中序序列，能否構造出此二叉樹?假設能，請證明之。假設不能，請給出反例。如果給出了一個二叉樹結點的前序序列和后序序列，能否構造出此二叉樹?假設能，請證明之。假設不能，請給出反例。分析：給定二叉樹結點的前序序列和對稱序〔中序〕序列，可以唯一確定該二叉樹。因為前序序列的第一個元素是根結點，該元素將二叉樹中序序列分成兩局部，左邊〔設l個元素〕表示左子樹，假設左邊無元素，那么說明左子樹為空；右邊〔設r個元素〕是右子樹，假設為空，那么右子樹為空。根據(jù)前序遍歷中“根-—左子樹—右子樹”的順序，那么由從第二元素開始的l個結點序列和中序序列根左邊的l個結點序列構造左子樹，由前序序列最后r個元素序列與中序序列根右邊的r個元素序列構造右子樹。由二叉樹的前序序列和后序序列不能唯一確定一棵二叉樹，因無法確定左右子樹兩局部。例如，任何結點只有左子樹的二叉樹和任何結點只有右子樹的二叉樹，其前序序列相同，后序序列相同，但卻是兩棵不同的二叉樹。5．給定一組數(shù)列〔15,8,10,21,6,19,3〕分別代表字符A,B,C,D,E,F,G出現(xiàn)的頻度，試表達建立哈夫曼樹的算法思想，畫出哈夫曼樹，給出各字符的編碼值，并說明這種編碼的優(yōu)點。分析：考查哈夫曼樹的構造和哈夫曼編碼，過程略。編碼的優(yōu)點是采用前綴編碼，出現(xiàn)頻度最高的字符編碼最短，減少編碼長度，減少出錯率。第7章圖一、考研知識點〔一〕圖的根本概念〔二〕圖的存儲及根本操作1.鄰接矩陣法2.鄰接表法〔三〕圖的遍歷1.深度優(yōu)先搜索2.廣度優(yōu)先搜索〔四〕圖的根本應用1.最小〔代價〕生成樹2.最短路徑3.拓撲排序4.關鍵路徑二、考查重點1．圖的根本概念及特點；2.圖的存儲結構〔鄰接矩陣和鄰接表〕；3．圖的深度優(yōu)先和廣度優(yōu)先遍歷；4．圖的應用〔最小生成樹的構造過程、拓撲序列的生成、最短路徑和關鍵路徑的求解過程〕。分析：在數(shù)據(jù)結構中，圖的結構是最復雜的，這里的概念也是最多的。我們要掌握圖的根本概念(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、最短路徑、關鍵路徑等)。圖的存儲及根本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無向圖的這2種存儲方法，要清楚圖的連通和存儲方法之間的關系。例如，一個頂點的出度和鄰接矩陣中1的個數(shù)有什么關系，等等。圖的遍歷方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，我們要掌握這2種遍歷方法的算法實現(xiàn)。給出一個具體的圖，要能知道它的遍歷次序。在數(shù)據(jù)結構課程中，圖的根本應用是最多的，也是最復雜的，我們要掌握這些應用的復雜度分析。要掌握的具體應用主要包括最小(代價)生成樹、最短路徑、拓撲排序、關鍵路徑。在給出的一個具體的圖中，我們要會利用條件，求出上述應用的結果。這一章的內容也比擬多，尤其大的知識點比擬多，容易出綜合題，特別是圖的應用。在理解最小生成樹、拓撲排序、最短路徑和關鍵路徑的求解的同時要注意和具體問題結合，一般不會直接考，會和具體問題結合來考，例如09年的考研題。這一章考算法的可能性不大，但那兩個最根本的遍歷算法最好掌握。三、考研真題〔一〕選擇題1.〔09年〕以下關于無向連通圖特性的表達中，正確的選項是〔〕。I.所有頂點的度之和為偶數(shù)II.邊數(shù)大于頂點個數(shù)減1III.至少有一個頂點的度為1A.只有IB.只有IIC.I和IID.I和III分析：答案是A，此題考查無向連通圖的特性。2.〔10年〕假設無向圖G-〔V.E〕中含7個頂點，那么保證圖G在任何情況下都是連通的，那么需要的邊數(shù)最少是〔〕。A.6

B.15

C.16

D.21分析：答案是C，此題考查無向連通圖的特點，解題時需要注意保證圖G在任何情況下都是連通的這句話，這是關鍵。因為要保證圖在任何情況下都連通，先考慮6個頂點全連通需要15條邊，加上一個頂點后，加上一條邊保證第七個頂點與圖連通，因此至少需要16條邊。3.〔10年〕對以下圖進行拓補排序，可以得到不同的拓補序列的個數(shù)是〔〕。A.4

B.3

C.2

D.1分析：答案是B，此題考查圖的拓撲排序。4．〔11年〕以下關于圖的表達中，正確的選項是〔〕。I．回路是簡單路徑II．存儲稀疏圖，用鄰接矩陣比鄰接表更省空間III．假設有向圖中存在拓撲序列，那么該圖不存在回路A.僅II

B.僅I、II

C.僅III

D.僅I、III分析：答案是C，此題考查圖的根本概念。回路對應于路徑，簡單回路對應于簡單路徑；II剛好說反了，III是拓撲有序的必要條件。5.〔12年〕對有n個結點，e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍歷，其算法時間復雜度是〔〕。A.O(n)B.O(e)C.O(n+e)D.O(n*e)分析：答案為C。此題考查有向圖的遍歷，只要清楚鄰接表的存儲方式，答案很直接。6.〔12年〕假設用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，那么關于該圖拓撲序列的結構是〔〕。A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一D.無法確定是否存在分析：答案為C。此題考查圖的鄰接矩陣存儲方式和拓撲排序。7.〔12年〕如下有向帶權圖，假設采用迪杰斯特拉算法求原點a到其他各頂點的最短路徑，得到的第一條最短路徑的目標頂點是b，第二條最短路徑的目標頂點是c，那么到其余各最短路徑的目標頂點依次是〔〕?！泊祟}暫時不完整，但題目比擬簡單，考察最短路徑的求解過程〕A.d,e,fB.f,e,dC.D.8.〔12年〕以下關于最小生成樹的說法中，正確的選項是〔〕。I.最小生成樹的代價唯一II.權值最小的邊一定會出現(xiàn)在所有的最小生成樹中III.用普里姆算法從不同頂點開始得到的最小生成樹一定相同IV.普里姆算法和克魯斯卡爾算法得到的最小生成樹總不相同A.僅IB.僅IIC.僅I、IIID.僅II、IV分析：此題考查最小生成樹的概念和構造方法，我認為I和II正確，可是答案沒有選項，因為題目是考生回憶的，是不是某個地方表達有錯誤？〔答案待定〕〔二〕綜合題1.〔09年〕帶權圖〔權值非負，表示邊連接的兩頂點間的距離〕的最短路徑問題是找出從初始頂點到目標頂點之間的一條最短路徑。假定從初始頂點到目標頂點之間存在路徑，現(xiàn)有一種解決該問題的方法：〔1〕設最短路徑初始時僅包含初始頂點，令當前頂點u為初始頂點；〔2〕選擇離u最近且尚未在最短路徑中的一個頂點v，參加到最短路徑中，修改當前頂點u=v；〔3〕重復步驟〔2〕，直到u是目標頂點為止。請問上述方法能否求得最短路徑？假設該方法可行，請證明之；否那么，請舉例說明。分析：此題考查最短路徑的求解思路，只是沒有直接考書上的最短路徑的求解過程，而是換個角度考查對最短路徑求解的理解。解答：該方法求得的路徑不一定是最短路徑。例如，對于以下圖所示的帶權圖，如果按照題中的原那么，從A到C的最短路徑為A->B->C，事實上其最短路徑為A->D->C。2．〔11年〕有6個頂點〔頂點編號為0-5〕的有向帶權圖G，其鄰接矩陣A為上三角矩陣，按行優(yōu)先為主序保存在如下的一維數(shù)組中。46∞∞∞5∞∞∞43∞∞33要求：〔1〕寫出圖G的鄰接矩陣A?！?〕畫出有向帶權圖G?！?〕求圖G的關鍵路徑，并計算該關鍵路徑的長度。解答：此題考查圖的鄰接矩陣的存儲以及關鍵路徑的求解，同時考查了特殊矩陣的壓縮存儲，主要是考查的圖的根本知識?！?〕圖G的鄰接矩陣A如下所示?！?〕有向帶權圖G如以下圖所示?！?〕關鍵路徑為0->1->2->3->5〔如以下圖粗線所示〕，長度為16。四、練習題〔一〕選擇題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)}，由頂點a開始對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的選項是〔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的拓撲序列中，假設頂點Vi在頂點Vj之前，那么以下情形不可能出現(xiàn)的是〔D〕。A．G中有弧<Vi，Vj>B．G中有一條從Vi到Vj的路徑C．G中沒有弧<Vi,Vj>D．G中有一條從Vj到Vi的路徑3.用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應的頂點，那么輸出的頂點序列是(B)。A．逆拓撲有序B．拓撲有序C．無序的4.下面哪一方法可以判斷出一個有向圖是否有環(huán)〔回路〕〔AB〕。A．深度優(yōu)先遍歷B.拓撲排序C.求最短路徑D.求關鍵路徑5.下面關于求關鍵路徑的說法不正確的選項是〔C〕。A．求關鍵路徑是以拓撲排序為根底的B．一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同C．一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差D．關鍵活動一定位于關鍵路徑上〔二〕綜合題1．給定n個村莊之間的交通圖，假設村莊i和j之間有道路，那么將頂點i和j用邊連接，邊上的Wij表示這條道路的長度，現(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應建在哪個村莊，才能使離醫(yī)院最遠的村莊到醫(yī)院的路程最短?分析：每個頂點到其余各頂點的最短路徑中最長的有n條，求這n條中最短的一條。2．設頂點a,b,c,d,e表示一個鄉(xiāng)的5個村莊，弧上的權值表示為兩村之間的距離；①求每個村莊到其它村莊的最短距離；②鄉(xiāng)內要建立一所醫(yī)院，問醫(yī)院設在哪個村莊才能使各村離醫(yī)院的距離較近。分析：每個頂點到其余各頂點最短路徑之和最短的一個。3．有6個村子，相互間道路的距離如下圖。擬合建一所小學，A處有小學生50人，B處40人，C處60人，C處20人，E處70人，F(xiàn)處90人，問小學應該建在哪個村子，是學生上學最為方便〔走的總路程最短〕。分析：此問題還是歸為最短路徑問題，考慮路徑的總體狀況。解答：先求出任意兩點間的最短路徑下表所示：ABCDEFA0267811B204569C640125D751014E862103F1195430將每行數(shù)字分別乘以各村小學生人數(shù)得下表：ABCDEFA0100300350400550B800160200240360C360240060120300D1401002002080E560420140700210F9908104503602700按列相加其總和最小的列所對應村子即是所求村子。4．某企業(yè)使用一臺設備，在每年年初，企業(yè)領導部門就要決定是購置新的，還是繼續(xù)使用舊的設備。假設購置新設備，就要支付一定的購置費用；假設繼續(xù)使用舊設備，那么需支付一定的維修費用。現(xiàn)在的問題是如何制定一個幾年之內的設備更新方案使得總支付費用最小。表1設備年初價格第1年第2年第3年第4年第5年1111121213表2維修費用使用年數(shù)0-11-22-33-44-5維修費用5681118分析：此問題同樣可以歸為最短路徑問題，假定每年年初都購置新設備，可以把每年年初作為一個頂點，任意兩個頂點之間的連線表示設備的使用情況，權值用使用過程中的費用表示，這樣可以構造一個圖，在圖中求從第一年年初到第五年末的最短路徑，路徑上的頂點就是設備更新方案。解答：設vi表示第i年購進一臺新設備，〔vi，vj〕表示設備由第i年初使用到第j年初，權值表示使用費用，得到以下圖：在圖中求由v1到v6的最短路徑得到兩條：v1-v3-v6和v1-v4-v6，因此設備的更新方案為在第1年和第3年年初更新設備或者是在第1年和第4年年初更新設備，總費用是53。5．下表給出了某工程各工序之間的優(yōu)先關系和各工序所需時間〔1〕畫出相應的AOE網(wǎng)〔2〕列出各事件的最早發(fā)生時間,最遲發(fā)生時間〔3〕找出關鍵路徑并指明完成該工程所需最短時間.工序代號ABCDEFGHIJKLMN所需時間15105081540300151206015302040先驅工作----A,BBC,DBEG,IEIF,IH,J,KLG分析：此題考查關鍵路徑的求解過程，求解過程略。第9章查找一、考研知識點〔一〕查找的根本概念〔二〕順序查找法〔三〕折半查找法〔四〕二叉排序樹〔五〕平衡二叉樹〔六〕B-樹及其根本操作、B+樹的根本概念〔七〕散列〔Hash〕表〔八〕查找算法的分析及應用二、考查重點1．順序表的查找及平均查找長度；2．有序表的查找〔折半查找〕及平均查找長度；3．二叉排序數(shù)的構造及查找效率分析；4．平衡二叉樹的構造；5．B-樹與B+樹的定義和特點；6．哈希表的構造〔哈希函數(shù)構造方法：除留余數(shù)法，處理沖突的方法：開放定址法和鏈地址法〕及平均查找長度。分析：在給定的數(shù)據(jù)集合中查找某個關鍵值就是查找，查找的根本方法主要有順序查找法、折半查找法、B-樹、散列(Hash)表及其查找?？嫉谋葦M多的是折半查找和散列表，我們要掌握它們的根本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等；二叉排序樹、平衡二叉樹的根本概念和應用，特別是二叉排序樹的根本性質和特點要能很好地理解。另外，我們要掌握各種查找算法的分析及應用，最好能把各種查找在查找成功、查找失敗的情況下的最好、平均、最壞的平均查找次數(shù)的計算方法搞清楚。這一章可以認為是線性表和二叉樹在查找中的應用，利用前面所學知識來解決新的問題，重點是分析各種查找方式下的時間效率，選擇題和綜合題都可以出。綜合題出哈希表的可能性比擬多，也有可能出算法題，這樣會和第2章線性表和第6章二叉樹結合來考，總之是和前面的內容有聯(lián)系的，一定要掌握各種查找方法的思想并能進行分析。三、考研真題〔一〕選擇題1.(09年)以下二叉排序樹中，滿足平衡二叉樹定義的是〔〕。分析：答案是B，此題考查平衡二叉樹的定義。2．〔09年〕以下表達中，不符合m階B樹定義要求的是〔〕。A.根結點最多有m棵子樹B.所有葉結點都在同一層上C.各結點內關鍵字均升序或降序排列D.葉結點之間通過指針鏈接分析：答案是D，此題考查B-樹的定義，題目出的不太嚴格，但是利用排除法可以得到答案。3.〔10年〕在以下所示的平衡二叉樹中插入關鍵字48后得到新平衡二叉樹，在新平衡二叉樹中，關鍵字37所在節(jié)點的左、右結點中保存的關鍵字分別是〔〕。A.13,48B.24,48C.24,53D.24,90分析：答案是C，此題考查平衡二叉樹的調整過程。4.〔10年〕一個長度為16的順序表L，其元素按關鍵字有序排列，假設采用折半查找法查找一個不存在的元素，那么比擬次數(shù)最多是〔〕。A.4

B.5

C.6

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