軟考輔導(dǎo)數(shù)據(jù)結(jié)構(gòu)與算法

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

1、順序表的結(jié)構(gòu)特點(diǎn)

2、單鏈表的結(jié)構(gòu)特點(diǎn)

3、雙向鏈表的插入刪除

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

1.無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；

2.可方便地隨機(jī)存取表中的任一元素。缺點(diǎn)：

1.插入或刪除運(yùn)算不方便，需要移動(dòng)大量的結(jié)點(diǎn)，其效率較低；

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

2.插入或刪除時(shí)只需要修改指針，而不需要進(jìn)行大量元素的移動(dòng)。缺點(diǎn)：

1.必需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；

2.不能隨機(jī)存取、訪問數(shù)據(jù)元素。特點(diǎn)：?jiǎn)捂湵碇羞壿嬌舷噜彽臄?shù)據(jù)元素在物理上不一定相鄰。數(shù)據(jù)元素之間的邏輯關(guān)系通過鏈指針間接地反映出來。第一部分線性表雙向鏈表特點(diǎn)：雙向鏈表中查找某結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的運(yùn)算的時(shí)間復(fù)雜度均為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)：鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向整個(gè)鏈表的頭結(jié)點(diǎn)，從而使鏈表形成一個(gè)首尾相接的環(huán)形鏈表。特點(diǎn)：從鏈表尾部到鏈表頭部比較方便。從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。判空：表尾判斷：La1…LanL->next==L;p->next==L;reara1aiai-1…an…采用尾指針的循環(huán)單鏈表開始結(jié)點(diǎn)的存儲(chǔ)位置：rear->next->next終端結(jié)點(diǎn)的存儲(chǔ)位置：rear第一部分線性表真題200505●循環(huán)鏈表的主要優(yōu)點(diǎn)是(38)（38）A.不再需要頭指針了

B.已知某個(gè)結(jié)點(diǎn)的位置后，能很容易找到它的直接前驅(qū)結(jié)點(diǎn)

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

B．n/2

C．(n-1)/2

D．1第一部分線性表真題200611●某雙向鏈表中的結(jié)點(diǎn)如下圖所示，刪除t所指結(jié)點(diǎn)的操作為（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●對(duì)于n（n≥0）個(gè)元素構(gòu)成的線性序列L，在（60）時(shí)適合采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（60）A.需要頻繁修改Ｌ中元素的值B.需要頻繁地對(duì)Ｌ進(jìn)行隨機(jī)查找C.需要頻繁地對(duì)Ｌ進(jìn)行刪除和插入操作D.要求L存儲(chǔ)密度高第一部分線性表真題2009.11●單向鏈表中往往含有一個(gè)頭結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，一般令鏈表的頭指針指向該結(jié)點(diǎn)，而該結(jié)點(diǎn)指針域的值為第一個(gè)元素結(jié)點(diǎn)的指針。以下關(guān)于單鏈表頭結(jié)點(diǎn)的敘述中，錯(cuò)誤的是(60)。(60)A．若在頭結(jié)點(diǎn)中存入鏈表長(zhǎng)度值，則求鏈表長(zhǎng)度運(yùn)算的時(shí)間復(fù)雜度為O(1)B．在鏈表的任何一個(gè)元素前后進(jìn)行插入和刪除操作可用一致的方式進(jìn)行處理C．加入頭結(jié)點(diǎn)后，代表鏈表的頭指針不因?yàn)殒湵頌榭斩淖僁．加入頭結(jié)點(diǎn)后，在鏈表中進(jìn)行查找運(yùn)算的時(shí)間復(fù)雜度為O(1)分值：0~1分（每年）分?jǐn)?shù)比重：0%~10%重要知識(shí)點(diǎn)：

1、棧的結(jié)構(gòu)特點(diǎn)

2、隊(duì)列的結(jié)構(gòu)特點(diǎn)

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

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

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

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

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

B.1、4、8、2

C.4、2、1、8

D.2、1、4、8第二部分棧、隊(duì)列真題200711●設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素按照a、b、c、d、e的次序進(jìn)入棧S，當(dāng)一個(gè)元素從棧中出來后立即進(jìn)入隊(duì)列Q。若隊(duì)列的輸出元素序列是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第二部分棧、隊(duì)列真題200905●下面關(guān)于棧和隊(duì)列的敘述，錯(cuò)誤的是（60）。（60）A.棧和隊(duì)列都是操作受限的線性表

B.隊(duì)列采用單循環(huán)鏈表存儲(chǔ)時(shí)，只需設(shè)置隊(duì)尾指針就可使入隊(duì)和出隊(duì)操作的時(shí)間復(fù)雜度都為O(1)C.若隊(duì)列的數(shù)據(jù)規(guī)模n可以確定，則采用順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)效率更高

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

1、數(shù)組的地址計(jì)算

2、數(shù)組的壓縮存儲(chǔ)

3、廣義表的表示

4、廣義表的表頭、表尾第三部分?jǐn)?shù)組與廣義表

數(shù)組特點(diǎn)：

1.數(shù)組中的數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。

2.數(shù)組是一種隨機(jī)存取結(jié)構(gòu)，只要給定一組下標(biāo)，就可以訪問與其對(duì)應(yīng)的數(shù)組元素。

3.數(shù)組中的元素個(gè)數(shù)是固定的?；静僮鳌嫒?、修改對(duì)于數(shù)組A，一旦給定其維數(shù)n及各維長(zhǎng)度bi（1≤i≤n），則該數(shù)組中元素的個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變化了，既不可以對(duì)數(shù)組做插入和刪除操作，也不涉及移動(dòng)元素操作。第三部分?jǐn)?shù)組與廣義表

多維數(shù)組和廣義表是對(duì)線性表的擴(kuò)展——線性表中的數(shù)據(jù)元素本身又是一個(gè)多層次的線性表。數(shù)組的地址計(jì)算第三部分?jǐn)?shù)組與廣義表

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行序?yàn)橹餍颍毫行驗(yàn)橹餍颍篴11a21a22......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當(dāng)i≥j時(shí)Loc[1,1]+j(j-1)/2+i-1當(dāng)i<j時(shí)

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

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

i=1,j=1,2;當(dāng)

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

An×n=a11a12a21a22a23a32a33a34a43a44a45

………ann-1ann0元素0元素?cái)?shù)組的壓縮存儲(chǔ)第三部分?jǐn)?shù)組與廣義表

1.確定存儲(chǔ)該矩陣所需的一維向量空間的大?。喝龑?duì)角帶狀矩陣中除第一行和最后一行只有兩個(gè)元素外，其余各行均有3個(gè)非零元素。由此可得到一維向量所需的空間大小為：3n-2。2.確定非零元素在一維數(shù)組空間中的位置：Loc[i,j]=Loc[1,1]+3×(i-1)-1+j-i+1=Loc[1,1]+2(i-1)+j-13.矩陣中元素aij

在一維數(shù)組A中對(duì)應(yīng)的下標(biāo)為：

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

rowcolvalue該非零元素所在的行號(hào)該非零元素所在的列號(hào)該非零元素的值數(shù)組的壓縮存儲(chǔ)第三部分?jǐn)?shù)組與廣義表

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

稀疏矩陣：十字鏈表-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是一個(gè)空表，其長(zhǎng)度為0表示廣義表B長(zhǎng)度為1，只有一個(gè)原子項(xiàng)e表示廣義表C長(zhǎng)度為2，兩個(gè)元素分別為原子項(xiàng)a和子表(b,c,d)。表示廣義表D長(zhǎng)度為3，三個(gè)元素都是廣義表，分別為A、A和()。表示廣義表E長(zhǎng)度為3，三個(gè)元素A、B、C都是廣義表，代入值以后E=((),(e),(a,(b,c,d)))。表示廣義表F長(zhǎng)度為2，兩個(gè)元素分別是原子項(xiàng)a和子表F。這是一個(gè)遞歸表，相當(dāng)于無窮廣義表F=（a,F）=(a,(a,(a,…,)))。廣義表的表示第三部分?jǐn)?shù)組與廣義表

廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù)。廣義表的深度定義為所含括弧的重?cái)?shù);“原子結(jié)點(diǎn)”的深度為0;“空表”的深度為1。廣義表的表頭、表尾第三部分?jǐn)?shù)組與廣義表

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

表頭Head(GL)=d1

和表尾Tail(GL)=(d2,…,dn)例如:D=(E,F)=((a,(b,c))，F(xiàn))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●簡(jiǎn)單無向圖的鄰接矩陣是對(duì)稱的，可以對(duì)其進(jìn)行壓縮存儲(chǔ)。若無向圖G有n個(gè)節(jié)點(diǎn)。若無向圖G有n個(gè)節(jié)點(diǎn)，其鄰接矩陣為A[1..n,1..n],且壓縮存儲(chǔ)在B[1..k]中，則k的值至少為(40)。若按行壓縮存儲(chǔ)對(duì)稱矩陣的上三角元素，則當(dāng)n等于10時(shí)，邊(V6，V3)的信息存儲(chǔ)在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第三部分?jǐn)?shù)組與廣義表

真題201005第三部分?jǐn)?shù)組與廣義表

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

分值：1~17分（每年）分?jǐn)?shù)比重：2%~20%重要知識(shí)點(diǎn)：

1、樹和二叉樹的定義

2、二叉樹的重要性質(zhì)

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

4、樹與二叉樹的轉(zhuǎn)換

5、二叉樹的應(yīng)用——哈夫曼樹第四部分樹與二叉樹

樹和二叉樹的定義樹的概念和邏輯特點(diǎn)：

1、有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn),該結(jié)點(diǎn)為樹的根結(jié)點(diǎn)。

2、除了根結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)。

3、包括根結(jié)點(diǎn)在內(nèi)，每個(gè)結(jié)點(diǎn)可以有多個(gè)后繼結(jié)點(diǎn)。二叉樹的概念和邏輯特點(diǎn)

1、每個(gè)結(jié)點(diǎn)的度都不大于2；2、每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。第四部分樹與二叉樹

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

。性質(zhì)5：對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上到下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從1開始順序編號(hào)，則對(duì)于任意的序號(hào)為i的結(jié)點(diǎn)有：(1)若i=1,則i無雙親結(jié)點(diǎn)若i>1,則i的雙親結(jié)點(diǎn)為i/2

(2)若2*i>n,則i無左孩子若2*i≤n,則i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)為2*i(3)若2*i+1>n,則i無右孩子若2*i+1≤n,則i的右孩子結(jié)點(diǎn)為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例：已知結(jié)點(diǎn)的先序序列和中序序列先序序列：ABDEJCFIG中序序列：DBJEAFICG

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

ADCIFGJBE第四部分樹與二叉樹

例：已知結(jié)點(diǎn)的中序序列和后序序列中序序列：ABCEFGHD后序序列：ABFHGEDC

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

一.什么是線索二叉樹二.線索二叉樹的構(gòu)造

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

樹轉(zhuǎn)換成二叉樹：

1、樹中所有相鄰兄弟之間加一條連線。2、對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連線。森林轉(zhuǎn)換為二叉樹的方法為：1、將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。2、第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，即為由森林轉(zhuǎn)換得到的二叉樹。ABECDFGHABCDEFIJGH帶權(quán)路徑長(zhǎng)度：

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

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

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

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

真題201005●若用n個(gè)權(quán)值構(gòu)造一棵最優(yōu)二叉樹（哈夫曼樹），則該二叉樹的結(jié)點(diǎn)總數(shù)為___(59)___。(38)A.2nB.2n-1C.2n+1D.2n1●在二叉樹的順序存儲(chǔ)中，每個(gè)結(jié)點(diǎn)的存儲(chǔ)位置與其父結(jié)點(diǎn)、左右子樹結(jié)點(diǎn)的位置都存在一個(gè)簡(jiǎn)單的映射關(guān)系，因此可與三叉鏈表對(duì)應(yīng)。若某二叉樹共有n個(gè)結(jié)點(diǎn)，采用三叉鏈表存儲(chǔ)時(shí)，每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域需要d個(gè)字節(jié)，每個(gè)指針域占用4個(gè)字節(jié)，若采用順序存儲(chǔ)，則最后一個(gè)結(jié)點(diǎn)下標(biāo)為k（起始下標(biāo)為1）,那么___(39)___時(shí)采用順序存儲(chǔ)更節(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-對(duì)應(yīng)的中綴表達(dá)式是（45）。（45）A．a(chǎn)-b-c*d

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

C．-a+b*c-d

D．(a+b)*(-c-d)●為便于存儲(chǔ)和處理一般樹結(jié)構(gòu)形式的信息，常采用孩子ˉ兄弟表示法將其轉(zhuǎn)換成二叉樹（左子關(guān)系表示父子、右子關(guān)系表示兄弟），與下圖所示的樹對(duì)應(yīng)的二叉樹是（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●由權(quán)值為29、12、15、6、23的五個(gè)葉子結(jié)點(diǎn)構(gòu)造的哈夫曼樹為（64），其帶權(quán)路徑長(zhǎng)度為（65）。第四部分樹與二叉樹

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

第四部分樹與二叉樹

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

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

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

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

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

分值：0~5分（每年）分?jǐn)?shù)比重：6%重要知識(shí)點(diǎn)：

1、圖的基本概念和存儲(chǔ)結(jié)構(gòu)

2、圖的遍歷

3、拓?fù)渑判蚝妥钚∩蓸?/p>

4、關(guān)鍵路徑

5、最短路徑第五部分圖

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

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

v1v2v3v4v5v6v7v8v9v1v2v4v7v9v5v3v6v8BAEDCABCDEv1v2v3v4v5v9v6v8v7ABCED拓?fù)渑判蛲負(fù)渑判驅(qū)⒁粋€(gè)有向圖中的所有結(jié)點(diǎn)排成一個(gè)序列，使得圖中所有結(jié)點(diǎn)應(yīng)存在的前驅(qū)和后繼關(guān)系都能在隊(duì)列中體現(xiàn)（前驅(qū)在前，后繼在后）。過程⑴從AOV網(wǎng)中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)并且輸出；⑵從AOV網(wǎng)中刪去該頂點(diǎn)并且刪去所有以該頂點(diǎn)為尾的?。虎侵貜?fù)上述兩步，直到全部頂點(diǎn)都被輸出;第五部分圖

C1C2C3C4C6C5C7拓?fù)湫蛄校篊1,C2,C3,C4,C5,C6,C7

最小生成樹概念生成樹是連通圖上的一個(gè)極小連通子圖。最小生成樹是一個(gè)連通網(wǎng)中所有生成樹中各邊權(quán)值之和最小的生成樹。最小生成樹的算法：

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

abdcef6155542663abdcef15342abdcef1532554關(guān)鍵路徑概念從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度即為完成整個(gè)工程任務(wù)所需的時(shí)間，該路徑叫做關(guān)鍵路徑。關(guān)鍵路徑上的活動(dòng)叫關(guān)鍵活動(dòng)。關(guān)鍵路徑的求法：

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

⑶活動(dòng)的最早開始時(shí)間e[i]⑷活動(dòng)的最晚開始時(shí)間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、求圖中的一個(gè)結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑。2、求圖中任意兩點(diǎn)間的最短路徑。最短路徑的求法：

⑴迪杰斯特拉(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、求圖中的一個(gè)結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑。2、求圖中任意兩點(diǎn)間的最短路徑。最短路徑的求法：

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

abd53863c122真題201105●設(shè)一個(gè)包含N個(gè)頂點(diǎn)，E條邊的簡(jiǎn)單無向圖采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)，則該矩陣中的非零元素?cái)?shù)目為（60）（60）A.N

B.E

C.2E

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

B.n

C.n+2

D.n-1第五部分圖

真題200511●在活動(dòng)圖中，結(jié)點(diǎn)表示項(xiàng)目中各個(gè)工作階段的里程碑，連接各個(gè)結(jié)點(diǎn)的邊表示活動(dòng)，邊上的數(shù)字表示活動(dòng)持續(xù)的時(shí)間。在下面的活動(dòng)圖中，從A到J的關(guān)鍵路徑是(16)，關(guān)鍵路徑長(zhǎng)度是(17)，從E開始的活動(dòng)啟動(dòng)的最早時(shí)間是(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●簡(jiǎn)單無向圖的鄰接矩陣是對(duì)稱的，可以對(duì)其進(jìn)行壓縮存儲(chǔ)。若無向圖G有n個(gè)節(jié)點(diǎn)。若無向圖G有n個(gè)節(jié)點(diǎn)，其鄰接矩陣為A[1..n,1..n],且壓縮存儲(chǔ)在B[1..k]中，則k的值至少為____(40)____。若按行壓縮存儲(chǔ)對(duì)稱矩陣的上三角元素，則當(dāng)n等于10時(shí)，邊(V6，V3)的信息存儲(chǔ)在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)是右圖的合法拓?fù)湫蛄小?/p>

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

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

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

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

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

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

分值：5~15分（每年）分?jǐn)?shù)比重：10%重要知識(shí)點(diǎn)：

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

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

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

查找基本概念：靜態(tài)查找：不涉及插入和刪除操作的查找。動(dòng)態(tài)查找：涉及插入和刪除操作的查找。平均查找長(zhǎng)度：將查找算法進(jìn)行的關(guān)鍵碼的比較次數(shù)的數(shù)學(xué)期望值定義為平均查找長(zhǎng)度。計(jì)算公式為：其中：n：?jiǎn)栴}規(guī)模，查找集合中的記錄個(gè)數(shù)；pi：查找第i個(gè)記錄的概率；ci：查找第i個(gè)記錄所需的關(guān)鍵碼的比較次數(shù)。第六部分排序與查找

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

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

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

動(dòng)態(tài)查找——二叉排序樹結(jié)論：對(duì)同樣一組數(shù)據(jù)元素，如果輸入的順序不同，則所建的二叉樹形態(tài)也不同。特點(diǎn)：

1、一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個(gè)有序序列;

2、每次插入的新結(jié)點(diǎn)都是二叉排序樹上新的葉子結(jié)點(diǎn);

3、找到插入位置后，不必移動(dòng)其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)點(diǎn)的指針；

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

5、新插入的結(jié)點(diǎn)沒有破壞原有結(jié)點(diǎn)之間的關(guān)系。第六部分排序與查找

練習(xí)：關(guān)鍵字的輸入順序?yàn)椋?5,24,53,12,28,90，和24,53,90,12,28,45，分別構(gòu)造二叉排序樹動(dòng)態(tài)查找——二叉排序樹的刪除1.

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

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

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

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

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

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

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

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

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

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

2、再哈希法：同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù)，當(dāng)哈希地址發(fā)生沖突時(shí)，再用其他哈希函數(shù)來計(jì)算地址，直到?jīng)_突不再產(chǎn)生。

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

第六部分排序與查找

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

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

插入類排序直接插入排序：每次將一個(gè)待排序的記錄按其關(guān)鍵碼的大小插入到一個(gè)已經(jīng)排好序的有序序列中，直到全部記錄排好序?yàn)橹?。折半插入排序：以折半查找和直接插入排序兩種方法結(jié)合起來實(shí)現(xiàn)排序；希爾排序：根據(jù)不同的間距di將元素分成組，在各組內(nèi)進(jìn)行直接插入排序，di的值是由大到小，最后為1，即將所有元素放在一組里進(jìn)行排序第六部分排序與查找

第六部分排序與查找

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

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

簡(jiǎn)單選擇4674165314264038866527341147416534626403886652734214167453462640388665273431416265346744038866527344141626274674403886655334514162627347440388665534661416262734384074866553467141626273438407486655346814162627343840468665537491416262734384046536586741014162627343840465365867411141626273438404653657486演示歸并排序基本思想：將兩個(gè)或兩個(gè)以上有序表合并成一個(gè)新的有序表。假設(shè)初始序列含有n個(gè)記錄，首先將這n個(gè)記錄看成n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的有序子序列；在此基礎(chǔ)上，再進(jìn)行兩兩歸并，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為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)分配類排序基本思想：設(shè)待排序的數(shù)據(jù)元素關(guān)鍵字是m位d進(jìn)制整數(shù)（不足m位的關(guān)鍵字在高位補(bǔ)0），設(shè)置d個(gè)桶，分別編號(hào)為0,1,2,…,d-1。1、首先按關(guān)鍵字最低位的數(shù)值依次把各數(shù)據(jù)元素放到相應(yīng)的桶中，然后按照桶號(hào)從小到大和進(jìn)入桶中數(shù)據(jù)元素的先后次序收集分配在各桶中的數(shù)據(jù)元素，這樣就形成了數(shù)據(jù)元素集合的一個(gè)新的排列，我們稱這樣的一次排序過程為一次基數(shù)排序；

2、再對(duì)一次基數(shù)排序得到的序列按關(guān)鍵字次低位的數(shù)值依次把各數(shù)據(jù)元素放到相應(yīng)的桶中，然后按照桶號(hào)從小到大和進(jìn)入桶中數(shù)據(jù)元素的先后次序收集分配在各桶中的數(shù)據(jù)元素；這樣的過程重復(fù)進(jìn)行，當(dāng)完成了第m次基數(shù)排序后，就得到了排好序的數(shù)據(jù)元素序列。第六部分排序與查找

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

2、再對(duì)一次基數(shù)排序得到的序列按關(guān)鍵字次低位的數(shù)值依次把各數(shù)據(jù)元素放到相應(yīng)的桶中，然后按照桶號(hào)從小到大和進(jìn)入桶中數(shù)據(jù)元素的先后次序收集分配在各桶中的數(shù)據(jù)元素；這樣的過程重復(fù)進(jìn)行，當(dāng)完成了第m次基數(shù)排序后，就得到了排好序的數(shù)據(jù)元素序列。第六部分排序與查找

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

(b)第二趟基數(shù)排序

(c)第三趟基數(shù)排序排序方法最好情況平均時(shí)間最壞情況穩(wěn)定性直接插入O(n)O(n2)O(n2)√簡(jiǎn)單選擇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)√基數(shù)O(d(n+rd))O(d(n+rd))O(d(n+rd))√第六部分排序與查找

各種排序方法性