熱點(diǎn)2023年全國計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考試試題及答案

隨著我國國民經(jīng)濟(jì)的快速發(fā)展以及國際金融危機(jī)的逐漸消退，計(jì)算機(jī)網(wǎng)絡(luò)設(shè)備制造行業(yè)獲得良好發(fā)展機(jī)遇，中國已成為全球計(jì)算機(jī)網(wǎng)絡(luò)設(shè)備制造行業(yè)重點(diǎn)發(fā)展市場。下面是小編整理的關(guān)于計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考試試題及答案，歡迎大家參考!

全國計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考試試題及答案

一、單項(xiàng)選擇題

1、對(duì)建立良好的程序設(shè)計(jì)風(fēng)格，下面描述正確的是

A.程序應(yīng)簡單、清晰、可讀性好

B.符號(hào)名的命名只要符合語法

C.充分考慮程序的執(zhí)行效率

D.程序的注釋可有可無

參考答案：A

2、下列敘述中正確的是

A.軟件測試的主要目的是發(fā)現(xiàn)程序中的錯(cuò)誤

B.軟件測試的主要目的是確定程序中錯(cuò)誤的位置

C.為了提高軟件測試的效率，最好由程序編制者自己來完成軟件測試的工作

D.軟件測試是證明軟件沒有錯(cuò)誤

參考答案：A

參考解析：軟件測試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程，所以軟件測試的主要目的是發(fā)現(xiàn)程序中的錯(cuò)誤。為了提高軟件測試的效率，程序員應(yīng)該避免檢查自己的程序。軟件測試是為了證明軟件有錯(cuò)，而不能證明程序沒有錯(cuò)。因此本題的正確答案是A。

3、將E—R圖轉(zhuǎn)換到關(guān)系模式時(shí)，實(shí)體與聯(lián)系都可以表示成(　　)

A.屬性B.關(guān)系C.鍵D.域

參考答案：B

4、對(duì)象的操作過程對(duì)外是封閉的不可見的，即用戶只能看到這一操作實(shí)施后的結(jié)果。對(duì)象的這一特性，即是對(duì)象的

A.封裝性B.繼承性C.多態(tài)性D.模塊性

參考答案：A

5、在數(shù)據(jù)管理技術(shù)發(fā)展的三個(gè)階段中，數(shù)據(jù)共享最好的是(　　)

A.人工管理階段B.文件系統(tǒng)階段C.數(shù)據(jù)庫系統(tǒng)階段D.三個(gè)階段相同

參考答案：C

參考解析：在數(shù)據(jù)管理技術(shù)發(fā)展的三個(gè)階段中，數(shù)據(jù)共享最好的是數(shù)據(jù)庫系統(tǒng)階段(見前面的表1.2)。因此本題的正確答案是C。

6、下列敘述中正確的是(　　)

A.線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

B.棧與隊(duì)列是非線性結(jié)構(gòu)

C.雙向鏈表是非線性結(jié)構(gòu)

D.只有根結(jié)點(diǎn)的二叉樹是線性結(jié)構(gòu)

參考答案：A

參考解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表;棧、隊(duì)列、雙向鏈表都是線性結(jié)構(gòu);樹、二叉樹(不管它有多少個(gè)結(jié)點(diǎn))都是非線性結(jié)構(gòu)。

7、信息隱蔽的概念與下列哪一種概念直接相關(guān)?

A.軟件結(jié)構(gòu)的定義B.模塊的獨(dú)立性C.模塊的分類性D.模塊的內(nèi)聚程度

參考答案：B

8、下列敘述中正確的是

A.程序設(shè)計(jì)就是編制程序

B.程序的測試必須由程序員自己去完成

C.程序經(jīng)調(diào)試改錯(cuò)后還應(yīng)進(jìn)行再測試

D.程序經(jīng)調(diào)試改錯(cuò)后不必進(jìn)行再測試

參考答案：C

參考解析：程序設(shè)計(jì)不只是編制程序，還包括編寫相應(yīng)的文檔等;程序的測試一般不由程序員自己去完成，應(yīng)該由獨(dú)立的第三方來構(gòu)造測試;由于修正一個(gè)錯(cuò)誤的同時(shí)有可能會(huì)引入新的錯(cuò)誤，所以在修改錯(cuò)誤之后，必須進(jìn)行回歸測試。因此選項(xiàng)C正確。

9、在表示樹的多重鏈表中，除了要存儲(chǔ)結(jié)點(diǎn)的值和多個(gè)指針之外，還必須需要存儲(chǔ)(　　)

A.結(jié)點(diǎn)的度B.結(jié)點(diǎn)的層次C.結(jié)點(diǎn)的高度D.結(jié)點(diǎn)的深度

參考答案：A

10、下列關(guān)于鏈表結(jié)構(gòu)的敘述正確的是(　　)

A.線性鏈表、帶鏈的棧和帶鏈的隊(duì)列的結(jié)點(diǎn)的結(jié)構(gòu)都是相同的

B.雙向鏈表也就是循環(huán)鏈表

C.線性鏈表與帶鏈的棧的結(jié)點(diǎn)的結(jié)構(gòu)是不同的

D.在循環(huán)鏈表中通過任意一個(gè)結(jié)點(diǎn)可以找到鏈表中其他所有的結(jié)點(diǎn)，而在雙向鏈表中做不到這一點(diǎn)

參考答案：A

11、在E.R圖中，用來表示實(shí)體的圖形是(　　)

A.矩形B.橢圓形C.菱形D.三角形

參考答案：A

參考解析：在E.R圖中用矩形表示實(shí)體，用橢圓表示實(shí)體的屬性，用菱形表示實(shí)體之間的聯(lián)系，用線段來連接矩形、橢圓和菱形。因此本題的正確答案是A。

12、JaCkson方法是一種什么樣的的.結(jié)構(gòu)化分析方法?

A.面向數(shù)據(jù)流B.面向?qū)ο驝.面向數(shù)據(jù)結(jié)構(gòu)D.面向控制流

參考答案：C

13、通過相鄰數(shù)據(jù)元素的交換逐步：搿線性表變成有序的排序方法是(　　)

A.冒泡排序法B.簡單選擇排序法C.簡單插入排序法D.希爾排序法

參考答案：A

二、填空題

1、在面向?qū)ο蠓椒ㄖ?，類之間共享屬性和操作的機(jī)制稱為________

參考解析：繼承

2、在軟件生命周期的________階段，軟件的結(jié)構(gòu)、模塊的劃分、功能的分配以及處理流程應(yīng)該給出。

參考解析：軟件設(shè)計(jì)

3、在二維表中能唯一標(biāo)識(shí)元組的最小屬性集稱為該表的_________。

參考解析：碼

4、________測試方法也稱為功能測試或數(shù)據(jù)驅(qū)動(dòng)測試，它是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿足需求進(jìn)行測試和驗(yàn)證。

參考解析：黑盒測試

5、樹是-種簡單的________(線性月)線性)結(jié)構(gòu)，在樹中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的________特性。

參考解析：非線性 層次

6、軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的________集合。

參考解析：軟件開發(fā)工具

7、數(shù)據(jù)管理技術(shù)發(fā)展過程經(jīng)過人工管理、文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)三個(gè)階段，其中數(shù)據(jù)獨(dú)立性最高的階段是_________。

參考解析：數(shù)據(jù)庫系統(tǒng)

【分析】數(shù)據(jù)庫系統(tǒng)階段數(shù)據(jù)獨(dú)立性最高。

8、源程序文檔化要求程序應(yīng)該加注釋。注釋一般分為序言性注釋和________。

參考解析：功能性注釋

【分析】本題考查程序中的兩種注釋方式，只要考生看過一兩個(gè)規(guī)范化的源程序文檔.就會(huì)很好的了解這兩種注釋出現(xiàn)的位置和作用。

9、為每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)是________階段的任務(wù)。

參考解析：詳細(xì)設(shè)計(jì)

10、________是應(yīng)用于計(jì)算機(jī)定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。

參考解析：軟件工程

11、對(duì)對(duì)象的抽象形成了________，它是具有共同屬性、共同方法的對(duì)象的集合。

參考解析：類

【分析】類是對(duì)許多對(duì)象的共同屬性和方法的抽象，對(duì)象是一個(gè)類的具體實(shí)例。

12、現(xiàn)實(shí)世界的要求只有在_________中才能得到真正的物理實(shí)現(xiàn)，而這種實(shí)現(xiàn)是通過信息世界逐步轉(zhuǎn)化得到的。

參考解析：計(jì)算機(jī)世界

13、一個(gè)算法通常由兩種基本要素組成：-是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是________。

參考解析：算法的控制結(jié)構(gòu)

14、在一般的計(jì)算機(jī)系統(tǒng)中，有算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算和________四類基本的操作和運(yùn)算。

參考解析：數(shù)據(jù)傳輸

15、擁有奇數(shù)個(gè)結(jié)點(diǎn)的完全二叉樹中有4個(gè)內(nèi)部結(jié)點(diǎn)(非葉子結(jié)點(diǎn))，請(qǐng)問它的葉子結(jié)點(diǎn)數(shù)是________。

參考解析：5

【分析】由于完全二叉樹是自上而下、自左而右的從l開始連續(xù)編碼的，因此完全二又樹要么不存在-度結(jié)點(diǎn)(當(dāng)結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)個(gè)時(shí))，要么存在一個(gè)-度結(jié)點(diǎn)，而且唯-的一個(gè)-度結(jié)點(diǎn)就是最后編號(hào)為n(n為偶數(shù))的葉子結(jié)點(diǎn)的父結(jié)點(diǎn)。而在二叉樹中零度結(jié)點(diǎn)個(gè)數(shù)總比二度結(jié)點(diǎn)個(gè)數(shù)多l(xiāng)，因此擁有4個(gè)二度結(jié)點(diǎn)的二叉樹的葉子結(jié)點(diǎn)的個(gè)數(shù)是4+1=5。

總結(jié)，設(shè)n為完全二叉樹的結(jié)點(diǎn)數(shù)，n0為葉子結(jié)點(diǎn)數(shù)，nl為度為1的結(jié)點(diǎn)數(shù)，n2為度2的結(jié)點(diǎn)數(shù)，則n=n0+nl+n2,n0=n2+1。若n為奇數(shù)，則nI=0;若n為偶數(shù)，則nl=l(注意-定要是完全二又樹)。

全國計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考試試題

1、用Access創(chuàng)建的數(shù)據(jù)庫文件，其擴(kuò)展名是___D___。

A..adp

B..dbf

C..frm

D..mdb

2、數(shù)據(jù)庫系統(tǒng)的核心是___B___。

A.數(shù)據(jù)模型

B.數(shù)據(jù)庫管理系統(tǒng)

C.數(shù)據(jù)庫

D.數(shù)據(jù)庫管理員

3、數(shù)據(jù)庫系統(tǒng)是由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、應(yīng)用程序、___A___、用戶等構(gòu)成的人機(jī)系統(tǒng)。

A.數(shù)據(jù)庫管理員

B.程序員

C.高級(jí)程序員

D.軟件開發(fā)商

4、在數(shù)據(jù)庫中存儲(chǔ)的是___B___。

A.信息

B.數(shù)據(jù)

C.數(shù)據(jù)結(jié)構(gòu)

D.數(shù)據(jù)模型

5、在下面關(guān)于數(shù)據(jù)庫的說法中，錯(cuò)誤的是___D___。

A.數(shù)據(jù)庫有較高的安全性

B.數(shù)據(jù)庫有較高的數(shù)據(jù)獨(dú)立性

C.數(shù)據(jù)庫中的數(shù)據(jù)可以被不同的用戶共享

D.數(shù)據(jù)庫中沒有數(shù)據(jù)冗余

6、下面關(guān)于新型數(shù)據(jù)庫的說法中，錯(cuò)誤的是___C___。

A.數(shù)據(jù)倉庫不是一個(gè)新的平臺(tái)，仍然使用傳統(tǒng)的.數(shù)據(jù)庫管理系統(tǒng)，而是一個(gè)新的概念

B.分布式數(shù)據(jù)庫是一個(gè)數(shù)據(jù)在多個(gè)不同的地理位置存儲(chǔ)的數(shù)據(jù)庫

C.面向?qū)ο髷?shù)據(jù)庫仍然采用傳統(tǒng)的關(guān)系型數(shù)據(jù)庫管理系統(tǒng)

D.空間數(shù)據(jù)庫是隨著地理信息系統(tǒng)gis的開發(fā)和應(yīng)用而發(fā)展起來的數(shù)據(jù)庫新技術(shù)

7、不是數(shù)據(jù)庫系統(tǒng)特點(diǎn)的是___C___。

A.較高的數(shù)據(jù)獨(dú)立性

B.最低的冗余度

C.數(shù)據(jù)多樣性

D.較好的數(shù)據(jù)完整性

8、在下列數(shù)據(jù)庫管理系統(tǒng)中，不屬于關(guān)系型的是___D___。

A.MicorsoftAccess

B.SQLserver

C.Oracle

D.DBTG系統(tǒng)

9、Access是___C___數(shù)據(jù)庫管理系統(tǒng)。

A.層次

B.網(wǎng)狀

C.關(guān)系型

D.樹狀：

10、在Access中，數(shù)據(jù)庫的基礎(chǔ)和核心是__A____。

A.表

B.查詢

C.窗體

D.宏

計(jì)算機(jī)二級(jí)考試《公共基礎(chǔ)知識(shí)》考點(diǎn)

(一)算法

1.算法的基本特征：可行性、確定性、有窮性、擁有足夠的情報(bào)。

2.算法的基本要素：

(1)算法中對(duì)數(shù)據(jù)的運(yùn)算和操作

一個(gè)算法由兩種基本要素組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作;二是算法的控制結(jié)構(gòu)。

在一般的計(jì)算機(jī)系統(tǒng)中，基本的運(yùn)算和操作有以下4類：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算和數(shù)據(jù)傳輸。

(2)算法的控制結(jié)構(gòu)：算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。

描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等。一個(gè)算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。

3.算法的時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。

同一個(gè)算法用不同的語言實(shí)現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，或者在不同的計(jì)算機(jī)上運(yùn)行，效率均不同。這表明使用絕對(duì)的時(shí)間單位衡量算法的效率是不合適的。撇開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法運(yùn)行工作量的大小，只依賴于問題的規(guī)模(通常用整數(shù)n表示)，它是問題規(guī)模的函數(shù)。即

算法的工作量=f(n)

4.算法的空間復(fù)雜度

算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。

一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過程中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間。如果額外空間量相對(duì)于問題規(guī)模來說是常數(shù)，則稱該算法是原地工作的。在許多實(shí)際問題中，為了減少算法所占的存儲(chǔ)空間，通常采用壓縮存儲(chǔ)技術(shù)，以便盡量減少不必要的額外空間。

疑難解答：算法的工作量用什么來計(jì)算?

算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來計(jì)算，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=f(n)，其中n是問題的規(guī)模。

(二)數(shù)據(jù)

(1)數(shù)據(jù)集合中個(gè)數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu);

(2)在對(duì)數(shù)據(jù)元素進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu);

(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。

數(shù)據(jù)：是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。外語學(xué)習(xí)網(wǎng)

數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

數(shù)據(jù)的邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合中的若干關(guān)系來表示。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素的集合，通常記為D;二是D上的關(guān)系，它反映了數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成

B=(D，R)

其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。

數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(也稱數(shù)據(jù)的物理結(jié)構(gòu))。

由于數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，為了表示存放在計(jì)算機(jī)存儲(chǔ)空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系(即前后件關(guān)系)，在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。

一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)，常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，選擇合適的存儲(chǔ)結(jié)構(gòu)是很重要的。

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：

(1)有且只有一個(gè)根結(jié)點(diǎn);

(2)每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。

則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。

疑難解答：空的數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)還是非線性結(jié)構(gòu)?

一個(gè)空的數(shù)據(jù)結(jié)構(gòu)究竟是屬于線性結(jié)構(gòu)還是屬于非線性結(jié)構(gòu)，這要根據(jù)具體情況來確定。如果對(duì)該數(shù)據(jù)結(jié)構(gòu)的算法是按線性結(jié)構(gòu)的規(guī)則來處理的，則屬于線性結(jié)構(gòu);否則屬于非線性結(jié)構(gòu)。

(三)棧與樹

1.棧的基本概念

棧是限定只在一端進(jìn)行插入與刪除的.線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當(dāng)表中沒有元素時(shí)稱為空棧。棧頂元素總是后插入的元素，從而也是最先被刪除的元素;棧底元素總是最先插入的元素，從而也是最后才能被刪除的元素。棧是按照先進(jìn)后出或后進(jìn)先出的原則組織數(shù)據(jù)的。

2.棧的順序存儲(chǔ)及其運(yùn)算

用一維數(shù)組S(1∶m)作為棧的順序存儲(chǔ)空間，其中m為最大容量。

在棧的順序存儲(chǔ)空間S(1∶m)中，S(bottom)為棧底元素，S(top)為棧頂元素。top=0表示?？?top=m表示棧滿。

棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。

(1)入棧運(yùn)算：入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。首先將棧頂指針加一(即top加1)，然后將新元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置時(shí)，說明棧空間已滿，不可能再進(jìn)行入棧操作。這種情況稱為棧上溢錯(cuò)誤。

(2)退棧運(yùn)算：退棧是指取出棧頂元素并賦給一個(gè)指定的變量。首先將棧頂元素(棧頂指針指向的元素)賦給一個(gè)指定的變量，然后將棧頂指針減一(即top減1)。當(dāng)棧頂指針為0時(shí)，說明?？?，不可進(jìn)行退棧操作。這種情況稱為棧的下溢錯(cuò)誤。

(3)讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。這個(gè)運(yùn)算不刪除棧頂元素，只是將它賦給一個(gè)變量，因此棧頂指針不會(huì)改變。當(dāng)棧頂指針為0時(shí)，說明?？眨x不到棧頂元素。

小技巧：棧是按照先進(jìn)后出或后進(jìn)先出的原則組織數(shù)據(jù)，但是出棧方式有多種選擇，在考題中經(jīng)常考查各種不同的出棧方式。

樹及二叉樹的性質(zhì)

誤區(qū)警示：

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

1、樹的基本概念

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

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

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

(1)二叉樹的定義

二叉樹是一種很有用的非線性結(jié)構(gòu)，具有以下兩個(gè)特點(diǎn)：

①非空二叉樹只有一個(gè)根結(jié)點(diǎn);

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

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

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

二叉樹具有以下幾個(gè)性質(zhì)：

性質(zhì)1：在二叉樹的第k層上，最多有2k-1(k≥1)個(gè)結(jié)點(diǎn);

性質(zhì)2：深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn);

性質(zhì)3：在任意一棵二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。

二叉樹的遍歷

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

(1)前序遍歷：先訪問根結(jié)點(diǎn)、然后遍歷左子樹，最后遍歷右子樹;并且，在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。

(2)中序遍歷：先遍歷左子樹、然后訪問根結(jié)點(diǎn)，最后遍歷右子樹;并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。

(3)后序遍歷：先遍歷左子樹、然后遍歷右子樹，最后訪問根結(jié)點(diǎn);并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。

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

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