數(shù)據(jù)結(jié)構(gòu)第八章習(xí)題及答案

1、習(xí)題八查找一、單項(xiàng)選擇題1順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（）的線性表。A散列存儲(chǔ)順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)壓縮存儲(chǔ)索引存儲(chǔ)若查找每個(gè)記錄的概率均等，則在具有個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度為。3適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（）.鏈接方式存儲(chǔ)，元素?zé)o序.鏈接方式存儲(chǔ)，元素有序.順序方式存儲(chǔ)，元素?zé)o序.順序方式存儲(chǔ)，元素有序4當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度（）A必定快不一定在大部分情況下要快取決于表遞增還是遞減5當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為（）A數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B數(shù)據(jù)分成若干塊

2、，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊大.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個(gè)數(shù)需相同6二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法（）。A正確錯(cuò)誤二叉查找樹(shù)的查找效率與二叉樹(shù)的（1）高度結(jié)點(diǎn)的多少結(jié)點(diǎn)太多完全二叉樹(shù)有關(guān)）,在（2）樹(shù)型大.呈單大枝.樹(shù)8如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求法。分快查找順序查找折半查找9分別以下列序列構(gòu)造二叉排序樹(shù)，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是A（10，08，09，06，01

3、，2101，013）大（.10，06，08，09，01，2101，013）順序查找時(shí)其）查找效率最低。結(jié)點(diǎn)的位置結(jié)點(diǎn)太復(fù)雜。則可采用查找基于屬性.，09），散列地址為的鏈中有，用鏈）個(gè)A與處理沖突方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)B與處理沖突方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)大與處理沖突方法有關(guān)且與表的長(zhǎng)度有關(guān)的與處理沖突方法無(wú)關(guān)且與表的長(zhǎng)度無(wú)關(guān)12.設(shè)有一組記錄的關(guān)鍵字為1，914，23，1，地址法構(gòu)造散列表，散列函數(shù)為（）記錄。13.關(guān)于雜湊查找說(shuō)法不正確的有幾個(gè)（）（1）采用鏈地址法解決沖突時(shí)，查找一個(gè)元素的時(shí)間是相同的（2）采用鏈地址法解決沖突時(shí)，若插入規(guī)定總是在鏈?zhǔn)祝瑒t插入任一個(gè)元素的時(shí)間是相同的（3）

4、用鏈地址法解決沖突易引起聚集現(xiàn)象（4）再哈希法不易產(chǎn)生聚集設(shè)哈希表長(zhǎng)為，哈希函數(shù)是表中已有數(shù)據(jù)的關(guān)鍵字為5,84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置是15將.10個(gè)元素散列到1000個(gè)0單0元的哈希表中,則（）產(chǎn)生沖突。一定會(huì)一定不會(huì)仍可能會(huì)二、填空題順序查找個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為。在順序表（）中，用二分（折半）法查找關(guān)鍵碼值0需做的關(guān)鍵碼比較次數(shù)為，一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵樹(shù)而變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。哈希表是通過(guò)將查找碼按選定

5、的和，把結(jié)點(diǎn)按查找碼轉(zhuǎn)換為地址進(jìn)行存儲(chǔ)的線性表。哈希方法的關(guān)鍵是和。一個(gè)好的TOC o 1-5 h z哈希函數(shù)其轉(zhuǎn)換地址應(yīng)盡可能，而且函數(shù)運(yùn)算應(yīng)盡可能。平衡二叉樹(shù)又稱，其定義是。在哈希函數(shù)（）中，值最好取。7假定有個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)再散列法把這個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行次探測(cè)。法構(gòu)造的哈希函數(shù)肯定不會(huì)發(fā)生沖突。動(dòng)態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有和運(yùn)算，而后者不包含這兩種運(yùn)算。o在散列存儲(chǔ)中，裝填因子a的值越大，則.；a的值越小，貝y。已知元整型數(shù)組存放個(gè)學(xué)生的成績(jī)，已按由大到小排序，以下算法是用對(duì)分（折半）查找方法統(tǒng)計(jì)成績(jī)大于或等于分的學(xué)生人數(shù)，請(qǐng)?zhí)羁帐怪晟啤W(xué)生人數(shù)函數(shù)返回大于等于分的學(xué)生人數(shù)第九章查找、單項(xiàng)選擇題、填空題3二叉排序_哈希函數(shù)解決沖突的方法選擇好的哈希函數(shù)處理沖突的方法均勻簡(jiǎn)單樹(shù)（高度平衡樹(shù)，高度平衡的二叉排序樹(shù)）或?yàn)榭斩鏄?shù)，或二叉樹(shù)中任意結(jié)點(diǎn)左子樹(shù)高度與右