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