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

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

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

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

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

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

6、最壞情況下的時(shí)間復(fù)雜度為——。三、運(yùn)算題(每小題6分，共24分)1假定一棵二叉樹廣義表表示為a(b(c，d)，c(((，8)))，分別寫出對(duì)它進(jìn)行先序、中序、后序和后序遍歷的結(jié)果。先序：中序；后序：2已知一個(gè)帶權(quán)圖的頂點(diǎ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個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點(diǎn)生成一棵哈夫曼樹，求出該樹的帶權(quán)路徑長(zhǎng)度、高度、雙分支結(jié)點(diǎn)數(shù)。帶權(quán)路徑長(zhǎng)度：——高度：——雙分支結(jié)點(diǎn)數(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分)評(píng)分標(biāo)準(zhǔn)：請(qǐng)參考語句后的注釋，或根據(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分?jǐn)?shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資

9、料數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料一、填空題一、填空題1.1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象操作對(duì)象以及它們之間的以及它們之間的關(guān)系關(guān)系和運(yùn)算等的學(xué)科。和運(yùn)算等的學(xué)科。2.2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（數(shù)據(jù)結(jié)構(gòu)被形式地定義為（DDR），其中，其中D是數(shù)據(jù)元素?cái)?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ù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的和數(shù)據(jù)的運(yùn)算運(yùn)算這三個(gè)方面的內(nèi)容。這三個(gè)方面的內(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)中元素之間存在一對(duì)一一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多多對(duì)多

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