數(shù)據(jù)結構補充習題

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

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

3、次元素之間的比較。（注意：查找不同元素，次數(shù)不同，要按照折半查找的過程來計算）15 在對一組記錄（18，6，27，12，52，15，47，29）進行直接插入排序時，當把第6個記錄15插入到有序表時，為尋找插入位置需比較 次。二、 選擇題1 數(shù)據(jù)的四種基本邏輯結構是指（ ）A數(shù)組、鏈表、樹、圖形結構B線性表、鏈表、棧隊列、數(shù)組廣義表C線性結構、鏈表、樹、圖形結構D集合、線性結構、樹、圖形結構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、復雜度為（ ）AO (n) BO (1)CO (n2 ) DO (log2 n)8 在一棵具有n個結點的二叉樹中，所有結點的空子樹個數(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、并后的結果為（ ）。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分）將下列樹轉換成為二叉樹（只要求給出轉換結果）掌握基本原理：第一個兒子是左子樹，后續(xù)的兒子是第一個兒子的右子樹2 設有序列(45，24，53，12，28，90)，請構成一棵二叉排序樹，并求其查找成功時的平均查找長度。3 以數(shù)據(jù)集（9，19，2，6，32，3，21，10）為葉結點的權值，構造一棵哈夫曼樹，并計算其帶權路徑長度。4 已知一組關鍵字為（39,23,54

7、,25,31,28,55,12,19,51,64），用鏈地址法解決沖突。假設裝填因子=0.75，散列函數(shù)的形式為H（K）= K MOD P，回答下列問題：（1）構造出散列函數(shù)；（3分）（2）畫出插入全部關鍵字后的鏈地址散列表（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，處理沖突的方法為線性探測法，請畫出依次插入關鍵字(10,8,40,27,21,57,46,23,19,56)以后的散列表，并計算查找成功和不成功時的平均查找長度。6 對關鍵字序列(56，20，23，75，29，61，36，87) 進行堆排序，使之按關鍵字遞增次序排列，請寫出排序過程中建初始堆的過程。7 對關鍵字序列(42，13，24，91，23，16，05，58)進行堆排序，使之按關鍵字遞增次序排列，請寫出排序過程中建初始堆的過程。四、 證明題1 寫出求