山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-什么是二叉樹(shù) - 常識(shí)判斷
山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-什么是二叉樹(shù)減小字體增大字體山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-什么是二叉樹(shù)
二叉樹(shù)是一種很有用的非線性結(jié)構(gòu)。二就樹(shù)具有以下兩個(gè)特點(diǎn):
非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn);
每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù),且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。
由以上特點(diǎn)可以看出,在二叉樹(shù)中,每一個(gè)結(jié)點(diǎn)的度最大為2,即所有子樹(shù)(左子樹(shù)或右子樹(shù))也均為二叉樹(shù),而樹(shù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以是任意的。另外,二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)的子樹(shù)被明顯地分為左子樹(shù)與右子樹(shù)??梢詻](méi)有其中的一個(gè),也可以全沒(méi)有。
二叉樹(shù)的基本性質(zhì)
性質(zhì)1:在二叉樹(shù)的第K層上,最多有(K1)個(gè)結(jié)點(diǎn)。
性質(zhì)2:濃度為M的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)。
深度為m的二叉樹(shù)是指二叉樹(shù)共有m層。
性質(zhì)3:在任意一棵二叉樹(shù)中度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。
性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的二叉樹(shù),其深度至少為[log2n]+1,其中[log2n]表示取的整數(shù)部分。
滿二叉樹(shù)與完全二叉樹(shù)
滿二叉樹(shù)與完全二叉樹(shù)是兩種特殊形態(tài)的二叉樹(shù)。
滿二叉樹(shù)
所謂滿二叉樹(shù)是指這樣的一種二叉樹(shù);除最后一層外,每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。這就是說(shuō),在滿二叉樹(shù)中,每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值,即在滿二叉樹(shù)的第K層上有2K-1個(gè)結(jié)點(diǎn),且深度為m的滿二叉樹(shù)有2m-1個(gè)結(jié)點(diǎn)。
完全二叉樹(shù)
所謂完全二叉樹(shù)是指這樣的二叉樹(shù),除最后一層外,每一層上的結(jié)點(diǎn)數(shù)均達(dá)的最大值;在最后一層上只缺少右邊的若干結(jié)點(diǎn)。
列確切地說(shuō),如果從根結(jié)點(diǎn)起,對(duì)二叉樹(shù)的結(jié)點(diǎn)自上而下、自左至右用自然數(shù)進(jìn)行邊疆編號(hào),則深度為m、且有n個(gè)結(jié)點(diǎn)的二叉樹(shù),當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí),稱之為完全二叉樹(shù)。
對(duì)于完全二叉樹(shù)來(lái)說(shuō),葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn);對(duì)于任何一個(gè)結(jié)點(diǎn),若其右分支下的子孫結(jié)點(diǎn)的最大層次為p,則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)閜,或?yàn)閜+1。
由滿二叉樹(shù)與完全二叉樹(shù)的特點(diǎn)可以看出,滿二叉樹(shù)也是完全二叉樹(shù),而完全二叉樹(shù)一般不是滿二叉樹(shù)。
完全二叉樹(shù)還具有以下兩個(gè)性質(zhì):
性質(zhì)5:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1。
性質(zhì)6:設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始,按層序(每一層從左到右)用自然數(shù)1,2,,n給結(jié)點(diǎn)進(jìn)行編號(hào),則對(duì)于編號(hào)為k(k=1,2,n)的結(jié)點(diǎn)有以下結(jié)論:
若k=1,則該結(jié)點(diǎn)為根結(jié)點(diǎn),它沒(méi)有父結(jié)點(diǎn);若k1,則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)。
若2kn,則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k;否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)(顯然也沒(méi)有右子結(jié)點(diǎn))。
若2k+1n,則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1;否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。
用戶名:!查看更多評(píng)論
分值:100分55分1分
內(nèi)容:!
通知管理員驗(yàn)證碼:點(diǎn)擊獲取驗(yàn)證碼
軍隊(duì)文職招聘行測(cè)基礎(chǔ)知識(shí)-計(jì)算機(jī)發(fā)展簡(jiǎn)史-第一代(1946~1957年),電子管計(jì)算機(jī) - 常識(shí)判斷
軍隊(duì)文職招聘行測(cè)基礎(chǔ)知識(shí)-計(jì)算機(jī)發(fā)展簡(jiǎn)史-第一代(1946~1957年),電子管計(jì)算機(jī)減小字體增大字體軍隊(duì)文職招聘行測(cè)基礎(chǔ)知識(shí)-計(jì)算機(jī)發(fā)展簡(jiǎn)史-第一代(1946~1957年),電子管計(jì)算機(jī)它是一臺(tái)電子數(shù)字積分計(jì)算機(jī),取名為ENIAC。這臺(tái)計(jì)算機(jī)是個(gè)龐然大物,共用了18000多個(gè)電子管、1500個(gè)繼電器,重達(dá)30噸,占地170平方米,每小時(shí)耗電140千瓦,計(jì)算速度為每秒5000次加法運(yùn)算。盡管它的功能遠(yuǎn)不如今天的計(jì)算機(jī),但ENIAC作為計(jì)算機(jī)大家族的鼻祖,開(kāi)辟了人類科學(xué)技術(shù)領(lǐng)域的先河,使信息處理技術(shù)進(jìn)入了一個(gè)嶄新的時(shí)代。其主要特征如下:
(1)電子管元件,體積龐大、耗電量高、可靠性差、維護(hù)困難。
(2)運(yùn)算速度慢,一般為每秒鐘1千次到1萬(wàn)次。
(3)使用機(jī)器語(yǔ)言,沒(méi)有系統(tǒng)軟件。
(4)采用磁鼓、小磁芯作為存儲(chǔ)器,存儲(chǔ)空間有限。
(5)輸入/輸出設(shè)備簡(jiǎn)單,采用穿孔紙帶或卡片。
(6)主要用于科學(xué)計(jì)算。
用戶名:!查看更多評(píng)論
分值:100分55分1分
內(nèi)容:!
通知管理員驗(yàn)證碼:點(diǎn)擊獲取驗(yàn)證碼