第一章資料結構與演算法
【考點1】演算法的基本概念
演算法：是指一組有窮的指令集，是解題方****而完整的描述。演算法不等於程式，也不等於計算方法。
演算法的基本特徵：
確定性，演算法中每一步驟都必須有明確定義，不允許有多義性；
有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止；
可行性，演算法原則上能夠精確地執行；
擁有足夠的情報。
演算法的組成要素：乙個演算法由資料物件的運算和操作以及其控制結構這兩部分組成。
演算法的基本運算和操作：算術運算，邏輯運算，關係運算，資料傳輸。
演算法的基本控制結構：順序，選擇，迴圈。
演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減半遞推技術。
【考點2】演算法的複雜度
演算法效率的度量——演算法的複雜度：時間複雜度和空間複雜度。
演算法時間複雜度：指執行演算法所需要的計算工作量。通常，乙個演算法所用的時間包括編譯時間和執行時間。
演算法空間複雜度：指執行這個演算法所需要的記憶體空間。包括演算法程式所佔的空間，輸入的初始資料所佔的空間，演算法執行過程中所需的額外空間。
空間複雜度和時間複雜度並不相關。
【考點3】資料結構的基本概念
資料：資料是客觀事物的符號表示，是能輸入到計算機中並被計算程式識別和處理的符號的總稱，如文件，聲音，**等。
資料元素：資料元素是資料的基本單位。
資料物件：資料物件是性質相同的資料元素的集合。
資料結構：是指由某一資料物件中所有資料成員之間的關係組成的集合。
【考點4】邏輯結構和儲存結構
資料結構可分為資料的邏輯結構和儲存結構。
資料的邏輯結構是對資料元素之間的邏輯關係的描述，與資料的儲存無關，是面向問題的，是獨立於計算機的。它包括資料物件和資料物件之間的關係。
資料的儲存結構也稱為資料的物理結構，是資料在計算機中的存放的方式，是面向計算機的，它包括資料元素的儲存方式和關係的儲存方式。
資料結構和邏輯結構的關係：一種資料的邏輯結構可以表示成多種儲存結構即資料的邏輯結構和儲存結構不一定一一對應。
常見的儲存結構有：順序，鏈結，索引等。採用不同的儲存結構其資料處理的效率是不同的。
【考點5】線性結構和非線性結構
線性結構的條件（乙個非空資料結構)：（1）有且只有乙個根結點；（2）每乙個結點最多有乙個前件，也最多有乙個後件。
非線性結構：不滿足線性結構條件的資料結構。
棧、佇列、雙向鍊錶是線性結構，樹、二叉樹為非線性結構。
【考點6】線性表及其順序儲存結構
線性表是由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
在複雜線性表中，由若干項資料元素組成的資料元素稱為記錄；由多個記錄構成的線性表稱為檔案。
非空線性表的結構特徵：
（1）有且只有乙個根結點a1，它無前件；
（2）有且只有乙個終端結點an，它無後件；
（3）除根結點與終端結點外，其他所有結點有且只有乙個前件，也有且只有乙個後件。
結點個數n稱為線性表的長度，當n=0時，稱為空表。
線性表的順序儲存結構具有以下兩個基本特點：
（1）線性表中所有元素所佔的儲存空間是連續的；
（2）線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
元素ai的儲存位址為：adr(ai)=adr(a1)+(i-1)*k，adr(a1)為第乙個元素的位址，k代表每個元素佔的位元組數。
順序表的運算：查詢、插入、刪除。
【考點7】線性鍊錶
線性鍊錶是線性表的鏈式儲存結構，資料結構中的每乙個結點對應於乙個儲存單元，這種儲存單元稱為儲存結點，簡稱結點。結點由兩部分組成：(1) 用於儲存資料元素值，稱為資料域；(2) 用於存放指標，稱為指標域，用於指向前乙個或後乙個結點。
在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。
鏈式儲存方式既可用於表示線性結構，也可用於表示非線性結構。
線性單鏈表中，head稱為頭指標，head=null（或0）稱為空表。
雙向鍊錶有兩個指標：左指標（llink）指向前件結點，右指標（rlink）指向後件結點。
迴圈鍊錶：。
線性鍊錶的基本運算：查詢、插入、刪除。
【考點8】棧
1、棧的基本概念
棧是一種特殊的線性表，只允許在表的一端進行插入和刪除的線性表；插入，刪除的一端為棧頂，另一端為棧底；當表中沒有元素時為空棧。
棧是一種後進先出（或先進後出last in first out）的線性表。棧具有記憶功能。棧的例項：火車排程，子彈夾。
2、棧的儲存結構
順序儲存結構：用一組位址連續的儲存單元即一維陣列來儲存；
鏈式儲存：用線性鍊錶來儲存；
3、棧的基本運算
(1) 入棧運算，在棧頂位置插入元素；
(2) 退棧運算，刪除元素(取出棧頂元素並賦給乙個指定的變數)；
(3) 讀棧頂元素，將棧頂元素賦給乙個指定的變數，此時指標無變化。
【考點9】佇列
1.佇列的基本概念
佇列是一種特殊的線性表，只允許在表的一端插入，在另一端刪除，允許插入的一端是隊尾（rear），允許刪除的一端為隊頭（front）；當表中沒有元素是空佇列；佇列是一種先進先出的線性表。(fifo)
2、佇列的儲存結構
順序儲存：一維陣列。
鏈式儲存：線性鍊錶。
3、佇列的運算:
(1) 入隊運算：從隊尾插入乙個元素； (2) 退隊運算：從隊頭刪除乙個元素。
佇列的順序儲存結構一般採用迴圈佇列的形式。迴圈佇列s=0表示隊列為空；s=1且front=rear表示隊滿。
計算迴圈佇列的元素個數：「尾指標減頭指標」，若為負數，再加其容量即可。
【考點10】樹的基本概念
樹是一種非線性結構，是n個結點的有限集。當n=0 時為空樹，n>0時為非空樹。結點的度：結點所擁有的子樹的個數。
葉子結點：度為0的結點。
分支結點：除葉子結點以外的結點。
結點的層次：根結點在第一層，同一層上左右結點的子結點在下一層。
樹的深度：所處層次最大的那個結點的層次。
樹的度：樹中所有結點的度的最大值。
【考點11】二叉樹及其基本性質
1、二叉樹的概念
二叉樹是一種特殊的樹形結構，每個結點最多只有兩棵子樹，且有左右之分不能互換，因此，二叉樹有五種不同的形態，見教材12頁。
2、二叉樹的性質
性質1 在二叉樹的第k層上，最多有2k-1(k≥1）個結點。
性質2 深度為m的二叉樹最多有2m-1個結點。
性質3 在任意一棵二叉樹中，度為0的結點（葉子結點）總是比度為2的結點多乙個。
性質4 具有n個結點的二叉樹，其深度不小於[log2n]+1,其中[log2n]表示為log2n的整數部分。
3、二叉樹的儲存結構：詳見教材第13-14頁。
【考點12】滿二叉樹與完全二叉樹
滿二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第k層上有2k-1個結點，且深度為m的滿二叉樹有2m－1個結點。
完全二叉樹是指這樣的二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。
滿二叉樹是完全二叉樹，而完全二叉樹一般不是滿二叉樹。
【考點13】完全二叉樹的性質
性質1 具有n個結點的完全二叉樹的深度為[log2n]+1。
性質2 完全二叉樹中度為1的結點數為0或1。
【考點14】二叉樹的遍歷
前序遍歷：先訪問根結點、然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
前序遍歷圖5可得：abcdfheg。
中序遍歷：先遍歷左子樹、然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
中序遍歷圖5可得：bafhdcge。
後序遍歷：先遍歷左子樹、然後遍歷右子樹，最後訪問根結點；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。
後序遍歷圖5可得：bhfdgeca。
【考點15】順序查詢
順序查詢是從表的一端開始，依次掃瞄表中的各個元素，並與所要查詢的數進行比較。
在下列兩種情況下也只能採用順序查詢：
（1）如果線性表為無序表，則不管是順序儲存結構還是鏈式儲存結構，只能用順序查詢。
（2）即使是有序線性表，如果採用鏈式儲存結構，也只能用順序查詢。
【考點16】二分查詢
二分查詢的條件：（1）用順序儲存結構 (2)線性表是有序表。
查詢的步驟：詳見教材第16頁。
對於長度為n的有序線性表，在最壞情況下，二分法查詢只需比較log2n次，而順序查詢需要比較n次。
【考點17】排序
1、交換排序
（1）氣泡排序法，在最壞的情況下，氣泡排序需要比較次數為n(n－1)/2。
（2）快速排序法 ，在最壞的情況下，快速排序需要比較次數為n(n－1)/2。
2、插入類排序法：
（1）簡單插入排序法，最壞情況需要n(n-1)/2次比較；
（2）希爾排序法，最壞情況需要o(n1.5)次比較。（大寫o是演算法複雜度的表示方法）
3、選擇類排序法：
（1）簡單選擇排序法，最壞情況需要n(n-1)/2次比較；
（2）堆排序法，最壞情況需要o(nlog2n)次比較。
相比以上幾種(除希爾排序法外)，堆排序法的時間複雜度最小。
第二章程式設計基礎
【考點1】程式設計方法與風格
形成良好的程式設計風格需注意：(詳見教材第19頁)。
1、源程式文件化； 2、資料說明的方法； 3、語句的結構； 4、輸入和輸出。
注釋分序言性注釋和功能性注釋。
語句結構清晰第
一、效率第二。
【考點2】結構化程式設計方法的四條原則
1、自頂向下； 2、逐步求精； 3、模組化； 4、限制使用goto語句。
【考點3】結構化程式的基本結構
順序結構：是最基本、最普通的結構形式，按照程式中的語句行的先後順序逐條執行。
選擇結構：又稱為分支結構，它包括簡單選擇和多分支選擇結構。
迴圈結構：根據給定的條件，判斷是否要重複執行某一相同的或類似的程式段。迴圈結構對應兩類迴圈語句：先判斷後執行的迴圈體稱為當型迴圈結構；先執行迴圈體後判斷的稱為直到型迴圈結構。
公共基礎知識
公共基礎知識.txt花前月下，不如花錢 日 下。葉子的離開，是因為風的追求還是樹的不挽留？乾掉熊貓，我就是國寶！別和我談理想，戒了！1 制度化教育階段開始於 近代。2 各國的學校教育系統基本形成於 19世紀末。3 現在世界上大多數國家的義務教育年限在 9年或9年以上。4 不憤不啟，不悱不發 啟發教學...
公共基礎知識
第一部分馬克思主義哲學 1 哲學 世界觀 方 哲學，是系統化 理論化的世界觀。方 是人們認識世界 改造世界的根本方法。2 哲學的基本問題 哲學的基本問題，包括兩個方面，兩個層次。第一方面，是關於物質和意識誰是第一性 誰是第二性的問題，是劃分唯物主義和唯心主義的根本依據。第二方面，是物質和意識是否具有...
公共基礎知識講義
公共基礎知識主要測查報考者應知應會的基本知識以及運用這些知識分析判斷的基本能力，重點測查對國情社情省情的了解程度 綜合管理基本素質等，涉及政治 經濟 法律 管理 公文 文史 科技 時政省情等方。共基礎知識的特點 1.範圍廣泛，內容龐雜 切忌面面俱到，考察的是廣度，並非深度2.把握重點，有的放矢 法律...