數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)復(fù)習(xí)市公開課金獎(jiǎng)市賽課一等獎(jiǎng)?wù)n件

數(shù)據(jù)結(jié)構(gòu)考研輔導(dǎo)–基礎(chǔ)復(fù)習(xí)浙江大學(xué)計(jì)算機(jī)學(xué)院1第1頁內(nèi)容提要考研概述1基礎(chǔ)內(nèi)容復(fù)習(xí)2線性表、堆棧、隊(duì)列、數(shù)組A樹與圖B查找與排序C2第2頁考研概述考查目標(biāo)了解數(shù)據(jù)結(jié)構(gòu)基本概念：掌握數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)、存放結(jié)構(gòu)及其差異，以及各種基本操作實(shí)現(xiàn)。在掌握基本數(shù)據(jù)處理原理和方法基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析。能夠選擇適當(dāng)數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解。3第3頁考研概述考試形式整卷滿分為150分，考試時(shí)間為180分鐘數(shù)據(jù)結(jié)構(gòu)占45分，預(yù)計(jì)用時(shí)45~50分鐘單項(xiàng)選擇題：40題2分/題，預(yù)計(jì)占10題20分左右，提議用時(shí)不超出2分鐘/題綜合題：70分，預(yù)計(jì)占2題共20~25分，提議用時(shí)不超出10分鐘/題4第4頁考研概述復(fù)習(xí)計(jì)劃基礎(chǔ)理論復(fù)習(xí)例題詳解題目范圍：真題1套+模擬題9套+補(bǔ)充題模擬題第10套將用于最終一天模擬考試5第5頁基礎(chǔ)內(nèi)容復(fù)習(xí)

《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴(yán)蔚敏、吳偉民，清華大學(xué)出版社線性表、堆棧、隊(duì)列、數(shù)組樹與圖查找與排序6第6頁線性表、堆棧、隊(duì)列、數(shù)組線性表定義：n個(gè)數(shù)據(jù)元素有限序列基本操作：隨機(jī)訪問、插入、刪除、前驅(qū)、后繼、倒序等實(shí)現(xiàn)方式：次序存放：數(shù)組aiai+1…………Loc(ai)Loc(ai+1)=Loc(ai)+llLoc(ai)=Loc(a1)+?(i-1)*l7第7頁線性表實(shí)現(xiàn)方式：次序存放：數(shù)組線性表、堆棧、隊(duì)列、數(shù)組是一個(gè)隨機(jī)存取存放結(jié)構(gòu)，方便隨機(jī)存取第i個(gè)數(shù)據(jù)元素插入、刪除復(fù)雜度為O(n)，需要移動(dòng)大量元素8第8頁自測題在n個(gè)結(jié)點(diǎn)次序表中，算法時(shí)間復(fù)雜度是O(1)操作是：訪問第i個(gè)結(jié)點(diǎn)(1≤i≤n)和求第i個(gè)結(jié)點(diǎn)直接前驅(qū)(2≤i≤n)在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）將n個(gè)結(jié)點(diǎn)從小到大排序線性表、堆棧、隊(duì)列、數(shù)組9第9頁線性表、堆棧、隊(duì)列、數(shù)組線性表實(shí)現(xiàn)方式：鏈?zhǔn)酱娣牛烘湵砭€性鏈表存放地址數(shù)據(jù)域指針域1LiNULL7Qian1313Sun119Zhao7頭指針H=19HZhaoQianSunLi若p->data=ai則p->next->data=ai+1typedefstruct

LNode{ElemType data;

struct

LNode*next;}LNode,*LinkList;有時(shí)附加頭結(jié)點(diǎn)10第10頁自測題線性表若采取鏈?zhǔn)酱娣沤Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存放單元地址:必須是連續(xù)部分地址必須是連續(xù)一定是不連續(xù)連續(xù)或不連續(xù)都能夠線性表、堆棧、隊(duì)列、數(shù)組11第11頁線性表、堆棧、隊(duì)列、數(shù)組線性表實(shí)現(xiàn)方式：鏈?zhǔn)酱娣牛烘湵砭€性鏈表插入、刪除復(fù)雜度為O(1)，僅需修改指針而不需要移動(dòng)元素是一個(gè)非隨機(jī)存取存放結(jié)構(gòu)，不方便隨機(jī)存取第i個(gè)數(shù)據(jù)元素*靜態(tài)鏈表（p.31-35）12第12頁自測題下面敘述不正確是（）線性表在鏈?zhǔn)酱娣艜r(shí)，查找第i個(gè)元素時(shí)間同i值成正比線性表在鏈?zhǔn)酱娣艜r(shí)，查找第i個(gè)元素時(shí)間同i值無關(guān)線性表在次序存放時(shí)，查找第i個(gè)元素時(shí)間同i值成正比線性表在次序存放時(shí)，查找第i個(gè)元素時(shí)間同i值無關(guān)線性表、堆棧、隊(duì)列、數(shù)組13第13頁自測題在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最終結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行：s->next=p;p->next=s;s->next=p->next;p->next=s;s->next=p->next;p=s;p->next=s;s->next=p;線性表、堆棧、隊(duì)列、數(shù)組ps14第14頁自測題在單鏈表中，指針p指向元素為x結(jié)點(diǎn)，實(shí)現(xiàn)“刪除x后繼”語句是：p=p->next;p->next=p->next->next;p->next=p;p=p->next->next;線性表、堆棧、隊(duì)列、數(shù)組xp15第15頁線性表、堆棧、隊(duì)列、數(shù)組線性表實(shí)現(xiàn)方式：鏈?zhǔn)酱娣牛烘湵硌h(huán)鏈表雙向鏈表HHHH有時(shí)設(shè)尾指針可簡化一些操作，如兩表合并。16第16頁自測題設(shè)一個(gè)鏈表最慣用操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選取()最節(jié)約時(shí)間。單鏈表單循環(huán)鏈表帶尾指針單循環(huán)鏈表帶頭結(jié)點(diǎn)雙循環(huán)鏈表線性表、堆棧、隊(duì)列、數(shù)組17第17頁自測題將線性表La和Lb頭尾連接，要求時(shí)間復(fù)雜度為O(1)，且占用輔助空間盡可能小。應(yīng)該使用哪種結(jié)構(gòu)？單鏈表單循環(huán)鏈表帶尾指針單循環(huán)鏈表帶頭結(jié)點(diǎn)雙循環(huán)鏈表線性表、堆棧、隊(duì)列、數(shù)組tmp=La->next;La->next=Lb->next;Lb->next=tmp;LaLb18第18頁線性表、堆棧、隊(duì)列、數(shù)組線性表練習(xí)1：分別實(shí)現(xiàn)數(shù)組、單鏈表、循環(huán)鏈表、雙向鏈表插入和刪除操作。練習(xí)2：實(shí)現(xiàn)單鏈表原地逆轉(zhuǎn)。練習(xí)3：分別用一元多項(xiàng)式兩種表示實(shí)現(xiàn)多項(xiàng)式加法。32-51-23000-1103200P19第19頁自測題給定2個(gè)帶有表頭結(jié)點(diǎn)單鏈表頭指針L1和L2，結(jié)點(diǎn)結(jié)構(gòu)為。假設(shè)這2個(gè)鏈表結(jié)點(diǎn)已經(jīng)按Data域遞增有序，請?jiān)O(shè)計(jì)算法把它們合并成一個(gè)按Data域遞增有序鏈表。注意：算法不能使用額外結(jié)點(diǎn)空間。

線性表、堆棧、隊(duì)列、數(shù)組DataNext算法思緒為次序比較L1和L2當(dāng)前所指兩結(jié)點(diǎn)Data域，將小那個(gè)結(jié)點(diǎn)從原鏈表摘除，貼到合并鏈表尾部。如此進(jìn)行到最少其中一個(gè)鏈表為空。若此時(shí)另一個(gè)鏈表不為空，則將另一個(gè)鏈表整個(gè)貼到合并鏈表尾部。注意原始2個(gè)鏈表有2個(gè)頭結(jié)點(diǎn)，合并后只保留一個(gè)，需要釋放另一個(gè)空間。20第20頁ListMergeSortedLists(ListL1,ListL2){ ListL=L1;ListTail=L2; L1=L1->Next;L2=L2->Next; free(Tail);Tail=L; //釋放第二個(gè)鏈表表頭，并將新鏈表表尾指針Tail初始化

while(L1&&L2){ if(L1->Data>L2->Data){ Tail->Next=L2;L2=L2->Next; //第二個(gè)鏈表第一結(jié)點(diǎn)值小，將其插入新鏈表尾} else{ Tail->Next=L1;L1=L1->Next; //第一個(gè)鏈表第一結(jié)點(diǎn)值小，將其插入新鏈表尾} Tail=Tail->Next; } if(L1)Tail->Next=L1; //將剩下第一個(gè)鏈表接到新鏈表表尾

elseif(L2)Tail->Next=L2; //將剩下第二個(gè)鏈表接到新鏈表表尾

returnL;}21第21頁自測題給定2個(gè)帶有表頭結(jié)點(diǎn)單鏈表頭指針L1和L2，結(jié)點(diǎn)結(jié)構(gòu)為。假設(shè)這2個(gè)鏈表結(jié)點(diǎn)已經(jīng)按Data域遞增有序，請?jiān)O(shè)計(jì)算法把它們合并成一個(gè)按Data域遞減有序鏈表。注意：算法不能使用額外結(jié)點(diǎn)空間。

線性表、堆棧、隊(duì)列、數(shù)組DataNext解題基本思緒不變，只要將原來表尾插入改為表頭插入即可。當(dāng)然，當(dāng)其中一個(gè)鏈表為空而另一個(gè)鏈表不為空時(shí)，不能直接將剩下鏈表貼到表尾，而必須將剩下結(jié)點(diǎn)一個(gè)一個(gè)插入表頭。22第22頁自測題若L1和L2是有序數(shù)組，其結(jié)點(diǎn)已經(jīng)按Data域遞增有序，請?jiān)O(shè)計(jì)算法把它們合并成一個(gè)按Data域遞增有序數(shù)組。注意：要求將L2并入L1，而且要求移動(dòng)元素次數(shù)盡可能少。

線性表、堆棧、隊(duì)列、數(shù)組必須事先算好合并后L1長度，然后從L1最終尾部向前插入元素。插入過程與前面算法類似，不過是從尾部開始比較L1和L2對應(yīng)元素大小，將較大元素先插入到后面位置。23第23頁voidMergeSortedArrays(ElementTypeL1[],intN1,ElementTypeL2[],intN2){ intp1,p2,cur; p1=N1-1; //p1指向L1當(dāng)前處理元素位置 p2=N2-1; //p2指向L2當(dāng)前處理元素位置 cur=N1+N2-1; //cur指向下一個(gè)要插入元素在L1中最終位置

while((p1>=0)&&(p2>=0)){ if(L1[p1]>L2[p2]){ L1[cur]=L1[p1];p1--; } else{ L1[cur]=L2[p2];p2--; } cur--; } while(p2>=0){//將p2剩下元素插入到L1中

L1[p2]=L2[p2];p2--; }}24第24頁堆棧概念：后進(jìn)先出，限定僅在表尾進(jìn)行插入刪除線性表。表示與實(shí)現(xiàn)：次序棧：數(shù)組，top++，top--鏈棧：鏈表，top即為頭指針應(yīng)用：括號(hào)匹配檢驗(yàn)、表示式求值、n階Hanoi塔問題（經(jīng)典遞歸）、迷宮問題線性表、堆棧、隊(duì)列、數(shù)組25第25頁自測題判定一個(gè)棧ST(最多元素為m0)為空條件是：ST->top!=0ST->top

==0ST->top!=m0ST->top

==m0線性表、堆棧、隊(duì)列、數(shù)組26第26頁自測題有六個(gè)元素以6，5，4，3，2，1次序進(jìn)棧，問以下哪一個(gè)不是正當(dāng)出棧序列？543612453126346521234156線性表、堆棧、隊(duì)列、數(shù)組27第27頁自測題若一個(gè)棧輸入序列為1，2，3，…，n，輸出序列第一個(gè)元素是i，則第j個(gè)輸出元素是：i–j–1i–jj–i–1不確定線性表、堆棧、隊(duì)列、數(shù)組28第28頁隊(duì)列概念：先進(jìn)先出，限定僅在隊(duì)尾進(jìn)行插入、僅在隊(duì)頭進(jìn)行刪除線性表。表示與實(shí)現(xiàn)：次序隊(duì)列：循環(huán)數(shù)組，(rear+1)%N,(front+1)%N鏈棧：鏈表，front為頭指針，rear為尾指針應(yīng)用：離散事件模擬線性表、堆棧、隊(duì)列、數(shù)組29第29頁自測題循環(huán)隊(duì)列用數(shù)組A[0,N－1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中元素個(gè)數(shù)是：(rear-front+N)%Nrear-front+1rear-front-1rear-front線性表、堆棧、隊(duì)列、數(shù)組[0][1][...][N-1]frontrear30第30頁自測題棧和隊(duì)列共同特點(diǎn)是：都是先進(jìn)后出

都是先進(jìn)先出

只允許在同一端點(diǎn)處插入和刪除

沒有共同點(diǎn)

線性表、堆棧、隊(duì)列、數(shù)組31第31頁數(shù)組——特殊矩陣壓縮存放對稱矩陣：線性表、堆棧、隊(duì)列、數(shù)組an,1a11a21a22a31……an,n……SAk0123…………*上（下）三角矩陣同理存放，或許多存放一個(gè)常數(shù)（若另二分之一矩陣元素是非零常數(shù)）。32第32頁線性表、堆棧、隊(duì)列、數(shù)組數(shù)組——特殊矩陣壓縮存放m對角矩陣：或者

稀疏矩陣：nrow=3,ncol=5,ntotal=6(1,3,4),(2,1,7),(2,3,1),(2,5,-3),(3,2,-2),(3,5,5),33第33頁線性表、堆棧、隊(duì)列、數(shù)組數(shù)組——特殊矩陣壓縮存放稀疏矩陣：三元組次序表：以行序?yàn)橹餍颍涡蚺帕袨槿M1維數(shù)組，并存行數(shù)、列數(shù)、非0元個(gè)數(shù)。typedefstruct

{

int i,j;ElemType v;}Triple;typedefunion

{Triple data[MAXSIZE+1];

int nrow,ncol,ntotal;}Sparse_Matrix;ij3553-22334第34頁線性表、堆棧、隊(duì)列、數(shù)組數(shù)組——特殊矩陣壓縮存放稀疏矩陣：三元組次序表：快速轉(zhuǎn)置ijv12723-2314321535-325ij3553-223對每列掃描整個(gè)數(shù)組：O(ncolntotal)怎樣一步到位，放入正確位置？num[col]–第col列中非0元個(gè)數(shù)；cpot[col]–第col列中第1個(gè)非0元在轉(zhuǎn)置矩陣中位置；cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];12345col11202num12355cpot42O(ncol+ntotal)35第35頁線性表、堆棧、隊(duì)列、數(shù)組數(shù)組——特殊矩陣壓縮存放稀疏矩陣：行邏輯鏈接次序表：矩陣相乘typedefstruct

{Triple data[MAXSIZE+1];int rpos[MAXRC+1];

int nrow,ncol,ntotal;}Sparse_Matrix;各行第1個(gè)非0元在數(shù)組中位置設(shè)M=A

B，則有關(guān)鍵：對每個(gè)A.data[p]，找全部B.data[q]，滿足(A.data[p].j==B.data[q].i)，將(A.data[p].vB.data[q].v)累加到對應(yīng)暫時(shí)行向量，最終壓縮到M中。O(ArowBcol

+AtotalBtotal/Brow)36第36頁線性表、堆棧、隊(duì)列、數(shù)組數(shù)組——特殊矩陣壓縮存放稀疏矩陣：十字鏈表：矩陣相加413721123-325-232535123M.rhead12345M.chead計(jì)算A+B

復(fù)雜度為

O(Atotal+Btotal)37第37頁自測題設(shè)稀疏矩陣A有t個(gè)非零元素，用二維數(shù)組存放時(shí)占用m*n個(gè)單元。問稀疏矩陣三元組表示法在什么情況下比二維數(shù)組存放節(jié)約空間？t<m*nt<m*n/3t<m*n/3–1t<m*n–1線性表、堆棧、隊(duì)列、數(shù)組38第38頁樹與圖樹與二叉樹概念樹概念：度(degree)；層(level)–注意：根為第1層；深度(depth)–結(jié)點(diǎn)最大層次。二叉樹概念：左右有序性質(zhì)1：第i層最多有2i-1個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為k二叉樹最多有2k-1個(gè)結(jié)點(diǎn)。性質(zhì)3：若n0為葉子數(shù)，n2為度為2結(jié)點(diǎn)數(shù)，則有n0=n2+1。性質(zhì)4：含有n個(gè)結(jié)點(diǎn)完全二叉樹深度為log2n+1。39第39頁樹與二叉樹概念二叉樹概念：性質(zhì)5：對有n個(gè)結(jié)點(diǎn)且次序編號(hào)完全二叉樹，其任一結(jié)點(diǎn)i

有樹與圖40第40頁二叉樹存放結(jié)構(gòu)次序存放結(jié)構(gòu)：數(shù)組–僅適合用于完全二叉樹鏈?zhǔn)酱娣沤Y(jié)構(gòu)：在含有n個(gè)結(jié)點(diǎn)二叉鏈表中有個(gè)空鏈域。二叉樹遍歷先序、中序、后序、層次樹與圖LchildDataRchildParent1234567n+141第41頁自測題一棵完全二叉樹共有2435個(gè)結(jié)點(diǎn)，則其中度為0結(jié)點(diǎn)數(shù)為？12181217不確定812樹與圖前11層共有211-1=2047個(gè)結(jié)點(diǎn)第12層共有2435-2047=388個(gè)結(jié)點(diǎn)388+[210–388/2]=121842第42頁自測題在一棵高度為h(假定樹根結(jié)點(diǎn)層號(hào)為0)完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)大于

2h–12h+12h–1

2h樹與圖43第43頁自測題結(jié)點(diǎn)中序遍歷為xyz不一樣二叉樹，它有幾個(gè)不一樣狀態(tài)？

3

456

樹與圖yxzzxyzyxxzyxyz44第44頁自測題前序遍歷和中序遍歷結(jié)果相同二叉樹為

普通二叉樹

只有根結(jié)點(diǎn)二叉樹全部結(jié)點(diǎn)只有左子樹二叉樹全部結(jié)點(diǎn)只有右子樹二叉樹

樹與圖45第45頁自測題前序遍歷和后序遍歷結(jié)果相同二叉樹為

普通二叉樹

只有根結(jié)點(diǎn)二叉樹全部結(jié)點(diǎn)只有左子樹二叉樹全部結(jié)點(diǎn)只有右子樹二叉樹

樹與圖46第46頁自測題已知中序遍歷和前序遍歷結(jié)果，給出算法求后序遍歷結(jié)果。

樹與圖（1）從前序遍歷結(jié)果推斷該樹樹根。（2）找出左子樹和右子樹中序和前序遍歷結(jié)果。（3）重復(fù)上述過程，找出左、右子樹根結(jié)點(diǎn)，并逐步往下擴(kuò)展，直到生成一顆完整二叉樹。中序前序左左右右47第47頁OutPostOrder(PreOrder,InOrder){ //已知前序序列PreOrder、中序序列InOrder，求后序序列

1）應(yīng)用前述方法，從序列PreOrder和InOrder中推斷出： 樹根r; 左子樹前序遍歷序列PreOrderLeft 和中序遍歷序列InOrderLeft; 右子樹前序遍歷序列PreOrderRight 和中序遍歷序列InOrderRight;2）遞歸OutPostOrder(PreOrderLeft,InOrderLeft);3）遞歸OutPostOrder(PreOrderRight,InOrderRight);4）輸出r;}48第48頁自測題下面是某二叉樹三種遍歷部分結(jié)果，請畫出對應(yīng)二叉樹。前序:_B_F_ICEH_G中序:D_KFIA_EJC_后序:_K_FBHJ_G_A

樹與圖ABCDFKIEHJGABDKDIHJGEC49第49頁自測題在任意一顆二叉樹中，任何兩個(gè)葉結(jié)點(diǎn)在先序、中序、后序中相對次序怎樣？

不變不一樣不能確定以上都不是

樹與圖50第50頁線索二叉樹概念：樹與圖LchildDataRchildLtagRtag0:Lchild指向左孩子1:Lchild指向前驅(qū)0:Rchild指向右孩子1:Rchild指向后繼+ADBC中序遍歷：A+BCD000+01A100001D11B11C1頭結(jié)點(diǎn)中序線索二叉樹51第51頁樹與圖線索二叉樹結(jié)構(gòu)：中序：增加pre指針，指向剛訪問過結(jié)點(diǎn)后序：須增加Parent指針域優(yōu)點(diǎn)：遍歷不需要堆棧。若經(jīng)常需要遍歷二叉樹或查找結(jié)點(diǎn)在遍歷序列中前驅(qū)和后繼，則應(yīng)采取線索鏈表作為存放結(jié)構(gòu)。52第52頁二叉排序樹定義：左<根<右；左右均為二叉排序樹。主要操作：查找、插入、刪除（分3種情況）問題：樹深與插入次序相關(guān)，最壞情況蛻變?yōu)閱沃?，到達(dá)O(n)。樹與圖53第53頁平衡二叉樹(AVL)：確保樹深O(logn)定義：BF=D(左)–D(右)。則AVL樹上全部結(jié)點(diǎn)BF只能是-1、0、1。旋轉(zhuǎn)：單向左旋樹與圖A1B0BLBRALA2B1BLBRALBLB0AALBR054第54頁平衡二叉樹(AVL)旋轉(zhuǎn)：單向右旋樹與圖A1B0BRBLARA2B1BRBLARB0AARBLBR055第55頁平衡二叉樹(AVL)旋轉(zhuǎn)：雙向旋轉(zhuǎn)（先左后右）樹與圖A1B0BLARC0CRCLA2B1BLARC1CRCLORBLARC0A1or0CRB0or1CLOR56第56頁平衡二叉樹(AVL)旋轉(zhuǎn)：雙向旋轉(zhuǎn)（先右后左）樹與圖A1B0BRALC0CLCRA2B1BRALC1CLCRORBRALC0A0or1CLB1or0CROR57第57頁自測題若AVL樹深度是6，則該樹最少結(jié)點(diǎn)數(shù)是？13172033樹與圖N6=N5+N4+1N5=N4+N3+1N4=N3+N2+1N3=N2+N1+1N2=2,N1=1Nh=Nh-1+Nh-2+158第58頁樹和森林樹存放結(jié)構(gòu)：雙親表示法

找雙親和根結(jié)點(diǎn)輕易，但找孩子必須遍歷數(shù)組。孩子表示法

適合包括

孩子操作，但不方便找雙親。樹與圖RABCDEFGHK-1R0idataparent123456789ABCDEFGHK000113666R0idata123456789ABCDEFGHK-1parent000113666child12345678959第59頁樹和森林樹存放結(jié)構(gòu)：孩子弟兄表示法（二叉樹表示法）樹與圖first_childDatanext_siblingRABCDEFGHKRABCDEFGHK60第60頁樹和森林森林與二叉樹轉(zhuǎn)換森林F={T1T2...Tm}->二叉樹B=(R,LB,RB)二叉樹B=(R,LB,RB)

->森林F={T1T2...Tm}樹與圖if(!F)B=NULL;else{ R=root(T1); LB={T11T12...T1m1}; RB={T2...Tm}; }if(!B)F=NULL;else{ root(T1)=R; {T11T12...T1m1}=LB; {T2...Tm}=RB; }61第61頁樹和森林樹和森林遍歷樹遍歷：先根（次序）遍歷==二叉樹先序遍歷后根（次序）遍歷==二叉樹中序遍歷森林遍歷：先序遍歷==二叉樹先序遍歷中序遍歷==二叉樹中序遍歷樹與圖62第62頁自測題設(shè)森林F對應(yīng)二叉樹為B，它有m個(gè)結(jié)點(diǎn)。B根為p，p右子樹結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹結(jié)點(diǎn)個(gè)數(shù)是？m-nm-n-1n+1無法確定

樹與圖mn63第63頁自測題樹最適適用來表示有序數(shù)據(jù)元素

無序數(shù)據(jù)元素

元素之間無聯(lián)絡(luò)數(shù)據(jù)

元素之間有分支層次關(guān)系

樹與圖64第64頁樹應(yīng)用等價(jià)類問題：給定集合Sn個(gè)元素，以及m個(gè)形如(x,y)等價(jià)偶對，求S等價(jià)類劃分。樹與圖

初始化n個(gè)只包含1個(gè)元素子集;

while(讀入x,y){

if(!(Find(x)==Find(y)))

Union

兩集合; }10687419235[1]4[2]0[10]0[9]4[8]10[7]10[6]10[5]2[4]0[3]2S65第65頁樹應(yīng)用等價(jià)類問題Unionbysize–根統(tǒng)計(jì)(-結(jié)點(diǎn)數(shù))，小樹并入大樹Find+壓縮路徑–將Find路徑上結(jié)點(diǎn)都變成根孩子樹與圖10687419235[1]4[2]-3[10]-7[9]4[8]10[7]10[6]10[5]2[4]8[3]2SUnion(2,10)-1010Find(9)106874192351010*等價(jià)劃分n元集合復(fù)雜度為O(n(n)

),(n)4對通常見到n成立。66第66頁哈夫曼(Huffman)樹和哈夫曼編碼哈夫曼樹：帶權(quán)路徑長度最小二叉樹樹與圖75247524路徑長度=72+52+22+42=367524路徑長度=73+53+21+42=46路徑長度=71+52+23+43=3567第67頁哈夫曼(Huffman)樹和哈夫曼編碼哈夫曼樹結(jié)構(gòu)將n個(gè)帶權(quán)結(jié)點(diǎn)作為n棵只有根二叉樹森林；選2棵根權(quán)值最小樹，作為左右子樹結(jié)構(gòu)新樹，新根權(quán)值=左右子樹根權(quán)值和；將上述2棵樹刪除，將新樹加入森林；重復(fù)第2、3步，直到只剩1棵樹，即是哈夫曼樹。樹與圖68第68頁哈夫曼(Huffman)樹和哈夫曼編碼哈夫曼編碼例：aaaxuaxz

普通被存為8個(gè)字符，占64字節(jié)。但因只有4個(gè)不一樣字符，故可編碼為a=00,u=01,x=10,z=11，只需要占16個(gè)字節(jié)。若采取哈夫曼編碼a=0,u=110,x=10,z=111，則得到00010110010111，只需要占14個(gè)字節(jié)。注意：任一字符編碼都不是另一字符編碼前綴

–前綴編碼。樹與圖69第69頁哈夫曼(Huffman)樹和哈夫曼編碼哈夫曼編碼結(jié)構(gòu)：將字符出現(xiàn)頻率作為權(quán)重，結(jié)構(gòu)哈夫曼樹，并按左0右1編碼。

例：aaaxuaxz樹與圖a:4x:2u:1z:1a:4x:2u:1z:1248000111a=0x=10u=110z=111思索：給定編碼，怎樣判斷是否哈夫曼編碼？70第70頁自測題哈夫曼樹有n個(gè)葉結(jié)點(diǎn)，則該樹共有多少個(gè)結(jié)點(diǎn)？2n2n-12n+1不能確定樹與圖N0=nN1=02*N2=N–1N=N0+N1+N2N=?71第71頁圖概念（p.156-160）圖存放及基本操作鄰接矩陣法無向圖頂點(diǎn)度有向圖頂點(diǎn)度網(wǎng)樹與圖72第72頁圖存放及基本操作鄰接表法樹與圖V1V2V3V4V1V2V3V40123iV1dataV2V3V421300123iV1dataV2V3V4312003020123iV1dataV2V3V43020逆鄰接表*邊稀疏時(shí)節(jié)約空間，但判斷任意兩頂點(diǎn)是否有弧相連時(shí)，則不如鄰接矩陣方便。73第73頁自測題含有n個(gè)頂點(diǎn)無向圖最多有幾條邊？

n(n-1)/2n(n+1)/2n2/22n

樹與圖74第74頁自測題在一個(gè)圖中，全部點(diǎn)度數(shù)之和等于全部邊數(shù)目標(biāo)多少倍？1/2124樹與圖75第75頁自測題一個(gè)無向圖采取鄰接矩陣存放，該鄰接矩陣一定是一個(gè)__對稱矩陣對角矩陣三角矩陣稀疏矩陣樹與圖76第76頁樹與圖自測題從鄰接矩陣能夠看出，該圖共有（）個(gè)頂點(diǎn)；假如是有向圖該圖共有（）條弧；假如是無向圖，則共有（）條邊

9,5,53,4,26,3,31,2,277第77頁圖遍歷深度優(yōu)先(DFS)：類似于樹先序遍歷。遞歸，需要堆棧。鄰接矩陣–O(n2)；鄰接表–

O(n+e)。廣度優(yōu)先(BFS)：類似于樹層次遍歷。需要隊(duì)列。時(shí)間復(fù)雜度與DFS相同。樹與圖78第78頁自測題已知無向圖為G=(V,E)，其中，頂點(diǎn)集合為V={v1,v2,v3,v4,v5,v6,v7}，邊集合為E={(v1,v2),(v1,v3),(v2,v4),(v2,v6),(v4,v5),(v4,v7),(v5,v6)}，請分別給出依據(jù)該鄰接表從頂點(diǎn)v1出發(fā)進(jìn)行深度優(yōu)先搜索與廣度優(yōu)先搜索后頂點(diǎn)序列。當(dāng)有各種選擇時(shí)，按序號(hào)先后訪問。深度優(yōu)先搜索序列：v1,v2,v4,v5,v6,v7,v3廣度優(yōu)先搜索序列：v1,v2,v3,v4,v6,v5,v7樹與圖123456779第79頁圖基本應(yīng)用及其復(fù)雜度分析最?。ù鷥r(jià)）生成樹普里姆(Prim)算法：一棵樹生長樹與圖v1v2v6v7v3v4v52421310758461*復(fù)雜度為

O(n2)，與邊數(shù)無關(guān)，適合于求邊稠密網(wǎng)最小生成樹。80第80頁圖基本應(yīng)用及其復(fù)雜度分析最?。ù鷥r(jià)）生成樹克魯斯卡爾(Kruskal)算法：森林生長樹與圖v1v2v6v7v3v4v52421310758461*適合于求邊稀疏網(wǎng)最小生成樹，復(fù)雜度為

O(eloge)。81第81頁自測題已知一個(gè)帶權(quán)連通圖G=(V,E)，其中頂點(diǎn)集合為V={1,2,3,4,5}，其鄰接矩陣如圖，求出其全部可能最小生成樹。樹與圖∞769∞7∞84468∞6∞946∞2∞4∞2∞82第82頁圖基本應(yīng)用及其復(fù)雜度分析最短路徑單源（帶權(quán)）最短路：迪杰斯特拉(Dijkstra)算法

貪心，按長度遞增生成，當(dāng)新頂點(diǎn)使路徑更短時(shí)，更新路徑，O(n2)。多源（帶權(quán)）最短路：弗洛伊德(Floyd)算法O(n3)，但比重復(fù)Dijkstra算法簡單。樹與圖83第83頁圖基本應(yīng)用及其復(fù)雜度分析拓?fù)渑判颍河邢驘o環(huán)圖(DAG)應(yīng)用之一選一個(gè)無前驅(qū)頂點(diǎn)輸出；刪除該頂點(diǎn)以及全部以之為尾?。恢貜?fù)第1、2步，直到全部頂點(diǎn)輸出，或不存在無前驅(qū)頂點(diǎn)(說明有環(huán))。注意：拓?fù)渑判蚩煞奖銠z驗(yàn)有向圖中是否存在環(huán)；確定無環(huán)時(shí)，也可用DFS進(jìn)行拓?fù)渑判颍顺鯠FS次序即為逆向拓?fù)湫?；DFS可方便檢驗(yàn)無向圖中是否存在環(huán)(若碰到回邊即有環(huán))。樹與圖84第84頁圖基本應(yīng)用及其復(fù)雜度分析關(guān)鍵路徑：AOE網(wǎng)–帶權(quán)DAG樹與圖012345678startfinisha0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=7a8=4a9=2a10=40645771614181816147105660232385第85頁自測題判斷有向圖是否存在回路，除了能夠利用拓?fù)渑判蚍椒ㄍ猓€能夠利用__求關(guān)鍵路徑方法

求最短路徑Dijkstra方法

深度優(yōu)先遍歷算法

廣度優(yōu)先遍歷算法

樹與圖86第86頁自測題弗洛伊德(Floyd)算法是求圖中每一對結(jié)點(diǎn)之間最短路徑算法。請描述該算法，而且回答：怎樣用該算法判斷圖是否有回路？請說明理由。樹與圖檢驗(yàn)對角元DN–1[i][i]，若存在非對角元，就表明圖中有回路。因?yàn)槿鬌N–1[i][i]非，說明存在某個(gè)k，使得Dk[i][i]值被更新為（Dk–1[i][k]+Dk–1[k][i]），即存在一條從i到k、再從k到i路徑。87第87頁自測題怎樣判斷圖中有負(fù)回路（即回路中邊權(quán)值之和為負(fù)數(shù)）？請說明理由。樹與圖將對角元Cost[i][i]初始化為0，當(dāng)Dk[i][i]<0時(shí)，圖中必存在負(fù)回路。88第88頁查找與排序查找概念：靜態(tài)查找動(dòng)態(tài)查找（隨時(shí)插入刪除）平均查找長度=PiCi，其中Pi為查找第i個(gè)統(tǒng)計(jì)概率，滿足Pi=1；Ci是找到第i個(gè)統(tǒng)計(jì)需要比較次數(shù)。當(dāng)查找不成功情況也考慮在內(nèi)時(shí)，平均查找長度是（成功+不成功）平均查找長度。89第89頁查找次序查找法：逐一比較。若對n個(gè)統(tǒng)計(jì)做等概率查找（即Pi=1/n），則平均查找長度為不成功查找必定進(jìn)行n+1次比較。設(shè)成功與不成功概率相同，都是1/2n，則平均查找長度為缺點(diǎn)：效率低優(yōu)點(diǎn)：簡單、適用面廣–對結(jié)構(gòu)無要求，不要求有序，也適合用于鏈表。查找與排序(n+1)/2。3(n+1)/4。90第90頁查找折半查找法：有序表查找成功查找最多比較次數(shù)為等概率成功查找平均查找長度為優(yōu)點(diǎn)：效率高缺點(diǎn)：只適合用于有序表，且不適合用于線性鏈表查找與排序log2n+1。(1+1/n)log2(n+1)-1。91第91頁查找B樹：平衡多路查找樹查找與排序111127139347536419911824378135每個(gè)結(jié)點(diǎn)至多有m棵子樹；若根不是葉子，則最少有2棵子樹；除根之外全部非葉子結(jié)點(diǎn)最少有m/2棵子樹；全部非葉子結(jié)點(diǎn)包含(n,p0,K1,p1,K2,p2,...,Kn,pn),其中Ki為關(guān)鍵字且有序（遞增）,pi所指子樹中所相關(guān)鍵字<Ki+1,pn所指子樹中所相關(guān)鍵字>Kn。全部葉子在同一層，為NULL。4723在有N個(gè)關(guān)鍵字m階B樹上進(jìn)行查找，從根結(jié)點(diǎn)到關(guān)鍵字所在結(jié)點(diǎn)路徑上包括結(jié)點(diǎn)數(shù)不超出92第92頁查找B樹：插入、刪除查找與排序303123750617010024539045303037262630375061701005390453123724268561708545312372430

26506110053709085705061100855390737122445703730263127703730263127506110085539024453123750617010024539045最小值50最小值615333753701002461905061245093第93頁自測題下面關(guān)于m階B樹說法正確是（）每個(gè)結(jié)點(diǎn)最少有兩棵非空子樹樹中每個(gè)結(jié)點(diǎn)至多有m一1個(gè)關(guān)鍵字全部葉子在同一層上當(dāng)插入一個(gè)數(shù)據(jù)項(xiàng)引發(fā)B樹結(jié)點(diǎn)分裂后，樹長高一層查找與排序94第94頁自測題B-樹中葉子結(jié)點(diǎn)數(shù)s與關(guān)鍵字?jǐn)?shù)n關(guān)系是s=n/2s=n-1s=n+1

無法確定查找與排序設(shè)B-樹第i個(gè)結(jié)點(diǎn)子樹數(shù)為Ci，則該結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)Ni=Ci-1。對于有k個(gè)結(jié)點(diǎn)B-樹：n=∑Ni=∑(Ci-1)=∑Ci-k

每個(gè)結(jié)點(diǎn)（除根結(jié)點(diǎn)）都是一棵子樹：∑Ci=(k-1)+s95第95頁查找散列(Hash)表及其查找關(guān)鍵問題：設(shè)計(jì)哈希函數(shù)處理同義詞沖突哈希函數(shù)：（任一關(guān)鍵字等概率映射到任一地址哈希函數(shù)是均勻(Uniform)）各種方法（p.253-256，其中key%p最常見）沖突處理開放定址法：線性、二次（）、偽隨機(jī)探測再散列再哈希法（沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址）鏈地址法（同義詞鏈表）查找與排序96第96頁查找散列(Hash)表及其查找查找分析裝填因子哈希表平均查找長度是

函數(shù)，而不是n

函數(shù)從非鏈地址處理沖突哈希表中刪除一個(gè)統(tǒng)計(jì)，須在該統(tǒng)計(jì)位置上填入一個(gè)特殊符號(hào)，以免找不到在它之后填入同義詞對于預(yù)先知道且規(guī)模不大關(guān)鍵字集，應(yīng)盡力設(shè)計(jì)不發(fā)生沖突完美哈希函數(shù)查找與排序97第97頁自測題下面關(guān)于哈希查找說法正確是（）哈希函數(shù)結(jié)構(gòu)越復(fù)雜越好，因?yàn)檫@么隨機(jī)性好，沖突小除留余數(shù)法是全部哈希函數(shù)中最好不存在尤其好與壞哈希函數(shù)，要視情況而定若需在哈希表中刪去一個(gè)元素，不論用何種方法處理沖突都只要簡單將該元素刪去即可查找與排序98第98頁自測題設(shè)有一組統(tǒng)計(jì)關(guān)鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法結(jié)構(gòu)散列表，散列函數(shù)為H（key）=keyMOD13，散列地址為1鏈中有幾個(gè)統(tǒng)計(jì)？

1234查找與排序99第99頁自測題設(shè)哈希表長m＝14，哈希函數(shù)H（key）＝key％11。表中已經(jīng)有4個(gè)結(jié)點(diǎn)：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址為空。假如用二次探測再散列處理沖突，關(guān)鍵字為49結(jié)點(diǎn)地址是8359查找與排序100第100頁內(nèi)部排序概念基本操作：比較+移動(dòng)存放方式：數(shù)組：必須移動(dòng)統(tǒng)計(jì)靜態(tài)鏈表：表排序，僅修改指針數(shù)組+地址：地址排序，然后調(diào)整統(tǒng)計(jì)位置穩(wěn)定排序法：關(guān)鍵字等值統(tǒng)計(jì)在排序前后先后位置不變查找與排序101第101頁內(nèi)部排序插入排序直接插入排序：理撲克牌過程。正序最快O(n)，逆序最慢O(n2)，平均O(n2)。折半插入排序：查找過程用“折半查找”，降低了比較次數(shù)，但移動(dòng)次數(shù)不變，還是O(n2)。氣泡排序(bubblesort)每趟比較相臨統(tǒng)計(jì)，最大值沉入水底。復(fù)雜度與直接插入排序類似。查找與排序102第102頁自測題用直接插入排序方法對下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少是哪個(gè)？94,32,40,90,80,46,21,6932,40,21,46,69,94,90,8021,32,46,40,80,69,90,9490,69,80,46,21,32,94,40查找與排序103第103頁自測題若用冒泡排序方法對序列{10,14,26,29,41,52}從大到小排序，需進(jìn)行多少次比較？3101525查找與排序5+4+3+2+1=15104第104頁內(nèi)部排序簡單項(xiàng)選擇擇排序方法：每次從未排序序列中（i~n–1）找關(guān)