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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)考研真題及知識點(diǎn)解析考察目標(biāo)1. 理解數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。 2. 掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時間復(fù)雜度與空間復(fù)雜度的分析。 3. 能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)的基本原理和方法進(jìn)行問題的分析與求解，具備采用C、C+或Java語言設(shè)計與實(shí)現(xiàn)算法的能力。第2章 線性表一、考研知識點(diǎn)（一）線性表的定義和基本操作（二）線性表的實(shí)現(xiàn)1.順序存儲2.鏈?zhǔn)酱鎯?.線性表的應(yīng)用二、考研真題（一）選擇題近兩年第2章沒有考選擇題，因?yàn)榇苏轮饕蔷€性表的操作，而且又是這門課的一個基礎(chǔ)，考綜合題的可能性比較大

2、，而且可以和第3章、第9章和第10章的內(nèi)容結(jié)合來出題。1（11年）設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時間復(fù)雜度是（ ）。 x=2; while(x<n/2) x=2*x;A.O(logn)   B.O(n)   C.O(nlogn)    D.O(n2)分析：答案是A，此題考查的是算法時間復(fù)雜度的計算?？梢苑旁诘诙?，實(shí)際這內(nèi)容貫穿每一章內(nèi)容中算法的度量。（二）綜合題1.（09年）已知一個帶有表頭結(jié)點(diǎn)的單鏈表結(jié)點(diǎn)結(jié)構(gòu)為(data,link)，假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設(shè)計一個盡

3、可能高效的算法，查找鏈表中倒數(shù)第k個位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的data值，并返回1；否則，只返回0。要求：（1）描述算法的基本設(shè)計思想；（2）描述算法的詳細(xì)實(shí)現(xiàn)步驟；（3）根據(jù)設(shè)計思想和實(shí)現(xiàn)步驟，采用程序設(shè)計語言描述算法（使用C或C+或JAVA語言實(shí)現(xiàn)），關(guān)鍵之處給出簡要注釋。 分析：此題考查線性表的鏈?zhǔn)酱鎯Γ饕蔷€性表的基本操作的應(yīng)用。做此題時要把握算法的效率。（1）算法基本思想如下：從頭到尾遍歷單鏈表，并用指針p指向當(dāng)前結(jié)點(diǎn)的前k個結(jié)點(diǎn)。當(dāng)遍歷到鏈表的最后一個結(jié)點(diǎn)時，指針p所指向的結(jié)點(diǎn)即為所查找的結(jié)點(diǎn)。（2）詳細(xì)實(shí)現(xiàn)步驟：增加兩個指針變量和一個整型變量，從鏈

4、表頭向后遍歷，其中指針p1指向當(dāng)前遍歷的結(jié)點(diǎn)，指針p指向p1所指向結(jié)點(diǎn)的前k個結(jié)點(diǎn)，如果p1之前沒有k個結(jié)點(diǎn)，那么p指向表頭結(jié)點(diǎn)。用整型變量i表示當(dāng)前遍歷了多少結(jié)點(diǎn)，當(dāng)i>k時，指針p隨著每次遍歷，也向前移動一個結(jié)點(diǎn)。當(dāng)遍歷完成時，p或者指向表頭結(jié)點(diǎn)，或者指向鏈表中倒數(shù)第k個位置上的結(jié)點(diǎn)。（3）算法描述：int locate(Linklist list, int k)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)retur

5、n 0; /鏈表沒有k個結(jié)點(diǎn)else printf(“%n”,p->data); return 1;2.（10年）設(shè)將n(n,1)個整數(shù)存放到一維數(shù)組R中，試設(shè)計一個在時間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P（0Pn）個位置，即將R中的數(shù)據(jù)由（X0 X1 Xn-1）變換為（Xp Xp+1 Xn-1  X0  X1 Xp-1）要求：（1）給出算法的基本設(shè)計思想。（2）根據(jù)設(shè)計思想，采用C或C+或JAVA語言表述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度分析：此題考查的是數(shù)組的操作，線性表的順序存儲的核心就是數(shù)組，因此此題實(shí)

6、質(zhì)上是考查的線性表的順序存儲的操作及其應(yīng)用。做此題時要考慮算法的時間和空間復(fù)雜度。解法一：（1）算法的基本設(shè)計思想：可以將這個問題看做是把數(shù)組ab轉(zhuǎn)化成數(shù)組ba（a代表數(shù)組的前p個元素，b代表數(shù)組中余下的n-p個元素），先將a逆置得到a-1b，再將b逆置得到a-1b-1，最后將整個a-1b-1逆置得到（a-1b-1）-1=ba。設(shè)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。注：rever

7、se中，兩個參數(shù)分別表示數(shù)組中待轉(zhuǎn)換元素的始末位置。（2）算法描述：void reverse(int R, int low, int high)/將數(shù)組中從low到high的元素逆置 int temp; for(i=0;i<=(high-low)/2;i+) temp=Rlow+i; Rl0ow+i=Rhigh-i; Rhigh-i=temp;void converse(int R, int n, int p) reverse(R,0,p-1); reverse(R,p,n-1); reverse(R,0,n-1);（3）上述算法中三個reverse函數(shù)的時間復(fù)雜度分別是O(p/2)、O

8、(n-p)/2)、O(n/2)，故所設(shè)計算法的時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。解法二：算法思想：創(chuàng)建大小為p的輔助數(shù)組S，將R中前p個整數(shù)依次暫存在S中，同時將R中后n-p個整數(shù)左移，然后將S中暫存的p個數(shù)依次放回到R中的后續(xù)單元。時間復(fù)雜度為O(n)，空間復(fù)雜度為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。現(xiàn)在有兩個等長升序序列A

9、和B，試設(shè)計一個在時間和空間方面都盡可能高效的算法，找出兩個序列A和B的中位數(shù)。要求：（1）給出算法的基本設(shè)計思想。（2）根據(jù)設(shè)計思想，采用C或C+或JAVA語言描述算法，關(guān)鍵之處給出注釋。解答：此題考查線性表的順序存儲，主要是線性表的基本操作的應(yīng)用。做此題時要把握算法的效率。（1）算法的基本設(shè)計思想如下：分別求出序列A 和B的中位數(shù)，設(shè)為a和b，求序列A和B的中位數(shù)過程如下：1）若a=b，則a或b即為所求中位數(shù)，算法結(jié)束；2）若a<b，則舍棄序列A中較小的一半，同時舍棄序列B中較大的一半，要求舍棄的長度相等；3）若a>b，則舍棄序列A中較大的一半，同時舍棄序列B中較小的一半，要求

10、舍棄的長度相等；在保留的兩個升序序列中，重復(fù)過程1）-3），直到兩個序列中只含一個元素時為止，較小者即為所求的中位數(shù)。（2）算法實(shí)現(xiàn)如下：int M_search(int A,int B.int n) int s1=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(Am1=Bm2) return Am1; else if(Am1<Bm2) if(s1+d1)%2=0 s1=m1;d2=m2; elses1=m1+1;d2=m2; el

11、se if(s1+d1)%2=0 d1=m1;s2=m2; elsed1=m1+1;s2=m2; return As1<Bs2? As1:Bs2;（3）算法的時間復(fù)雜度為O(logn)，空間負(fù)責(zé)雜度為O(1)。三、考查重點(diǎn)1線性結(jié)構(gòu)的特點(diǎn)；2線性表在順序存儲及鏈?zhǔn)酱鎯Ψ绞较碌幕静僮骷捌鋺?yīng)用；3線性表的順序存儲及鏈?zhǔn)酱鎯η闆r下，其不同和優(yōu)缺點(diǎn)比較，及其各自適用的場合。單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針的各自好處；4能分析所寫算法的時間和空間復(fù)雜度。分析：線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中，其作用都是不可低估的。線性表一章小的知識點(diǎn)比較少，一般會出一

12、個綜合題，并且容易和第三章、第九章和第十章的內(nèi)容結(jié)合來考，注意對基本知識的理解，能夠利用書上的理論解決具體問題。學(xué)習(xí)過程中要注意多積累，多看、多寫一些相關(guān)算法。四、練習(xí)題（一）選擇題1下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)？（ A ）A存儲密度大 B插入運(yùn)算方便 C刪除運(yùn)算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲表示2下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ B ）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。3線性表是具有n個（ C ）的有限序列（n>0

13、）。 A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項(xiàng) E信息項(xiàng)4若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ A ）存儲方式最節(jié)省時間。A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表5某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ D ）存儲方式最節(jié)省運(yùn)算時間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表6若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（ C ）(1<=i<=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2

14、) 7. 對于順序存儲的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時間復(fù)雜度為（ C ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)8線性表（ a1,a2,an）以鏈接方式存儲時，訪問第i位置元素的時間復(fù)雜性為（ C ）。AO（i） BO（1） CO（n） DO（i-1）（二）綜合題1掌握線性表中幾個最基本的操作算法（1）逆置操作順序表的就地逆置void reverse(SqList &A) for(i=1,j=A.length;i<j;i+,j-)A.elemi<->A.elemj; /元素交換鏈表的就地逆置void

15、LinkList_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; /修改表頭結(jié)點(diǎn)指針值（2）線性表的合并順序表的合并：順序存儲的線性表la，lb的關(guān)鍵字為整數(shù)，元素非遞減有序，線性表空間足夠大，試編寫高效算法，將lb中元素合并到la中，使新的la的元素仍非遞減有序。分析：從后往前插入，避免移動元素void union (Sqlist la, S

16、qlist lb)m=la.length; n=lb.length;k=m+n; i=m; j=n; /循環(huán)指針賦值，從后往前比較while (i>0&&j>0)if (la.elemi>=lb.elemj)la.elemk=la.elemi; k-; i-;elsela.elemk=lb.elemj; k-; j-; if(j>0) /判斷l(xiāng)b是否為空 la.elemk=lb.elemj; k-; j-; la.length=m+n;鏈表的合并：把元素遞增排列的鏈表A和B合并為C，且C中元素遞減排列，使用原結(jié)點(diǎn)空間。分析：本算法的思想是，按從小到大的順

17、序依次把A和B的元素插入新表的頭部pc處，因?yàn)楹喜⒁院笫悄嫘颍虼瞬捎妙^插法，最后處理A或B的剩余元素。LinkList Union( LinkList A, LinkList B, LinkList C) 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->nex

18、t; 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; return C;（3）鏈表的拆分：設(shè)L為一單鏈表的頭指針，單鏈表的每個結(jié)點(diǎn)由一個整數(shù)域 data和指針域next組成，整數(shù)在單鏈表中是無序的。設(shè)計算法，將鏈表中結(jié)點(diǎn)分成一個奇數(shù)鏈和一個偶數(shù)鏈，算法中不

19、得申請新的結(jié)點(diǎn)空間。 分析：利用原鏈表空間，在原鏈表的分解過程中新建鏈表。void discreat( linklist L)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)的高效算法。voi

20、d delete ( linklist L)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òu)成，其中d

21、ata域?yàn)樽址汀懗鏊惴╠c(h,n),判斷該鏈表的前n個字符是否中心對稱。例如 xyx, xyyx都是中心對稱。分析：判斷鏈表中數(shù)據(jù)是否中心對稱，通常使用棧。將鏈表的前一半元素依次進(jìn)棧。在處理鏈表的后一半元素時，當(dāng)訪問到鏈表的一個元素后，就從棧中彈出一個元素，兩元素比較，若相等，則將鏈表中下一元素與棧中再彈出元素比較，直至鏈表到尾。這時若棧是空棧，則得出鏈表中心對稱的結(jié)論；否則，當(dāng)鏈表中一元素與棧中彈出元素不等時，結(jié)論為鏈表非中心對稱，結(jié)束算法的執(zhí)行。int dc（Linklist h,int n） h是帶頭結(jié)點(diǎn)的n個元素單鏈表，鏈表中結(jié)點(diǎn)的數(shù)據(jù)域是字符。char s; int i=1;i

22、記結(jié)點(diǎn)個數(shù)， s字符棧p=h->next;p是鏈表的工作指針，指向待處理的當(dāng)前元素。for（i=1;i<=n/2;i+） 鏈表前一半元素進(jìn)棧。 si=p->data; p=p->next; i-; 恢復(fù)最后的i值if（n%2=1）p=p->next;若n是奇數(shù)，后移過中心結(jié)點(diǎn)。while（p!=null && si=p->data）i-; p=p->next;測試是否中心對稱。if（p=null）return 1;鏈表中心對稱else return 0;鏈表不中心對稱算法結(jié)束。（3）已知兩個單鏈表A和B,其頭指針分別為heada和hea

23、db，編寫一個過程從單鏈表A中刪除自第i個元素起的共len個元素，然后將單鏈表A插入到單鏈表B的第j個元素之前。分析：在單鏈表中刪除自第i個元素起的共len個元素，應(yīng)從第1個元素起開始計數(shù)，記到第i個時開始數(shù)len個，然后將第i-1個元素的后繼指針指向第i+len個結(jié)點(diǎn)，實(shí)現(xiàn)了在A鏈表中刪除自第i個起的len個結(jié)點(diǎn)。這時應(yīng)繼續(xù)查到A的尾結(jié)點(diǎn)，得到刪除元素后的A鏈表。再查B鏈表的第j個元素，將A鏈表插入之。插入和刪除中應(yīng)注意前驅(qū)后繼關(guān)系，不能使鏈表“斷鏈”。另外，算法中應(yīng)判斷i，len和j的合法性。Linklist DelInsert（Linklist heada, Linklist headb

24、,int i,j,len）heada和headb均是帶頭結(jié)點(diǎn)的單鏈表。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個結(jié)點(diǎn)。k+；p=p->next；if（p=null）printf（“給的%d太大n”,i）；exit（0）； i太大，退出算法q=p->next；q為工作指針，初始指向A鏈表第一個被刪結(jié)點(diǎn)。k=0；while（q!=null &&

25、 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個元素。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；計數(shù)while（q!=null && k<j-1） 查找第j個結(jié)點(diǎn)。k+；q= q-

26、>next；查找成功時，q指向第j-1個結(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個結(jié)點(diǎn)之后/iffree（heada）；釋放A表頭結(jié)點(diǎn)。第3章 棧和隊列一、考研知識點(diǎn)（一）棧和隊列的基本概念（二）棧和隊列的順序存儲結(jié)構(gòu)（三）棧和隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（四）棧和隊列的應(yīng)用二、考研真題（一）選擇題1.（09年）為解決計算機(jī)和打印機(jī)之間速度不匹配的問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)，而打

27、印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（ ）。A.棧 B.隊列 C.樹 D.圖分析：答案是B，此題可以認(rèn)為考查隊列的特點(diǎn)，也可以看做是考查四種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)。2.（09年）設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。若每個元素出棧后立即進(jìn)入隊列Q，且7個元素出隊順序是bdcfeag，則棧S的容量至少是（ ）。A.1 B.2 C.3 D.4分析：答案是C，此題考查棧的入棧和出棧操作和隊列的入隊和出隊操作。3.（10年）若元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是（ 

28、0; ）。A.dcebfa   B.cbdaef    C.dbcaef    D.afedcb分析：答案是D，此題考查棧的入棧和出棧操作，但題目出的不是太嚴(yán)謹(jǐn)，嚴(yán)格說應(yīng)該是CD兩個答案。4.（10年）某隊列允許在其兩端進(jìn)行入隊操作，但僅允許在一端進(jìn)行出隊操作，則不可能得到的順序是（ C ）A.bacde    B.dbace     C.dbcae     D.ecbad分析：答案是C，此題考查隊列的入隊

29、和出隊操作。5（11年）元素a，b，c，d，e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可進(jìn)棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數(shù)是A.3    B.4     C.5     D.6分析：答案是B，出棧序列必為d_c_b_a.e的順序不定，在任意一個“_”上都有可能。6（11年）已知循環(huán)隊列存儲在一維數(shù)組A0.n-1中，且隊列非空時front和rear分別指向隊頭元素和對位元素。若初始時隊列為空，且要求低1個進(jìn)入隊列的元素存儲在0處，則初始時fro

30、nt和rear的值分別是A.0,0    B.0，n-1     C.n-1,0     D.n-1,n-1分析：答案是B，插入元素時，front不變，rear+1，而插入第一個元素之后，隊尾要指向尾元素，顯然，rear初始應(yīng)該為n-1，front為0（二）綜合題10年考研綜合題的第二題如果用解法二，可以認(rèn)為考查了隊列的基本操作，因?yàn)闂：完犃斜旧硎蔷€性結(jié)構(gòu)，所以考試時可以綜合來考，和第2章的內(nèi)容沒有太明顯的界限。三、考查重點(diǎn)1棧和隊列的特點(diǎn)，及其應(yīng)用2棧的順序存儲和鏈?zhǔn)酱鎯Φ娜霔：统鰲?/p>

31、操作，以及判斷棧的空和滿的條件；3隊列的順序存儲和鏈?zhǔn)酱鎯Φ娜腙牶统鲫牪僮?，以及判斷隊列空和滿的條件；4理解棧與遞歸的關(guān)系，利于對以后章節(jié)（樹和圖）的學(xué)習(xí)和復(fù)習(xí)。分析：此章內(nèi)容是線性表的深化，如果線性表理解的好，這一章就比較容易。這一章小的知識點(diǎn)比較多，一般容易出選擇題，從09和10年的考研真題來看，主要是考查站和隊列的特點(diǎn)及其應(yīng)用、棧的入棧出棧操作和隊列的入隊出對操作、判斷棧和隊列的空與滿的條件。一般不會單獨(dú)出綜合題，如果出綜合題會將棧和隊列作為其他結(jié)構(gòu)中一個小環(huán)節(jié)出題，比如和線性表結(jié)合，作為實(shí)現(xiàn)遞歸的工具和二叉樹結(jié)合等。四、練習(xí)題（一）選擇題1. 一個棧的輸入序列為123n，若輸出序列的第

32、一個元素是n，輸出第i（1<=i<=n）個元素是（ B ）。A.不確定 B.n-i+1 C.i D.n-i2. 若一個棧的輸入序列為1,2,3,n，輸出序列的第一個元素是i，則第j個輸出元素是（ D ）。A. i-j-1 B. i-j C. j-i+1 D. 不確定的3. 輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為（ B ）。A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,popC. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop4.循環(huán)隊列存儲

33、在數(shù)組A0.m中，則入隊時的操作為（ D ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 5. 若用一個大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（ B ）？A. 1和 5 B. 2和4 C. 4和2 D. 5和1 （二）綜合題這一章一般不會單獨(dú)出綜合題，和其他章節(jié)的結(jié)合在相關(guān)章節(jié)中有例題體現(xiàn)。第5章 數(shù)組和廣義表一、考研知識點(diǎn)特殊矩陣的壓縮存儲二、考研真題近

34、兩年此知識點(diǎn)沒有出題。三、考查重點(diǎn)分析：重點(diǎn)考查特殊矩陣的壓縮存儲中矩陣中元素于在存儲空間中地址的計算，只要掌握計算的方法就行，計算時需要特別特別主要矩陣首元素的下標(biāo)值以及存儲空間首元素的下標(biāo)值。四、練習(xí)題1.設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯?，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（ B ）。A.13 B.33 C.18 D.402. 設(shè)有數(shù)組Ai,j，數(shù)組的每個元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A5，8的存儲首地址為( B )。A.BA+141 B

35、.BA+180 C.BA+222 D.BA+2253. 假設(shè)以行序?yàn)橹餍虼鎯ΧS數(shù)組A=array1.100，1.100，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC5，5=（ B ）。A.808 B.818 C.1010 D.10204. 將一個A1.100，1.100的三對角矩陣，按行優(yōu)先存入一維數(shù)組B1298中，A中元素A6665（即該元素下標(biāo)i=66，j=65），在B數(shù)組中的位置K為（ B ）。A. 198 B. 195 C. 197 D. 1965. 二維數(shù)組A的元素都是6個字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圈從1到10。從供選擇的答案中選出應(yīng)填入下列關(guān)于數(shù)組

36、存儲敘述中（）內(nèi)的正確答案。（1）存放A至少需要（ E ）個字節(jié)；（2）A的第8列和第5行共占（ A ）個字節(jié)；（3）若A按行存放，元素A8，5的起始地址與A按列存放時的元素（ B ）的起始地址一致。（1）A.90 B.180 C.240 D.270 E.540（2）A.108 B.114 C.54 D.60 E.150（3）A.A8,5 B.A3,10 C.A5,8 D. A0,96. 設(shè)A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數(shù)組B1.n(n+1)/2中，對上述任一元素aij(1i，jn，且ij)在B中的位置為( B )。A.i(i-l)/2+j B.j

37、(j-l)/2+i C.j(j-l)/2+i-1 D.i(i-l)/2+j-1第6章 樹和二叉樹一、考研知識點(diǎn)（一）樹的概念（二）二叉樹1.二叉樹的定義及其主要特征2.二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)3.二叉樹的遍歷4.線索二叉樹的基本概念和構(gòu)造（三）樹、森林1.樹的存儲結(jié)構(gòu)2.森林與二叉樹的轉(zhuǎn)換3.樹和森林的遍歷（四）樹與二叉樹的應(yīng)用哈夫曼（Huffman）樹和哈夫曼編碼二、考研真題（一）選擇題1.（09年）給定二叉樹如圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3,7,5,6,1,2,4，則其遍歷方式是（ ）。A.LRN B.NRL C.R

38、LN D.RNL分析：答案是D，此題考查二叉樹的遍歷。2.（09年）已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個數(shù)最多是（ ）。A.39 B.52 C.111 D.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ǔ).只有II B.I和II C.I和III D.I、II和III分析：答案是B，此題考查樹與二叉樹的轉(zhuǎn)換，因?yàn)閡是v的父結(jié)點(diǎn)，若v是u的左

39、子樹，則u與v是父子關(guān)系，若v是u的右子樹，則u與v是兄弟關(guān)系。4.（10年）下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（  ）。分析：答案是D，此題考查二叉樹的線索化。5.（10年）在一棵度為4的樹T中，若有20個度為4的結(jié)點(diǎn)，10個度為3的結(jié)點(diǎn)，1個度為2的結(jié)點(diǎn)，10個度為1的結(jié)點(diǎn)，則樹T的葉節(jié)點(diǎn)個數(shù)是（ ）。A.41     B.82   C.113   D.122分析：答案是B，此題考查二叉樹的性質(zhì)，利用二叉樹的性質(zhì)3的證明思路進(jìn)行求解。6.（10年）對n(n大于等于2)個權(quán)值均不

40、相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（ ）。A.該樹一定是一棵完全二叉樹  B.樹中一定沒有度為1的結(jié)點(diǎn)C.樹中兩個權(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個結(jié)點(diǎn)，則該二叉樹中葉結(jié)點(diǎn)的個數(shù)是（ ）。A.257     B.258   C.384   D.385分析：答案是C，考查二叉樹的性質(zhì)，葉結(jié)點(diǎn)個數(shù)為你n則度為2的結(jié)點(diǎn)個數(shù)為n-1，總結(jié)

41、點(diǎn)個數(shù)為偶數(shù)，則度為1的結(jié)點(diǎn)個數(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，考查二叉樹的遍歷。此題可以用畫圖的方式進(jìn)行判斷。9（11年）已知一棵有2011個結(jié)點(diǎn)的樹，其葉結(jié)點(diǎn)個數(shù)116，該樹對應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)個數(shù)是（ ）。A.115   B.116  

42、 C.1895   D.1896分析：答案是D，此題考查二叉樹和樹的轉(zhuǎn)換?？紤]一種特殊的情況，設(shè)題意中的樹是如下圖所示的結(jié)構(gòu)，則對應(yīng)的二叉樹中僅有前115個葉結(jié)點(diǎn)有右孩子。（二）綜合題近兩年沒有考查二叉樹的題目，如果考的話一般應(yīng)該是二叉樹的遍歷和哈夫曼樹以及哈夫曼編碼。三、考查重點(diǎn)1二叉樹的定義與特點(diǎn)；2二叉樹的性質(zhì)及應(yīng)用；3二叉樹的遍歷（遍歷過程及算法實(shí)現(xiàn)）；4線索二叉樹的構(gòu)造；5樹的存儲及樹與二叉樹的轉(zhuǎn)換；6哈夫曼樹構(gòu)造和哈夫曼編碼。分析：此章知識點(diǎn)比較多，并且每個知識點(diǎn)都可能出題，因此要做到對每一個知識點(diǎn)的理解和掌握，選擇題和綜合題都可以出。雖然近兩年沒有出綜合題，同

43、學(xué)們也不要忽視，綜合題一般會現(xiàn)在二叉樹的遍歷及其應(yīng)用、樹與二叉樹的轉(zhuǎn)換和哈夫曼樹的構(gòu)造及哈夫曼編碼。四、練習(xí)題（一）選擇題1.一個具有1025個結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（ C ）。A11 B10 C11至1025之間 D10至1024之間2一棵二叉樹高度為h，所有結(jié)點(diǎn)的度或?yàn)?或?yàn)?，則這棵二叉樹最少有( B )結(jié)點(diǎn)。A2h B2h-1 C2h+1 Dh+13.對二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點(diǎn)的編號大于其左、右孩子的編號，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用( C )次序的遍歷實(shí)現(xiàn)編號。A先序 B中序 C后序 D從根開始按層次遍歷4.某二叉樹的前序序列和后

44、序序列正好相反，則該二叉樹一定是（ C ）的二叉樹。A空或只有一個結(jié)點(diǎn) B任一結(jié)點(diǎn)無左子樹 C高度等于其結(jié)點(diǎn)數(shù) D任一結(jié)點(diǎn)無右子樹5.若X是二叉中序線索樹中一個有左孩子的結(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.一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是( B )。A.0 B.1 C.2 D.不確定（二）綜合題1.二叉樹的基本遍歷算法（1）二叉樹前序、中序、后序和層次遍歷的非遞歸算法前序void PreOrder(Bitree T)InitStack(S); Push(S,T

45、);   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);    中序void InOrder(Bitree T)InitStack(S); p=T;  while(!StackEmpty(S)|p!=NULL)while(p!=NULL) push(S

46、,p); p=p->lchild; if(!StackEmpty(S) pop(S,p);   visit(p->data); p=p->rchild;       后序void PostOrder(Bitree T)Bitree stack, p; int tag, top=0; p=T; while(top>0|p!=NULL)  while(p!=NULL) top+; stacktop=p; tagtop=0; p=p->lchild; if(top>0) p=stack

47、top; while(tagtop=1) top-; visit(p->data); p=stackto    if(top>0) p=stacktop; p=p->rchild; tagtop=1;       層次void LayerOrder(Bitree T) InitQueue(Q);   EnQueue(Q,T);  while(!QueueEmpty(Q)  DeQueue(Q,p);    visit(p->data);

48、60;   if(p->lchild) EnQueue(Q,p->lchild);    if(p->rchild) EnQueue(Q,p->rchild);  （2）二叉樹遍歷遞歸算法的應(yīng)用求二叉樹中葉子結(jié)點(diǎn)的數(shù)目int LeafCount_BiTree(Bitree T)if(!T) return 0; /空樹沒有葉子  else if(!T->lchild&&!T->rchild) return 1; else return Leaf_Count(T->lch

49、ild)+Leaf_Count(T>rchild);交換所有結(jié)點(diǎn)的左右子樹。void Bitree_Revolute(Bitree T) 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)為根的子樹深度。int Get_Sub_Depth(Bitree T,int x)if(T->data=x)

50、0; printf("%dn",Get_Depth(T);     exit 1;   elseif(T->lchild) Get_Sub_Depth(T->lchild,x);if(T->rchild) Get_Sub_Depth(T->rchild,x); int Get_Depth(Bitree T)if(!T) return 0;  else  m=Get_Depth(T->lchild);    n=Get_Depth(T->rchild)

51、;    return (m>n?m:n)+1;  判斷兩棵樹是否相似的遞歸算法。int Bitree_Sim(Bitree B1,Bitree B2)if(!B1&&!B2) return 1;  else if(B1&&B2) return(Bitree_Sim(B1->lchild,B2->lchild) &&Bitree_Sim(B1->rchild,B2->rchild)else return 0;2.二叉樹非遞歸遍歷算法的應(yīng)用（1）判斷一二叉樹是否為完全二

52、叉樹。int Full_Bitree(Bitree T)InitQueue(Q); flag=0; EnQueue(Q,T); while(!QueueEmpty(Q)      DeQueue(Q,p);    if(!p) flag=1;    else if(flag) return 0;   else      EnQueue(Q,p->lchild);      EnQu

53、eue(Q,p->rchild);       return 1;（2）在二叉樹中查找值為x的結(jié)點(diǎn)，編寫算法輸出x的所有祖先。void PostOrder(Bitree T，int x)Bitree stack, p;int tag, top=0; p=T;while(top>0|p!=NULL)while(p!=NULL&&p->data!=x) top+; stacktop=p; tagtop=0; p=p->lchild; if(p->data=x) printf(“”);for(i=1;i<=t

54、op;i+) printf(stacki->data);return;while(tagtop=1&&top>1)top-;if(top>0) p=stacktop; p=p->rchild; tagtop=1;   分析：二叉樹遍歷算法的應(yīng)用中關(guān)鍵的一個環(huán)節(jié)是分析要實(shí)現(xiàn)相關(guān)功能應(yīng)該選擇二叉樹的哪一種遍歷方式有利于實(shí)現(xiàn)，如以上兩個例子中分別選用二叉樹的層次遍歷和后序遍歷實(shí)現(xiàn)具體操作，主要對遍歷算法稍加處理就可以實(shí)現(xiàn)了。3從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。分析：樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。4如果給出了一個二叉樹結(jié)點(diǎn)的前序序列和中序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例