首頁 - 網(wǎng)校 - 題庫 - 直播 - 雄鷹 - 團購 - 書城 - 模考 - 學(xué)習(xí)通 - 導(dǎo)航 - 510 -
首頁考試吧網(wǎng)校題庫直播雄鷹510團購書城?論壇實用文檔作文大全寶寶起名
2014中考
法律碩士
2014高考
MBA考試
2015考研
MPA考試
在職研
中科院
考研培訓(xùn) 自學(xué)考試 成人高考
四 六 級
GRE考試
攻碩英語
零起點日語
職稱英語
口譯筆譯
申碩英語
零起點韓語
商務(wù)英語
日語等級
GMAT考試
公共英語
職稱日語
新概念英語
專四專八
博思考試
零起點英語
托?荚
托業(yè)考試
零起點法語
雅思考試
成人英語三級
零起點德語
等級考試
華為認證
水平考試
Java認證
職稱計算機 微軟認證 思科認證 Oracle認證 Linux認證
公 務(wù) 員
導(dǎo)游考試
物 流 師
出版資格
單 證 員
報 關(guān) 員
外 銷 員
價格鑒證
網(wǎng)絡(luò)編輯
駕 駛 員
報檢員
法律顧問
管理咨詢
企業(yè)培訓(xùn)
社會工作者
銀行從業(yè)
教師資格
營養(yǎng)師
保險從業(yè)
普 通 話
證券從業(yè)
跟 單 員
秘書資格
電子商務(wù)
期貨考試
國際商務(wù)
心理咨詢
營 銷 師
司法考試
國際貨運代理人
人力資源管理師
廣告師職業(yè)水平
衛(wèi)生資格 執(zhí)業(yè)醫(yī)師 執(zhí)業(yè)藥師 執(zhí)業(yè)護士
會計從業(yè)資格
基金從業(yè)資格
統(tǒng)計從業(yè)資格
經(jīng)濟師
精算師
統(tǒng)計師
會計職稱
法律顧問
ACCA考試
注冊會計師
資產(chǎn)評估師
高級經(jīng)濟師
審計師考試
高級會計師
注冊稅務(wù)師
國際內(nèi)審師
理財規(guī)劃師
美國注冊會計師
一級建造師
安全工程師
設(shè)備監(jiān)理師
公路監(jiān)理師
公路造價師
二級建造師
招標師考試
物業(yè)管理師
電氣工程師
建筑師考試
造價工程師
注冊測繪師
質(zhì)量工程師
巖土工程師
注冊給排水
造價員考試
注冊計量師
環(huán)保工程師
化工工程師
暖通工程師
咨詢工程師
結(jié)構(gòu)工程師
城市規(guī)劃師
材料員考試
監(jiān)理工程師
房地產(chǎn)估價
土地估價師
安全評價師
房地產(chǎn)經(jīng)紀人
投資項目管理師
環(huán)境影響評價師
土地登記代理人
寶寶起名
繽紛校園
實用文檔
入黨申請
英語學(xué)習(xí)
思想?yún)R報
作文大全
工作總結(jié)
求職招聘 論文下載 直播課堂

2014年計算機二級公共基礎(chǔ)知識總結(jié)第一章(4)

考試吧整理了“2014年計算機二級公共基礎(chǔ)知識總結(jié)”,更多計算機等級考試輔導(dǎo)及試題,請關(guān)注考試吧!

  查看匯總:2014年計算機二級公共基礎(chǔ)知識總結(jié)匯總熱點文章

  1.4樹與二叉樹

  考點7 樹與二叉樹及其基本性質(zhì)

  考試鏈接:

  考點7在筆試考試中,是一個必考的內(nèi)容,在筆試考試中出現(xiàn)的幾率為100%,主要是以選擇的形式出現(xiàn),有時也有出現(xiàn)在填空題中,分值為2分,此考點為重點掌握內(nèi)容。重點識記樹及二叉樹的性質(zhì)。

  誤區(qū)警示:

  滿二叉樹也是完全二叉樹,而完全二叉樹一般不是滿二叉樹。應(yīng)該注意二者的區(qū)別。

  1、樹的基本概念

  樹(tree)是一種簡單的非線性結(jié)構(gòu)。在樹結(jié)構(gòu)中,每一個結(jié)點只有一個前件,稱為父結(jié)點,沒有前件的結(jié)點只有一個,稱為樹的根結(jié)點。每一個結(jié)點可以有多個后件,它們稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。

  在樹結(jié)構(gòu)中,一個結(jié)點所擁有的后件個數(shù)稱為該結(jié)點的度。葉子結(jié)點的度為0。在樹中,所有結(jié)點中的最大的度稱為樹的度。

  2、二叉樹及其基本性質(zhì)

  (1)二叉樹的定義

  二叉樹是一種很有用的非線性結(jié)構(gòu),具有以下兩個特點:

 、俜强斩鏄渲挥幸粋根結(jié)點;

  ②每一個結(jié)點最多有兩棵子樹,且分別稱為該結(jié)點的左子樹和右子樹。

  由以上特點可以看出,在二叉樹中,每一個結(jié)點的度最大為2,即所有子樹(左子樹或右子樹)也均為二叉樹,而樹結(jié)構(gòu)中的每一個結(jié)點的度可以是任意的。另外,二叉樹中的每個結(jié)點的子樹被明顯地分為左子樹和右子樹。在二叉樹中,一個結(jié)點可以只有左子樹而沒有右子樹,也可以只有右子樹而沒有左子樹。當一個結(jié)點既沒有左子樹也沒有右子樹時,該結(jié)點即為葉子結(jié)點。

  (2)二叉樹的基本性質(zhì)

  二叉樹具有以下幾個性質(zhì):

  性質(zhì)1:在二叉樹的第k層上,最多有2k-1(k≥1)個結(jié)點;

  性質(zhì)2:深度為m的二叉樹最多有2m-1個結(jié)點;

  性質(zhì)3:在任意一棵二叉樹中,度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個。

  性質(zhì)4:具有n個結(jié)點的二叉樹,其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分。

  小技巧:在二叉樹的遍歷中,無論是前序遍歷,中序遍歷還是后序遍歷,二叉樹的葉子結(jié)點的先后順序都是不變的。

  3、滿二叉樹與完全二叉樹

  滿二叉樹是指這樣的一種二叉樹:除最后一層外,每一層上的所有結(jié)點都有兩個子結(jié)點。在滿二叉樹中,每一層上的結(jié)點數(shù)都達到最大值,即在滿二叉樹的第k層上有2k-1個結(jié)點,且深度為m的滿二叉樹有2m-1個結(jié)點。

  完全二叉樹是指這樣的二叉樹:除最后一層外,每一層上的結(jié)點數(shù)均達到最大值;在最后一層上只缺少右邊的若干結(jié)點。

  對于完全二叉樹來說,葉子結(jié)點只可能在層次最大的兩層上出現(xiàn):對于任何一個結(jié)點,若其右分支下的子孫結(jié)點的最大層次為p,則其左分支下的子孫結(jié)點的最大層次或為p,或為p+1。

  完全二叉樹具有以下兩個性質(zhì):

  性質(zhì)5:具有n個結(jié)點的完全二叉樹的深度為[log2n]+1。

  性質(zhì)6:設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始,按層次(每一層從左到右)用自然數(shù)1,2,……,n給結(jié)點進行編號,則對于編號為k(k=1,2,……,n)的結(jié)點有以下結(jié)論:

 、偃鬹=1,則該結(jié)點為根結(jié)點,它沒有父結(jié)點;若k>1,則該結(jié)點的父結(jié)點編號為INT(k/2)。

  ②若2k≤n,則編號為k的結(jié)點的左子結(jié)點編號為2k;否則該結(jié)點無左子結(jié)點(顯然也沒有右子結(jié)點)。

 、廴2k+1≤n,則編號為k的結(jié)點的右子結(jié)點編號為2k+1;否則該結(jié)點無右子結(jié)點。

  考點8 二叉樹的遍歷

  考試鏈接:

  考點8在筆試考試中考核幾率為30%,分值為2分,讀者應(yīng)該熟練掌握各種遍歷的具體算法,能由兩種遍歷的結(jié)果推導(dǎo)另一種遍歷的結(jié)果。

  在遍歷二叉樹的過程中,一般先遍歷左子樹,再遍歷右子樹。在先左后右的原則下,根據(jù)訪問根結(jié)點的次序,二叉樹的遍歷分為三類:前序遍歷、中序遍歷和后序遍歷。

  (1)前序遍歷:先訪問根結(jié)點、然后遍歷左子樹,最后遍歷右子樹;并且,在遍歷左、右子樹時,仍然先訪問根結(jié)點,然后遍歷左子樹,最后遍歷右子樹。

  (2)中序遍歷:先遍歷左子樹、然后訪問根結(jié)點,最后遍歷右子樹;并且,在遍歷左、右子樹時,仍然先遍歷左子樹,然后訪問根結(jié)點,最后遍歷右子樹。

  (3)后序遍歷:先遍歷左子樹、然后遍歷右子樹,最后訪問根結(jié)點;并且,在遍歷左、右子樹時,仍然先遍歷左子樹,然后遍歷右子樹,最后訪問根結(jié)點。

  疑難解答:樹與二叉樹的不同之處是什么?

  在二叉樹中,每一個結(jié)點的度最大為2,即所有子樹(左子樹或右子樹)也均為二叉樹,而樹結(jié)構(gòu)中的每一個結(jié)點的度可以是任意的。

1 2  下一頁

  相關(guān)推薦:

  計算機等級考試合格標準

  2014年計算機等考上機六大注意事項

  考試吧:2014年3月計算機等考真題及答案解析專題

文章搜索
計算機等級考試欄目導(dǎo)航
版權(quán)聲明:如果計算機等級考試網(wǎng)所轉(zhuǎn)載內(nèi)容不慎侵犯了您的權(quán)益,請與我們聯(lián)系800@exam8.com,我們將會及時處理。如轉(zhuǎn)載本計算機等級考試網(wǎng)內(nèi)容,請注明出處。
Copyright © 2004- 考試吧計算機等級考試網(wǎng) All Rights Reserved 
中國科學(xué)院研究生院權(quán)威支持(北京) 電 話:010-62168566 傳 真:010-62192699