《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集第9章_查找

1、1第九章第九章查找查找1.若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A［3］的比較序列的下標(biāo)依次為()A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，32設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為（）。A.O(1)B.O(log2n)C.O(n)D.O(n2)5設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較（）次。A.25B.10C.7

2、D.16順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（）。A.O(n)B.O(n2)C.O(n12)D.O(1og2n)8（）二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷9設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134)則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（）。A.1B.2C.3D.410設(shè)某散列表的長(zhǎng)度為100，散

3、列函數(shù)H(k)=k%P，則P通常情況下最好選擇（）。A.99B.97C.91D.9311在二叉排序樹(shù)中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（）。A.O(n)B.O(1og2n)C.O(nlog2n)D.O(n2)12設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過(guò)程中比較元素的順序?yàn)?)。A.A[1]，A[2]，A[3]，A[4]B.A[1]，A[14]，A[7]，A[4]C.A[7]，A[3]，A[5]，A

4、[4]D.A[7]，A[5]，A[3]，A[4]13設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)=key%p，則p最好選擇（）。A.小于等于m的最大奇數(shù)B.小于等于m的最大素?cái)?shù)C.小于等于m的最大偶數(shù)D.小于等于m的最大合數(shù)14設(shè)順序表的長(zhǎng)度為n，則順序查找的平均比較次數(shù)為（）。A.nB.n2C.(n1)2D.(n1)215設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過(guò)（）

5、次比較。A.1B.2C.3D.417設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹(shù)的深度為（）。A.4B.5C.6D.718二叉排序樹(shù)中左子樹(shù)上所有結(jié)點(diǎn)的值均（）根結(jié)點(diǎn)的值。A.C.=D.!=355二叉查找樹(shù)的查找效率與二叉樹(shù)的樹(shù)型有關(guān)在()時(shí)其查找效率最低。A.結(jié)點(diǎn)太多B.完全二叉樹(shù)C.呈單枝樹(shù)D.結(jié)點(diǎn)太復(fù)雜。64.對(duì)于長(zhǎng)度為18的順序存儲(chǔ)的有序表，若采用二分查找，則查找第

6、15個(gè)元素的查找長(zhǎng)度為()。A.3B.4C.5D.6二、填空題7根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹(shù)的高度為_(kāi)___________。12設(shè)二叉排序樹(shù)的高度為h，則在該樹(shù)中查找關(guān)鍵字key最多需要比較_________次。13設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k%7，用線性探測(cè)法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長(zhǎng)度是________。16解決

7、散列表沖突的兩種方法是________________和__________________。18從一棵二叉搜索樹(shù)中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明_______，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向________查找，若元素的大于根結(jié)點(diǎn)的值，則繼續(xù)向________查找。20二叉搜索樹(shù)的中序遍歷得到的結(jié)點(diǎn)序列為_(kāi)_______。27在一棵二叉排序樹(shù)上按____________遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。28實(shí)現(xiàn)二

8、分查找的存儲(chǔ)結(jié)構(gòu)僅限于順序存儲(chǔ)結(jié)構(gòu)，且其中元素排列必須是____的。31一棵平衡二叉樹(shù)中任一結(jié)點(diǎn)的平衡因子只可能是__________。32二分查找的時(shí)間復(fù)雜度為_(kāi)________。41在線性表的________存儲(chǔ)中，對(duì)每一個(gè)元素只能采用順序查找。48對(duì)于二分查找所對(duì)應(yīng)的判定樹(shù)，它既是一棵_______，又是一棵________。64.平衡二叉樹(shù)又稱_________，其定義是________。69.在含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中查找一

9、個(gè)關(guān)鍵字，進(jìn)行關(guān)鍵字比較次數(shù)最大值是。72.動(dòng)態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有__________和__________運(yùn)算，而后者不包含這兩種運(yùn)算。83.在一棵二叉排序樹(shù)中，每個(gè)分支結(jié)點(diǎn)的左子樹(shù)上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值。86.向一棵二叉排序樹(shù)中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則接著向根結(jié)點(diǎn)的________插入，若元素的值大于根結(jié)點(diǎn)的值，則接