數(shù)據(jù)結(jié)構(gòu) 第九章 查找 作業(yè)及答案

1、第九章 查找一、填空題1. 在數(shù)據(jù)的存放無(wú)規(guī)律而言的線(xiàn)性表中進(jìn)行檢索的最佳方法是 。2. 線(xiàn)性有序表（a1，a2，a3，a256)是從小到大排列的，對(duì)一個(gè)給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索 次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是 。3. 假設(shè)在有序線(xiàn)性表a1.20上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為 2 ；比較四次查找成功的結(jié)點(diǎn)數(shù)為 ,其下標(biāo)從小到大依次是 _，平均查找長(zhǎng)度為 。4折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素 比較

2、大小。5. 在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是 。6. 散列法存儲(chǔ)的基本思想是由 決定數(shù)據(jù)的存儲(chǔ)地址。7. 有一個(gè)表長(zhǎng)為m的散列表，初始狀態(tài)為空，現(xiàn)將n（n<m）個(gè)不同的關(guān)鍵碼插入到散列表中，解決沖突的方法是用線(xiàn)性探測(cè)法。如果這n個(gè)關(guān)鍵碼的散列地址都相同，則探測(cè)的總次數(shù)是 。(而任一元素查找次數(shù) n-1)8、設(shè)一哈希表表長(zhǎng)M為100 ，用除留余數(shù)法構(gòu)造哈希函數(shù)，即H（K）=K MOD P（P<=M）, 為使函數(shù)具有較好性能，P應(yīng)選 。 9、在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)的是 。10、對(duì)線(xiàn)性表進(jìn)行二分查找時(shí)，要求線(xiàn)性表必須以 方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)

3、鍵字 排列。11 在分塊查找方法中，首先查找索引，然后再查找相應(yīng)的 。12 順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為_(kāi)   _次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為_(kāi)   。13在有序表A1.12中，采用二分查找算法查等于A(yíng)12的元素，所比較的元素下標(biāo)依次為 。14. 在有序表A1.20中，按二分查找方法進(jìn)行查找，查找長(zhǎng)度為5的元素個(gè)數(shù)是_  _。15. 已知二叉排序樹(shù)的左右子樹(shù)均不為空，則_ _上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)值， 上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。16、中序遍歷二叉排序樹(shù)得到的序列是 序列

4、（填有序或無(wú)序）。17、從有序表(10，16，25，40，61，28，80，93)中依次二分查找40和61元素時(shí)，其查找長(zhǎng)度分別為 和 ·二、單項(xiàng)選擇題1在表長(zhǎng)為的鏈表中進(jìn)行順序查找，它的平均查找長(zhǎng)度為（ ）. ; . （）; . ; . （）2折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中（ ）比較大小，查找結(jié)果是失敗。A20，70，30，50 B30，88，70，50 C20，50 D30，88，503對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較（ ）次關(guān)鍵字。A3 B4 C5 D 64. 鏈表適用于

5、（ ）查找A順序 B二分法 C順序，也能二分法 D隨機(jī)5. 折半搜索與二叉搜索樹(shù)的時(shí)間性能（ ）。 A. 相同 B. 完全不同 C. 有時(shí)不相同 D. 數(shù)量級(jí)都是O（log2n）6散列表的地址區(qū)間為0-17,散列函數(shù)為H(K)=K mod 17。采用線(xiàn)性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲(chǔ)到散列表中。元素59存放在散列表中的地址是（ ）。A 8 B. 9 C. 10 D. 117. 當(dāng)采用分快查找時(shí)，數(shù)據(jù)的組織方式為 ( ) 。A數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊C.

6、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊D. 數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個(gè)數(shù)需相同8. 散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以( )取其值域的每個(gè)值。A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率9. 假定有k個(gè)關(guān)鍵字互為同義詞，若用線(xiàn)性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測(cè)？( ) Ak-1次 B. k次 C. k+1次 D. k（k+1）/2次10、 哈希查找中k個(gè)關(guān)鍵字具有同一哈希值，若用線(xiàn)性探測(cè)法將這k個(gè)關(guān)鍵字對(duì)應(yīng)的記錄存入哈希表中，至少要進(jìn)行( )次探測(cè)。A k B. k+1 C. k(k+1)/2 D.1

7、+k(k+1)/211、在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并已知A的左孩子的平衡因子為0右孩子的平衡因子為1,則應(yīng)作( ) 型調(diào)整以使其平衡。A. LL B. LR C. RL D. RR12、二叉查找樹(shù)的查找效率與二叉樹(shù)的( )有關(guān), 在 ( ）)時(shí)其查找效率最低 (1): A. 高度 B. 結(jié)點(diǎn)的多少 C. 樹(shù)型 D. 結(jié)點(diǎn)的位置 (2): A. 結(jié)點(diǎn)太多 B. 完全二叉樹(shù) C. 呈單枝樹(shù) D. 結(jié)點(diǎn)太復(fù)雜。13、順序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半查找算法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比

8、較次數(shù)為（ ） A) 2 B) 3 C) 4 D) 514、對(duì)包含n個(gè)元素的哈希表進(jìn)行查找，平均查找長(zhǎng)度為（ ）A) O(log2n) B) O(n) C) O(nlog2n) D) 不直接依賴(lài)于n15、若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為( )。 A (n-1)/2 B. n/2 C. (n+1)/2 D. n16. 下面關(guān)于二分查找的敘述正確的是 ( ) A. 表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ) C. 表必須有序，而且只能從小到大排列B. 表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型 D. 表必須有序，

9、且表只能以順序方式存儲(chǔ)17. 對(duì)線(xiàn)性表進(jìn)行二分查找時(shí)，要求線(xiàn)性表必須（ ）A.以順序方式存儲(chǔ) B.以順序方式存儲(chǔ),且數(shù)據(jù)元素有序 C.以鏈接方式存儲(chǔ) D.以鏈接方式存儲(chǔ),且數(shù)據(jù)元素有序18適用于折半查找的表的存儲(chǔ)方式及元素排列要求為( ) A鏈接方式存儲(chǔ)，元素?zé)o序 B鏈接方式存儲(chǔ)，元素有序C順序方式存儲(chǔ)，元素?zé)o序 D順序方式存儲(chǔ)，元素有序19. 用二分（對(duì)半）查找表的元素的速度比用順序法( ) A 必然快 B. 必然慢 C. 相等 D. 不能確定20當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度( ) A必定快 B.不一定 C. 在大部分情況下

10、要快 D. 取決于表遞增還是遞減21. 具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度（ ） A. 3.1 B. 4 C. 2.5 D. 522. 折半查找的時(shí)間復(fù)雜性為（ ）A. O（n2） B. O（n） C. O（nlogn） D. O（logn）23設(shè)順序線(xiàn)性表的長(zhǎng)度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長(zhǎng)度為（ D ）。(A) 6(B) 11(C) 5(D) 6.524. 二叉排序樹(shù)的查找效率與二叉樹(shù)的( )有關(guān)。 A. 高度 B. 結(jié)點(diǎn)的多少 C. 樹(shù)型 D. 結(jié)點(diǎn)的位置25在等概率情況下,一棵平衡樹(shù)的ASL為 ( )。A. O(1) B. O( log2

11、n ) C. O(log2n)2) D.O(nlog2n) 26分別以下列序列構(gòu)造二叉排序樹(shù)，與用其它三個(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)27. 在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并已知A的左孩子的平衡因子為0右孩子的平衡因子為1,則應(yīng)作( ) 型調(diào)整以使其平衡。A. LL B. LR C. RL D. RR28、下

12、列二叉排序樹(shù)中，滿(mǎn)足平衡二叉樹(shù)定義的是（ ）。C、D、B、A、  29下列關(guān)于m階B-樹(shù)的說(shuō)法錯(cuò)誤的是( )。 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ù)是有序的30. 下面關(guān)于m階B樹(shù)說(shuō)法正確的是( ) 每個(gè)結(jié)點(diǎn)至少有兩棵非空子樹(shù)； 樹(shù)中每個(gè)結(jié)點(diǎn)至多有m一1個(gè)關(guān)鍵字; 所有葉子在同一層上; 當(dāng)插入一個(gè)數(shù)據(jù)項(xiàng)引起B(yǎng)樹(shù)結(jié)點(diǎn)分裂后，樹(shù)長(zhǎng)高一層。A B. C. D. 31. 下面關(guān)于B和B+樹(shù)的敘述中，不正確的是( ) A. B樹(shù)和B+樹(shù)都是平衡的多叉樹(shù)。 B. B樹(shù)和B+樹(shù)都可用于

13、文件的索引結(jié)構(gòu)。C. B樹(shù)和B+樹(shù)都能有效地支持順序檢索。 D. B樹(shù)和B+樹(shù)都能有效地支持隨機(jī)檢索。32、下列敘述中，不符合m階B樹(shù)定義要求的是（ ） A根節(jié)點(diǎn)最多有m棵子樹(shù)    B.所有葉結(jié)點(diǎn)都在同一層上   C各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列 D.葉結(jié)點(diǎn)之間通過(guò)指針鏈接  33、設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)= key % p，則p最好選擇（ ）。(A) 小于等于m的最大奇數(shù)(B) 小于等于m的最大素?cái)?shù)(C) 小于等于m的最大偶數(shù)(D) 小于等于m的最大合數(shù)34、

14、適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（ ）。A有序表 B分塊有序表 C二叉排序樹(shù) D線(xiàn)性鏈表三、判斷題1、查找相同結(jié)點(diǎn)的效率折半查找總比順序查找高。( )2、索引順序表的特點(diǎn)是塊內(nèi)可無(wú)序，塊間要有序。（ ）3、 在采用線(xiàn)性探測(cè)法處理沖突的散列表中，所有同義詞在表中一定相鄰。( )4、在平衡二叉樹(shù)中，任意結(jié)點(diǎn)左右子樹(shù)的高度差（絕對(duì)值）不超過(guò)1。( )5、若查找表的長(zhǎng)度為n，則順序查找法的平均查找長(zhǎng)度為（n+1）/2。（ ）6、折半搜索適用于有序表，包括有序的順序表和有序的鏈表。( )7采用線(xiàn)性探測(cè)法處理散列時(shí)的沖突，當(dāng)從哈希表刪除一個(gè)記錄時(shí)，不應(yīng)將這個(gè)記錄的所在位置置空，因?yàn)檫@會(huì)

15、影響以后的查找。（ ）8在散列檢索中，“比較”操作一般也是不可避免的。（ ）9在m階B-樹(shù)中每個(gè)結(jié)點(diǎn)上至少有 個(gè)關(guān)鍵字，最多有m個(gè)關(guān)鍵字。( )10負(fù)載因子 (裝填因子)是散列表的一個(gè)重要參數(shù)，它反映散列表的裝滿(mǎn)程度。（ ）11. 散列法的平均查找長(zhǎng)度不隨表中結(jié)點(diǎn)數(shù)目的增加而增加，隨負(fù)載因子的增大而增大。（ ）12. 哈希表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指針。 ( )13. 若散列表的負(fù)載因子<1，則可避免沖突的產(chǎn)生。( )14用向量和單鏈表表示的有序表均可使用折半查找方法來(lái)提高查找速度。( )15. 在平衡二叉樹(shù)中，向某個(gè)平衡因子不為零的結(jié)點(diǎn)的子樹(shù)中插入一新結(jié)點(diǎn)，一定會(huì)引

16、起平衡旋轉(zhuǎn)。( )16. 二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。（ ）17. 就平均查找長(zhǎng)度而言，分塊查找最小，折半查找次之，順序查找最大。( )18對(duì)大小均為n的有序表和無(wú)序表分別進(jìn)行順序查找，在等概率查找的情況下，對(duì)于查找成功，它們的平均查找長(zhǎng)度是相同的，而對(duì)于查找失敗，它們的平均查找長(zhǎng)度是不同的。（ ）19任一查找樹(shù)(二叉分類(lèi)樹(shù))的平均查找時(shí)間都小于用順序查找法查找同樣結(jié)點(diǎn)的線(xiàn)性表的平均查找時(shí)間。 ( )20、在二叉樹(shù)排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。( )21、順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈接存儲(chǔ)的線(xiàn)性表。（ ）四、簡(jiǎn)答題

17、1.對(duì)分（折半）查找適不適合鏈表結(jié)構(gòu)的序列，為什么？用二分查找的查找速度必然比線(xiàn)性查找的速度快，這種說(shuō)法對(duì)嗎？2.假定對(duì)有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問(wèn)題：（1） 畫(huà)出描述折半查找過(guò)程的判定樹(shù)；（2） 若查找元素54，需依次與哪些元素比較？（3） 若查找元素90，需依次與哪些元素比較？（4） 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。3.設(shè)哈希（Hash）表的地址范圍為017，哈希函數(shù)為：H（K）K MOD 16。K為關(guān)鍵字，用線(xiàn)性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字序列： （10，24，32，17，31，30，4

18、6，47，40，63，49）造出Hash表，試回答下列問(wèn)題：（1） 畫(huà)出哈希表的示意圖；（2） 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？（3） 若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？（4） 假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。4、設(shè)哈希表長(zhǎng)度為11，哈希函數(shù)H（K）=（K的第一字母在字母表中的序號(hào)）MOD11，若輸入順序?yàn)椋―，BA，TN，M，CI，I，K，X，TA），處理沖突方法為線(xiàn)性探測(cè)再散列或鏈地址法，要求構(gòu)造哈希表，并求出等概率情況下查找成功平均查找長(zhǎng)度。5、輸入一個(gè)正整數(shù)序列100，50，302，450，66，200，30，260，建立一棵二叉排序樹(shù)，要求： 畫(huà)出該二叉排序樹(shù)； 畫(huà)出刪除結(jié)點(diǎn)302后的二叉排序樹(shù)。6、 設(shè)有一組關(guān)鍵字：19，01，23，14，55，20，84，27，68，采用哈希函數(shù)：H（key）=key mod 7，采用開(kāi)放地址法的線(xiàn)性探測(cè)再散列方法解決沖突。要求：在011的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表。7、已知如下所示長(zhǎng)度為12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）(1) 試按表中元素的順序依次插入一棵初始為空的二叉排序樹(shù)，畫(huà)出插入完成之后的