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

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

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

3、列函數(shù)H(k)=k%P，則P通常情況下最好選擇（）。A.99B.97C.91D.9311在二叉排序樹中插入一個關(guān)鍵字值的平均時間復雜度為（）。A.O(n)B.O(1og2n)C.O(nlog2n)D.O(n2)12設(shè)一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。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個存儲單元，散列函數(shù)H(key)=key%p，則p最好選擇（）。A.小于等于m的最大奇數(shù)B.小于等于m的最大素數(shù)C.小于等于m的最大偶數(shù)D.小于等于m的最大合數(shù)14設(shè)順序表的長度為n，則順序查找的平均比較次數(shù)為（）。A.nB.n2C.(n1)2D.(n1)215設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過（）

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

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

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

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

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