科文學院09z網絡數據結構期末復習資料-簡答題

/科文學院09z網絡數據結構期末復習資料三、簡答題1、已知一個65稀疏矩陣如下所示，試：（1）寫出它的三元組線性表；（2）給出三元組線性表的順序存儲表示。（1）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))（2）三元組線性表的順序存儲表示如下所示：2、求網的最小生成樹有哪些算法？它們的時間復雜度分別下多少，各適用何種情況？求網的最小生成樹可使用Prim算法，時間復雜度為O(n2)，此算法適用于邊較多的稠密圖，也可使用Kruskal算法，時間復雜度為O(eloge)，此算法適用于邊較少的稀疏圖。3、對于如下圖所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序的，試寫出：（1）從頂點v1出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；（2）從頂點v2出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹。（1）DFS：v1v2v3v4v5（2）BFS：v2v3v4v5v14、已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7};E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序的，試給出得到的拓撲排序的序列。拓撲排序為：43657215、對于序列{8,18,6,16,29,28}，試寫出堆頂元素最小的初始堆。所構造的堆如下圖所示：6、一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內容，并畫出該二叉樹。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。7、設有序列：w={23,24,27,80,28}，試給出：（1）二叉排序樹；（2）哈夫曼樹；（3）平衡二叉樹；（4）對于增量d=2按降序執(zhí)行一遍希爾排序的結果。（1）二叉排序樹如下圖所示：（2）哈夫曼樹如下圖所示：（3）平衡二叉樹如下圖所示：（4）對于增量d=2按降序執(zhí)行一遍希爾排序的結果：28,80,27,24,238、有關鍵字序列{7,23,6,9,17,19,21,22,5}，Hash函數為H(key)=key%5，采用鏈地址法處理沖突，試構造哈希表。哈希表如下圖所示：9、假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進行先序、中序、后序、按層遍歷的結果。先序：a,b,c,d,e,f中序：c,b,a,e,d,f后序：c,b,e,f,d,a按層：a,b,d,c,e,f10、已知一個無向圖的頂點集為{a,b,c,d,e}，其鄰接矩陣如下所示：（1）畫出該圖的圖形；（2）根據鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應的遍歷序列。【解答】（1）該圖的圖形如下圖所示：（2）深度優(yōu)先遍歷序列為：abdce；廣度優(yōu)先遍歷序列為：abedc。11、樹有哪些遍歷方法？它們分別對應于把樹轉變?yōu)槎鏄涞哪男┍闅v方法？樹的遍歷方法有先根序遍歷和后根序遍歷，它們分別對應于把樹轉變?yōu)槎鏄浜蟮南刃虮闅v與中序遍歷方法。12、設有數組A[-1:3,0:6,-2:3]，按行為主序存放在2000開始的連續(xù)空間中，如元素的長度是5，試計算出A[1,1,1]的存儲位置。A。13、試列出如下圖中全部可能的拓撲排序序列。全部可能的拓撲排序序列為：1523634、152634、156234、561234、516234、512634、51236414、已知哈希表地址空間為0..8，哈希函數為H(key)=key%7，采用線性探測再散列處理沖突，將數據序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入時的比較次數，并求出在等概率下的平均查找長度。哈希表及查找各關鍵字要比較的次數如下所示：ASL=(4×1+1×2+1×4+2×5)=2.515、設有一個輸入數據的序列是{46,25,78,62,12,80},試畫出從空樹起，逐個輸入各個數據而生成的二叉搜索樹。16、試畫出表達式(a+b/c)*(d-e*f)的二叉樹表示，并寫出此表達式的波蘭式表示，中綴表示及逆波蘭式表示。表達式的波蘭式表示，中綴表示及逆波蘭式表示分別是此表達式的二叉樹表示的前序遍歷、中序遍歷及后序遍歷序列。二叉樹表示如下圖所示：波蘭式表示：*+a/bc-d*ef中綴表示：a+b/c*d-e*f逆波蘭式表示：abc/+def*-*17、已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)2018、請畫出如下圖所示的鄰接矩陣和鄰接表。鄰接矩陣：鄰接表如下圖所示：19、設（1）找出所有的關鍵路徑。（2）v3事件的最早開始時間是多少。（1）找出所有的關鍵路徑有：v1→v2→v3→v5→v6，以及v1→v4→v6。（2）v3事件的最早開始時間是13。20、如果在1000000個記錄中找出兩個最小的記錄，你認為采用什么樣的排序方法所需的關鍵字比較次數最少？最多比較多少次？采用樹形選擇排序方法所需的關鍵字比較次數最少，最多比較次數=999999+=1000019次。21、假設把n個元素的序列（a1,a2,…an）滿足條件ak<max{at|1≤t≤k}的元素ak稱為“逆序元素”。若在一個無序序列中有一對元素ai>aj(i<j)，試問，當ai與aj相互交換后，該序列中逆序元素的個數一定不會增加，這句話對不對？如果對，請說明為什么？如果不對，請舉一例說明。不22、設內存有大小為6個記錄的緩沖區(qū)供內排序使用，文件的關鍵字序列為｛29,50,70,33,38,60,28,31,43,36,25,9,80,100,57,18,65,2,78,30,14,20,17,99），試列出：（1）用內排序求出初始歸并段；（2）用置換一選擇排序求初始歸并段。（1）用內排序求出初始歸并段為：歸并段1：29,33,38,50,60,70:歸并段2：9,25,28,31,36,43歸并段3：2,18,57,65,80,100:歸并段4：14,17,20,30,78,99.（2）用置換一選擇排序求初始歸并段為：歸并段1：29,33,38,50,60,70,80,100歸并段2：9,18,25,28,31,36,57,65,78,99;歸并段3：2,14,17,20,30.23、已知一組關鍵字為（19,14,23,1,68,20,84,27,55,11,10,79），哈希函數：H(key)=keyMOD13，哈希地址空間為0~12，請構造用鏈地址法處理沖突的哈希表，并求平均查找長度。用鏈地址法處理沖突的哈希表如下圖所示：ASL=(1*6+2*4+3*1+4*1)=1.7524、已知關鍵字序列{23，13，5，28，14，25}，試構造二叉排序樹。構造二叉排序樹的過程如下圖所示。構造的二叉排序樹如下圖所示：25、試述順序查找法、折半查找法和分塊查找法對被查找的表中元素的要求，對長度為n的查找表來說，三種查找法在查找成功時的查找長度各是多少？三種方法對查找的要求分別如下：順序查找法：表中元素可以任意存放；折半查找法：表中元素必須以關鍵字的大小遞增或遞減的次序存放：分塊查找法：表中元素每塊內的元素可任意存放，但塊與塊之間必須以關鍵字的大小遞增（或遞減）存放，即前一塊內所有元素的關鍵字都不能大于（或小）后一塊內任何元素的關鍵字。三種方法的平均查找長度分別如下：順序查找法：查找成功的平均查找長度為；折半查找法：查找成功的平均查找長度為log2(n+1)+1；分塊查找法：若用順序查找確定所在的塊，平均查找長度為；若用折半確定所在塊，平均查找長度為。26、設有一個輸入數據的序列是{46,25,78,62,12,80}，試畫出從空樹起，逐個輸入各個數據而生成的二叉排序樹。如下圖所示：27、給定一個關鍵字序列｛24，19，32，43，38，6，13，22｝，請寫出快速排序第一趟的結果；堆排序時所建的初始堆；然后回答上述兩種排序方法中哪一種方法使用的輔助空間最小，在最壞情況下哪種方法的時間復雜度最差？快速排序的第一趟結果為｛22,19,13,6,24,38,43,12｝；堆排序時所建立的初始大頂堆如所圖所示：兩種排序方法所需輔助空間：堆是O(1)，快速排序是O(logn)，可見堆排序所需輔助空間較少；在最壞情況下兩種排序方法所需時間：堆是O(nlogn)，快速排序是O(n2)，所以，可見快速排序時間復雜度最差。注意：快速排序的平均時排序速度最快，但在最壞情況下不一定比其他排序方法快。28、設二維數組A[0:10,-5:0]，按行優(yōu)先順序存儲，每個元素占4個單元，A[0][-5]的存儲地址為1000，則A[9][-2]的存儲地址為多少？依題意A的起始地址為1000，則有：Loc(9,-2)=1000+[(9-0)*(0-(-5)+1)+(-2-(-5))]*4=1228。29、用一維數組存放的一棵完全二叉樹：ABCDEFGHIJKL。請寫出后序遍歷該二叉樹的訪問結點序列。先畫出該二叉樹的樹形結構。對其進行后序遍歷得到后序序列為：HIDJKEBLFGCA。30、請說明對一棵二叉樹進行前序、中序和后序遍歷，其葉結點的相對次序是否會發(fā)生改變？為什么？二叉樹任兩個中葉結點必在某結點的左/右子樹中，三種遍歷方法對左右子樹的遍歷都是按左子樹在前、右子樹在后的順序進行遍歷的。所