一、 資料結構：
1、資料的概念和術語
1）資料：是資訊的載體，它能夠被計算機識別、儲存和加工處理。也就是具有一定意義的01**。
2）資料元素：是資料的基本單位。也稱為元素、結點、頂點、記錄。有時元素可以包含多個資料項。
注：資料項是具有獨立含義的最小的標識單位。
3）資料結構：資料之間的關係，即資料的組織形式。
·分為層次、網狀和關係（二維表）。
·資料結構包括：資料的邏輯結構和資料的儲存結構（物理結構）
·資料的邏輯結構：資料元素之間的邏輯關係。
分為：線性結構、非線性結構。
·資料的儲存結構：資料元素及其關係在計算機儲存器內的表示方法。
分為：順序儲存、鏈結儲存、索引儲存、雜湊儲存
4）演算法：解題方****而完整的描述。（插入、排序）
它有四個基本特徵：可行性，確定性、有窮性和擁有足夠的情報。
分為：時間複雜度、空間複雜度
·時間複雜度：解決乙個問題需要的計算次數。
·空間複雜度：解決乙個問題需要的儲存空間大小。
2、資料的邏輯結構包括線性結構和非線性結構。線性結構包括線性表、佇列和棧、串
·線性表：是由n(n>=0)個資料元素（結點）組成的有限序列。
如：·英文本母（a-z）
·撲克牌的點數（2-a）
·班級學生的成績（65，78，56，89，48……）
·線性表的儲存結構包括：順序儲存、鏈式儲存（單鏈表、迴圈鍊錶、雙鏈表）
·順序儲存：把線性表的結點按邏輯次序依次存放在一組連續的儲存單元裡。也稱為順序表。
·單鏈表：把線性表的結點按邏輯次序放在一組任意的儲存單元裡。而通過給資料新增指標的方式將結點按邏輯順序鏈結在一起。指標中存放下一結點的位址資訊。
·迴圈鍊錶：一種首尾相接的鍊錶。
·雙鏈表：在單鏈表的每個結點裡增加乙個指向其前一結點的指標，形成的鍊錶有兩個方向的鏈。
3、棧和佇列
·棧：限制僅在表的一端進行插入和刪除運算的線性表。又稱為先進後出或後進先出（如向試管中放入桌球，再拿出）
·佇列：一種只允許在一端刪除，在另一端插入的線性表。又稱為先進先出表或後進後出表（如排隊上車）
4、樹是非線性結構的一種。具有層次關係，結點之間有分支的結構。如（家譜，自然界的樹）
根：樹最上方的結點稱為根結點。
葉子：沒有子結點的結點稱為葉子。
度：乙個結點的子結點的個數稱為該結點的度。
深度：樹結點的層數稱為該樹的深度。
二叉樹：每個結點最多只有兩個子結點的樹稱為二叉樹。
子結點分為左結點和右結點。
·滿二叉樹：一棵深度為k且有2k-1個結點的二叉樹。
·完全二叉樹：一棵只有最下二層結點度數小於2，並最下一層的所有結點都有左結點。
·非完全二叉樹：其餘的二叉樹
·二叉樹的遍歷：沿某條搜尋路線，依次訪問每個結點。共有三種遍歷方法：先序遍歷nlr、中序遍歷lnr、後序遍歷lrn
·先序遍歷：先訪問結點的根結點，再訪問左結點，再右結點
·中序遍歷：先訪問結點的左結點，再訪問根結點，再右結點
·後序遍歷：先訪問結點的左結點，再訪問右結點，再根結點
先序遍歷：abdecfg
中序遍歷：dbeafcg
後序遍歷：debfgca
例：寫出下圖的先序、中序和後序遍歷
1） abcdefghij
2） bdcagfihje
3） dcbgijhfea
5、排序：排序是一種最常用的資料操作。
·插入排序: 直接插入排序希爾排序
·交換排序: 氣泡排序快速排序
·選擇排序: 直接選擇排序堆排序
·歸併排序
·分配排序: 箱排序基數排序
6、查詢：順序查詢和二分法查詢
順序查詢：從表的一端到另一端順序掃瞄，將每個結點與給定值比較，直至相等。
注：使用順序查詢平均查詢次數為n/2，最壞查詢次數為n次
二分法查詢：將有序表分為二半，判斷給定值大於還是小於中間數，小於則將有序表的前半分為二半，再判斷給定值大於還是小於中間數，以此類推，直至找到相等的數。
注：查詢次數為log2n 如：3個數需2次，8個以內需3次
二、 軟體生命週期
1）軟體生命週期分為：軟體定義、軟體開發及軟體執行維護3個階段軟體開發階段包括：詳細設計、軟體編碼和軟體測試。
·軟體維護是軟體生命週期的最後乙個階段，是持續時間最長，花費代價最大的階段。
2）軟體生命週期包括：可行性研究與需求分析、設計、實現、測試、交付使用以及維護等活動。
二、軟體工程
1）軟體工程概念的出現源自軟體危機。
·軟體危機是泛指在計算機軟體的開發和維過程中所遇到的一系列嚴重問題。
·軟體的顯著特點是規模龐大，複雜度超線性增長，在開發大型軟體時，要保證高技術，極端複雜困難，不僅涉及技術問題，更重要的是必須要有嚴格而科學的管理。
·可以將軟體危機歸結為成本、質量、生產率等問題。
2）軟體工程的3個要素：方法、工具和過程。
·方法是完成軟體工程專案的技術手段；
·工具支援軟體和開發、管理、文件生成；
·過程支援軟體開發的各個環節的控制、管理。
3）軟體工程學的目的是提高軟體的可維護性，降低維護的代價。
4）軟體工程的目標是，在給定的成本、進度的前提下，開發出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足使用者需求的產品。
5）軟體工程的理論和技術性研究的內容主要包括：軟體開發技術和軟體工程管理。
·軟體開發技術包括：軟體開發方法學、開發過程、開發工具和軟體工程環境，其主體內容是軟體開發方法學。
·軟體工程管理包括：軟體管理學、軟體工程經濟學，以及軟體心理學等內容。
三、軟體設計
1）包括軟體結構設計、資料設計、介面設計和過程設計。
·結構設計是定義軟體系統各主要部件之間的關係；
·資料設計是將分析時建立的模型轉化為資料結構的定義；
·介面設計是描述軟體內部、軟體和作業系統之間及軟體與人之間如何通訊；
·過程設計則是把系統結構部件轉換成軟體的過程性描述。
四、軟體需求說明書（srs）
1）軟體需求說明書（srs）是需求分析階段的最後成果，是軟體開發中的重要文件之一。
2）軟體需求說明書的作用：
a）便於使用者、開發人員進行理解和交流；
b）反映出使用者問題的結構，可以作為軟體開發工作的基礎和依據；
c）作為確認測試和驗收的依據。
五、結構化分析方法
1）結構化分析方法包括：
·面向資料流的結構化分析方法（sa），
·面向資料結構的 jackson方法（jsd）
·面向資料結構的結構化資料系統開發方法（dssd）
六、測試
1）的目的是發現軟體中的錯誤，程式中存在的錯誤與該程式中已發現的錯誤成正比。2）測試人員應集中對付錯誤群集的程式。3）軟體測試的目標是在精心控制的環境下執行程式，以發現程式中的錯誤，給出程式可靠性的鑑定。
4）除錯也稱排錯，它是乙個與測試有聯絡又有區別的概念。5）測試的目的是暴露錯誤，評價程式的可靠性，而除錯的目的是發現錯誤的位置，並改正錯誤。
6）軟體測試過程，輔助資源包括測試用例（測試資料）、測試計畫、出錯統計和最終分析報告等。
七、軟體的白盒測試測試是把測試物件看做乙個開啟的盒子,它允許測試人員利有程式內部的邏輯結構及有關資訊,設計或選擇測試用例,對程式所有邏輯路徑進行測試.黑箱測試方法完全不考慮程式的內部結構和內部特徵,而只是根據程式功能匯出測試用例.常用的黑箱測試有等價分類法、邊值分板法、因果圖法和錯誤推測法4種。
八、確認測試的任務是難軟體的功能和效能，以及其他特性是否滿足需求規格說明中確定的各種需求；整合測試的主要目的是發現與介面有關的錯誤。
1、 軟體維護活動包括改正性維護，適應性維護、完善性維護和預防性維護。
2、 結構化程式設計的三個基本結構是順序、選擇、迴圈。結構化程式設計方法的主要原則要以概括為自頂向下、逐步求精、模組化、及限制goto語句。可使程式結構良好、易讀、易理解、易維護。
3、 外模式是使用者的資料檢視也是使用者所見到的資料模式。全域性資料檢視的描述稱為概念模式，即資料庫中全部資料的整體邏輯結構的描述。物理儲存資料檢視的描述稱為內模式，即資料庫在物理儲存方面的描述。
內模式（物理模式）它給出了資料庫物理儲存結構與物理豐取方法，如資料儲存的檔案結構、索引、集簇及hash等訪問方式與訪問路徑。資料模型按應用層次分：概念資料模型、邏輯資料模型、物理資料模型
4、 資料庫邏輯設計的主要工作是將e-r圖轉換成指定rdbms中的關係模式。
5、 資料流圖包括4個方面：即加工、資料流、儲存檔案、源和潭。加工**換。
輸入資料經加工變換產生輸出）。資料流（沿箭頭方向傳送資料的通道）。源和潭（表示系統和環境的介面，屬系統之外的實體）。
資料流型別有兩種：變換型和事務型。變換型是指資訊沿輸入通路進入系統，同時由外部開式變換成內容形式，進入系統的資訊通過變換中心，經加工處理以後再沿輸出通路變換成外部形式離開軟體系統；在軟體應用中，存在某種作業資料流，它可以引發乙個或多個處理，這些處理能夠完成該作業要求的功能，這種資料流就叫事務。
資料流相當於一條管道，並有一級資料（資料）流經它。在資料流圖中，用標有名字的箭頭表示資料流。資料流可以從加工流向加工，也可以從加工流向檔案或從檔案流向加工，並且可以從外部實體流向系統或從系統流向外部實體。
6、 e-r模型即實體-聯絡模型，是將現實世界的要求轉化成實體、聯絡、屬性等幾個基本概念，以及它們之間的兩種聯接關係。資料庫邏輯設計階段包括以下幾個過程：從e-r圖向關係模式轉換，邏輯模式規範化及調整、實現規範化和rdbms，以及關係檢視設計。
7、 程式結構圖中矩形內用於註明模組的功能和名字；箭頭表示模組間的呼叫關係，帶實心圓的箭頭表示傳遞的是控制資訊，帶空心圓的箭頭表示傳遞的是資料。
8、 模組化是指解決乙個複雜問題時自頂向下逐層把軟體系統劃分成若干模組的過程，由此分解來降低複雜性。內聚性是乙個模組內部各個元素間彼此結合的緊密程式的度量，是從功能角度來度量模組內的聯絡。耦合性是模組間互相連線的緊密程式的度量。
按耦合程式從弱到強，可分為資料耦合、同構耦合、控制耦合、公用耦合和內容耦合。
計算機公共基礎
公共基礎知識 基本要求 1 掌握演算法的基本概念。2 掌握基本資料結構及其操作。3 掌握基本排序和查詢演算法。4 掌握逐步求精的結構化程式設計方法。5 掌握軟體工程的基本方法，具有初步應用相關技術進行軟體開發的能力。6 掌握資料庫的基本知識，了解關聯式資料庫的設計。考試內容 一 基本資料結構與演算法...
計算機二級公共知識
全國計算機二級考試公共基礎知識習題 1 下面敘述正確的是 c a.演算法的執行效率與資料的儲存結構無關 b.演算法的空間複雜度是指演算法程式中指令 或語句 的條數 指的是演算法所占用的空間 c.演算法的有窮性是指演算法必須能在執行有限個步驟之後終止 d.以上三種描述都不對 2 以下資料結構中不屬於線...
計算機二公共試題
全國計算機等級考試二級公共基礎知識試題總匯 一 選擇題 1 棧和佇列的共同特點是 c a 都是先進先出 b 都是先進後出 c 只允許在埠處插入和刪除元素d 沒有共同點 2 已知二叉樹後序遍歷序列是dabec，中序遍因序列是dabec，它的前序遍歷序列是 d a acbedb decabc deabc...