1、下面分為四個部分進行組織。文中標注了三個星號的，表示非常重要，基本每次考試都是必考；標注了兩個星號或一個星號的，表示也較重要，很容易考到。出現在【】括號中的內容，表示要很精確的背下來的。第一部分算法與數據結構( 歷年比例 41%)1 、算法問題處理方案的正確而完整的描述稱為 【算法】。 算法分析的目的是， 分析算法的效率以求改進。算法的基本特征是【可行性】、【確定性】、【有窮性】和擁有足夠情報。算法的有窮性是指：算法程序的運行時間是有限的。算法的復雜度是衡量算法好壞的度量，分為【時間復雜度】和【空間復雜度】。時間復雜度是指執行算法所需要的 【計算工作量】 ；算法的空間復雜度是指算法執行過程中所

2、需的【存儲空間】。算法時間復雜度或空間復雜度中的一項的值，沒有辦法推出另一項的值。2 、數據結構數據結構分為 【邏輯結構 】和【存儲結構 】。線性結構和非線性結構屬于邏輯結構；順序、鏈式、索引屬于存儲結構 (物理結構 )。循環隊列屬于【存儲結構】。數據的存儲結構 又稱為物理結構，是 數據的邏輯結構在計算機存儲空間中的存放形式。一個邏輯結構可以有多種存儲結構， 且各種存儲結構影響數據處理的效率。 程序執行的效率與數據的存儲結構密切相關。數據結構分為線性結構和非線性結構，帶鏈的隊列屬于【線性結構】。線性表的存儲結構主要分為順序存儲結構和鏈式存儲結構。 順序存儲結構的存儲一定是連續的，鏈式存儲的存儲

3、空間不一定是連續的。有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構。隊列是一種特殊的線性表，循環隊列按照【先進先出】原則組織數據。循環隊列是隊列的【順序】存儲結構。數據的獨立性分為【物理獨立】性和【邏輯獨立性】。當數據的存儲結構改變時，其邏輯結構可以不變，因此，基于邏輯結構的應用程序可以不用修改，稱為【物理獨立性】。3 、棧和隊列棧是一種特殊的線性表，是只能在一端進行插入和刪除的線性表，特點是FILO(FirstInLastOut)。棧是【 先進后出】的線性表；棧具有記憶作用；對棧的插入與刪除操作中，不需要改變【棧底指針】。假定讓元素1 、 2、 3、 A、 B 依次入棧，則出棧的順

4、序是：B、 A、 3、 2、1 。棧與隊列都是線性結構，樹是非線性結構。支持子程序調用的數據結構是【?！俊Ｅc隊列的共同點是，都只允許在【端點處】插入和刪除元素。棧只能順序存儲的描述是 錯誤 的。?？梢杂小卷樞蚝玩準健績煞N存儲方式。隊列是允許在一段插入，在另一端進行刪除的線性表，其特點是【先進先出 】。循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定尾指針為 rear ，容量為maxSize ，則循環隊列中元素的個數是【(rear-front+maxSize)modmaxSize】。循環隊列的頭指針為front ，4 、線性鏈表線性鏈表是線性表的鏈式存儲結構。用鏈表表示線性表的優點是【便于插

5、入和刪除操作】。線性鏈表的存儲空間不一定連續，且各元素的存儲順序是任意的。5 、樹與二叉樹在樹結構中， 一個結點所擁有的后件（繼）稱為樹的度。二叉樹各結點的度 只可能取值度為 1 結點數量的前提下，葉子結點或度為的個數稱為該結點的度， 所有結點中最大的度 0 、 1 、 2 ，不可能是其它值。換言之，知道了 2 的結點中知道其一，就可以求出總的結點數。下面關于計算結點數量的幾個性質，非常重要：(1) 對任意的二叉樹， 葉子結點的數量，比度為 2 的結點數量多一個 ( 換言之，已知葉子結點的數量，減去1 則是度為2 的結點數量；已知度為2 的結點數量，加上1 就是葉子結點數量)(2) 完全二叉樹

6、如果有 N 個結點，當子結點及度為 2 的結點，沒有度為N 為奇數的時候，葉子結點數為 (N+1)/2 ，此時二叉樹只有度為 0 的葉 1 的結點；當 N 為偶數的時候，葉子結點的數量為 N/2 。( 注意條件，必須是完全二叉樹，當然包括滿二叉樹)(3) 滿二叉樹第K 層上的結點數量為2K-1 ；深度為K 的滿二叉樹，結點總數為2 K -1。上述的計算公式，關鍵要能夠應用，例如，深度為7 的滿二叉樹，度為2 的結點數量是多少？既然是滿二叉樹，葉子結點的數量就是第7 層的結點數量，也就是2 6 ，可以算出葉子結點為 64 ，因此度為2 的結點數是63( 葉子結點數減去1) 。二叉樹的前序遍歷、中

7、序遍歷、后續遍歷：前中后三個詞是相對于根來講的，前序是【根 -> 左 -> 右】，中序是【 左 -> 根 -> 右】，后續是【 左 -> 右 -> 根】。具體操作為：先序遍歷 (DLR): 訪問根結點，按先序遍歷左子樹，按先序遍歷右子樹。中序遍歷 (LDR): 按中序遍歷左子樹，訪問根結點，按中序遍歷右子樹。后序遍歷 (LRD): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結點。下面以中序遍歷為例，來講解實際的解題方法：對一棵樹， 將根結點下的左子樹用一個橢圓圈起來，右子樹也用一個橢圓圈起來。之后，在左子樹上標記上1，在根結點標記上2，在右子樹上標記上3。對

8、在左邊橢圓內的左子樹，現在把它單獨拿出來分析。把它的左子樹圈起來標上1.1 ，根結點標記上1.2 ，右子樹標上1.3 。按照上述方法依次往下，直到樹不能拆分，然后按照 “左 -> 根 -> 右 ”的順序寫出結點的訪問先后即可。6 、查找技術對于長度為n 的線性表，順序查找 最壞情況下需要比較 n 次。(對數據是否有序沒有要求)。順序查找最好情況下查詢次數是1，最壞情況下是n，平均為 (1+n)/2 。對于長度為n 的有序線性表 ，二分法 最壞情況下只需要比較log 2n 次。 (數據必須有序)能用二分法進行查找的是【順序存儲的有序線性表】。7 、排序技術對于長度為n 的線性表，【

9、冒泡排序、快速排序、簡單插入排序、簡單選擇排序】這四種排序方式在最壞情況下的比較次數相同，都是【n(n-1)/2】。堆排序 的效率最高，是【nlog 2 n 】。希爾排序最壞情況下需要次比較【 n 1.5 】。希爾排序屬于 【插入類排序法】 。已知數據表 A 中每個元素距最終位置不遠，為節省時間，應該采用的算法是【直接插入排序】。選擇排序、插入排序、快速排序、歸并排序中對內存要求最大的是【歸并排序】。第二部分軟件工程基礎(歷年比例 27%)1 、軟件工程基本概念軟件是包括【程序】、【數據】及【相關文檔】的完整集合，軟件是一種邏輯產品。軟件工程三要素包括【方法、工具和過程】，其中【過程】支持軟件

10、開發的各個環節的控制和管理。軟件工程的核心思想： 把軟件產品當作是一個工程產品來處理， 強調在軟件開發過程中應用【 工程化】 原則。從工程管理角度，軟件設計一般分為兩步完成，它們是【概要設計】和【詳細設計】。軟件生命周期可分為多個階段，一般分為 【定義】 階段、【開發】階段和 【維護】階段，編碼和測試屬于【開發階段】。需求分析階段產生的主要文檔是 【軟件需求規格說明書】 。軟件需求的規格說明書應該有完整性、無歧義性、正確性、可驗證性、可修改性等特征，其中最重要的是【正確性】。2 、結構化分析與設計需求分析的分發有： 【結構化】需求分析方法， 【面向對象】的分析方法。 DFD 是【需求分析階段】

11、可以使用的工具之一。結構化分析的常用工具：數據流圖(DFD) ；數據字典；判定樹；判定表。在結構化分析使用數據流圖 (DFD) 時候，利用【數據字典】對其中的圖形元素進行確切的解釋?！緮祿值洹渴墙Y構化分析的核心。典型的數據流類型有兩種，【交換性】和【事務型】。常見的過程設計工具有：圖形工具 (程序流程圖、 N-S，PAD，HIPO) 、表格工具 (判定表 )、語言工具 (PDL 偽碼 )。內聚性是模塊內部的聯系，耦合性模塊之間的相互聯系的緊密程度。追求目標是：模塊的內聚程度要高，模塊間的耦合程度要盡量弱。即高內聚低耦合。 程序流程圖 中帶有箭頭的線段表示的是【控制流 】。【平行四邊形】 代表

12、輸入輸出， 【矩形】代表處理，菱形代表【判斷】(注意，數據流圖中的箭頭，代表【數據流】) 。符合結構化原則的三種基本控制結構是：【順序結構】，【選擇結構】和【循環結構】。3 、軟件測試與維護軟件測試的目的是盡可能多的發現程序中的錯誤，但是目的才是改正錯誤)不包括改正錯誤。 ( 軟件調試的軟件測試分為靜態測試和動態測試， 其中【靜態測試】是指不執行程序，只對程序文本進行檢查。軟件的動態測試主要包括【黑盒測試】和【白盒測試】。黑盒測試的方法有等價類劃分法，邊界值分析法，錯誤推測法，因果圖；白盒測試主要方法有邏輯覆蓋、基本路徑測試。( 考試時給出一種方法的名字，你要知道屬于白盒還是黑盒)【白盒測試】

13、 的原則之一是保證所測模塊的每一個獨立路徑至少要執行一次。序看做是【路徑的集合】。白盒測試將程軟件測試一般按照四個步驟進行：單元測試，集成測試，驗收測試和系統測試。集成測試應該在【單元測試】之后進行。在模塊測試中，需要為每個被測試的模塊設計【驅動模塊】和【承接模塊】。其中，驅動模塊的作用是將測試的數據傳給被測試的模塊，并顯示結果?！緶y試用例】 是為某個目標而編制的一組測試輸入、執行條件及預期結果。測試用例包括輸入值集和【輸出值集】。診斷和改正程序中的錯誤稱為【程序調試】 ( 或軟件調試 ) ，通常也稱為 Debug 。軟件調試可分為【靜態調試】和【動態調試】。在軟件已經交付使用之后， 為了改正

14、錯誤或滿足新的需要而修改軟件的過程稱為護】。注意軟件維護不屬于軟件生命周期【開發階段】的任務?！拒浖S第三部分數據庫設計基礎( 歷年比例 24%)1 、數據庫系統基本概念數據庫設計的根本目標是要解決 【數據共享問題】 。在數據庫管理技術發展的三個階段中，數據共享最好的是【數據庫系統階段】。數據獨立性最高的階段是【數據庫系統階段】。數據庫系統與文件系統的區別是前者具有【特定的數據模型】。數據庫系統常見的數據模型有層次模型，網絡模型和【關系模型】。數據庫系統的核心是【數據庫管理系統】。DBS 包括 DB 和 DBMS。完整講，數據庫系統數據庫管理員DBA 、硬件平臺和軟件平臺組成。DBS 由數據庫

15、DB、數據庫管理系統DBMS、數據庫 應用系統 的核心是【數據庫維護】。數據庫系統的三級模式結構：內模式處于最底層，它反映了數據在計算機物理結構中的實際存儲形式； 概念模式處于中層，它放映了設計者的數據全局邏輯要求，與軟硬件環境無關；外模式處于最外層，它反映了用戶對數據的要求。在數據庫系統中，用戶所見的數據模式為【外模式】。數據庫設計的四個階段是：需求分析、概念設計、【邏輯設計】和【物理設計】。將圖轉換成關系數據模型屬于【邏輯設計】階段。E-R數據庫管理系統提供的數據語言：數據定義語言言 DCL。 SQL 的全稱是StructuredQueryLanguageDDL，數據操縱語言DML，數據控

16、制語，中文意思是【結構化查詢語言】。2 、數據模型實體之間的聯系用 樹形結構 來表示的模型是 【層次模型】 。采用二維表來表示的是 【關系模型】。在關系數據庫中，把數據表示成二維表，每一個二維表稱為【關系】。在關系數據庫中，用來表示實體之間聯系的是【關系】。將 E-R 圖轉化為關系模式時，實體和聯系都可以表示為【關系】。確定兩個實體之間是一對一、一對多、還是多對多的方法是：選擇實體A，看是否有多個實體 B 與之對應；選擇實體B，看是否有多個實體A 與之對應。例如在“學生學習課程 ”中的兩個實體，學生與課程，一個學生可以學習多門課程，一門課程可以被多個學生學習，所以二者是一種多對多的關系。在 E

17、-R 圖中，用來表示實體的圖形是【矩形】。用來表示【屬性】的圖形是橢圓。用菱形來表示聯系。一個關系表的行稱為【元組】 (或記錄 ) ，列稱為【 屬性 】 (或字段 )。在二維表中，元組的【分量】不能再分為更小的數據線。為了建立一個關系，首先要構造數據的【邏輯關系】。3 、關系代數在交、差、投影中，不改變關系表中的屬性個數但是能減少元組個數的是【交】運算。關系運算的規則(下面介紹的7 種運算，考試的時候一般會考察一種，都要背)(1) 并運算 R S：并運算是 兩個表行上的合并 ，重復的行只出現一次。(2) 交運算 R S：交運算是 選出兩個表中的公共行 。(3) 差運算 R-S：差運算是從表R 中，刪除R 與 S 中都出現過的行。(4) 選擇運算：選出二維表【部分的行】稱為選擇運算。(5) 投影運算：選出二維表【部分的列】稱為投影運算。(6) 連接運算：根據兩個表的共同屬性的值，將它們連接起來，無需去除共同屬性。如果去掉了重復屬性，就稱為自然連接。(7) 笛卡爾乘積：將關系R 中的每一行依次與關系S 中的每一行進行排列組合。注意：除了選擇運算和投影運算操作的是 單個表 之外，其余的元算都需要兩個表 ( 兩個關系 ) 。其中，并運算、交運算和差運算要求兩個關系R 與 S 要具有相同個數的屬性。第四部分程序設計基礎(歷年比例 8%)程序設計總體原則：清晰第一、效率第二。良好程序風