計算機二級公共基礎(chǔ)知識考點整理

1、1. 一般將數(shù)據(jù)結(jié)構(gòu) 分為兩大類型： 線性結(jié)構(gòu) 與非線性結(jié)構(gòu) 。（ 1）如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件： 有且只有一個根結(jié)點； 每一個結(jié)點最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為 線性結(jié)構(gòu) 。線性結(jié)構(gòu)又稱 線性表。在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)是線性結(jié)構(gòu)。棧、隊列、串 等都為線性結(jié)構(gòu)。 如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為 非線性結(jié)構(gòu) 。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是 非線性結(jié)構(gòu) 。 2. （1）棧（stack ）是一種特殊的線性表 ，是限定 只在一端 進行插入與刪除的線性表。棧是按照 “先進后出 ”或“后進先出 ”的原則組織數(shù) 據(jù)的。(2) 隊列是只允許

2、在 一端進行刪除，在另一端進行插入的順序表 。隊列的修改是依照 先進先出 的原則進行的， 因此隊列也稱為先進先出 的線性表，或者后進后出 的線性表。(3) 循環(huán)隊列就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在實際應(yīng)用中，隊列的 順序存儲結(jié)構(gòu) 一般采用 循環(huán)隊列 的形式。循環(huán)隊列 主要由兩種基本運算： 入隊運算與退隊運算。3. 隊列運算：入隊運算是往隊列 隊尾插入 一個數(shù)據(jù)元素； 退隊運算是從隊列的 隊頭刪除一個數(shù)據(jù)元素。隊列的順序存儲結(jié)構(gòu)一般采用隊列循環(huán)的形式。循環(huán)隊列 s=0表示隊列空； s=1且 front=rear表示隊列滿。計算循環(huán)隊列的元素

3、個數(shù)：“尾指針減頭指針”，若為負(fù)數(shù)，再加其容量即可。4. 算法復(fù)雜度：包括時間復(fù)雜度 和空間復(fù)雜度 。注意兩者的區(qū)別， 無混 淆，見表 1-1。表1-1 算法復(fù)雜性名稱描述時間復(fù)雜度執(zhí)行算法所需要的 計算工作量空間復(fù)雜度執(zhí)行這個算法所需要的內(nèi)存空間5.衡量 軟件模塊獨立性 使用耦合性和內(nèi)聚性兩個定性的度量標(biāo)準(zhǔn)內(nèi)聚性是度量一個模塊 功能強度 的一個相對指標(biāo) 。內(nèi)聚是從 功能角度來衡量模塊的聯(lián)系，它描述的是模塊內(nèi)的功能聯(lián)系。內(nèi)聚有如下種類，它們之間的內(nèi)聚度 由弱到強 排列：偶然內(nèi)聚、邏輯內(nèi)聚、時間內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚、功能內(nèi)聚。耦合性是模塊之間互相連接的 緊密程度 的度量。耦合性取決

4、于各個模塊之間接口的 復(fù)雜度、調(diào)用方式 以及哪些信息 通過接口。耦合可以分為多種形勢，它們之間的耦合度 由高到低 排列：內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合、非直接耦合。在程序結(jié)構(gòu) 中，各模塊的 內(nèi)聚性越強，則耦合性越弱。一般較優(yōu)秀的軟件設(shè)計，應(yīng)盡量做到 高內(nèi)聚，低耦合 ，即減弱模塊之間的耦合性和提高 模塊內(nèi)的內(nèi)聚性，有利于提高模塊的獨立性。6. 結(jié)構(gòu)化程序設(shè)計的原則 ：自頂向下、逐步求精、模塊化和限制使用 goto 語句。 自頂向上 ：先考慮整體，再考慮細(xì)節(jié)；先考慮全局目標(biāo)，再考慮局部目標(biāo)； 逐步求精 ：對復(fù)雜問題應(yīng)設(shè)計一些子目標(biāo)作為過渡，逐步細(xì)化；模塊化：把程序要解決

5、的總目標(biāo)分解為分目標(biāo)，再進一步分解為具體的小目標(biāo)，把每個小目標(biāo)稱為一個模塊。限制使用 goto 語句：在程序開發(fā)過程中要限制使用goto 語句。7. 數(shù)據(jù)庫管理系統(tǒng)（ DBMS ，Database Management System）是數(shù)據(jù)庫的機構(gòu)，它是一種系統(tǒng)軟件 ，負(fù)責(zé)數(shù)據(jù)庫中的 數(shù)據(jù)組織 、數(shù)據(jù)操作 、數(shù)據(jù)維護、控制及保護 和數(shù)據(jù)服務(wù) 等。數(shù)據(jù)庫管理系統(tǒng) 是數(shù)據(jù)系統(tǒng)的核心 。為完成數(shù)據(jù)庫管理系統(tǒng)的功能，數(shù)據(jù)庫管理系統(tǒng)提供相應(yīng)的數(shù)據(jù)語言：數(shù)據(jù)定義語言 、數(shù)據(jù)操縱語言 、數(shù)據(jù)控制語言 。8. E-R模型的基本概念實體：現(xiàn)實世界中的事物可以抽象成為實體，實體是概念世界中的基本單位，它們是客觀存

6、在的且又能相互區(qū)別的事物；屬性：現(xiàn)實世界中事物均有一些特性， 這些特性可以用屬性來表示；碼：唯一標(biāo)識實體的屬性集稱為碼；域：屬性的取值范圍稱為該屬性的域；聯(lián)系：在現(xiàn)實世界中事物間的關(guān)聯(lián)稱為聯(lián)系。兩個實體集間的聯(lián)系 實際上是 實體集間的函數(shù)關(guān)系 ，這種函數(shù)關(guān)系可以有下面幾種： 一對一的關(guān)系、 一對多或多對一關(guān)系、多對多 關(guān)系。E-R 模型的的 圖示法E-R模型用 E-R圖來表示。實體表示法 ：在E-R圖中用矩形表示實體集，在矩形內(nèi)寫上該實體集的名字；屬性表示法 ：在E-R圖中用橢圓形表示屬性，在橢圓形內(nèi)寫上該屬性的名稱；聯(lián)系表示法 ：在 E-R 圖中用菱形表示聯(lián)系，菱形內(nèi)寫上聯(lián)系名。9.文件流的

7、定位：（1）文件位置與 定位方式定位方式：C+流的定位方式（也就是指針移動方式)有三種，被定義為ios_base:seek_dir中的一組枚舉符號：ios_base:beg相對于文件首ios_base:cur 相對于當(dāng)前位置 （負(fù)數(shù)表示當(dāng)前位置之前 ）ios_base:end相對于文件尾（2）輸入定位（3）輸出定位10.1 二叉樹 及其基本概念二叉樹是一種很有用的 非線性結(jié)構(gòu) ，具有以下 兩個特點：非空二叉樹 只有一個 根結(jié)點；每一個結(jié)點 最多有兩棵子樹，且分別稱為該結(jié)點的 左子樹 和右子樹。在二叉樹中， 每一個結(jié)點的度最大為 2，即所有子樹（左子樹或右子樹）也均為二叉樹。另外，二叉樹中的每個

8、結(jié)點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個結(jié)點 可以只有左子樹 而沒有右子樹 ，也可以只有右子樹而沒有左子樹 。當(dāng)一個結(jié)點既沒有左子樹也沒有右子樹 時，該結(jié)點即為葉子結(jié)點 。例如，一個家族中的族譜關(guān)系如圖1-1所示：A有后代 B，C；B有后代 D，E；C有后代 F。典型的二叉樹如圖 1-1所示：詳細(xì)講解二叉樹的基本概念，圖 1-1 二叉樹圖見表 1-2。表1-2 二叉樹的基本概念父結(jié)點（根）子結(jié)點和葉子結(jié)點度深度子樹在樹結(jié)構(gòu)中， 每一個結(jié)點只有一個前件 ，稱為父結(jié)點，沒有前件 的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。例如，在圖 1-1中，結(jié)點 A是樹的根結(jié)點。在樹結(jié)構(gòu)中， 每一

9、個結(jié)點 可以有多個后件 ，稱為該結(jié)點的子結(jié)點。沒有后件 的結(jié)點稱為 葉子結(jié)點 。例如，在圖 1-1 中，結(jié)點 D，E，F(xiàn) 均為葉子結(jié)點。在樹結(jié)構(gòu)中， 一個結(jié)點 所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點 中最大的度 稱為樹的度。例如，在圖 1-1 中，根結(jié)點 A 和結(jié)點 B 的度為 2，結(jié)點 C 的度為 1，葉子結(jié)點 D，E，F(xiàn) 的度為 0。所以， 該樹的度為 2。定義一棵樹的 根結(jié)點所在的層次為 1，其他結(jié)點所在的層次等于它的 父結(jié)點所在 的層次加 1。樹的 最大層次稱為樹的深度 。例如，在圖 1-1 中，根結(jié)點 A 在第1 層，結(jié)點 B，C 在第 2 層，結(jié)點 D，E，F(xiàn) 在第 3 層。該

10、樹的深度為 3。在樹中，以 某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一棵子樹 。2. 二叉樹基本性質(zhì)二叉樹具有以下幾個性質(zhì)：性質(zhì) 1：在二叉樹的 第k層上，最多有2(k-1)（k1）個結(jié)點 。性質(zhì) 2：深度為m的二叉樹最多 有( 2m)-1個結(jié)點 。性質(zhì) 3：在任意一棵 二叉樹中， 度為 的結(jié)點（即 葉子結(jié)點 ）總是比度0 為2的結(jié)點多一個 。性質(zhì) 4：具有 n 個結(jié)點的二叉樹，其深度至少為log2n+1 ，其中 log2n 表示取 log2n 的整數(shù)部分。11. 軟件需求規(guī)格說明書軟件需求規(guī)格說明書 是需求分析階段 的最后成果 ，是軟件開發(fā) 的重要文檔之一。它的特點是具有 正確性、無歧義性

11、 、完整性、可驗證性 、一致性、可理解性 、可修改性 和可追蹤性 。12.1 軟件測試的目的測試的目的是發(fā)現(xiàn)軟件中的錯誤 ，但是，暴露錯誤并不是軟件測試的最終目的，測試的 根本目的 是盡可能多地發(fā)現(xiàn)并排除 軟件中隱藏的錯誤 。 2 軟件測試的準(zhǔn)則軟件測試過程中應(yīng)遵循以下準(zhǔn)則：所有測試都應(yīng)追溯到需求； 嚴(yán)格執(zhí)行測試計劃， 排除測試的隨意性； 充分注意測試中的群集現(xiàn)象； 程序員應(yīng)避免檢查自己的程序；窮舉測試不可能；妥善保存測試計劃、測試用例、出錯統(tǒng)計和最終分析報告。13. 程序的調(diào)試在對程序進行了成功的測試之后將進入程序調(diào)試（通常稱 Debug，即 排錯）14. 軟件工程為了擺脫軟件危機，提出了軟

12、件工程的概念。軟件工程學(xué)是 研究軟件開發(fā)和維護的普遍原理與技術(shù) 的一門工程學(xué)科。 所謂軟件工程是指采用工程的概念、原理、技術(shù)和方法指導(dǎo)軟件的開發(fā)與維護。軟件工程學(xué)的 主要研究對象 包括軟件開發(fā)與維護的技術(shù)、 方法、工具和管理 等方面。 軟件工程包括 3個要素： 方法、工具和過程 ，見表 3-2。表3-2軟件工程三要素名稱描述方法方法是完成軟件工程項目的技術(shù)手段工具工具支持軟件的開發(fā)、管理、文檔生成過程過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理15.關(guān)系模型關(guān)系模式 采用二維表來 表示，一個關(guān)系對應(yīng)一張二維表 。可以這么說，一個關(guān)系就是一個二維表，但是一個二維表不一定是一個關(guān)系。?元組：在一個二維表（一個具體關(guān)系）中，水平方向 的行稱為元組。元組對應(yīng)存儲文件中的一個具體記錄；?屬性：二維表中 垂直方向 的列稱為屬性，每一列有一個屬性名；?域：屬性的取值范圍 ，也就是不同元組對同一屬性的取值所限定的范圍。在二維表中 惟一標(biāo)識元組的最小屬性值稱為該表的鍵或碼 。二維表中可能有若干個健 ，它們稱為 表的侯選碼或侯選健 。從二維表的所有侯選鍵選取一個作為用戶使用的鍵稱為 主鍵或主碼 。表 A中的某屬性集是某表B的鍵，則稱該屬性值為 A的外鍵或外碼 。關(guān)系模型采用二維表來表示，二維表一般滿足下面7個性質(zhì)：二維表中元組個數(shù)是有限的 元組個數(shù) 有限性；二維表中元組均不相同 元組的唯一性；二維表中元