文正學院數(shù)據(jù)結(jié)構(gòu)期末復習

1、數(shù)據(jù)結(jié)構(gòu)期末復習主要知識點算法的時間復雜度計算方法單鏈表堆棧和隊列的概念和應(yīng)用串的概念和應(yīng)用樹的概念和應(yīng)用圖的概念和應(yīng)用查找和排序算法滿足以下性質(zhì): (1)輸入性(2)輸出性 (3)有限性 (4)確定性 (5)可執(zhí)行性算法設(shè)計滿足以下目標: (1)正確性 (2)可讀性 (3)健壯性 (4)高時間效率 (5)高空間效率算法的時間復雜度計算方法常見的時間復雜度表示：O(1)，O(n)，O(n2) ，O(n3)，O(lbn) ，O(lgn)算法時間復雜度定義:T(n)=O(f(n),當且僅當存在正常數(shù)c和n0，對所有的n(n n0)滿足T(n)cf(n) 。T（n）為算法的基本語句執(zhí)行次數(shù)，稱為時間

2、復雜度，隨n增大與f（n）增長接近相同，級，用O(f（n）)表示其復雜度即可稱同一個數(shù)量。推導大O階的方法:(1)用常數(shù)1取代運行時間中的所有加法常數(shù)。(2)在修改后的運行次數(shù)函數(shù)中，只保留最高階項。(3)如果最高階項在且不是1，則去除與這個項相乘的常數(shù)最后得到的結(jié)果就是大O階 例1 求和算法，求1+2+3.+99+100=5050。int i,sum=0,n=100; /執(zhí)行了1次 for(i=1;i=n;i+) /執(zhí)行n+1次 sum=sum+i; /執(zhí)行n次 printf(“%d”,sum); /執(zhí)行了1次 該算法一共執(zhí)行了1+n+1+n+1=2n+3次在求時間復雜度的時候我們忽略頭尾循

3、環(huán)判斷的開銷，只需要分析影響一個算法時間復雜度的主要部分即可，即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)：該算法的時間復雜度為 T(n)=O(n) 稱為線性階注意：分析這類算法的復雜度關(guān)鍵是分析循環(huán)結(jié)構(gòu)的運行情況 例2 求和算法，求1+2+3.+99+100=5050。int sum=0,n=100; /執(zhí)行了1次sum=(1+n)*n/2 /執(zhí)行1次printf(“%d”,sum); /執(zhí)行了1次 該算法一共執(zhí)行了1+1+1=3次在求時間復雜度的時候只需要分析影響一個算法時間復雜度的主要部分即可，即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)：該算法的時間復雜度為 T(n)=O(1) 稱為常數(shù)階注意

4、：不管這個常數(shù)是多少，我們都記做O(1) ，而不是O(3)。 例3 求和算法，求1+2+3.+99+100+.=int i,j,x=0,sum=0,n=100; /執(zhí)行了1次 for(i=1;i=n;i+) for(j=1;j=n;j+) x+; /執(zhí)行n*n次 sum=sum+x; printf(“%d”,sum); /執(zhí)行了1次 在求時間復雜度的時候我們忽略頭尾循環(huán)判斷的開銷，只需要分析影響一個算法時間復雜度的主要部分即可，即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)：該算法的時間復雜度為 T(n)=O(n2) 稱為平方階注意：循環(huán)的時間復雜度等于循環(huán)體的復雜度乘以該循環(huán)的次數(shù) 例1-3 設(shè)數(shù)

5、組a和b在前邊部分已賦值，求如下兩個n階矩陣相乘運算算法的時間復雜度。for(i=0;in;i+) for(j=0;jn;j+) cij=0; /基本語句1 for(k=0;kn;k+) cij=cij+aik*bkj; /基本語句2 該算法的時間復雜度為 T(n)=O(n3) 例1-4 設(shè)n為如下算法處理的數(shù)據(jù)個數(shù)，求如下算法的時間復雜度。 for(i=1;i=n;i=2*i) printf(“i=%dn”，i)；解:設(shè)基本語句的執(zhí)行次數(shù)為T(n),有2T(n) n,即有T(n) lbn。所以該算法的時間復雜度為T(n)=O(lb n)。 稱為對數(shù)階 例1-5:下邊的算法是用冒泡排序法對數(shù)字

6、a中的n個整數(shù)類型的數(shù)據(jù)元素(a0an-1)，從小到大進行排序，求該算法的時間復雜度。void BubbleSort(int a,int n) int i,j,flag=1; int temp; for(i=1;in&flag=1;i+) flag=0; for(j=0;jaj+1) flag=1; temp=aj; aj=aj+1; aj+1=temp; 解:該算法基本語句執(zhí)行次數(shù)與原始數(shù)據(jù)序列大小情況有關(guān)系，此時，按最壞情況統(tǒng)計。設(shè)基本語句的執(zhí)行次數(shù)為T(n),最壞情況下有 T(n)n+4*n2/2因T(n) n+2* n2 c* n2,其中c為常數(shù)，所以該算法的時間復雜度為T(n)=O(

7、n2)。 算法的時間復雜度是衡量一個算法好壞的重要指標。一般來說，具有多項式時間復雜度的算法，是可接受、可實際使用的算法;具有指數(shù)時間復雜度的算法，是只有當n足夠小時才可使用的算法。 例1-6 下面的算法是在一個有n個數(shù)據(jù)元素的數(shù)組a中刪除第i個位置的數(shù)組元素，要求當刪除成功時數(shù)組元素個數(shù)減1，求該算法的時間復雜度。其中數(shù)組下標從0至n-1。int Delete(int a, int &n,int i) int j; if(i=n) return 0; /刪除位置錯誤，失敗返回 for(j=i+1;jnext=p-next;p-next=s;注：兩條語句順序不能顛倒，即“先勾右鏈，再勾左鏈”單

8、鏈表2).刪除帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素結(jié)點pa0a1an-1headdata next核心操作語句為：p=head；s=p-next; *x=s-datap-next=p-next-next; free(s);3).在不帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素前插入結(jié)點a0a1an-1headxs(a) 插入前a0a1an-1headxs(b) 插入后核心操作語句為：s-next=head;head=s;4).在不帶頭結(jié)點單鏈表其他數(shù)據(jù)元素前插入結(jié)點pai-1a0aian-1headdata nextxs核心操作語句為：s-next=p-next;p-next=s;5).刪除不帶頭結(jié)點單鏈表第一個數(shù)據(jù)

9、元素結(jié)點a0a1an-1headdata next6).刪除不帶頭結(jié)點單鏈表其他數(shù)據(jù)元素結(jié)點pai-1a0aian-1headdata nextai+1核心操作語句為：s=head;head=head-next; free(s);核心操作語句為：s=p-next; *x=s-datap-next=p-next-next; free(s);1、在帶頭結(jié)點的單鏈表head中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行的核心代碼是（ ）。s-next=p；p-next=s；s-next=p-next；p-next=s；C. s-next=p-next；p=s；D. p-next=s；s

10、-next=p；2、在帶頭結(jié)點的單鏈表head中，若刪除p所指結(jié)點的后繼結(jié)點，則執(zhí)行的核心代碼是（ ）。p-next=p-next-next；p=p-next；p-next=p-next-next；C. p-next=p-next；D. p=p-next-next；習題練習BA4、單鏈表中，增加一個頭結(jié)點的目的是為了（ ）。使單鏈表至少有一個結(jié)點。 標識表結(jié)點中首結(jié)點的位置。C. 方便運算的實現(xiàn)。 D. 說明單鏈表是線性表的鏈式存儲。5、帶頭結(jié)點的單鏈表head為空的判定條件是（ ）。A. head=NULL B. head-Next=NULL C. head-next=head D. hea

11、d!=NULLCB6、已知head為帶頭結(jié)點的單鏈表，p為其中非首元的結(jié)點，分別寫出以下操作的序列：（1）將s結(jié)點插入p結(jié)點之后；（2）刪除p的直接后繼結(jié)點；（3）刪除尾元結(jié)點；s-Next=p-Next; p-Next=s;q= p-Next; p-Next= p-Next-Next; free(q);p=head;While(p-Next-Next!=NULL) p=p-Next;q= p-Next;p-Next= p-Next-Next;free(q);堆棧和隊列的基本概念和應(yīng)用堆棧的數(shù)據(jù)元素及邏輯關(guān)系與線性表完全相同，但是操作受限。(1)定義:限定只能在固定一端進行插入和刪除操作的線性

12、表。特點：后進先出。故又稱后進先出表(2)允許進行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。隊列的基本概念堆棧的基本概念(1)定義:只能在表的一端進行插入操作，在表的另一端進行刪除操作的線性表（又稱先進先出表）。一個隊列的示意圖如下：a0a1a2an-1隊頭隊尾隊尾插入隊頭刪除1、有六個元素6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？（ ）。5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 2、一個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（ ）。A. 2 3 4 1 5 B

13、. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 23、 某堆棧的輸入序列為a, b，c ，d,下面的四個序列中，不可能是它的輸出序列的是（ ）。a，c，b，d B. b, c，d，a C. c，d，b， a D. d, c，a，b習題練習CBD5、棧和隊列的共同點是（ ） 。A都是先進后出。 B都是先進先出。C只允許在端點處插入和刪除元素。 D沒有共同點。6、以下（ ）不是隊列的基本運算?A從隊尾插入一個新元素。B從隊列中刪除第i個元素。C判斷一個隊列是否為空。D讀取隊頭元素的值。CB7、順序循環(huán)隊列中判定隊列滿的條件為（ ）。 A.rear=front B. coun

14、t 0 C. count 0 & rear=front D. count 0 | rear=front8、順序循環(huán)隊列中判定隊列空的條件為（ ）。 A.rear=front B. count = 0 C. count 0 & rear=front D. count 0 | rear=frontCB9、輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為（ ）。Apush，pop，push，pop，push，popBpush，push，push，pop， pop， popCpush，push，pop， pop，push，popDpush，pop，push，push，pop， pop10、允許對隊列

15、進行的操作有（ ）。A對隊列中的元素排序B取出最近進隊的元素C在隊頭元素之前插入元素D刪除隊頭元素11、對于循環(huán)隊列（ ）。A無法判斷隊列是否為空B無法判斷隊列是否為滿C隊列不可能滿D以上說法都不對BDD12、若用一個大小為6的數(shù)值來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（ ）。A1和5 B2和4 C4和2D5和113、隊列的“先進先出”特性是指（ ）。A最早插入隊列中的元素總是最后被刪除。B當同時進行插入、刪除操作時，總是插入操作優(yōu)先。C每當有刪除操作時，總是要先做一次插入操作。D每次從隊列中刪除的總

16、是最早插入的元素。DB、串（又稱字符串）是由n(n 0)個字符組成的有限序列。（它是數(shù)據(jù)元素為單個字符的特殊線性表。）、串長:串中字符的個數(shù)（n0）。、空串:串中字符的個數(shù)為0 時稱為空串 。、空格串:由一個或多個空格符組成的串。、子串:串S中任意個連續(xù)的字符序列叫S的子串; S叫主串。、子串位置:子串的第一個字符在主串中的序號(從0開始)。、字符位置:字符在串中的序號(從0開始) 。、串相等:串長度相等，且對應(yīng)位置上字符相等。（即兩個串中的字符序列一一對應(yīng)相等。）串的基本概念和應(yīng)用35 1、現(xiàn)有以下4個字符串：a =“BEI” b =“JING” c = “BEIJING” d = “BEI

17、 JING” 他們各自的長度？答：a是c和d的子串，在c和d中的位置都是0。 a是哪個串的子串？在主串中的位置是多少？答：a ：3，b ：4，c ：7，d：8。 空串是哪個串的子串？ a是不是自己的子串？答：空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串。子串個數(shù)問題？如：串S=“produce”，則S共多少個子串？長為2,3的子串分別多少個？習題練習2、設(shè)S1=“Data Structure Course”,S2=“Structure”,S3=“Base”，求（1）Length(S1); （2）Compare(S2,S3)；（3）Insert(S1,5,

18、S3)；（4）Delete(S1,5,9);（5）SubString(S1,5,9,T)；（6）Search(S1,0,S2);（7）Replace(S1,0,S2,S3);36Length(S1)=21。返回值為1。輸出“Data BaseStructure Course”。輸出“Data Course”。輸出T=“Structure”。返回值為5。輸出“Data Base Course”。3、串的長度是指（ ）。A串中所含不同字母的個數(shù)B串中所含字符的個數(shù)C串中所含不同字符的個數(shù)D串中所含非空格字符的個數(shù)4、串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。A可以順序存儲B數(shù)據(jù)元素是一個字符C可

19、以鏈式存儲D數(shù)據(jù)元素可以是多個字符BB若干術(shù)語（要求:理解、認識這些術(shù)語）ABCGEIDHFJFLK結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)(也可稱分支數(shù))。 葉結(jié)點（或葉子結(jié)點）：度為0的結(jié)點，也稱作終端結(jié)點。 分支結(jié)點：度不為0的結(jié)點，一棵樹中除葉結(jié)點外的所有結(jié)點都是分支結(jié)點。 樹的基本概念和應(yīng)用孩子結(jié)點：樹中某個結(jié)點的所有子樹的根結(jié)點，稱為該結(jié)點的孩子結(jié)點。雙親結(jié)點：若樹中某結(jié)點有孩子結(jié)點，則這個結(jié)點就稱作它的孩子結(jié)點的雙親結(jié)點。 兄弟結(jié)點：具有相同的雙親結(jié)點的結(jié)點之間互為兄弟結(jié)點。 樹的度：樹中所有結(jié)點的度的最大值。 結(jié)點的層次：從根結(jié)點到樹中某結(jié)點所經(jīng)路徑上的分支數(shù)，根的層次為0，其它為雙親

20、層次加1 。樹的深度：樹中所有結(jié)點的層次的最大值。 無序樹：樹中任意一個結(jié)點的各孩子結(jié)點之間的不要求區(qū)分次序，即左右顛倒后還是同一棵樹；（本章的“樹”）。 有序樹：樹中任意一個結(jié)點的各孩子結(jié)點有嚴格排列次序的樹（本章的“二叉樹”）。森林：m（m0）棵樹的集合。 二叉樹基本特點： 每個結(jié)點最多只有兩棵子樹（不存在度大于2的結(jié)點）； 左子樹和右子樹次序不能顛倒。所以下面是兩棵不同的樹。二叉樹形態(tài)：二叉樹的所有結(jié)點的形態(tài)有五種：空 、無左右子樹、只有左子樹、只有右子樹、左右子樹均存在。（形態(tài)只看形狀，不看具體結(jié)點元素值）分析：只有三個結(jié)點（假設(shè)分別為A,B,C）的二叉樹形態(tài)共有哪些情況？滿二叉樹：在

21、一棵二叉樹中，如果所有分支結(jié)點都存在左 子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的 二叉樹稱為滿二叉樹。（所有的存在的層次上結(jié)點都滿）完全二叉樹：如果一棵深度為k，有n個結(jié)點的二叉樹中各 結(jié)點能夠與深度為k的順序編號的滿二叉樹從1到n標號的 結(jié)點相對應(yīng)的二叉樹稱為完全二叉樹。（相對于深度相同 的滿二叉樹來說完全二叉樹只可能最后一層缺少最后面連 續(xù)的結(jié)點） 如下圖所示滿二叉樹也是一棵特殊的完全二叉樹。BACEDFGHIJKLMNO(a)滿二叉樹 BACEDFGHIJ(b)完全二叉樹 問題:一個深度為h的完全二叉樹最多有多少個結(jié)點?最少有多少個結(jié)點?根結(jié)點深度為0。最多2(h+1)-1個，

22、最少2h個二叉樹的性質(zhì)性質(zhì)1 在一棵非空二叉樹的第i層上至多有2i個結(jié)點（i0）。（理解、記結(jié)論）性質(zhì)2 深度為k的二叉樹至多有2k+1-1個結(jié)點。 說明：深度k=-1，表示空二叉樹，沒有一個結(jié)點；深度k=0，表示只有一個根結(jié)點。（理解、記結(jié)論）性質(zhì)3 具有n個結(jié)點的完全二叉樹的深度k為大于或等于lb(n+1)-1的最小整數(shù)。（要求會根據(jù)結(jié)點數(shù)求深度）如：20個結(jié)點的完全二叉樹深度為？答：2k-1n=2k+1-1，k=4哈夫曼樹的基本概念 從A結(jié)點到B結(jié)點所經(jīng)過的分支序列叫做從A結(jié)點到B結(jié)點的路徑；從A結(jié)點到B結(jié)點所經(jīng)過的分支個數(shù)叫做從A結(jié)點到B結(jié)點的路徑長度；從二叉樹的根結(jié)點到二叉樹中所有葉

23、結(jié)點的路徑長度之和稱作該二叉樹的路徑長度。設(shè)二叉樹有n個帶權(quán)值的葉結(jié)點，定義從二叉樹的根結(jié)點到二叉樹中所有葉結(jié)點的路徑長度與相應(yīng)葉結(jié)點權(quán)值的乘積之和稱作該二叉樹的帶權(quán)路徑長度（WPL），即：WPL = 其中，wi為第i個葉結(jié)點的權(quán)值，li為從根結(jié)點到第i個葉結(jié)點的路徑長度。 1、已知一棵樹T=(D,R),D=A,B,C,D,E,F,G,H,I,J,K,L,M,N；R=, , , ，, , , , 請畫出這棵樹，并回答以下問題：(1)哪個是根結(jié)點？ (2)哪些是葉子結(jié)點？ (3)哪個是結(jié)點G的雙親？ (4)哪些是結(jié)點E的孩子？(5)哪些是E的兄弟？ 習題練習(6)哪些是F的兄弟？ (7)結(jié)點N的

24、層次是多少？(8)以結(jié)點C為根的子樹的深度是多少？ (9)該樹的深度是多少？ (10)該樹的度是多少？2、某二叉樹結(jié)點的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點數(shù)目為（ ）。A3B2 C4D53、對某二叉樹進行先序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果是（ ）。DBFEAC B. DFEBCAC. BDFECAD. BDEFACCB4、設(shè)a,b為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，a在b前面的條件是（ ）。a在b的右方 B. a在b的左方C. a是b的祖先D. a是b的子孫5、若以4,5,6,7,8作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶

25、權(quán)路徑長度為（ ）。A. 67 B. 68C. 69 D. 70BC6、樹最適合用來表示（ ）。有序數(shù)據(jù)元素。 無序數(shù)據(jù)元素。 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù)。 D. 元素之間無聯(lián)系的數(shù)據(jù)。7、假設(shè)用于通訊的電文僅由8個字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。請為這8個字母設(shè)計哈夫曼編碼。C8、已知權(quán)值集合為5,7,2,3,6,9，要求給出哈夫曼樹，并計算帶權(quán)路徑長度WPL。9、已知一棵二叉樹的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。畫出二叉樹的形

26、態(tài)。10、設(shè)有如下圖所示的樹，要求：（1）將其轉(zhuǎn)換為二叉樹；（2）分別寫出該樹的先根遍歷序列和后根遍歷序列；（3）分別寫出轉(zhuǎn)換后的二叉樹的前序、中序以及后序遍歷序列。ABCDEFGHIJK（1）完全圖：在有n個頂點的無向圖中，若有n(n-1)/2條邊，即任意兩個頂點之間有且只有一條邊，則稱此圖為無向完全圖；在有n個頂點的有向圖中，若有n(n-1)條邊，即任意兩個頂點之間有且只有方向相反的兩條邊，則稱此圖為有向完全圖。（2）鄰接結(jié)點：在無向圖G中，若（u,v）是E(G)中的一條邊，則稱u和v互為鄰接結(jié)點，并稱邊（u,v）依附于結(jié)點u和v；在有向圖G中，若u,v是E(G)中的一條邊，則稱結(jié)點u鄰接

27、到結(jié)點v，結(jié)點v鄰接自結(jié)點u，并稱邊u,v和結(jié)點u和結(jié)點v相關(guān)聯(lián)。 圖的基本概念和應(yīng)用（3）結(jié)點的度：結(jié)點v的度是與它相關(guān)聯(lián)的邊的條數(shù)，記作TD(v)。有向圖中：結(jié)點的度 = 入度 + 出度。 即TD(v)=ID(v)+OD(v)思考：在無向圖中，所有頂點度的和是圖中邊數(shù)有何關(guān)系？答：所有頂點度的和是圖中邊數(shù)的2倍。有向圖中：所有出度和=入度和=邊總數(shù)（4）連通圖和強連通圖：在無向圖中，若從結(jié)點vi到結(jié)點vj有路徑，則稱結(jié)點vi和結(jié)點vj是連通的。如果圖中任意一對結(jié)點都是連通的，則稱該圖是連通圖。在有向圖中，若對于任意一對結(jié)點vi和結(jié)點vj（vivj）都存在路徑，則稱圖G是強連通圖。（5）最小

28、連通子圖：G1包含G的全部結(jié)點，但只有G中足夠構(gòu)成連通圖的最少數(shù)目的邊，則G1稱為G的最小連通子圖（6）生成樹：一個連通圖的最小連通子圖稱作該圖的生成樹。有n個結(jié)點的連通圖的生成樹有n個結(jié)點和n-1條邊。 生成樹一般是對無向圖來討論。 一個有n個頂點的連通圖的生成樹是原圖的極小連通子圖，它包含原圖中的所有n個頂點，并且有保持圖連通的最少的邊。 若在生成樹中刪除一條邊就會使該生成樹因變成非連通圖而不再滿足生成樹的定義；若在生成樹中增加一條邊就會使該生成樹中因存在回路而不再滿足生成樹的定義；一個連通圖的生成樹可能有許多；有n個頂點的無向連通圖，無論它的生成樹的形狀如何，一定有且只有n-1條邊。 1

29、、采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）。A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷2、采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（ ）。A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷3、具有n 個結(jié)點的連通圖至少有（ ）條邊。An1B n C n（n1）/2 D 2nAAD4、使用克魯斯卡爾算法構(gòu)造出圖G的一顆最小生成樹。127654318672051084232512155、使用普里姆算法構(gòu)造如下圖所示的一顆最小生成樹，從結(jié)點1開始。52346165356516426、已知如下圖的鄰接表，請給出頂點V1出發(fā)的深度優(yōu)先遍歷序列，以及頂點V1出發(fā)的廣度優(yōu)先遍歷序列。