【考點1】算法的基本概念

1、算法：是指一組有窮的指令集，是解題方案的準確而完整的描述。算法不等于程序，也不等于計算方法。

2、算法的基本特征：

1）確定性，算法中每一步驟都必須有明確定義，不允許有多義性；

2）有窮性，算法必須能在有限的時間內做完，即能在執(zhí)行有限個步驟后終止；

3）可行性，算法原則上能夠精確地執(zhí)行；

4）擁有足夠的情報。

3、算法的組成要素：一個算法由數據對象的運算和操作以及其控制結構這兩部分組成。

4、算法的基本運算和操作：算術運算，邏輯運算，關系運算，數據傳輸。

5、算法的基本控制結構：順序，選擇，循環(huán)。

6、算法基本設計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術。

【考點2】算法的復雜度

1、算法效率的度量——算法的復雜度：時間復雜度和空間復雜度。

1）算法時間復雜度：指執(zhí)行算法所需要的計算工作量。通常，一個算法所用的時間包括編譯時間和運行時間。

2）算法空間復雜度：指執(zhí)行這個算法所需要的內存空間。包括算法程序所占的空間，輸入的初始數據所占的空間，算法執(zhí)行過程中所需的額外空間。

空間復雜度和時間復雜度并不相關。

【考點2】算法的復雜度

1、算法效率的度量——算法的復雜度：時間復雜度和空間復雜度。

1）算法時間復雜度：指執(zhí)行算法所需要的計算工作量。通常，一個算法所用的時間包括編譯時間和運行時間。

2）算法空間復雜度：指執(zhí)行這個算法所需要的內存空間。包括算法程序所占的空間，輸入的初始數據所占的空間，算法執(zhí)行過程中所需的額外空間。

空間復雜度和時間復雜度并不相關。

【考點3】數據結構的基本概念

數據：數據是客觀事物的符號表示，是能輸入到計算機中并被計算程序識別和處理的符號的總稱，如文檔，聲音，視頻等。

數據元素：數據元素是數據的基本單位。

數據對象：數據對象是性質相同的數據元素的集合。

數據結構：是指由某一數據對象中所有數據成員之間的關系組成的集合。

【考點4】邏輯結構和存儲結構

1、數據結構可分為數據的邏輯結構和存儲結構。

1）數據的邏輯結構是對數據元素之間的邏輯關系的描述，與數據的存儲無關，是面向問題的，是獨立于計算機的。它包括數據對象和數據對象之間的關系。

2）數據的存儲結構也稱為數據的物理結構，是數據在計算機中的存放的方式，是面向計算機的，它包括數據元素的存儲方式和關系的存儲方式。

2、存儲結構和邏輯結構的關系：一種數據的邏輯結構可以表示成多種存儲結構即數據的邏輯結構和存儲結構不一定一一對應。

3、常見的存儲結構有：順序，鏈接，索引等。采用不同的存儲結構其數據處理的效率是不同的。

【考點5】線性結構和非線性結構

1、線性結構的條件（一個非空數據結構)：

（1）有且只有一個根結點；

（2）每一個結點最多有一個前件，也最多有一個后件。

2、非線性結構：不滿足線性結構條件的數據結構。

棧、隊列、雙向鏈表是線性結構，樹、二叉樹為非線性結構。

【考點6】線性表及其順序存儲結構

1、線性表是由一組數據元素構成，數據元素的位置只取決于自己的序號，元素之間的相對位置是線性的。

2、在復雜線性表中，由若干項數據元素組成的數據元素稱為記錄；由多個記錄構成的線性表稱為文件。

3、非空線性表的結構特征：

（1）有且只有一個根結點a1，它無前件；

（2）有且只有一個終端結點an，它無后件；

（3）除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個后件。

結點個數n稱為線性表的長度，當n=0時，稱為空表。

4、線性表的順序存儲結構具有以下兩個基本特點：

（1）線性表中所有元素所占的存儲空間是連續(xù)的；

（2）線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。

元素ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)*k，ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數。

5、順序表的運算：查找、插入、刪除。

【考點7】線性鏈表

線性鏈表是線性表的鏈式存儲結構，數據結構中的每一個結點對應于一個存儲單元，這種存儲單元稱為存儲結點，簡稱結點。結點由兩部分組成：(1) 用于存儲數據元素值，稱為數據域；(2) 用于存放指針，稱為指針域，用于指向前一個或后一個結點。

在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續(xù)，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。

鏈式存儲方式既可用于表示線性結構，也可用于表示非線性結構。