計(jì)算機(jī)二級(jí)基礎(chǔ)知識(shí)

1、數(shù)據(jù)結(jié)構(gòu)與算法算法的基本概念1. 算法：是對(duì)問(wèn)題處理方案的正確而完整的描述， 是求解問(wèn)題的方法， 是指 令的有效序列。2. 具有 5個(gè)特性：（ 1）有窮性（在有窮步后完成）算法程序的運(yùn)行時(shí)間是有限的（2）確定性（每一步都有確定的含義）（3）可行性（4）輸入（一個(gè)算法有零個(gè)或多個(gè)輸入）（5）輸出（一個(gè)算法有一個(gè)或多個(gè)輸出）3. 算法的復(fù)雜度 包括：時(shí)間復(fù)雜度和空間復(fù)雜度。二者沒(méi)有必然的聯(lián)系。 時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量或基本運(yùn)算次數(shù)。 空間復(fù)雜度：算法所需要的空間的度量。數(shù)據(jù)結(jié)構(gòu)的定義1. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的操作 數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的外部結(jié)構(gòu)， 指各

2、數(shù)據(jù)元素之間的邏輯關(guān)系， 反映人 們對(duì)數(shù)據(jù)含義的解釋。包括：線性結(jié)構(gòu)（線性表、棧、隊(duì)列）和非線性結(jié)構(gòu)（樹(shù) 和圖）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)，指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示。 一個(gè)邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)。線性表：線性表中元素的個(gè)數(shù) n （n>=0）定義為線性表的長(zhǎng)度。 順序存儲(chǔ)是線性表的一種最常用的存儲(chǔ)方式。線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是隨機(jī)存取的存儲(chǔ)結(jié) 構(gòu)和順序存取的存儲(chǔ)結(jié)構(gòu)。1. 棧：是限定在表尾進(jìn)行插入和刪除操作的線性表。 具有記憶功能只能順序 存儲(chǔ)（錯(cuò)）允許插入和刪除的一端叫棧頂。另一端叫棧底。后進(jìn)先出的線性表2 隊(duì)列：是限定在一端插入而在另一端刪除，

3、插入端叫隊(duì)尾， 刪除端叫對(duì)頭 先進(jìn)先出的線性表3 棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) 循環(huán)隊(duì)列屬于線性表存儲(chǔ)結(jié)構(gòu)中順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的前者。樹(shù)1. 定義: 樹(shù)的結(jié)點(diǎn)、度（結(jié)點(diǎn)的度）、葉子（終端結(jié)點(diǎn)）、數(shù)的度、深度、 有序樹(shù)和無(wú)序數(shù)2. 二叉樹(shù)：結(jié)點(diǎn)至多有兩棵子樹(shù)， 并且二叉樹(shù)的子樹(shù)有之分， 次序不能顛倒。 性質(zhì)：在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)深度為 k 的二叉樹(shù)至多有 2k-1 個(gè)結(jié)點(diǎn)。對(duì)任一個(gè)二叉樹(shù)T,如果其葉子（終端結(jié)點(diǎn)數(shù)）為 n,度為二的結(jié)點(diǎn)數(shù)為m,貝U n=m+1.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 k+1,其中k是炯2n的整數(shù)部分。2. 二叉樹(shù)的遍歷先序遍歷（根左右）中序遍歷（左根

4、右）后序遍歷（左右根）查找算法（ 1 ）順序查找順序查找的平均查找長(zhǎng)度為（n+1）/ 2,最壞的情況下比較的次數(shù)為n（2） 二分查找最壞情況下次數(shù)為 log2n 限定于順序存儲(chǔ)的有序線性表排序算法（ 1 ）插入類排序直接插入排序折半插入排序希爾排序n A1 . 5(2) 交換類排序冒泡排序最壞情況下的比較次數(shù) n(n-1) /2快速排序最壞情況下的比較次數(shù) n(n-1) /2(3)選擇類排序例題精選：1. 設(shè)一棵完全二叉樹(shù)共有699個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為：3502. 已知二叉樹(shù)后序遍歷序列是 dabec,中序遍歷序列是debac,它的前序遍歷 序列為：cedba3. 要求內(nèi)存量最

5、大的是：歸并排序4. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的是：邏輯結(jié)構(gòu)5.5. 已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)采取的算法 是：直接插入排序6. 用鏈?zhǔn)奖硎揪€性表的優(yōu)點(diǎn)是：便于插入和刪除操作。程序設(shè)計(jì)基礎(chǔ)1. 程序設(shè)計(jì)風(fēng)格好的程序設(shè)計(jì)風(fēng)格有利于提高程序的正確性、可讀性、可維護(hù)性和可用性。要是程序有良好的風(fēng)格概括起來(lái)可以分為 4部分：源程序文檔化、數(shù)據(jù)說(shuō)明、語(yǔ) 句結(jié)構(gòu)、輸入輸出方法。用戶所定義的標(biāo)示符必須以字母或下劃線開(kāi)頭。大、小寫字母代表不同標(biāo)識(shí)。2. 結(jié)構(gòu)化程序設(shè)計(jì)(1) 結(jié)構(gòu)化程序設(shè)計(jì)的基本特征：程序有3中基本結(jié)構(gòu)組成：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)整個(gè)程序采用

6、模塊化結(jié)構(gòu)。模塊劃分的原則：模塊內(nèi)具有高內(nèi)聚度、模塊 間具有低耦合度。有限的使用轉(zhuǎn)移語(yǔ)句，只限定在一個(gè)結(jié)構(gòu)的內(nèi)部跳轉(zhuǎn)，不允許從一個(gè)結(jié)構(gòu) 跳到另一結(jié)構(gòu)。程序設(shè)計(jì)時(shí)采用“至頂向下、逐步詳細(xì)”的實(shí)施方法。(2) 結(jié)構(gòu)化程序設(shè)計(jì)的3種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)3種基本結(jié)構(gòu)組成的算法只能完成符合結(jié)構(gòu)化的任務(wù)(3) 結(jié)構(gòu)化程序設(shè)計(jì)的方法：逐步求精和模塊化程序設(shè)計(jì)方法。結(jié)構(gòu)化設(shè)計(jì)的總體思想是采用模塊化結(jié)構(gòu)，自上而下，逐步求精。3. 面向?qū)ο蟪绦蛟O(shè)計(jì)基本概念對(duì)象：系統(tǒng)中運(yùn)行的實(shí)體，是有特殊屬性(數(shù)據(jù))和方法的實(shí)體類：由屬性和方法構(gòu)成。一組具有相同的數(shù)據(jù)結(jié)構(gòu)和相同的行為特征的對(duì)象的集合稱為類在面對(duì)對(duì)

7、象的方法中，類的實(shí)例稱為對(duì)象面向?qū)ο蟪绦蛟O(shè)計(jì)特征的是：繼承性、多態(tài)性、封裝性在面向?qū)ο蟮姆椒ㄖ?，?shí)現(xiàn)信息隱蔽是依靠對(duì)象的封裝任何對(duì)象都必須有繼承性(錯(cuò))例題精選：1. 在面對(duì)對(duì)象的方法中，一個(gè)對(duì)象請(qǐng)求另一個(gè)對(duì)象為其服務(wù)的方式是通過(guò)發(fā)送：信息2. 面對(duì)對(duì)象的設(shè)計(jì)方法與傳統(tǒng)的面向過(guò)程的方法有本質(zhì)的區(qū)別，它的基本原理是：使用現(xiàn)實(shí)世界的概念抽象的思考問(wèn)題從而自然地解決問(wèn)題 .3. 結(jié)構(gòu)化方法中，軟件功能分解屬于軟件開(kāi)發(fā)階段中的總體設(shè)計(jì)4. 結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是：程序的易讀性5. 面向?qū)ο蟮脑O(shè)計(jì)程序主要考慮的是：提高軟件的可重用性6. 類通過(guò)接口與外界發(fā)生關(guān)系.軟件工程基礎(chǔ)1.軟件工程的基本概念(

8、1) 定義:軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合。軟件包括系統(tǒng)軟件和應(yīng)用軟 件(2) 軟件工程的基本思想是軟件開(kāi)發(fā)中，應(yīng)用工程化原則進(jìn)行軟件開(kāi)發(fā)，并將這個(gè)思想貫穿在軟件開(kāi)發(fā)的整個(gè)過(guò)程中。軟件工程的3要素：方法、工具和過(guò)程(3) 軟件的生命周期：從軟件定義、開(kāi)發(fā)、使用、維護(hù)到報(bào)廢為止的整個(gè)過(guò) 程。分三階段：設(shè)計(jì)階段、開(kāi)發(fā)階段、維護(hù)階段包括：?jiǎn)栴}定義、可行性分析、需求分析、總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼、測(cè) 試和維護(hù)問(wèn)題定義：確定開(kāi)發(fā)的任務(wù)可行性分析：確定問(wèn)題的可行性需求分析：對(duì)用戶要求進(jìn)行分析，明確目標(biāo)系統(tǒng)要做什么 總體設(shè)計(jì)：把軟件功能轉(zhuǎn)化為所需要的體系結(jié)構(gòu)，即如何解決問(wèn)題。 詳細(xì)設(shè)計(jì)：怎樣具體的解決問(wèn)題

9、2. 結(jié)構(gòu)化分析方法(1) 結(jié)構(gòu)化分析(SA是面向數(shù)據(jù)流進(jìn)行需求分析的方法SA方法的基本思想正是運(yùn)用了分解和抽象兩個(gè)基本手段，采用：自頂向下， 逐步分解的分析思路。(2) 數(shù)據(jù)流圖基本圖形符號(hào)：在結(jié)構(gòu)化方法中，用數(shù)據(jù)流程圖(DFD)作為描述工具的軟件開(kāi)發(fā)階段是：需求 分析(3) 數(shù)據(jù)字典在結(jié)構(gòu)化分析的數(shù)據(jù)流圖中 ,利用數(shù)據(jù)字典對(duì)其中的圖形元素進(jìn)行確切解 釋.3. 軟件設(shè)計(jì)( 1 )概要設(shè)計(jì)(總體設(shè)計(jì))包括兩個(gè)主要階段：系統(tǒng)設(shè)計(jì)(確定具體的實(shí)現(xiàn)方案)和結(jié)構(gòu)設(shè)計(jì)(確定 每個(gè)系統(tǒng)的模塊組成及模塊間的關(guān)系)模塊之間聯(lián)系越緊密 , 其耦合性就越強(qiáng) , 模塊的獨(dú)立性就越差 ; 一個(gè)模塊內(nèi)個(gè)要素聯(lián)系越緊密，

10、則它的內(nèi)聚性就越高。 模塊劃分原則：高內(nèi)聚低耦合( 2)詳細(xì)設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的要點(diǎn)：采用自頂向下、逐步求精的程序設(shè)計(jì)方法，一個(gè) 程序只有一個(gè)入口和一個(gè)出口。詳細(xì)設(shè)計(jì)的常用工具：程序流程圖、盒圖、PAD和PDL(3) 軟件測(cè)試目的軟件測(cè)試的目的是盡可能多的發(fā)現(xiàn)程序中的錯(cuò)誤。軟件測(cè)試方法：靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試(黑盒測(cè)試法和白盒測(cè)試法) 黑盒測(cè)試包括：等價(jià)分析法、邊值分析法、因果圖法和錯(cuò)誤推測(cè)法 白盒測(cè)試法測(cè)試的原則之一就是保證所測(cè)模塊中的每一個(gè)獨(dú)立的路徑至少 執(zhí)行一次。(4) 程序調(diào)試分為靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試調(diào)試的目的：改正錯(cuò)誤經(jīng)調(diào)試后還必須進(jìn)行再測(cè)試(5) 軟件維護(hù)軟件維護(hù)就是在軟件已經(jīng)交付使用以

11、后，為改正錯(cuò)誤或滿足新的需求而修改 軟件的過(guò)程。例題精選：1 分析的結(jié)果是產(chǎn)生需求規(guī)格說(shuō)明書(shū)。2軟件詳細(xì)設(shè)計(jì)的主要任務(wù)是確定每一個(gè)模塊的算法和使用的數(shù)據(jù)結(jié)構(gòu)。3 進(jìn)行單元測(cè)試時(shí)，常用的方法時(shí)采用白盒測(cè)試，輔以黑盒測(cè)試。4軟件工程的出現(xiàn)是由于軟件危機(jī)的出現(xiàn)，人們提出了軟件工程學(xué)的原理 設(shè)計(jì)軟件。5 數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，通常包括 4個(gè)部分：數(shù)據(jù)項(xiàng)、數(shù)據(jù)流、 數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)加工。數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)1.數(shù)據(jù)庫(kù)(1) 數(shù)據(jù)庫(kù)設(shè)計(jì)的根本目的是要解決數(shù)據(jù)共享的問(wèn)題。(2) 數(shù)據(jù)庫(kù)的特點(diǎn)：數(shù)據(jù)按一定的數(shù)據(jù)模型組織和存儲(chǔ)。冗余度較小數(shù)據(jù)的獨(dú)立性較高。 數(shù)據(jù)獨(dú)立性： 數(shù)據(jù)的組織結(jié)構(gòu)和存儲(chǔ)方法與應(yīng)用程序 互不

12、依賴、彼此獨(dú)立。易擴(kuò)展可為多種用戶共享2. 數(shù)據(jù)庫(kù)管理系統(tǒng)（ DBM）S 位于用戶與操作系統(tǒng)之間的完成數(shù)據(jù)管理的系統(tǒng)軟件。3. 數(shù)據(jù)庫(kù)系統(tǒng) 由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、應(yīng)用系統(tǒng)、數(shù)據(jù)庫(kù)管理員和用戶組成。 最核心的部分是數(shù)據(jù)庫(kù)管理系統(tǒng)。4. 數(shù)據(jù)模型（1）實(shí)體聯(lián)系模型及 E-R 圖3 部分：實(shí)體、聯(lián)系和屬性 實(shí)體集間的聯(lián)系：一對(duì)一聯(lián)系、一對(duì)多聯(lián)系和多對(duì)多聯(lián)系 （2）層次、網(wǎng)狀、關(guān)系模型 層次模型：有且只有一個(gè)結(jié)點(diǎn)無(wú)雙親，其他結(jié)點(diǎn)只有一個(gè)雙親。 用樹(shù)形結(jié)構(gòu)來(lái)表示各實(shí)體與實(shí)體之間的聯(lián)系。在關(guān)系數(shù)據(jù)庫(kù)中， 把數(shù)據(jù)表示成二維表， 每個(gè)二維表稱為關(guān)系。 一個(gè)關(guān)系對(duì) 應(yīng)一張二維表。關(guān)系的屬性名稱為關(guān)系模式。5. 關(guān)系運(yùn)算（1）并（2）差（3）交（4）笛卡爾積（X）6. 專門關(guān)系運(yùn)算：選擇、連接和投影（ 1 ）從關(guān)系中找到滿足條件的所有元組稱為選擇（