大學(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í)行( )。A． HL＝ps p 一>next＝HLB． p 一>next＝HL；HL＝p3C． p 一>next＝Hl；p＝HL；D． p 一>next＝HL 一>next;HL 一>next＝p；2．n 個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含

2、有( )。A.n—l 條有向邊 B.n 條有向邊C.n(n—1)／2 條有向邊 D.n(n 一 1)條有向邊3.從一棵二叉搜索樹(shù)中查找一個(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)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為( )。A．24 B．48C． 72 D． 53 5．當(dāng)一個(gè)作

3、為實(shí)際傳遞的對(duì)象占用的存儲(chǔ)空間較大并可能需要修改時(shí)，應(yīng)最好把它說(shuō)明為( )參數(shù)，以節(jié)省參數(shù)值的傳 輸時(shí)間和存儲(chǔ)參數(shù)的空間。A.整形 B.引用型C.指針型 D.常值引用型· 6．向一個(gè)長(zhǎng)度為 n 的順序表中插人一個(gè)新元素的平均時(shí)間復(fù)雜度為( )。A．O(n) B．O(1)C．O(n2) D．O(10g2n)二、填空題(每空 1 分，共 28 分)1．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為——、——、——和——四

4、種。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 叉樹(shù)中，最多含有——結(jié)點(diǎn)。 5．假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為 18，則它的最小深度為——，最大深度為——·6．在一棵二叉搜索樹(shù)中，每個(gè)分支結(jié)點(diǎn)的左子樹(shù)上所有結(jié)點(diǎn)的值一定——該結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值一定——該 結(jié)點(diǎn)的值。

5、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 和 56 元素時(shí)，其查找長(zhǎng)度分別為——和——·11．

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

7、時(shí)間復(fù)雜度為——。 三、運(yùn)算題(每小題 6 分，共 24 分)1．假定一棵二叉樹(shù)廣義表表示為 a(b(c，d)，c(((，8)))，分別寫(xiě)出對(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}，則求出該圖的最小生成樹(shù)的

8、權(quán)。最小生成樹(shù)的權(quán)；3．假定一組記錄的排序碼為(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)生成一棵哈夫曼樹(shù)，求出該樹(shù)的帶權(quán)路 徑長(zhǎng)度、高度、雙分支結(jié)點(diǎn)數(shù)。帶權(quán)路徑長(zhǎng)度：—— 高度：—— 雙分支結(jié)點(diǎn)數(shù)：——。 四、閱讀算法，回答問(wèn)題(每小題 8 分，共 16 分)1．VOldAC(List25)；Inse

9、rtFront(L，50)；IntaL4]＝{5，8，12，15，36};for(inti＝0; iright，X) ／／3 分(c2>=1)returnc2 十 1 ／／3 分 六、編寫(xiě)算法(8 分)評(píng)分標(biāo)準(zhǔn)：請(qǐng)參考語(yǔ)句后的注釋?zhuān)蚋鶕?jù)情況酌情給分。ElemType MaxValue(LNodeO* HL。){if (HL＝=NUlL){ ／／2 分cerrdata； ／／3 分LNOde*p=HI 一

10、>next； ／／4 分while(P!：NULL){ ／／7 分if(maxdata)max＝p 一>data；p＝p 一>next；}returnmax； ／／8 分}數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 一、填空題 一、填空題1. 1. 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的 操作對(duì)象 操作對(duì)象

11、 以及它們之間的 以及它們之間的 關(guān)系 關(guān)系 和運(yùn)算等的學(xué)科。 和運(yùn)算等的學(xué)科。2. 2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（ 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, D, R） ，其中 ，其中 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ù)的 邏輯結(jié)構(gòu) 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 、數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)

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

13、之間存在多對(duì)多 多對(duì)多關(guān)系。 關(guān)系。6． 在線(xiàn)性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 在線(xiàn)性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒(méi)有 沒(méi)有 前驅(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) 沒(méi)有 沒(méi)有 后續(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. 在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有 在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有 前驅(qū) 前驅(qū) 結(jié)點(diǎn)