計算機二級公共基礎知識

計算機二級考試包括計算機基礎知識。雖然分值不高但是我們還是要把握好每一分。下面百分網小編整理了相關計算機二級公共基礎知識，希望大家喜歡。

計算機二級公共基礎知識

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：這樣，不僅節省了存儲空間，又能方便地確定每一個結點的父結點與左右子結點的位置，但順序存儲結構對于一般的二叉樹不適用。

【計算機二級公共基礎知識】相關文章：