集合(散列搜索樹折半)習(xí)題

《集合(散列搜索樹折半)習(xí)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、一、選擇題：1、對(duì)N個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長(zhǎng)度為(A)【南京理工大學(xué)1998—、7(2分)】A.(N+1)/2C.NB.N/2D.

2、(l+N)*N]/22、下面關(guān)于二分查找的敘述正確的是)【南京理工大學(xué)A.表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)C.表必須有序，而且只能從小到大排列B.表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型D.表必須有序，且表只能以順序方式存儲(chǔ)【南京理工大學(xué)3、適用于折半查找的表的存儲(chǔ)方式及元素排列要求為(D1997—、6(2分〉】元素?zé)o序匹素有序元素?zé)o序元素有序A.鏈接方式存儲(chǔ),B.鏈接方式

3、存儲(chǔ),C.順序方式存儲(chǔ),D.順序方式存儲(chǔ),4、當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度(C)A.必定快B.不一定C.在大部分情況下要快D.取決于表遞增還是遞減【南京理工大學(xué)〈2分〉】5、具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度(A〉【中山大學(xué)1998二、10(2分〉】A.3.1B.4C.2.5D.56、折半查找的時(shí)間復(fù)雜性為(D〉【中山大學(xué)1999-x15]A.O(n2)B.O(n)C.O(nlogn)D.O(logn)7、散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以(D)取其值域的每個(gè)值。A.最大概率

4、B.最小概率C.平均概率D.同等概率8、二叉查找樹的查找效率與二叉樹的（（1）C）有關(guān)，在（（2）C）時(shí)其查找效率最低【武漢交通科技大學(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è)序列所構(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.若需在哈希表中刪去一個(gè)元素，不管用何種方法解決沖突都只要簡(jiǎn)單的將該元素刪去即可11、設(shè)哈希表長(zhǎng)為14,哈希函數(shù)是H（key）=key%ll,表中已有數(shù)據(jù)的關(guān)鍵字為15,38,61,8個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置是（D）【南京理工大學(xué)20

6、01一、15（1?5分）】A.8B?3C?5二次探測(cè)：h2i.i(x)=(h(x)4-i2)%B;h2i+i(x)=(h(x)-i2)%B;12、假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測(cè)？（D）A.k-1次B.k次C.k+1次D.k（k+1〉/2次13、散列表的地址區(qū)間為0?17,散列函數(shù)為H（K）=Kmod17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26,25,72,38,8,18,59依次存儲(chǔ)到散列表中。【北方交通大學(xué)2001】（1）元素59存放在散列表中的地址是（D）。A.8B?9C.10D.11（2）存放

7、元素59需要搜索的次數(shù)是（C〉。A.2B?3C?4D?514.將10個(gè)元素散列到100000個(gè)單元的哈希表中，則（C〉產(chǎn)生沖突?！颈本┼]電大學(xué)2001—、4（2分）】A.—定會(huì)B.—定不會(huì)C.仍可能會(huì)二、判斷題: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表的平均查找長(zhǎng)度與處理沖突的方法無關(guān)。（X〉1997—、9（1分

8、〉】5.順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈接存儲(chǔ)的線性表。（V〉【山東大學(xué)2001—、1（1分）】6.折半查找法的查找速度一定比順序查找法快。（X〉【山東大學(xué)2001一、8（1分）】7.對(duì)大小均為n的有序表和無序表分別進(jìn)行順序查找，在等概率查找的情況下,對(duì)于查找成功，它們的平均查找長(zhǎng)度是相同的，而對(duì)于查找失敗，它們的平均查找長(zhǎng)度是不同的。（V）8、在查找樹(二叉樹排序樹〉中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。(X)【上海海運(yùn)學(xué)院1999一、8(1分〉】9、完全二叉樹肯定是平衡二叉樹。(X)【南京航空航天大學(xué)1996六、5(1分〉】10對(duì)一棵二叉排序樹按前序方法

9、遍歷得出的結(jié)點(diǎn)序列是從小