查找(相關(guān)試題)數(shù)據(jù)結(jié)構(gòu)第九章

查找(相關(guān)試題)數(shù)據(jù)結(jié)構(gòu)第九章復(fù)習(xí)提要比較式基于樹的查找法基于線性表的查找法分塊（或索引順序表）查找法折半（或二分）查找法順序查找法對(duì)存儲(chǔ)結(jié)構(gòu)和關(guān)鍵字排列方式?jīng)]有特殊要求只適合順序存儲(chǔ)的有序表另建一個(gè)索引表，分塊有序，塊間可用折半查找，塊內(nèi)順序查找二叉排序樹平衡二叉樹（AVL）B-樹B+樹——哈希法/散列法/雜湊法在記錄存儲(chǔ)位置與關(guān)鍵字之間建立確定的關(guān)系——哈希函數(shù)左子樹上所有節(jié)點(diǎn)的值<根節(jié)點(diǎn)的值<右子樹上所有節(jié)點(diǎn)的值左、右子樹深度之差的絕對(duì)值不超過(guò)1的二叉排序樹一種平衡的多路查找樹，m叉樹B-樹的變型樹，關(guān)鍵字信息全部在葉子結(jié)點(diǎn)中，其它結(jié)點(diǎn)是其索引21.

某順序存儲(chǔ)的表格中有90000個(gè)元素，已按關(guān)鍵字值升序排列，假定對(duì)每個(gè)元素進(jìn)行查找的概率是相同的，且每個(gè)元素的關(guān)鍵字的值皆不相同。用順序查找法查找時(shí)，平均比較次數(shù)約為（）A．25000 B．30000 C．45000 D．9000032.

若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為()。A.(n-1)/2B.n/2C.(n+1)/2D.n42’.

對(duì)長(zhǎng)度為n的有序單鏈表，若查找每個(gè)元素的概率相等，則順序查找到表中任一元素的平均查找長(zhǎng)度為（）。A．n/2 B．（n+1）/2C．（n－1）/2 D．n/453.

下面關(guān)于二分查找的敘述正確的是()A.表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)B.表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型C.表必須有序，而且只能從小到大排列D.表必須有序，且表只能以順序方式存儲(chǔ)64.

有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下，查找成功所需的平均比較次數(shù)為（）A.37/12 B.35/12C.39/12 D.43/127先看一個(gè)具體的情況，假設(shè)：n=11分析折半查找的平均查找長(zhǎng)度639141025781112判定樹1223333444412485.

適用于折半查找的表的存儲(chǔ)方式及元素排列要求為()A．鏈接方式存儲(chǔ)，元素?zé)o序B．鏈接方式存儲(chǔ)，元素有序C．順序方式存儲(chǔ)，元素?zé)o序D．順序方式存儲(chǔ)，元素有序96.

有一個(gè)有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí),（）次比較后查找成功。A.1B.2C.4D.8107.

具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度（）A.3.1B.4C.2.5D.5118.當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為()A．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊C.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最小）的數(shù)據(jù)組成索引塊D.數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個(gè)數(shù)需相同129.分別以下列序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是()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，80，60，90，120，130，110)1310.

在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并已知A的左孩子的平衡因子為0右孩子的平衡因子為1,則應(yīng)作()型調(diào)整以使其平衡。A.LLB.LRC.RLD.RR14如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過(guò)程為平衡旋轉(zhuǎn)?，F(xiàn)分別介紹這四種平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：

LL平衡旋轉(zhuǎn)

RR平衡旋轉(zhuǎn)

LR平衡旋轉(zhuǎn)

RL平衡旋轉(zhuǎn)15若在A的左子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC若在A的右子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC1）LL平衡旋轉(zhuǎn)：16若在A的右子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC若在A的左子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：這種調(diào)整規(guī)則可以保證二叉排序樹的次序不變171．B-樹的定義B-樹是一種平衡的多路查找樹：18

在m階的B-樹，或?yàn)榭諛洌驗(yàn)闈M足下列特性的m叉樹：（1）樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹；（2）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；（3）除根之外的所有非終端結(jié)點(diǎn)至少有m/2棵子樹；（4）所有的非終端結(jié)點(diǎn)結(jié)構(gòu)如下：

（n,A0,K1,R1,A1,K2,R2,A2,………,Kn,Rn,An）多叉樹的特性19

其中，每個(gè)非終端結(jié)點(diǎn)含有：關(guān)鍵字個(gè)數(shù)n

n個(gè)關(guān)鍵字Ki（1≤i≤n）n<m

n個(gè)指向記錄的指針Ri（1≤i≤n）

n+1個(gè)指向子樹的指針Ai（0≤i≤n）;（5）所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶任何信息。多叉樹的特性2011.m階B-樹是一棵(B)A.m叉排序樹B.m叉平衡排序樹C.m-1叉平衡排序樹D.m+1叉平衡排序樹2112.散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計(jì)算轉(zhuǎn)化為記錄的存放地址，因?yàn)樯⒘泻瘮?shù)是一對(duì)一的關(guān)系，則選擇好的（D）方法是散列文件的關(guān)鍵。A.散列函數(shù)B.除余法中的質(zhì)數(shù)C.沖突處理D.散列函數(shù)和沖突處理

2213.

下面關(guān)于哈希(Hash，雜湊)查找的說(shuō)法正確的是(C)A．哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小B．除留余數(shù)法是所有哈希函數(shù)中最好的C．不存在特別好與壞的哈希函數(shù)，要視情況而定D．若需在哈希表中刪去一個(gè)元素，不管用何種方法解決沖突都只要簡(jiǎn)單的將該元素刪去即可2314.設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構(gòu)造散列表，散列函數(shù)為H（key）=keyMOD13,散列地址為1的鏈中有（D）個(gè)記錄。A．1B.2C.3D.4

2415.關(guān)于雜湊查找說(shuō)法不正確的有幾個(gè)(B)（1）采用鏈地址法解決沖突時(shí)，查找一個(gè)元素的時(shí)間是相同的（2）采用鏈地址法解決沖突時(shí)，若插入規(guī)定總是在鏈?zhǔn)祝瑒t插入任一個(gè)元素的時(shí)間是相同的（3）用鏈地址法解決沖突易引起聚集現(xiàn)象（4）再哈希法不易產(chǎn)生聚集A.1B.2C.3D.42516.設(shè)哈希表長(zhǎng)為14，哈希函數(shù)是H(key)=key%11,表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置是(D)A．8B．3C．5D．92617.假定有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次2718.散列表的地址區(qū)間為0-17,散列函數(shù)為H(K)=Kmod17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲(chǔ)到散列表中。（1）元素59存放在散列表中的地址是（D）。A．8B.9C.10D.11（2）存放元素59需要搜索的次數(shù)是（C）。A．2B.3C.4D.52819.已知一個(gè)線性表（3