數(shù)據(jù)結(jié)構(gòu)c語言版期末題庫

1、“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”期末考試試題期末考試試題一、單選題一、單選題(每小題每小題2分，共分，共1212分)1在一個單鏈表在一個單鏈表HLHL中，若要向表頭插入一個由指針中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行指向的結(jié)點，則執(zhí)行()。AHLHL＝pspsp一nextnext＝HLHLBp一nextnext＝HLHL；HLHL＝p3p3Cp一nextnext＝HlHl；p＝HLHL；Dp一nextnext＝HLHL一nextHLnex

2、tHL一nextnext＝p；2n個頂點的強連通圖中至少含有個頂點的強連通圖中至少含有()。A.nA.n—l條有向邊條有向邊B.nB.n條有向邊條有向邊C.n(nC.n(n—1)1)／2條有向邊條有向邊D.n(nD.n(n一1)1)條有向邊條有向邊3.3.從一棵二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為從一棵二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為()。A.O(1)A.O(1)B.O(n)B.O(n)C.O(1Ogzn)C.O

3、(1Ogzn)D.O(n2)D.O(n2)4由權(quán)值分別為由權(quán)值分別為3，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()。A2424B4848C7272D53535當(dāng)一個作為實際傳遞的對象占用的存儲空間較大并可能需要修改時，應(yīng)最好把它說明為當(dāng)一個作為實際傳遞的對象占用的存儲空間較大并可能需要修改時，應(yīng)最好把它說明為()參數(shù)，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。參數(shù)，以節(jié)省

4、參數(shù)值的傳輸時間和存儲參數(shù)的空間。A.A.整形整形B.B.引用型引用型C.C.指針型指針型D.D.常值引用型常值引用型6向一個長度為向一個長度為n的順序表中插人一個新元素的平均時間復(fù)雜度為的順序表中插人一個新元素的平均時間復(fù)雜度為()。AO(n)O(n)BO(1)O(1)CO(n2)O(n2)DO(10g2n)O(10g2n)二、填空題二、填空題(每空每空1分，共分，共2828分)1假定一棵二叉樹廣義表表示為假定一棵二叉樹廣義表表示為a

5、(b(ca(b(c，d)d)，c(((c(((，8)))8)))，分別寫出對它進行先序、中序、后序和后序遍歷，分別寫出對它進行先序、中序、后序和后序遍歷的結(jié)果。的結(jié)果。先序：先序：中序；中序；后序：后序：2已知一個帶權(quán)圖的頂點集已知一個帶權(quán)圖的頂點集V和邊集和邊集G分別為：分別為：V＝00，1，2，3，4，55；E=(0E=(0，1)81)8，(0(0，2)52)5，(0(0，3)23)2，(1(1，5)65)6，(2(2，3)253)

6、25，(2(2，4)134)13，(3(3，5)95)9，(4(4，5)105)10，則求出該圖的最小生則求出該圖的最小生成樹的權(quán)。成樹的權(quán)。最小生成樹的權(quán)；最小生成樹的權(quán)；3假定一組記錄的排序碼為假定一組記錄的排序碼為(46(46，7979，5656，3838，4040，8484，5050，42)42)，則利用堆排序方法建立的，則利用堆排序方法建立的初始堆為初始堆為——。4有有7個帶權(quán)結(jié)點，其權(quán)值分別為個帶權(quán)結(jié)點，其權(quán)值分別為3，7，

7、8，2，6，1010，1414，試以它們?yōu)槿~子結(jié)點生成一棵，試以它們?yōu)槿~子結(jié)點生成一棵哈夫曼樹，求出該樹的帶權(quán)路徑長度、高度、雙分支結(jié)點數(shù)。哈夫曼樹，求出該樹的帶權(quán)路徑長度、高度、雙分支結(jié)點數(shù)。帶權(quán)路徑長度：帶權(quán)路徑長度：——高度：高度：——雙分支結(jié)點數(shù)：雙分支結(jié)點數(shù)：——。四、閱讀算法，回答問題四、閱讀算法，回答問題(每小題每小題8分，共分，共1616分)1VOldAC(List25)Rear(L25)；Front(LFront(L，