資料結構與演算法
一、基本概念：
資料(data)：資訊的載體，能夠被計算機識別、儲存和加工處理的物理符號。包括文字型別的資料(如：字母、數字、漢字)和多**型別的資料(如：聲音、動畫、影象)。
資料元素(data element)：是資料的基本單位，有時也稱為元素、結點、頂點、記錄，可以有若干個資料項（字段、域、屬性）組成。
資料結構（data structure）：指的是資料之間的相互關係，即資料的組織形式。其包括三個部分：
1、邏輯結構：資料元素之間的邏輯關係
2、儲存結構：資料元素及其關係在計算機儲存器內的表示。
3、資料的運算（演算法）：即對資料施加的操作
資料的邏輯結構有兩大類：
1、線性結構：
特徵是：若結構是非空集，則有且僅有乙個開始結點和乙個終端結點，並且所有結點最多只有乙個直接前趨和乙個直接後繼。
例：一維陣列、鍊錶、棧、佇列、串
2、非線性結構：
特徵是：乙個結點可能有多個直接前趨和直接後繼。
例：多維陣列、廣義表、樹、圖
資料的儲存結構有以下基本儲存方法：
1、順序儲存方法：
該方法是將邏輯上相鄰的結點儲存在物理位置上相鄰的儲存單元裡，結點間的邏輯關係由儲存單元的鄰接關係來體現，一般通過陣列來實現的。
2、鏈結儲存方法：
該方法不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關係是由附加的指標字段表示的。通過指標型別來實現的。
3、索引儲存方法：
該方法通常是在儲存結點資訊的同時，還建立附加的索引表，索引表中的每一項稱為索引項，索引項的一般形式是：關鍵字，位址。
4、雜湊儲存方法：
該方法的基本思想是根據結點的關鍵字直接計算出該結點的儲存位址，通過雜湊函式實現。例：除餘法雜湊函式、相乘取整法雜湊函式
演算法的基本特徵：
1、可行性(effectiveness)：針對實際問題而設計的演算法，執行後能夠得到滿意的結果。
2、確定性(definiteness)：演算法中的每乙個步驟都必須有明確的定義，不允許出現歧義性。
3、有窮性(finiteness)：演算法必須在有限時間內做完，即必須在執行有限個步驟之後終止。
時間複雜度：該演算法執行的時間耗費，它是該演算法所求解問題規模n的函式。
空間複雜度：該演算法執行時所耗費的儲存空間，它也是問題規模n的函式。
二、線性表：
線性表(linear list)：是由n(n>=0)個資料元素(結點)a1,a2,a3,······,an組成的有限序列。對於非空的線性表，有且僅有乙個開始結點a1，它沒有直接前趨；有且僅有乙個終端結點an，它沒有直接後繼；其餘的結點有且僅有乙個直接前趨結點和乙個直接後繼結點。
線性表的儲存結構：
1、順序儲存(sequential list)：將線性表的結點按邏輯次序依次存放在一組位址連續的儲存單元裡，用這種方法儲存的線性表稱為順序表。
2、鏈式儲存(linked list)：邏輯上相鄰的結點，物理上也相鄰，儲存單元可以是連續的，也可以是不連續的，在儲存每個結點值的同時，還儲存指向其後繼結點的位址，用這種方法儲存的線性表稱為鍊錶。
常見的運算有：
表的初始化、求表的長度、取表中的第i個結點、查詢結點、插入新的結點、刪除結點。
順序表和煉表的比較：
1、基於空間的考慮：
a、順序表的儲存空間是靜態分配的，而鍊錶的儲存空間是動態分配的。
b、順序表佔的儲存空間必須是連續的，而鍊錶佔的儲存空間可以是連續的，也可是不連續的
c、順序表儲存密度為1，而鍊錶中的每個結點，除了資料域外，還要額外的設定指標域，儲存密度小於1
2、基於時間的考慮：
a、在鍊錶中的任何位置上進行插入和刪除，只需要修改指標，而順序表中平均將要移動近一半的結點。
b、順序表是隨機訪問結構，它的訪問時間為o(1)，而鍊錶需從頭結點順著鏈掃瞄鍊錶。
總之，當線性表的長度變化不大，易於事先確定其大小時，為了節約儲存空間，宜採用順序表作為儲存結構；當線性表的長度變化較大，難以估計其儲存規模時，以採用鍊錶作為儲存結構為好。若線性表的操作主要是進行查詢，很少做插入和刪除操作時，採用順序表做儲存結構為宜；對於頻繁進行插入和刪除的線性表，宜採用鍊錶做儲存結構。
例：關於線性表的描述中，錯誤的是（ ）
a、線性表是線性結構 b、線性表的順序儲存結構，必須占用一片連續的儲存單元
c、線性表是單鏈表 d、線性表的鏈式儲存結構，不必占用一片連續的儲存單元
用陣列表示線性表的優點是（ ）
a、便於插入和刪除操作 b、便於隨機訪問
c、可以動態地分配儲存空間 d、不需要占用一片連續的儲存空間
三、棧：
棧(stack)：是限制僅在表的一端進行插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂(top)，另一端稱為棧底(bottom)。當表中沒有元素時稱為空棧。
是一種後進先出的線性表，又稱為lifo表。
棧的基本運算有：
棧的初始化、判棧空、判棧滿、進棧、出棧等
棧的儲存：
順序儲存、鏈式儲存
例：若進棧的輸入序列是a、b、c、d、e，並且在它們進棧的過程中可以進行出棧操作，則不可能出現的出棧序列是（ ）
a、edcba b、decba c、dceab d、abcde
四、佇列：
佇列(queue)：也是一種運算受限的線性表，它只允許在表的一端進行插入，而在另一端進行刪除。允許刪除的一段稱為隊頭(front)，允許插入的一段稱為隊尾(rear)。
（類似於生活中的購物排隊）。是一種先進先出的線性表，又稱為fifo表。
佇列的基本運算：
佇列的初始化、判隊空、判隊滿、入隊、出隊
佇列的儲存實現：
順序儲存、鏈式儲存
例：乙個佇列的入隊序列是1，2，3，4，則佇列的輸出序列是 （ ）
a、4，3，2，1 b、1，2，3，4 c、1，4，3，2 d、3，2，4，1
五、串：
串(string)：是零個或多個字元組成的有限序列。
串中所包含的字元個數稱為該串的長度。
串中任意個連續字元組成的子串行稱為該串的子串，包含子串的串相應地稱為主串
注：空串是任意串的子串，任意串是其自身的子串
串有串常量、串變數之分：
1、串常量在程式中只能被引用但不能改變其值，即只能讀不能寫。
2、串變數其值是可以改變的。
串的基本運算：
求串長、串複製、串聯接、串比較、字元定位、
六、樹（非線性結構）：
樹(tree)：是n(n>=0)個結點的有限集t，t(n=0)為空時稱為空樹，否則它滿足如下兩個條件：
1、有且僅有乙個特定的稱為根(root)的結點
2、其餘的結點可分為m(m>=0)個互不相交的子集t1，t2，…….，tm，其中每個子集本身又是一棵樹，並稱其為根的子樹(subtree)。
在樹的樹形圖表示中，結點通常是用圓圈表示的，結點的名字一般是寫在圓圈旁邊，有時亦可寫在圓圈內。
度(degree)：乙個結點擁有的子樹數稱為該結點的度。一棵樹的度是指該樹中結點的最大度數。
葉子(leaf)：度為零的結點稱為葉子或終端結點
分支結點(node)：度不為零的結點稱為分支結點。
樹中某個結點的子樹之根稱為該結點的孩子(child)結點或子結點，相應的該結點稱為孩子結點的雙親(parents)結點或父結點。
同乙個雙親的孩子稱為兄弟結點(sibling)
結點的層數(level)是從根起算,設根的層數為1,其餘結點的層數等於其雙親結點的層數加1.
樹中結點的最大層數稱為樹的高度(height)或深度(depth).
森林(forest)：是m(m>=0)棵互不相交的樹的集合。刪去一棵樹的根，就得到乙個森林，反之，加上乙個結點作樹根，森林就變為一棵樹。
二叉樹(binary tree)：是n(n>=0)個結點的有限集，它或者是空集(n=0)，或者由乙個根結點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。
二叉樹中，每個結點最多只能有兩棵子樹，並且有左右之分。
二叉樹的五種基本形態：
例：具有3個結點的二叉樹有幾種形態。
滿二叉樹(full binary tree)：一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹
完全二叉樹(complete binary tree)：若一棵二叉樹至多只有最下面的兩層上結點的度數可以小於2，並且最下一層上的結點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。
二叉樹的性質：
性質1：二叉樹第i層上的結點數目最多為2i-1(i>=1)
性質2：深度為k的二叉樹至多有2k-1個結點(k>=1)
性質3：在任意一棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1
性質4：具有n個結點的完全二叉樹的深度為[lgn]+1(取下整) 或 [lg(n+1)](取上整)。
例：一棵二叉樹的結點數為18個，求它的最小高度
已知度為2的結點數為15個，求葉子結點數
二叉樹的遍歷：
遍歷(tr**ersal)：是指沿著某條搜尋路線，依次對樹中每個結點均做一次且僅做一次訪問。
前序遍歷：（又稱為先序遍歷、先根遍歷）
若二叉樹為空，則執行空操作。否則：
1、訪問根結點；
2、前序遍歷左子樹；
3、前序遍歷右子樹。
中序遍歷：（又稱為中根遍歷）
若二叉樹為空，則執行空操作。否則：
1、中序遍歷左子樹；
2、訪問根結點；
3、中序遍歷右子樹。
後序遍歷：（又稱為後根遍歷）
若二叉樹為空，則執行空操作。否則：
1、後序遍歷左子樹；
2、後序遍歷右子樹；
3、訪問根結點。
例：已知一棵二叉樹的中序遍歷序列是：fdgbache，其後序遍歷序列是：fgdbheca
求其前序遍歷序列。
一棵二叉樹的前序遍歷序列為abdgcfk，中序遍歷序列為dgbafck，則結點的後序遍歷序列是（ ）
a、acfkdbg b、gdbfkca c、kcfagdb d、abcdfkg
七、排序(sort)：
所謂排序，就是指整理檔案中的記錄，使之按關鍵字遞增（或遞減）次序排列起來。
氣泡排序(bubble sorting)：
通過對待排序序列從後向前或從前向後(從下標較大的元素開始)，依次比較相鄰元素的排序碼，若發現逆序則交換，使排序碼較大的元素逐漸從前部移向後部或較小的元素逐漸從後部移向前部（從下標較大的單元移向下標較小的單元）。
直接選擇排序(selection sorting)：
掃瞄整個線性表，從中選出最小的元素，將它交換到表的最前面；然後對剩下的子表採用同樣的方法，直到子表空為止。
二級基礎知識公共
第一章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...
二級公共基礎知識
第一章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...
二級公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 演算法 是一組有窮指令集，是解題方 而完整的描述。通俗地說，演算法就是計算機解題的過程。演算法不等於程式，也不等於計算方法，程式的編制不可能優於演算法的設計。演算法是一組嚴謹地定義運算順序的規則，每乙個規則都是有效的，且是明確的，此順序將在有限的次數下終止。所...