資源描述：
《集合(散列搜索樹折半)習(xí)題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、一、選擇題：1、對N個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為(A)【南京理工大學(xué)1998—、7(2分)】A.(N+1)/2C.NB.N/2D.
2、(l+N)*N]/22、下面關(guān)于二分查找的敘述正確的是)【南京理工大學(xué)A.表必須有序，表可以順序方式存儲，也可以鏈表方式存儲C.表必須有序，而且只能從小到大排列B.表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型D.表必須有序，且表只能以順序方式存儲【南京理工大學(xué)3、適用于折半查找的表的存儲方式及元素排列要求為(D1997—、6(2分〉】元素?zé)o序匹素有序元素?zé)o序元素有序A.鏈接方式存儲,B.鏈接方式
3、存儲,C.順序方式存儲,D.順序方式存儲,4、當(dāng)在一個有序的順序存儲表上查找一個數(shù)據(jù)時，即可用折半查找，也可用順序查找，但前者比后者的查找速度(C)A.必定快B.不一定C.在大部分情況下要快D.取決于表遞增還是遞減【南京理工大學(xué)〈2分〉】5、具有12個關(guān)鍵字的有序表，折半查找的平均查找長度(A〉【中山大學(xué)1998二、10(2分〉】A.3.1B.4C.2.5D.56、折半查找的時間復(fù)雜性為(D〉【中山大學(xué)1999-x15]A.O(n2)B.O(n)C.O(nlogn)D.O(logn)7、散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以(D)取其值域的每個值。A.最大概率
4、B.最小概率C.平均概率D.同等概率8、二叉查找樹的查找效率與二叉樹的（（1）C）有關(guān)，在（（2）C）時其查找效率最低【武漢交通科技大學(xué)1996-v2（4分）】(1):A.高度B.結(jié)點(diǎn)的多少C.樹型D.結(jié)點(diǎn)的位置(2)：A.結(jié)點(diǎn)太多B.完全二叉樹C.呈單枝樹D?結(jié)點(diǎn)太復(fù)雜。9、分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的是（C）【合肥工業(yè)大學(xué)2000—V4（2分）】A.(100,80,90,60,120,110,130)B.(100,120,110,130,80,60,90)C.(100,60,80,90,120,110,130)D.(100
5、,80,60,90,120,130,110)10、下面關(guān)于哈希（Hash,雜凄）查找的說法正確的是（C）【南京理工大學(xué)1998—、10（2分）】A.哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小B.除留余數(shù)法是所有哈希函數(shù)中最好的C.不存在特別好與壞的哈希函數(shù)，要視情況而定D.若需在哈希表中刪去一個元素，不管用何種方法解決沖突都只要簡單的將該元素刪去即可11、設(shè)哈希表長為14,哈希函數(shù)是H（key）=key%ll,表中已有數(shù)據(jù)的關(guān)鍵字為15,38,61,8個，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測再散列法解決沖突，則放入的位置是（D）【南京理工大學(xué)20
6、01一、15（1?5分）】A.8B?3C?5二次探測：h2i.i(x)=(h(x)4-i2)%B;h2i+i(x)=(h(x)-i2)%B;12、假定有k個關(guān)鍵字互為同義詞，若用線性探測法把這k個關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測？（D）A.k-1次B.k次C.k+1次D.k（k+1〉/2次13、散列表的地址區(qū)間為0?17,散列函數(shù)為H（K）=Kmod17。采用線性探測法處理沖突，并將關(guān)鍵字序列26,25,72,38,8,18,59依次存儲到散列表中?！颈狈浇煌ù髮W(xué)2001】（1）元素59存放在散列表中的地址是（D）。A.8B?9C.10D.11（2）存放
7、元素59需要搜索的次數(shù)是（C〉。A.2B?3C?4D?514.將10個元素散列到100000個單元的哈希表中，則（C〉產(chǎn)生沖突?！颈本┼]電大學(xué)2001—、4（2分）】A.—定會B.—定不會C.仍可能會二、判斷題:1-在散列檢索中，“比較，，操作一般也是不可避免的。（J）【華南理工大學(xué)2001一、4分）】2.散列函數(shù)越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突概率小?（X）【南京理工大學(xué)1997二、5（2分〉】3?哈希函數(shù)的選取平方取中法最好。（X）【青島大學(xué)2000、7（1分）】【南京航空航天大學(xué)4.Hash表的平均查找長度與處理沖突的方法無關(guān)。（X〉1997—、9（1分
8、〉】5.順序查找法適用于存儲結(jié)構(gòu)為順序或鏈接存儲的線性表。（V〉【山東大學(xué)2001—、1（1分）】6.折半查找法的查找速度一定比順序查找法快。（X〉【山東大學(xué)2001一、8（1分）】7.對大小均為n的有序表和無序表分別進(jìn)行順序查找，在等概率查找的情況下,對于查找成功，它們的平均查找長度是相同的，而對于查找失敗，它們的平均查找長度是不同的。（V）8、在查找樹(二叉樹排序樹〉中插入一個新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。(X)【上海海運(yùn)學(xué)院1999一、8(1分〉】9、完全二叉樹肯定是平衡二叉樹。(X)【南京航空航天大學(xué)1996六、5(1分〉】10對一棵二叉排序樹按前序方法
9、遍歷得出的結(jié)點(diǎn)序列是從小
