09級數(shù)據(jù)結(jié)構(gòu)復習題完整修正版版

1、一、填空題（每空1分 ）1、組成數(shù)據(jù)的基本單位是（數(shù)據(jù)元素）。2、棧和隊列的共同點是（只允許在端點處插入和刪除元素）。3、算法設(shè)計的原則是（正確性）、（可讀性）、（健壯性）及（高效率與存儲量）。4、ADT（Abstract Data Type），即稱為（抽象數(shù)據(jù)類型），是指一個數(shù)學模型及定義在該模型上的一組操作（運算）；ADT只考慮數(shù)據(jù)的（類型）。5、算法分析的兩個主要方面是（空間復雜性）和（時間復雜性）。6、所有能輸入到計算機中去的描述客觀事物的符號，稱為（數(shù)據(jù)）。7、線性表a是n 個類型相同數(shù)據(jù)元素的有限序列，通常記作（a0,a1,.ai-1,ai,ai+1,.,an）。8、若線性表第一個

2、元素的存儲地址是102，每個元素的長度為4，則第5個元素的地址是：(118)9、在插入排序、選擇排序、快速排序和歸并排序等方法中，平均查找長度最小的是：（快速排序）10、線性表的鏈式存儲結(jié)構(gòu)是用一組任意的存儲單元存儲線性表的各個數(shù)據(jù)元素。為了表示線性表中元素的先后關(guān)系，每個元素除了需要存儲自身的信息外還需保存（直接前驅(qū)元素）或（直接后繼元素）的存儲位置。11、數(shù)據(jù)元素及直接后繼的存儲位置（地址）組成一個數(shù)據(jù)元素的存儲結(jié)構(gòu)，稱為：（指針域）。12、線性結(jié)構(gòu)中元素之間存在（一對一）關(guān)系,樹形結(jié)構(gòu)中元素之間存在（一對多）關(guān)系,圖形結(jié)構(gòu)中元素之間存在（多對多）關(guān)系。13、數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（物理結(jié)構(gòu)

3、）與（邏輯結(jié)構(gòu)）以及它們之間的相互關(guān)系。14、線性的數(shù)據(jù)結(jié)構(gòu)包括：（線性表）、（棧）、（隊列）、（數(shù)組）和（串）。15、在一棵高度為k的滿二叉樹中，結(jié)點總數(shù)為（2k-1）。16、判定一個棧ST(最多元素為m0)為棧滿的條件是（ST> top= =0）。17、頭結(jié)點是指：（在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點），稱為頭結(jié)點。18、在線性結(jié)構(gòu)中,第一個結(jié)點（沒有）前驅(qū)結(jié)點,其余每個結(jié)點有且只有（一個）個前驅(qū)結(jié)點；最后一個結(jié)點（沒有）后續(xù)結(jié)點,其余每個結(jié)點有且只有（一個）個后續(xù)結(jié)點。19、在樹形結(jié)構(gòu)中,樹根結(jié)點沒有（前驅(qū)）結(jié)點,其余每個結(jié)點有且只有（一個）個前驅(qū)結(jié)點；葉子結(jié)點沒有（后繼）結(jié)點,

4、其余每個結(jié)點的后續(xù)結(jié)點可以（任意個）。20、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是(數(shù)據(jù)元素)的有限集合，R是D上的 關(guān)系有限集合。21在各種查找方法中,平均查找長度與結(jié)點個數(shù)n無關(guān)的查法方法是（哈希表查找法）22、哈夫曼樹是帶權(quán)路徑長度 最小 的二叉樹，又稱最優(yōu)二叉樹。23、 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系 有限集合。二、選擇題（每題1分 ）1、樹是結(jié)點的集合，它的根結(jié)點數(shù)目是 A 。A)有且只有1 B)1或多于 C)0或1 D)至少22、線性表L=(a1，a2，a3，ai，an)，下列說法正確的是 D 。A) 每個元素都有一個直接前件和

5、直接后件 B) 線性表中至少要有一個元素C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件3、棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是 B 。A) ABCED B) DCBEA C) DBCEA D) CDABE4、 n個頂點的連通圖中邊的條數(shù)至少為 C 。A) 0 B) 1 C) n-1 D) n5、在待排序的元素序列基本有序的前提下，效率最高的排序方法是 A 。A) 冒泡排序 B) 選擇排序 C) 快速排序 D) 歸并排序6、希爾排序?qū)儆?D 。A)

6、交換排序 B) 歸并排序 C) 選擇排序 D) 插入排序7、由個結(jié)點所構(gòu)成的二叉樹有 D 種形態(tài)。A）3 B）2 C） 1 D）58、非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)，滿足 C 。A) pnext=NULL B) p=NULL C) pnext=head D) P=head9、數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進行的運算，以及 A 。A)數(shù)據(jù)的存儲結(jié)構(gòu) B)計算方法 C)數(shù)據(jù)映象 D)邏輯存儲10、 n個頂點的強連通圖的邊數(shù)至少有 C 。A) n-1 B) n(n-1) C) n D) n+l11、循環(huán)鏈表的主要優(yōu)點是 B 。A) 不再需要頭指針

7、了 B) 從表中任一結(jié)點出發(fā)都能訪問到整個鏈表C) 在進行插入、刪除運算時，能更好的保證鏈表不斷開D) 已知某個結(jié)點的位置后，能夠容易的找到它的直接前件12、棧和隊列的共同特點是 C 。A)都是先進先出 B)都是先進后出 C)只允許在端點處插入和刪除元素 D)沒有共同點13、己知一個有序表為(12,18,20,25,29,32,40,62,83,90,95,98)，當順序查找值為29和90的元素時，分別需要 A 次比較才能查找成功。（A）5次和10次 （B）10次和5次 （C）5次和9次 （D）10次和4次14、設(shè)一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有 D 個葉子結(jié)點，度為2的結(jié)點

8、有C 個。（A）1000 （B）501 （C） 499 （D）500 （E）0 （F）1 15、用鏈表表示線性表的優(yōu)點是 C 。A)便于隨機存取 B)花費的存儲空間較順序存儲少 C)便于插入和刪除操作 D)數(shù)據(jù)元素的物理順序與邏輯順序相同16、下列敘述中正確的是 A 。A) 線性表是線性結(jié)構(gòu) B) 棧與隊列是非線性結(jié)構(gòu)C) 線性鏈表是非線性結(jié)構(gòu) D) 二叉樹是線性結(jié)構(gòu)17、深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為 C 。A)32 B)31 C)16 D)1518、一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是 C 。（A） edcba（B）decba（C）dceab （D）abc

9、de19、為了方便插入一個元素,數(shù)據(jù)結(jié)構(gòu)宜用 B 結(jié)構(gòu)。（A）順序存儲 （B）鏈式存儲 （C） 指針存儲 （D）數(shù)組存儲20、拓撲排序算法是通過重復選擇具有0個前驅(qū)頂點的過程來完成的。圖的BFS生成樹的樹高比DFS生成樹的樹高 A 。（A）小或相等 （B）大或相等 （C）小或不相等 （D）大或不相等21、數(shù)據(jù)結(jié)構(gòu)的三要素是指_ B_。（A）數(shù)據(jù)元素、順序存儲、存儲結(jié)構(gòu)（B）數(shù)據(jù)元素、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)（C）順序存儲、鏈式存儲、存儲結(jié)構(gòu)（D）數(shù)據(jù)元素、邏輯結(jié)構(gòu)、鏈式存儲22、己知一個有序表為(12,18,20,25,29,32,40,62,83,90,95,98),當二分查找值為29和90的元素

10、時,分別需要_ C _比較才能查找成功。（A）4次和2次 （B）3次和4次 （C）4次和4次 （D）3次和5次23、在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向后移動_ A _個元素。（A）ni+1 （B）n+i+1 （C）ni （D） n+1 24、 在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行 B （A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s;（C）s->next=p->next;p=s; （D）p->next

11、=s;s->next=p;25、設(shè)有一個空棧，棧頂指針為1000H(十六進制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_ B _。（A）16 （B）23 （C） 28 （D）2026、設(shè)有1000個無序的元素,希望用最快的速度挑選出其中前10個最大的元素，最好用_ B_ _ 排序法。（A）快速排序 （B）堆排序 （C）插入排序 （D）選擇排序27、設(shè)有一批數(shù)據(jù)元素,為了最快的存儲某元素,數(shù)據(jù)結(jié)構(gòu)宜用_ A_結(jié)構(gòu),（A）順序存儲 （B）鏈式存儲 （C） 指針存儲 （D）數(shù)組存儲28、一棵具有個結(jié)點的完全二叉樹，

12、它的深度為_ D_。（A）6 （B）7 （C） 8（D）929、一個有n個頂點的無向圖最多有_C_條邊。（A）n(n-1) （B）n /2 （C） n(n-1)/2 （D） (n-1)/230、在計算機中，算法是指_B_A)加工方法 B)解題方案的準確而完整的描述 C)排序方法 D)查詢方法31. 引入二叉線索樹的目的是（A）A加快查找結(jié)點的前驅(qū)或后繼的速度 B為了能在二叉樹中方便的進行插入與刪除C為了能方便的找到雙親 D使二叉樹的遍歷結(jié)果唯一32設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（B）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En233下面哪一方法可以判斷出一個有向圖

13、是否有環(huán)（B）： A廣度優(yōu)先遍歷 B. 拓撲排序 C. 求最短路徑 D. 求關(guān)鍵路徑34、設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用_D_數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B. 隊列 C. 線性表的鏈式存儲結(jié)構(gòu) D. 棧35、已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為_A_。ACBEFDA B FEDCBA C CBEDFA D不定36、數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：_C_A. 存儲結(jié)構(gòu) B. 邏輯結(jié)構(gòu) C. 順序存儲結(jié)構(gòu) D. 鏈式存儲結(jié)構(gòu)37、 廣度優(yōu)先遍歷類似于二叉樹的_D_ 。A先

14、序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷38、以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是_D_。A循環(huán)隊列 B. 鏈表 C. 哈希表 D. 棧39、 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1 , 則T中的葉子數(shù)為_D_ A5 B6 C7 D8 三、判斷題（ 正確在括號內(nèi)打“”，錯的打“X”。 ）1、線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰（X）2、對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。(X)3、有向圖的鄰接矩陣必定不是對稱矩陣。(X)4、歸并排序要求內(nèi)存量比較大。()5、棧和鏈表是兩種相同的數(shù)據(jù)結(jié)構(gòu)。() 6、線性表在物理存儲

15、空間中也不一定是連續(xù)的。()7、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。(X) 8、樹的后根遍歷序列等同于該樹對應的二叉樹的中序遍歷。( )9、棧是實現(xiàn)過程和函數(shù)等子程序所必需的結(jié)構(gòu)。()10、棧和隊列的存儲方式只能是鏈接方式。（X）11、線性表在物理存儲空間中也一定是連續(xù)的。（X ）12、棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式。()13、二叉樹是一般樹的特殊情形。( )14、棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。(X) 15、一棵哈夫曼樹的帶權(quán)路徑長度等于其中所有分支結(jié)點的權(quán)值之和。( )16、在中序線索二叉樹中，每一非空的線索均指向其祖先結(jié)點。( )17、必須把一般樹轉(zhuǎn)換成

16、二叉樹后才能進行存儲。(X)18、二叉樹的遍歷只是為了在應用中找到一種線性次序。( )19、由一棵二叉樹的前序序列和后序序列可以唯一確定它。(X)20、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。()21、棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。（X）22、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(X)23、二叉樹中每個結(jié)點的兩棵子樹是有序的。（）24、集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。(X)25、順序存儲方式只能用于存儲線性結(jié)構(gòu)（X）。 26、程序一定是算法。(X)27、一棵哈夫曼樹的帶權(quán)路徑長度等于其中所有分支結(jié)點的權(quán)值之和。( )28、鏈表中的頭結(jié)點僅起到標識的作用。(X) 29、健壯的算法不會因非法

17、的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()30、一個圖按廣度優(yōu)先搜索法遍歷的結(jié)果是惟一的。(X)四、簡答題 1、數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學科？ 答：數(shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計算的程序設(shè)計問題中，計算機的操作對象及對象間的關(guān)系和施加于對象的操作等的學科。2、設(shè)有一個二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個元素占一個空間，問A33(10)存放在什么位置？腳注(10)表示用10進制表示。 答：設(shè)數(shù)組元素Aij存放在起始地址為Loc ( i, j ) 的存儲單元中. Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 64

18、4 + 2 * n + 2 = 676. n= ( 676 - 2 - 644 ) / 2 = 15 Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692.3、在結(jié)點個數(shù)為n (n>1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？高度最大的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？ 答：結(jié)點個數(shù)為n時，高度最小的樹的高度為2，有2層； 它有n -1個葉結(jié)點，1個分支結(jié)點； 高度最大的樹的高度為n ,有n層；它有1個葉結(jié)點，n-1個分支結(jié)點。4、用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點

19、個數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？ 答：設(shè)圖的頂點個數(shù)為n(n>1),則鄰接矩陣元素的個數(shù)為n2，即頂點個數(shù)的平方，與圖的邊數(shù)無關(guān)。5、 已知某圖的鄰接表，如何建立該圖的鄰接矩陣？6、如果一棵樹有n1個度為1的結(jié)點, 有n2個度為2的結(jié)點, , nm個度為m的結(jié)點, 試問有多少個度為0的結(jié)點? 試推導之。 答：總結(jié)點數(shù) n = n0 + n1 + n2 + + nm總分支數(shù) e = n-1 = n0 + n1 + n2 + + nm-1= m*nm + (m-1)*nm-1 + + 2*n2 + n1則有 n0=1+0*n1+1*n2+2*n3+.(m-1)*nm7、有n個頂點的無向連通

20、圖至少有多少條邊？有n個頂點的有向強連通圖至少有多少條邊？試舉例說明 答：n個頂點的無向連通圖至少有n-1條邊,n個頂點的有向強連通圖至少有n條邊.例如:特例情況是當n = 1時,此時至少有0條邊.8、簡述分塊查找算法的思想。答：（1）首先查找索引表 ，索引表是有序表，可采用二分查找或順序查找，以確定待查的結(jié)點在哪一塊。 （2）然后在已確定的塊中進行順序查找 由于塊內(nèi)無序，只能用順序查找。9、什么是AOV網(wǎng)的關(guān)鍵路徑？ 答：用頂點表示活動，用弧表示活動間的優(yōu)先關(guān)系的有向圖，叫頂點表示活動的網(wǎng)，簡稱AOV網(wǎng)，在AOV-網(wǎng)中路徑長度最長的路徑叫關(guān)鍵路徑。10、試分別找出滿足以下條件的所有二叉樹:(

21、1) 二叉樹的前序序列與中序序列相同;(2) 二叉樹的中序序列與后序序列相同;(3) 二叉樹的前序序列與后序序列相同。 答：1) 二叉樹的前序序列與中序序列相同：空樹或缺左子樹的單支樹；(2) 二叉樹的中序序列與后序序列相同：空樹或缺右子樹的單支樹；(3) 二叉樹的前序序列與后序序列相同：空樹或只有根結(jié)點的二叉樹。11、數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？ 答：“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義，一是作為一門課程的名稱；二是作為一個科學的概念。作為科學概念，目前尚無公認定義，一般認為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個方面，一是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲結(jié)構(gòu)，三是對數(shù)據(jù)進行的操作（

22、運算）。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。12、一棵度為2的樹與一棵二叉樹有何區(qū)別？ 答：一棵度為二的有序樹與一棵二叉樹的區(qū)別在于:有序樹的結(jié)點次序是相對于另一結(jié)點而言的，如果有序樹中的子樹只有一個孩子時，這個孩子結(jié)點就無須區(qū)分其左右次序，而二叉樹無論其孩子數(shù)是否為2，均需確定其左右次序，也就是說二叉樹的結(jié)點次序不是相對于另一結(jié)點而言而是確定的。13、對于有n個頂點的無向圖，采用鄰接矩陣表示，如何判斷以下問題： 圖中有多少條邊？任意兩個頂點i和j之間是否有邊相連？任意一個頂點的度是多少？ 答：1）若有n個非零值，則邊為n/2條邊。（2）設(shè)

23、鄰接矩陣為A，若aij=1，則i,j有邊直接相連；若aik=1，akj=1則經(jīng)過k有邊直接相連。（3）統(tǒng)計以該點為行的非零元素個數(shù)。14、求網(wǎng)的最小生成樹有哪些算法？各適用于哪些情況？為什么？ 答：有普里姆算法和克魯斯卡爾算法。1）普里姆算法的時間復雜度為O(n2),與網(wǎng)中的邊無關(guān)，因此適用于求邊稀疏的網(wǎng)的生成樹。2）克魯斯卡爾算法恰恰相反，他的時間復雜度為O(eloge)(e為網(wǎng)中的邊數(shù))，因此它相對于普里姆算法而言，適合于求邊稀疏的網(wǎng)的最小生成樹。15、簡述順序查找法，折半（二分）查找法和分塊查找法對被查找表中元素中的要求。答：1）順序查找法：表中元素可以任意次序存入。2）二分查找法：表中

24、元素必須以關(guān)鍵字的大小遞增或遞減的次序有序列且順序表存儲。3）分塊查找法：表中元素塊內(nèi)的元素可以任意次序存放，但塊與塊之間必須以關(guān)鍵字的大小遞增（或遞減）存放，即前一塊內(nèi)所有元素的關(guān)鍵字都不能大（或?。┯诤笠粔K內(nèi)任何元素的關(guān)鍵字。 16、 一棵高度為h的滿k叉樹有如下性質(zhì): 第h層上的結(jié)點都是葉結(jié)點, 其余各層上每個結(jié)點都有k棵非空子樹, 如果按層次自頂向下, 同一層自左向右, 順序從1開始對全部結(jié)點進行編號, 試問:(1) 各層的結(jié)點個數(shù)是多少?(2) 編號為i的結(jié)點的父結(jié)點(若存在)的編號是多少?(3) 編號為i的結(jié)點的第m個孩子結(jié)點(若存在)的編號是多少?(4) 編號為i的結(jié)點有右兄弟的

25、條件是什么? 其右兄弟結(jié)點的編號是多少? 答：(1) ki ( i = 0, 1, , h ) (2) (3) ( i-1)*k + m + 1 (4) ( i-1 ) % k ¹ 0 或 時有右兄弟，右兄弟為i + 1。17、在單鏈表中設(shè)置頭結(jié)點的作用是什么？ 【答案】主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入元素和刪除第一個結(jié)點不必另作判斷。另外，不論鏈表是否為空，鏈表頭指針不變。18、一個有序表是采用鏈式存儲的，那么你能采用什么樣的查找技術(shù)從該表中查找某個給定的關(guān)鍵字？ 【答案】順序查找法進行查找。19、 給定一組權(quán)值: 23, 15, 66, 07, 11, 45,

26、33, 52, 39, 26, 58, 試構(gòu)造一棵具有最小帶權(quán)外部路徑長度的擴充4叉樹, 要求該4叉樹中所有內(nèi)部結(jié)點的度都是4, 所有外部結(jié)點的度都是0。這棵擴充4叉樹的帶權(quán)外部路徑長度是多少? 20、 設(shè)有序順序表中的元素依次為017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。試畫出對其進行折半搜索時的二叉搜索樹, 并計算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。 ASLsucc = ASLunsucc = 21、有一份電文中共使用5個字符：a、b、c、d、e，它們的出現(xiàn)頻率依次為4、7、5、2、

27、4，試畫出對應的哈夫曼樹，并求出每個字符的哈夫曼編碼五、寫出下列各題的構(gòu)造過程： 1、已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則構(gòu)造出此二叉樹并寫其后序遍歷的結(jié)果。2、請畫出下圖所示的樹所對應的二叉樹 。12543768 3、設(shè)一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列： A B D F C E G H 中序遍歷序列： B F D A G E H C（1）畫出這棵二叉樹。 （2）畫出這棵二叉樹的后序線索樹。 （3）將這棵二叉樹轉(zhuǎn)換成對應的樹（或森林）。 4、已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫

28、出這棵二叉樹。 5、設(shè)無向網(wǎng)絡圖G的鄰接矩陣的上三角部分如下表，請回答：（1） 畫出該網(wǎng)絡圖； （2） 求該網(wǎng)絡圖的最小生成樹(只要給出生成樹即可)； （3） 給出從頂點V5出發(fā)深度優(yōu)先搜索遍歷該圖的頂點序列（頂點標號小者優(yōu)先）。 V1 V2 V3 V4 V5 V6 V7 V1 18 23 4 6 V2 5 8 12 V3 10 G: V4 15 V5 25 V6 7 V7 6、假定用于通信的電文僅由8個字母c1, c2, c3, c4, c5, c6, 組成, 各字母在電文中出現(xiàn)的頻率分別為5, 25, 3, 6, 10, 11,。試為這6個字母設(shè)計不等長Huffman編碼, 并給出該電文的

29、總碼數(shù)。 7、給定權(quán)值集合15, 03, 14,20，02, 06, 09, 16, 17, 構(gòu)造相應的霍夫曼樹, 并計算它的帶權(quán)外部路徑長度。 8、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：B = (K, R), K = k1, k2, , k9R=<k1, k3>, <k1, k8>, <k2, k3>,<k2, k4>, <k2, k5>, <k3, k9>,<k5, k6>, <k8, k9>, <k9, k7>, <k4, k7>, <k4, k6>（1）畫出這個邏輯結(jié)構(gòu)的圖

30、示。 （2）相對于關(guān)系R, 指出所有的開始結(jié)點和終端結(jié)點。 （3）分別對關(guān)系R中的開始結(jié)點，舉出一個拓撲序列的例子。 （4）分別畫出該邏輯結(jié)構(gòu)的正向鄰接表和逆向鄰接表。 9、已知序列503，61， 512，87，122，908，170，897，275，請給出采用快速排序法對該序列作升序排列時每一趟的結(jié)果。（5分）10已知一個無向圖如下圖所示，要求用普魯姆算法算法生成最小樹 V2V0V3V5V4V1365216554611、請寫出如下無向連通圖的最小生成樹，寫出prim算法執(zhí)行過程示意圖。263566455V3V2V5V6V4V1112、對如下圖所示的二叉樹進行遍歷，分別畫出先序、中序、后序線索

31、二叉樹的邏輯表示圖。六、算法分析題 1、簡述以下關(guān)于二叉樹某操作的算法的功能和主要思想。 typedef struct BiTNode char data ; / 結(jié)點信息是字符 struct BiTNode *lchild,*rchild; / 左右孩子指針 *BiTree;Status xxxx (BiTree T, Status(*Visit)(char e) TStack S; BiTree p; InitStack(S); if(T) Push(S,T); while (!StackEmpty(S) Pop(S,p); Visit(p->data); if(p->lchi

32、ld) Push(S,p->lchild); if(p->rchild) Push(S,p->rchild); return OK; 2、一線性表存儲在帶頭結(jié)點的雙向循環(huán)鏈表中，L為頭指針，算法如下。說明該算法的功能。 void unknown (BNODETP *L) p=L->next; q=p->next; r=q->next；while (q!=L) while (p!=L) && (p->data>q->data) p=p->prior；q->prior->next=r；r->prior=q

33、->prior；q->next=p->next；q->prior=p；p->next->prior=q；p->next=q; q=r；p=q->prior；r=r->next;或r=q->next;3、分析下列算法，并簡述其功能。 void conversion( ) InitStack(s); scanf(“%d”,&x); while(x!=0) push(s, x% 8); x=x/8; while(! StackEmpty(s) ) /輸出存放在棧中 x=pop(s); printf(“%d”,x); 4、寫出以下遞歸

34、算法功能 。typedef struct BiTNode char data ; / 結(jié)點信息是字符 struct BiTNode *lchild,*rchild; / 左右孩子指針 *BiTree;Status exchangelr(BiTree &T) / 算法用函數(shù)名 exchangelr 表示BiTree p; / 臨時工作指針叉樹某操作的算法的功能和主要思想。 . / 待完成的若干語句；Status exchangelr(BiTree &T) / 算法用函數(shù)名 exchangelr 表示BiTree p; / 臨時工作指針if(!T) return OK; / 待完成

35、的若干語句；else p = T->lchild; T->lchild = T->rchild; T->rchild = p; exchangelr(T->lchild); exchangelr(T->rchild);5、簡述以下兩個算法的功能并指出這兩個算法在算法思想上的主要區(qū)別是什么。 typedef struct ElemType *elem; int length; int listsize; SqList; (1) Status DK1(SqList &a, int i, int k) int j, count; if (i<1 |

36、k<0 | i+k > a.length) return INFEASIBLE; /參數(shù)不合法 else for (count = 0; count < k; count+) for (j = i; j < a.length; j+) a.elemj-1 = a.elemj;a.length-; return OK; / DK1 (2) Status DK2(SqList &a, int i, int k) int count; if (i<1 | k<0 | i+k > a.length) return INFEASIBLE; / 參數(shù)不合法

37、 else for (count = 0; count < a.length-(i+1); count+) a.elemi-1+count = a.elemi+k-1+count; a.length -= k; return OK; / DK2 6、簡述以下算法的功能 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)        pa=La->next; pb=Lb->next;