數(shù)據(jù)結(jié)構(gòu)第8章 查找 答案

《數(shù)據(jù)結(jié)構(gòu)第8章 查找 答案》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第8章查找測(cè)試題及答案一、填空題1.在數(shù)據(jù)的存放無(wú)規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是順序查找（線性查找）。2.線性有序表（a1，a2，a3，…，a256)是從小到大排列的，對(duì)一個(gè)給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索8次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是7。3.假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為2；比較四次查找成功的結(jié)點(diǎn)數(shù)為8；平均查找長(zhǎng)度為3.7。解：顯然，平均查找長(zhǎng)度＝O（log2n

2、）<5次（25）。但具體是多少次，則不應(yīng)當(dāng)按照公式來(lái)計(jì)算（即（21×log221）/20＝4.6次并不正確！）。因?yàn)檫@是在假設(shè)n＝2m-1的情況下推導(dǎo)出來(lái)的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為＝（1＋2×2＋4×3＋8×4＋5×5）＝74；ASL＝74/20=3.7?。?！4．【計(jì)研題2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素28，6，12，20比較大小。5.在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是散列查找

3、。6.散列法存儲(chǔ)的基本思想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址。7.有一個(gè)表長(zhǎng)為m的散列表，初始狀態(tài)為空，現(xiàn)將n（n

4、20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中比較大小，查找結(jié)果是失敗。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50（C）3．對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較次關(guān)鍵字。A．3B．4C．5D．6（A）4.鏈表適用于查找A．順序B．二分法C．順序，也能二分法D．隨機(jī)（C）5.折半搜索與二叉搜索樹(shù)的時(shí)間性能A.相同B.完全不同C.有時(shí)不相同D.數(shù)量級(jí)都是O（log2n）6．從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切

5、的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。8要進(jìn)行線性查找，則線性表A；要進(jìn)行二分查找，則線性表B；要進(jìn)行散列查找，則線性表C。某順序存儲(chǔ)的表格，其中有90000個(gè)元素，已按關(guān)鍵項(xiàng)的值的上升順序排列?，F(xiàn)假定對(duì)各個(gè)元素進(jìn)行查找的概率是相同的，并且各個(gè)元素的關(guān)鍵項(xiàng)的值皆不相同。當(dāng)用順序查找法查找時(shí)，平均比較次數(shù)約為D，最大比較次數(shù)為E。供選擇的答案：A~C：①必須以順序方式存儲(chǔ)②必須以鏈表方式存儲(chǔ)③必須以散列方式存儲(chǔ)④既可以以順序方式，也可以以鏈表方式存儲(chǔ)⑤必須以順序方式存儲(chǔ)且數(shù)據(jù)元素已按值遞增或遞減的次序排好⑥必須以

6、鏈表方式存儲(chǔ)且數(shù)據(jù)元素已按值遞增或遞減的次序排好D，E：①25000②30000③45000④90000答案：A=④B=⑤C=③D＝③E＝④7.從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。鏈表是一種A，它對(duì)于數(shù)據(jù)元素的插入和刪除B。通常查找線性表數(shù)據(jù)元素的方法有C和D兩種方法，其中C是一種只適合于順序存儲(chǔ)結(jié)構(gòu)但E的方法；而D是一種對(duì)順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)均適用的方法。供選擇的答案：A：①順序存儲(chǔ)線性表②非順序存儲(chǔ)非線性表③順序存儲(chǔ)非線性

7、表④非順序存儲(chǔ)線性表B：①不需要移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針②不需要移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針③只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針④既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針C：①順序查找②循環(huán)查找③條件查找④二分法查找D：①順序查找②隨機(jī)查找③二分法查找④分塊查找E：①效率較低的線性查找②效率較低的非線性查找③效率較高的非線性查找④效率較高的線性查找答案：A＝④B＝②C＝④D＝①E＝③8.從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。在二叉排序樹(shù)中，每個(gè)結(jié)點(diǎn)的關(guān)鍵碼值A(chǔ)，B一棵二叉排序，

8、即可得到排序序列。同一個(gè)結(jié)點(diǎn)集合，可用不同的二叉排序樹(shù)表示，人們把平均檢索長(zhǎng)度最短的二叉排序樹(shù)稱作最佳二叉排序，最佳二叉排序樹(shù)在結(jié)構(gòu)上的特點(diǎn)是C。供選擇的答案A：①比左子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值大，比右子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值?、诒茸笞訕?shù)所有結(jié)點(diǎn)的關(guān)鍵碼值小，比右子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值大③比左右子樹(shù)的所有結(jié)點(diǎn)的關(guān)鍵碼值都大④與左子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值和右子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值無(wú)必然的大小關(guān)系