第一部分 算法與數據結構 (歷年比例41%)

　　1、算法

　　◆ 問題處理方案的正確而完整的描述稱為【算法】。算法分析的目的是，分析算法的效率以求改進。算法的基本特征是【可行性】、【確定性】、【有窮性】和擁有足夠情報。

　　◆ 算法的有窮性是指：算法程序的運行時間是有限的。

　　◆ 算法的復雜度是衡量算法好壞的度量，分為【時間復雜度】和【空間復雜度】。

　　★★ 時間復雜度是指執行算法所需要的【計算工作量】;算法的空間復雜度是指算法執行過程中所需的【存儲空間】。

　　◆ 算法時間復雜度或空間復雜度中的一項的值，沒有辦法推出另一項的值。

　　2、數據結構

　　◆ 數據結構分為【邏輯結構】和【存儲結構】。線性結構和非線性結構屬于邏輯結構;順序、鏈式、索引屬于存儲結構(物理結構)。循環隊列屬于【存儲結構】。

　　★ 數據的存儲結構又稱為物理結構，是數據的邏輯結構在計算機存儲空間中的存放形式。

　　◆ 一個邏輯結構可以有多種存儲結構，且各種存儲結構影響數據處理的效率。程序執行的效率與數據的存儲結構密切相關。

　　◆ 數據結構分為線性結構和非線性結構，帶鏈的隊列屬于【線性結構】。

　　◆ 線性表的存儲結構主要分為順序存儲結構和鏈式存儲結構。順序存儲結構的存儲一定是連續的，鏈式存儲的存儲空間不一定是連續的。

　　◆ 有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構。

　　◆ 隊列是一種特殊的線性表，循環隊列按照【先進先出】原則組織數據。循環隊列是隊列的【順序】存儲結構。

　　◆ 數據的獨立性分為【物理獨立】性和【邏輯獨立性】。當數據的存儲結構改變時，其邏輯結構可以不變，因此，基于邏輯結構的應用程序可以不用修改，稱為【物理獨立性】。

　　3、棧和隊列

　　★★ 棧是一種特殊的線性表，是只能在一端進行插入和刪除的線性表，特點是FILO(First In Last Out)。

　　★★ 棧是【先進后出】的線性表;棧具有記憶作用;對棧的插入與刪除操作中，不需要改變【棧底指針】。假定讓元素1、2、3、A、B依次入棧，則出棧的順序是：B、A、3、2、1。

　　◆ 棧與隊列都是線性結構，樹是非線性結構。支持子程序調用的數據結構是【棧】。

　　◆ 棧與隊列的共同點是，都只允許在【端點處】插入和刪除元素。

　　◆ 棧只能順序存儲的描述是錯誤的。棧可以有【順序和鏈式】兩種存儲方式。

　　★★ 隊列是允許在一段插入，在另一端進行刪除的線性表，其特點是【先進先出】。

　　◆ 循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定。循環隊列的頭指針為front，尾指針為rear，容量為maxSize，則循環隊列中元素的個數是【 (rear-front+maxSize) mod maxSize】。

　　4、線性鏈表

　　◆ 線性鏈表是線性表的鏈式存儲結構。用鏈表表示線性表的優點是【便于插入和刪除操作】。

　　◆ 線性鏈表的存儲空間不一定連續，且個元素的存儲順序是任意的。

　　5、樹與二叉樹

　　◆ 在樹結構中，一個結點所擁有的后件(繼)的個數稱為該結點的度，所有結點中最大的度稱為樹的度。二叉樹各結點的度只可能取值0、1、2，不可能是其它值。換言之，知道了度為1結點數量的前提下，葉子結點或度為2的結點中知道其一，就可以求出總的結點數。

　　★★★下面關于計算結點數量的幾個性質，非常重要：

　　(1)對任意的二叉樹，葉子結點的數量，比度為2的結點數量多一個(換言之，已知葉子結點的數量，減去1則是度為2的結點數量;已知度為2的結點數量，加上1就是葉子結點數量)

　　(2)完全二叉樹如果有N個結點，當N為奇數的時候，葉子結點數為(N+1)/2，此時二叉樹只有度為0的葉子結點及度為2的結點，沒有度為1的結點;當N為偶數的時候，葉子結點的數量為N/2。(注意條件，必須是完全二叉樹，當然包括滿二叉樹)

　　(3)滿二叉樹第K層上的結點數量為2K-1;深度為K的滿二叉樹，結點總數為2K-1。

　　上述的計算公式，關鍵要能夠應用，例如，深度為7的滿二叉樹，度為2的結點數量是多少?既然是滿二叉樹，葉子結點的數量就是第7層的結點數量，也就是26，可以算出葉子結點為64，因此度為2的結點數是63(葉子結點數減去1)。

　　★★★ 二叉樹的前序遍歷、中序遍歷、后續遍歷：前中后三個詞是相對于根來講的，前序是【根-->左-->右】，中序是【左-->根-->右】，后續是【左-->右-->根】。具體操作為：

　　先序遍歷(D L R): 訪問根結點，按先序遍歷左子樹，按先序遍歷右子樹。

　　中序遍歷(L D R): 按中序遍歷左子樹，訪問根結點，按中序遍歷右子樹。

　　后序遍歷(L R D): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結點。

　　下面以中序遍歷為例，來講解實際的解題方法：對一棵樹，將根結點下的左子樹用一個橢圓圈起來，右子樹也用一個橢圓圈起來。之后，在左子樹上標記上1，在根結點標記上2，在右子樹上標記上3。對在左邊橢圓內的左子樹，現在把它單獨拿出來分析。把它的左子樹圈起來標上1.1，根結點標記上1.2，右子樹標上1.3。按照上述方法依次往下，直到樹不能拆分，然后按照“左-->根--->右”的順序寫出結點的訪問先后即可。

　　6、查找技術

　　◆ 對于長度為n的線性表，順序查找最壞情況下需要比較n次。(對數據是否有序沒有要求)。◆ 順序查找最好情況下查詢次數是1，最壞情況下是n，平均為(1+n)/2。

　　★★ 對于長度為n的有序線性表，二分法最壞情況下只需要比較log2n次。(數據必須有序)

　　◆ 能用二分法進行查找的是【順序存儲的有序線性表】。

　　7、排序技術

　　★★ 對于長度為n的線性表，【冒泡排序、快速排序、簡單插入排序、簡單選擇排序】這四種排序方式在最壞情況下的比較次數相同，都是【n(n-1)/2】。堆排序的效率最高，是【nlog2n】。★★ 希爾排序最壞情況下需要次比較【n1.5】。希爾排序屬于【插入類排序法】。

　　◆ 已知數據表A中每個元素距最終位置不遠，為節省時間，應該采用的算法是【直接插入排序】。選擇排序、插入排序、快速排序、歸并排序中對內存要求最大的是【歸并排序】。