二級公共基礎知識總結
第一章資料結構與演算法
1.1演算法
1.1.1演算法：是指解題方****而完整的描述。
演算法不等於程式，也不等計算機方法，程式的編制不可能優於演算法的設計。
a演算法的基本特徵：
（1）可行性；
（2）確定性
（3）有窮性
（4）擁有足夠的情報。
b演算法的基本要素：一是對資料物件的運算和操作；二是演算法的控制結構。
指令系統：乙個計算機系統能執行的所有指令的集合。 計算機可以執行的基本操作是以指令的形式描述的。
基本的運算和操作包括：算術運算、邏輯運算、關係運算、資料傳輸。
演算法的控制結構：順序結構、選擇結構、迴圈結構。
c演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減鬥遞推技術、回溯法。
1.1.2演算法複雜度：演算法時間複雜度和演算法空間複雜度。
演算法時間複雜度是指執行演算法所需要的計算工作量。
演算法空間複雜度是指執行這個演算法所需要的記憶體空間。
1.2資料結構的基本概念
1.2.1資料結構研究的三個方面：
（1）資料邏輯結構；
（2）資料儲存結構；
（3）對各種資料結構進行的運算。
資料結構是指反映資料元素之間關係的資料元素集合的表示。
資料處理，是指對資料集合中的各元素以各種方式進行運算，包括插入、刪除、查詢、更改等運算，也包括對資料元素進行分析。
a資料的邏輯結構包含：
（1）表示資料元素的資訊；
（2）表示各資料元素之間的前後件關係。
資料元素之間的前後件關係是指它們的邏輯關係，而與它們在計算機中的儲存位置無關。
資料的邏輯結構，是指反映資料元素之間邏輯關係的資料結構。
b資料的儲存結構有順序、鏈結、索引等。
1.2.2線性結構（又稱線性表）條件：
（1）有且只有乙個根結點；
（2）每乙個結點最多有乙個前件，也最多有乙個後件。
非線性結構：不滿足線性結構條件的資料結構。
1.3線性表及其順序儲存結構
1.3.1線性表：由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
（1）且只有乙個根結點a1，它無前件；
（2）有且只有乙個終端結點an，它無後件；
（3）除根結點與終端結點外，其他所有結點有且只有乙個前件，也有且只有乙個後件。
結點個數n稱為線性表的長度，當n=0時，稱為空表。
1.3.2線性表的順序儲存結構具有以下兩個基本特點：
（1）線性表中所有元素的所佔的儲存空間是連續的；
（2）線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
1.3.3順序表的運算：插入、刪除。
1.4棧和佇列
1.4.1棧
線性表，「先進後出」或「後進先出」
用top指示棧頂位置，用bottom指向棧底。
棧的基本運算：
（1）入棧運算：棧頂位置插入乙個元素
（2）退棧運算：取出棧頂元素並賦給乙個指定的變數
（3）讀棧頂元素：是將棧頂元素賦給乙個指定的變數，此時棧頂指標無變化。
1.4.2★佇列
線性表，「先進行出」（fifo）或「後進後出」
尾指標（rear）指向隊尾元素，排頭指標（front）指向排頭元素的前乙個位置。
佇列基本運算：
（1）入隊運算
（2）退隊運算
迴圈佇列：s=0表示佇列空，s=1且front=rear表示佇列滿
1.5線性鍊錶
1.5.1結點
假設資料結構中的每乙個資料結點對應於乙個儲存單元，這種儲存單元稱為儲存結點，簡稱結點。
結點組成：（1）資料域（2）指標域
在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。
鏈式儲存方式即可用於表示線性結構，也可用於表示非線性結構。
1.5.2線性鍊錶的基本運算：查詢、插入、刪除。
1.6樹與二叉樹
1.6.1樹
非線性結構，上端結點是前件，下端結點是後件。
父節點：每乙個結點僅有的乙個前件
根節點：唯一沒有前件的結點
子節點：每乙個結點的多個後件
葉子節點：沒有後件的結點
度：乙個結點所擁有的後件的個數
葉子結點的度為0。所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
1.6.2二叉樹的特點：（1）非空二叉樹只有乙個根結點；（2）每乙個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
二叉樹的基本性質：
（1）在二叉樹的第k層上，最多有2k-1(k≥1)個結點；
（2）深度為m的二叉樹最多有2m-1個結點；
（3）度為0的結點（即葉子結點）總是比度為2的結點多乙個；
（4）具有n個結點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分；
（5）具有n個結點的完全二叉樹的深度為[log2n]+1；
（6）設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從左到右）用自然數1，2，….，n給結點進行編號（k=1,2….n），有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為int(k/2)；
②若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（也無右子結點）；
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
滿二叉樹是指除最後一層外，每一層上的所有結點有兩個子結點，則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。
完全二叉樹是指除最後一層外，每一層上的結點數均達到最大值，在最後一層上只缺少右邊的若干結點。
1.6.3二叉樹儲存結構採用鏈式儲存結構，對於滿二叉樹與完全二叉樹可以按層序進行順序儲存。
由於二叉樹的儲存結構中每乙個儲存結點有兩個指標域，因此二叉樹的鏈式儲存結構也稱為二叉鍊錶。
1.6.4二叉樹的遍歷是指不重複地訪問二叉樹中的所有結點：
（1）前序遍歷（dlr）：訪問根結點；前序遍歷左子樹；前序遍歷右子樹。
（2）中序遍歷（ldr）：中序遍歷左子樹；訪問根結點；中序遍歷右子樹。
（3）後序遍歷（lrd）：後序遍歷左子樹；後序遍歷右子樹；訪問根結點。
1.7查詢技術
1.7.1順序查詢
（1）線性表為無序表；
（2）表採用鏈式儲存結構。
1.7.2二分法
查詢只適用於順序儲存的有序表，對於長度為n的有序線性表，最壞情況只需比較log2n次，而順序查詢需要比較n次。
1.8排序技術
排序是指將乙個無序序列整理成按值非遞減順序排列的有序序列。
1.8.1交換類排序法：
（1）氣泡排序法，最壞情況需要比較的次數為n(n-1)/2
（2）快速排序法。
1.8.2插入類排序法：
（1）簡單插入排序法，最壞情況需要n(n-1)/2次比較
（2）希爾排序法
1.8.3選擇類排序法：
（1）簡單選擇排序法, 最壞情況需要n(n-1)/2次比較；
（2）堆排序法，最壞情況需要o(nlog2n)次比較。
第二章程式設計基礎
2.1程式設計方法與風格
當今主導的程式設計風格：清晰第一，效率第二
注重和考慮的因素：（1）源程式文件化 （2）資料說明的方法 （3）語句的結構 （4）輸入和輸出
2.2結構化程式設計
2.2.1結構化程式設計的原則：（1）自頂而下（2）逐步求精（3）模組化（4）限制使用goto語句
2.2.2結構化程式設計的基本結構：（1）順序結構（2）選擇結構（3）重複結構
2.2.3結構化程式設計注意把握如下要素：
（1）使用程式語言中的順序、選擇、迴圈等有限的控制結構表示程式的控制邏輯；
（2）選用的控制結構只准許有乙個入口和乙個出口；
（3）程式語句組成容易識別的塊，每塊只有乙個入口和乙個出口；
（4）複雜結構應該用巢狀的基本控制結構進行組合巢狀來實現；
（5）前後一致的方法來模擬；
（6）限制使用goto語句
2.3物件導向的程式設計
2.3.1 物件導向方法的優點
（1）與人類習慣的思維方法一致
（2）穩定性好
（3）可重用性好
（4）易於開發大型軟體產品
（5）可維護性好
2.3.2
a物件可以用來表示客觀世界中的任何實體。物件導向的程式設計方法中設計的物件是系統中用來描述客觀食物的乙個實體，是構成系統的乙個基本單位，它由一組表示其靜態特徵的屬性和它可執行的一組操作組成。
物件的基本特點：（1）標識唯一性（2）分類性（3）多型性（4）封裝性
b類是具有共同屬性、共同方法的物件的集合。類是物件的抽象，而乙個物件則是其對應類的乙個例項。
c訊息訊息的組成：（1）接收訊息的物件的名稱；（2）訊息識別符號；（3）零個或多個引數。
d繼承是使用已有的類定義作為基礎建立新類的定義技術。
繼承分為單繼承與多重繼承。
第三章軟體工程基礎
3.1 軟體工程基本概念
3.1.1計算機軟體是包括程式、資料及相關文件的完整集合。
軟體的特點包括：
（1）軟體是一種邏輯實體，而不是物理實體，具有抽象性；
（2）軟體的生產與硬體不同，它沒有明顯的製作過程；
（3）軟體在執行、使用期間不存在磨損、老化問題；
（4）軟體的開發、執行對計算機系統具有依賴性，受計算機系統的限制，這導致了軟體移植的問題；
（5）軟體複雜性高，成本昂貴；
（6）軟體開發涉及諸多的社會因素。
軟體按功能分為應用軟體、系統軟體、支撐軟體（或工具軟體）。
3.1.2軟體危機主要表現在成本、質量、生產率等問題。
軟體工程是應用於計算機軟體的定義、開發和維護的一整套方法、工具、文件、實踐標準和工序。
軟體工程包括3個要素：方法、工具和過程。方法是完成軟體工程專案的技術手段；工具支援軟體的開發、管理、文件生成；過程支援軟體開發的各個環節的控制、管理。
3.1.3軟體工程過程是把輸入轉化為輸出的一組彼此相關的資源和活動，包含4種基本活動：
（1）p（plan）——軟體規格說明；
（2）d(do)——軟體開發；
（3）c(check)——軟體確認；
（4）a(action)——軟體演進。
軟體生命週期：軟體產品從提出、實現、使用維護到停止使用退役的過程。
軟體生命週期三個階段:軟體定義、軟體開發、執行維護，主要活動階段是：
（1）可行性研究與計畫制定； （2）需求分析； （3）軟體設計； （4）軟體實現； （5）軟體測試； （6）執行和維護。
3.1.4軟體工程的目標和與原則：
目標：在給定成本、進度的前提下，開發出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足使用者需求的產品。
基本目標：付出較低的開發成本；達到要求的軟體功能；取得較好的軟體效能；開發軟體易於移植；需要較低的費用；能按時完成開發，及時交付使用。
基本原則：抽象、資訊隱蔽、模組化、區域性化、確定性、一致性、完備性和可驗證性。
軟體工程的理論和技術性研究的內容主要包括：軟體開發技術和軟體工程管理。
軟體開發技術包括：軟體開發方法學、開發過程、開發工具和軟體工程環境。
軟體工程管理包括：軟體管理學、軟體工程經濟學、軟體心理學等內容。
軟體管理學包括人員組織、進度安排、質量保證、配置管理、專案計畫等。
軟體工程經濟學是研究軟體開發中成本的估算、成本效益分析的方法和技術，用經濟學的基本原理來研究軟體工程開發中的經濟效益問題。
軟體心理學是軟體工程領域具有挑戰性的乙個全新的研究視角，它是從個體心理、人類行為、組織行為和企業文化等角度來研究軟體管理和軟體工程的。
3.2 結構化分析方法
結構化方法包括結構化分析方法、結構化設計方法和結構化程式設計方法，其核心和基礎是結構化程式設計理論。
3.2.1需求分析方法有（1）結構化需求分析方法； （2）物件導向的分析的方法。
需求分析階段的工作：（1）需求獲取（2）需求分析（3）編寫需求規格說明書（4）需求評審
3.2.2結構化分析方法的實質：著眼於資料流，自頂向下，逐層分解，建立系統的處理流程，以資料流圖和資料字典為主要工具,建立系統的邏輯模型。
結構化分析的常用工具：
（1）資料流圖（2）資料字典（3）判定樹（4）判定表
資料字典是結構化分析的核心。
3.2.3軟體需求規格說明書的作用：（1）便於使用者、開發人員進行理解和交流（2）反映出使用者問題的結構，可以作為軟體開發工作的基礎和依據（3）作為確認測試和驗收的依據
軟體需求規格說明書的特點： （1）正確性； （2）無岐義性； （3）完整性； （4）可驗證性； （5）一致性； （6）可理解性； （7）可追蹤性。
3.3 結構化設計方法
3.3.1軟體設計是乙個把軟體需求轉換為軟體表示的過程。軟體設計的基本目標是用比較抽象概括的方式確定目標系統如何完成預定的任務，即軟體設計是確定系統的物理模型。
從技術觀點來看，軟體設計包括軟體結構設計、資料設計、介面設計、過程設計。
結構設計：定義軟體系統各主要部件之間的關係。
資料設計：將分析時建立的模型轉化為資料結構的定義。
介面設計：描述軟體內部、軟體和協作系統之間以及軟體與人之間如何通訊。
過程設計：把系統結構部件轉換成軟體的過程描述。
從工程管理角度來看：概要設計和詳細設計。
軟體設計的一般過程：軟體設計是乙個迭代的過程；先進行高層次的結構設計；後進行低層次的過程設計；穿插進行資料設計和介面設計。
計算機二級公共基礎120題
1 下面敘述正確的是 c a.演算法的執行效率與資料的儲存結構無關 b.演算法的空間複雜度是指演算法程式中指令 或語句 的條數 c.演算法的有窮性是指演算法必須能在執行有限個步驟之後終止 d.以上三種描述都不對 2 以下資料結構中不屬於線性資料結構的是 c a.佇列 b.線性表 c.二叉樹 d.棧 ...
計算機二級公共基礎命題超高
下面的138道題目，在二級考試中命中率極高。一 選擇題 1 下面敘述正確的是 c a.演算法的執行效率與資料的儲存結構無關 b.演算法的空間複雜度是指演算法程式中指令 或語句 的條數 c.演算法的有窮性是指演算法必須能在執行有限個步驟之後終止 d.以上三種描述都不對 2 以下資料結構中不屬於線性資料...
計算機二級公共知識
全國計算機二級考試公共基礎知識習題 1 下面敘述正確的是 c a.演算法的執行效率與資料的儲存結構無關 b.演算法的空間複雜度是指演算法程式中指令 或語句 的條數 指的是演算法所占用的空間 c.演算法的有窮性是指演算法必須能在執行有限個步驟之後終止 d.以上三種描述都不對 2 以下資料結構中不屬於線...