T8查找練習(xí)課件

1、practicepractice1 下面關(guān)于二分查找的敘述，正確的是下面關(guān)于二分查找的敘述，正確的是( )。 a表必須有序，表可以順序方式存儲(chǔ)，也表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)可以鏈表方式存儲(chǔ) b表必須有序且表中數(shù)據(jù)必須是整型、實(shí)表必須有序且表中數(shù)據(jù)必須是整型、實(shí)型或字符型型或字符型 c表必須有序，而且只能從上到大排列表必須有序，而且只能從上到大排列 d表必須有序，而且只能以順序方式存儲(chǔ)表必須有序，而且只能以順序方式存儲(chǔ) d2 有一組元素為有一組元素為11,11,2, 33, 21, 34,10, 422, 33, 21, 34,10, 42， 已知哈希表大小為，已知哈希表

2、大小為， 散列函數(shù)散列函數(shù)hfhf（x x）x x1010， 沖突時(shí)采用線(xiàn)性探查法查找沖突時(shí)采用線(xiàn)性探查法查找“下一個(gè)下一個(gè)”位置，位置， 則元素的桶地址（）則元素的桶地址（） a a b b c c d d d3 當(dāng)采用索引表有序查找時(shí)，數(shù)據(jù)的組織方式當(dāng)采用索引表有序查找時(shí)，數(shù)據(jù)的組織方式為為( ) a數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序 b數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大但塊間必須有序，每塊內(nèi)最大(或最小或最小)的數(shù)的數(shù)據(jù)組成索引塊據(jù)組成索引塊 c數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每數(shù)據(jù)分成若干塊，每塊

3、內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大塊內(nèi)最大(或最小或最小)的數(shù)據(jù)組成索引塊的數(shù)據(jù)組成索引塊 d數(shù)據(jù)分成若干塊，每塊數(shù)據(jù)分成若干塊，每塊(除最后一塊除最后一塊)中中數(shù)據(jù)個(gè)數(shù)需相同數(shù)據(jù)個(gè)數(shù)需相同 b4 假定對(duì)線(xiàn)性表假定對(duì)線(xiàn)性表(38,25,74,52,48)進(jìn)行哈希存儲(chǔ)，進(jìn)行哈希存儲(chǔ)，采用采用h(k)=k % 7作為哈希函數(shù)，采用線(xiàn)性探作為哈希函數(shù)，采用線(xiàn)性探測(cè)法處理沖突，則在建立哈希表的過(guò)程中，測(cè)法處理沖突，則在建立哈希表的過(guò)程中，將會(huì)碰到將會(huì)碰到( )次存儲(chǔ)沖突。次存儲(chǔ)沖突。 a4 b5 c6 d7 b5 從一棵二叉排序樹(shù)中查找一個(gè)元素時(shí)，若元從一棵二叉排序樹(shù)中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則

4、表明找到該元素，素的值等于根結(jié)點(diǎn)的值，則表明找到該元素，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向( )查查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向( )查找。查找。 a左子樹(shù)，左子樹(shù)左子樹(shù)，左子樹(shù) b左子樹(shù)，右子樹(shù)左子樹(shù)，右子樹(shù) c右子樹(shù)，左子樹(shù)右子樹(shù)，左子樹(shù) d右子樹(shù)，右子樹(shù)右子樹(shù)，右子樹(shù) b6 單若根據(jù)查找表建立長(zhǎng)度為單若根據(jù)查找表建立長(zhǎng)度為m的哈希表，采的哈希表，采用線(xiàn)性探測(cè)法處理沖突，假定對(duì)一個(gè)元素第用線(xiàn)性探測(cè)法處理沖突，假定對(duì)一個(gè)元素第一次計(jì)算的哈希地址為一次計(jì)算的哈希地址為d，則下一次的哈希地，則下一次的哈希地址為址為

5、( ) ad bd+1 c(d+1)/m d(d+1)%m d7 在長(zhǎng)度為在長(zhǎng)度為100的順序表的順序表r0100中，中，r0作作為監(jiān)視哨，那么查找失敗時(shí)，需進(jìn)行為監(jiān)視哨，那么查找失敗時(shí)，需進(jìn)行( )次關(guān)次關(guān)鍵字比較。鍵字比較。 a99 b100 c101 d以上答案都錯(cuò)啦以上答案都錯(cuò)啦 c8 對(duì)一棵二叉排序樹(shù)進(jìn)行對(duì)一棵二叉排序樹(shù)進(jìn)行( )時(shí)，得到的結(jié)點(diǎn)序時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)有序序列。列是一個(gè)有序序列。 a前序遍歷前序遍歷 b中序遍歷中序遍歷 c后序遍歷后序遍歷 d層序遍歷層序遍歷 b9 *有一組元素為有一組元素為 11,2, 33, 21, 23，存放于一個(gè)，存放于一個(gè)大小為的哈希表中，

6、散列函數(shù)大小為的哈希表中，散列函數(shù)hf（x）x10;沖突時(shí)采用線(xiàn)性探查法查找沖突時(shí)采用線(xiàn)性探查法查找“下一個(gè)下一個(gè)”位置，位置， 則查找各個(gè)數(shù)平均查找長(zhǎng)度為（則查找各個(gè)數(shù)平均查找長(zhǎng)度為（） a（）（） b（）（） c（）（） c10 若采用鏈地址法處理沖突，則哈希表是將若采用鏈地址法處理沖突，則哈希表是將( )和和( )組組合在一起的數(shù)據(jù)結(jié)構(gòu)合在一起的數(shù)據(jù)結(jié)構(gòu) a數(shù)組和表數(shù)組和表 b數(shù)組和堆棧數(shù)組和堆棧 c表和隊(duì)列表和隊(duì)列 d堆棧和隊(duì)列堆棧和隊(duì)列 a11 在一棵高度為在一棵高度為h的具有的具有n個(gè)元素的二叉搜索樹(shù)個(gè)元素的二叉搜索樹(shù)中，搜索所有元素的搜索長(zhǎng)度中最大的為中，搜索所有元素的搜索長(zhǎng)度中

7、最大的為（ ）。）。 an blog2n(以以2為底為底) c(h+1)/2 dh+1 d12 對(duì)元素對(duì)元素(18,25,63,50,42,32,90)進(jìn)行哈希存儲(chǔ)時(shí)，進(jìn)行哈希存儲(chǔ)時(shí)，若選用若選用h(k)=k % 9作為哈希函數(shù)，則哈希地作為哈希函數(shù)，則哈希地址為址為0的元素有的元素有( )個(gè)個(gè) a2 b3 c4 d5 b13 假設(shè)對(duì)長(zhǎng)度為假設(shè)對(duì)長(zhǎng)度為n=50的有序表進(jìn)行二分查找，的有序表進(jìn)行二分查找，則對(duì)應(yīng)的判斷樹(shù)高度和最后一層的結(jié)點(diǎn)數(shù)分則對(duì)應(yīng)的判斷樹(shù)高度和最后一層的結(jié)點(diǎn)數(shù)分別為別為( )。 a8， 13 b6， 13 c8， 19 d6， 19 d14 散列法的主要問(wèn)題在于散列法的主要問(wèn)題

8、在于( )。 a散列函數(shù)難以計(jì)算散列函數(shù)難以計(jì)算 b散列表的存取速度慢散列表的存取速度慢 c會(huì)發(fā)生沖突會(huì)發(fā)生沖突 d散列表占很多內(nèi)存散列表占很多內(nèi)存 c15 對(duì)于一個(gè)大小為對(duì)于一個(gè)大小為m含有含有n項(xiàng)的散列表，它的裝項(xiàng)的散列表，它的裝填因子為填因子為( )。 am-n bm+n cm/n dn/m d16 二叉搜索樹(shù)重新平衡算法中常用的工具為二叉搜索樹(shù)重新平衡算法中常用的工具為( ) a結(jié)點(diǎn)的旋轉(zhuǎn)變換結(jié)點(diǎn)的旋轉(zhuǎn)變換 b將結(jié)點(diǎn)插入到堆棧中將結(jié)點(diǎn)插入到堆棧中 c將結(jié)點(diǎn)插入到隊(duì)列中將結(jié)點(diǎn)插入到隊(duì)列中 d散列技術(shù)散列技術(shù) a17 順序查找方法適合于存儲(chǔ)結(jié)構(gòu)為順序查找方法適合于存儲(chǔ)結(jié)構(gòu)為( )的線(xiàn)性的線(xiàn)

9、性表。表。 a順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) b散列存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu) c索引存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu) d壓縮存儲(chǔ)結(jié)構(gòu)壓縮存儲(chǔ)結(jié)構(gòu) a18 若每個(gè)記錄的查找概率相等，則在有若每個(gè)記錄的查找概率相等，則在有n個(gè)數(shù)據(jù)個(gè)數(shù)據(jù)的序列中采用順序查找方法，平均查找長(zhǎng)度的序列中采用順序查找方法，平均查找長(zhǎng)度asl=( )。 an bn/2 c(n-1)/2 d(n+1)/2 d19 從具有從具有n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的avl樹(shù)中搜索一個(gè)元素時(shí)，樹(shù)中搜索一個(gè)元素時(shí)，在等概率情況下進(jìn)行成功搜索的時(shí)間復(fù)雜度在等概率情況下進(jìn)行成功搜索的時(shí)間復(fù)雜度大致為（大致為（ ）。）。 ao(n) bo(1) co

10、(log2n)（以（以2為底）為底） do(n2) c20 散列查找時(shí)，解決沖突的方法有散列查找時(shí)，解決沖突的方法有( )。 a除留余數(shù)法除留余數(shù)法 b數(shù)字分析法數(shù)字分析法 c直接地址法直接地址法 d鏈地址法鏈地址法 d21 在相等搜索概率的情形下，高度為在相等搜索概率的情形下，高度為h+1的最優(yōu)的最優(yōu)的二叉排序樹(shù)中，上面的二叉排序樹(shù)中，上面 h (h是高度是高度) 層都是層都是( )的，第的，第 h+1層層( )。 a滿(mǎn)，不滿(mǎn)滿(mǎn)，不滿(mǎn) b不滿(mǎn)，不滿(mǎn)不滿(mǎn)，不滿(mǎn) c滿(mǎn)，滿(mǎn)滿(mǎn)，滿(mǎn) d不滿(mǎn)，滿(mǎn)不滿(mǎn)，滿(mǎn) a22 假定一個(gè)線(xiàn)性表為假定一個(gè)線(xiàn)性表為(12, 23, 74, 55, 63, 40, 82,

11、36)，若按，若按key%3條件進(jìn)行劃分，使得同一余條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的三個(gè)子表數(shù)的元素成為一個(gè)子表，則得到的三個(gè)子表分別為分別為_(kāi)、_和和_ 12， 63， 36 55， 40， 82 23， 7423 在有序表在有序表a112中，采用二分查找算法查中，采用二分查找算法查找等于找等于a12的元素，所比較的元素下標(biāo)依次的元素，所比較的元素下標(biāo)依次為為( )。 6-9-11-1224 對(duì)于長(zhǎng)度為對(duì)于長(zhǎng)度為n的線(xiàn)性表，若采用順序查找法進(jìn)的線(xiàn)性表，若采用順序查找法進(jìn)行查找，則時(shí)間復(fù)雜度為行查找，則時(shí)間復(fù)雜度為( )；若采用二分；若采用二分查找法進(jìn)行查找，則時(shí)間復(fù)雜度

12、為查找法進(jìn)行查找，則時(shí)間復(fù)雜度為( )。 o(n) o(log2n)25 在散列函數(shù)在散列函數(shù)h(key)=key%p，p應(yīng)取應(yīng)取( )。 小于或等于小于或等于key的最大素?cái)?shù)的最大素?cái)?shù)26 長(zhǎng)度為長(zhǎng)度為100和和1000的散列表中分別存放有的散列表中分別存放有50和和500個(gè)數(shù)據(jù)，采用鏈地址解決沖突，那么散列個(gè)數(shù)據(jù)，采用鏈地址解決沖突，那么散列查找的平均查找長(zhǎng)度分別近似為查找的平均查找長(zhǎng)度分別近似為( )、( )。 1.5 1.527 假定一組數(shù)據(jù)對(duì)象為假定一組數(shù)據(jù)對(duì)象為 ( 40, 28, 16, 56, 50, 32, 30, 63 )，按，按次序插入每個(gè)對(duì)象生成一棵次序插入每個(gè)對(duì)象生成一棵avl樹(shù)（高度平衡的二叉搜樹(shù)（高度平衡的二叉搜