大學數(shù)據(jù)結構復習要點

A—熟練掌握B—理解C—了解第一章：緒論1.基本概念：包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構和數(shù)據(jù)的相關運算。C四類數(shù)據(jù)組織結構：集合、線性表、樹形、圖狀結構C數(shù)據(jù)的存儲方式：順序存儲和鏈式存儲。B2.算法和分析算法的特征、時間復雜度的分析和常見的時間復雜度增長率排序、空間復雜度B本章重點：分析算法時間復雜度例1.下面關于算法說法錯誤的選項是〔〕A．算法最終必須由計算機程序實現(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的D例2.以下那一個術語與數(shù)據(jù)的存儲結構無關？〔〕A．棧B.哈希表C.線索樹D.雙向鏈表A．例3.．求下段程序的時間復雜度：voidmergesort(inti,intj){ intm; if(i!=j){ m=(i+j)/2; mergesort(i,m); mergesort(m+1,j); merge(i,j,m);}}其中mergesort()用于對數(shù)組a[n]歸并排序，調用方式為mergesort(0,n-1);，merge()用于兩個有序子序列的合并，是非遞歸函數(shù)，時間復雜度為。解：分析得到的時間復雜度的遞歸關系：為merge〔〕所需的時間，設為cn〔c為常量〕。因此 令，有有第二章：線性表1.線性表的基本運算：…..C2.線性表的順序存儲〔利用靜態(tài)數(shù)組或動態(tài)內存分配〕。相應的表示與操作A3.線性表的鏈式存儲。相應的表示與操作。包括循環(huán)鏈表、雙向鏈表。A4.順序存儲與鏈式存儲的比較：基于時間的考慮--分別適用于靜態(tài)的和動態(tài)的操作：比如靜態(tài)查找和插入刪除〕；基于空間的考慮--…….B這也適用于后面用兩種方式存儲的其他數(shù)據(jù)結構?！锉菊轮攸c：很熟悉順序表，單鏈表、雙鏈表，循環(huán)鏈表的基本操作；并學會在各種鏈表上進行一些算法設計〔與基本操作類似的操作或組合〕，請仔細復習。例4．假設有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結點存放歸并后的單鏈表。[題目分析]因為兩鏈表已按元素值遞增次序排列，將其合并時，均從第一個結點起進行比較，將小的鏈入鏈表中，同時后移鏈表工作指針。該問題要求結果鏈表按元素值遞減次序排列。故在合并的同時，將鏈表結點逆置。voidUnion(LinkListla,LinkListlb)

∥la,lb分別是帶頭結點的兩個單鏈表的頭指針，鏈表中的元素值按遞增序排列，本算法將兩鏈表合并成一個按元素值遞減次序排列的單鏈表。

{pa=la->ne*t;pb=lb->ne*t;∥pa，pb分別是鏈表la和lb的工作指針

la->ne*t=null;

∥la作結果鏈表的頭指針，先將結果鏈表初始化為空。

while(pa!=null&&pb!=null)∥當兩鏈表未訪問結束

if(pa->data<=pb->data)

{ q=pa->ne*t;

∥將pa的后繼結點暫存于q。

pa->ne*t=la->ne*t;

∥將pa結點鏈于結果表中，同時逆置。la->ne*t=pa;pa=q;

∥恢復pa為當前待比較結點。}

else{q=pb->ne*t;∥將pb的后繼結點暫存于q。pb->ne*t=la->ne*t;∥將pb結點鏈于結果表中，同時逆置。la->ne*t=pb;pb=q;∥恢復pb為當前待比較結點。}

while(pa!=null)∥將la表的剩余部分鏈入結果表，并逆置。

{q=pa->ne*t;pa->ne*t=la->ne*t;la->ne*t=pa;pa=q;}

while(pb!=null)

{q=pb->ne*t;pb->ne*t=la->ne*t;la->ne*t=pb;pb=q;}}∥算法Union結束。注意：〔1〕此處q用作暫存后繼結點，操作后pa或pb還回原指向位置；這與我們原來不改變pa或pb的指向，增加一個q=pa或pb作為摘取結點進行添加操作起到的作用一樣?！?〕此處要完成逆序插入操作故用頭插法〔基于頭指針la或lb〕，注意尾插法〔附設一個尾指針，基于該指針插入〕的可完成順序插入?！沧⒁猓耗嫘蛄硪环N方式也要掌握！〕練習：練習題2編程1——67.判斷帶頭結點雙向循環(huán)鏈表L是否對稱相等.8.設計一個算法判斷單鏈表〔帶頭結點〕是否是遞增的〔注意比排序算法應該簡單，鏈表排序也要會實現(xiàn)〕9.設計一個算法判斷有序表A是否是有序表B的子集〔即表A中的元素在B中〕?！菜伎迹喝绻f歸程序怎么寫？〕第三章：棧與隊列1.兩種特殊線性表：分別有后進先出、先進先出的特性。B2.棧的順序表示與實現(xiàn)〔利用靜態(tài)數(shù)組或動態(tài)內存分配〕A注意棧頂指針的初始位置不同，進出棧，?？諚M的實現(xiàn)語句有差別！舉例：假設定義typedefstruct{SElemType*base;SElemType*top;intstacksize;//當前棧能使用的最大容量}SqStack;SqStacks;top的初始值指向棧底，即top=base；棧空條件：s.top==s.base此時不能出棧棧滿條件：s.top-s.base>=s.stacksize進棧操作：*s.top++=e;或*s.top=e;s.top++;退棧操作：e=*--s.top；或s.top--；e=*s.top假設定義：typedefstruct{SElemTypebase[MA*SIZE];inttop;}SqStack;SqStacks;top的初始值為0時:?？諚l件：s.top==0此時不能出棧棧滿條件：s.top>=MA*SIZE進棧操作：s.base[s.top++]=e;退棧操作：e=s.base[--s.top]top的初始值為-1時:?？諚l件：s.top==-1此時不能出棧棧滿條件：s.top>=MA*SIZE-1進棧操作：s.base[++s.top]=e;退棧操作：e=s.base[s.top--]3.棧的鏈式表示與實現(xiàn)B(對比順序棧，實質不帶頭結點的鏈表在頭指針處插入和刪除)4.隊列的順序表示與實現(xiàn)—循環(huán)隊列A設兩個指針：Q.front指向隊列頭元素；Q.rear指向隊列尾元素的下一個位置注意隊中假設Q.rear指向隊列尾元素，進出隊，實現(xiàn)語句有差別！初始狀態(tài)〔空隊列〕：Q.front=Q.rear=0隊頭指針進1:Q.front=(Q.front+1)%MA*SIZE隊尾指針進1:Q.rear=(Q.rear+1)%MA*SIZE;隊列初始化：Q.front=Q.rear=0;隊空條件：Q.front==Q.rear;隊滿條件：(Q.rear+1)%MA*SIZE==Q.front隊列長度：(Q.rear-Q.front+MA*SIZE)%MA*SIZE6.隊列的鏈式表示與實現(xiàn)B本章重點：順序棧的初始條件、操作，循環(huán)隊列的初始條件、操作本章難點：棧的設計與使用，隊列的設計與使用〔主要結合后面樹和圖中的應用復習〕例5．鏈棧與順序棧比起來優(yōu)勢在于。沒有預設容量的限制例6．計算算術表達式的值時，可用兩個棧作輔助工具。對于給出的一個表達式，從左向右掃描它的字符，并將操作數(shù)放入棧S1中，運算符放入棧S2中，但每次掃描到運算符時，要把它同S2的棧頂運算符進行優(yōu)先級比較，當掃描到的運算符的優(yōu)先級不高于棧頂運算符的優(yōu)先級時，取出棧S1的棧頂和次棧頂?shù)膬蓚€元素，以及棧S2的棧頂運算符進行運算將結果放入棧S1中〔得到的結果依次用T1、T2等表示〕。為方便比較，假設棧S2的初始棧頂為?〔?運算符的優(yōu)先級低于加、減、乘、除中任何一種運算〕。現(xiàn)假設要計算表達式：A-B*C/D+E/F。寫出棧S1和S2的變化過程。步驟棧S1棧S2輸入的算術表達式〔按字符讀入〕初始

?A-B*C/D+E/F?1A?A-B*C/D+E/F?2A?--B*C/D+E/F?3AB?-B*C/D+E/F?4AB?-**C/D+E/F?5ABC?-*C/D+E/F?6AT1〔注：T1=B*C〕?-//D+E/F?7AT1D?-/D+E/F?8AT2〔注：T2=T1/D〕T3〔注：T3=A-T2〕?-?++E/F?9T3E?+E/F?10T3E?+//F?11T3EF?+/F?12T3T4〔注：T4=E/F〕T5〔注：T5=T3+T4〕?+??例7．將兩個棧存入數(shù)組V[1..m]應如何安排最好？這時?？?、棧滿的條件是什么？，入棧和出棧的操作是什么？分析：為了增加內存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的空間時，應將兩棧的棧底分別設在內存空間的兩端，這樣只有當兩棧頂指針相鄰〔即值之差的絕對值為1時才產(chǎn)生溢出。設棧S1和棧S2共享向量V[1..m]，初始時，棧S1的棧頂指針top0=0，棧S2的棧頂指針top1=m+1，當top0=0為棧S1空，top1=m+1為棧S2空；當top0=0并且top1=m+1時為兩棧全空。當top1-top0=1時為棧滿。入棧核心操作S1:V[++top0]=*1;S2:V[--top1]=*2出棧核心操作S1:*1=V[top0--];S2:*2=V[top1++]例8．如果用一個循環(huán)數(shù)組base[0..MA*-1]表示隊列時，該隊列只有一個隊列頭指針front，不設隊列尾指針rear，而改置計數(shù)器count用以記錄隊列中結點的個數(shù)。〔1〕編寫實現(xiàn)隊列的三個基本運算：判空、入隊、出隊〔2〕隊列中能容納元素的最多個數(shù)是多少typedefstruct{ElemTypebase[MA*];intfront,count;//front是指向隊頭元素針，count是隊列中元素個數(shù)。}CQueue;//定義類型標識符。(1)判空：intEmpty(CQueueq)//q是CQueue類型的變量{if(q.count==0)return(1)；elsereturn(0);//空隊列}入隊:intEnQueue(CQueueq，ElemType*){if(q.count==MA*){printf(〞隊滿\n〞)；e*it(0);}q.base[(q.front+q.count)%MA*]=*;//*入隊q.count++;return(1);//隊列中元素個數(shù)增加1,入隊成功。}出隊:intDelQueue(CQueueq,ElemType&*){if(q.count==0){printf(〞隊空\n〞)；return(0);}*=q.base[q.front];q.front=(q.front+1)%MA*;//計算新的隊頭指針q.count--;return(1);}(2)隊列中能容納的元素的個數(shù)為MA*。第四章：串1.串的基本概念C2.串的順序表示與實現(xiàn)〔兩種存儲方式〕A特別的模式匹配算法之KMP算法B本章重點：串的定長順序存儲和堆分配存儲、掌握一些常規(guī)的串操作〔自己會用和會編寫〕本章難點：串的模式匹配快速算法〔KMP〕例9.串的定長順序存儲缺點在于存在情況。截斷例10．已知u=‘*y*y*y**y*y’；t=‘**y’；ASSIGN〔s，u〕；ASSIGN〔v，SUBSTR〔s，INDE*〔s，t〕，LEN〔t〕+1〕〕；ASSIGN〔m，‘ww’〕求REPLACE〔ｓ，ｖ，m〕=________?！?y*y*ywwy’例11．14．設字符串S=‘a(chǎn)abaabaabaac'，P=‘a(chǎn)abaac'〔1〕給出S和P的ne*t值和ne*tval值；〔2〕假設S作主串，P作模式串，試給出利用BF算法和KMP算法的匹配過程。．〔1〕〔1〕p的ne*t與ne*tval值分別為012123和002003?！?〕利用BF算法的匹配過程：第一趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaacaa(i=3,j=2)第三趟匹配：aabaabaabaaca(i=3,j=1)第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac利用KMP算法的匹配過程：第一趟匹配：aabaabaabaacaabaac(i=6,j=6,ne*tval(j)=3)第二趟匹配：aabaabaabaac(aa)baac(i=9,j=6)第三趟匹配：aabaabaabaac(成功)(aa)baac(i=13,j=7)例12．一般串定位函數(shù)Inde*(S,T,pos),設S的串長為n，T的串長為m,那么最壞時間復雜度；而改進的Inde*_KMP(S,T,pos)時間復雜度為。第五章：數(shù)組和廣義表1.數(shù)組的存儲結構：以行為主序、以列為主序的地址映像函數(shù)B2矩陣的壓縮存儲：〔1〕特殊陣：包括對稱陣、三角陣、帶狀陣〔利用其特性壓縮存儲到一維數(shù)組〕B〔2〕稀疏陣利用的是三元組順序表來表示B用十字鏈表表示C〔本次考試不做要求〕3.廣義表定義與存儲表示B〔本次考試不做要求〕本章重點：地址映像函數(shù)的計算〔包括數(shù)組和特殊矩陣〕例13．已知n階下三角矩陣A〔即當i<j時，有aij=0〕，按照壓縮存儲的思想，可以將其主對角線以下所有元素(包括主對角線上元素)依次存放于一維數(shù)組B中，請寫出從第一列開始采用列序為主序分配方式時在B中確定元素aij的存放位置的公式。答：n階下三角矩陣元素A[i][j]〔1<=i,j<=n,i>=j〕。第1列有n個元素，第j列有n-j+1個元素，第1列到第j-1列是等腰梯形，元素數(shù)為(n+(n-j+2)(j-1)/2，而aij在第j列上的位置是為i-j+1。所以n階下三角矩陣A按列存儲，其元素aij在一維數(shù)組B中的存儲位置k與i和j的關系為：k=(n+(n-(j-1)+1)(j-1)/2+(i-j+1)=(2n-j)(j-1)/2+i第六章：二叉樹與樹1.二叉樹的定義和性質：B幾個特殊的二叉樹：滿二叉樹、完全二叉樹、二叉排序樹、平衡二叉樹B2.二叉樹的順序存儲：C3.二叉樹的鏈式存儲：用二叉鏈表表示與實現(xiàn)A4.二叉樹的遍歷：先〔中、后〕序遍歷及應用，相應遞歸算法和非遞歸算法A5.線索化二叉樹〔利用二叉鏈表n+1空指針域來存放某遍歷下指向該結點的直接前驅或直接后繼，使得蘊含更多信息〕B6.二叉樹的應用：算術表達式，霍夫曼樹〔最優(yōu)二叉樹〕，判定樹B7.樹的定義和存儲表示：…..B8.樹和森林和二叉樹的轉換B9.樹與森林的遍歷B★本章重點：很熟悉二叉樹〔在二叉鏈表表示下〕的基本操作的遞歸算法和遍歷的非遞歸算法，請仔細復習。本章難點：二叉樹〔含排序樹、平衡樹〕的遞歸算法和非遞歸算法。線索化二叉樹及相應操作，重在理解，不考編程！例14．引入二叉線索樹的目的是〔〕A．將非線性序列轉化成某種線性序列；加快查找結點的前驅或后繼的速度B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結果唯一A例15．二叉鏈表在線索化后，仍不能有效求解的問題是〔〕。A．前〔先〕序線索二叉樹中求前〔先〕序后繼B．中序線索二叉樹中求中序后繼C．中序線索二叉樹中求中序前驅D．后序線索二叉樹中求后序后繼D例16．在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A,并已知A的左孩子的平衡因子為-1右孩子的平衡因子為0,那么應作()型調整以使其平衡?！财胶庖蜃?左子樹深度-右子樹深度〕A.LL〔單向右旋〕B.LR〔先左后右雙向旋轉〕C.RL〔先右后左雙向旋轉〕D.RR〔單向左旋〕B例17．一棵非空的二叉樹其先序序列和后序序列正好相反，畫出這棵二叉樹的形狀。先序序列是〞根左右〞后序序列是〞左右根〞，可見對任意結點，假設至多只有左子女或至多只有右子女，均可使前序序列與后序序列相反，圖示如下：例18：已知二叉樹結點結構如下：用C語言表示typedefstructBiNode｛ElemTypedata;structBiNode*lchild,*rchild;intval;｝BiNode,*BiTree;其中val域表示該結點的子孫〔含孩子結點〕的個數(shù)。開始時，val域值均為0，T為指向某二叉樹根結點的指針。請寫算法填寫該二叉樹中每個結點的val域。遞歸算法如下：intwriteVal(BiNode*root){if(root==NULL)root->val=0;elseif(root->lchild==NULL&&root->rchild==NULL)root->val=1;elseroot->val=writeVal(root->lchild)+writeVal(root->rchild);returnroot->val;}例19．編寫一個算法，將指針S所指的結點插入到根結點指針為T的二叉排序樹中，假設已存在那么不再插入返回0；否那么返回1。〔遞歸的算法見教材〕intInsert_BST(BiTree&T,BiTNodeS){BiTreep,q;//p指向當前訪問的結點if(!T)T=S;else{p=T;while(p){q=p;//q指向p結點的雙親結點if(S->data.key<p->data.key)p=p->lchild;elseif(S->data.key>p->data.key)p=p->rchild; elsep=NULL;} if(S->data.key==q->data.key)return0;if(S->data.key<q->data.key)q->lchild=S;elseq->rchild=S; }return1;}例20．編寫一個算法，計算平衡二叉樹中所有結點的平衡因子解：計算一個結點＊bt的bf的值遞歸模型如下：f(bt):bt->bf不存在 當bt==NULLf(bt):bt->bf=0 當bt->lchild==NULL&&bt->rchild=NULLf(bt):bt->bf=bt的右子樹的高度－左子樹的高度其它情況可選用先序的方式統(tǒng)計出各個結點的平衡因子如何求高度呢？遞歸模型如下：f(bt):０不存在 當bt==NULLf(bt):１ 當bt->lchild==NULL&&bt->rchild=NULLf(bt):bt的左子樹和右子樹的高度的最大值＋１其它情況intHeight(BSTNode*bt){//求樹的高度 intma*1,ma*2; if(bt==NULL)return0; elseif(bt->lchild==NULL&&bt->rchild=NULL)return1; else{ ma*1=Height(bt->lchild); ma*2=Height(bt->rchild); returnma*1>ma*2?ma*1+1:ma*2+1; }}voidCountbf(BSTNode*&bt){//求所有結點的bf if(bt!=NULL){ if(bt->lchild==NULL&&bt->rchild=NULL){ bf->bf=0; } else{ Countbf(bt->lchild); Countbf(bt->rchild); bt->bf=Height(bt->rchild)-Height(bt->lchild); } }}實質上可以將上面求bf和求高度合二為一。intCountbf1(BSTNode*&bt){//求所有結點的bf,返回對應結點高度值 intma*1,ma*2; if(bt==NULL)return0; if(bt->lchild==NULL&&bt->rchild=NULL){ bf->bf=0; return1; } else{ ma*1=Height(bt->lchild); ma*2=Height(bt->rchild); bt->bf=ma*2-ma*1; returnma*1>ma*2?ma*1+1:ma*2+1; }}例21．設給出一段報文：CASTCASTSATATATASA；字符集合是{C,A,S,T}，各個字符出現(xiàn)的頻度(次數(shù))是W＝{2,7,4,5}；試設計赫夫曼編碼，畫出赫夫曼樹。假設給每個字符以等長編碼A:00T:10C:01S:11；試說明赫夫曼編碼比此方案的優(yōu)越之處。(編碼最短) 解答見ppt練習1．設計一個算法，刪除該二叉樹，釋放所有結點2．設計一算法判斷二叉鏈表存儲的二叉樹是否結構對稱〔左右子樹結點結構對稱相同〕3．試寫出復制一棵二叉樹的算法。二叉樹采用標準鏈接結構。4．習題六編程〔除打星號的部分〕5.設計一個算法，尋找二叉樹中滿足特定數(shù)值*的第一個結點(相應的變形：尋找最小值，尋找父結點，尋找兄弟)6.設計一個算法，統(tǒng)計二叉樹中滿足特定數(shù)值*結點的個數(shù)〔相應的變形：統(tǒng)計度為0，1，2的結點〕第七章圖1.圖的定義、基本概念：B2.圖的存儲方式：鄰接矩陣和鄰接表A3.圖的遍歷深度優(yōu)先和廣度優(yōu)先A4.圖的連通性和生成樹B帶權圖的最小生成樹及算法B5.圖的最短路徑問題B6.拓撲排序、AOE網(wǎng)中的關鍵路徑B本章重點：熟悉鄰接矩陣和鄰接表的表示方法，學會編寫遍歷算法深度優(yōu)先和廣度優(yōu)先遍歷算法以及一些遍歷算法的應用。請仔細復習。本章難點：圖的一些算法〔如最小生成樹、最短路徑、關鍵路徑；這部分重在理解算法思想和設計過程〕例22．將鄰接矩陣g裝換為鄰接表G(鄰接表的表示方法) voidMatToList(MGraghg,ALGLink&G){ inti,j,N=g.n;//N表示頂點數(shù) ArcNode*p; G=(ALGraph*)malloc(sizeof(ALGraph)); for(i=0;i<N;i++){//給鄰接表中所有頂點的賦值并使其指針域置空 G->vertices[i].data=g.ve*s[i]; G->vertices[i].firstedge=NULL; } for(i=0;i<N;i++)/*對鄰接陣掃描每一行的每一列*/ for(j=N-1;j>=0;j--)//對第i個頂點進行建立鏈表〔由后向前添加〕 if(g.edges[i][j]!=0){ p=(ArcNode*)malloc(sizeof(ArcNode));//新建結點 p->adjve*=j; p->info=g.edges[i][j];//存放邊的權值 p->ne*t=G->vertices[i].firstedge;//前插 G->vertices[i].firstedge=p; } G->n=N;G->e=g.e; }例23．試利用深度優(yōu)先遍歷DFS判斷該圖〔在鄰接表存儲下〕是否是連通的，假設是連通的返回１，假設是不連通的返回圖的連通分量個數(shù)，空圖那么返回０。(圖的遍歷)intvisted[MA*NUM];//全局數(shù)組voidDFS(ALGraph*G,inti){/*以Vi為出發(fā)點對鄰接表圖進行DFS*/ ArcNode*p; printf("visitdata:%d\n",G->vertices[i].data);//訪問頂點Vi visited[i]=1;//標記Vi已訪問，標志為１ p=G->vertices[i].firstarc;//取Vi邊表的頭指針while(p){//依次搜索Vi的鄰接點Vj， if(!visited[p->adjve*])//假設Vj尚未訪問，那么以Vj為出發(fā)點向縱深搜索 DFS(G,p->adjve*); p=p->ne*t;}}/*判斷無向圖是否連通，假設連通返回1*/intConnects(ALGraph*G){inti,flag=1;//flag為標記是否連通for(i=0;i<G->ve*num;i++) visited[i]=0;//標志向量visted[]初始化，標志為０ DFS(g,0);for(i=0;i<G->ve*num;i++) if(visited[i]==0){//還有vi未訪問過，修改標記flag量 flag=0;break; } returnflag;}例24．下面是求連通網(wǎng)的最小生成樹的prim算法：集合VT，ET分別放頂點和邊，初始為〔1〕，下面步驟重復n-1次:a：〔2〕；b：〔3〕；最后：〔4〕?！?〕．A．VT，ET為空B．VT為所有頂點，ET為空C．VT為網(wǎng)中任意一點，ET為空D．VT為空，ET為網(wǎng)中所有邊〔2〕．A.選i屬于VT，j不屬于VT，且〔i，j〕上的權最小B．選i屬于VT，j不屬于VT，且〔i，j〕上的權最大C．選i不屬于VT，j不屬于VT，且〔i，j〕上的權最小D．選i不屬于VT，j不屬于VT，且〔i，j〕上的權最大〔3〕．A．頂點i加入VT，〔i,j〕加入ETB.頂點j加入VT，〔i,j〕加入ETC.頂點j加入VT，〔i,j〕從ET中刪去D．頂點i,j加入VT，〔i,j〕加入ET〔4〕．A．ET中為最小生成樹B．不在ET中的邊構成最小生成樹C．ET中有n-1條邊時為生成樹，否那么無解D．ET中無回路時，為生成樹，否那么無解CABA例25．P182算法7.12〔思考：用鄰接矩陣存儲怎么實現(xiàn)？〕練習1.假設有向圖以鄰接表存儲，計算Vi頂點的出度和入度。2.在有向無環(huán)圖中，試利用深度優(yōu)先遍歷DFS求出一個拓撲排序序列。提示：由某點出發(fā)進行深度優(yōu)先遍歷，退出DFS函數(shù)調用時記錄此時頂點序號，最先退出DFS函數(shù)的頂點是拓撲序列中的最后一個頂點，依次下去…..得到一個逆向拓撲有序序列；再將此頂點序號反向輸出即可。3.設計一個深度優(yōu)先搜索算法，以判斷用鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj〔i≠j〕的路徑。第八章查找基本概念C靜態(tài)查找表中常用的方法：順序查找、折半查找、分塊查找〔分別適用于一般、有序、分塊有序的表〕相應算法和性能分析A動態(tài)查找表：二叉排序樹的建立、查找、刪除；A二叉平衡樹Ｂ哈希表：哈希函數(shù)的構造和沖突處理方法Ｂ本章重點：查找樹的建立和查找〔含靜態(tài)折半查找、動態(tài)查找樹〕、哈希函數(shù)和沖突方法本章難點：二叉排序樹刪除；平衡排序樹的插入例26．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標依次為________。6,9,11,12例27．設散列表為HT[0..12],即表的大小為m=13?，F(xiàn)采用雙散列法解決沖突。散列函數(shù)