熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第六章 答案 (四)[5]

2013-11-15 14:59:16  來源: 數據結構 

  .根據順序存儲的完全二叉樹的性質編號為i的結點的雙親的編號是ëi/û故A[i]和A[j]的最近公共祖先可如下求出

  while(i/!=j/)

  if(i>j) i=i/; else  j=j/;

  退出while後若i/=則最近公共祖先為根結點否則最近公共祖先是i/

  .N個結點的K叉樹最大高度N(只有一個葉結點的任意k叉樹)設最小高度為H第i(<=i<=H)層的結點數Ki則N=+k+k+…+ kH由此得H=ëlogK(N(K)+

   結點個數在的滿二叉樹且結點數是素數的數是其葉子數是

  .設分枝結點和葉子結點數分別是為nk和n因此有n=n+nk      ()

  另外從樹的分枝數B與結點的關系有 n=B+=K*nk +               ()

  由()和()有 n=nnk=(n(K)+)/K

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/22664.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.