問題處理方案的正確而完整的描述稱為算法。算法分析的目的是，分析算法的效率以求改進。算法的基本特征是可行性、確定性、有窮性和擁有足夠情報。
算法的有窮性是指：算法程序的運行時間是有限的。
算法的復雜度是衡量算法好壞的度量，分為時間復雜度和空間復雜度。
時間復雜度是指執行算法所需要的計算工作量；算法的空間復雜度是指算法執行過程中所需的存儲空間。
算法時間復雜度或空間復雜度中的壹項的值，沒有辦法推出另壹項的值。
2、數據結構
索引屬於存儲結構(物理結構)。循環隊列屬於存儲結構。
數據的存儲結構又稱為物理結構，是數據的邏輯結構在計算機存儲空間中的存放形式。
壹個邏輯結構可以有多種存儲結構，且各種存儲結構影響數據處理的效率。程序執行的效率與數據的存儲結構密切相關。
數據結構分為線性結構和非線性結構，帶鏈的隊列屬於線性結構。
線性表的存儲結構主要分為順序存儲結構和鏈式存儲結構。順序存儲結構的存儲壹定是連續的，鏈式存儲的存儲空間不壹定是連續的。
有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構。
隊列是壹種特殊的線性表，循環隊列按照先進先出原則組織數據。循環隊列是隊列的順序存儲結構。
數據的獨立性分為物理獨立性和邏輯獨立性。當數據的存儲結構改變時，其邏輯結構可以不變，因此，基於邏輯結構的應用程序可以不用修改，稱為物理獨立性。
3、棧和隊列
棧是壹種特殊的線性表，是只能在壹端進行插入和刪除的線性表，特點是先進後出
棧是先進後出的線性表；棧具有記憶作用；對棧的插入與刪除操作中，不需要改變棧底指針。假定讓元素1、2、3、A、B依次入棧，則出棧的順序是：B、A、3、2、1。
棧與隊列都是線性結構，樹是非線性結構。支持子程序調用的數據結構是棧。
棧與隊列的***同點是，都只允許在端點處插入和刪除元素。
棧只能順序存儲的描述是錯誤的。棧可以有順序和鏈式兩種存儲方式。
隊列是允許在壹段插入，在另壹端進行刪除的線性表，其特點是先進先出。
循環隊列中元素的個數是由隊頭指針和隊尾指針***同決定。循環隊列的頭指針為front，尾指針為rear，容量為maxSize，則循環隊列中元素的個數是 (rear-front+maxSize) mod maxSize。
4、線性鏈表
線性鏈表是線性表的鏈式存儲結構。用鏈表表示線性表的優點是便於插入和刪除操作。
線性鏈表的存儲空間不壹定連續，且個元素的存儲順序是任意的。
5、樹與二叉樹
在樹結構中，壹個結點所擁有的後件（繼）的個數稱為該結點的度，所有結點中最大的度稱為樹的度。二叉樹各結點的度只可能取值0、1、2，不可能是其它值。換言之，知道了度為1結點數量的前提下，葉子結點或度為2的結點中知道其壹，就可以求出總的結點數。
上述的計算公式，關鍵要能夠應用，例如，深度為7的滿二叉樹，度為2的結點數量是多少？既然是滿二叉樹，葉子結點的數量就是第7層的結點數量，也就是26，可以算出葉子結點為64，因此度為2的結點數是63(葉子結點數減去1)。
二叉樹的前序遍歷、中序遍歷、後續遍歷：前中後三個詞是相對於根來講的，前序是根-->左-->右，中序是左-->根-->右，後續是左-->右-->根。具體操作為：
先序遍歷(D L R): 訪問根結點，按先序遍歷左子樹，按先序遍歷右子樹。
中序遍歷(L D R): 按中序遍歷左子樹，訪問根結點，按中序遍歷右子樹。
後序遍歷(L R D): 按後序遍歷左子樹，按後序遍歷右子樹，訪問根結點。
下面以中序遍歷為例，來講解實際的解題方法：對壹棵樹，將根結點下的左子樹用壹個橢圓圈起來，右子樹也用壹個橢圓圈起來。之後，在左子樹上標記上1，在根結點標記上2，在右子樹上標記上3。對在左邊橢圓內的左子樹，現在把它單獨拿出來分析。把它的左子樹圈起來標上1.1，根結點標記上1.2，右子樹標上1.3。按照上述方法依次往下，直到樹不能拆分，然後按照“左-->根--->右”的順序寫出結點的訪問先後即可。
6、查找技術
對於長度為n的線性表，順序查找最壞情況下需要比較n次。(對數據是否有序沒有要求)。◆ 順序查找最好情況下查詢次數是1，最壞情況下是n，平均為(1+n)/2。
對於長度為n的有序線性表，二分法最壞情況下只需要比較log2n次。(數據必須有序)
能用二分法進行查找的是順序存儲的有序線性表。
7、排序技術
對於長度為n的線性表，冒泡排序、快速排序、簡單插入排序、簡單選擇排序這四種排序方式在最壞情況下的比較次數相同，都是n(n-1)/2。堆排序的效率最高，是nlog2n。★★ 希爾排序最壞情況下需要次比較n1.5。希爾排序屬於插入類排序法。
已知數據表A中每個元素距最終位置不遠，為節省時間，應該采用的算法是直接插入排序。選擇排序、插入排序、快速排序、歸並排序中對內存要求最大的是歸並排序。
第二部分 軟件工程基礎
1、軟件工程基本概念
軟件是包括程序、數據及相關文檔的完整集合，軟件是壹種邏輯產品。軟件工程三要素包括方法、工具和過程，其中過程支持軟件開發的各個環節的控制和管理。
軟件工程的核心思想：把軟件產品當作是壹個工程產品來處理，強調在軟件開發過程中應用工程化原則。
從工程管理角度，軟件設計壹般分為兩步完成，它們是概要設計和詳細設計。
軟件生命周期可分為多個階段，壹般分為定義階段、開發階段和維護階段，編碼和測試屬於開發階段。
需求分析階段產生的主要文檔是軟件需求規格說明書。軟件需求的規格說明書應該有完整性、無歧義性、正確性、可驗證性、可修改性等特征，其中最重要的是正確性。
2、結構化分析與設計
需求分析的分發有：結構化需求分析方法，面向對象的分析方法。DFD是需求分析階段可以使用的工具之壹。
結構化分析的常用工具：數據流圖(DFD)；數據字典；判定樹；判定表。
在結構化分析使用數據流圖(DFD)時候，利用數據字典對其中的圖形元素進行確切的解釋。數據字典是結構化分析的核心。
典型的數據流類型有兩種，交換性和事務型。
常見的過程設計工具有：圖形工具(程序流程圖、N-S，PAD，HIPO)、表格工具(判定表)、語言工具(PDL偽碼)。
內聚性是模塊內部的聯系，耦合性模塊之間的相互聯系的緊密程度。
追求目標是：模塊的內聚程度要高，模塊間的耦合程度要盡量弱。即高內聚低耦合。
程序流程圖中帶有箭頭的線段表示的是控制流。平行四邊形代表輸入輸出，矩形代表處理，菱形代表判斷(註意，數據流圖中的箭頭，代表數據流)。
符合結構化原則的三種基本控制結構是：順序結構，選擇結構和循環結構。
3、軟件測試與維護
軟件測試的目的是盡可能多的發現程序中的錯誤，但是不包括改正錯誤。(軟件調試的目的才是改正錯誤)
軟件測試分為靜態測試和動態測試，其中靜態測試是指不執行程序，只對程序文本進行檢查。軟件的動態測試主要包括黑盒測試和白盒測試。
黑盒測試的方法有等價類劃分法，邊界值分析法，錯誤推測法，因果圖；白盒測試主要方法有邏輯覆蓋、基本路徑測試。(考試時給出壹種方法的名字，妳要知道屬於白盒還是黑盒)
白盒測試的原則之壹是保證所測模塊的每壹個獨立路徑至少要執行壹次。白盒測試將程序看做是路徑的集合。
軟件測試壹般按照四個步驟進行：單元測試，集成測試，驗收測試和系統測試。集成測試應該在單元測試之後進行。
在模塊測試中，需要為每個被測試的模塊設計驅動模塊和承接模塊。其中，驅動模塊的作用是將測試的數據傳給被測試的模塊，並顯示結果。
測試用例是為某個目標而編制的壹組測試輸入、執行條件及預期結果。測試用例包括輸入值集和輸出值集。
診斷和改正程序中的錯誤稱為程序調試(或軟件調試)，通常也稱為Debug。軟件調試可分為靜態調試和動態調試。
在軟件已經交付使用之後，為了改正錯誤或滿足新的需要而修改軟件的過程稱為軟件維護。註意軟件維護不屬於軟件生命周期開發階段的任務。
第三部分 數據庫設計基礎 (歷年比例24%)
1、數據庫系統基本概念
數據庫設計的根本目標是要解決數據***享問題。在數據庫管理技術發展的三個階段中，數據***享最好的是數據庫系統階段。數據獨立性最高的階段是數據庫系統階段。
數據庫系統與文件系統的區別是前者具有特定的數據模型。
數據庫系統常見的數據模型有層次模型，網絡模型和關系模型。
數據庫系統的核心是數據庫管理系統。
DBS包括DB和DBMS。完整講，數據庫系統DBS由數據庫DB、數據庫管理系統DBMS、數據庫管理員DBA、硬件平臺和軟件平臺組成。
數據庫應用系統的核心是數據庫維護。
形式；概念模式處於中層，它放映了設計者的數據全局邏輯要求，與軟硬件環境無關；
外模式處於最外層，它反映了用戶對數據的要求。
在數據庫系統中，用戶所見的數據模式為外模式。
數據庫設計的四個階段是：需求分析、概念設計、邏輯設計和物理設計。將E-R圖轉換成關系數據模型屬於邏輯設計階段。
數據庫管理系統提供的數據語言：數據定義語言DDL，數據操縱語言DML，數據控制語言DCL。SQL的全稱是Structured Query Language，中文意思是結構化查詢語言。
2、數據模型
實體之間的聯系用樹形結構來表示的模型是層次模型。采用二維表來表示的是關系模型。在關系數據庫中，把數據表示成二維表，每壹個二維表稱為關系。
在關系數據庫中，用來表示實體之間聯系的是關系。
將E-R圖轉化為關系模式時，實體和聯系都可以表示為關系。
確定兩個實體之間是壹對壹、壹對多、還是多對多的方法是：選擇實體A，看是否有多個實體B與之對應；選擇實體B，看是否有多個實體A與之對應。例如在“學生學習課程”中的兩個實體，學生與課程，壹個學生可以學習多門課程，壹門課程可以被多個學生學習，所以二者是壹種多對多的關系。
在E-R 圖中，用來表示實體的圖形是矩形。用來表示屬性的圖形是橢圓。用菱形來表示聯系。
壹個關系表的行稱為元組(或記錄)，列稱為屬性(或字段)。
在二維表中，元組的分量不能再分為更小的數據線。
為了建立壹個關系，首先要構造數據的邏輯關系。
3、關系代數
在交、差、投影中，不改變關系表中的屬性個數但是能減少元組個數的是交運算。
關系運算的規則(下面介紹的7種運算，考試的時候壹般會考察壹種，都要背)
(1)並運算R∪S：並運算是兩個表行上的合並，重復的行只出現壹次。
(2)交運算R∩S：交運算是選出兩個表中的公***行。
(3)差運算R-S：差運算是從表R中，刪除R與S中都出現過的行。
(4)選擇運算：選出二維表部分的行稱為選擇運算。
(5)投影運算：選出二維表部分的列稱為投影運算。
(6)連接運算：根據兩個表的***同屬性的值，將它們連接起來，無需去除***同屬性。如果去掉了重復屬性，就稱為自然連接。
(7)笛卡爾乘積：將關系R中的每壹行依次與關系S中的每壹行進行排列組合。
註意：除了選擇運算和投影運算操作的是單個表之外，其余的元算都需要兩個表(兩個關系)。其中，並運算、交運算和差運算要求兩個關系R與S要具有相同個數的屬性。
第四部分 程序設計基礎
程序設計總體原則：清晰第壹、效率第二。
良好程序風格包括：源程序要文檔化，數據說明的次序要規範化，避免濫用goto語句。
結構化程序設計的核心是算法，面向對象的核心是對象(類)。
結構化程序設計的基本原則是：自頂向下、逐步求精、模塊化、限制使用Goto語句。
類是壹組具有相同屬性和相同操作的對象的集合。面向對象模型中，最基本的概念是對象和類。在面向對象方法中，類的實例稱為對象，實現信息隱藏是通過對象的封裝。
繼承提高了軟件的可重用性。
對象是屬性和方法的封裝體，對象間的通訊靠消息傳遞，操作是對象的動態性屬性。
第壹套
(1) 下面敘述正確的是______。(C)
A. 算法的執行效率與數據的存儲結構無關
B. 算法的空間復雜度是指算法程序中指令（或語句）的條數（指的是算法所占用的空間）
C. 算法的有窮性是指算法必須能在執行有限個步驟之後終止
D. 以上三種描述都不對
(2) 以下數據結構中不屬於線性數據結構的是______。(C)
A. 隊列
B. 線性表
C. 二叉樹
D. 棧
(3) 在壹棵二叉樹上第5層的結點數最多是______。(B)2n-1
A. 8
B. 16
C. 32
D. 15
(4) 下面描述中，符合結構化程序設計風格的是______。(A)
A. 使用順序、選擇和重復（循環）三種基本控制結構表示程序的控制邏輯
B. 模塊只有壹個入口，可以有多個出口(可以有0個入口)
C. 註重提高程序的執行效率
D. 不使用goto語句（只是限制使用）
(5) 下面概念中，不屬於面向對象方法的是______。(D)
A. 對象
B. 繼承
C. 類
D. 過程調用
(6) 在結構化方法中，用數據流程圖（DFD）作為描述工具的軟件開發階段是______。(B)
A. 可行性分析 B. 需求分析C. 詳細設計D. 程序編碼
(7) 在軟件開發中，下面任務不屬於設計階段的是______。(D)
A. 數據結構設計
B. 給出系統模塊結構
C. 定義模塊算法
D. 定義需求並建立系統模型
(8) 數據庫系統的核心是______。(B)
A. 數據模型
B. 數據庫管理系統
C. 軟件工具
D. 數據庫
(9) 下列敘述中正確的是______。(C)
A. 數據庫是壹個獨立的系統，不需要操作系統的支持
B. 數據庫設計是指設計數據庫管理系統
C. 數據庫技術的根本目標是要解決數據***享的問題
D. 數據庫系統中，數據的物理結構必須與邏輯結構壹致
(10) 下列模式中，能夠給出數據庫物理存儲結構與物理存取方法的是______。(A)
A. 內模式 B. 外模式 C. 概念模式D. 邏輯模式
第二套
(1) 算法的時間復雜度是指______。(C)
A. 執行算法程序所需要的時間
B. 算法程序的長度
C. 算法執行過程中所需要的基本運算次數
D. 算法程序中的指令條數
(2) 下列敘述中正確的是______。(A)
A. 線性表是線性結構
B. 棧與隊列是非線性結構
C. 線性鏈表是非線性結構
D. 二叉樹是線性結構
(3) 設壹棵完全二叉樹***有699個結點，則在該二叉樹中的葉子結點數為______。(B)
A. 349
B. 350
C. 255
D. 351
(4) 結構化程序設計主要強調的是______。(B)
A. 程序的規模
B. 程序的易讀性
C. 程序的執行效率
D. 程序的可移植性
(5) 在軟件生命周期中，能準確地確定軟件系統必須做什麽和必須具備哪些功能的階段是______。(D)
A. 概要設計
B. 詳細設計
C. 可行性分析
D. 需求分析
(6) 數據流圖用於抽象描述壹個軟件的邏輯模型，數據流圖由壹些特定的圖符構成。下列圖符名標識的圖符不屬於數據流圖合法圖符的是______。(A)
A. 控制流
B. 加工
C. 數據存儲
D. 源和潭
(7) 軟件需求分析階段的工作，可以分為四個方面：需求獲取、需求分析、編寫需求規格說明書以及______。(B)
A. 階段性報告
B. 需求評審
C. 總結
D. 都不正確
(8) 下述關於數據庫系統的敘述中正確的是______。(A)
A. 數據庫系統減少了數據冗余
B. 數據庫系統避免了壹切冗余
C. 數據庫系統中數據的壹致性是指數據類型的壹致
D. 數據庫系統比文件系統能管理更多的數據
(9) 關系表中的每壹橫行稱為壹個______。(A)
A. 元組
B. 字段
C. 屬性
D. 碼
(10) 數據庫設計包括兩個方面的設計內容，它們是______。(A)
A. 概念設計和邏輯設計
B. 模式設計和內模式設計
C. 內模式設計和物理設計
D. 結構特性設計和行為特性設計