大學數(shù)據(jù)結(jié)構(gòu)期末考試試題有答案

1、“數(shù)據(jù)結(jié)構(gòu)”期末考試試題“數(shù)據(jù)結(jié)構(gòu)”期末考試試題一、單選題(每小題2分，共12分)1在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行()。AHL＝psp一next＝HLBp一next＝HL；HL＝p3Cp一next＝Hl；p＝HL；Dp一next＝HL一nextHL一next＝p；2n個頂點的強連通圖中至少含有()。A.n—l條有向邊B.n條有向邊C.n(n—1)／2條有向邊D.n(n一1)條有向邊3.從一棵二叉搜索樹中

2、查找一個元素時，其時間復雜度大致為()。A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4由權(quán)值分別為3，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()。A24B48C72D535當一個作為實際傳遞的對象占用的存儲空間較大并可能需要修改時，應最好把它說明為()參數(shù)，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。A.整形B.引用型C.指針型D.常值引用型6向一個長度為n的順序表中插人一個新元素的平均時間復雜度為()。

3、AO(n)BO(1)CO(n2)DO(10g2n)二、填空題(每空1分，共28分)1數(shù)據(jù)的存儲結(jié)構(gòu)被分為——、——、——和——四種。2在廣義表的存儲結(jié)構(gòu)中，單元素結(jié)點與表元素結(jié)點有一個域?qū)煌?，各自分別為——域和——域。3——中綴表達式3十x(2.4／5—6)所對應的后綴表達式為————。4在一棵高度為h的3叉樹中，最多含有——結(jié)點。5假定一棵二叉樹的結(jié)點數(shù)為18，則它的最小深度為——，最大深度為——6在一棵二叉搜索樹中，每個分支結(jié)點

4、的左子樹上所有結(jié)點的值一定——該結(jié)點的值，右子樹上所有結(jié)點的值一定——該結(jié)點的值。7當向一個小根堆插入一個具有最小值的元素時，該元素需要逐層——調(diào)整，直到被調(diào)整到——位置為止。8表示圖的三種存儲結(jié)構(gòu)為——、——和———。9對用鄰接矩陣表示的具有n個頂點和e條邊的圖進行任一種遍歷時，其時間復雜度為——，對用鄰接表表示的圖進行任一種遍歷時，其時間復雜度為——。10從有序表(12，18，30，43，56，78，82，95)中依次二分查找43和

5、56元素時，其查找長度分別為——和——11假定對長度n＝144的線性表進行索引順序查找，并假定每個子表的長度均為，則進行索引順序查找的平均查找長度為——，時間復雜度為——12一棵B—樹中的所有葉子結(jié)點均處在——上。13每次從無序表中順序取出一個元素，把這插入到有序表中的適當位置，此種排序方法叫做——排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做——排序。14快速排序在乎均情況下的時間復雜度為——，

6、最壞情況下的時間復雜度為——。三、運算題(每小題6分，共24分)1假定一棵二叉樹廣義表表示為a(b(c，d)，c(((，8)))，分別寫出對它進行先序、中序、后序和后序遍歷的結(jié)果。先序：中序；后序：2已知一個帶權(quán)圖的頂點集V和邊集G分別為：V＝0，1，2，3，4，5；E=(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10，則求出該圖的最小生成樹的權(quán)。最小生成樹的權(quán)；3假定

7、一組記錄的排序碼為(46，79，56，38，40，84，50，42)，則利用堆排序方法建立的初始堆為——。4有7個帶權(quán)結(jié)點，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點生成一棵哈夫曼樹，求出該樹的帶權(quán)路徑長度、高度、雙分支結(jié)點數(shù)。帶權(quán)路徑長度：——高度：——雙分支結(jié)點數(shù)：——。四、閱讀算法，回答問題(每小題8分，共16分)1VOldAC(List25)；Front(L，50)；IntaL4]＝5，8，12，15，36f

8、(inti＝0iright，X)／／3分(c2=1)returnc2十1／／3分六、編寫算法(8分)評分標準：請參考語句后的注釋，或根據(jù)情況酌情給分。ElemTypeMaxValue(LNodeOHL。)if(HL＝=NUlL)／／2分cerrdata；／／3分LNOdep=HI一next；／／4分while(P!：NULL)／／7分if(maxdata)max＝p一data；p＝p一next；returnmax；／／8分數(shù)據(jù)結(jié)構(gòu)復習資

9、料數(shù)據(jù)結(jié)構(gòu)復習資料一、填空題一、填空題1.1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象操作對象以及它們之間的以及它們之間的關(guān)系關(guān)系和運算等的學科。和運算等的學科。2.2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（數(shù)據(jù)結(jié)構(gòu)被形式地定義為（DDR），其中，其中D是數(shù)據(jù)元素數(shù)據(jù)元素的有限集合，的有限集合，R是D上的上的關(guān)系關(guān)系有限集合。有限集合。3.3.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的

10、邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)、數(shù)據(jù)的、數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)和數(shù)據(jù)的和數(shù)據(jù)的運算運算這三個方面的內(nèi)容。這三個方面的內(nèi)容。4.4.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)線性結(jié)構(gòu)和非線性結(jié)構(gòu)非線性結(jié)構(gòu)。5.5.線性結(jié)構(gòu)中元素之間存在線性結(jié)構(gòu)中元素之間存在一對一一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多多對多

11、關(guān)系。關(guān)系。6在線性結(jié)構(gòu)中，第一個結(jié)點在線性結(jié)構(gòu)中，第一個結(jié)點沒有沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點個前驅(qū)結(jié)點；最后一個結(jié)點沒有沒有后續(xù)結(jié)點，其后續(xù)結(jié)點，其余每個結(jié)點有且只有余每個結(jié)點有且只有1個后續(xù)結(jié)點。個后續(xù)結(jié)點。7.7.在樹形結(jié)構(gòu)中，樹根結(jié)點沒有在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)前驅(qū)結(jié)點，其余每個結(jié)點有且只有結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；葉子結(jié)點沒有個前驅(qū)結(jié)點；葉子結(jié)點