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