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

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

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

3、次元素之間的比較。（注意：查找不同元素，次數(shù)不同，要按照折半查找的過程來計算）15 在對一組記錄（18，6，27，12，52，15，47，29）進行直接插入排序時，當(dāng)把第6個記錄15插入到有序表時，為尋找插入位置需比較 次。二、 選擇題1 數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)是指（ ）A數(shù)組、鏈表、樹、圖形結(jié)構(gòu)B線性表、鏈表、棧隊列、數(shù)組廣義表C線性結(jié)構(gòu)、鏈表、樹、圖形結(jié)構(gòu)D集合、線性結(jié)構(gòu)、樹、圖形結(jié)構(gòu)2 線性表采用鏈式地址時，其地址（ ）A必須是連續(xù)的B一定是不連續(xù)的C部分地址必須是連續(xù)的D連續(xù)與否均可以3 在長度為n的順序表的第i (1in+1)個位置上插入一個元素，元素的移動次數(shù)為（ ）An i +

4、1Bn i CiDi - 1 4 鏈表不具有的特點是（ ）A插入、刪除不需要移動元素B可隨機訪問任一元素C不必事先估計存儲空間D所需空間與線性長度成正比5 一個棧的入棧序列是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)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（ ）。A. (rear+1) MOD n = frontB. (rear-l) MOD n = front Crear+1=frontD. rear=front7 在一個長度為n的順序表的表尾插入一個新元素的時間

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

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

7、,25,31,28,55,12,19,51,64），用鏈地址法解決沖突。假設(shè)裝填因子=0.75，散列函數(shù)的形式為H（K）= K MOD P，回答下列問題：（1）構(gòu)造出散列函數(shù)；（3分）（2）畫出插入全部關(guān)鍵字后的鏈地址散列表（5分）（3）計算出等概率情況下查找成功的平均查找長度（3分）（4）計算出等概率情況下查找失敗的平均查找長度（3分）012345678910111239 54 28 55 31 19 23 25 12 51 64 解：（1）由=0.75，得表長m=11/0.75=15，取P=13（p取小于等于表長的最大素數(shù)），得 散列函數(shù)H（k）=k MOD 13（2）因為p=13，散列地

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