《數(shù)據(jù)結(jié)構(gòu)》期末（A卷）2011

1、命題方式： 獨(dú)立命題佛山科學(xué)技術(shù)學(xué)院2011 2012 學(xué)年第 一 學(xué)期數(shù)據(jù)結(jié)構(gòu)（A卷）課程期 末 考試試題專業(yè)、班級(jí)： 10計(jì)算機(jī) 姓名： 學(xué)號(hào)： 題 號(hào)一二三四五六七八九十十一十二總成績(jī)得 分一、 填空（20分，每空2分）1. 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)包括順序、 、索引和散列等四種。2. 存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的 實(shí)現(xiàn)。3. 在程序運(yùn)行過(guò)程中可以擴(kuò)充的數(shù)組是 分配的數(shù)組。這種數(shù)組在聲明它時(shí)需要使用數(shù)組指針。4. 在鏈表中進(jìn)行插入和 操作的效率比在順序存儲(chǔ)結(jié)構(gòu)中進(jìn)行相同操作的效率高。5. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 。6. 若一個(gè)算法中的語(yǔ)句頻度之和為T(n) = n + 2n

2、logn，則算法的時(shí)間復(fù)雜度為 。7. 一棵具有10個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為 。8. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2、e3、e5、e4、e6、e1，則棧S的容量至少應(yīng)該是 。9. 在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找查找元素22，需進(jìn)行 次元素之間的比較。10. 在對(duì)一組記錄（18，6，27，12，52，15，47，29）進(jìn)行直接插入排序時(shí)，當(dāng)把第5個(gè)記錄52插入到有序表時(shí)，為尋找插入位置需比較 次。二、 選擇題（20分，每選2分）1. 數(shù)

3、據(jù)的四種基本邏輯結(jié)構(gòu)是指（ ）A數(shù)組、鏈表、樹、圖形結(jié)構(gòu)B線性表、鏈表、棧隊(duì)列、數(shù)組廣義表C線性結(jié)構(gòu)、鏈表、樹、圖形結(jié)構(gòu)D集合、線性結(jié)構(gòu)、樹、圖形結(jié)構(gòu)2. 線性表采用鏈?zhǔn)降刂窌r(shí)，其地址（ ）A必須是連續(xù)的B一定是不連續(xù)的C部分地址必須是連續(xù)的D連續(xù)與否均可以3. 在長(zhǎng)度為n的順序表的第i (1in+1)個(gè)位置上插入一個(gè)元素，元素的移動(dòng)次數(shù)為（ ）An i + 1Bn i CiDi - 1 4. 一個(gè)棧的入棧序列是a、b、c、d、e，則棧的不可能的輸出序列是（ ）Ae d c b aBd e c b a Cd c e a bDa b c d e5. 最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)

4、頭是front，則隊(duì)空的條件是（ ）。A. (rear+1) MOD n = frontB. (rear-l) MOD n = front Crear+1=frontD. rear=front6. 在一個(gè)長(zhǎng)度為n的順序表的表尾插入一個(gè)新元素的時(shí)間復(fù)雜度為（ ）AO (n) BO (1)CO (n2 ) DO (log2 n)7. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于（ ）AnBn-1Cn+1D2*n8. 已知某二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（ ）。AacbedBdecabCdeabcDcedba9. n個(gè)頂點(diǎn)的有向圖中含有向邊

5、的數(shù)目最多為（ ）An-1BnCn(n-1)/2Dn(n-1) 10. 一組記錄的值為(12,38,35,25,74,50,63,90),按2路歸并排序方法對(duì)序列進(jìn)行一趟歸并后的結(jié)果為（ ）。A12,38,25,35,50,74,63,90B12,38,35,25,74,50,63,90C12,25,35,38,50,74,63,90D12,35,38,25,63,50,74,90三、 解答題：（共40分）1 （5分）將下列樹轉(zhuǎn)換成為二叉樹（只要求給出轉(zhuǎn)換結(jié)果） 2 (7分) 設(shè)有序列(45，24，53，12，28，90)，請(qǐng)構(gòu)成一棵二叉排序樹，并求其查找成功時(shí)的平均查找長(zhǎng)度。3 (8分) 以

6、數(shù)據(jù)集（9，19，2，6，32，3，21，10）為葉結(jié)點(diǎn)的權(quán)值，構(gòu)造一棵哈夫曼樹，并計(jì)算其帶權(quán)路徑長(zhǎng)度。4 （14分）已知一組關(guān)鍵字為（39,23,54,25,31,28,55,12,19,51,64），用鏈地址法解決沖突。假設(shè)裝填因子=0.75，散列函數(shù)的形式為H（K）= K MOD P，回答下列問(wèn)題：（1）構(gòu)造出散列函數(shù)；（3分）（2）畫出插入全部關(guān)鍵字后的鏈地址散列表（5分）（3）計(jì)算出等概率情況下查找成功的平均查找長(zhǎng)度（3分）（4）計(jì)算出等概率情況下查找失敗的平均查找長(zhǎng)度（3分）5 （6分）對(duì)關(guān)鍵字序列(56，20，23，75，29，61，36，87) 進(jìn)行堆排序，使之按關(guān)鍵字遞增次序排列，請(qǐng)寫出排序過(guò)程中建初始堆的過(guò)程。四、證明與問(wèn)答題（共20分）1 (