第一章資料結構與演算法
演算法---是一組嚴謹地定義運算順序的規則
演算法的基本要素---一是對資料物件的運算和操作，二是演算法的控制結構
演算法設計基本方法---列舉法、歸納法、遞推、遞迴、減半遞推
演算法的複雜度---包括時間複雜度和空間複雜度
時間複雜度---執行演算法所需的計算工作量
空間複雜度---執行演算法所需的記憶體空間
資料結構---相互有關聯的資料元素的集合。如春、夏、秋、冬；18、11、35、23、16。。。；父親、兒子、女兒等都是資料元素。
前件---資料元素之間的關係，如父親是兒子和女兒的前件
後件---如兒子是父親的後件
結構---指資料元素之間的前後件關係
資料的邏輯結構—是指反映資料元素之間邏輯關係，而與它們在計算機中的儲存位置無關
資料的儲存結構（物理結構）---資料的邏輯結構在計算機儲存空間中的存放形式，資料元素在計算機儲存空間的位置關係可能與邏輯關係不同。
根據資料結構中各資料元素之間前後件關係的複雜程度，可將資料結構分兩類---線性結構與非線性結構
線性結構（線性表）---滿足下列兩個條件（1）有且只有乙個根結點（2）每乙個結點最多有乙個前件和後件。則稱該資料結構為線性結構，否則為非線性結構。
線性表是最簡單、最常用的一種資料結構，其資料元素之間的相對位置是線性的，其儲存方式為順序儲存的，如陣列
棧---是限定在一端進行插入與刪除的線性表，一端封閉，另一端開口，其操作原則是「先進後出」，棧的運算有入棧、退棧、讀棧頂元素
佇列---是指在一端進行插入（稱為隊尾）而在另一端進行刪除（稱為隊頭）的線性表，其操作規則是「先進先出」，其運算有入隊和退隊。
樹---是一種簡單的非線性結構，而且是層次結構，是倒立的大樹，有根結點、父結點、子結點、葉子結點。根結點在第一層，乙個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度，樹的最大層次稱為樹的深度。
二叉樹---（1）非空二叉樹只有乙個根結點（2）每乙個結點最多有兩棵子樹（左子樹和右子樹），其儲存結構為鏈式。
二叉樹性質---（1）k層上最多有2（k-1）個結點（2）深度為m的二叉樹最多有2m-1個結點 （3）度為0的結點（葉子結點）比度為2的結點多乙個（4）具有n個結點的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示對log2n取整
滿二叉樹---除最後一層外，其餘層的結點都有兩個子結點
完全二叉樹---除最後一層外，每一層上的結點數均達到最大值，在最後一層上只缺少右邊的若干結點，葉子結點只可能在層次最大的兩層上出現。滿二叉樹是完全二叉樹，而完全二叉樹不是滿二叉樹。完全二叉樹有兩個性質：
（1）具有n個結點的完全二叉樹的深度為[log2n]+1（2） 二叉樹遍歷---不重複地訪問各個結點。分為前序遍歷(dlr-根左右)、中序遍歷(ldr-左根右)和後序遍歷（lrd-左右根）
查詢技術---順序查詢——對於長度為n的有序線性表，查詢時需要比較n次
二分法查詢——對於長度為n的有序線性表，查詢時需要比較log2n次
排序技術---假設線性表的長度為n，則氣泡排序和簡單插入排序的比較次數（時間複雜度）為n(n-1)/2;希爾排序的比較次數為o(n1.5);簡單選擇排序的比較次數為n(n-1)/2;堆排序的比較次數為o(nlog2n).
習題1演算法的時間複雜度是指（ ），演算法的空間複雜度是指（ ）；
佇列是（先進先出），棧是（先進後出）；
下列二叉樹的遍歷結果：前序遍歷（abdecf）、中序遍歷（dbeafc）、後續遍歷（debfca）；
在深度為5的滿二叉樹中，葉子結點的個數為（16）；設樹t的度為4，其中度為1，2，3；
線性表、棧、佇列、線性鍊錶是（線性結構），樹是（非線性結構）；資料的儲存結構是指（ ）；，4的結點的個數分別為4，2，1，1。則t中的葉子結點的個數為（8）；對於長度為n的有序線性表，順序查詢次數為（n）,二分法查詢次數為（log2n）；一棵完全二叉樹共有700個結點，則在該二叉樹中有（350）個葉子結點；一棵二叉樹的中序遍歷結果為dbeafc，前序遍歷結果為abdecf，則後續遍歷結果為（debfca）；氣泡排序的時間複雜度為（n(n-1)/2）;在乙個容量為15的迴圈佇列中，若頭指標front=6,尾指標rear=9,則該迴圈佇列中共有（3）元素
資料結構與演算法
演算法的基本特性：可行性，確定性，有窮性，擁有足夠的情報。
演算法是指解題方案準確而完善的描述。
演算法複雜度包括時間複雜度和空間複雜度。
時間複雜度：執行演算法所需要的計算機工作量。
空間複雜度：執行演算法所要的記憶體空間。
資料結構分為邏輯結構和儲存結構。常用的儲存結構有順序結構、鏈式儲存結構、索引儲存結構、 資料邏輯結構：反映資料元素之間邏輯關係的資料結構。
資料儲存結構：資料的邏輯結構在計算機儲存空間中的存放形式。
隊：fifo，一頭進，另一頭出來。迴圈佇列，一般題型：概念、計算佇列中還有幾個元素（尾指標減去頭指標）。
棧：filo，只能從乙個頭進，出。一般題型：概念、問a b c d四個選項中不能出棧的次序。
線性表的基本概念。記住線性表頂多有乙個頭節點和乙個後繼節點。所以棧、佇列、單向鍊錶都是線性表，樹、雙向鍊錶不是線性表。
樹；葉子節點最多的個數：2n-1個節點。一共的節點數目2n-1，節點為2的數目為節點為1的數目減一。也就是n2=n0-1
滿二叉樹
完全二叉樹
二叉樹中，度為0的數目比度為2的數目多乙個。 n0=n2+1
二叉樹的前序遍歷、中序遍歷、後序遍歷是考試重點。
順序查詢：長度為n的線性表，平均要進行n/2，最壞要進行n次比較。（常考）
二分查詢：對於長度為n的線性表，在最壞情況進行 log2n 次。
要背的話：
演算法的時間複雜度和空間複雜度沒有必然的聯絡。
乙個資料結構的邏輯結構根據需要可以有多個儲存結構。儲存結構的不同，會造成處理的效率不同。
棧具有記憶性。如果要存的資料是1 2 3 4 5，棧可以不順序儲存。
我們存放資料的時候，儲存空間不一定是連續的，並且各個元素的儲存順序可以是任意的。如：鍊錶。
**性煉表中查詢乙個元素比在順序表中查詢乙個元素要快， 氣泡排序、選擇排序、交換排序、堆排序中平均排序次數最快的是堆排序。
能夠用二分查詢的是順序儲存的有序線性表。
第二章程式設計基礎
結構化程式設計的三種結構---是順序、選擇和迴圈
物件---表示客觀世界的任何實體
類---是具有共同屬性和方法的物件的集合
例項---任何乙個物件都是其對應類的例項
訊息---乙個例項和另乙個例項之間傳遞的資訊
繼承---是指直接獲得已有的性質和特徵，而不必重複定義它們。例如子類繼承父類
結構化程式設計主要強調---程式的易讀性
良好的程式設計風格是---程式應簡單、清晰、可讀性好
程式設計基礎
1、 程式設計方法和技術的發展經過了結構化程式設計和物件導向設計兩個階段。
2、 當今程式設計的風格是「清晰第一，效率第二」。
3、 程式可以沒有輸入，但是一定要有輸出。
4、 結構化程式設計遵循：自頂向下，逐步求精，模組化，限制使用goto語句（常考）。
5、 物件導向的基本特點：標誌唯一性，分類性，多型性，封裝性，模組獨立性。尤其重要的是多型性和封裝性。沒有模擬性。
6、 多型性：統一操作可以是不同物件的行為。同樣的訊息被不同的物件接收時可導致不同的動作的現象。
7、 封裝性：從外面看不到物件的內部，只能看到物件的外部特性。
8、 類：是具有共同屬性、共同方法的物件的集合。描述了屬於該物件型別的所有物件的性質，而乙個物件則是對應類的乙個例項。（常考）
9、 訊息：是指物件間的相互合作的協作機制，是乙個物件與另乙個物件之間的傳遞的訊息。
10、 繼承：是指使用已有的類定義作為基礎建立新類的定義技術。繼承分為單繼承和多繼承。單繼承只有乙個父親，多繼承可以有多個父親。
11、 物件導向中，類的例項叫做物件。
12、 源程式文件化要求程式應該加上注釋。注釋一般為序言性注釋和功能性注釋。
13、 物件導向方法和技術是以物件為核心。
習題2在物件導向方法中，乙個物件請求另乙個物件為其服務的方式是通過傳送（訊息）來實現的
資訊隱蔽的概念與（模組獨立性）概念直接相關（任何物件都具有繼承性）這句話是錯誤的
注釋分為（序言性注釋）和（功能性注釋）
在物件導向方法中，資訊隱蔽是通過物件的（封裝性）來實現的
類是乙個支援整合的抽象資料型別，而物件是類的（例項）
在物件導向方法中，類之間共享屬性和操作的機制稱為（繼承）
第三章軟體工程基礎
軟體生命週期---軟體產品從提出、實現、使用維護到停止使用退役的過程。分為軟體定義、軟體開發、軟體執行維護三個階段。
軟體生命週期的主要活動階段---可行性分析、需求分析、軟體設計、軟體實現、軟體測試、執行和維護。
常見的需求分析方法---
（1）結構化分析方法---主要包括面向資料流的結構化分析方法sa；面向資料結構的jackson方法jsd；面向資料結構的結構化資料系統開發方法dssd。
（2）物件導向的分析方法ooa
結構化分析方法工具---
（1）資料流圖dfd，記住dfd圖的幾個符號：
（2）資料字典dd
（3）判定樹
（4）判定表
程式結構圖（sc），n-s圖，問題分析圖（pad）
程式流程圖（pfd）的幾個符號：
軟體測試---黑盒測試：功能測試
白盒測試：內部結構測試，窮舉路徑測試
軟體工程基礎
1、 軟體工程的核心思想是把軟體當作乙個工程產品來處理。
2、 軟體開發的三個階段以及每個階段的任務：
這個表請大家抽時間背下。軟體開發的三個階段，每個階段的工程。
3、 軟體開發方法包括分析方法，設計方法，程式設計方法。
4、 結構化方法包括結構化分析方法，結構化設計方法，結構化程式設計方法。
5、 結構化分析方法在軟體需求分析階段的應用。
6、 結構化分析常用的工具中最重要的工具是資料流圖。○表示加工，→表示資料流，—資料來源，□表示源。
7、 軟體規格說明書（srs）是需求分析階段的最後結果，是軟體開發文件重要的文件之一。
二級基礎知識公共
第一章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...
二級公共基礎知識
第一章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...
二級公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 演算法 是一組有窮指令集，是解題方 而完整的描述。通俗地說，演算法就是計算機解題的過程。演算法不等於程式，也不等於計算方法，程式的編制不可能優於演算法的設計。演算法是一組嚴謹地定義運算順序的規則，每乙個規則都是有效的，且是明確的，此順序將在有限的次數下終止。所...