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

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

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

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

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

5、初始?xì)w并段。初始?xì)w并段 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。試在01 0的散列地址空間中對(duì)關(guān)鍵字序列(22,41,53,46,30,13,01,6 7)造哈希表，并求等概率下查找成功時(shí)的平均查找長(zhǎng)度。012345678910L2267413053134601平均查找長(zhǎng)度：=(1 + 1+1+2+2+1+6+3 ) /8=口8學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考六、(20 分 )設(shè)計(jì)遞歸算法，從大到小輸出給定二叉排序樹中所有關(guān)鍵字值不小于X的數(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);Printf(T-data);/按關(guān)鍵字值從大到小的順序輸出右子樹中所有結(jié)點(diǎn)/輸出 p 所指結(jié)點(diǎn)OutputNLT(T-lchild,x);/處理左子樹else OutputNLT(T-lch