第一章資料結構與演算法
1.1 演算法
演算法：是一組有窮指令集，是解題方****而完整的描述。通俗地說，演算法就是計算機解題的過程。演算法不等於程式，也不等於計算方法，程式的編制不可能優於演算法的設計。
演算法是一組嚴謹地定義運算順序的規則，每乙個規則都是有效的，且是明確的，此順序將在有限的次數下終止。所以其四個基本特徵包括：
（1）確定性，演算法中每一步驟都必須有明確定義，不允許有模稜兩可的解釋，不允許有多義性；
（2）有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止；
（3）可行性，演算法原則上能夠精確地執行；
（4）擁有足夠的情報。
演算法的基本要素：一是對資料物件的運算和操作；二是演算法的控制結構。
指令系統：乙個計算機系統能執行的所有指令的集合。
基本運算和操作包括：算術運算、邏輯運算、關係運算、資料傳輸。
演算法的三種基本控制結構：順序結構、選擇結構、迴圈結構。
演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減半遞推技術、回溯法。
演算法效率的度量—演算法複雜度：演算法時間複雜度和演算法空間複雜度。
演算法時間複雜度：指執行演算法所需要的計算工作量。即演算法執行過程中所需要的基本運算次數。通常，乙個演算法所用的時間包括編譯時間和執行時間。
演算法空間複雜度：指執行這個演算法所需要的記憶體空間。包括演算法程式所佔的空間，輸入的初始資料所佔的空間，演算法執行過程中所需的額外空間。
1.2 資料結構的基本概念
資料結構：指相互有關聯的資料元素的集合。
資料結構研究的三個方面：
（1）資料集合中各資料元素之間所固有的邏輯關係，即資料的邏輯結構；
（2）在對資料進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構；
（3）對各種資料結構進行的運算。
資料的邏輯結構應包含：
（1）表示資料元素的資訊；
（2）表示各資料元素之間的前後件關係(指邏輯關係，與儲存位置無關)。
資料的邏輯結構在計算機儲存空間中的存放形式稱為資料的儲存結構,也稱資料物理結構。
資料的儲存結構有順序、鏈結、索引等。
線性結構的條件，(乙個非空資料結構)：
（1）有且只有乙個根結點； （2）每乙個結點最多有乙個前件，也最多有乙個後件。
非線性結構：不滿足線性結構條件的資料結構。
1.3 線性表及其順序儲存結構
線性表是由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
在複雜線性表中，由若干項資料元素組成的資料元素稱為記錄；
由多個記錄構成的線性表稱為檔案。
非空線性表的結構特徵：
（1）且只有乙個根結點a1，它無前件；
（2）有且只有乙個終端結點an，它無後件；
（3）除根結點與終端結點外，其他所有結點有且只有乙個前件，也有且只有乙個後件。
結點個數n稱為線性表的長度，當n=0時，稱為空表。
線性表的順序儲存結構具有以下兩個基本特點：
（1）線性表中所有元素所佔的儲存空間是連續的；
（2）線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
元素ai的儲存位址為：adr(ai)=adr(a1)+(i-1)k，
adr(a1)為第乙個元素的位址，k代表每個元素佔的位元組數。
順序表的運算：查詢、插入、刪除。
1.4線性鍊錶
資料結構中的每乙個結點對應於乙個儲存單元，這種儲存單元稱為儲存結點，簡稱結點。
結點由兩部分組成：(1) 用於儲存資料元素值，稱為資料域；
(2) 用於存放指標，稱為指標域，用於指向前乙個或後乙個結點。
在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。
鏈式儲存方式即可用於表示線性結構，也可用於表示非線性結構。
線性單鏈表中，head稱為頭指標，head=null（或0）稱為空表。
如果是雙項鍊表的兩指標：左指標（llink）指向前件結點，右指標（rlink）指向後件結點。
線性鍊錶的基本運算：查詢、插入、刪除。
1.5棧和佇列
棧：限定在一端進行插入與刪除的線性表。
其允許插入與刪除的一端稱為棧頂，用指標top表示棧頂位置。
不允許插入與刪除的另一端稱為棧底，用指標bottom表示棧底。
棧按照「先進後出」（filo）或「後進先出」（lifo）組織資料，棧具有記憶作用。
棧的儲存方式有順序儲存和鏈式儲存。
棧的基本運算：(1) 入棧運算，在棧頂位置插入元素；
(2) 退棧運算，刪除元素(取出棧頂元素並賦給乙個指定的變數)；
(3) 讀棧頂元素，將棧頂元素賦給乙個指定的變數，此時指標無變化。
佇列：指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。
用rear指標指向隊尾，用front指標指向隊頭元素的前乙個位置。
佇列是「先進先出」（fifo）或「後進後出」（lilo）的線性表。
佇列運算包括：(1) 入隊運算：從隊尾插入乙個元素； (2) 退隊運算：從隊頭刪除乙個元素。
佇列的順序儲存結構一般採用佇列迴圈的形式。
迴圈佇列s=0表示佇列空；s=1且front=rear表示佇列滿。
計算迴圈佇列的元素個數：「尾指標減頭指標」，若為負數，再加其容量即可。
1.6 樹與二叉樹
樹是一種簡單的非線性結構，其所有元素之間具有明顯的層次特性。
在樹結構中，每乙個結點只有乙個前件，稱為父結點。
沒有前件的結點只有乙個，稱為樹的根結點，簡稱樹的根。
每乙個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，乙個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
二叉樹的特點：(1) 非空二叉樹只有乙個根結點；
(2) 每乙個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
滿二叉樹是指除最後一層外，每一層上的所有結點有兩個子結點，則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。
完全二叉樹是指除最後一層外，每一層上的結點數均達到最大值，在最後一層上只缺少右邊的若干結點。
二叉樹基本性質：（1）在二叉樹的第k層上，最多有2k-1(k≥1)個結點；
2）深度為m的二叉樹最多有2m-1個結點；
3）度為0的結點（即葉子結點）總是比度為2的結點多乙個；
4）具有n個結點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示
取log2n的整數部分
(5) 具有n個結點的完全二叉樹的深度為[log2n]+1；
(6) 設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從
左到右）用自然數1,2,…n給結點進行編號（k=1,2….n），有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為int(k/2)；
②若2k≤n，則k結點的左子結點編號為2k；否則該結點無左子結點（也無右子結點）；
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
補充：增加度為1的結點不會影響二叉樹的葉子結點數，每增加乙個度為2的結點便會增加
乙個葉子結點，沒有度為2的結點時葉子結點數為1。
已知完全二叉樹有x個結點，求其葉子結點數：
①確定層數為k； ②第k層的結點數y=x-(2 k-1-1)；
③第k-1層的葉子結點數n=2 (k-1)-1-y/2《若y/2有餘，則要加1>； ④最後y+n。
二叉樹儲存結構採用鏈式儲存結構，對於滿二叉樹與完全二叉樹可以按層序進行順序儲存。
二叉樹的遍歷：
（1）前序遍歷（dlr），首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；
（樹根在第一，下走不跳結點）
（2）中序遍歷（ldr），首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；
（有左先左，再尋根，後找右。最左邊的結點最先遍歷，最右邊的結點最後遍歷）
（3）後序遍歷（lrd）首先遍歷左子樹，然後訪問遍歷右子樹，最後訪問根結點。
（有左先左，再找右，後尋根，到最右一路上行，樹根在最後）
小結：邏輯結構可分為線性表和非線性表。
線性表包括棧、佇列，其儲存方式為順序儲存、鏈式儲存均可。鏈式型有：線性鍊錶，帶鏈的棧，
帶鏈的佇列，迴圈鍊錶等。
非線性表包括樹(二叉樹)，其儲存方式為鏈式儲存。
1.7 查詢技術
只能使用順序查詢的兩種情況：
（1）線性表為無序表，不管是順序儲存還是鏈式儲存；
（2）表採用鏈式儲存結構，即使是有序線性表。
二分法查詢只適用於順序儲存的有序表，對於長度為n的有序線性表，最壞情況只需比較log2n次，而順序查詢需要比較n次。
1.8 排序技術
排序是指將乙個無序序列整理成按值非遞減順序排列的有序序列。
交換類排序法：（1）氣泡排序法，需要比較的次數為n(n-1)/2；
(2 ) 快速排序法。
插入類排序法：（1）簡單插入排序法，最壞情況需要n(n-1)/2次比較；
(2) 希爾排序法，最壞情況需要o(n1.5)次比較。
選擇類排序法：（1）簡單選擇排序法, 最壞情況需要n(n-1)/2次比較；
(2) 堆排序法，最壞情況需要o(nlog2n)次比較。
相比以上幾種(除希爾排序法外)，堆排序法的時間複雜度最小。
第二章程式設計基礎
2.1 程式設計設計方法和風格
「清晰第
一、效率第二」已成為當今主導的程式設計風格。
形成良好的程式設計風格需注意：(詳見書p27)
1、源程式文件化； 2、資料說明的方法； 3、語句的結構； 4、輸入和輸出。
注釋分序言性注釋和功能性注釋。 語句結構清晰第
一、效率第二。
2.2 結構化程式設計
結構化程式設計方法的四條原則是：
1、自頂向下； 2、逐步求精； 3、模組化； 4、限制使用goto語句。
結構化程式的基本結構及特點：
（1）順序結構：一種簡單的程式設計，最基本、最常用的結構；
（2）選擇結構：又稱分支結構，包括簡單選擇和多分支選擇結構，可根據條件，判斷應該
選擇哪一條分支來執行相應的語句序列；
（3）迴圈結構：又稱重複結構，可根據給定條件，判斷是否需要重複執行某一相同或類似
的程式段。
結構化程式設計的特點：只有乙個入口和出口
2.3 物件導向的程式設計
物件導向的程式設計的首次提出以60年代末挪威奧斯陸大學和挪威計算機中心研製的simula語言為標誌。
物件導向方法的優點：
（1）與人類習慣的思維方法一致； （2）穩定性好； （3）可重用性好；
（4）易於開發大型軟體產品； （5）可維護性好。
物件是物件導向方法中最基本的概念，可以用來表示客觀世界中的任何實體，物件是實體的抽象。
物件導向的程式設計方法中，物件是由資料的容許的操作組成的封裝體，是系統中用來描述客觀事物的乙個實體，是構成系統的乙個基本單位，由一組表示其靜態特徵的屬性和它可執行的一組操作組成。
屬性即物件所包含的資訊，它在設計物件時確定，一般只能通過執行物件的操作來改變。
二級公共基礎知識總結
線性表由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。在複雜線性表中，由若干項資料元素組成的資料元素稱為記錄，而由多個記錄構成的線性表又稱為檔案。非空線性表的結構特徵 1 且只有乙個根結點a1，它無前件 2 有且只有乙個終端結點an，它無後件 3 除根結點與終端結點...
二級基礎知識公共
第一章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...
二級公共基礎知識
第一章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...