全國(guó)2005年10月高教自考《數(shù)據(jù)結(jié)構(gòu)》試題

　　11. n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有( )
　　A. n-1條有向邊　　　　　 　B. n條有向邊
　　C. n(n-1)/2條有向邊　　　　D. n(n-1)條有向邊
　　12. 對(duì)關(guān)鍵字序列(56，23，78，92，88，67，19，34)進(jìn)行增量為3的一趟希爾排序的結(jié)果為　( 　)
　　A. (19，23，56，34，78，67，88，92) 　B. 23，56，78，66，88，92，19，34)
　　C. (19，23，34，56，67，78，88，92)　 D. (19，23，67，56，34，78，92，88)
　　13. 若在9階B-樹(shù)中插入關(guān)鍵字引起結(jié)點(diǎn)分裂，則該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個(gè)數(shù)為( )
　　A. 4 　　　　　　　　　　　B. 5
　　C. 8 　　　　　　　　　　　D. 9
　　14. 由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹(shù)( )
　　A. 其形態(tài)不一定相同，但平均查找長(zhǎng)度相同
　　B. 其形態(tài)不一定相同，平均查找長(zhǎng)度也不一定相同
　　C. 其形態(tài)均相同，但平均查找長(zhǎng)度不一定相同
　　D. 其形態(tài)均相同，平均查找長(zhǎng)度也都相同
　　15. ISAM文件和VSAM文件的區(qū)別之一是( )
　　A. 前者是索引順序文件，后者是索引非順序文件
　　B. 前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)存取
　　C. 前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動(dòng)態(tài)索引結(jié)構(gòu)
　　D. 前者的存儲(chǔ)介質(zhì)是磁盤(pán)，后者的存儲(chǔ)介質(zhì)不是磁盤(pán)

　　二、填空題(本大題共10小題，每空2分，共20分)

　　16. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱(chēng)為數(shù)據(jù)的____________。
　　17. 刪除雙向循環(huán)鏈表中*p的前驅(qū)結(jié)點(diǎn)(存在)應(yīng)執(zhí)行的語(yǔ)句是____________。
　　18. 棧下溢是指在____________時(shí)進(jìn)行出棧操作。
　　19. 已知substr(s,i,len)函數(shù)的功能是返回串s中第i個(gè)字符開(kāi)始長(zhǎng)度為len的子串，strlen(s)函數(shù)的功能是返回串s的長(zhǎng)度。若s=″ABCDEFGHIJK″,t=″ABCD″,執(zhí)行運(yùn)算substr(s,strlen(t), strlen(t))后的返回值為_(kāi)___________。
　　20. 去除廣義表LS=(a1,a2,a3,……，an)中第1個(gè)元素，由其余元素構(gòu)成的廣義表稱(chēng)為L(zhǎng)S的____________。
　　21. 已知完全二叉樹(shù)T的第5層只有7個(gè)結(jié)點(diǎn)，則該樹(shù)共有____________個(gè)葉子結(jié)點(diǎn)。
　　22. 在有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱(chēng)為v的____________。
　　23. 當(dāng)關(guān)鍵字的取值范圍是實(shí)數(shù)集合時(shí)，無(wú)法進(jìn)行箱排序和____________排序。
　　24. 產(chǎn)生沖突現(xiàn)象的兩個(gè)關(guān)鍵字稱(chēng)為該散列函數(shù)的____________。
　　25. 假設(shè)散列文件中一個(gè)桶能存放m個(gè)記錄，則桶“溢出”的含義是，當(dāng)需要插入新的記錄時(shí)，該桶中____________。