嚴魏敏習(xí)題 1．選擇題

（1）對n個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為（C）。D

堅守“ 做人真誠 · 做事靠譜 · 口碑至上 · 高效敬業(yè) ”的價值觀，專業(yè)網(wǎng)站建設(shè)服務(wù)10余年為成都成都葡萄架小微創(chuàng)業(yè)公司專業(yè)提供企業(yè)網(wǎng)站制作營銷網(wǎng)站建設(shè)商城網(wǎng)站建設(shè)手機網(wǎng)站建設(shè)小程序網(wǎng)站建設(shè)網(wǎng)站改版，從內(nèi)容策劃、視覺設(shè)計、底層架構(gòu)、網(wǎng)頁布局、功能開發(fā)迭代于一體的高端網(wǎng)站建設(shè)服務(wù)。

總查找次數(shù)：N=1+2+3+…+n=n(n+1)/2
則平均查找長度為：N/n=(n+1)/2

（2）適用于折半查找的表的存儲方式，以及元素排列要求為（ D ）。
A. 鏈接方式存儲，元素?zé)o序
B. 鏈接方式存儲，元素有序
C. 順序方式存儲，元素?zé)o序
D. 順序方式存儲，元素有序

（3）如果要求一個線性表既能較快的查找，又能適應(yīng)動態(tài)變化的要求，最好采用( C )查找法。D

A. 順序查找
B. 折半查找
C. 分塊查找
D. 哈希查找

（4）折半查找有序表（4, 6, 10, 12, 20, 30, 50, 70, 88, 100）。若查找表中元素58，則它將依次與表中（A）比較大小，查找結(jié)果是失敗。C

A. 20，70，30，50
B. 30，88，70，50
C. 20，50
D. 30，88，50

表中共10個元素
第一次取(1+10)/2=5
與第五個元素20比較
58大于20
再取(6+10)/2=8
與第八個元素70比較
依次類推再與30、50比較
最終查找失敗。

（5）對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較（B）次關(guān)鍵字。C

A. 3
B. 4
C. 5
D. 6

22個記錄的有序表
其折半查找的判定樹深度為 ?log222? + 1=5
且該判定樹不是滿二叉樹，即查找失敗時至多比較5次，至少比較4次。`

（6）折半查找與二叉排序樹的時間性能（C）。A

A. 相同
B. 完全不同
C. 有時不相同
D. 數(shù)量級都是O(log2n)

（7）分別以下列序列構(gòu)造二叉排序樹，與用其他三個序列所構(gòu)造的結(jié)果不同的是（ C ）。

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)

（8）在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作（C）型調(diào)整以使其平衡。

A. LL
B. LR
C. RL
D. RR

（9）下列關(guān)于m階B-樹的說法錯誤的是（D）。

A. 根結(jié)點至多有m棵子樹
B. 所有葉子都在同一層次上
C. 非葉結(jié)點至少有m/2（m為偶數(shù)）或m/2+1（m為奇數(shù)）棵子樹
D. 根結(jié)點中的數(shù)據(jù)是有序的

（10）下面關(guān)于B-和B+樹的敘述中，不正確的是（C）。

A. B-樹和B+樹都是平衡的多叉樹
B. B-樹和B+樹都可用于文件的索引結(jié)構(gòu)
C. B-樹和B+樹都能有效地支持順序檢索
D. B-樹和B+樹都能有效地支持隨機檢索

（11）m階B-樹是一棵（B）。

A. m叉排序樹
B. m叉平衡排序樹
C. m?1叉平衡排序樹
D. m+1叉平衡排序樹

（12）下面關(guān)于散列查找的說法，正確的是（C ）。

A. 散列函數(shù)構(gòu)造的越復(fù)雜越好，因為這樣隨機性好，沖突小
B. 除留余數(shù)法是所有散列函數(shù)中最好的
C. 不存在特別好與壞的散列函數(shù)，要視情況而定
D. 散列表的平均查找長度有時也和記錄總數(shù)有關(guān)

（13）下面關(guān)于散列查找的說法，不正確的是（A ）。C

A. 采用鏈地址法處理沖突時，查找任何一個元素的時間都相同
B. 采用鏈地址法處理沖突時，若插入規(guī)定總是在鏈首，則插入任一個元素的時間是相同的
C. 用鏈地址法處理沖突，不會引起二次聚集現(xiàn)象
D. 用鏈地址法處理沖突，適合表長不確定的情況

（14）設(shè)散列表長為14，散列函數(shù)是H(key)=key%11，表中已有數(shù)據(jù)的關(guān)鍵字為15, 38, 61, 84共四個，現(xiàn)要將關(guān)鍵字為49的元素加到表中，用二次探測法解決沖突，則放入的位置是（D）。C

A. 3
B. 5
C. 8
D. 9

關(guān)鍵字15放入位置4，關(guān)鍵字38放入位置5，
關(guān)鍵字61放入位置6，關(guān)鍵字84放入位置7，
再添加關(guān)鍵字49，計算得到地址為5，沖突
用二次探測法解決沖突得到新地址為6，仍沖突，
再用用二次探測法解決沖突，得到新地址為4，仍沖突
再用用二次探測法解決沖突，得到新地址為9，不沖突，
即將關(guān)鍵字49放入位置9。

（15）采用線性探測法處理沖突，可能要探測多個位置，在查找成功的情況下，所探測的這些位置上的關(guān)鍵字（ A）。
A. 不一定都是同義詞
B. 一定都是同義詞
C. 一定都不是同義詞
D. 都相同

應(yīng)用題

（1）假定對有序表：（3, 4, 5, 7, 24, 30, 42, 54,63, 72, 87, 95）進行折半查找，試回答下列問題。① 畫出描述折半查找過程的判定樹。② 若查找元素54，需依次與哪些元素比較？③ 若查找元素90，需依次與哪些元素比較？④ 假定每個元素的查找概率相等，求查找成功時的平均查找長度。

（2）在一棵空的二叉排序樹中依次插入關(guān)鍵字序列為12, 7, 17, 11, 16, 2, 13, 9, 21, 4，請畫出所得到的二叉排序樹。

（3）已知如下所示長度為12的表：（Jan, Feb,Mar, Apr, May, June, July, Aug, Sep, Oct, Nov,Dec）。
① 試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。
② 若對表中元素先進行排序構(gòu)成有序表，求在等概率的情況下對此有序表進行折半查找時查找成功的平均查找長度。
③ 按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。

（4）對圖7.31所示的3階B-樹，依次執(zhí)行下列操作，畫出各步操作的結(jié)果。

① 插入90② 插入25③ 插入45④ 刪除60

（5）設(shè)散列表的地址范圍為0～17，散列函數(shù)為：H(key)=key%16。用線性探測法處理沖突，輸入關(guān)鍵字序列：（10, 24, 32, 17, 31, 30, 46, 47, 40, 63,49），構(gòu)造散列表，試回答下列問題：① 畫出散列表的示意圖。② 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進行比較？③ 若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字進行比較？④ 假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。

（6）設(shè)有一組關(guān)鍵字（9, 1, 23, 14, 55, 20, 84,27），采用散列函數(shù)：H(key)=key%7，表長為10，用開放地址法的二次探測法處理沖突。要求：對該關(guān)鍵字序列構(gòu)造散列表，并計算查找成功的平均查找長度。

（7）設(shè)散列函數(shù)H(K)=3 K % 11，散列地址空間為0～10，對關(guān)鍵字序列（32, 13, 49, 24, 38, 21, 4,12），按下述兩種解決沖突的方法構(gòu)造散列表，并分別求出等概率下查找成功時和查找失敗時的平均查找長度ASLsucc和ASLunsucc。
① 線性探測法。② 鏈地址法。

算法設(shè)計題

（1）試寫出折半查找的遞歸算法。
（2）試寫一個判別給定二叉樹是否為二叉排序樹的算法。
（3）已知二叉排序樹采用二叉鏈表存儲結(jié)構(gòu)，根結(jié)點的指針為T，鏈結(jié)點的結(jié)構(gòu)為（lchild, data,rchild），其中l(wèi)child、rchild分別指向該結(jié)點左、右孩子的指針，data域存放結(jié)點的數(shù)據(jù)信息。請寫出遞歸算法，從小到大輸出二叉排序樹中所有數(shù)據(jù)值≥x的結(jié)點的數(shù)據(jù)。要求先找到第一個滿足條件的結(jié)點后，再依次輸出其他滿足條件的結(jié)點。
（4）已知二叉樹T的結(jié)點形式為(llink, data, count,rlink)，在樹中查找值為X的結(jié)點，若找到，則記數(shù)（count）加1；否則，作為一個新結(jié)點插入樹中，插入后仍為二叉排序樹，寫出其非遞歸算法。
（5）假設(shè)一棵平衡二叉樹的每個結(jié)點都標明了平衡因子b，試設(shè)計一個算法，求平衡二叉樹的高度。
（6）分別寫出在散列表中插入和刪除關(guān)鍵字為K的一個記錄的算法，設(shè)散列函數(shù)為H，解決沖突的方法為鏈地址法。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：嚴魏敏-習(xí)題-查找-07-創(chuàng)新互聯(lián)
鏈接地址：http://vcdvsql.cn/article8/eisop.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計公司、域名注冊、網(wǎng)站設(shè)計、ChatGPT、外貿(mào)建站、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)