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

.z.數(shù)據(jù)構(gòu)造與算法◆算法的根本概念1.算法：是對問題處理方案的正確而完整的描述，是求解問題的方法，是指令的有效序列。2.具有5個(gè)特性：〔1〕有窮性〔在有窮步后完成〕算法程序的運(yùn)行時(shí)間是有限的〔2〕確定性〔每一步都有確定的含義〕〔3〕可行性〔4〕輸入〔一個(gè)算法有零個(gè)或多個(gè)輸入〕〔5〕輸出〔一個(gè)算法有一個(gè)或多個(gè)輸出〕3.算法的復(fù)雜度包括：時(shí)間復(fù)雜度和空間復(fù)雜度。二者沒有必然的聯(lián)系。時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量或根本運(yùn)算次數(shù)?？臻g復(fù)雜度：算法所需要的空間的度量?！魯?shù)據(jù)構(gòu)造的定義1.數(shù)據(jù)構(gòu)造包括數(shù)據(jù)的邏輯構(gòu)造、數(shù)據(jù)的存儲構(gòu)造、數(shù)據(jù)的操作數(shù)據(jù)的邏輯構(gòu)造：數(shù)據(jù)的外部構(gòu)造，指各數(shù)據(jù)元素之間的邏輯關(guān)系，反映人們對數(shù)據(jù)含義的解釋。包括：線性構(gòu)造〔線性表、棧、隊(duì)列〕和非線性構(gòu)造〔樹和圖〕數(shù)據(jù)的存儲構(gòu)造：數(shù)據(jù)的物理構(gòu)造，指數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)中的表示。一個(gè)邏輯構(gòu)造可以有多種存儲構(gòu)造?！艟€性表：線性表中元素的個(gè)數(shù)n〔n>=0〕定義為線性表的長度。順序存儲是線性表的一種最常用的存儲方式。線性表的順序存儲構(gòu)造和線性表的鏈?zhǔn)酱鎯?gòu)造分別是隨機(jī)存取的存儲構(gòu)造和順序存取的存儲構(gòu)造。1.棧：是限定在表尾進(jìn)展插入和刪除操作的線性表。具有記憶功能只能順序存儲〔錯(cuò)〕允許插入和刪除的一端叫棧頂。另一端叫棧底。后進(jìn)先出的線性表2隊(duì)列：是限定在一端插入而在另一端刪除，插入端叫隊(duì)尾，刪除端叫對頭。先進(jìn)先出的線性表3棧和隊(duì)列的順序存儲構(gòu)造循環(huán)隊(duì)列屬于線性表存儲構(gòu)造中順序存儲構(gòu)造和鏈?zhǔn)酱鎯?gòu)造的前者?！魳?.定義:樹的結(jié)點(diǎn)、度〔結(jié)點(diǎn)的度〕、葉子〔終端結(jié)點(diǎn)〕、數(shù)的度、深度、有序樹和無序數(shù)2.二叉樹：結(jié)點(diǎn)至多有兩棵子樹，并且二叉樹的子樹有之分，次序不能顛倒。性質(zhì)：*在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)*深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。*對任一個(gè)二叉樹T，如果其葉子〔終端結(jié)點(diǎn)數(shù)〕為n，度為二的結(jié)點(diǎn)數(shù)為m,則n=m+1.*具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k+1，其中k是㏒2n的整數(shù)局部。2.二叉樹的遍歷▼先序遍歷〔根—左—右〕▼中序遍歷〔左—根—右〕▼后序遍歷〔左—右—根〕◆查找算法〔1〕順序查找順序查找的平均查找長度為〔n+1〕／2，最壞的情況下比擬的次數(shù)為n(2)二分查找最壞情況下次數(shù)為log2n限定于順序存儲的有序線性表◆排序算法〔1〕插入類排序▲直接插入排序▲折半插入排序▲希爾排序ｎ^１.５〔2〕交換類排序▲冒泡排序最壞情況下的比擬次數(shù)n(n-1)／2▲快速排序最壞情況下的比擬次數(shù)n(n-1)／2(3)選擇類排序例題精選:1.設(shè)一棵完全二叉樹共有699個(gè)結(jié)點(diǎn),則在該二叉樹中的葉子結(jié)點(diǎn)數(shù)為:3502.二叉樹后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列為：cedba3.要求存量最大的是：歸并排序4.在數(shù)據(jù)構(gòu)造中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的是：邏輯構(gòu)造5.棧底至棧頂依次存放元素A.B.C.D,在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是：DCBEA6.數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)采取的算法是：直接插入排序7.用鏈?zhǔn)奖硎揪€性表的優(yōu)點(diǎn)是：便于插入和刪除操作。程序設(shè)計(jì)根底1.程序設(shè)計(jì)風(fēng)格好的程序設(shè)計(jì)風(fēng)格有利于提高程序的正確性、可讀性、可維護(hù)性和可用性。要是程序有良好的風(fēng)格概括起來可以分為4局部：源程序文檔化、數(shù)據(jù)說明、語句構(gòu)造、輸入輸出方法。用戶所定義的標(biāo)示符必須以字母或下劃線開頭。大、小寫字母代表不同標(biāo)識。2.構(gòu)造化程序設(shè)計(jì)〔1〕構(gòu)造化程序設(shè)計(jì)的根本特征：▼程序有3中根本構(gòu)造組成：順序構(gòu)造、選擇構(gòu)造、循環(huán)構(gòu)造▼整個(gè)程序采用模塊化構(gòu)造。模塊劃分的原則：模塊具有高聚度、模塊間具有低耦合度。▼有限的使用轉(zhuǎn)移語句，只限定在一個(gè)構(gòu)造的部跳轉(zhuǎn)，不允許從一個(gè)構(gòu)造跳到另一構(gòu)造。▼程序設(shè)計(jì)時(shí)采用“至頂向下、逐步詳細(xì)〞的實(shí)施方法?！?〕構(gòu)造化程序設(shè)計(jì)的3種根本構(gòu)造：順序構(gòu)造、選擇構(gòu)造、循環(huán)構(gòu)造3種根本構(gòu)造組成的算法只能完成符合構(gòu)造化的任務(wù)〔3〕構(gòu)造化程序設(shè)計(jì)的方法：逐步求精和模塊化程序設(shè)計(jì)方法。構(gòu)造化設(shè)計(jì)的總體思想是采用模塊化構(gòu)造，自上而下，逐步求精。3.面向?qū)ο蟪绦蛟O(shè)計(jì)●根本概念對象：系統(tǒng)中運(yùn)行的實(shí)體，是有特殊屬性〔數(shù)據(jù)〕和方法的實(shí)體類：由屬性和方法構(gòu)成。一組具有一樣的數(shù)據(jù)構(gòu)造和一樣的行為特征的對象的集合稱為類在面對對象的方法中，類的實(shí)例稱為對象面向?qū)ο蟪绦蛟O(shè)計(jì)特征的是：繼承性、多態(tài)性、封裝性在面向?qū)ο蟮姆椒ㄖ?，?shí)現(xiàn)信息隱蔽是依靠對象的封裝任何對象都必須有繼承性〔錯(cuò)〕例題精選:1.在面對對象的方法中，一個(gè)對象請求另一個(gè)對象為其效勞的方式是通過發(fā)送：信息2.面對對象的設(shè)計(jì)方法與傳統(tǒng)的面向過程的方法有本質(zhì)的區(qū)別,它的根本原理是:使用現(xiàn)實(shí)世界的概念抽象的思考問題從而自然地解決問題.3.構(gòu)造化方法中,軟件功能分解屬于軟件開發(fā)階段中的總體設(shè)計(jì)4.構(gòu)造化程序設(shè)計(jì)主要強(qiáng)調(diào)的是:程序的易讀性5.面向?qū)ο蟮脑O(shè)計(jì)程序主要考慮的是:提高軟件的可重用性6.類通過接口與外界發(fā)生關(guān)系.軟件工程根底1.軟件工程的根本概念(1)定義:軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合。軟件包括系統(tǒng)軟件和應(yīng)用軟件(2)軟件工程的根本思想是軟件開發(fā)中，應(yīng)用工程化原則進(jìn)展軟件開發(fā)，并將這個(gè)思想貫穿在軟件開發(fā)的整個(gè)過程中。軟件工程的3要素：方法、工具和過程(3)軟件的生命周期：從軟件定義、開發(fā)、使用、維護(hù)到報(bào)廢為止的整個(gè)過程。分三階段：設(shè)計(jì)階段、開發(fā)階段、維護(hù)階段包括：問題定義、可行性分析、需求分析、總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼、測試和維護(hù)問題定義：確定開發(fā)的任務(wù)可行性分析：確定問題的可行性需求分析：對用戶要求進(jìn)展分析，明確目標(biāo)系統(tǒng)要做什么總體設(shè)計(jì)：把軟件功能轉(zhuǎn)化為所需要的體系構(gòu)造，即如何解決問題。詳細(xì)設(shè)計(jì)：怎樣具體的解決問題2.構(gòu)造化分析方法〔1〕構(gòu)造化分析〔SA〕是面向數(shù)據(jù)流進(jìn)展需求分析的方法SA方法的根本思想正是運(yùn)用了分解和抽象兩個(gè)根本手段，采用：自頂向下，逐步分解的分析思路?！?〕數(shù)據(jù)流圖根本圖形符號：在構(gòu)造化方法中,用數(shù)據(jù)流程圖(DFD)作為描述工具的軟件開發(fā)階段是:需求分析(3)數(shù)據(jù)字典在構(gòu)造化分析的數(shù)據(jù)流圖中,利用數(shù)據(jù)字典對其中的圖形元素進(jìn)展確切解釋.3.軟件設(shè)計(jì)〔1〕概要設(shè)計(jì)〔總體設(shè)計(jì)〕◆包括兩個(gè)主要階段：系統(tǒng)設(shè)計(jì)〔確定具體的實(shí)現(xiàn)方案〕和構(gòu)造設(shè)計(jì)〔確定每個(gè)系統(tǒng)的模塊組成及模塊間的關(guān)系〕◆模塊之間聯(lián)系越嚴(yán)密,其耦合性就越強(qiáng),模塊的獨(dú)立性就越差;一個(gè)模塊個(gè)要素聯(lián)系越嚴(yán)密，則它的聚性就越高。模塊劃分原則：高聚低耦合〔2〕詳細(xì)設(shè)計(jì)◆構(gòu)造化程序設(shè)計(jì)的要點(diǎn)：采用自頂向下、逐步求精的程序設(shè)計(jì)方法，一個(gè)程序只有一個(gè)入口和一個(gè)出口?！粼敿?xì)設(shè)計(jì)的常用工具：程序流程圖、盒圖、PAD和PDL〔3〕軟件測試目的◆軟件測試的目的是盡可能多的發(fā)現(xiàn)程序中的錯(cuò)誤?！糗浖y試方法：靜態(tài)測試和動態(tài)測試〔黑盒測試法和白盒測試法〕黑盒測試包括：等價(jià)分析法、邊值分析法、因果圖法和錯(cuò)誤推測法白盒測試法測試的原則之一就是保證所測模塊中的每一個(gè)獨(dú)立的路徑至少執(zhí)行一次?！?〕程序調(diào)試分為靜態(tài)調(diào)試和動態(tài)調(diào)試調(diào)試的目的:改正錯(cuò)誤經(jīng)調(diào)試后還必須進(jìn)展再測試〔5〕軟件維護(hù)軟件維護(hù)就是在軟件已經(jīng)交付使用以后，為改正錯(cuò)誤或滿足新的需求而修改軟件的過程。例題精選：1．分析的結(jié)果是產(chǎn)生需求規(guī)格說明書。2．軟件詳細(xì)設(shè)計(jì)的主要任務(wù)是確定每一個(gè)模塊的算法和使用的數(shù)據(jù)構(gòu)造。3．進(jìn)展單元測試時(shí)，常用的方法時(shí)采用白盒測試，輔以黑盒測試。4．軟件工程的出現(xiàn)是由于軟件危機(jī)的出現(xiàn)，人們提出了軟件工程學(xué)的原理設(shè)計(jì)軟件。5．?dāng)?shù)據(jù)字典是各類數(shù)據(jù)描述的集合，通常包括4個(gè)局部：數(shù)據(jù)項(xiàng)、數(shù)據(jù)流、數(shù)據(jù)存儲和數(shù)據(jù)加工。數(shù)據(jù)庫設(shè)計(jì)根底1.數(shù)據(jù)庫〔1〕數(shù)據(jù)庫設(shè)計(jì)的根本目的是要解決數(shù)據(jù)共享的問題?！?〕數(shù)據(jù)庫的特點(diǎn)：▼數(shù)據(jù)按一定的數(shù)據(jù)模型組織和存儲。▼冗余度較小▼數(shù)據(jù)的獨(dú)立性較高。數(shù)據(jù)獨(dú)立性：數(shù)據(jù)的組織構(gòu)造和存儲方法與應(yīng)用程序互不依賴、彼此獨(dú)立。▼易擴(kuò)展▼可為多種用戶共享2.數(shù)據(jù)庫管理系統(tǒng)〔DBMS〕位于用戶與操作系統(tǒng)之間的完成數(shù)據(jù)管理的系統(tǒng)軟件。3.數(shù)據(jù)庫系統(tǒng)由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、應(yīng)用系統(tǒng)、數(shù)據(jù)庫管理員和用戶組成。最核心的局部是數(shù)據(jù)庫管理系統(tǒng)。4.數(shù)據(jù)模型〔1〕實(shí)體聯(lián)系模型及E-R圖3局部：實(shí)體、聯(lián)系和屬性實(shí)體集間的聯(lián)系：一對一聯(lián)系、一對多聯(lián)系和多對多聯(lián)系〔2〕層次、網(wǎng)狀、關(guān)系模型層次模型：有且只有一個(gè)結(jié)點(diǎn)無雙親，其他結(jié)點(diǎn)只有一個(gè)雙親。用樹形構(gòu)造來表示各實(shí)體與實(shí)體之間的聯(lián)系。在關(guān)系數(shù)據(jù)庫中，把數(shù)據(jù)表示成二維表，每個(gè)二維表稱為關(guān)系。一個(gè)關(guān)系對應(yīng)一二維表。關(guān)系的屬性名稱為關(guān)系模式。5.關(guān)系運(yùn)算〔1〕并〔2〕差〔3〕交〔4〕笛卡爾積〔×〕6.專門關(guān)系運(yùn)算：選擇、連接和投影〔1〕從關(guān)系中找到滿足條件的所有元組稱為