數(shù)據(jù)結(jié)構(gòu)知識點(diǎn)歸納

、數(shù)據(jù)結(jié)構(gòu)的章節(jié)結(jié)構(gòu)及重點(diǎn)構(gòu)成數(shù)據(jù)結(jié)構(gòu)學(xué)科的章節(jié)劃分基本上為:概論，線性表，棧和隊(duì)列，串，多維數(shù)組和廣義表，樹和二叉樹，圖，查找，內(nèi)排，外排，文件，動態(tài)存儲分配。對于絕大多數(shù)的學(xué)校而言，''外排，文件，動態(tài)存儲分配〃三章基本上是不考的，在大多數(shù)高校的計(jì)算機(jī)本科教學(xué)過程中，這三章也是基本上不作講授的。數(shù)據(jù)結(jié)構(gòu)的章節(jié)比重大致為：概論：概念，時間復(fù)雜度。線性表:基礎(chǔ)章節(jié)，必考內(nèi)容之一。概念，算法設(shè)計(jì)題。棧和隊(duì)列:基本概念。串：基本概念。多維數(shù)組及廣義表：基本概念。樹和二叉樹：重點(diǎn)難點(diǎn)章節(jié)，各校必考章節(jié)。概念，問答，算法設(shè)計(jì)題。圖:重點(diǎn)難點(diǎn)章節(jié)，各校必考章節(jié)。概念，問答，算法設(shè)計(jì)題。查找：重點(diǎn)難點(diǎn)章節(jié)，概念，問答。排序：重點(diǎn)難點(diǎn)章節(jié)，問答各種排序算法的排序過程二、各章節(jié)的主要內(nèi)容：第一章概述主要內(nèi)容：本章主要起到總領(lǐng)作用，為讀者進(jìn)行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)進(jìn)行了一些先期鋪墊。大家主要注意以下幾點(diǎn)（1） 數(shù)據(jù)結(jié)構(gòu)的基本概念。（數(shù)據(jù)；數(shù)據(jù)元素；數(shù)據(jù)項(xiàng)；數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)的邏輯結(jié)構(gòu)：線性和非線性，具體分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)；數(shù)據(jù)的存儲結(jié)構(gòu)：順序存儲和鏈?zhǔn)酱鎯?；運(yùn)算）（2） 算法的度量：時間效率和空間效率，分別用時間復(fù)雜度和空間復(fù)雜度度量，掌握時間復(fù)雜度的度量方法量方法。（大O表示法）參考題目填空題：1、 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容，分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、（）和（ ）。2、 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是（）和（）3、 數(shù)據(jù)的物理結(jié)構(gòu)主要包括（ ）和（ ）兩種情況。4、線性表，棧，隊(duì)列和二叉樹四種數(shù)據(jù)結(jié)構(gòu)中（ ）是非線性結(jié)構(gòu)，（ ）是線性結(jié)構(gòu)。5、線性結(jié)構(gòu)中元素之間存在（ ）關(guān)系，樹形結(jié)構(gòu)中元素之間存在（）關(guān)系，圖形結(jié)構(gòu)中元素之間存在（ ）關(guān)系。6、程序段的時間復(fù)雜度是。for（i=1;i<=n;i++）{k++;for(j=1;j<=n;j++)x=x+k;}下列算法的時間復(fù)雜度是。for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i；下列算法的時間復(fù)雜度是i=s=0;while(s<n){i++;s+=i;}判斷題：TOC\o"1-5"\h\z1、 在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。（ ）2、順序存儲方式優(yōu)點(diǎn)是存儲密度大，且插入和刪除運(yùn)算效率高。 （）3、線性表的鏈接存儲，表中元素的邏輯順序與物理順序一定相同。 （）第二章線性表主要內(nèi)容：作為線性結(jié)構(gòu)的開篇章節(jié)，線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中，其作用都是不可低估的。在這一章，第一次系統(tǒng)性地引入鏈?zhǔn)酱鎯Φ母拍?，鏈?zhǔn)酱鎯Ω拍顚⑹钦麄€數(shù)據(jù)結(jié)構(gòu)學(xué)科的重中之重，無論哪一章都涉及到了這個概念。線性表一章注意以下幾個方面：（1） .線性表的相關(guān)基本概念，如:前驅(qū)、后繼、表長、空表、首元結(jié)點(diǎn)，頭結(jié)點(diǎn)，頭指針等概念。（2） 線性表的結(jié)構(gòu)特點(diǎn)，主要是指:除第一及最后一個元素外，每個結(jié)點(diǎn)都只有一個前趨和只有一個后繼。（3） 線性表的順序存儲方式及基本運(yùn)算（插入、刪除操作、平均移動次數(shù)、時間復(fù)雜度）。（4） 線性表的鏈?zhǔn)酱鎯Ψ绞郊盎具\(yùn)算（單鏈表插入、刪除，求長度操作平均移動次數(shù)、時間復(fù)雜度）。（5） 順序存儲和鏈?zhǔn)酱鎯Φ奶攸c(diǎn)，不同之處。（6） 線性表的簡單算法題參考題目一、選擇題：1、線性表是（ ）一個有限序列，可以為空B.一個有限序列，不能為空C.一個無限序列，可以為空 D.一個無限序列，不能為空2、 在表長為n的順序表上做插入運(yùn)算，平均要移動的結(jié)點(diǎn)數(shù)為（）。n B.n/2C.n/3 D.n/43、 鏈表不具有的特點(diǎn)是（）。A.隨機(jī)訪問 B.不必事先估計(jì)存儲空間C-插入刪除時不需移動元素 D.所需的空間與線性表成正比4、 帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（ ）A.head=NULL； B.head->next=NULL； C.head->next=head；D.head!=NULL；5、在一個單鏈表中，若P所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在P之后插入S所指結(jié)點(diǎn)，則執(zhí)行（ ）A.S->next=P->next;P->next=S B.P->next=S->next;S->next=P；C.P->next=P;P->next=S； D.P->next=S;S->next=P；6、在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點(diǎn)，其算法所需的時間復(fù)雜度為()A.O(l) B.O(log2n) C.O(n) D.O(n2)7、 在一個單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前趨，若在p，q之間插入，結(jié)點(diǎn)，則執(zhí)行的操作是()。A.s—〉next=p—〉next;p—〉next=s; B.q->next=s;s->next=p;C.p—〉next=s—〉next;s—〉next=p; D.p—〉next=s;s—〉next=q;8、設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中( )個數(shù)據(jù)元素，TOC\o"1-5"\h\z刪除第i個元素(lWiWn)時，需向前移動的元素的個數(shù)是()。在順序表中插入一個元素，需要平均移動( )元素，刪除一個元素，需要平均移動( )元素，具體移動的元素個數(shù)與( )有關(guān)，插入\刪除操作的時間復(fù)雜度均為( )。9、 設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn),若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語句：( )。10.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A的前驅(qū)結(jié)點(diǎn)，若刪除單鏈表中結(jié)點(diǎn)A，則執(zhí)行操作()三、算法設(shè)計(jì)：設(shè)計(jì)算法，計(jì)算順序表中數(shù)據(jù)元素為x的元素個數(shù)。順序表結(jié)構(gòu)如下：typedefstruct{intdata[100];intlength;}sqlist;函數(shù)首部為：intcount(sqlistL,intx)2.設(shè)計(jì)算法，在順序線性表中，刪除順序表中第i個元素，順序表結(jié)構(gòu)同上題。函數(shù)首部為：intdel(sqlist*L,inti)2.設(shè)計(jì)算法，在順序線性表中，刪除值為x的元素。函數(shù)首部為：voiddelx(sqlist*L,intx)對給定的單鏈表L(元素各不相同)，編寫一個刪除L中值為x的結(jié)點(diǎn)的算法。鏈?zhǔn)浇Y(jié)構(gòu)如下：typedefstructLinkList{intdata;structLinkList*next;}Node,*LinkList;intdelx(LinkList*head,intx)編寫算法求帶頭結(jié)點(diǎn)的單鏈表的表長,結(jié)構(gòu)同上題。intcount(LinkList*head)第三章棧與隊(duì)列主要內(nèi)容：棧與隊(duì)列，是很多學(xué)習(xí)DS的同學(xué)遇到第一只攔路虎，很多人從這一章開始坐暈車，一直暈到現(xiàn)在。棧和隊(duì)列一章注意以下幾個方面：（1） 棧的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念：合法的出棧序列、出棧序列個數(shù)、順序棧，鏈棧（2） 隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括:循環(huán)隊(duì)列。（3） 棧和隊(duì)列的特點(diǎn)：棧---后進(jìn)先出；隊(duì)列一先進(jìn)先出。（4） 遞歸算法概念。棧與遞歸的關(guān)系，所有的遞歸算法都可以借助棧將遞歸轉(zhuǎn)向于非遞歸算法。（5） 操作：順序棧的進(jìn)棧、出棧操作。循環(huán)隊(duì)列的隊(duì)空、隊(duì)滿條件，出隊(duì)、入隊(duì)、求隊(duì)列元素個數(shù)操作。參考題目循環(huán)隊(duì)列是空隊(duì)列的條件是（）A.Q.rear==Q.frontB.（Q.rear+1）%maxsize==Q.frontC.Q.rear==0D.Q.front==0鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是（ ）A.通常不會出現(xiàn)棧滿的情況 B.通常不會出現(xiàn)?？盏那闆rC-插入操作更加方便 D.刪除操作更加方便若一個棧的輸入序列是1,2,3,……，n，輸出序列的第一個元素是n，則第i個輸出元素是（ ）A.n-iB.n-i+1C.i D.不確定對于一個棧，給定輸入序列為1，2,3,則下列不可能為輸出序列的是（）A.1，2，3 B.3，2，1 C.3，1，2 D.2，1，3棧是限定在（）處進(jìn)行插入或刪除操作的線性表。A.端點(diǎn) B.棧底 C?棧頂 D.中間當(dāng)循環(huán)隊(duì)列q是滿隊(duì)列時，存放隊(duì)列元素的數(shù)組data有n個元素，則data中存放（ ）個數(shù)據(jù)元素。A.n B.n-1 C.n-2 D.0循環(huán)隊(duì)列用數(shù)組elem[0,m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個數(shù)是。棧的特點(diǎn)是 ，隊(duì)列的特點(diǎn)是。設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧，一個元素出棧后立即進(jìn)入隊(duì)列Q，若6個元素出隊(duì)的順序是e2,e4,e3,e6,e5,e1,則棧S的容量至少應(yīng)該。若用一個大小為6的一維數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，當(dāng)前rear和front的值分別是0和3,從隊(duì)列中刪除一個元素，再加入兩個元素后，當(dāng)前隊(duì)列中共 個元素，rear的值為，front的值為。第四章串主要內(nèi)容：最容易自學(xué)的章節(jié)之一本章注意：（1） 串的基本概念：串（串是其元素均為字符型數(shù)據(jù)的特殊線性表），子串、空串與空格串的區(qū)別，串相等的條件、模式匹配。（2） 串的定長順序存儲（3） 串的基本操作功能，如求串長,串連接，串替換等，給出一個字符串能夠?qū)懗霾僮鞯慕Y(jié)果。參考題目串是一種特殊的線性表，其特殊性體現(xiàn)在( )。S1=“ABCD”，S2=“CD”則S2在S1中的位置是( )假設(shè)S="abcaabcaaabca”，T="bca”，Index(S,T,3)的結(jié)果是(6)設(shè)有S1=‘ABCDEFG’，S2=‘PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(S,i,j)返回串S的從序號i的字符開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的結(jié)果是。在串中，SubString(“student”，5,2)的結(jié)果是 。假設(shè)S="abcaabcaaabca"，T="bca"，V="x"，Replace(S,T,V結(jié)果是。兩個串相等的充分必要條件是且。子串的定位操作通常稱為 。第五章數(shù)組與廣義表主要內(nèi)容：多維數(shù)組中某數(shù)組元素的存儲位置求解。一般是給出數(shù)組元素的首元素地址和每個元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個元素所在的位置。明確按行存儲和按列存儲的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲方式求解1中類型的題。稀疏矩陣的壓縮存儲概念，三元組表和十字鏈表存儲。廣義表的概念，理解廣義表的遞歸特性，特別應(yīng)該明確表頭與表尾的定義。廣義表的存儲特性---難以用順序存儲結(jié)構(gòu)存儲。能畫出頭尾表示法廣義表的操作GetHead和GetTail，給出一個廣義表能夠?qū)懗鋈”眍^和取表尾操作的結(jié)果。參考題目TOC\o"1-5"\h\z常對數(shù)組進(jìn)行的兩種基本操作是( )。A.建立與刪除B.索引和修改C.對數(shù)據(jù)元素的存取和修改 D.查找與索引二維數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，數(shù)組元素A[7]⑷的起始地址為( )。A.SA+141B.SA+144C.SA+222D.SA+225對稀疏矩陣進(jìn)行壓縮存儲目的是 。已知廣義表：A=(a,b),B=(A,A),C=(a,(b,A),B)，貝Utail(head(tail(C)))運(yùn)算的結(jié)果為。求下列廣義表操作的結(jié)果：GetTail[GetHead[((a,b),(c,d))]]=GetTail[GetHead[GetTail[((a,b),(c,d))]]]=第六章樹與二叉樹主要內(nèi)容：從對線性結(jié)構(gòu)的研究過度到對樹形結(jié)構(gòu)的研究，是數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的一次躍變，此次躍變完成的好壞，將直接關(guān)系到你到實(shí)際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專業(yè)課總分。所以，樹這一章的重要性，已經(jīng)不說自明了?？傮w來說，樹一章的知識點(diǎn)包括：二叉樹的概念、性質(zhì)(性質(zhì)非常重要)二叉樹的存儲結(jié)構(gòu)(順序存儲和二叉鏈表存儲)（3） 二叉樹遍歷的三種算法（①給二叉樹能寫出遍歷序列，根據(jù)遍歷序列可以構(gòu)造二叉樹；②遍歷遞歸算法（二叉樹的其他算法很多都是在遍歷的基礎(chǔ)上得到的）、在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹的其它算法（如求葉子結(jié)點(diǎn)、總結(jié)點(diǎn)、高度等，仔細(xì)揣摩求解思路）（4） 線索二叉樹的概念。（利用二叉鏈表存儲時的空鏈域指向前驅(qū)和后繼，空鏈域個數(shù)；給出一棵二叉樹能畫出對應(yīng)的線索二叉樹，如P149—圖6.16）（5）樹、森林的概念，樹與森林的遍歷算法（給出樹或森林，能寫出其要求的遍歷序列）樹和森林的遍歷算法與二叉樹遍歷算法的聯(lián)系。（6） 樹與森林和二叉樹的相互轉(zhuǎn)換。（7）最優(yōu)二叉樹的概念，哈夫曼樹的概念，特點(diǎn)（只有0和2的結(jié)點(diǎn)），能夠按指定權(quán)值建立哈夫曼樹，給出哈夫曼編碼，計(jì)算WPL。樹一章，處處是重點(diǎn)，道道是考題，大家務(wù)必個個過關(guān)。參考題目1、 在具有n個結(jié)點(diǎn)的完全二叉樹中，結(jié)點(diǎn)i（i>1）的父結(jié)點(diǎn)是（ ）A.2i B.不存在C.2i+1 D.Li/2J2、下列陳述中正確的（ ）二叉樹是度為2的有序樹二叉樹中結(jié)點(diǎn)只有一個孩子時無左右之分二叉樹中必有度為2的結(jié)點(diǎn)二叉樹中最多只有兩棵子樹，并且有左右之分TOC\o"1-5"\h\z3、 以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，在具有n個結(jié)點(diǎn)的二叉鏈表中（n>0），空鏈域的個數(shù)為（ ）A.2n-1 B.n-1C.n+1 D.2n+14、 將一棵有100個結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為1，則編號為49的結(jié)點(diǎn)的左孩子編號為（ ）A.99 B.98 C.50 D.485、 在一棵具有五層的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（ ）A.31 B.32 C.33 D.166、深度為k的完全二叉樹中最少有（）個結(jié)點(diǎn)。A.2k-1-1 B.2k-1 C.2k-1+1 D.2k-17、三個結(jié)點(diǎn)可以構(gòu)成（ ）種不同形狀的二叉樹。A.1 B.2 C.3 D.58、 樹中所有結(jié)點(diǎn)的度之和等于所有結(jié)點(diǎn)數(shù)加（ ）。A.0 B.1 C.-1 D.29、含有10個結(jié)點(diǎn)的二叉樹中，度為0的結(jié)點(diǎn)數(shù)為4,則度為2的結(jié)點(diǎn)數(shù)為（），度為1的結(jié)點(diǎn)數(shù)為（）A.3 B.4 C.5 D.610、 有m個葉結(jié)點(diǎn)的哈夫曼樹所具有的結(jié)點(diǎn)數(shù)為（ ）A.mB.m+1C.2mD.2m-1填空：若某二叉樹有20個葉子節(jié)點(diǎn)，有30個節(jié)點(diǎn)僅有一個孩子，則該二叉樹的總的節(jié)點(diǎn)數(shù)。設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹中總共有個結(jié)點(diǎn)。若前序遍歷二叉樹的結(jié)果為序列A、B、C，則有棵不同的二叉樹可以得到這一結(jié)果。線索二叉樹的左線索指向其，右線索指向其 。已知完全二叉樹T的第5層只有7個結(jié)點(diǎn)，則該樹共有個葉子結(jié)點(diǎn)。簡答：已知一棵二叉樹的先序遍歷序列EFHIGJK，中序遍歷序列為HFIEJGK，構(gòu)造該二叉樹，寫出后序序列。已知一棵二叉樹的前序序列為ABCDEFGH，中序序列為CBEDFAGH，請畫出該二叉樹，寫出后序序列。已知一棵二叉樹的后序序列“cdbgfea”,中序序列“cbdaegf”，請畫出該二叉樹，寫出先序序列。根據(jù)后序序列“cedbhjigfa”和中序序列“cbedahgijf”構(gòu)建二叉樹，并給出其先序序列。假設(shè)用于通信的電文字符集為{ABCDE},各字母出現(xiàn)次數(shù)分別為{29576}，現(xiàn)需求這些字母的最優(yōu)編碼，計(jì)算huffman樹的帶權(quán)路徑長度。假設(shè)用于通信的電文由8個字母a,b,c,d,e,f,g組成，其頻率分別為W={5,2,9,11,8,3,7}，試構(gòu)造相應(yīng)的哈夫曼樹，給出每個字母的haffman編碼，并計(jì)算它的帶權(quán)路徑長度。三、算法設(shè)計(jì)：編寫算法求二叉樹中葉子結(jié)點(diǎn)的數(shù)目。數(shù)據(jù)結(jié)構(gòu)定義為：typedefstructNode{intdata;structNode*Lchild;structNode*Rchild;}BiTNode,*BiTree;函數(shù)首部為：intleaf（BiTree*root）利用二叉樹遍歷算法求二叉樹的高度，假設(shè)根結(jié)點(diǎn)的高度為1.intDepth（BiTree*root）以二叉鏈表為存儲結(jié)構(gòu)寫出求二叉樹結(jié)點(diǎn)總數(shù)的算法。第六章圖主要內(nèi)容：如果說，從線性結(jié)構(gòu)向樹形結(jié)構(gòu)研究的轉(zhuǎn)變，是數(shù)據(jù)結(jié)構(gòu)學(xué)科對數(shù)據(jù)組織形式研究的一次升華，那么從樹形結(jié)構(gòu)的研究轉(zhuǎn)到圖形結(jié)構(gòu)的研究，則進(jìn)一步讓我們看到了數(shù)據(jù)結(jié)構(gòu)對于解決實(shí)際問題的重大推動作用。圖這一章的特點(diǎn)是:概念繁多，與離散數(shù)學(xué)中圖的概念聯(lián)系緊密，算法復(fù)雜，考研時極易被考到，且容易出大題，如果不考查樹與圖兩章的知識，幾乎是不可想像的。主要知識點(diǎn)如下：（1） 圖的基本概念：圖的定義和特點(diǎn)，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，回路，（強(qiáng)）連通圖，（強(qiáng)）連通分量、生成樹等概念。與這些概念相聯(lián)系的相關(guān)計(jì)算題也應(yīng)該掌握（如：有向（無向）完全圖邊的條數(shù)、生成樹的邊的條數(shù)等）。（2） 圖的存儲形式：只看鄰接矩陣和（逆）鄰接表（3） 圖的兩種遍歷算法:深度遍歷和廣度遍歷，能夠畫出任意一幅圖的深度優(yōu)先搜索生成樹和廣度優(yōu)先搜索生成樹。（4） 生成樹、最小生成樹的概念以及最小生成樹的構(gòu)造RIM算法和KRUSKAL算法?？疾闀r，一般不要求寫出算法源碼，而是要求根據(jù)Prim算法、Kruskal算法構(gòu)造該圖的最小生成樹，畫出其構(gòu)造過程及最終生成的最小生成樹。以下內(nèi)容考研很重要（5） 拓?fù)渑判騿栴}：拓?fù)渑判蛴袃煞N方法，一是無前趨的頂點(diǎn)優(yōu)先算法，二是無后繼的頂點(diǎn)優(yōu)先算法。換句話說，一種是“從前向后”的排序，一種是“從后向前”排。當(dāng)然，后一種排序出來的結(jié)果是“逆拓?fù)溆行颉钡?。要求按指定圖，寫出拓?fù)渑判蛐蛄?。?） 關(guān)鍵路徑問題：這個問題是圖一章的難點(diǎn)問題。理解關(guān)鍵路徑的關(guān)鍵有三個方面:一是何謂關(guān)鍵路徑，二是最早時間是什么意思、如何求，三是最晚時間是什么意思、如何求。關(guān)鍵路徑問題是工程進(jìn)度控制的重要方法，具有很強(qiáng)的實(shí)用性。要求對指定圖，寫出關(guān)鍵路徑。（7）最短路徑問題：與關(guān)鍵路徑問題并稱為圖一章的兩只攔路虎。概念理解是比較容易的，關(guān)鍵是算法的理解。最短路徑問題分為兩種:一是求從某一點(diǎn)出發(fā)到其余各點(diǎn)的最短路徑；二是求圖中每一對頂點(diǎn)之間的最短路徑。這個問題也具有非常實(shí)用的背景特色，一個典型的應(yīng)該就是旅游景點(diǎn)及旅游路線的選擇問題。解決第一個問題用DIJSKTRA算法，解決第二個問題用FLOYD算法。注意區(qū)分。參考題目1、 在一個具有n個結(jié)點(diǎn)的無向圖中，要連通全部結(jié)點(diǎn)至少需要（ ）A.n條邊 B.n+1條邊C.n-1條邊 D.n/2條邊2、 最小生成樹指的是（）由連通圖所得到的邊數(shù)最少的生成樹由連通圖所得到的頂點(diǎn)相對較少的生成樹連通圖的所有生成樹中權(quán)值之和最小的生成樹連通圖的極小連通子圖3、 在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）A.1/2倍B.1倍C.2倍 D.4倍4、有n個結(jié)點(diǎn)的無向圖的邊數(shù)最多為（ ）A.n+1B.n（n-1）/2C.n（n+1） D.2n（n+1）5、 若n個頂點(diǎn)的無向圖采用鄰接矩陣存儲方法，該鄰接矩陣是一個（ ）A.一般矩陣B.對稱矩陣 C.對角矩陣 D.稀疏矩陣6、 下列算法中，算法用來求圖中每對頂點(diǎn)之間的最短路徑。A.DijkstraB.FloyedC.Prim D.Kruskal7、 最小生成樹的構(gòu)造可使用（A）。A.prim算法 B.冒泡算法C.迪杰斯特拉算法 D.哈夫曼算法8、 有8個結(jié)點(diǎn)的有向完全圖有（C）條邊。A.14 B.28 C.56 D.1129、 已知有向圖G=（V,E）,其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓?fù)湫蛄惺牵?）。A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7CVVVVVVV DVVVVVVV.▼i^vo, , , , , . ,'c,,,,,r1345267 125346/i V_z i V_z 10、 設(shè)無向圖G中的邊的集合E={（a，b），（a，e），（a，c），（b，e），（e，d），（d，f），（f，c）}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為。11、有N個頂點(diǎn)組成的無向連通圖，最多可以有 條邊。簡答題：給出下圖中從a出發(fā)的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列

求下圖的最小生成樹，要求分別用prim算法和kruskal算法，prim算法從定點(diǎn)1出發(fā)。畫出最小生成樹的生成過程。求下圖的最小生成樹，要求分別用prim算法和kruskal算法，prim算法從定點(diǎn)a出發(fā)。畫出最小生成樹的生成過程。已知圖G如下所示，列出圖G的鄰接表，寫出拓?fù)渑判蛐蛄校▽懗鲆环N即可），求出關(guān)鍵路徑。已知圖G如下所示，列出圖G的鄰接表，寫出拓?fù)渑判蛐蛄校▽懗鲆环N即可），求出關(guān)鍵路徑。第七章查找主要內(nèi)容:在不少數(shù)據(jù)結(jié)構(gòu)的教材中，是把查找與排序放入高級數(shù)據(jù)結(jié)構(gòu)中的。應(yīng)該說，查找和排序兩章是前面我們所學(xué)的知識的綜合運(yùn)用，用到了樹、也用到了鏈表等知識，對這些數(shù)據(jù)結(jié)構(gòu)某一方面的運(yùn)用就構(gòu)成了查找和排序?，F(xiàn)實(shí)生活中，search幾乎無處不在，特別是現(xiàn)在的網(wǎng)絡(luò)時代，萬事離不開search，小到文檔內(nèi)文字的搜索，大到INTERNET上的搜索，search占據(jù)了我們上網(wǎng)的大部分時間。在DS的教材中，一般將search分為三類:1在順序表上的查找；2在樹表上的查找；3在哈希表上的查找。本次復(fù)習(xí)這一章的知識時，要掌握以下內(nèi)容：（1） 關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字的含義；靜態(tài)查找與動態(tài)查找的含義及區(qū)別；（2） 線性表上的查找：順序查找和二分查找及其比較次數(shù)。（3） 基本哈希表的查找算法：參考題目TOC\o"1-5"\h\z1、順序查找法適合于存儲結(jié)構(gòu)為 的線性表。（ ）A.散列存儲 B.順序存儲或鏈接存儲C.壓縮存儲 D.索引存儲2、 在查找過程中，若同時還要做增、刪工作，這種查找則稱為（ ）A.靜態(tài)查找 B.動態(tài)查找 C.內(nèi)查找D.外查找3、 對線性表進(jìn)行二分查找時，要求線性表必須（ ）A.以順序方式存儲 B.以順序方式存儲且兀素有序C.以鏈接方式存儲 D.以鏈接方式存儲且元素有序4、在有序表（12,24,36,48,60,72,84沖二分查找關(guān)鍵字72時所需進(jìn)行的關(guān)鍵字比較次數(shù)為 。5、 折半查找有序表（4,6,12,20,28,38,50,70,88,100），若查找表中元素20，它將依次與表中元素 比較大小。簡答題：1、已知散列函數(shù)為H（k）=kmod13，關(guān)鍵值序列為（19，01，23，14，55，20，84，27，68，11，10，77）處理沖突的方法為線性探測法，散列表長度為13（1） 構(gòu)造哈希表（畫示意圖）；（2） 計(jì)算裝填因子；（3） 計(jì)算查找成功情況下的平均查找長度；2.采用哈希函數(shù)H（k）=3*kmod13并用線性探測開放地址法處理沖突，在數(shù)列地址空間［0..12］中對關(guān)鍵字序列22,15,40,46,17,13,14,28,38（1） 構(gòu)造哈希表（畫示意圖）；（2） 裝填因子；（3） 等概率下成功的平均查找長度3.已知散列函數(shù)為H（k）