首頁 考試吧論壇 Exam8視線 考試商城 網(wǎng)絡課程 模擬考試 考友錄 實用文檔 求職招聘 論文下載
2011中考 | 2011高考 | 2012考研 | 考研培訓 | 在職研 | 自學考試 | 成人高考 | 法律碩士 | MBA考試
MPA考試 | 中科院
四六級 | 職稱英語 | 商務英語 | 公共英語 | 托福 | 雅思 | 專四專八 | 口譯筆譯 | 博思 | GRE GMAT
新概念英語 | 成人英語三級 | 申碩英語 | 攻碩英語 | 職稱日語 | 日語學習 | 法語 | 德語 | 韓語
計算機等級考試 | 軟件水平考試 | 職稱計算機 | 微軟認證 | 思科認證 | Oracle認證 | Linux認證
華為認證 | Java認證
公務員 | 報關員 | 銀行從業(yè)資格 | 證券從業(yè)資格 | 期貨從業(yè)資格 | 司法考試 | 法律顧問 | 導游資格
報檢員 | 教師資格 | 社會工作者 | 外銷員 | 國際商務師 | 跟單員 | 單證員 | 物流師 | 價格鑒證師
人力資源 | 管理咨詢師考試 | 秘書資格 | 心理咨詢師考試 | 出版專業(yè)資格 | 廣告師職業(yè)水平
駕駛員 | 網(wǎng)絡編輯
衛(wèi)生資格 | 執(zhí)業(yè)醫(yī)師 | 執(zhí)業(yè)藥師 | 執(zhí)業(yè)護士
會計從業(yè)資格考試會計證) | 經(jīng)濟師 | 會計職稱 | 注冊會計師 | 審計師 | 注冊稅務師
注冊資產(chǎn)評估師 | 高級會計師 | ACCA | 統(tǒng)計師 | 精算師 | 理財規(guī)劃師 | 國際內(nèi)審師
一級建造師 | 二級建造師 | 造價工程師 | 造價員 | 咨詢工程師 | 監(jiān)理工程師 | 安全工程師
質(zhì)量工程師 | 物業(yè)管理師 | 招標師 | 結構工程師 | 建筑師 | 房地產(chǎn)估價師 | 土地估價師 | 巖土師
設備監(jiān)理師 | 房地產(chǎn)經(jīng)紀人 | 投資項目管理師 | 土地登記代理人 | 環(huán)境影響評價師 | 環(huán)保工程師
城市規(guī)劃師 | 公路監(jiān)理師 | 公路造價師 | 安全評價師 | 電氣工程師 | 注冊測繪師 | 注冊計量師
繽紛校園 | 實用文檔 | 英語學習 | 作文大全 | 求職招聘 | 論文下載 | 訪談 | 游戲
您現(xiàn)在的位置: 考試吧(Exam8.com) > 軟件水平考試 > 復習資料 > 程序員資料 > 正文

2011年軟考程序員考試復習筆試知識點整理(9)

來源:考試吧Exam8.com) 2011-4-11 19:48:13 考試吧:中國教育培訓第一門戶 模擬考場
考試吧提供了“2011年軟考程序員考試復習筆試知識點整理”,供考生參考。

  (3)B+樹

  B+樹是B-樹的變體,也是一種多路搜索樹:

  1.其定義基本與B-樹同,除了:

  2.非葉子結點的子樹指針與關鍵字個數(shù)相同;

  3.非葉子結點的子樹指針P[i],指向關鍵字值屬于[K[i], K[i+1])的子樹(B-樹是開區(qū)間);

  5.為所有葉子結點增加一個鏈指針;

  6.所有關鍵字都在葉子結點出現(xiàn);

  如:(M=3)

  B+的搜索與B-樹也基本相同,區(qū)別是B+樹只有達到葉子結點才命中(B-樹可以在非葉子結點命中),其性能也等價于在關鍵字全集做一次二分查找;

  B+的特性:

  1.所有關鍵字都出現(xiàn)在葉子結點的鏈表中(稠密索引),且鏈表中的關鍵字恰好是有序的;

  2.不可能在非葉子結點命中;

  3.非葉子結點相當于是葉子結點的索引(稀疏索引),葉子結點相當于是存儲(關鍵字)數(shù)據(jù)的數(shù)據(jù)層;

  4.更適合文件索引系統(tǒng);

  (4)B*樹

  是B+樹的變體,在B+樹的非根和非葉子結點再增加指向兄弟的指針;

  B*樹定義了非葉子結點關鍵字個數(shù)至少為(2/3)*M,即塊的最低使用率為2/3(代替B+樹的1/2);

  B+樹的分裂:當一個結點滿時,分配一個新的結點,并將原結點中1/2的數(shù)據(jù)復制到新結點,最后在父結點中增加新結點的指針;B+樹的分裂只影響原結點和父結點,而不會影響兄弟結點,所以它不需要指向兄弟的指針;

  B*樹的分裂:當一個結點滿時,如果它的下一個兄弟結點未滿,那么將一部分數(shù)據(jù)移到兄弟結點中,再在原結點插入關鍵字,最后修改父結點中兄弟結點的關鍵字(因為兄弟結點的關鍵字范圍改變了);如果兄弟也滿了,則在原結點與兄弟結點之間增加新結點,并各復制1/3的數(shù)據(jù)到新結點,最后在父結點增加新結點的指針;

  所以,B*樹分配新結點的概率比B+樹要低,空間使用率更高;

  (5)紅黑樹

  紅黑樹(Red-Black Tree)是二叉搜索樹(BinarySearch Tree)的一種改進。我們知道二叉搜索樹在最壞的情況下可能會變成一個鏈表(當所有節(jié)點按從小到大的順序依次插入后)。而紅黑樹在每一次插入或刪除節(jié)點之后都會花O(log N)的時間來對樹的結構作修改,以保持樹的平衡。也就是說,紅黑樹的查找方法與二叉搜索樹完全一樣;插入和刪除節(jié)點的的方法前半部分節(jié)與二叉搜索樹完全一樣,而后半部分添加了一些修改樹的結構的操作。

  map就是采用紅黑樹存儲的,紅黑樹(RB Tree)是平衡二叉樹,其優(yōu)點就是樹到葉子節(jié)點深度一致,查找的效率也就一樣,為logN。在實行查找,插入,刪除的效率都一致,而當是全部靜態(tài)數(shù)據(jù)時,沒有太多優(yōu)勢,可能采用hash表各合適。

  相對來說,hash_map是一個hashtable占用內(nèi)存更多,查找效率高一些,但是hash的時間比較費時?傮w而言,hash_map 查找速度會比map快,而且查找速度基本和數(shù)據(jù)數(shù)據(jù)量大小無關,屬于常數(shù)級別;而map的查找速度是log(n)級別。并不一定常數(shù)就比log(n)小, hash還有hash函數(shù)的耗時,明白了吧,如果你考慮效率,特別是在元素達到一定數(shù)量級時,考慮考慮hash_map。但若你對內(nèi)存使用特別嚴格,希望程序盡可能少消耗內(nèi)存,那么一定要小心,hash_map可能會讓你陷入尷尬,特別是當你的hash_map對象特別多時,你就更無法控制了,而且 hash_map的構造速度較慢。

  現(xiàn)在知道如何選擇了嗎?權衡三個因素: 查找速度, 數(shù)據(jù)量, 內(nèi)存使用。

  紅黑樹的每個節(jié)點上的屬性除了有一個key、3個指針:parent、lchild、rchild以外,還多了一個屬性:color。它只能是兩種顏色:紅或黑。而紅黑樹除了具有二叉搜索樹的所有性質(zhì)之外,還具有以下4點性質(zhì):

  1. 根節(jié)點是黑色的。

  2. 空節(jié)點是黑色的(紅黑樹中,根節(jié)點的parent以及所有葉節(jié)點lchild、rchild都不指向NULL,而是指向一個定義好的空節(jié)點)。

  3. 紅色節(jié)點的父、左子、右子節(jié)點都是黑色。

  4. 在任何一棵子樹中,每一條從根節(jié)點向下走到空節(jié)點的路徑上包含的黑色節(jié)點數(shù)量都相同。

上一頁  1 2 3 4 下一頁
  相關推薦:

  軟考程序員考試歷年真題重點題總結及答案

  2011年上半年軟考報名時間及方式匯總

  軟考程序員考試歷年真題匯總(2007年-2010年)

文章搜索
軟件水平考試欄目導航
版權聲明:如果軟件水平考試網(wǎng)所轉載內(nèi)容不慎侵犯了您的權益,請與我們聯(lián)系800@exam8.com,我們將會及時處理。如轉載本軟件水平考試網(wǎng)內(nèi)容,請注明出處。