【正文】 第一個元素的概率為 1/2 ，查找第二個元素的概率為 1/3 ，查找第三個元素的概率為 1/6 ，則查找任一元素的平均查找長度為 ( A ) 。 A .5/3 B .2 C. 7/3 D. 4/362. 對長度為 n 的單鏈有序表，若查找每個元素的概率相等，則查找任一元素的平均查找長度為 ( B ) 。 A. n/2 B . (n+1)/2 C. (n1)/2 D. n/463. 對于長度為 9 的順序存儲的有序表，若采用二分查找，在等概率情況下的平均查找長度為 ( A ) 的 9 分之一。 A .20 B. 18 C. 25 D. 2264. 對于長度為 18 的順序存儲的有序表，若采用二分查找，則查找第 15 個元素的查找長度為 ( B ) 。 A. 3 B. 4 C. 5 D. 665. 對于順序存儲的有序表 (5,12,20,26,37,42,46,50,64) ，若采用二分查找，則查找元素 26 的查找長度為 ( C ) 。 A .2 B. 3 C. 4 D. 566. 對具有 n 個元素的有序表采用二分查找，則算法的時間復雜性為 ( D ) 。 A. O (n) B. O (n 2 ) C. O (1) D. O (log 2 n)67. 在索引查找中，若用于保存數據元素的主表的長度為 n ，它被均分為 k 個子表，每個子表的長度均為 n/k ，則索引查找的平均查找長度為 ( D ) 。 A. n+k B. k+n/k C. (k+n/k)/2 D. (k+n/k)/2+168. 在索引查找中，若用于保存數據元素的主表的長度為 n ，它被均分為若干個子表，每個子表的長度均為 s ，則索引查找的平均查找長度為 ( B ) 。 A. (n+s)/2 B. (n/s+s)/2+1 C. (n+s)/2+1 D . (n/s+s)/269. 在索引查找中，若用于保存數據元素的主表的長度為 144 ，它被均分為 12 子表，每個子表的長度均為 12 ，則索引查找的平均查找長度為 ( A ) 。 A .13 B. 24 C. 12 D. 7970. 在索引查找中，若用于保存數據元素的主表的長度為 117 ，它被均分為 9 子表，則索引查找的平均查找長度為 ( B ) 。 A. 11 B. 12 C .13 D. 971. 在一棵深度為 h 的具有 n 個元素的二叉排序樹中，查找所有元素的最長查找長度為 ( D ) 。 A. n B. log 2 n C. (h+1)/2 D. h72. 從具有 n 個結點的二叉搜索樹中查找一個元素時，在平均情況下的時間復雜性大致為 ( C ) 。 A. O (n) B. O (1) C. O (log 2 n) D. O (n 2 )73. 從具有 n 個結點的二叉搜索樹中查找一個元素時，在最壞情況下的時間復雜性為 ( A ) 。 A. O (n) B. O (1) C. O (log 2 n) D. O (n 2 )74. 向具有 n 個結點的二叉搜索樹中插入一個元素時，其時間復雜性大致為 ( B ) 。 A. O (1) B .O (log 2 n ) C. O (n) D. O ( n log 2 n )75. 根據 n 個元素建立一棵二叉搜索樹時，其時間復雜性大致為 ( D ) 。 A. O (n) B .O (log 2 n ) C. O (n 2 ) D .O ( n log 2 n )76. 在一棵平衡二叉排序樹中，每個結點的平衡因子的取值范圍是 ( A) 。 A .1 ~ 1 B. 2 ~ 2 C. 1 ~ 2 D. 0 ~ 177. 若根據查找表 (23,44,36,48,52,73,64,58) 建立開散列表，采用 h(K)=K%13 計算散列地址，則元素 64 的散列地址為 ( C ) 。 A. 4 B. 8 C. 12 D. 1378. 若根據查找表 (23,44,36,48,52,73,64,58) 建立開散列表，采用 h(K)=K%7 計算散列地址，則散列地址等于 3 的元素個數 ( B ) 。 B .2 C. 3 D. 479. 若根據查找表 (23,44,36,48,52,73,64,58) 建立開散列表，采用 h(K)=K%7 計算散列地址，則同義詞元素個數最多為 ( C ) 。 A. 1 B. 2 C. 3 D. 480. 若根據查找表建立長度為 m 的閉散列表，采用線性探測法處理沖突，假定對一個元素第一次計算的散列地址為 d ，則下一次的散列地址為 (D ) 。 A. d B. d+1 C. (d+1)/m D. (d+1)%m81. 若根據查找表建立長度為 m 的閉散列表，采用二次探測法處理沖突，假定對一個元素第一次計算的散列地址為 d ，則第四次計算的散列地址為 ( C ) 。 A. (d+1)%m B. (d1)%m C . (d+4)%m D. (d4)%m82. 在采用線性探測法處理沖突的閉散列表上，假定裝填因子 a 的值為 ，則查找任一元素的平均查找長度為 (B ) 。 A. 1 B. C. 2 D .83. 在采用鏈接法處理沖突的開散列表上，假定裝填因子 a 的值為 4 ，則查找任一元素的平均查找長度為 ( A ) 。 A. 3 B. C. 4 D. 84. 在散列查找中，平均查找長度主要與 ( C ) 有關。 A. 散列表長度 B. 散列元素的個數 C. 裝填因子 D. 處理沖突方法85. 對順序表進行二分查找時，要求順序表必須： ，且數據元素有序 ，且數據元素有序【解答】B86. 下列二叉排序樹中查找效率最高的是： 【解答】A二、填空題1．假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進行劃分，使得同一余數的元素成為一個子表，則得到的四個子表分別為_____________、___________、________和___________。（12，40），（ ），（74），（23,55，63）2．向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度___________。增加13. 為了能有效地應用HASH查找技術，必須解決的兩個問題是________________和_____________________。構造一個好的HASH函數，確定解決沖突的方法4．設查找表中有100個元素，如果用二分法查找方法查找數據元素X，則最多需要比較________次就可以斷定數據元素X是否在查找表中。75．下列算法實現在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。struct record{int key。 int others。}。int hashsqsearch(struct record hashtable[ ],int k){int i,j。 j=i=k % p。while (hashtable[j].key!=kamp。amp。hashtable[j].flag!=0){j=(____) %m。 if (i==j) return(1)。}if (_______________________ ) return(j)。 else return(1)。} j+1，hashtable[j].key==k6．下列算法實現在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。typedef struct node{int key。 struct node *lchild。 struct node *rchild。}bitree。bitree *bstsearch(bitree *t, int k){ if (t==0 ) return(0)。else while (t!=0)if (tkey==k)_____________。 else if (tkeyk) t=tlchild。 else_____________。} return(t)，t=trchild7．根據初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。38．設散列函數H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。typedef struct node {int key。 struct node *next。} lklist。 void createlkhash(lklist *hashtable[ ]){int i,k。 lklist *s。for(i=0。im。i++)_____________________。for(i=0。in。i++){s=(lklist *)malloc(sizeof(lklist))。 skey=a[i]。k=a[i] % p。 snext=h