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

1、-WORD格式 - 專業(yè)資料 - 可編輯 -數(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è)計(jì)與實(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ù)雜度的計(jì)算。可以放在第二章，實(shí)際這內(nèi)容貫穿每一章內(nèi)容中算法的度量。（二）綜合題1. （ 09 年）已知一個帶有表頭結(jié)點(diǎn)的單鏈表結(jié)點(diǎn)結(jié)構(gòu)為(data,link)，假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請?jiān)O(shè)計(jì)一個盡可能高效的算法，查找鏈表中倒數(shù)第 k 個位置上的結(jié)點(diǎn) （

3、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語言實(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）算法描述：-WORD格式 - 專業(yè)資料 - 可編輯 -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>

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

6、數(shù)組的操作， 線性表的順序存儲的核心就是數(shù)組， 因此此題實(shí)質(zhì)上是考查的線性表的順序存儲的操作及其應(yīng)用。做此題時要考慮算法的時間和空間復(fù)雜度。解法一：（ 1）算法的基本設(shè)計(jì)思想：可以將這個問題看做是把數(shù)組ab 轉(zhuǎn)化成數(shù)組ba（ a 代表數(shù)組的前 p 個元素， b 代表數(shù)組中余下的 n-p個元素），先將 a 逆置得到 a-1 b，再將 b 逆置得-1 -1-1 -1-1 -1-1函數(shù)執(zhí)行將數(shù)組元素逆置的到 a b ，最后將整個a b 逆置得到（ a b） =ba。設(shè) reverse操作，對 abcdefgh 向左循環(huán)移動3（ p=3）個位置的過程如下：reverse(0,p-1)得到 cbadef

7、gh ；reverse(p,n-1)得到 cbahgfde ；reverse(0,n-1)得到 defghabc 。注： reverse中，兩個參數(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;-WORD格式 - 專業(yè)資料 - 可編輯 -Rhigh-i=temp;void converse(int R, int n, int p)rev

8、erse(R,0,p-1);reverse(R,p,n-1);reverse(R,0,n-1);（ 3）上述算法中三個reverse函數(shù)的時間復(fù)雜度分別是O(p/2) 、O(n-p)/2)、O(n/2) ，故所設(shè)計(jì)算法的時間復(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 的中位

9、數(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，試設(shè)計(jì)一個在時間和空間方面都盡可能高效的算法，找出兩個序列 A 和 B 的中位數(shù)。要求：（ 1）給出算法的基本設(shè)計(jì)思想。（ 2）根據(jù)設(shè)計(jì)思想，采用 C 或 C+ 或 JAVA 語言描述算法，關(guān)鍵之處給出注釋。解答：此題考查線性表的順序存儲， 主要是線性表的基本操作的應(yīng)用。 做此題時要把握算法的效率。（ 1）算法的基本設(shè)計(jì)思想如下：分別求出序列

10、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 中較小的一半，要求舍棄的長度相等；在保留的兩個升序序列中，重復(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;/ 分別

11、表示序列 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)-WORD格式 - 專業(yè)資料 - 可編輯 -if(s1+d1)%2=0s1=m1;d2=m2;elses1=m1+1;d2=m2;elseif(s1+d1)%2=0d1=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)的特

12、點(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)比較少，一般會出一個綜合題，并且容易和第三章、第九章和第十章的內(nèi)容結(jié)合來考， 注意對基本知識的理解， 能夠利用書上的理論解決具體問題。 學(xué)習(xí)過程中要注意多積累，多看、多寫一些相關(guān)算法。四、練習(xí)題（一）選擇題1下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)？（A）A存儲密度大B

13、插入運(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）。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某線性表中最常用的操作是在最后一個元素之后插

14、入一個元素和刪除第一個元素，則采用（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)7.對于順序存儲的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時間復(fù)雜度為（C）。-WORD格式 - 專業(yè)資料 - 可編輯 -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 位置

15、元素的時間復(fù)雜性為（ C ）。A O（i ）B O（ 1）C O（ n）D O（ i-1 ）（二）綜合題1掌握線性表中幾個最基本的操作算法（ 1）逆置操作順序表的就地逆置void reverse(SqList &A)for(i=1,j=A.length;i<j;i+,j-)A.elemi<->A.elemj; /元素交換鏈表的就地逆置void LinkList_reverse(Linklist &L)p=L->next; q=p->next;while (q)r=q->next;q->next=p;p=q; q=r;L->next

16、->next=NULL; /修改第一個元素的指針值L->next=p;/修改表頭結(jié)點(diǎn)指針值（ 2）線性表的合并順序表的合并：順序存儲的線性表la ，lb 的關(guān)鍵字為整數(shù)，元素非遞減有序，線性表空間足夠大， 試編寫高效算法，將 lb 中元素合并到la 中，使新的 la 的元素仍非遞減有序。分析：從后往前插入，避免移動元素void union (Sqlist la, Sqlist lb)m=la.length; n=lb.length;k=m+n; i=m; j=n;/循環(huán)指針賦值，從后往前比較while (i>0&&j>0)if (la.elemi>

17、=lb.elemj)la.elemk=la.elemi; k-; i-;elsela.elemk=lb.elemj; k-; j-; if(j>0)/判斷 lb 是否為空 la.elemk=lb.elemj; k-; j-; la.length=m+n;-WORD格式 - 專業(yè)資料 - 可編輯 -鏈表的合并：把元素遞增排列的鏈表A 和 B 合并為 C，且 C 中元素遞減排列，使用原結(jié)點(diǎn)空間。分析：本算法的思想是， 按從小到大的順序依次把A和 B 的元素插入新表的頭部pc 處，因?yàn)楹喜⒁院笫悄嫘?，因此采用頭插法，最后處理A 或 B 的剩余元素。LinkList Union( LinkLis

18、t 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;elser=pb->next; pb->next=C->next;C->next=pb; pb=r;while(pa!=null)r=pa->next; pa->

19、;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è)計(jì)算法，將鏈表中結(jié)點(diǎn)分成一個奇數(shù)鏈和一個偶數(shù)鏈，算法中不得申請新的結(jié)點(diǎn)空間。分析：利用原鏈表空間，在原鏈表的分解過程中新建鏈表。void discreat( linklist L)s=L->next;p=L;p-&

20、gt;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)的高效算法。void delete ( linklist L)-WORD格式 - 專業(yè)資料 - 可編輯 -p=L->next; pre=L; q=p;while (p->next!=NU

21、LL)/找最小值元素，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)成，其中data 域?yàn)樽址?。寫出算法dc(h,n),判斷該鏈表的前n 個字符是否中心對稱。例如xyx, xyyx都是中心對稱。分析： 判斷鏈表中

22、數(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記結(jié)點(diǎn)個數(shù)，s 字符棧p=h->next;p是鏈表的工作指針，指向待處理的當(dāng)前元素。for （ i=1;i<

23、=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 和 headb，編寫一個過程從單鏈表A 中刪除自第i 個元素起的共len 個元素，

24、 然后將單鏈表A 插入到單鏈表B 的第 j 個元素之前。分析：在單鏈表中刪除自第i 個元素起的共len 個元素，應(yīng)從第1 個元素起開始計(jì)數(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,in

25、t i,j,len） heada 和 headb 均是帶頭結(jié)點(diǎn)的單鏈表。if （ i<1 | len<1 | j<1）-WORD格式 - 專業(yè)資料 - 可編輯 -printf （“參數(shù)錯誤 n”）； exit （0）； 參數(shù)錯，退出算法。p=heada；p為鏈表 A 的工作指針，初始化為 A 的頭指針k=0；計(jì)數(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

26、；q 為工作指針，初始指向A 鏈表第一個被刪結(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 個元素。if(heada- >next!=null)heada ->next=null說明鏈表中結(jié)點(diǎn)均已刪除，無需往 B表插入while （ p->next!=null）p= p->next；找 A 的尾

27、結(jié)點(diǎn)。q=headb；q 為鏈表 B 的工作指針。k=0；計(jì)數(shù)while （ q!=null && k<j-1） 查找第j 個結(jié)點(diǎn)。k+ ；q= q->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章 棧和隊(duì)列一、考研知識點(diǎn)（一）棧和隊(duì)列的基本概念（二）棧和

28、隊(duì)列的順序存儲結(jié)構(gòu)（三）棧和隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（四）棧和隊(duì)列的應(yīng)用二、考研真題（一）選擇題1. （ 09 年）為解決計(jì)算機(jī)和打印機(jī)之間速度不匹配的問題，通常設(shè)置一個打印數(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。若每個元-WORD格式 - 專業(yè)資料 - 可編輯 -素出棧后立即進(jìn)入隊(duì)列Q，且 7 個元素出隊(duì)順序是bdcfeag ，則

29、棧 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兩個答案。4. （ 10 年）某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，則不可能得到的順序是（ C ）A.bacdeB.dbaceC.dbcaeD.ecbad分析：答案是

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

31、1,n-1分析：答案是 B，插入元素時， front 不變， rear+1 ，而插入第一個元素之后，隊(duì)尾要指向尾元素，顯然， rear 初始應(yīng)該為 n-1 ， front 為 0（二）綜合題10 年考研綜合題的第二題如果用解法二，可以認(rèn)為考查了隊(duì)列的基本操作，因?yàn)闂：完?duì)列本身是線性結(jié)構(gòu)，所以考試時可以綜合來考，和第2 章的內(nèi)容沒有太明顯的界限。三、考查重點(diǎn)1棧和隊(duì)列的特點(diǎn)，及其應(yīng)用2棧的順序存儲和鏈?zhǔn)酱鎯Φ娜霔：统鰲２僮鳎约芭袛鄺５目蘸蜐M的條件；3隊(duì)列的順序存儲和鏈?zhǔn)酱鎯Φ娜腙?duì)和出隊(duì)操作，以及判斷隊(duì)列空和滿的條件；4理解棧與遞歸的關(guān)系，利于對以后章節(jié)（樹和圖）的學(xué)習(xí)和復(fù)習(xí)。分析： 此章內(nèi)容是

32、線性表的深化，如果線性表理解的好，這一章就比較容易。這一章小的知識點(diǎn)比較多，一般容易出選擇題，從 09 和 10 年的考研真題來看，主要是考查站和隊(duì)列的特點(diǎn)及其應(yīng)用、 棧的入棧出棧操作和隊(duì)列的入隊(duì)出對操作、判斷棧和隊(duì)列的空與滿的條件。一般不會單獨(dú)出綜合題，如果出綜合題會將棧和隊(duì)列作為其他結(jié)構(gòu)中一個小環(huán)節(jié)出題，比如和線性表結(jié)合，作為實(shí)現(xiàn)遞歸的工具和二叉樹結(jié)合等。四、練習(xí)題（一）選擇題1.一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i （ 1<=i<=n ）個元素是（B）。A. 不確定B.n-i+1C.iD.n-i2. 若一個棧的輸入序列為 1,2,3, ,n ，輸出

33、序列的第一個元素是 i ，則第 j 個輸出元素是（ D ）。A. i-j-1B. i-jC. j-i+1D.不確定的3.輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為（B）。-WORD格式 - 專業(yè)資料 - 可編輯 -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ì)列存儲在數(shù)組A0.m中，則入隊(duì)時的操作為（D）。A. rear=rear+1B. rear=(rear+1) mod (m-1)C.

34、rear=(rear+1) mod mD. rear=(rear+1)mod(m+1)5.若用一個大小為6 的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear和 front的值分別為0 和 3，當(dāng)從隊(duì)列中刪除一個元素，再加入兩個元素后，rear 和 front的值分別為（B）？A.1 和5B.2和4C.4和2D.5和1（二）綜合題這一章一般不會單獨(dú)出綜合題，和其他章節(jié)的結(jié)合在相關(guān)章節(jié)中有例題體現(xiàn)。第 5 章 數(shù)組和廣義表一、考研知識點(diǎn)特殊矩陣的壓縮存儲二、考研真題近兩年此知識點(diǎn)沒有出題。三、考查重點(diǎn)分析：重點(diǎn)考查特殊矩陣的壓縮存儲中矩陣中元素于在存儲空間中地址的計(jì)算，只要掌握計(jì)算的方法就行， 計(jì)算時需要特

35、別特別主要矩陣首元素的下標(biāo)值以及存儲空間首元素的下標(biāo)值。四、練習(xí)題1. 設(shè)有一個 10 階的對稱矩陣 A，采用壓縮存儲方式， 以行序?yàn)橹鞔鎯Γ?a11 為第一元素，其存儲地址為 1，每個元素占一個地址空間，則a85 的地址為（ B ）。A.13B.33C.18D.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+141B.BA+180C.BA+222D.BA+2253.假設(shè)以行序?yàn)橹餍虼鎯ΧS數(shù)組A=array1.100， 1.100

36、 ，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則 LOC5，5= （ B）。A.808B.818C.1010D.10204.將一個 A1.100， 1.100 的三對角矩陣，按行優(yōu)先存入一維數(shù)組B1298 中， A中元素A6665（即該元素下標(biāo)i=66 ， j=65 ），在 B 數(shù)組中的位置 K 為（ B ）。A. 198B. 195C. 197D. 1965.二維數(shù)組 A 的元素都是 6 個字符組成的串，行下標(biāo)i 的范圍從0 到 8，列下標(biāo) j的范圈從 1 到 10。從供選擇的答案中選出應(yīng)填入下列關(guān)于數(shù)組存儲敘述中（）內(nèi)的正確答案。（ 1）存放 A 至少需要（ E ）個字節(jié)；（ 2）A 的

37、第 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.54D.60E.150（ 3） A.A8,5 B.A3,10C.A5,8D. A0,9-WORD格式 - 專業(yè)資料 - 可編輯 -6. 設(shè) A 是 n*n 的對稱矩陣，將 A 的對角線及對角線上方的元素以列為主的次序存放在一維數(shù)組B1.n(n+1)/2中，對上述任一元素aij(1i ，j n，且i j) 在 B 中的位置為(B)。A.i(i-l

38、)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.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，則其遍

39、歷方式是（）。A.LRNB.NRLC.RLND.RNL分析：答案是D，此題考查二叉樹的遍歷。2. （ 09 年）已知一棵完全二叉樹的第6 層（設(shè)根為第 1 層）有 8 個葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個數(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分

40、析：答案是B，此題考查樹與二叉樹的轉(zhuǎn)換，因?yàn)閡 是 v 的父結(jié)點(diǎn)，若v 是 u 的左子樹，則 u 與 v 是父子關(guān)系，若v 是 u 的右子樹，則u 與 v 是兄弟關(guān)系。-WORD格式 - 專業(yè)資料 - 可編輯 -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.41B.82C.113D.122分析：答案是B，此題考查二叉樹的性質(zhì)

41、，利用二叉樹的性質(zhì)3 的證明思路進(jìn)行求解。6. （ 10 年）對 n(n 大于等于 2) 個權(quán)值均不相同的字符構(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.257B.258C.384D.385分析：答案是C，考查二叉樹的性質(zhì)，葉結(jié)點(diǎn)個數(shù)為你n 則度為 2 的結(jié)點(diǎn)個數(shù)為n-1 ，總結(jié)點(diǎn)個數(shù)

42、為偶數(shù)，則度為1 的結(jié)點(diǎn)個數(shù)為1，因此 2n=768。8（ 11 年）若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和 4,3,2,1，則該二叉樹的中序遍歷序列不會是（）。A.1,2,3,4B.2,3,4,1C.3,2,4,1D.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.115B.116C.1895D.1896分析：答案是D，此題考查二叉樹和樹的轉(zhuǎn)換?？紤]一種特殊的情況，設(shè)題意中的樹是如下圖所示的結(jié)構(gòu)，則對應(yīng)的二叉樹中僅有前115

43、 個葉結(jié)點(diǎn)有右孩子。-WORD格式 - 專業(yè)資料 - 可編輯 -（二）綜合題近兩年沒有考查二叉樹的題目， 如果考的話一般應(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)的理解和掌握，選擇題和綜合題都可以出。 雖然近兩年沒有出綜合題，同學(xué)們也不要忽視，綜合題一般會現(xiàn)在二叉樹的遍歷及其應(yīng)用、樹與二叉樹的轉(zhuǎn)換和哈夫曼樹的構(gòu)造及哈夫曼編碼。四、練習(xí)題（一）選擇題1

44、. 一個具有1025 個結(jié)點(diǎn)的二叉樹的高h(yuǎn) 為（ C）。A11B10C11 至 1025 之間D10 至 1024 之間2一棵二叉樹高度為h，所有結(jié)點(diǎn)的度或?yàn)? 或?yàn)?2，則這棵二叉樹最少有( B )結(jié)點(diǎn)。A 2hB 2h-1C 2h+1D h+13. 對二叉樹的結(jié)點(diǎn)從1 開始進(jìn)行連續(xù)編號，要求每個結(jié)點(diǎn)的編號大于其左、右孩子的編號，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用(C)次序的遍歷實(shí)現(xiàn)編號。A先序B中序C后序D從根開始按層次遍歷4. 某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（C）的二叉樹。A空或只有一個結(jié)點(diǎn)B任一結(jié)點(diǎn)無左子樹C高度等于其結(jié)點(diǎn)數(shù)D任一結(jié)點(diǎn)

45、無右子樹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.0B.1C.2D.不確定（二）綜合題1. 二叉樹的基本遍歷算法（ 1）二叉樹前序、中序、后序和層次遍歷的非遞歸算法-WORD格式 - 專業(yè)資料 - 可編輯 -前序void PreOrder(Bitree T)InitStack(S);Push(S,T);while(!StackEmpty(S)pop(S,p);visit

46、(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,p); p=p->lchild; if(!StackEmpty(S)pop(S,p);visit(p->data);p=p->rchild;后序void PostOrder(Bitree T

47、)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=stacktop;while(tagtop=1) top-; visit(p->data); p=stackto if(top>0)-WORD格式 - 專業(yè)資料 - 可編輯 - p=stacktop; p=p->rchild; tagtop=1;層次void LayerOrder(Bitree T)InitQueu

48、e(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ù)目int LeafCount_BiTree(Bitree T)if(!T) return 0; /空樹沒有葉子else if(!T->lchild&&!T->rchild) return 1;elsereturn Leaf_Count(T->lchild)+Leaf_Count(T>rchild);交換所有結(jié)點(diǎn)的左右子樹。void Bitree_Revolute(Bitree T)if(T!=NULL)T->lchild<->T->rchild;if(T->lc