第9章查找(二)習題練習

設散列表長度為散列函數h(x)=x%給定的關鍵字序列為試畫出分別用拉鏈法和線性探查法解決沖突時所構造的散列表並求出在等概率情況下這兩種方法查找成功和失敗時的平均查找長度請問裝填因子的值是什麼? 

假定有k個關鍵字互為同義詞若用線性探查法把這些同義詞存入散列表中至少要進行多少次探查?

為什麼說當裝填因子非常接近時線性探查類似於順序查找?為什麼說當裝填因子比較小(比如α=左右)時散列查找的平均查找時間為O()?

設順序表中關鍵字是遞增有序的試寫一順序查找算法將哨兵設在表的高下標端然後求出等概率情況下查找成功與失敗時的ASL

試寫出二分查找的遞歸算法

試寫一算法判別給定的二叉樹是否為二叉排序樹設此二叉樹以二叉鏈表為存儲結構且樹中結點的關鍵字均不相同

試寫一遞歸算法從大到小輸出二叉排序樹中所有其值不小於x的關鍵字要求算法的時間為O(lgn+m)n為樹中結點數m為輸出關鍵字個數(提示先遍歷右子樹後遍歷左子樹)

寫一個遍歷B樹的算法使輸出的關鍵字序列遞增有序算法中的讀盤操作可假定為DiskRead

若采用除余法作為散列函數線性探查解決沖突則節中通用的散列表查找算法可改寫為對線性探查專用的查找算法
  int HashSearch(HashTable TKeyType Kint *pos){
  　　　int i=;//記錄探查次數
  　　　*pos=K%m; //散列函數值作為第一個散列地址
 　　　 while(i++<m) //最多探查m次
    　　　　{
      　　　　　if(T[*pos]key==K) return ;//查找成功返回
      　　　　　if(T[*pos]key==NIL) return ;//查找失敗返回
      　　　　　*pos=(*pos+)%m;//用線性探查法求下一個探查地址
    　　　　}
  　　　return ;//查找失敗且表滿
　　}//HashSearch
　　假設散列表上的刪除操作已將結點的關鍵字標記為DELETED(例如不妨設DELETED為)請修改上述散列表上的查找算法及插入算法HashInsert使之能正確地查找和插入

用拉鏈法解決沖突有關的類型說明和插入算法如下請據此寫出散列表的建表查找及刪除算法
　typedef struct node{
　　　KeyType key;//關鍵字
　　　InfoType Otherinfo;//以下不處理此域
　　　struct node *next;//鏈域
　　}CNodeType;
　typedef CNodeType *CHashTable[m];//散列表類型是一個指針數組
　void ChainHashInsert(CHashTable TKeyType K){
　　　//將關鍵字K插入表T中設散列函數為h(K)=K%m
　　　CNodeType *p;
　　　int addr;
　　　p=ChainHashSearch(TK);//在T中查找有無關鍵字為K的結點
　　　if (p) printf(duplicate key!);//關鍵字已存在
　　　else {//申請一個新結點將其關鍵字置為K並插入相應鏈表的頭上
　　　　　　　addr=K%m;//求散列函數值作為散列地址
　　　　　　　p=(CNodeType *)malloc(sizeof(CNodeType));
　　　　　　　p>key=K;p>next=T[addr];T[addr]=p;//將*p插入鏈表T[addr]的頭部 
　　　　　　}//endif
　　}//ChainHashInsert

From:http://tw.wingwit.com/Article/program/sjjg/201311/23279.html