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

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

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

3、法，以第一個(gè)記錄為基準(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í)數(shù)據(jù)調(diào)入內(nèi)存的排序方法學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考9、下述文件中適合于磁帶存儲(chǔ)的是（C）。、順序文件、索引文件、散列文件、多關(guān)鍵字文件10、 ISAM 文件和 VSAM文件屬于（ A）。、索引非順序文件、索引順序文件、順序文件、散列文件二、（10

4、 分 ）設(shè)用堆排序法對(duì)給定關(guān)鍵字序列（，）按升序進(jìn)行排序，試畫出初始堆。答：96， 85，43， 24，15，76，33三、（10 分 ）畫出對(duì)長(zhǎng)度為的有序表進(jìn)行折半查找的判定樹，并求等概率下查找成功時(shí)的平均查找長(zhǎng)度。9413261115135710121416平均查找長(zhǎng)度：8175917學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考四、（15 分 ）設(shè)內(nèi)存有大小為個(gè)記錄的區(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 的散列地址空間中對(duì)關(guān)鍵字序列（，）造哈希表，并求等概率下查找成功時(shí)的平均查找長(zhǎng)度。L0 221 672 4133045 53613784691001平均查找長(zhǎng)度=（ 1+1+1+2+2+1+6+3 ） /8= 178學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考六、（20 分 ）設(shè)計(jì)遞歸算法，從大到小輸出給定二叉排序樹中所有關(guān)鍵字值不小于的數(shù)據(jù)元素。Viod OutputNLT(BiTree T,KeyType X)if(!T) return;if(!LT(T->data.key,x)/ 根結(jié)點(diǎn)及右子樹中所有結(jié)點(diǎn)的關(guān)鍵字值俊不小于xOutput(T->rchild);/ 按關(guān)鍵字值從大到小的順序輸出右子樹中所有結(jié)點(diǎn)Printf(T->data);/輸出 p 所指結(jié)點(diǎn)OutputNLT(T->lchild,x);/處理左子樹else OutputNLT(T->lchild,x);/Ou