計算機科學被認為比其它科學學科與數學的聯絡更加密切，一些觀察者說計算就是一門數學科學。下面是小編整理的關於計算機二級公共基礎知識錦集，歡迎大家參考!
1.3棧及線性連結串列
考點5 棧及其基本運算
考試連結：
考點5在筆試考試中，是一個必考的內容，在筆試考試中出現的機率為100%，主要是以選擇的形式出現，分值為2分，此考點為重點掌握內容，讀者應該掌握棧的運算 。
1.棧的基本概念
棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當表中沒有元素時稱為空棧。棧頂元素總是後給插入的元素，從而也是最先被刪除的元素;棧底元素總是最先給插入的元素，從而也是最後才能被刪除的元素。棧是按照"先進後出"或"後進先出"的原則組織資料的。
2.棧的順序儲存及其運算
用一維陣列S(1∶m)作為棧的順序儲存空間，其中m為最大容量。
在棧的順序儲存空間S(1∶m)中，S(bottom)為棧底元素，S(top)為棧頂元素。top=0表示棧空;top=m表示棧滿。
棧的基本運算有三種：入棧、退棧與讀棧頂元素。
(1)入棧運算：入棧運算是指在棧頂位置插入一個新元素。首先將棧頂指標加一(即top加1)，然後將新元素插入到棧頂指標指向的位置。當棧頂指標已經指向儲存空間的最後一個位置時，說明棧空間已滿，不可能再進行入棧操作。這種情況稱為棧"上溢"錯誤。
(2)退棧運算：退棧是指取出棧頂元素並賦給一個指定的變數。首先將棧頂元素(棧頂指標指向的元素)賦給一個指定的變數，然後將棧頂指標減一(即top減1)。當棧頂指標為0時，說明棧空，不可進行退棧操作。這種情況稱為棧的"下溢"錯誤。
(3)讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變數。這個運算不刪除棧頂元素，只是將它賦給一個變數，因此棧頂指標不會改變。當棧頂指標為0時，說明棧空，讀不到棧頂元素。
小技巧：棧是按照"先進後出"或"後進先出"的原則組織資料，但是出棧方式有多種選擇，在考題中經常考查各種不同的出棧方式。
考點6 線性連結串列的基本概念
考試連結：
考點6在筆試考試中出現的機率為30%，主要是以選擇的形式出現，分值為2分，此考點為識記內容。重點識記結點的組成。
在鏈式儲存方式中，要求每個結點由兩部分組成：一部分用於存放資料元素值，稱為資料域，另一部分用於存放指標，稱為指標域。其中指標用於指向該結點的前一個或後一個結點(即前件或後件)。
鏈式儲存方式既可用於表示線性結構，也可用於表示非線性結構。
(1)線性連結串列
線性表的鏈式儲存結構稱為線性連結串列。
在某些應用中，對線性連結串列中的每個結點設定兩個指標，一個稱為左指標，用以指向其前件結點;另一個稱為右指標，用以指向其後件結點。這樣的表稱為雙向連結串列。
(2)帶鏈的棧
棧也是線性表，也可以採用鏈式儲存結構。帶鏈的棧可以用來收集計算機儲存空間中所有空閒的儲存結點，這種帶鏈的棧稱為可利用棧。
疑難解答：在鏈式結構中，儲存空間位置關係與邏輯關係是什麼?
在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。
1.4樹與二叉樹
考點7 樹與二叉樹及其基本性質
考試連結：
考點7在筆試考試中，是一個必考的內容，在筆試考試中出現的機率為100%，主要是以選擇的形式出現，有時也有出現在填空題中，分值為2分，此考點為重點掌握內容。重點識記樹及二叉樹的性質。
誤區警示：
滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。應該注意二者的區別。
1、樹的基本概念
樹(tree)是一種簡單的非線性結構。在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點。每一個結點可以有多個後件，它們稱為該結點的子結點。沒有後件的結點稱為葉子結點。
