計算機二級公共基礎知識總結

　　全國計算機二級考試主要考核使用一種高階計算機語言編寫程式以及上機除錯的基本技能，以下是由小編整理關於的內容，希望大家喜歡!

　　計算機二級總結：資料結構與演算法

　　1.1 演算法

　　演算法：是指解題方案的準確而完整的描述。

　　演算法不等於程式，也不等計算機方法，程式的編制不可能優於演算法的設計。

　　演算法的基本特徵：是一組嚴謹地定義運算順序的規則，每一個規則都是有效的，是明確的，此順序將在有限的次數下終止。特徵包括：

　　***1***可行性;

　　***2***確定性，演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性;

　　***3***有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止，包括合理的執行時間的含義;

　　***4***擁有足夠的情報。

　　演算法的基本要素：一是對資料物件的運算和操作;二是演算法的控制結構。 指令系統：一個計算機系統能執行的所有指令的集合。

　　基本運算和操作包括：算術運算、邏輯運算、關係運算、資料傳輸。 演算法的控制結構：順序結構、選擇結構、迴圈結構。

　　演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減鬥遞推技術、回溯法。 演算法複雜度：演算法時間複雜度和演算法空間複雜度。 演算法時間複雜度是指執行演算法所需要的計算工作量。 演算法空間複雜度是指執行這個演算法所需要的記憶體空間。

　　1.2 資料結構的基本基本概念

　　資料結構研究的三個方面：

　　***1***資料集合中各資料元素之間所固有的邏輯關係，即資料的邏輯結構;

　　***2***在對資料進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構; ***3***對各種資料結構進行的運算。

　　資料結構是指相互有關聯的資料元素的集合。 資料的邏輯結構包含：

　　***1***表示資料元素的資訊;

　　***2***表示各資料元素之間的前後件關係。 資料的儲存結構有順序、連結、索引等。

　　線性結構條件： ***1***有且只有一個根結點; ***2***每一個結點最多有一個前件，也最多有一個後件。 非線性結構：不滿足線性結構條件的資料結構。

　　1.3 線性表及其順序儲存結構

　　線性表由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。 在複雜線性表中，由若干項資料元素組成的資料元素稱為記錄，而由多個記錄構成的線性表又稱為檔案。 非空線性表的結構特徵： ***1***且只有一個根結點a1，它無前件; ***2***有且只有一個終端結點an，它無後件; ***3***除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個後件。結點個數n稱為線性表的長度，當n=0時，稱為空表。 線性表的順序儲存結構具有以下兩個基本特點： ***1***線性表中所有元素的所佔的儲存空間是連續的; ***2***線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。 ai的儲存地址為：ADR***ai***=ADR***a1***+***i-1***k,，ADR***a1***為第一個元素的地址，k代表每個元素佔的位元組數。 順序表的運算：插入、刪除。

　　1.4 棧和佇列

　　棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。 棧按照“先進後出”***FILO***或“後進先出”***LIFO***組織資料，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。 棧的基本運算：***1***插入元素稱為入棧運算;***2***刪除元素稱為退棧運算;***3***讀棧頂元素是將棧頂元素賦給一個指定的變數，此時指標無變化。 佇列是指允許在一端***隊尾***進入插入，而在另一端***隊頭***進行刪除的線性表。Rear指標指向隊尾，front指標指向隊頭。 佇列是“先進行出”***FIFO***或“後進後出”***LILO***的線性表。 佇列運算包括***1***入隊運算：從隊尾插入一個元素;***2***退隊運算：從隊頭刪除一個元素。 迴圈佇列：s=0表示佇列空，s=1且front=rear表示佇列滿