數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言版期末考試試題附帶復(fù)習(xí)資料

1、“數(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.從一棵二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)

2、雜度大致為()。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)度為()。A24B48C72D535當(dāng)一個(gè)作為實(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ù)雜度為()。AO(n)BO(1)CO

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

4、定——該結(jié)點(diǎn)的值，右子樹(shù)上所有結(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和56元素時(shí)，其查找長(zhǎng)度分

5、別為——和——11假定對(duì)長(zhǎng)度n＝144的線性表進(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ù)雜度為——，最壞情況下的時(shí)間復(fù)雜度為

6、——。三、運(yùn)算題(每小題6分，共24分)else；elsereturn—l；2已知二叉樹(shù)中的結(jié)點(diǎn)類型BinTreeNode定義為：structBinTreeNodeElemTypedata；BinTreeNodeleft，right；其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域。下面函數(shù)的功能是返回二叉樹(shù)BT中值為x的結(jié)點(diǎn)所在的層號(hào)，請(qǐng)?jiān)趧澯袡M線的地方填寫(xiě)合適內(nèi)容。IntNodeLevel(BinTree

7、NodeBT，ElemTypeX)if(BT：＝NULL)return0；／／空樹(shù)的層號(hào)為0elseif(BT一data＝＝X)return1／／根結(jié)點(diǎn)的層號(hào)為1／／向子樹(shù)中查找x結(jié)點(diǎn)elseintcl＝NodeLevel(BT一left，X)；if(cl＝1)returncl1intc2＝；if——；／／若樹(shù)中不存在X結(jié)點(diǎn)則返回oelsereturn0；六、編寫(xiě)算法(8分)按所給函數(shù)聲明編寫(xiě)一個(gè)算法，從表頭指針為HL的單鏈表中查找出具

8、有最大值的結(jié)點(diǎn)，該最大值由函數(shù)返回，若單鏈表為空則中止運(yùn)行。EIemTypeMaxValue(LNOdeHL)“數(shù)據(jù)結(jié)構(gòu)”期末考試試題答案一、單選題(每小題2分，共12分)評(píng)分標(biāo)準(zhǔn)；選對(duì)者得2分，否則不得分。1B2B3C4D5B6A二、填空題(每空1分，共28分)1順序結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)散列結(jié)構(gòu)(次序無(wú)先后)2值(或data)子表指針(或sublist)33x245／6一十4(3h一1)／255186小于大于(或大于等于)7向上堆頂8