數(shù)據(jù)結(jié)構(gòu)補(bǔ)充習(xí)題

1、復(fù)習(xí)補(bǔ)充題一、 填空1 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)包括順序、鏈?zhǔn)?、索引和散列等四種。2 存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的物理實(shí)現(xiàn)。3 在程序運(yùn)行過(guò)程中可以擴(kuò)充的數(shù)組是動(dòng)態(tài)分配的數(shù)組。這種數(shù)組在聲明它時(shí)需要使用數(shù)組指針。4 在鏈表中進(jìn)行插入和刪除操作的效率比在順序存儲(chǔ)結(jié)構(gòu)中進(jìn)行相同操作的效率高。5 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂。6 主程序第一次調(diào)用遞歸函數(shù)被稱為外部調(diào)用，遞歸函數(shù)自己調(diào)用自己被稱為內(nèi)部調(diào)用，它們都需要利用棧保存調(diào)用后的返回地址。7 如果一個(gè)對(duì)象部分地包含自己，或自己定義自己，則稱這個(gè)對(duì)象是遞歸的對(duì)象。8 若一個(gè)算法中的語(yǔ)句頻度之和為T(n)=n+2nlogn，則算法的時(shí)間復(fù)

2、雜度為？9 在無(wú)向圖的鄰接矩陣A中，若Ai,j等于1，則Aj,i等于？10 一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為？11 深度為h的完全二叉樹(shù)至少有_個(gè)結(jié)點(diǎn)。12 設(shè)有一個(gè)順序棧S，元素1、2、3、4、5、6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)?、3、4、6、5、1，則順序棧的容量至少應(yīng)為？13 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e3，e5，e4,e6,e2,e1,則棧S的容量至少應(yīng)該是 。14 在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找查找元素24，需進(jìn)行

3、次元素之間的比較。（注意：查找不同元素，次數(shù)不同，要按照折半查找的過(guò)程來(lái)計(jì)算）15 在對(duì)一組記錄（18，6，27，12，52，15，47，29）進(jìn)行直接插入排序時(shí)，當(dāng)把第6個(gè)記錄15插入到有序表時(shí)，為尋找插入位置需比較 次。二、 選擇題1 數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)是指（ ）A數(shù)組、鏈表、樹(shù)、圖形結(jié)構(gòu)B線性表、鏈表、棧隊(duì)列、數(shù)組廣義表C線性結(jié)構(gòu)、鏈表、樹(shù)、圖形結(jié)構(gòu)D集合、線性結(jié)構(gòu)、樹(shù)、圖形結(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 +

4、1Bn i CiDi - 1 4 鏈表不具有的特點(diǎn)是（ ）A插入、刪除不需要移動(dòng)元素B可隨機(jī)訪問(wèn)任一元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與線性長(zhǎng)度成正比5 一個(gè)棧的入棧序列是a、b、c、d、e，則棧的不可能的輸出序列是（ ）Ae d c b aBd e c b a Cd c e a bDa b c d e6 最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（ ）。A. (rear+1) MOD n = frontB. (rear-l) MOD n = front Crear+1=frontD. rear=front7 在一個(gè)長(zhǎng)度為n的順序表的表尾插入一個(gè)新元素的時(shí)間

5、復(fù)雜度為（ ）AO (n) BO (1)CO (n2 ) DO (log2 n)8 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，所有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于（ ）AnBn-1Cn+1D2*n9 已知某二叉樹(shù)的后序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（ ）。AacbedBdecabCdeabcDcedba10 n個(gè)頂點(diǎn)的有向圖中含有向邊的數(shù)目最多為（ ）An-1BnCn(n-1)/2Dn(n-1) 11 要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（ ）條邊。An-lBnCn+lD2n12 一組記錄的值為(12,38,35,25,74,50,63,90),按2路歸并排序方法對(duì)序列進(jìn)行一趟歸

6、并后的結(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三、 解答題：1 （5分）將下列樹(shù)轉(zhuǎn)換成為二叉樹(shù)（只要求給出轉(zhuǎn)換結(jié)果）掌握基本原理：第一個(gè)兒子是左子樹(shù)，后續(xù)的兒子是第一個(gè)兒子的右子樹(shù)2 設(shè)有序列(45，24，53，12，28，90)，請(qǐng)構(gòu)成一棵二叉排序樹(shù)，并求其查找成功時(shí)的平均查找長(zhǎng)度。3 以數(shù)據(jù)集（9，19，2，6，32，3，21，10）為葉結(jié)點(diǎn)的權(quán)值，構(gòu)造一棵哈夫曼樹(shù)，并計(jì)算其帶權(quán)路徑長(zhǎng)度。4 已知一組關(guān)鍵字為（39,23,54

7、,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）畫(huà)出插入全部關(guān)鍵字后的鏈地址散列表（5分）（3）計(jì)算出等概率情況下查找成功的平均查找長(zhǎng)度（3分）（4）計(jì)算出等概率情況下查找失敗的平均查找長(zhǎng)度（3分）012345678910111239 54 28 55 31 19 23 25 12 51 64 解：（1）由=0.75，得表長(zhǎng)m=11/0.75=15，取P=13（p取小于等于表長(zhǎng)的最大素?cái)?shù)），得 散列函數(shù)H（k）=k MOD 13（2）因?yàn)閜=13，散列地

8、址取0到12，用鏈地址法解決沖突，實(shí)際長(zhǎng)就取13，畫(huà)出鏈地址表如圖（3）查找成功：ASL = (17 + 22 + 31 + 41)/11 = 18/11（4）查找不成功：ASL = (16 + 25 + 31 + 51)/13 = 24/135 已知散列表長(zhǎng)度為13，散列函數(shù)為H(key)=key % 11，處理沖突的方法為線性探測(cè)法，請(qǐng)畫(huà)出依次插入關(guān)鍵字(10,8,40,27,21,57,46,23,19,56)以后的散列表，并計(jì)算查找成功和不成功時(shí)的平均查找長(zhǎng)度。6 對(duì)關(guān)鍵字序列(56，20，23，75，29，61，36，87) 進(jìn)行堆排序，使之按關(guān)鍵字遞增次序排列，請(qǐng)寫(xiě)出排序過(guò)程中建初始堆的過(guò)程。7 對(duì)關(guān)鍵字序列(42，13，24，91，23，16，05，58)進(jìn)行堆排序，使之按關(guān)鍵字遞增次序排列，請(qǐng)寫(xiě)出排序過(guò)程中建初始堆的過(guò)程。四、 證明題1 寫(xiě)出求