江南大學(xué)現(xiàn)代遠(yuǎn)程教育數(shù)據(jù)結(jié)構(gòu)第3階段測試題3b

1、學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考江南大學(xué)現(xiàn)代遠(yuǎn)程教育第三階段測試卷考試科目 :數(shù)據(jù)結(jié)構(gòu) 第五章至第七章 （總分 100 分）時間： 90 分鐘_學(xué)習(xí)中心（教學(xué)點）批次：層次：專業(yè)：學(xué)號：身份證號：姓名：得分：一、選擇題（ 每題 3 分，共 30 分）1、 m 階樹中的一個分支結(jié)點最多含（C）個關(guān)鍵字。、 m-1 、 m 、 m+1、 m/2-1、 m/2、 m/2+12、設(shè)有 k 個關(guān)鍵字互為同義詞，若用線性探測法把這k 個關(guān)鍵字存入散列表，至少要進(jìn)行 （ B）次探測。、 k-1 、 k 、 k+1、 k(k-1)/23、設(shè)表中含 100 個數(shù)據(jù)元素，用折半查找法進(jìn)行查找，則所需最大比較次數(shù)為（A

2、 ）。、 50 、 25 、 10、 74、設(shè)哈希表地址范圍為 019，哈希函數(shù)H(key)=key%17 ，使用二次探測再散列法處理沖突。若表中已存放有關(guān)鍵字值為6、22、38、55 的記錄，則再放入關(guān)鍵字值為72 的記錄時，其存放地址應(yīng)為（）。、 2、 3、 4、 7、 8、以上都不對5、直接插入排序在最好情況下的時間復(fù)雜度為（D ）。、 O(logn)、 O(n)、 O(n*logn)、 O(n 2)6、將兩個各有n 個元素的有序表歸并成一個有序表，最少進(jìn)行（B ）次比較。、 n、 2n-1、 2n、 n-17、設(shè)有一組關(guān)鍵字值（ 46,79,56,38,40,84 ），則用快速排序的方

3、法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ D ）。、 38,40,46,56,79,84、 40,38,46,79,56,84、 40,38,46,56,79,84、 40,38,46,84,56,798、外部排序是指（B ）。、在外存上進(jìn)行的排序方法、不需要使用內(nèi)存的排序方法、數(shù)據(jù)量很大，需要人工干預(yù)的排序方法、排序前后數(shù)據(jù)在外存，排序時數(shù)據(jù)調(diào)入內(nèi)存的排序方法學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考9、下述文件中適合于磁帶存儲的是（C）。、順序文件、索引文件、散列文件、多關(guān)鍵字文件10、 ISAM 文件和 VSAM文件屬于（ A）。、索引非順序文件、索引順序文件、順序文件、散列文件二、（10

4、 分 ）設(shè)用堆排序法對給定關(guān)鍵字序列（，）按升序進(jìn)行排序，試畫出初始堆。答：96， 85，43， 24，15，76，33三、（10 分 ）畫出對長度為的有序表進(jìn)行折半查找的判定樹，并求等概率下查找成功時的平均查找長度。9413261115135710121416平均查找長度：8175917學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考四、（15 分 ）設(shè)內(nèi)存有大小為個記錄的區(qū)域可供內(nèi)部排序之用，文件的關(guān)鍵字序列為：（ 18， 32，56， 40，23， 11， 8， 99， 58， 36，21， 7， 4，15， 19， 87， 73， 52， 82， 63），要求用置換選擇排序求初始?xì)w并段。初始?xì)w并段

5、1： 18，23， 32，40， 56，58， 99；初始?xì)w并段2： 7， 8， 11， 15，19， 21，36， 52， 63， 73， 82， 87初始?xì)w并段3： 4五、（15 分 ）設(shè)哈希函數(shù) H(key)=(3*key)%11 ，用開放定址法處理沖突， di=i*(7*key)%10+1) ，i=1,2,3 。試在 0 的散列地址空間中對關(guān)鍵字序列（，）造哈希表，并求等概率下查找成功時的平均查找長度。L0 221 672 4133045 53613784691001平均查找長度=（ 1+1+1+2+2+1+6+3 ） /8= 178學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考六、（20 分 ）設(shè)計遞歸算法，從大到小輸出給定二叉排序樹中所有關(guān)鍵字值不小于的數(shù)據(jù)元素。Viod OutputNLT(BiTree T,KeyType X)if(!T) return;if(!LT(T->data.key,x)/ 根結(jié)點及右子樹中所有結(jié)點的關(guān)鍵字值俊不小于xOutput(T->rchild);/ 按關(guān)鍵字值從大到小的順序輸出右子樹中所有結(jié)點Printf(T->data);/輸出 p 所指結(jié)點OutputNLT(T->lchild,x);/處理左子樹else OutputNLT(T->lchild,x);/Ou