第一章資料結構與演算法
1.1 演算法
1．演算法的基本特徵：可行性；確定性，有窮性；擁有足夠的情報。，
2．確定性：演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性；
3．演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減鬥遞推技術、回溯法。
4．：通過觀察一些簡單而特殊的情況，最後總結出一般性的結論的演算法的設計方法。
5．演算法時間複雜度是指執行演算法所需要的計算工作量。可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。
6．演算法時間複雜度取決於問題的規模和待處理的資料的初態。
7．如果演算法p呼叫另乙個演算法q，而演算法q又呼叫演算法p，則稱為
8．工程上常用的分治法是減半遞推技術
9．演算法空間複雜度是指執行這個演算法所需要的。
10．如果查詢的x一定在陣列中，此時q=1，則a(n)=(n+1)/2。也就是說，在這種情況下，用順序搜尋法在長度為n的一維陣列中查詢值為x的元素，在平均的情況下需要檢查陣列中一半的元素。如果已知需要查詢的x有一半機會在陣列中，此時q=1/2。
則a(n)=[(n+1)/4]+n/2=3n/4。x不在陣列中時，a(n)=n。.
11．下面程式段的時間複雜度是
for(int i=0;ifor(int j=1;j<=m;j++)
a[i][j]=0;
語句的頻度指的是該語句重複執行的次數，乙個演算法中所有語句的頻度之和構成了該演算法的執行時間。本例中語句:a[i][j]=0;的頻度是n*m，所以該程式段的時間複雜度是：
o(m*n).
12．演算法的基本要素：一是；二是。
13．乙個遞迴的定義可以用遞迴過程求解，也可以用非遞迴過程求解，但單從執行時間來看，通常遞迴過程比非遞迴過程較慢。
14．演算法複雜度：演算法和演算法。
1.2 資料結構的基本基本概念
1．資料結構研究的三個方面：資料的邏輯結構；資料的（物理結構）；資料運算。
2．邏輯結構是資料元素間關係的描述，與所用的計算機無關
3．資料的邏輯關係是指資料元素的關聯。
4．資料的不可分割的基本單位是資料項。
5．資料結構是指相互有關聯的的集合。
6．一般來說，一種資料的邏輯結構根據需要可以表示成多種儲存結構，常用的儲存結構有順序、鏈結、7。索引等儲存結構。而採用不同的儲存結構，其資料處理的效率是不同的。
8．資料的儲存結構是指資料的邏輯結構在計算機儲存空間中的存放形式，與所使用的計算機密切相關
9．根據資料結構中各資料元素之間前後件關係的複雜度，一般將資料結構分為兩大型別：與。
10．在資料結構的圖形表示中，對於資料集合中的每乙個資料元素用中間標有元素值的方框表示，一般稱之為資料結點或
11．插入和刪除是對資料結構的兩種基本運算。除此之外，對資料結構的運算還有查詢、分類、合併、分解、複製和修改等。
12．在資料結構中，用一組位址連續的儲存單元依次儲存資料元素的方式是線性結構。
13．乙個資料結構除了用二元關係表示外，還可以直觀地用表示
1．3 線性表及其順序儲存結構
1．資料元素的位置只取決於自己的[, ]，
2．線性表是由n個資料元素組成的乙個有限序列。刪除乙個元素，平均移動的元素的個數為(n-1+n-2+......+0)/n=(n-1)/2；插入乙個元素，平均移動元素個數為(n+n-1+n-2+......
+1)/n=(n+1)/2，所以總體移動元素個數為[, ]
3．線性表是一種結構，資料元素之間的相對位置是線性的。
4．線性表可以是空表。
5．非空線性表的結構特徵：
（1）且只有乙個根結點a1，它無前件；
（2）有且只有乙個終端結點an，它無後件；
（3）除根結點與終端結點外，其他所有結點有且只有乙個前件，也有且只有乙個後件。結點個數n稱為線性表的長度，當n=0時，稱為空表。
6．線性表的順序儲存結構具有以下兩個基本特點：
（1）線性表中所有元素的所佔的儲存空間是；
（2）線性表中各資料元素在儲存空間中是按依次存放的。
7．ai的儲存位址為：adr(ai)=adr(a1)+(i-1)k,，adr(a1)為第乙個元素的位址，k代表每個元素佔的位元組數。
例：乙個向量第乙個元素的儲存位址是100，每個元素的長度為2，則第5個元素的位址是108
資料元素的儲存位置均取決於第乙個資料元素的儲存位置，即：。
adr(ai)=adr(a1)+(i-1)k
第5個元素的位址：adr(a5)=100+(5-1)x2=108
8．**性表的順序儲存結構下，可以對線性表進行各種處理。主要的運算有：線性表的插入、線性表的刪除、線性表的查詢、線性表的、線性表的分解、線性表的合併、線性表的複製、線性表的逆轉等
9．線性表的儲存結構對於小線性表或者其中元素不常變動的線性表來說是合適的，因為順序儲存的結構比較簡單。
10．採用順序儲存的線性表，順序儲存結構必須占用一片連續的儲存單元，當對其進行插入和刪除操作時需要移動大量的元素，優點是儲存密度大，由於陣列的儲存方式是採用順序儲存的，即占用連續的儲存空間，所以可以用陣列的下標直接訪問。
11．查詢第i-1個結點和第i個結點，在順序表中查詢的時間複雜度為o(1) 速度最快。由於鍊錶結構在空間儲存上的不連續性，在查詢某個結點時，需要從當前結點開始向前或者向後逐個比較查詢，浪費時間，查詢結果的時間複雜度均為o(n)，
12．鏈結儲存不是占用一片連續的儲存空間，所以便於進行插入和刪除操作。
13．線性表的鏈式儲存結構中的每乙個儲存結點不僅含有乙個資料元素，還包括指標，每乙個指標指向乙個與本結點有邏輯關係的結點，此類儲存方式屬於順序儲存。
1．4 棧和佇列
1．棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。
2．棧按照「」（filo）[, ]」（lifo）組織資料，棧具有作用。用top表示棧頂位置，用bottom表示棧底。
3．當乙個棧st （最多元素為maxsize）時，st->top= -1是判斷順序棧為空的條件。st->top=maxsize-1是判斷順序棧為滿的條件。
4．棧的基本運算：（1）插入元素稱為[, ]（2）刪除元素稱為；（3）是將棧頂元素賦給乙個指定的變數，此時指標無變化。棧的基本運算有：
入棧，出棧（刪除棧頂元素），初始化、置空、判斷棧是否為空或滿、提取棧頂元素等，對棧的操作都是在棧頂進行的。
5．通常元素出棧的順序是先取出棧頂元素再，使之指向新的棧頂元素。
6．從乙個迴圈佇列中刪除乙個元素，通常是先取出元素再
7．佇列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。rear指標指向隊尾，front指標指向隊頭。
8．在乙個容量為25的迴圈佇列中，若頭指標front=6，尾指標rear=9，則該迴圈佇列中共有個元素
9．佇列是「」（fifo）[, ]」（lilo）的線性表。
10．佇列運算包括（1）運算：從隊尾插入乙個元素；（2）運算：從隊頭刪除乙個元素。
迴圈佇列：s=0表示佇列空，s=1且front=rear表示佇列滿
11．當迴圈隊列為空（s=0）時，不能進行退隊運算，這種情況稱為
12．棧的基本操作。乙個棧的入棧序列是1,2,3,...,n,其輸出序列為p1，p2，p3，。。。，pn，若p1=n，則pi為n-i+1
當p1=n，即n是最先出棧的，根據棧的運算原理，n必定是最**棧的，那麼輸入順序必定是1,2,3,...,n,則出棧的序列是n,n-1,n-2,...,1
13．設初始輸入序列為1，2，3，4，5，利用乙個棧產生輸出序列，下列b序列是不可能通過棧產生的
由於棧的壓入和退出只能在棧頂進行，所以要使出棧的第乙個數是序列的最後乙個數5，只能先把序列所有元素都壓入棧，但這時出棧序列只能是（a 5，4，3，2，1），所以（b 5，3，4，1，2）選項的出棧序列是錯誤的，應選（b）。當初始序列壓入乙個時，就退出乙個元素，這樣就得到（a）選項的出棧序列1，2，3，4，5；先壓入1，2，3，4四個元素，再退出所有元素，最後壓入5，並退棧這時得到（c）選項的出棧序列4，3，2，1，5；壓入1，2後對後面的元素3，4，5分別壓入乙個退出乙個，這時便得到（d）選項的出棧序列3，4，5，2，1。
1．5 線性鍊錶
1．資料結構分為邏輯結構與儲存結構，線性鍊錶屬於。
2．資料結構中的每乙個結點對應於乙個儲存單元，這種儲存單元（乙個乙個小塊）稱為，簡稱結點。
3．結點由兩部分組成：（1）用於儲存資料元素值，稱為資料域；（2）用於存放指標，稱為，用於指向前乙個或後乙個結點。
4．在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。因此，鏈式儲存結構是雜湊儲存
5．帶頭結點的雙向迴圈鍊錶l為空的條件是：只有該頭結點，即l->next==l 或者 l->prior==l
6．對於鏈式佇列結構，插入元素是在隊尾進行的，只需修改隊尾指標，不需修改隊頭指標。向鏈式佇列中插入乙個結點就是在單鏈表表尾插入乙個結點，同時新插入的結點成為表尾結點。例：
在乙個鏈式佇列中，假設f和r分別為隊頭和隊尾指標，則插入s所指結點的運算是r->next=s;r=s;
7．向鏈式棧中插入乙個結點，就是在單鏈表的表頭插入乙個結點，同時將新結點的位置賦予棧頂指標。例：向乙個棧頂指標為hs的鏈式棧中插入乙個s所指的結點時，則執行s->next=hs;hs=s;
8．線性鍊錶的基本操作：、刪除、查詢、排序。
9．雙向鍊錶每個結點有兩個指標域，這兩個指標分別指向它的前驅結點和。
10．單鏈表中，每個結點都含有乙個指標域，這個指標指向它的下乙個結點。因此訪問單鏈表中的結點時，必須沿著它的逐個進行。
11．由於雙向鍊錶比單鏈表結構複雜，所以在插入和刪除元素時，要修改更多的指標域，相對比較複雜，單向鍊錶和雙向鍊錶在空間儲存上的不連續性決定了兩者都不可以隨機訪問，在雙向鍊錶中由於每個結點包括兩個指標域，其中乙個指向該結點的前驅結點，另乙個指向該結點的後繼結點，因此它既可以直接訪問前驅結點，又可以直接訪問後繼結點，而單鏈表每個結點只有乙個指標域，指向它的後繼結點，所以它只能直接訪問它的下乙個結點，而無法直接訪問它的前乙個結點。所以雙向鍊錶順序訪問相鄰結點更加靈活。
全國計算機等級考試二級公共基礎知識
第1章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...
2019全國計算機等級考試二級公共基礎知識 考試大綱
一 資料結構與演算法 一 基本概念 資料 data 資訊的載體，能夠被計算機識別 儲存和加工處理的物理符號。包括文字型別的資料 如 字母 數字 漢字 和多 型別的資料 如 聲音 動畫 影象 資料元素 data element 是資料的基本單位，有時也稱為元素 結點 頂點 記錄，可以有若干個資料項 字...
全國計算機等級考試二級公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 1 演算法的基本特徵 可行性 確定性，有窮性 擁有足夠的情報。2 確定性 演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性 3 演算法基本設計方法 列舉法 歸納法 遞推 遞迴 減鬥遞推技術 回溯法。4 歸納法 通過觀察一些簡單而特殊的情...