嚴(yán)魏敏-習(xí)題-查找-07-創(chuàng)新互聯(lián)

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

（1）對(duì)n個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長(zhǎng)度為（C）。D

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

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

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

（3）如果要求一個(gè)線(xiàn)性表既能較快的查找，又能適應(yīng)動(dò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個(gè)元素
第一次取(1+10)/2=5
與第五個(gè)元素20比較
58大于20
再取(6+10)/2=8
與第八個(gè)元素70比較
依次類(lèi)推再與30、50比較
最終查找失敗。

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

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

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

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

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

（7）分別以下列序列構(gòu)造二叉排序樹(shù)，與用其他三個(gè)序列所構(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）在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作（C）型調(diào)整以使其平衡。

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

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

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

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

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

（11）m階B-樹(shù)是一棵（B）。

A. m叉排序樹(shù)
B. m叉平衡排序樹(shù)
C. m?1叉平衡排序樹(shù)
D. m+1叉平衡排序樹(shù)

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

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

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

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

（14）設(shè)散列表長(zhǎng)為14，散列函數(shù)是H(key)=key%11，表中已有數(shù)據(jù)的關(guān)鍵字為15, 38, 61, 84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的元素加到表中，用二次探測(cè)法解決沖突，則放入的位置是（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，計(jì)算得到地址為5，沖突
用二次探測(cè)法解決沖突得到新地址為6，仍沖突，
再用用二次探測(cè)法解決沖突，得到新地址為4，仍沖突
再用用二次探測(cè)法解決沖突，得到新地址為9，不沖突，
即將關(guān)鍵字49放入位置9。

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

應(yīng)用題

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

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

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

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

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

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

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

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

算法設(shè)計(jì)題

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

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

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

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

廣告

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