軟考輔導數據結構與算法

數據結構與算法軟考輔導數據結構與算法概述算法知識點復習模擬練習考點分析主要內容數據結構知識點復習考點分析數據結構與算法基礎常用數據結構：57%數據結構基礎與線性表：7樹和二叉樹：14圖：11算法基礎：43%算法的描述與分析常用數值計算算法常用非數值計算算法排序算法查找算法數據結構與算法概述數據結構的概念：數據結構研究的內容：數據結構的主要邏輯結構數據結構：(DataStructure)數據結構是帶“結構”的數據元素的集合。“結構”即指數據元素之間存在的聯系。所以數據結構又可以定義為有聯系的數據元素的集合。數據結構主要研究幾種常用的數據結構的邏輯特點、存儲結構的實現、常用的操作的具體實現方法、各種結構的具體應用等問題。線性結構：線性表、棧、隊列、數組、廣義表非線性結構：樹、圖常用的排序算法、查找算法、數值計算、字符串處理、數據壓縮算法、遞歸算法、圖的相關算法算法第一部分線性表分值：0~1分（每年）分數比重：0%~10%重要知識點：

1、順序表的結構特點

2、單鏈表的結構特點

3、雙向鏈表的插入刪除

4、循環(huán)鏈表的結構特點第一部分線性表順序表特點：利用物理存儲位置的相鄰關系反應元素之間的次序關系優(yōu)點：

1.無需為表示結點間的邏輯關系而增加額外的存儲空間；

2.可方便地隨機存取表中的任一元素。缺點：

1.插入或刪除運算不方便，需要移動大量的結點，其效率較低；

2.需要預先確定順序表的最大表長，由于順序表要求占用連續(xù)的存儲空間，存儲分配只能預先進行靜態(tài)分配。因此當表長變化較大時，難以確定合適的存儲規(guī)模。第一部分線性表單鏈表lista1d1a2d2a3d3a4d4∧物理狀態(tài)邏輯狀態(tài)d2d1d3d4a2a3a4a1d3d4∧d2…優(yōu)點：1.鏈表動態(tài)存儲分配的結構，能有效利用存儲空間；。

2.插入或刪除時只需要修改指針，而不需要進行大量元素的移動。缺點：

1.必需為表示結點間的邏輯關系而增加額外的存儲空間；

2.不能隨機存取、訪問數據元素。特點：單鏈表中邏輯上相鄰的數據元素在物理上不一定相鄰。數據元素之間的邏輯關系通過鏈指針間接地反映出來。第一部分線性表雙向鏈表特點：雙向鏈表中查找某結點的直接前驅結點和直接后繼結點的運算的時間復雜度均為O(1)

es①②③④

…

bp

a

…①s->prior=p->prior;②p->prior->next=s;③s->next=p;④p->prior=s;①p->prior->next=p->next;②p->next->prior=p->prior;

a

b

c②①……插入：刪除：p第一部分線性表循環(huán)鏈表循環(huán)鏈表(CircularLinkedList)：鏈表中最后一個結點的指針域指向整個鏈表的頭結點，從而使鏈表形成一個首尾相接的環(huán)形鏈表。特點：從鏈表尾部到鏈表頭部比較方便。從表中任一結點出發(fā)均可找到表中其它結點。判空：表尾判斷：La1…LanL->next==L;p->next==L;reara1aiai-1…an…采用尾指針的循環(huán)單鏈表開始結點的存儲位置：rear->next->next終端結點的存儲位置：rear第一部分線性表真題200505●循環(huán)鏈表的主要優(yōu)點是(38)（38）A.不再需要頭指針了

B.已知某個結點的位置后，能很容易找到它的直接前驅結點

C.在進行刪除操作后，能保證鏈表不斷開D.從表中任一結點出發(fā)都能遍歷整個鏈200605●給定—個有n個元素的有序線性表。若采用順序存儲結構，則在等概率前提下，刪除其中的一個元素平均需要移動（54）個元素。（54）A．(n+1)/2

B．n/2

C．(n-1)/2

D．1第一部分線性表真題200611●某雙向鏈表中的結點如下圖所示，刪除t所指結點的操作為（54）。(54)A.t->prior->next=t->next;t->next->prior=t->prior;B.t->prior->prior=t->prior;t->next->next=t->next;C.t->prior->next=t->prior;t->next->prior=t->next;D.t->prior->prior=t->next;t->next->prior=t->prior;第一部分線性表真題200711●對于n（n≥0）個元素構成的線性序列L，在（60）時適合采用鏈式存儲結構。（60）A.需要頻繁修改Ｌ中元素的值B.需要頻繁地對Ｌ進行隨機查找C.需要頻繁地對Ｌ進行刪除和插入操作D.要求L存儲密度高第一部分線性表真題2009.11●單向鏈表中往往含有一個頭結點，該結點不存儲數據元素，一般令鏈表的頭指針指向該結點，而該結點指針域的值為第一個元素結點的指針。以下關于單鏈表頭結點的敘述中，錯誤的是(60)。(60)A．若在頭結點中存入鏈表長度值，則求鏈表長度運算的時間復雜度為O(1)B．在鏈表的任何一個元素前后進行插入和刪除操作可用一致的方式進行處理C．加入頭結點后，代表鏈表的頭指針不因為鏈表為空而改變D．加入頭結點后，在鏈表中進行查找運算的時間復雜度為O(1)分值：0~1分（每年）分數比重：0%~10%重要知識點：

1、棧的結構特點

2、隊列的結構特點

3、雙端隊列與循環(huán)隊列第二部分棧、隊列棧特點：后進先出的線性表雙向棧：使兩個棧共享一維數組S[MAXNUM]，利用棧的“棧底位置不變，棧頂位置動態(tài)變化”的特性，將兩個棧底分別設為0和MAXNUM-1，而它們的棧頂都往中間方向延伸的棧稱為雙向棧。在一端進行插入和刪除操作的線性表。棧頂：允許插入和刪除的一端。棧底：不允許插入和刪除的一端。a1a2a3an-1an…入棧出棧棧頂元素棧底元素

概念：自由區(qū)0MAXNUM-1lefttoprighttop第二部分棧、隊列隊列特點：先進先出的線性表隊列是只能在表的一端進行插入操作，在表的另一端進行刪除操作的線性表。隊尾(rear)：允許插入的一端叫做隊尾。隊頭(front)：允許刪除的一端叫做隊頭。a1a2a3…an-1an入隊列出隊列隊尾元素隊頭元素概念：第二部分棧、隊列循環(huán)隊列特點：

1、循環(huán)隊列只針對順序隊列而言2、入隊rear=(rear+1)%MAXSIZE;3、出隊front=(front+1)%MAXSIZE;

4、判隊滿：front==(rear+1)%MAXSIZE5、判隊空：rear==front6、元素個數：(rear-front+MAXSIZE)%MAXSIZE(采用少用一個存儲單元的方法區(qū)分隊空和隊滿)7012a2front345a6a5a4a3rear6把順序隊列所使用的存儲空間臆造成一個邏輯上首尾相連的循環(huán)隊列。第二部分棧、隊列雙端隊列分類：

1、輸出受限的雙端隊列（即一個端點允許插入和刪除，另一個端點只允許插入）；2、輸入受限的雙端隊列（即一個端點允許插入和刪除，另一個端點只允許刪除）。3、限定雙端隊列從某個端點插入的元素只能從該端點刪除，則雙端隊列就蛻變?yōu)閮蓚€棧底相鄰接的棧了。想象自己在郵局里排隊,當最終輪到自己時,郵局工作人員要求填寫一張表格,于是自己站在旁邊填表,工作人員為隊列中下一個人服務.在填表后,工作人員將繼續(xù)為自己服務,實質上自己又回到了隊列的前端.有時可能會排在一個隊列后面,隨即因嫌隊伍太長而離去.a1a2aia0an-1端1端2第二部分棧、隊列真題200705●輸入受限的雙端隊列是指元素只能從隊列的一端輸入、但可以從隊列的兩端輸出，如下圖所示。若有8、1、4、2依次進入輸入受限的雙端隊列，則得不到輸出序列（57）。（57）A.2、8、1、4

B.1、4、8、2

C.4、2、1、8

D.2、1、4、8第二部分棧、隊列真題200711●設棧S和隊列Q的初始狀態(tài)為空，元素按照a、b、c、d、e的次序進入棧S，當一個元素從棧中出來后立即進入隊列Q。若隊列的輸出元素序列是c、d、b、a、e，則元素的出棧順序是（58），棧S的容量至少為（59）。（58）A.a、b、c、d、eB.e、d、c、b、aC.c、d、b、a、eD.e、a、b、d、c（59）A.2B.3C.4D.5第二部分棧、隊列真題200905●下面關于棧和隊列的敘述，錯誤的是（60）。（60）A.棧和隊列都是操作受限的線性表

B.隊列采用單循環(huán)鏈表存儲時，只需設置隊尾指針就可使入隊和出隊操作的時間復雜度都為O(1)C.若隊列的數據規(guī)模n可以確定，則采用順序存儲結構比鏈式存儲結構效率更高

D.利用兩個?？梢阅M一個隊列的操作，反之亦可第二部分棧、隊列真題200911●對于長度為m（m>1）的指定序列，通過初始為空的一個棧、一個隊列后，錯誤的敘述是（61）。(61)A．若入棧和入隊的序列相同，則出棧序列和出隊序列可能相同B．若入棧和入隊的序列相同，則出棧序列和出隊序列可以互為逆序C．入隊序列與出隊序列關系為1:1，而入棧序列與出棧序列關系是l:n(n≥1)D．入棧序列與出棧序列關系為1:1，而入隊序列與出隊序列關系是l:n(n≥1)第二部分棧、隊列真題201011●設循環(huán)隊列Q的定義中有rear和len兩個域變量,其中rear表示隊尾元素的指針,len表示隊列的長度,如下圖所示(隊列長度為3,隊頭元素為e)。設隊列的存儲空間容量為M,則隊頭元素的指針為(57)。(57)A.(Q.rear+Q.len-1)B.(Q.rear+Q.len-1+M)%MC.(Q.rear-Q.len+1)D.(Q.rear-Q.len+1+M)%M第二部分棧、隊列分值：0~1分（每年）分數比重：0%~10%重要知識點：

1、數組的地址計算

2、數組的壓縮存儲

3、廣義表的表示

4、廣義表的表頭、表尾第三部分數組與廣義表

數組特點：

1.數組中的數據元素具有相同的數據類型。

2.數組是一種隨機存取結構，只要給定一組下標，就可以訪問與其對應的數組元素。

3.數組中的元素個數是固定的。基本操作——存取、修改對于數組A，一旦給定其維數n及各維長度bi（1≤i≤n），則該數組中元素的個數和元素之間的關系就不再發(fā)生變化了，既不可以對數組做插入和刪除操作，也不涉及移動元素操作。第三部分數組與廣義表

多維數組和廣義表是對線性表的擴展——線性表中的數據元素本身又是一個多層次的線性表。數組的地址計算第三部分數組與廣義表

Loc[aij]

=

Loc[a00]+(

n

i

+

j

)

size

a00a02a03a0j…a0,n-1

a10a11a12a1j…a1,n-1a20a21a22a2j…a2,n-1A[m][n]=…………ai,0ai,1……aij……am-1,0am-1,1am-1,2……am-1,n-1Loc[aij]=Loc[a00]+(mj+i)size行序為主序：列序為主序：a11a21a22......aij......ann

Loc[i

,

j]=123......n*(n+1)/2

a11

a12a13……a1n

a21a22a23……a2n

a31a32a33

……a3nA=…………

an1an2an3……annLoc[i,j]={Loc[1,1]+i(i-1)/2+j-1當i≥j時Loc[1,1]+j(j-1)/2+i-1當i<j時

對于對稱矩陣，因其元素滿足aij=aji，我們可以為每一對相等的元素分配一個存儲空間，即只存下三角（或上三角）矩陣，從而將n2個元素壓縮到n(n+1)/2個空間中。一維數組A中對應的下標為：數組的壓縮存儲第三部分數組與廣義表

對稱矩陣：aij=aji帶狀矩陣：在矩陣A中，所有的非零元素都集中在以主對角線為中心的帶狀區(qū)域中。最常見的是三對角帶狀矩陣。特點:

i=1,j=1,2;當

1<i<n，j=i-1,i,i+1i=n,j=n-1,n;時，即|i-j|≤1，aij非零，其他元素均為零。

An×n=a11a12a21a22a23a32a33a34a43a44a45

………ann-1ann0元素0元素數組的壓縮存儲第三部分數組與廣義表

1.確定存儲該矩陣所需的一維向量空間的大?。喝龑菐罹仃囍谐谝恍泻妥詈笠恍兄挥袃蓚€元素外，其余各行均有3個非零元素。由此可得到一維向量所需的空間大小為：3n-2。2.確定非零元素在一維數組空間中的位置：Loc[i,j]=Loc[1,1]+3×(i-1)-1+j-i+1=Loc[1,1]+2(i-1)+j-13.矩陣中元素aij

在一維數組A中對應的下標為：

k=2(i-1)+j-1(1≤i,j≤n，|i-j|≤1)j-i-101aij在第i行中的位置123第i行中aij前面非零元素個數012數組的壓縮存儲第三部分數組與廣義表

rowcolvalue該非零元素所在的行號該非零元素所在的列號該非零元素的值數組的壓縮存儲第三部分數組與廣義表

稀疏矩陣：三元組存儲十字鏈表M6×7=012900000000000-3000014000240000018000001500-7000121213931-3361452184324611564-7data[0]data[1]data[2]data[3]data[4]data[5]data[6]data[7]data[8]數組的壓縮存儲第三部分數組與廣義表

稀疏矩陣：十字鏈表-30050-100800711314522-138^^^^^347^^11、A=()2、B=(e)3、C=(a,(b,c,d))4、D=(A,A,())5、E=(A,B,C)6、F=(a,F)表示廣義表A是一個空表，其長度為0表示廣義表B長度為1，只有一個原子項e表示廣義表C長度為2，兩個元素分別為原子項a和子表(b,c,d)。表示廣義表D長度為3，三個元素都是廣義表，分別為A、A和()。表示廣義表E長度為3，三個元素A、B、C都是廣義表，代入值以后E=((),(e),(a,(b,c,d)))。表示廣義表F長度為2，兩個元素分別是原子項a和子表F。這是一個遞歸表，相當于無窮廣義表F=（a,F）=(a,(a,(a,…,)))。廣義表的表示第三部分數組與廣義表

廣義表的長度定義為最外層包含元素個數。廣義表的深度定義為所含括弧的重數;“原子結點”的深度為0;“空表”的深度為1。廣義表的表頭、表尾第三部分數組與廣義表

任何一個非空廣義表GL=(d1,d2,…,dn)均可分解為

表頭Head(GL)=d1

和表尾Tail(GL)=(d2,…,dn)例如:D=(E,F)=((a,(b,c))，F)Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()Head((b,c))=bTail((b,c))=(c)Head((c))=cTail((c))=()真題200511●簡單無向圖的鄰接矩陣是對稱的，可以對其進行壓縮存儲。若無向圖G有n個節(jié)點。若無向圖G有n個節(jié)點，其鄰接矩陣為A[1..n,1..n],且壓縮存儲在B[1..k]中，則k的值至少為(40)。若按行壓縮存儲對稱矩陣的上三角元素，則當n等于10時，邊(V6，V3)的信息存儲在B[(41)]中。（40）A.n(n+1)/2B.n2/2C.(n-1)(n+1)/2D.n(n-1)/2(41)A.18B.19C.20D.21第三部分數組與廣義表

真題201005第三部分數組與廣義表

真題200905●設L為廣義表，將head(L)定義為取非空廣義表的第一個元素，tail(L)定義為取非空廣義表除第一個元素外剩余元素構成的廣義表。若廣義表L=((x,y,z),a,(u,t,w))，則從L中取出原子項y的運算是（62）（62）A.head(tail(tail(L)))B.tail(head(head(L)))C.head(tail(head(L)))D.tail(tail(head(L)))第三部分數組與廣義表

分值：1~17分（每年）分數比重：2%~20%重要知識點：

1、樹和二叉樹的定義

2、二叉樹的重要性質

3、二叉樹的遍歷、線索二叉樹

4、樹與二叉樹的轉換

5、二叉樹的應用——哈夫曼樹第四部分樹與二叉樹

樹和二叉樹的定義樹的概念和邏輯特點：

1、有且僅有一個結點沒有前驅結點,該結點為樹的根結點。

2、除了根結點外,每個結點有且僅有一個直接前驅結點。

3、包括根結點在內，每個結點可以有多個后繼結點。二叉樹的概念和邏輯特點

1、每個結點的度都不大于2；2、每個結點的孩子結點次序不能任意顛倒。第四部分樹與二叉樹

相關術語：結點、結點的度、葉子結點、分支結點、結點的層次、結點的層序編號、樹的度、樹的高度（深度）、雙親結點、孩子結點、兄弟結點、堂兄弟結點、子孫結點、祖先結點。完全二叉樹、滿二叉樹。二叉樹的重要性質性質1：在二叉樹的第i層上至多有2i-1個結點(i≥1)。性質2：深度為k的二叉樹至多有2k-1個結點（k≥1）。性質3：對任意一棵二叉樹T，若終端結點數為n0，而其度數為2的結點數為n2，則n0=n2+1。性質4：具有n個結點的完全二叉樹深度為log2n+1

。性質5：對于具有n個結點的完全二叉樹，如果按照從上到下和從左到右的順序對二叉樹中的所有結點從1開始順序編號，則對于任意的序號為i的結點有：(1)若i=1,則i無雙親結點若i>1,則i的雙親結點為i/2

(2)若2*i>n,則i無左孩子若2*i≤n,則i結點的左孩子結點為2*i(3)若2*i+1>n,則i無右孩子若2*i+1≤n,則i的右孩子結點為2*i+1第四部分樹與二叉樹

二叉樹的遍歷第四部分樹與二叉樹

ABCDKFGIJEH前序遍歷序列:

A,B,D,K,J,G,C,F,I,E,H中序遍歷序列:

D,B,G,J,K,A,F,I,E,C,H后序遍歷序列:

D,G,J,K,B,E,I,F,H,C,A按層次遍歷序列:

A,B,C,D,K,F,H,J,I,G,E例：已知結點的先序序列和中序序列先序序列：ABDEJCFIG中序序列：DBJEAFICG

則可按上述分解求得整棵二叉樹。

ADCIFGJBE第四部分樹與二叉樹

例：已知結點的中序序列和后序序列中序序列：ABCEFGHD后序序列：ABFHGEDC

則可按上述分解求得整棵二叉樹。CADGEHFB線索二叉樹第四部分樹與二叉樹

一.什么是線索二叉樹二.線索二叉樹的構造

利用二叉鏈表中空的指針域指出結點在遍歷序列中的直接前驅和直接后繼;這些指向前驅和后繼的指針稱為線索,加了線索的二叉樹稱為線索二叉樹.利用結點的空的左指針域存放該結點的直接前驅的地址,空的右指針域存放該結點直接后繼的地址;而非空的指針域仍然存放結點的左孩子或右孩子的地址.注：每棵二叉樹都可以構造先序、中序和后序三種線索二叉樹。樹、森林與二叉樹的轉換第四部分樹與二叉樹

樹轉換成二叉樹：

1、樹中所有相鄰兄弟之間加一條連線。2、對樹中的每個結點，只保留其與第一個孩子結點之間的連線，刪去其與其它孩子結點之間的連線。森林轉換為二叉樹的方法為：1、將森林中的每棵樹轉換成相應的二叉樹。2、第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連在一起后，即為由森林轉換得到的二叉樹。ABECDFGHABCDEFIJGH帶權路徑長度：

設二叉樹有n個帶權值的葉子結點，定義從二叉樹的根結點到二叉樹中所有葉子結點的路徑長度li與相應葉子結點權值wi的乘積之和稱作該二叉樹的帶權路徑長度。TWPL(T)=72+52+23+43+92=6075249ACBIGFDEHWPL=哈夫曼樹第四部分樹與二叉樹

52310515782511110000(011)(010)(10)(11)(00)字符：staec

字符出現的次數：38752c:010s:011e:00a:10t:11哈夫曼編碼第四部分樹與二叉樹

真題200505●表達式a*(b+c)-d的后綴表達形式為___(39)___。（39）A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd●若二叉樹的先序遍歷序列為ABDECF，中序遍歷序列DBEAFC，則其后序遍歷序列為__(40)___。（40）A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA第四部分樹與二叉樹

真題201005●若用n個權值構造一棵最優(yōu)二叉樹（哈夫曼樹），則該二叉樹的結點總數為___(59)___。(38)A.2nB.2n-1C.2n+1D.2n1●在二叉樹的順序存儲中，每個結點的存儲位置與其父結點、左右子樹結點的位置都存在一個簡單的映射關系，因此可與三叉鏈表對應。若某二叉樹共有n個結點，采用三叉鏈表存儲時，每個結點的數據域需要d個字節(jié)，每個指針域占用4個字節(jié)，若采用順序存儲，則最后一個結點下標為k（起始下標為1）,那么___(39)___時采用順序存儲更節(jié)省空間。(39)A.d<12n/(k-n)B.d>12n/(k-n)C.d<12n/(k+n)D.d>12n/(k+n)第四部分樹與二叉樹

真題200605●與逆波蘭式ab+-c*d-對應的中綴表達式是（45）。（45）A．a-b-c*d

B．-(a+b)*c-d

C．-a+b*c-d

D．(a+b)*(-c-d)●為便于存儲和處理一般樹結構形式的信息，常采用孩子ˉ兄弟表示法將其轉換成二叉樹（左子關系表示父子、右子關系表示兄弟），與下圖所示的樹對應的二叉樹是（53）。（53）第四部分樹與二叉樹

真題200612●“X=(A+B)×(C-D/E)”的后綴式表示為（20）（20）A.XAB+CDE/-×=B.XAB+C-DE/×=C.XAB+CDE-/×=D.XAB+CD-E/×=200705●已知某二叉樹的中序序列為CBDAEFI、先序序列為ABCDEFI，則該二叉樹的高度為（58）。（58）A.2B.3C.4D.5第四部分樹與二叉樹

真題200705●由權值為29、12、15、6、23的五個葉子結點構造的哈夫曼樹為（64），其帶權路徑長度為（65）。第四部分樹與二叉樹

真題200805●若將某有序樹T轉換為二叉樹T1，則T中結點的后(根)序序列就是T1中結點的__(59)__遍歷序列。例如，下圖(a)所示的有序樹轉化為二叉樹后如圖(b)所示。(59)A.先序B.中序C.后序D.層序

第四部分樹與二叉樹

真題201011●下面關于哈夫曼樹的敘述中,正確的是(58)。(58)A.哈夫曼樹一定是完全二叉樹

B.哈夫曼樹一定是平衡二叉樹

C.哈夫曼樹中權值最小的兩個結點互為兄弟結點D.哈夫曼樹中左孩子結點小于父結點、右孩子結點大于父結點●已知一棵度為3的樹(一個結點的度是指其子樹的數目,樹的度是指該樹中所有結點的度的最大值)中有5個度為1的結點,4個度為2的結點,2個度為3的結點,那么,該樹中的葉子結點數目為(61)。(61)A.10 B.9C.8D.7第四部分樹與二叉樹

真題200905●下面關于二叉樹的敘述，正確的是（61）。（61）A.完全二叉樹的高度h與其結點數n之間存在確定的關系B.在二叉樹的順序存儲和鏈式存儲結構中，完全二叉樹更適合采用鏈式存儲結構C.完全二叉樹中一定不存在度為1的結點D.完全二叉樹中必定有偶數個葉子結點201105●在（59）中，任意一個結點的左右字數的高度之差的絕對值不超過1.(59)A.完全二叉樹B.二叉排序樹C.線索二叉樹D.最優(yōu)二叉樹第四部分樹與二叉樹

真題200911●已知一個二叉樹的先序遍歷序列為①、②、③、④、⑤，中序遍歷序列為②、①、④、③、⑤，則該二叉樹的后序遍歷序列為（57）。對于任意一棵二叉樹，敘述錯誤的是（58）。（57）A．②、③、①、⑤、④B．①、②、③、④、⑤C．②、④、⑤、③、①D．④、⑤、③、②、①（58）A．由其后序遍歷序列和中序遍歷序列可以構造該二叉樹的先序遍歷序列B．由其先序遍歷序列和后序遍歷序列可以構造該二叉樹的中序遍歷序列C．由其層序遍歷序列和中序遍歷序列可以構造該二叉樹的先序遍歷序列D．由其層序遍歷序列和中序遍歷序列不能構造該二叉樹的后序遍歷序列第四部分樹與二叉樹

分值：0~5分（每年）分數比重：6%重要知識點：

1、圖的基本概念和存儲結構

2、圖的遍歷

3、拓撲排序和最小生成樹

4、關鍵路徑

5、最短路徑第五部分圖

圖的基本概念和存儲結構圖的基本概念：無向圖、有向圖、無向完全圖、有向完全圖、稀疏圖、稠密圖、子圖、有向圖與無向圖的頂點的度、網、回路和環(huán)、路徑長度、簡單路徑、簡單回路、連通圖、連通分量、強連通圖、強連通分量。圖的存儲結構鄰接矩陣(數組)表示法；鄰接表；十字鏈表；第五部分圖

BACDG1BADEG2C圖的遍歷深度優(yōu)先搜索：是指按照深度方向搜索，它類似于樹的先根遍歷。廣度優(yōu)先搜索：是指按照廣度方向搜索，它類似于樹的按層次遍歷。第五部分圖

v1v2v3v4v5v6v7v8v9v1v2v4v7v9v5v3v6v8BAEDCABCDEv1v2v3v4v5v9v6v8v7ABCED拓撲排序拓撲排序將一個有向圖中的所有結點排成一個序列，使得圖中所有結點應存在的前驅和后繼關系都能在隊列中體現（前驅在前，后繼在后）。過程⑴從AOV網中選擇一個沒有前驅的頂點并且輸出；⑵從AOV網中刪去該頂點并且刪去所有以該頂點為尾的?。虎侵貜蜕鲜鰞刹?，直到全部頂點都被輸出;第五部分圖

C1C2C3C4C6C5C7拓撲序列：C1,C2,C3,C4,C5,C6,C7

最小生成樹概念生成樹是連通圖上的一個極小連通子圖。最小生成樹是一個連通網中所有生成樹中各邊權值之和最小的生成樹。最小生成樹的算法：

1、普里姆算法2、克魯斯卡爾算法第五部分圖

abdcef6155542663abdcef15342abdcef1532554關鍵路徑概念從源點到匯點的最長路徑的長度即為完成整個工程任務所需的時間，該路徑叫做關鍵路徑。關鍵路徑上的活動叫關鍵活動。關鍵路徑的求法：

⑴事件的最早發(fā)生時間ve[k]⑵事件的最遲發(fā)生時間vl[k]

⑶活動的最早開始時間e[i]⑷活動的最晚開始時間l[i]第五部分圖

v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4第五部分圖

v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4ve[k]v2v7v6v5v4v1v3v9v8064577161418a2a7a6a5a4a1a3a9a8e[i]000645777a10a111614第五部分圖

v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4l[i]10778663201614a2a7a6a5a4a1a3a9a8a10a11v2v7v6v5v4v1v3v9v8vl[k]1814161078660最短路徑分類1、求圖中的一個結點到其他結點的最短路徑。2、求圖中任意兩點間的最短路徑。最短路徑的求法：

⑴迪杰斯特拉(Dijkstra)算法⑵Floyd算法第五部分圖

BAEDC105030101002060S={A,B,D,C,E}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60BAEDC105030101002060最短路徑分類1、求圖中的一個結點到其他結點的最短路徑。2、求圖中任意兩點間的最短路徑。最短路徑的求法：

⑴迪杰斯特拉(Dijkstra)算法⑵Floyd算法第五部分圖

abd53863c122真題201105●設一個包含N個頂點，E條邊的簡單無向圖采用鄰接矩陣存儲結構，則該矩陣中的非零元素數目為（60）（60）A.N

B.E

C.2E

D.N+E200505●一個具有n(n>0)個頂點的連通無向圖至少有(49)條邊。（49）A.n+1

B.n

C.n+2

D.n-1第五部分圖

真題200511●在活動圖中，結點表示項目中各個工作階段的里程碑，連接各個結點的邊表示活動，邊上的數字表示活動持續(xù)的時間。在下面的活動圖中，從A到J的關鍵路徑是(16)，關鍵路徑長度是(17)，從E開始的活動啟動的最早時間是(18)。

(16)A.ABEGJ

B.ADFHJ

C.ACFGJ

D.ADFIJ(17)A.22

B.49

C.19

D.35(18)A.10

B.12

C.13

D.15第五部分圖

真題200511●簡單無向圖的鄰接矩陣是對稱的，可以對其進行壓縮存儲。若無向圖G有n個節(jié)點。若無向圖G有n個節(jié)點，其鄰接矩陣為A[1..n,1..n],且壓縮存儲在B[1..k]中，則k的值至少為____(40)____。若按行壓縮存儲對稱矩陣的上三角元素，則當n等于10時，邊(V6，V3)的信息存儲在B[___(41)___]中。(40)A.n(n+1)/2B.n2/2C.(n-1)(n+1)/2D.n(n-1)/2(41)A.18B.19C.20D.21第五部分圖

真題200605●(59)是右圖的合法拓撲序列。

(59)A.654321B.123456C.563421D.564213第五部分圖

真題200611●求單源點最短路徑的迪杰斯特拉（Dijkstra）算法是按（57）的順序求源點到各頂點的最短路徑的。（57）A.路徑長度遞減B.路徑長度遞增C.頂點編號遞減D.頂點編號遞增第五部分圖

真題200705●某工程計劃如下圖所示，各個作業(yè)所需的天數如下表所示，設該工程從第0天開工，則該工程的最短工期是（59）天，作業(yè)J最遲應在第（60）天開工。第五部分圖

真題200711●拓撲排序是指有向圖中的所有頂點排成一個線性序列的過程，若在有向圖中從頂點vi到vj有一條路徑，則在該線性序列中，頂點vi必然在頂點vj之前。因此，若不能得到全部頂點的拓撲排序序列，則說明該有向圖一定（57）。（57）A.包含回路B.是強連通圖C.是完全圖D.是有向樹200805●設一個包含N個頂點、E條邊的簡單有向圖采用鄰接矩陣存儲結構(矩陣元素A[i][j]等于1/0分別表示頂點i與頂點j之間有/無弧)，則該矩陣的元素數目為__(60)__，其中非零元素數目為__(61)__。(60)A.E2B.N2C.N2-E2D.N2+E2(61)A.NB.N+EC.ED.N–E第五部分圖

真題200811●（59）的鄰接矩陣是一個對稱矩陣。（59）A.無向圖B.AOV網C.AOE網D.有向圖●具有n個頂點、e條邊的圖采用鄰接表存儲結構，進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷運算的時間復雜度均為（63）。（63）A.O(n2)B.O(e2)C.O(n*e)D.O(n+e)第五部分圖

真題200905●下面關于圖（網）的敘述，正確的是（58）。（58）A.連通無向網的最小生成樹中，頂點數恰好比邊數多1B.若有向圖是強連通的，則其邊數至少是頂點數的2倍C.可以采用AOV網估算工程的工期D.關鍵路徑是AOE網中源點至匯點的最短路徑第五部分圖

分值：5~15分（每年）分數比重：10%重要知識點：

1、靜態(tài)表查找——順序查找、折半查找

2、動態(tài)表查找——二叉排序樹、平衡二叉樹3、哈希表

4、插入類排序5、交換類排序6、選擇類排序7、分配類排序第六部分排序與查找

查找基本概念：靜態(tài)查找：不涉及插入和刪除操作的查找。動態(tài)查找：涉及插入和刪除操作的查找。平均查找長度：將查找算法進行的關鍵碼的比較次數的數學期望值定義為平均查找長度。計算公式為：其中：n：問題規(guī)模，查找集合中的記錄個數；pi：查找第i個記錄的概率；ci：查找第i個記錄所需的關鍵碼的比較次數。第六部分排序與查找

靜態(tài)查找順序查找：從線性表的一端向另一端逐個將關鍵碼與給定值進行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個表檢測完仍未找到與給定值相等的關鍵碼，則查找失敗，給出失敗信息。折半查找：在有序表中，取中間元素作為比較對象1、若給定值與中間記錄的關鍵字相等，則查找成功；2、若給定值小于中間記錄的關鍵字，則在中間記錄的左半區(qū)繼續(xù)查找；若給定值大于中間記錄的關鍵字，則在中間記錄的右半區(qū)繼續(xù)查找。3、不斷重復上述過程，直到查找成功，或所查找的區(qū)域無記錄(low>high)，查找失敗。

前提：線性表中的記錄必須按關鍵字有序；必須采用順序存儲。第六部分排序與查找

動態(tài)查找——二叉排序樹定義：一棵二叉樹中，每一個結點的左子樹上的結點都比它小，右子樹上的結點都比它大。這種二叉樹稱為二叉排序樹。二叉排序樹的查找：從根結點開始比較，如果比根結點的值小，則到根結點的左子樹上去查找；比根結點大，到根結點的右子樹上去查找；與根結點相等，說明查找成功。依此類推，直到所要查找的結點為空，說明查找失敗。二叉排序樹的構造：將二叉排序樹初始化為一棵空樹，然后按照順序逐個讀入元素，每讀入一個元素，就建立一個新的結點插入到當前已生成的二叉排序樹中，即調用上述二叉排序樹的插入算法將新結點插入。直到所有結點插入完成，二叉排序樹就構造完成了。注：若二叉排序樹為空樹，則新插入的結點為新的根結點；否則，新插入的結點必為一個新的葉子結點，其插入位置由查找過程得到。第六部分排序與查找

動態(tài)查找——二叉排序樹結論：對同樣一組數據元素，如果輸入的順序不同，則所建的二叉樹形態(tài)也不同。特點：

1、一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列;

2、每次插入的新結點都是二叉排序樹上新的葉子結點;

3、找到插入位置后，不必移動其它結點，僅需修改某個結點的指針；

4、在左子樹/右子樹的查找過程與在整棵樹上查找過程相同；

5、新插入的結點沒有破壞原有結點之間的關系。第六部分排序與查找

練習：關鍵字的輸入順序為：45,24,53,12,28,90，和24,53,90,12,28,45，分別構造二叉排序樹動態(tài)查找——二叉排序樹的刪除1.

若結點p是葉子，則直接刪除結點p；2.若p結點只有左子樹，或只有右子樹，則因為該結點只有左子樹或只有右子樹，也就是說，其后繼只有一個分支。刪除該結點時，只要將被刪除結點的唯一后繼（左子樹或右子樹）直接鏈接到被刪除結點的位置即可。3.若結點p的左右子樹均不空：首先找到p結點在中序序列中的直接前驅s結點，然后用s結點的值，替代p結點的值，再將s結點刪除,因為s的右指針一定為空，所以只要把s的左孩子鏈接到s結點本身的位置即可。第六部分排序與查找

動態(tài)查找——平衡二叉樹平衡二叉樹：或者是一棵空的二叉排序樹，或者是具有下列性質的二叉排序樹：⑴根結點的左子樹和右子樹的深度最多相差1;⑵根結點的左子樹和右子樹也都是平衡二叉樹。平衡因子：結點的平衡因子是該結點的左子樹的深度與右子樹的深度之差。在平衡二叉樹中，結點的平衡因子可以是1，0，-1。最小不平衡子樹：在平衡二叉樹的構造過程中，以距離插入結點最近的、且平衡因子絕對值大于1的祖先結點為根的子樹。第六部分排序與查找

動態(tài)查找——平衡二叉樹的構造基本思想：在構造二叉排序樹的過程中，每插入一個結點時，首先檢查是否因插入新結點而破壞了樹的平衡性，若是，則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。1.LL型：由于在A的左子樹根結點B的左子樹上插入結點，A的平衡因子由1變?yōu)?。2.RR型：由于在A的右子樹根結點B的右子樹上插入結點，A的平衡因子由-1變?yōu)?2。3.LR型：由于在A的左子樹根結點B的右子樹上插入結點，A的平衡因子由1變?yōu)?。4.RL型：由于在A的右子樹根結點B的左子樹上插入結點，A的平衡因子由1變?yōu)?。第六部分排序與查找

動態(tài)查找——平衡二叉樹的構造第六部分排序與查找

LL型RR型第六部分排序與查找

LR型RR型動態(tài)查找——平衡二叉樹依次輸入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序樹

(1)試畫出生成之后的二叉排序樹;(2)假定每個元素的查找概率相等，試計算該二叉排序樹的平均查找長度；(3)畫出由這組元素所構造的平衡二叉樹。第六部分排序與查找

哈希表定義：在元素的關鍵字k和元素的存儲位置p之間建立一個對應關系H，使得p=H(k)，H稱為哈希函數。創(chuàng)建哈希表時，把關鍵字為k的元素直接存入地址為H(k)的單元；以后當查找關鍵字為k的元素時，再利用哈希函數計算出該元素的存儲位置p=H(k)，從而達到按關鍵字直接存取元素的目的。這種查找的方法稱為哈希法。哈希函數設計原則：⑴計算簡單。哈希函數不應該有很大的計算量，否則會降低查找效率。⑵函數值即哈希地址分布均勻。函數值要盡量均勻散布在地址空間，這樣才能保證存儲空間的有效利用并減少沖突。第六部分排序與查找

哈希表沖突：對于兩個不同關鍵碼ki≠kj，有H(ki)＝H(kj)，即兩個不同的記錄需要存放在同一個存儲位置。哈希函數沖突的處理方法：

1、開放定址法(再散列法)：線性探測再散列、二次探測再散列；

2、再哈希法：同時構造多個不同的哈希函數，當哈希地址發(fā)生沖突時，再用其他哈希函數來計算地址，直到沖突不再產生。

3、鏈地址法：將所有哈希地址為i的元素構成一個單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在這個鏈中進行。4、建立公共溢出區(qū)法：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表。

第六部分排序與查找

哈希表裝填因子：哈希法中影響關鍵字比較次數的因素有三個：哈希函數、處理沖突的方法以及哈希表的裝填因子。哈希表的裝填因子α的定義如下：α可描述哈希表的裝滿程度。α越小，發(fā)生沖突的可能性越?。沪猎酱螅l(fā)生沖突的可能性也越大。第六部分排序與查找

α＝哈希表中元素個數哈希表的長度基本概念內部排序：整個排序過程完全在內存中進行，稱為內部排序。外部排序：由于待排序的記錄個數太多，不能同時放置在內存，而需要將另一部分記錄放置在外存上，整個排序過程需要在內外存之間多次交換數據才能得到排序的結果。排序的穩(wěn)定性：相同關鍵字的相對位置關系在排序過程中沒有發(fā)生變化者，則稱所用的排序方法是穩(wěn)定的；反之，則稱為不穩(wěn)定的。第六部分排序與查找

插入類排序直接插入排序：每次將一個待排序的記錄按其關鍵碼的大小插入到一個已經排好序的有序序列中，直到全部記錄排好序為止。折半插入排序：以折半查找和直接插入排序兩種方法結合起來實現排序；希爾排序：根據不同的間距di將元素分成組，在各組內進行直接插入排序，di的值是由大到小，最后為1，即將所有元素放在一組里進行排序第六部分排序與查找

第六部分排序與查找

直接插入4674165314264038866527341467416531426403886652734216467453142640388665273431646537414264038866527344141646537426403886652734514162646537440388665273461416264046537438866527347141626384046537486652734814162638404653748665273491416263840465365748627341014162627384046536574863411141626273438404653657486希爾排序467416531426403886652734126341653142740388665467422614164034275338746546863141626273438404653657486交換類排序冒泡排序：快速排序：第六部分排序與查找

快速排序4674165314264038866527341342716381426404686655374226271614343840467465538631416262734384046536574864141626273438404653657486選擇類排序：簡單選擇排序、堆排序第六部分排序與查找

簡單選擇4674165314264038866527341147416534626403886652734214167453462640388665273431416265346744038866527344141626274674403886655334514162627347440388665534661416262734384074866553467141626273438407486655346814162627343840468665537491416262734384046536586741014162627343840465365867411141626273438404653657486演示歸并排序基本思想：將兩個或兩個以上有序表合并成一個新的有序表。假設初始序列含有n個記錄，首先將這n個記錄看成n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2的有序子序列；在此基礎上，再進行兩兩歸并，如此重復，直至得到一個長度為n的有序序列為止。第六部分排序與查找

(19)(13)(05)(27)(01)(26)(31)(16)

(13,19)(05,27)(01,26)(16,31)

(05,13,19,27)(01,16,26,31)

(01,05,13,16,19,26,27,31)分配類排序基本思想：設待排序的數據元素關鍵字是m位d進制整數（不足m位的關鍵字在高位補0），設置d個桶，分別編號為0,1,2,…,d-1。1、首先按關鍵字最低位的數值依次把各數據元素放到相應的桶中，然后按照桶號從小到大和進入桶中數據元素的先后次序收集分配在各桶中的數據元素，這樣就形成了數據元素集合的一個新的排列，我們稱這樣的一次排序過程為一次基數排序；

2、再對一次基數排序得到的序列按關鍵字次低位的數值依次把各數據元素放到相應的桶中，然后按照桶號從小到大和進入桶中數據元素的先后次序收集分配在各桶中的數據元素；這樣的過程重復進行，當完成了第m次基數排序后，就得到了排好序的數據元素序列。第六部分排序與查找

分配類排序基本思想：設待排序的數據元素關鍵字是m位d進制整數（不足m位的關鍵字在高位補0），設置d個桶，分別編號為0,1,2,…,d-1。1、首先按關鍵字最低位的數值依次把各數據元素放到相應的桶中，然后按照桶號從小到大和進入桶中數據元素的先后次序收集分配在各桶中的數據元素，這樣就形成了數據元素集合的一個新的排列，我們稱這樣的一次排序過程為一次基數排序；

2、再對一次基數排序得到的序列按關鍵字次低位的數值依次把各數據元素放到相應的桶中，然后按照桶號從小到大和進入桶中數據元素的先后次序收集分配在各桶中的數據元素；這樣的過程重復進行，當完成了第m次基數排序后，就得到了排好序的數據元素序列。第六部分排序與查找

數據元素的關鍵字序列為{710,342,045,686,006,841,429,134,068,264}8411342231342644045568600667068871004299放置7101429213438413420454526406867686800609006710429134841342045264068686收集后的新序列:放置1341264234234294568667107841800604506809006045068134264342429686710841收集后的新序列:放置710841342134264045686006068429收集后的新序列:(a)第一趟基數排序

(b)第二趟基數排序

(c)第三趟基數排序排序方法最好情況平均時間最壞情況穩(wěn)定性直接插入O(n)O(n2)O(n2)√簡單選擇O(n2)O(n2)O(n2)√冒泡O(n)O(n2)O(n2)√快速O(nlog2n)O(nlog2n)O(n2)×堆排序O(nlog2n)O(nlog2n)O(nlog2n)×歸并O(nlog2n)O(nlog2n)O(nlog2n)√基數O(d(n+rd))O(d(n+rd))O(d(n+rd))√第六部分排序與查找

各種排序方法性