1．對于二叉排序樹，下面的說法（ ）是正確的。 A．二叉排序樹是動態樹表，查找不成功時插入新結點時，會引起樹的重新分裂和組合 B．對二叉排序樹進行層序遍歷可得到有序序列 C．用逐點插入法構造二叉排序樹時，若先后插入的關鍵字有序，二叉排序樹的深度最大 D．在二叉排序樹中進行查找，關鍵字的比較次數不超過結點數的1/2 2．在有n個結點且為完全二叉樹的二叉排序樹中查找一個鍵值，其平均比較次數的數量級為（ ）。 A．O(n) B．O(log2n) C．O(n*log2n) D．O(n2) 3．靜態查找與動態查找的根本區別在于（ ）。 A. 它們的邏輯結構不一樣 B. 施加在其上的操作不同 C. 所包含的數據元素類型不一樣 D. 存儲實現不一樣 4．已知一個有序表為{12，18，24，35，47，50，62，83，90，115，134}，當折半查找值為90的元素時，經過（ ）次比較后查找成功。 A．2 B．3 C．4 D．5 5．已知數據序列為（34，76，45，18，26，54，92，65），按照依次插入結點的方法生成一棵二叉排序樹，則該樹的深度為（ ）。 A. 4 B. 5 C. 6 D. 7 6．設散列表表長m=14，散列函數H（k）=k mod 11 。表中已有15，38，61，84四個元素，如果用線性探測法處理沖突，則元素49的存儲地址是（ ）。 A. 8 B. 3 C. 5 D. 9 7. 平衡二叉樹的查找效率呈（ ）數量級。 A. 常數階 B. 線性階 C. 對數階 D. 平方階 8. 設輸入序列為{20,11,12,…},構造一棵平衡二叉樹，當插入值為12的結點時發生了不平衡，則應該進行的平衡旋轉是（ ）。 A. LL B. LR C. RL D. RR 二、填空題（每空3分，共24分）。 1．在有序表A[1..18]中，采用二分查找算法查找元素值等于A[7]的元素，所比較過的元素的下標依次為 。 2．利用逐點插入法建立序列(61，75，44，99，77，30，36，45)對應的二叉排序樹以后，查找元素36要進行 次元素間的比較，查找序列為 。 3. 用順序查找法在長度為n的線性表中進行查找，在等概率情況下，查找成功的平均比較次數是 。 4. 二分查找算法描述如下： intSearch_Bin(SST ST, KT key) { low=1 ; high=ST. length; while(low<=high) { mid=(low+high)/2; if(key==ST.elem[mid].key) return mid; else if(key<ST.elem[mid].key) ; else ; } return 0; } 5．鏈式二叉樹的定義如下： typedef struct Btn{ TElemType data; ; }BTN ,*BT; 6．在有n個葉子結點的哈夫曼樹中，總結點數是 。 三、綜合題（共52分）。 1. （共12分）假定關鍵字輸入序列為19，21，47，32，8，23，41，45，40，畫出建立二叉平衡樹的過程。 2. （共15分）有關鍵字{13，28，31，15，49，36，22，50，35，18，48，20}，Hash 函數為H=key mod 13，沖突解決策略為鏈地址法，請構造Hash表（12分），并計算平均查找長度（3分）。 ASL= 3. （共10分）設關鍵字碼序列{20，35，40，15，30，25}，給出平衡二叉樹的構造過程。 4. （共15分）設哈希表長為m=13，散列函數為H(k)=k mod 11，關鍵字序列為5，7，16，12，11，21，31，51，17