計算機二級公共基礎知識
計算機二級考試包括計算機基礎知識。雖然分值不高但是我們還是要把握好每一分。下面本站小編整理了相關計算機二級公共基礎知識，希望大家喜歡。
1.1棧和隊列
1、棧及其基本運算
棧是限定在一端進行插入與刪除運算的線性表。
在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最後插入的元素，棧底元素總是最先插入的元素。即棧是按照“先進後出”或“後進先出”的原則組織數據的。
棧具有記憶作用。
棧的基本運算：1)插入元素稱為入棧運算;2)刪除元素稱為退棧運算;3)讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。
棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈式棧。
2、隊列及其基本運算
隊列是指允許在一端(隊尾)進入插入，而在另一端(隊頭)進行刪除的線性表。尾指針(Rear)指向隊尾元素，頭指針(front)指向排頭元素的前一個位置(隊頭)。
隊列是“先進先出”或“後進後出”的線性表。
隊列運算包括：1)入隊運算：從隊尾插入一個元素;2)退隊運算：從隊頭刪除一個元素。
循環隊列及其運算：所謂循環隊列，就是將隊列存儲空間的最後一個位置繞到第一個位置，形成邏輯上的'環狀空間，供隊列循環使用。在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的後一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。
循環隊列中元素的個數=rear-front。
1.2 樹與二叉樹
1、樹的基本概念
樹是一種簡單的非線性結構。在樹這種數據結構中，所有數據元素之間的關係具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點。沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
(1)什麼是二叉樹
二叉樹是一種很有用的非線性結構，它具有以下兩個特點：1)非空二叉樹只有一個根結點;2)每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
根據二叉樹的概念可知，二叉樹的度可以為0(葉結點)、1(只有一棵子樹)或2(有2棵子樹)。
(2)二叉樹的基本性質(學吧學吧獨家稿件)
性質1 在二叉樹的第k層上，最多有2k-1(k≥1)個結點。
性質2 深度為m的二叉樹最多有個2m-1個結點。
性質3 在任意一棵二叉樹中，度數為0的結點(即葉子結點)總比度為2的結點多一個。
性質4 具有n個結點的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示取log2n的整數部分。
3、滿二叉樹與完全二叉樹
滿二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。
完全二叉樹：除最後一層外，每一層上的結點數均達到最大值;在最後一層上只缺少右邊的若干結點。
根據完全二叉樹的定義可得出：度為1的結點的個數為0或1。
下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：
完全二叉樹還具有如下兩個特性：
性質5 具有n個結點的完全二叉樹深度為[log2n]+1。
性質6 設完全二叉樹共有n個結點，如果從根結點開始，按層序(每一層從左到右)用自然數1，2，…，n給結點進行編號，則對於編號為k(k=1，2，…，n)的結點有以下結論：
①若k=1，則該結點為根結點，它沒有父結點;若k>1，則該結點的父結點的編號為INT(k/2)。
②若2k≤n，則編號為k的左子結點編號為2k;否則該結點無左子結點(顯然也沒有右子結點)。
③若2k+1≤n，則編號為k的右子結點編號為2k+1;否則該結點無右子結點。
4、二叉樹的存儲結構
在計算機中，二叉樹通常採用鏈式存儲結構。
與線性鏈表類似，用於存儲二叉樹中各元素的存儲結點也由兩部分組成：數據域和指針域。但在二叉樹中，由於每一個元素可以有兩個後件(即兩個子結點)，因此，用於存儲二叉樹的存儲結點的指針域有兩個：一個用於指向該結點的左子結點的存儲地址，稱為左指針域;另一個用於指向該結點的右子結點的存儲地址，稱為右指針域。
一般二叉樹通常採用鏈式存儲結構，對於滿二叉樹與完全二叉樹來説，可以按層序進行順序存儲(註釋1)。
5、二叉樹的遍歷
二叉樹的遍歷是指不重複地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種：
(1)前序遍歷(DLR)：若二叉樹為空，則結束返回。否則：首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹;並且，在遍歷左右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
(2)中序遍歷(LDR)：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹;並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
(3)後序遍歷(LRD)：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。
註釋1：這樣，不僅節省了存儲空間，又能方便地確定每一個結點的父結點與左右子結點的位置，但順序存儲結構對於一般的二叉樹不適用。
