江南大學(xué)跳遠(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階B樹中的一個(gè)分支結(jié)點(diǎn)最多含（C）個(gè)關(guān)鍵字。A、m-1B、mC、m+1D、[m/2]-1E、[m/2]F、[m/2]+12、設(shè)有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表，至少要進(jìn)行（B）次探測(cè)。A、k-1B、kC、k+1D、k（k-1）/23、設(shè)表中含100個(gè)數(shù)據(jù)元素，用折半查找法進(jìn)行查找，則所需最大比較次數(shù)為（A）。A、50B、25C、10D、74、設(shè)哈希表地址范圍為0?19,哈希函數(shù)H（key）=key%17,使用二次探測(cè)再散列法處理沖突。若表中已存放有關(guān)鍵字值為6、22、38、55的記錄，則再放入關(guān)鍵字值為72的記錄時(shí)，其存放地址應(yīng)為（）。A、2B、3C、4D、7E、8F、以上都不對(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、nB、2n-1C、2nD、n-17、設(shè)有一組關(guān)鍵字值（46,79,56,38,40,84）,則用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（D）。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)存的排序方法word可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除9、下述文件中適合于磁帶存儲(chǔ)的是（C）。A、順序文件B、索引文件C、散列文件D、多關(guān)鍵字文件10、ISAM文件和VSAM文件屬于（A）。A、索引非順序文件B、索引順序文件C、順序文件D、散列文件二、（10分）設(shè)用堆排序法對(duì)給定關(guān)鍵字序列（85,61,15,33,24,96,76,43）按升序進(jìn)行排序，試畫出初始堆。答：96,85,43,24,15,76,33三、（10分）畫出對(duì)長(zhǎng)度為17的有序表進(jìn)行折半查找的判定樹，并求等概率下查找成功時(shí)的平均查找長(zhǎng)度。word可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除四、(15分)設(shè)內(nèi)存有大小為5個(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并段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…試在。?10的散列地址空間中對(duì)關(guān)鍵字序列(22,41,53,46,30,13,01,67)造哈希表，并求等概率下查找成功時(shí)的平均查找長(zhǎng)度。L0221672413304553613784691001…， 、17平均查找長(zhǎng)度=(1+1+1+2+2+1+6+3)/8=—8word可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除六、(20分)設(shè)計(jì)遞歸算法，從大到小輸出給定二叉排序樹中所有關(guān)鍵字值不小于x的數(shù)據(jù)元素。ViodOutputNLT(BiTreeT,KeyTypeX){if(!T)return;if(!LT(T->data.key,x)){〃根結(jié)點(diǎn)及右子樹中所有結(jié)點(diǎn)的關(guān)鍵字值俊不小于x

Output(T->rchild); 〃按關(guān)鍵字值從大到小的順序輸出右子樹中所有結(jié)點(diǎn)Printf(T->data); //輸出p所指結(jié)點(diǎn)OutputNLT(T->lchild,x); 〃處理左子樹)elseOutputNLT(T->lchild,x);}//OutputNLTword可編輯資料收集于網(wǎng)