2011年 二級公共基礎(chǔ) 考前背誦版本

1、二級公共基礎(chǔ)知識總結(jié)請認(rèn)真背誦該資料，至少要看三遍，劃橫線和方框的都是重點！第一章 數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法算法：是指解題方案的準(zhǔn)確而完整的描述。算法不等于程序，也不等計算機方法，程序的編制不可能優(yōu)于算法的設(shè)計。算法的特征包括：（1）可行性；（2）確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性:（3）有窮性，算法必須能在有限的時間內(nèi)做完，包括合理的執(zhí)行時間的含義；（4）擁有足夠的情報。算法的基本要素：一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。指令系統(tǒng)：一個計算機系統(tǒng)能執(zhí)行的所有指令的集合?；具\算包括：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。算法的控制結(jié)

2、構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。算法復(fù)雜度：算法時間復(fù)雜度和算法空間復(fù)雜度。 兩個之間沒有聯(lián)系的。算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。1.2 數(shù)據(jù)結(jié)構(gòu)的基本基本概念數(shù)據(jù)結(jié)構(gòu)研究的三個方面：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；（3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運算。數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。線性結(jié)構(gòu)條件：（1）有且只有一個根

3、結(jié)點；（2）每一個結(jié)點最多有一個前件，也最多有一個后件。非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。13 線性表及其順序存儲結(jié)構(gòu)線性表是由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。在復(fù)雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個記錄構(gòu)成的線性表又稱為文件。線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：（1）線性表中所有元素的所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。14 棧和隊列棧是限定在一端進(jìn)行插入與刪除的線性表。1、先進(jìn)后出 FILO;1、支持子程序調(diào)用;2、具有記憶功能；3、可以不用順序存放數(shù)據(jù)；4

4、、只能夠在top首部進(jìn)行操作，bottom是絕對不動的；5、棧的存放數(shù)據(jù)的個數(shù)為 num = （bottom top）+1；隊列是指允許在一端（隊尾）進(jìn)入插入，而在另一端（隊頭）進(jìn)行刪除的線性表。1、Rear指針指向隊尾，front指針指向隊頭。3、先進(jìn)先出FIFO,或者是后進(jìn)后出LILO2、循環(huán)隊列里面的個數(shù)計算方法：A、rear front 的時候， num = rear front；B、rear 箭頭表示控制流，菱形表示邏輯條件。34 軟件測試軟件測試定義：使用人工或自動手段來運行或測定某個系統(tǒng)的過程，其目的在于檢驗它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實際結(jié)果之間的差別。軟件測試的目的

5、：發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。軟件測試方法：靜態(tài)測試和動態(tài)測試。靜態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實際運行軟件，主要通過人工進(jìn)行。動態(tài)測試：是基本計算機的測試，主要包括白盒測試方法和黑盒測試方法。白盒測試：在程序內(nèi)部進(jìn)行，主要用于完成軟件內(nèi)部CAO作的驗證。主要方法有邏輯覆蓋、基 本基路徑測試。黑盒測試：主要診斷功能不對或遺漏、界面錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能錯誤、初始化和終止條件錯，用于軟件確認(rèn)。白盒主要方法：1、邏輯覆蓋測試 2、基本路徑測試。黑盒主要方法：1等價類劃分法、2邊界值分析法、3錯誤推測法、4因果圖。軟件測試過程一般按4個步驟進(jìn)行（要背先后順序）：

6、單元測試、集成測試、驗收測試（確認(rèn)測試）和系統(tǒng)測試。35 程序的調(diào)試程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤，主要在開發(fā)階段進(jìn)行。軟件調(diào)試可分表靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和排錯，是主要的設(shè)計手段，動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。調(diào)試方法有：（1）強行排錯法；（2）回溯法；（3）原因排除法。第四章 數(shù)據(jù)庫設(shè)計基礎(chǔ)41 數(shù)據(jù)庫系統(tǒng)的基本概念數(shù)據(jù)：實際上就是描述事物的符號記錄。數(shù)據(jù)的特點：有一定的結(jié)構(gòu)，有型與值之分，如整型、實型、字符型等。數(shù)據(jù)庫：長期存儲在計算機內(nèi)部的、有組織、可共享的數(shù)據(jù)的集合。數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的具有集成與共享的特點。數(shù)據(jù)庫管

7、理系統(tǒng)：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫的核心。數(shù)據(jù)庫管理系統(tǒng)提供以下的數(shù)據(jù)語言：（1）數(shù)據(jù)定義語言：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；（2）數(shù)據(jù)操縱語言：負(fù)責(zé)數(shù)據(jù)的操縱，如查詢與增、刪、改等；（3）數(shù)據(jù)控制語言：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復(fù)等。數(shù)據(jù)語言按其使用方式具有兩種結(jié)構(gòu)形式：交互式命令(又稱自含型或自主型語言)宿主型語言（一般可嵌入某些宿主語言中）。數(shù)據(jù)庫管理員：對數(shù)據(jù)庫進(jìn)行規(guī)劃、設(shè)計、維護(hù)、監(jiān)視等的專業(yè)管理人員。數(shù)據(jù)庫系統(tǒng)：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、硬件平

8、臺（硬 件）、軟件平臺（軟件）五個部分構(gòu)成的運行實體。DBS是最大的包括其他所有的。數(shù)據(jù)庫應(yīng)用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。數(shù)據(jù)庫發(fā)展的三個階段：人工管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫管理階段。數(shù)據(jù)庫系統(tǒng)階段的基本特點：1、數(shù)據(jù)的集成性 、2、數(shù)據(jù)的高共享性與低冗余性 、3、數(shù)據(jù)獨立性（物理獨立性與邏輯獨立性）、數(shù)據(jù)統(tǒng)一管理與控制。數(shù)據(jù)庫系統(tǒng)的三級模式：（1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶公共數(shù)據(jù)視圖；（2）外模式：也稱子模式與用戶模式。是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式；（3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法。一個

9、數(shù)據(jù)庫只有一個內(nèi)模式，可以有多個外模式。數(shù)據(jù)庫系統(tǒng)的兩級映射：（1）概念模式到內(nèi)模式的映射；（2）外模式到概念模式的映射。4.2 數(shù)據(jù)模型數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信息表與操作提供一個抽象的框架。描述了數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作及數(shù)據(jù)約束。E-R模型的基本概念（1）實體：現(xiàn)實世界中的事物；（2）屬性：事物的特性；（3）聯(lián)系：現(xiàn)實世界中事物間的關(guān)系。實體集的關(guān)系有一對一、一對多、多對多的聯(lián)系。E-R模型的圖示法：（1）實體集表示法； （2）屬性表法； （3）聯(lián)系表示法。E-R模型的:矩形表示實體；橢圓表示矩形；棱形表示聯(lián)系。關(guān)系

10、模型采用二維表來表示，簡稱表，由表框架及表的元組組成。1、一個二維表就是一個關(guān)系。2、在二維表中凡能唯一標(biāo)識元組的最小屬性稱為鍵或碼。具有唯一性。3、元組就是二維表中一行，屬性就是二維表表中一列。4、從所有侯選健中選取一個作為用戶使用的鍵稱主鍵。5、表A中的某屬性是某表B的鍵，則稱該屬性集為A的外鍵或外碼。6、分量是不可以再分的。以上六點非常重要。關(guān)系中的數(shù)據(jù)約束：（1）實體完整性約束：約束關(guān)系的主鍵中屬性值不能為空值；（2）參照完全性約束：是關(guān)系之間的基本約束；（3）用戶定義的完整性約束：它反映了具體應(yīng)用中數(shù)據(jù)的語義要求。4.3關(guān)系代數(shù)關(guān)系數(shù)據(jù)庫系統(tǒng)的特點之一是它建立在數(shù)據(jù)理論的基礎(chǔ)之上，有

11、很多數(shù)據(jù)理論可以表示關(guān)系模型的數(shù)據(jù)操作，其中最為著名的是關(guān)系代數(shù)與關(guān)系演算。關(guān)系模型的基本運算：（1）插入 （2）刪除 (3)修改 （4）查詢（包括投影、選擇、笛卡爾積）兩個表的運算一般會考到：投影、鏈接、選擇、笛卡爾積、交、并當(dāng)中的一個。4.4 數(shù)據(jù)庫設(shè)計與管理數(shù)據(jù)庫設(shè)計是數(shù)據(jù)應(yīng)用的核心。數(shù)據(jù)庫設(shè)計的兩種方法：（1）面向數(shù)據(jù)：以信息需求為主，兼顧處理需求；（2）面向過程：以處理需求為主，兼顧信息需求。數(shù)據(jù)庫的生命周期：需求分析階段、概念設(shè)計階段、邏輯設(shè)計階段、物理設(shè)計階段、編碼階段、測試階段、運行階段、進(jìn)一步修改階段。需求分析常用結(jié)構(gòu)析方法和面向?qū)ο蟮姆椒?。結(jié)構(gòu)化分析（簡稱SA）方法用自頂向

12、下、逐層分解的方式分析系統(tǒng)。用數(shù)據(jù)流圖表達(dá)數(shù)據(jù)和處理過程的關(guān)系。對數(shù)據(jù)庫設(shè)計來講，數(shù)據(jù)字典是進(jìn)行詳細(xì)的數(shù)據(jù)收集和數(shù)據(jù)分析所獲得的主要結(jié)果。數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，包括5個部分：數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流（可以是數(shù)據(jù)項，也可以是數(shù)據(jù)結(jié)構(gòu)）、數(shù)據(jù)存儲、處理過程。數(shù)據(jù)庫概念設(shè)計的目的是分析數(shù)據(jù)內(nèi)在語義關(guān)系。公共基礎(chǔ)補充知識點1、 一個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)根據(jù)需要可以有多個存儲結(jié)構(gòu)。存儲結(jié)構(gòu)的不同，會造成處理的效率不同。2、程序設(shè)計方法和技術(shù)的發(fā)展經(jīng)過了結(jié)構(gòu)化程序設(shè)計和面向?qū)ο笤O(shè)計兩個階段。3、當(dāng)今程序設(shè)計的風(fēng)格是“清晰第一，效率第二”。4、程序可以沒有輸入，但是一定要有輸出。5、結(jié)構(gòu)化程序設(shè)計遵循

13、：自頂向下，逐步求精，模塊化，限制使用goto語句（?？迹?。6、面向?qū)ο蟮幕咎攸c：標(biāo)志唯一性，分類性，多態(tài)性，封裝性，模塊獨立性。尤其重要的是多態(tài)性和封裝性。沒有類比性。7、多態(tài)性：統(tǒng)一操作可以是不同對象的行為。同樣的消息被不同的對象接收時可導(dǎo)致不同的動作的現(xiàn)象。8、封裝性：從外面看不到對象的內(nèi)部，只能看到對象的外部特性。9、類：是具有共同屬性、共同方法的對象的集合。描述了屬于該對象類型的所有對象的性質(zhì)，而一個對象則是對應(yīng)類的一個實例。（?？迹?0、消息：是指對象間的相互合作的協(xié)作機制，是一個對象與另一個對象之間的傳遞的消息。11繼承：是指使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。繼承分為

14、單繼承和多繼承。12、面向?qū)ο笾校惖膶嵗凶鰧ο蟆?3、源程序文檔化要求程序應(yīng)該加上注釋。注釋一般為序言性注釋和功能性注釋。14、面向?qū)ο蠓椒ê图夹g(shù)是以對象為核心。軟件工程基礎(chǔ)1、 軟件工程的核心思想是把軟件當(dāng)作一個工程產(chǎn)品來處理。2、 軟件開發(fā)的三個階段以及每個階段的任務(wù)：可行性研究初步項目計劃需求分析概要設(shè)計詳細(xì)分析實現(xiàn)測試使用維護(hù)退役定義階段開發(fā)階段維護(hù)階段這個表請大家抽時間背下。軟件開發(fā)的三個階段，每個階段的工程。3、 軟件開發(fā)方法包括分析方法，設(shè)計方法，程序設(shè)計方法。4、 結(jié)構(gòu)化方法包括結(jié)構(gòu)化分析方法，結(jié)構(gòu)化設(shè)計方法，結(jié)構(gòu)化編程方法。5、 結(jié)構(gòu)化分析方法在軟件需求分析階段的應(yīng)用。6

15、、 結(jié)構(gòu)化分析常用的工具中最重要的工具是數(shù)據(jù)流圖。表示加工，表示數(shù)據(jù)流， 表示數(shù)據(jù)存儲（數(shù)據(jù)源） 表示源和潭 。7、 軟件規(guī)格說明書（SRS）是需求分析階段的最后結(jié)果，是軟件開發(fā)文檔重要的文檔之一。8、 軟件設(shè)計要求高耦合性和低內(nèi)聚性是考試的重點,要知道什么是耦合,什么是內(nèi)聚。9、 軟件測試和程序調(diào)試的區(qū)別。軟件測試的過程涵蓋了整個軟件生命周期。目的是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。10、從是否要執(zhí)行被測試軟件的角度，軟件測試分為靜態(tài)測試和動態(tài)測試。11、從功能上劃分，軟件測試分為白盒測試和黑盒測試。12、白盒測試是檢查內(nèi)部成分，方法有：邏輯覆蓋測試方法，基本路徑測試。13、黑盒測試是對軟件已經(jīng)

16、實現(xiàn)的功能是否滿足需求進(jìn)行測試和驗證。方法有：等價類劃分法，邊界值劃分法，錯誤推測法。14、 程序調(diào)試的任務(wù)：診斷和改正程序中錯誤，它和軟件測試不同，調(diào)試主要在開發(fā)階段。15、 軟件調(diào)試方法：強制排錯法，回朔法，原因排除法。16、 軟件維護(hù)不屬于軟件生命周期開發(fā)階段的任務(wù)。17、 軟件進(jìn)行了程序調(diào)試后還要進(jìn)行測試。18、 軟件工程的主要思想是：強調(diào)在軟件開發(fā)過程中需要應(yīng)用工程化的原則。19、 軟件設(shè)計中，不屬于過程設(shè)計工具的是：DFD圖。20、 結(jié)構(gòu)化分析常見的工具：DFD圖，DD（數(shù)據(jù)字典），判定樹，判定表。21、 程序和軟件是不同的，軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合。22、 軟件的開發(fā)、運

17、行對計算機系統(tǒng)具有依賴性。23、 軟件工程的三要素：工具、過程、方法。24、 軟件生命周期中，能夠準(zhǔn)確確定軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是：需求分析。25、 數(shù)據(jù)流圖只含有數(shù)據(jù)流，不含有控制流。數(shù)據(jù)流圖用于抽象描述一個軟件的邏輯模型。26、 數(shù)據(jù)流的類型有兩種：事務(wù)型和變換型。在很多軟件應(yīng)用中，存在某種作業(yè)數(shù)據(jù)流，它可以引發(fā)一個或多個處理，這些處理能夠完成該作業(yè)要求的功能，這種數(shù)據(jù)流叫做事務(wù)型數(shù)據(jù)流。27、 程序流程圖中的箭頭代表的是：控制流。28、 在結(jié)構(gòu)化方法中，軟件功能分解屬于總體設(shè)計階段。29、 內(nèi)聚型中內(nèi)聚性最強的是：功能內(nèi)聚。30、 檢查軟件產(chǎn)品是否符合需求定義的過程是

18、：確認(rèn)測試。31、 軟件危機：泛指在計算機軟件的開發(fā)和維護(hù)過程中遇到的一系列嚴(yán)重的問題。32、 Jackson 方法是一種面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化方法。33、 軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的軟件開發(fā)工具集合。34、 軟件需求是指用戶對目標(biāo)軟件系統(tǒng)在功能、行為、性能設(shè)計約束等方面的期望。35、 為每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)的是詳細(xì)設(shè)計階段的任務(wù)。數(shù)據(jù)庫設(shè)計基礎(chǔ)1、 關(guān)系運算是考試的重點，考的多的是并和笛卡爾積。不改變屬性但減少元組個數(shù)的是并。投影也是比較喜歡考的，一般的意思是從4、5個列中選出2、3個。笛卡爾積則是會增加元組的個數(shù)。2、 E-R圖中，矩形、菱形、橢圓形等代表的意思是

19、考試的重點。3、 數(shù)據(jù)庫系統(tǒng)中，數(shù)據(jù)的物理結(jié)構(gòu)不一定要和邏輯結(jié)構(gòu)一致。4、 數(shù)據(jù)庫技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問題。5、 數(shù)據(jù)庫系統(tǒng)中，用戶所見的數(shù)據(jù)模式為：外模式。6、 數(shù)據(jù)庫設(shè)計的四個階段是：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計。7、 兩個實體間的關(guān)系是：一對一，多對多，一對多等，這種題目根據(jù)具體的題目分析。（?？碱}目）8、 數(shù)據(jù)庫DB，數(shù)據(jù)庫系統(tǒng)DBS，數(shù)據(jù)庫管理系統(tǒng)DBMS之間的關(guān)系：DBS包含DB和DBMS。9、 數(shù)據(jù)庫系統(tǒng)的核心：數(shù)據(jù)庫管理系統(tǒng)。10、數(shù)據(jù)獨立性：是指數(shù)據(jù)與程序的互不依賴性。他包括數(shù)據(jù)的物理獨立性和邏輯獨立性。物理獨立性是數(shù)據(jù)的物理結(jié)構(gòu)（包括存儲結(jié)構(gòu)、存取方式）的改變，不影響數(shù)據(jù)庫的邏輯結(jié)構(gòu)。11、數(shù)據(jù)的邏輯獨立性是指數(shù)據(jù)庫總體邏輯結(jié)構(gòu)的改變，不需要相應(yīng)修改應(yīng)用程序。12、用樹形結(jié)構(gòu)表示實體之間聯(lián)系的模型是：層次模型。13、數(shù)據(jù)庫系統(tǒng)中修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、改變數(shù)據(jù)間的聯(lián)系等，不需要相