第1章資料結構與演算法
經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度、資料結構的概念、棧、二叉樹的遍歷、二分法查詢，讀者應對此部分進行重點學習。
詳細重點學習知識點：
1．演算法的概念、演算法時間複雜度及空間複雜度的概念
2．資料結構的定義、資料邏輯結構及物理結構的定義
3．棧的定義及其運算、線性鍊錶的儲存方式
4．樹與二叉樹的概念、二叉樹的基本性質、完全二叉樹的概念、二叉樹的遍歷
5．二分查詢法
6．氣泡排序法
1.1演算法
考點1 演算法的基本概念
考試鏈結：
考點1在筆試考試中考核的機率為30%，主要是以填空題的形式出現，分值為2分，此考點為識記內容，讀者還應該了解演算法中對資料的基本運算。
計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。
1．演算法的基本特徵：可行性、確定性、有窮性、擁有足夠的情報。
2．演算法的基本要素：
（1）演算法中對資料的運算和操作
乙個演算法由兩種基本要素組成：一是對資料物件的運算和操作；二是演算法的控制結構。
在一般的計算機系統中，基本的運算和操作有以下4類：算術運算、邏輯運算、關係運算和資料傳輸。
（2）演算法的控制結構：演算法中各操作之間的執行順序稱為演算法的控制結構。
描述演算法的工具通常有傳統流程圖、n-s結構化流程圖、演算法描述語言等。乙個演算法一般都可以用順序、選擇、迴圈3種基本控制結構組合而成。
考點2 演算法複雜度
考試鏈結：
考點2在筆試考試中，是乙個經常考查的內容，在筆試考試**現的機率為70%，主要是以選擇的形式出現，分值為2分，此考點為重點識記內容，讀者還應該識記演算法時間複雜度及空間複雜度的概念。
1.演算法的時間複雜度
演算法的時間複雜度是指執行演算法所需要的計算工作量。
同乙個演算法用不同的語言實現，或者用不同的編譯程式進行編譯，或者在不同的計算機上執行，效率均不同。這表明使用絕對的時間單位衡量演算法的效率是不合適的。撇開這些與計算機硬體、軟體有關的因素，可以認為乙個特定演算法"執行工作量"的大小，只依賴於問題的規模（通常用整數n表示），它是問題規模的函式。
即演算法的工作量=f（n）
2.演算法的空間複雜度
演算法的空間複雜度是指執行這個演算法所需要的記憶體空間。
乙個演算法所占用的儲存空間包括演算法程式所佔的空間、輸入的初始資料所佔的儲存空間以及演算法執行過程中所需要的額外空間。其中額外空間包括演算法程式執行過程中的工作單元以及某種資料結構所需要的附加儲存空間。如果額外空間量相對於問題規模來說是常數，則稱該演算法是原地工作的。
在許多實際問題中，為了減少演算法所佔的儲存空間，通常採用壓縮儲存技術，以便儘量減少不必要的額外空間。
疑難解答：演算法的工作量用什麼來計算？
演算法的工作量用演算法所執行的基本運算次數來計算，而演算法所執行的基本運算次數是問題規模的函式，即演算法的工作量=f（n），其中n是問題的規模。
1.2資料結構的基本概念
考點3 資料結構的定義
考試鏈結：
考點3在筆試考試中，是乙個經常考查的內容，在筆試考試**現的機率為70%，主要是以選擇的形式出現，分值為2分，此考點為識記內容，讀者還應該識記資料的邏輯結構和儲存結構的概念。
資料結構作為計算機的一門學科，主要研究和討論以下三個方面：
（1）資料集合中個資料元素之間所固有的邏輯關係，即資料的邏輯結構；
（2）在對資料元素進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構；
（3）對各種資料結構進行的運算。
資料：是對客觀事物的符號表示，在電腦科學中是指所有能輸入到計算機中並被電腦程式處理的符號的總稱。
資料元素：是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。
資料物件：是性質相同的資料元素的集合，是資料的乙個子集。
資料的邏輯結構是對資料元素之間的邏輯關係的描述，它可以用乙個資料元素的集合和定義在此集合中的若干關係來表示。資料的邏輯結構有兩個要素：一是資料元素的集合，通常記為d；二是d上的關係，它反映了資料元素之間的前後件關係，通常記為r。
乙個資料結構可以表示成
b=（d，r）
其中b表示資料結構。為了反映d中各資料元素之間的前後件關係，一般用二元組來表示。
資料的邏輯結構在計算機儲存空間中的存放形式稱為資料的儲存結構（也稱資料的物理結構）。
由於資料元素在計算機儲存空間中的位置關係可能與邏輯關係不同，因此，為了表示存放在計算機儲存空間中的各資料元素之間的邏輯關係（即前後件關係），在資料的儲存結構中，不僅要存放各資料元素的資訊，還需要存放各資料元素之間的前後件關係的資訊。
一種資料的邏輯結構根據需要可以表示成多種儲存結構，常用的儲存結構有順序、鏈結、索引等儲存結構。而採用不同的儲存結構，其資料處理的效率是不同的。因此，在進行資料處理時，選擇合適的儲存結構是很重要的。
考點4 線性結構與非線性結構
考試鏈結：
考點4在筆試考試中，雖然說不是考試經常考查的內容，但讀者還是對此考點有所了解，在筆試考試**現的機率為30%，主要是以填空題出現的形式出現，分值為2分，此考點為識記內容。
根據資料結構中各資料元素之間前後件關係的複雜程度，一般將資料結構分為兩大型別：線性結構與非線性結構。如果乙個非空的資料結構滿足下列兩個條件：
（1）有且只有乙個根結點；
（2）每乙個結點最多有乙個前件，也最多有乙個後件。
則稱該資料結構為線性結構。線性結構又稱線性表。在乙個線性結構中插入或刪除任何乙個結點後還應是線性結構。如果乙個資料結構不是線性結構，則稱之為非線性結構。
疑難解答：空的資料結構是線性結構還是非線性結構？
乙個空的資料結構究竟是屬於線性結構還是屬於非線性結構，這要根據具體情況來確定。如果對該資料結構的演算法是按線性結構的規則來處理的，則屬於線性結構；否則屬於非線性結構。
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）是一種簡單的非線性結構。在樹結構中，每乙個結點只有乙個前件，稱為父結點，沒有前件的結點只有乙個，稱為樹的根結點。每乙個結點可以有多個後件，它們稱為該結點的子結點。
沒有後件的結點稱為葉子結點。
在樹結構中，乙個結點所擁有的後件個數稱為該結點的度。葉子結點的度為0。在樹中，所有結點中的最大的度稱為樹的度。
2、二叉樹及其基本性質
（1）二叉樹的定義
二叉樹是一種很有用的非線性結構，具有以下兩個特點：
①非空二叉樹只有乙個根結點；
②每乙個結點最多有兩棵子樹，且分別稱為該結點的左子樹和右子樹。
由以上特點可以看出，在二叉樹中，每乙個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每乙個結點的度可以是任意的。另外，二叉樹中的每個結點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，乙個結點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。
當乙個結點既沒有左子樹也沒有右子樹時，該結點即為葉子結點。
（2）二叉樹的基本性質
二叉樹具有以下幾個性質：
性質1：在二叉樹的第k層上，最多有2k-1（k≥1）個結點；
2019全國計算機等級考試二級公共基礎知識 考試大綱
一 資料結構與演算法 一 基本概念 資料 data 資訊的載體，能夠被計算機識別 儲存和加工處理的物理符號。包括文字型別的資料 如 字母 數字 漢字 和多 型別的資料 如 聲音 動畫 影象 資料元素 data element 是資料的基本單位，有時也稱為元素 結點 頂點 記錄，可以有若干個資料項 字...
全國計算機等級考試二級公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 1 演算法的基本特徵 可行性 確定性，有窮性 擁有足夠的情報。2 確定性 演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性 3 演算法基本設計方法 列舉法 歸納法 遞推 遞迴 減鬥遞推技術 回溯法。4 通過觀察一些簡單而特殊的情況，最後...
全國計算機等級考試二級公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 1 演算法的基本特徵 可行性 確定性，有窮性 擁有足夠的情報。2 確定性 演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性 3 演算法基本設計方法 列舉法 歸納法 遞推 遞迴 減鬥遞推技術 回溯法。4 歸納法 通過觀察一些簡單而特殊的情...