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

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

  T[]
    ┌──┐
   │    │→ → →∧
    ├──┤
   │    │→ → →→ ∧
    ├──┤
   │    │→ →∧
    ├──┤
   │ ∧ │
    ├──┤
   │ ∧ │
    ├──┤
   │    │→ → →∧
　　├──┤
　 │ ∧ │
    ├──┤
   │ ∧ │
    ├──┤
   │ ∧ │
    ├──┤
   │ ∧ │ 
    ├──┤
  │ ∧ │
    └──┘

  ()線性探查法如下圖

      下標                                 
          ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
  T[]││ │││││││  │  │  │
          └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
  探查次數                       


  用拉鏈法的查找成功平均查找長度為
    ASLsucc=(*+*+*)/=

  查找失敗時平均查找長度為
    ASLunsucc=(++++++++++)/=

  用線性探查法查找成功時平均查找長度為
    ASLsucc=(+++++++)/=

  查找失敗時平均查找長度為
    ASLunsucc=(++++++++++)/=

  裝填因子α拉鏈=/= α線性探查=/=

假定有k個關鍵字互為同義詞若用線性探查法把這些同義詞存入散列表中至少要進行多少次探查?
答
    至少要進行+++k+k次探查
    也就是說在散列表的一連串連續空間內第一個關鍵字只需探查一次第二個就要探查次如此這般第k個關鍵字就要探查k次才能找到位置存放所以至少要把它們全加起來才夠

為什麼說當裝填因子非常接近時線性探查類似於順序查找?為什麼說當裝填因子比較小(比如α=左右)時散列查找的平均查找時間為O()?
答
    當α非常接近時整個散列表幾乎被裝滿由於線性探查法在關鍵字同義時解決沖突的辦法是線性地向後查找當整個表幾乎裝滿時它就很類似於順序查找了
    當α比較小時關鍵字碰撞的幾率比較小一般情況下只要按照散列函數計算出的結果能夠次性就找到相應結點因此它的平均查找時間接近於

設順序表中關鍵字是遞增有序的試寫一順序查找算法將哨兵設在表的高下標端然後求出等概率情況下查找成功與失敗時的ASL
答:
  typedef struct{
　　　KeyType key
　　　InfoType otherinfo //此類型依賴於應用
　　}NodeType
　typedef NodeType SeqList[n+] //n號單元用作哨兵

　int SeqSearch(Seqlist RKeyType K)
　　　{ //在關鍵字遞增有序的順序表R[n]中順序查找關鍵字為K的結點
　　　　//成功時返回找到的結點位置失敗時返回
　　　　int i
　　　　R[n]key=K //設置哨兵
　　　　for(i=R[i]key<=K;i) //從表前往後找
　　　　if (i<n&&R[i]key==K) return i; //R[i]是要找的結點
　　　　else return  
　　　} //SeqSearch

　　等概率情況下查找成功ASL=(+++…+n)/n
　　等概率情況下查找失敗時的ASL=(+++…+n+n+)/(n+)

試寫出二分查找的遞歸算法
解
  int BinSearch(SeqList RKeyType Kint lowint high)
　　{ //在有序表R[lowhigh]中進行二分查找成功時返回結點的位置失敗時返回零
　　　int mid //置當前查找區間上下界的初值
　　　if (low<=high){ //當前查找區間R[lowhigh]非空
　　　　　mid=(low+high)/
　　　　　if(R[mid]key==K) return mid //查找成功返回
　　　　　if(R[mid]kdy>K)
　　　　　　　return BinSearch( RKlowmid)//在R[lowmid]中查找
　　　　　else
　　　　　　　return BinSearch( RKmid+high) //在R[mid+high]中查找
　　　　}
　　　return //當low>high時表示查找區間為空查找失敗
　　} //BinSeareh

試寫一算法判別給定的二叉樹是否為二叉排序樹設此二叉樹以二叉鏈表為存儲結構且樹中結點的關鍵字均不相同
解
　　由二叉排序樹的定義可得二叉排序樹中左子樹的所有結點的值都小於根結點的值所有右子樹中結點的值都大於根結點的值那麼只要對待判定的二叉樹中的結點按層遍歷並判斷即可在該算法中要用到隊列保存已遍歷的結點指針

　typedef BinTNode *DataType;//循環隊列中元素為二叉樹結點指針 
　int BinSortStree(BinTree T)
　　{ 
　　　CirQueue Q;
　　　BinTNode *p;
　　　if (!T) return ;//空樹為二叉排序樹
　　　InitQueue(&Q);
　　　EnQueue(&QT);
　　　while(!QueueEmpty(&Q))
　　　　{
　　　　　p=DeQueue(&Q);
　　　　　if (p>lchild)
　　　　　　if (p>data<p>lchild>data) return ;//不是二叉排序樹
　　　　　　else EnQueue(&Qp>lchild);
　　　　　if (p>rchild)
　　　　　　if (p>data>p>rchild>data) return ;//不是二叉排序樹
　　　　　　else EnQueue(&Qp>rchild);
　　　　}
　　　return ;//是二叉排序樹　
　　}

試寫一遞歸算法從大到小輸出二叉排序樹中所有其值不小於x的關鍵字要求算法的時間為O(lgn+m)n為樹中結點數m為輸出關鍵字個數(提示先遍歷右子樹後遍歷左子樹)
答
　typedef int KeyType //假定關鍵字類型為整數
　typedef struct node { //結點類型
　　　KeyType key //關鍵字項
　　　InfoType otherinfo //其它數據域InfoType視應用情況而定下面不處理它
　　　struct node *lchild*rchild //左右孩子指針
　　} BSTNode
　typedef BSTNode *BSTree

　void OUTPUTNODE(BSTree TKeyType x)
　　{//從大到小輸出二叉排序樹中所有其值不小於x的關鍵字
　　　if (T)
　　　　{
　　　　　OUTPUTNODE( T>rchildx);
　　　　　if (T>key>=x) printf(%dT>key);
　　　　　OUTPUTNODE( T>Lchildx);
　　　　}
　　}

寫一個遍歷B樹的算法使輸出的關鍵字序列遞增有序算法中的讀盤操作可假定為DiskRead
答
　#define Max l //結點中關鍵字的最大數目Max=mm是B樹的階
　#define Min //非根結點中關鍵字的最小數目Min=「m/(
　typedef int KeyType //KeyType應由用戶定義
　typedef struct node{ //結點定義中省略了指向關鍵字代表的記錄的指針
　　　int keynum //結點中當前擁有的關鍵字的個數keynum<=Max
　　　KeyType key[Max+] //關鍵字向量為key[keynum]key[]不用
　　　struct node *parent //指向雙親結點
　　　struct node *son[Max+]//孩子指針向量為son[keynum]
　　}BTreeNode
　typedef BTreeNode *BTree

　void travelBtree(BTree T){
　　//按關鍵字遞增序輸出B樹序列
　　int i;
　　if (T){
　　　　for(i=;i<=T>keynum;i++)//T>keynum個關鍵字的結點有T>keynum+棵子樹
　　　　　{
　　　　　　　if (T>son[i]){
　　　　　　　　　DiskRead(T>son[i]);//讀入根結點的第i棵子樹
　　　　　　　　　travelBtree(T>son[i]);//遍歷第i棵子樹
　　　　　　　　}
　　　　　　　if (i<T>keynmu)//若剛遍歷的子樹不是最後一棵子樹
　　　　　　　　　printf(%dT>key[i+];　
　　　　　}
　　}

數據結構免費提供，內容來源於互聯網,本文歸原作者所有。