《數(shù)據(jù)結(jié)構(gòu)》考前復(fù)習(xí)大綱

1、數(shù)據(jù)結(jié)構(gòu)考前復(fù)習(xí)大綱本復(fù)習(xí)大綱按章分別敘述三方面的內(nèi)容：1、考試大綱要求， 2、復(fù)習(xí)考試知識(shí)點(diǎn)，3、應(yīng)用舉例。為了方便考生復(fù)習(xí)，知識(shí)點(diǎn)還給出較詳細(xì)的描述內(nèi)容，舉例題型也給出具體的分析過(guò)程和完整的參考答案。第一章 緒論 考綱要求：1.數(shù)據(jù)的四種邏輯結(jié)構(gòu)與四種存儲(chǔ)結(jié)構(gòu)（理解） 2.時(shí)間復(fù)雜度的估算及比較（掌握）知識(shí)點(diǎn)：1 、數(shù)據(jù)結(jié)構(gòu)：研究是是數(shù)據(jù)元素之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存貯表示，并對(duì)每種結(jié)構(gòu)定義各自的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而且經(jīng)過(guò)運(yùn)算后所得的新結(jié)構(gòu)一般仍然是原來(lái)的結(jié)構(gòu)類型。2、數(shù)據(jù)的四類基本組成形式：集合中任何兩個(gè)結(jié)點(diǎn)之間都沒(méi)有邏輯關(guān)系，組成形式松散。線性結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)

2、系一次排列形成一條“鎖鏈”。樹(shù)形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)像自然界中的樹(shù)。圖狀結(jié)構(gòu)最復(fù)雜，其中的各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個(gè)結(jié)點(diǎn)都可以鄰接。算法：是執(zhí)行特定計(jì)算的有窮過(guò)程。特點(diǎn)：動(dòng)態(tài)有窮確定性輸入輸出可行性。1、以算法在所有輸入下的計(jì)算量的最大值作為算法的計(jì)算量，這種計(jì)算量稱為算法的最壞時(shí)間復(fù)雜性或最壞時(shí)間復(fù)雜度。2、以算法在所有輸入下的計(jì)算量的加權(quán)平均值作為算法的計(jì)算量，這種計(jì)算量稱為算法的平均時(shí)間復(fù)雜性或者平均時(shí)間復(fù)雜度。3. 時(shí)間復(fù)雜度從好到壞的級(jí)別依次是:常量階O(1),對(duì)數(shù)階O(log2n),線性階O(n), 優(yōu)化的平方階O(n*log2n),平方階O(N2),立方階

3、O(n3),指數(shù)階O(2),階乘階O(n!)4、數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)可以概括為數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和實(shí)現(xiàn)。應(yīng)用舉例： 設(shè)n為正整數(shù)，利用大O記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。(1) i=1; k=0;while(in) k=k+10*i;i+;分析：i=1; /1k=0; /1 while(i=0)個(gè)結(jié)點(diǎn)的有窮序列。線性表:n(n0)個(gè)結(jié)點(diǎn)組成的有限序列線性結(jié)構(gòu)中的元素是有序的，元素個(gè)數(shù)可以為0 空表元素的個(gè)數(shù)是有限的同一線性表中的元素的類型,長(zhǎng)度相同.2、每個(gè)結(jié)點(diǎn)至多只有一個(gè)之間前趨和一個(gè)直接后趨，在線性結(jié)構(gòu)中這種關(guān)系是1對(duì)1的。3、線性表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)。所含結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的長(zhǎng)

4、度（簡(jiǎn)稱表長(zhǎng)）。表長(zhǎng)為0的線性表為空表。4、順序表是線性表的順序存儲(chǔ)結(jié)構(gòu)，即按順序存儲(chǔ)方式構(gòu)造的線性表的存儲(chǔ)結(jié)構(gòu)。5、第i個(gè)結(jié)點(diǎn)ai的存儲(chǔ)地址為b+（i1）L （L為內(nèi)存所占單元/表長(zhǎng)。b是順序表的第一個(gè)存儲(chǔ)結(jié)點(diǎn)的第一個(gè)單元的內(nèi)存地址。）6、線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址連不連續(xù)都可以。7、求表長(zhǎng)和讀表元算法的時(shí)間復(fù)雜性為O（1），從量級(jí)上來(lái)說(shuō)已經(jīng)達(dá)到最低水平即最高效率。8、順序表要求占用連續(xù)的空間，為克服順序表的這一缺點(diǎn)，可采用鏈接方式來(lái)存儲(chǔ)線性表，通常我們將鏈接方式存儲(chǔ)的線性表稱為鏈表。9、線性表的常見(jiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有單鏈表、循環(huán)表和雙鏈表，最簡(jiǎn)單的是單鏈表。10、定

5、位運(yùn)算在順序表和單鏈表上的實(shí)現(xiàn)算法的時(shí)間復(fù)雜性是同量級(jí)的，均為O（n）。11. 線性結(jié)構(gòu)的邏輯表示如下:L1=() L1是一個(gè)空的線性結(jié)構(gòu);L2=(a,b,c,d,e) L2線性結(jié)構(gòu)中有5個(gè)元素,a是起始元素,e是終端元素,c的直接前驅(qū)元素是b,c的直接后繼元素是d,a元素的序號(hào)是1,c元素的序號(hào)是3.L1=() L1線性表的長(zhǎng)度為零L2=(a,b,c,d,e) L2線性表的長(zhǎng)度為512 鏈表中的元素順序用結(jié)點(diǎn)中的指針給出,即用指針表示結(jié)點(diǎn)間的邏輯關(guān)系, 元素順序與邏輯順序一致.采用順序存取方式. 鏈表的長(zhǎng)度是可變的應(yīng)用舉例： 1、下述算法的功能是什么?LinkList Demo(LinkLi

6、st L) / L 是無(wú)頭結(jié)點(diǎn)單鏈表ListNode *Q,*P;if(L&L-next)Q=L;L=L-next;P=L;while (P-next) P=P-next;P-next=Q; Q-next=NULL;return L;/ Demo答：該算法的功能是：將開(kāi)始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開(kāi)始結(jié)點(diǎn)，返回新鏈表的頭指針。2. 設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入L中，并使L仍是一個(gè)有序表。答：因已知順序表L是遞增有序表，所以只要從順序表終端結(jié)點(diǎn)（設(shè)為i位置元素）開(kāi)始向前尋找到第一個(gè)小于或等于x的元素位置i后插入該位置即可。在尋找過(guò)程

7、中，由于大于x的元素都應(yīng)放在x之后，所以可邊尋找，邊后移元素，當(dāng)找到第一個(gè)小于或等于x的元素位置i時(shí)，該位置也空出來(lái)了。算法如下：/順序表存儲(chǔ)結(jié)構(gòu)如題2.7void InsertIncreaseList( Seqlist *L , Datatype x )int i;if ( L-length=ListSize)Error(“overflow);for ( i=L - length ; i0 & L-data i-1 x ; i-)L-data i =L-data i ; / 比較并移動(dòng)元素L-data i =x;L - length+;第三章 棧與隊(duì)列: 考綱要求：1棧的存儲(chǔ)及運(yùn)算實(shí)現(xiàn)（掌握

8、） ,2棧的應(yīng)用：表達(dá)式求值（理解）3棧與遞歸的實(shí)現(xiàn)（理解） ,4隊(duì)列的定義及存儲(chǔ)實(shí)現(xiàn)（掌握）知識(shí)點(diǎn)：1. 棧:棧是限定僅在一端進(jìn)行插入,刪除的特殊線性表.，棧屬于加了限定條件的線性結(jié)構(gòu)，棧是后進(jìn)先出的線性表(1) 進(jìn)棧和出棧端稱為棧頂,另一端稱為棧底(2) 棧中元素個(gè)數(shù)為0時(shí)為空棧.(3) 棧中的元素個(gè)數(shù)為有限多個(gè)(4) 同一個(gè)棧中的元素的類型,長(zhǎng)度相同新進(jìn)棧的元素稱為棧頂元素(5) 棧的順序?qū)崿F(xiàn):使用一個(gè)數(shù)組data,棧底元素存放在data(0)中,top值為棧內(nèi)元素個(gè)數(shù)及位置,空棧時(shí)top=-1(6) 使用一個(gè)結(jié)構(gòu)體變量表示一個(gè)棧元素:其中一個(gè)域?yàn)閿?shù)組data,另一個(gè)為top(7) 棧的

9、鏈接實(shí)現(xiàn):使用鏈表實(shí)現(xiàn)棧的存儲(chǔ) (8) 鏈棧:鏈表的首元素定為棧頂元素,尾元素為棧底.2、隊(duì)列也可以看成是一種運(yùn)算受限的線性表，在這種線性表中允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。隊(duì)列又稱為先進(jìn)先出線性表。(1)、隊(duì)滿的條件為：（隊(duì)尾指針+1）%長(zhǎng)度= =隊(duì)內(nèi)指針 如：（sq.rear+1）%maxsize）= =sq.front 隊(duì)空的條件為：sq.rear= =sq.front(2).隊(duì)列:限定僅能在一端進(jìn)隊(duì),另一端出隊(duì)的特殊線性表(3) 加限制的線性結(jié)構(gòu)，先進(jìn)先出表(4) 進(jìn)隊(duì)在隊(duì)尾,出隊(duì)在隊(duì)首(頭)，可以是空隊(duì)(5) 隊(duì)列中的元素個(gè)數(shù)是有限的,可變的，元素的類型,長(zhǎng)度相同應(yīng)用

10、舉例：1、指出下述程序段的功能是什么?(4)void Demo3( CirQueue *Q) / 設(shè)DataType 為int 型int x; SeqStack S;InitStack( &S);while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x);while (! StackEmpty( &s) x=Pop(&S); EnQueue( Q,x );/ Demo3功能是：程序段的功能是將一個(gè)循環(huán)隊(duì)列Q經(jīng)過(guò)S棧的處理，反向排列，原來(lái)的隊(duì)頭變成隊(duì)尾，原來(lái)的隊(duì)尾變成隊(duì)頭。2. 設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序

11、夾入其中，請(qǐng)分析 1，2 ，3 ，4 的24種排列中，哪些序列是可以通過(guò)相應(yīng)的入出棧操作得到的。答： 在1，2 ，3 ，4 的24種排列中，可通過(guò)相應(yīng)入出棧操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,4312第四章 串, 考綱要求：1串的模式匹配算法（理解）知識(shí)點(diǎn)：1、串是由零個(gè)或多個(gè)字符組成的有窮序列。含零個(gè)字符的串稱為空串，用表示。2. 串（又稱字符串）是一種特殊的線性

12、表，它的每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成。串（String）是零個(gè)或多個(gè)字符組成的有限序列。一般記為S=a1a2an將串值括起來(lái)的雙引號(hào)本身不屬于串,它的作用是避免串與常數(shù)或與標(biāo)識(shí)符混淆。3. 長(zhǎng)度為零的串稱為空串（Empty String），它不包含任何字符。 僅由一個(gè)或多個(gè)空格組成的串稱為空白串（Blank String）。 和分別表示長(zhǎng)度為1的空白串和長(zhǎng)度為0的空串。4. 串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串。包含子串的串相應(yīng)地稱為主串?？沾侨我獯淖哟?任意串是其自身的子串。5. 通常在程序中使用的串可分為：串變量和串常量。串變量和其它類型的變量一樣，其取值是可以改變的。串常量和整常

13、數(shù)、實(shí)常數(shù)一樣，在程序中只能被引用但不能改變其值。即只能讀不能寫。6. 對(duì)于某一個(gè)i,0 i n-m,將目標(biāo)串的子串Ti.i+m-1和模式串P0.m-1進(jìn)行比較,若相等,則稱匹配成功 位置i 稱為位移舉例：4.2 假設(shè)有如下的串說(shuō)明：char s130=Stocktom,CA, s230=March 5 1999, s330, *p;(1)在執(zhí)行如下的每個(gè)語(yǔ)句后p的值是什么?p=stchr(s1,t); p=strchr(s2,9); p=strchr(s2,6);(2)在執(zhí)行下列語(yǔ)句后，s3的值是什么?strcpy(s3,s1); strcat(s3,); strcat(s3,s2);解：(

14、1) stchr(*s,c)函數(shù)的功能是查找字符c在串s中的位置，若找到，則返回該位置，否則返回NULL。因此:執(zhí)行p=stchr(s1,t);后p的值是指向第一個(gè)字符t的位置, 也就是p=&s11。執(zhí)行p=strchr(s2,9);后p的值是指向s2串中第一個(gè)9所在的位置,也就是p=&s29。 執(zhí)行p=strchr(s2,6);之后，p的返回值是NULL。(2)strcpy函數(shù)功能是串拷貝，strcat函數(shù)的功能是串聯(lián)接。所以:在執(zhí)行strcpy(s3,s1); 后，s3的值是Stocktom,CA在執(zhí)行strcat(s3,); 后，s3的值變成Stocktom,Ca,在執(zhí)行完strcat(

15、s3,s2);后，s3的值就成了Stocktom,Ca,March 5,1999第五章 多維數(shù)組與廣義表（理解）,本章內(nèi)容安排學(xué)生自學(xué)。第六章 樹(shù)與二叉樹(shù), 考綱要求：1.樹(shù)的基本概念（理解） ,2.樹(shù)的存儲(chǔ)結(jié)構(gòu)與遍歷（理解）3.二叉樹(shù)的定義及鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（掌握）, 4二叉樹(shù)的遍歷算法，掌握遞歸算法（掌握），5.樹(shù)與二叉樹(shù)的轉(zhuǎn)換（掌握）, 6.哈夫曼樹(shù)的應(yīng)用（掌握）知識(shí)點(diǎn)：1、樹(shù)：是一個(gè)或多個(gè)結(jié)點(diǎn)的有窮集合T，且滿足以下條件：(1)、有且僅有一個(gè)指定的稱作樹(shù)根的結(jié)點(diǎn)；(2)、除根以外的其余結(jié)點(diǎn)被分成m個(gè)不相交的集合，這些集合的每一個(gè)又都是樹(shù)，并且稱為根的子樹(shù)。2、樹(shù)的術(shù)語(yǔ)結(jié)點(diǎn)的度：結(jié)點(diǎn)N的子樹(shù)

16、數(shù)稱為結(jié)點(diǎn)的度。(1)、樹(shù)的度：樹(shù)T中各結(jié)點(diǎn)的度的最大值稱的樹(shù)T的度。(2)、葉子：樹(shù)中度為0的結(jié)點(diǎn)稱為葉子（終端結(jié)點(diǎn)）。(3)、分枝結(jié)點(diǎn)：樹(shù)中度不為0的結(jié)點(diǎn)稱為分枝結(jié)點(diǎn)（非終端結(jié)點(diǎn)）。(4)、雙親和孩子：若樹(shù)中結(jié)點(diǎn)P的一棵子樹(shù)的根是結(jié)點(diǎn)C，則我們稱P是C的雙親或父母，反之稱C是P的孩子。(5)、結(jié)點(diǎn)的層數(shù)：樹(shù)的層數(shù)為1，其余任一結(jié)點(diǎn)的層數(shù)等于它的雙親的層數(shù)加1.(6)、樹(shù)的深度：樹(shù)中各結(jié)點(diǎn)的層數(shù)的最大值稱為T的深度（高度）。(7)、兄弟和堂兄弟：同一雙親的孩子之間互稱為兄弟，其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。(8)、祖先和子孫：一個(gè)點(diǎn)的祖先是指從樹(shù)的根到該結(jié)點(diǎn)所經(jīng)分枝上的所有結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的子

17、樹(shù)的所有結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。(9)、有序樹(shù)和無(wú)序樹(shù)：如果樹(shù)中結(jié)點(diǎn)各棵子樹(shù)規(guī)定從左至右是有次序的，則稱樹(shù)為有序樹(shù)，否則為無(wú)序樹(shù)。(10)、森林：N棵互不相交的樹(shù)的集合稱為森林。3.樹(shù)的存貯表示：(1)、雙親數(shù)組表示：記錄型一維數(shù)組：data，parent(2)、孩子鏈表表示法：多重鏈表表示法： data，degree，link1，link2單鏈表表示法：data，likn(3)、左孩子右兄弟鏈表示法：lchild，data，rsibling除樹(shù)根結(jié)點(diǎn)外,若一個(gè)結(jié)點(diǎn)的編號(hào)為i,則它的雙親結(jié)點(diǎn)的編號(hào)為i/2,也就是說(shuō):當(dāng)i為偶數(shù)時(shí),其雙親結(jié)點(diǎn)的編號(hào)為i/2,它是雙親結(jié)點(diǎn)的左孩子.當(dāng)i為奇數(shù)時(shí),其

18、雙親結(jié)點(diǎn)編號(hào)為(i-1)/2,它是雙親結(jié)點(diǎn)的右孩子.4.二叉樹(shù)：概念：是有限個(gè)結(jié)點(diǎn)的集合，它或者為空集，或者是由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的且分別稱為根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。五種形態(tài)：空，根，左，右，左右 2、性質(zhì)：位于二叉樹(shù)第I層上的結(jié)點(diǎn)，最多為2I-1；（I）=1深度為K的二叉樹(shù)的結(jié)點(diǎn)總數(shù)，最多為2K-1（K）=1N0=N2+1滿二叉樹(shù)：一棵深度為K的具有2K-1個(gè)結(jié)點(diǎn)的二叉樹(shù)完全二叉樹(shù)：在一棵二叉樹(shù)中，若所有結(jié)點(diǎn)的度為0或?yàn)?的二叉樹(shù)順序二叉樹(shù)：如果深度為K的具有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，它的每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中順序編號(hào)是1到N的結(jié)點(diǎn)相對(duì)應(yīng)的二叉樹(shù)。5.二叉樹(shù)的存貯表示：順

19、序存貯：鏈表表示：lchild，data，rchlid遍歷：前序：根左右中序：左根右后序：左右根6.二叉樹(shù)的遍歷先序遍歷,先根遍歷訪問(wèn)根結(jié)點(diǎn),遍歷左子樹(shù),遍歷右子樹(shù)中序遍歷后序遍歷按層遍歷算法有遞歸方式和非遞歸方式兩種三種遍歷的命名，根據(jù)訪問(wèn)結(jié)點(diǎn)操作發(fā)生位置命名： NLR：前序遍歷(亦稱(先序遍歷) 訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之前。 LNR：中序遍歷訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之中(間)。 LRN：后序遍歷訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之后。由于被訪問(wèn)的結(jié)點(diǎn)必是某子樹(shù)的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解釋為根、根的左

20、子樹(shù)和根的右子樹(shù)。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。. 遍歷算法:中序遍歷的遞歸算法定義：(1)遍歷左子樹(shù)； (2)訪問(wèn)根結(jié)點(diǎn)； (3)遍歷右子樹(shù)。先序遍歷的遞歸算法定義：(1)訪問(wèn)根結(jié)點(diǎn)； (2)遍歷左子樹(shù)； (3)遍歷右子樹(shù)。后序遍歷得遞歸算法定義：(1)遍歷左子樹(shù)； (2)遍歷右子樹(shù)； (3)訪問(wèn)根結(jié)點(diǎn)。7.二叉樹(shù)的線索化線索鏈表結(jié)點(diǎn)結(jié)構(gòu)為:ltag=0:lchild是指向結(jié)點(diǎn)左孩子的指針ltag=1:lchild是指向結(jié)點(diǎn)前驅(qū)的左線索rtag=0:rchild是指向結(jié)點(diǎn)右孩子的指針rtag=1:rchild是指向結(jié)點(diǎn)后繼的右線索lchild ltag dat

21、a rtag rchild8.樹(shù)的二叉樹(shù)表示，森林與二叉樹(shù)的轉(zhuǎn)換。樹(shù),森林與二叉樹(shù)之間存在一一對(duì)應(yīng)關(guān)系.樹(shù) 二叉樹(shù)(1) 先在所有兄弟結(jié)點(diǎn)之間加一連線(2) 對(duì)于每一結(jié)點(diǎn),保留與其長(zhǎng)子連線,其余去掉.森林 二叉樹(shù)(1) 先將森林中的每一棵樹(shù)變成二叉樹(shù)(2) 將二叉樹(shù)的根結(jié)點(diǎn)作為兄弟,從左到右連接9.哈夫曼樹(shù)最優(yōu)二叉樹(shù)(1)路徑長(zhǎng)度：樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之關(guān)的路徑由這兩個(gè)結(jié)點(diǎn)之間的分枝所構(gòu)成，路徑上的分枝數(shù)目稱為它的路徑長(zhǎng)度。(2)n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中,帶權(quán)路徑長(zhǎng)度WPL最小的樹(shù).(3)權(quán)值最大的葉子結(jié)點(diǎn)離根越近的二叉樹(shù).(4)滿二叉樹(shù)或完全二叉樹(shù)不一定是最優(yōu)二叉樹(shù).(5) 哈

22、夫曼編碼最優(yōu)二叉樹(shù)中左孩子為0,右孩子為1,葉子結(jié)點(diǎn)路徑的編碼.哈夫曼樹(shù)：WPL，哈夫曼碼應(yīng)用舉例：1、若二叉樹(shù)中各結(jié)點(diǎn)的值均不相同，則由二叉樹(shù)的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹(shù)，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹(shù)。 (1)已知一棵二叉樹(shù)的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF，請(qǐng)畫(huà)出此二叉樹(shù)。 (2)已知一棵二叉樹(shù)的在序序列和后序序列分別為BDCEAFHG和DECBHGFA，請(qǐng)畫(huà)出此二叉樹(shù)。 (3)已知一棵二叉樹(shù)的前序序列和后序序列分別為AB和BA，請(qǐng)畫(huà)出這兩棵不同的二叉樹(shù)。解： (1)已知二叉樹(shù)的前序序列為ABD

23、GHCEFI和中序序列GDHBAECIF，則可以根據(jù)前序序列找到根結(jié)點(diǎn)為A，由此，通過(guò)中序序列可知它的兩棵子樹(shù)包分別含有GDHB和ECIF結(jié)點(diǎn)，又由前序序列可知B和C分別為兩棵子樹(shù)的根結(jié)點(diǎn).以此類推可畫(huà)出所有結(jié)點(diǎn)： A / B C / / D EF / / G H I (2)以同樣的方法可畫(huà)出該二叉樹(shù)： A / B F C G / D E H (3)這兩棵不同的二叉樹(shù)為： A A / B B第七章 圖, 考綱要求： 1.有向圖，連通圖，連通分量，強(qiáng)連通分量等（理解）, 2.圖的存儲(chǔ)結(jié)構(gòu)（理解）3.圖的遍歷過(guò)程（理解）知識(shí)點(diǎn)：1.概念：一個(gè)圖G由兩個(gè)集合V和E組成，V是有限的非空頂點(diǎn)集，E是用頂

24、點(diǎn)對(duì)表示的邊集。無(wú)向圖，有向圖；2. 有向圖:圖G中的每條邊都是有方向的有向邊也稱為弧,是有兩個(gè)頂點(diǎn)組成的有序?qū)?有向圖的頂點(diǎn)集表示為:V1,V2,V3,V4,邊集表示為:V1,V2，V1,V3，V1,V4，V2,V3，V3,V4,3. 無(wú)向圖:圖G中的每條邊都是無(wú)方向的無(wú)向完全圖:有n*(n-1)/2條邊的無(wú)向圖無(wú)向圖的頂點(diǎn)集表示為:V1,V2,V3,V4,邊集表示為:(V1,V2),(V1,V3),(V1,V4), (V2,V3),(V3,V4),稱邊(Vi,Vj)的頂點(diǎn)Vi和Vj互為鄰接點(diǎn)(相鄰接,相關(guān)聯(lián)),邊(Vi,Vj)依附或關(guān)聯(lián)于頂點(diǎn)Vi和Vj4. 無(wú)向圖中,頂點(diǎn)v的度(Degre

25、ee)是關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目,記為D(v).有向圖中,以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目,稱為v的入度;以頂點(diǎn)v為始點(diǎn)的邊的數(shù)目,稱為v的出度;頂點(diǎn)v的度為入度與出度之和.5. 路徑:在無(wú)向圖G中,若存在一個(gè)頂點(diǎn)序列, Vp,Vi1,Vi2,Vim,Vq使得無(wú)向邊 (Vp,Vi1),(Vi1,Vi2),(Vim,Vq)均屬于E(G),則稱頂點(diǎn)Vp到Vq存在一條路徑.路徑中邊的數(shù)目稱為路徑長(zhǎng)度除Vp和Vq外,其余頂點(diǎn)均不相同,稱其為簡(jiǎn)單路徑.頂點(diǎn)的度：圖G中關(guān)聯(lián)于頂點(diǎn)V的邊的數(shù)目稱為V的度。所有頂點(diǎn)的度等于邊的兩倍。完全圖：每對(duì)頂點(diǎn)之間都有一條邊相連的圖。在有向圖中，每對(duì)頂點(diǎn)之間都有兩條有向邊相互關(guān)聯(lián)的

26、圖。在無(wú)向完全圖中，邊的總數(shù)為Cn2=n（n-1）/2在有向完全圖中，邊的總數(shù)為Pn2=n（n-1）路徑：由邊組成。連通圖：對(duì)于無(wú)向圖，如果圖中任何兩頂點(diǎn)都是可達(dá)的，則稱此圖為連能圖。對(duì)于有向圖，如果圖中任何兩個(gè)頂點(diǎn)都是相互可達(dá)的，則此有向圖是強(qiáng)連通的，如果圖中任何兩頂點(diǎn)至少有一個(gè)頂點(diǎn)另一個(gè)頂點(diǎn)可達(dá)，則稱此有向圖是單向連通的。強(qiáng)連通分量：有向圖的最大強(qiáng)連通子圖稱為它的強(qiáng)連通分量。 樹(shù)圖：其本質(zhì)特征是連通性和無(wú)圈性，把不含圈的無(wú)向連通圖稱為樹(shù)圖。網(wǎng)絡(luò)：是每條邊上帶有數(shù)量指標(biāo)的連通圖。應(yīng)用舉例：1 在圖7.23所示的各無(wú)向圖中：(1)找出所有的簡(jiǎn)單環(huán)。(2)哪些圖是連通圖?對(duì)非連通圖給出其連通分量

27、。答:(1)所有的簡(jiǎn)單環(huán)：(同一個(gè)環(huán)可以任一頂點(diǎn)作為起點(diǎn))(a)1231(b)無(wú)(c)1231、2342、12341(d)無(wú)(2)連通圖：(a)、(c)、(d)是連通圖，(b)不是連通圖，因?yàn)閺?到2沒(méi)有路徑。具體連通分量為：第八章 查找表 ,考綱要求：1二叉排序樹(shù)概念、插入、刪除算法（掌握）, 2二分查找算法（掌握）知識(shí)點(diǎn)：、查找是所有數(shù)據(jù)處理中最基本、最常用的操作。特別當(dāng)查找的對(duì)象是一個(gè)龐大數(shù)量的數(shù)據(jù)集合中的元素時(shí)，查找的方法和效率就顯得格外重要。查找：就是確定一個(gè)已給的數(shù)據(jù)是否出現(xiàn)在某個(gè)數(shù)據(jù)表中。域（字段）：組成記錄的每個(gè)數(shù)據(jù)項(xiàng)。關(guān)鍵字：通常記錄中總存在某個(gè)或某組數(shù)據(jù)項(xiàng)，它們的值能唯一標(biāo)

28、識(shí)一個(gè)記錄，這個(gè)（組）數(shù)據(jù)項(xiàng)稱為關(guān)鍵字。2.查找方法：(1)順序;(2)二分，線性插值，分區(qū)3.順序查找:從表的一端開(kāi)始,順序掃描.，平均查找次數(shù):ASLsq=(n+1)/2順序查找算法的平均查找長(zhǎng)度為：ASLs=n+1/2 （n表示第n個(gè)元素）順序查找:從表的一端開(kāi)始,順序掃描.平均查找次數(shù):ASLsq=(n+1)/24. 二分查找:在有序表中進(jìn)行,先確定表的中點(diǎn)位置,再通過(guò)比較確定下一步在哪一個(gè)半?yún)^(qū)查找.平均查找次數(shù):利用二分查找的判定樹(shù),當(dāng)n足夠大時(shí),有: ASLbnlg(n+1)-1最大查找次數(shù)為判定樹(shù)的高度h,平均查找次數(shù)約為h-1.、二分查找的時(shí)間復(fù)雜度為：O（2n）、二分查找的時(shí)

29、間性能比順序查找好，但二分查找要求以有序表作為存儲(chǔ)表示。應(yīng)用舉例：.設(shè)有序表為(a,b,c,e,f,g,i,j,k,p,q),請(qǐng)分別畫(huà)出對(duì)給定值b,g和n進(jìn)行折半查找的過(guò)程。解：(1)查找b的過(guò)程如下(其中方括號(hào)表示當(dāng)前查找區(qū)間，圓括號(hào)表示當(dāng)前比較的關(guān)鍵字)下標(biāo)： 1 2 3 4 5 6 7 8 9 10 11 12 13第一次比較： a b c d e f (g) h i j k p q第二次比較： a b (c) d e f g h i j k p q第三次比較： a (b)c d e f g h i j k p q經(jīng)過(guò)三次比較，查找成功。 (2)g的查找過(guò)程如下： a b c d e f

30、 (g) h i j k p q 一次比較成功。 (3)n的查找過(guò)程如下： 下標(biāo)： 1 2 3 4 5 6 7 8 9 10 11 12 13 第一次比較： a b c d e f (g) h i j k p q 第二次比較： a b c d e f g h i (j) k p q 第三次比較： a b c d e f g h i j k (p) q 第四次比較： a b c d e f g h i j k p q 經(jīng)過(guò)四次比較，查找失敗。第九章 排序,考綱要求： 1直接插入排序、冒泡排序、快速排序、直接選擇排序（掌握） 2.快速排序的數(shù)據(jù)變化過(guò)程（理解）知識(shí)點(diǎn)：1.排序是將一批(組)任意次序

31、的記錄重新排列成按關(guān)鍵字有序的記錄序列的過(guò)程關(guān)鍵字:用來(lái)作為排序運(yùn)算的依據(jù)就地排序:排序算法所需的輔助空間不依賴于問(wèn)題的規(guī)模,即輔助空間復(fù)雜度為O(1),非就地排序的輔助空間復(fù)雜度為O(n).2. 直接插入排序:將當(dāng)前未排序部分的第一個(gè)記錄插入到已排序部分中的適當(dāng)位置.R0為哨兵,保存要插入的記錄.R1.i-1為已排序部分,Ri.n為未排序部分.當(dāng)Ri.keyRI-1.KEY時(shí),確定RI為要插入的記錄.將大于Ri.key的記錄后移,當(dāng)R0.key Rj.key時(shí),確定Rj+1為插入位置.3.快速排序通過(guò)一趟排序，將待排序記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，再分別對(duì)這兩部分記錄進(jìn)行下一趟排序，以達(dá)到整個(gè)序列有序。三,各排序法的比較穩(wěn)定排序:直接插入排序,冒泡排序,歸并排序,基數(shù)排序.元素較小:直接插入排序,直接選擇排序元素較大:快速排序,堆排序,歸并排序穩(wěn)定排序:如果在排序期間具有相同關(guān)鍵字的記錄相對(duì)位置不變,則稱此排序方法是穩(wěn)定的.2、排序要求掌握各種排序方法的同時(shí)記住以下這張表：內(nèi)排序方法的性能比較排序方法最好時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性適用場(chǎng)合直接插入0（n）（n2）O（n2）O（1）穩(wěn)定n較小冒泡排序0（n）O（n2）O（n2）O（1）穩(wěn)定n較小快速排序O（n2n）O（n2