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

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

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當(dāng)一個作為實際傳遞的對象占用的存儲空間較大并可能需要修改時，應(yīng)最好把它說明為()參數(shù)，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。A.整形B.引用型C.指針型D.常值引用型6向一個長度為n的順序表中插人一個新元素的平均時間復(fù)雜度為()。AO(n)BO(1)CO

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

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

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

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

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

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