數據結構第四教學單元測驗練習題(答案)(自動保存的)

1、數據結構第4教學單元測試練習題第 9 頁 共 9 頁一、 選擇題1. 對N個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為( ) A（N+1）/2 B. N/2 C. N D. （1+N）*N /2AB2適用于折半查找的表的存儲方式及元素排列要求為( ) A鏈接方式存儲，元素無序 B鏈接方式存儲，元素有序C順序方式存儲，元素無序 D順序方式存儲，元素有序3當在一個有序的順序存儲表上查找一個數據時，即可用折半查找，也可用順序查找，但前者比后者的查找速度( ) A必定快 B.不一定 C. 在大部分情況下要快 D. 取決于表遞增還是遞減4. 具有12個關鍵字的有序表，折半查找的平均

2、查找長度（ ）A. 3.1 B. 4 C. 2.5 D. 55. 折半查找的時間復雜性為（ ）A. O（n2） B. O（n） C. O（nlogn）D. O（logn）6.對有18個元素的有序表作折半查找，則查找A3的比較序列的下標為（ ）A.1，2，3B.9，5，2，3 C.9，5，3 D.9，4，2，37.設有序表的關鍵字序列為1，4，6，10，18，35，42，53，67，71，78，84，92，99，當用二分查找法查找健值為84的結點時，經（ ）次比較后查找成功。A.2 B. 3 C. 4 D.128、用n個鍵值構造一棵二叉排序樹，最低高度為（ ）A.n/2 B.、n C.logn

3、D.logn+1 9分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是( ) 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)10.設有一組記錄的關鍵字為19，14，23，1，68，20，84，27，55，11，10，79，用鏈地址法構造散列表，散列函數為H（key）=key% 13,散列地址為1的鏈中有（ ）個記錄。A1 B. 2 C. 3 D. 411已知一采用開放地址法解決Has

4、h表沖突，要從此Hash表中刪除出一個記錄，正確的做法是(）A.將該元素所在的存儲單元清空。B.將該元素用一個特殊的元素代替C.將與該元素有相同Hash地址的后繼元素順次前移一個位置。D.用與該元素有相同Hash地址的最后插入表中的元素替代。11. 假定有k個關鍵字互為同義詞，若用線性探測法把這k個關鍵字存入散列表中，至少要進行多少次探測？( ) Ak-1次 B. k次C. k+1次D. k（k+1）/2次12. 散列表的地址區(qū)間為0-17,散列函數為H(K)=K mod 17。采用線性探測法處理沖突，并將關鍵字序列26，25，72，38，8，18，59依次存儲到散列表中。（1）元素59存放在

5、散列表中的地址是（ ）。A 8 B. 9 C. 10 D. 11 （2）存放元素59需要搜索的次數是（ ）。A 2 B. 3 C. 4 D. 513. 將10個元素散列到100000個單元的哈希表中，則（ ）產生沖突。A. 一定會 B. 一定不會 C. 仍可能會二、 判斷題1查找相同結點的效率折半查找總比順序查找高。 2對無序表用二分法查找比順序查找快。3對大小均為n的有序表和無序表分別進行順序查找，在等概率查找的情況下，對于查找成功，它們的平均查找長度是相同的，而對于查找失敗，它們的平均查找長度是不同的。4在查找樹（二叉樹排序樹）中插入一個新結點，總是插入到葉結點下面。 5對一棵二叉排序樹按

6、前序方法遍歷得出的結點序列是從小到大的序列。 6二叉樹中除葉結點外, 任一結點X，其左子樹根結點的值小于該結點（X）的值；其右子樹根結點的值該結點（X）的值,則此二叉樹一定是二叉排序樹。7. 在任意一棵非空二叉排序樹中，刪除某結點后又將其插入，則所得二排序叉樹與原二排序叉樹相同。8采用線性探測法處理散列時的沖突，當從哈希表刪除一個記錄時，不應將這個記錄的所在位置置空，因為這會影響以后的查找。9在散列檢索中，“比較”操作一般也是不可避免的。10散列函數越復雜越好，因為這樣隨機性好，沖突概率小. 11Hash表的平均查找長度與處理沖突的方法無關。 12負載因子 (裝填因子)是散列表的一個重要參數，

7、它反映散列表的裝滿程度。13. 若散列表的負載因子1，則可避免碰撞的產生。 三、填空題1.順序查找n個元素的順序表，若查找成功，則比較關鍵字的次數最多為_（1）n _次。 2.在有序表A1.20中，按二分查找方法進行查找，查找長度為5的元素個數是_ （2）5 _。3.在有序表A120中，按二分查找方法進行查找，查找長度為4的元素的下標從小到大依次是_（3）1,3,6,8,11,13,16,19_。4.有序表(12,18,24,35,47,50,62,83,90,115，134)使用二分法查找90時，需_（4）2_次查找成功，查100時，需_（5）4_次才能確定不成功。5.在n個記錄的有序順序表

8、中進行折半查找，最大比較次數是_（6）log2n+1_。（取下界）6.平衡因子的定義是_（7）結點的左子樹的高度減去結點的右子樹的高度_7.高度為8的平衡二叉樹的結點數至少有_（8）54_個。（參照教材P238：N0=0,N1=1,N2=2,公式Nh=Nh-1+Nh-2+1）8. 動態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有_（9）插入 _和_（10）_刪除_運算，而后者不包含這兩種運算。四、應用題1.假定對有序表：(3,4,5,7,24,30,42,54,63,72,87,95)進行折半查找，試回答下列問題：(1).畫出描述折半查找過程的判定樹；(2).若查找元素54，需依次與那些元素比較?(3).若查找元素90，需依次與那些元素比較?(4).假定每個元素的查找概率相等，求查找成功時的平均查找長度。2.一棵二叉排序樹結構如下,各結點的值從小到大依次為1-9，請標出各結點的值。3.依次輸入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序樹【華中理工大學 2000 五 （10分）】(1) 試畫出生成之后的二叉排序樹; (2) 對該二叉排序樹作中序遍歷，試寫出遍歷序列; (3) 假定每個元素的查找概率相等，試