1、二級(jí)公共基礎(chǔ)學(xué)問考點(diǎn)總結(jié)第一章數(shù)據(jù)結(jié)構(gòu)與算法考點(diǎn)1：算法的概念和基本特點(diǎn)算法是指解題方案的精確而完整 的描述；算法的基本特點(diǎn)包括：（1）可行性：針對(duì)實(shí)際問題設(shè)計(jì)的算法,總是在某個(gè)特定運(yùn)算工具上執(zhí)行,往往要受到計(jì) 算工具的限制,使執(zhí)行結(jié)果產(chǎn)生偏差；（2）確定性：算法中每一步驟都必需有明確定義,不充許有模棱兩可的說明,不答應(yīng)有多 義性；（3）有窮性：算法必需能在有限的時(shí)間內(nèi)做完,即能在執(zhí)行有限個(gè)步驟后終止,包括合理 的執(zhí)行時(shí)間的含義；（4）擁有足夠的情報(bào)：擁有足夠的輸入；考點(diǎn)2：算法復(fù)雜度 算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的運(yùn)算工作量 即算法執(zhí)行過程中所

2、需基本運(yùn)算的執(zhí)行次數(shù) ；算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的 內(nèi)存空間；特別留意：時(shí)間復(fù)雜度與空間復(fù)雜度沒有必定的正比或反比的關(guān)系；考點(diǎn)3：數(shù)據(jù)的規(guī)律結(jié)構(gòu)與儲(chǔ)備結(jié)構(gòu)數(shù)據(jù)的規(guī)律結(jié)構(gòu)是反映數(shù)據(jù)元素之間規(guī)律關(guān)系的數(shù)據(jù)結(jié)構(gòu),關(guān)；與它們?cè)谶\(yùn)算機(jī)中的儲(chǔ)備位置無數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)（也稱物理結(jié)構(gòu)）是指數(shù)據(jù)的規(guī)律結(jié)構(gòu)在運(yùn)算機(jī)儲(chǔ)備空間中的存放形式；一種數(shù)據(jù)的規(guī)律結(jié)構(gòu)依據(jù)需要可以表示成多種儲(chǔ)備結(jié)構(gòu),常用的儲(chǔ)備結(jié)構(gòu)有次序,鏈接,索引等（包括線性結(jié)構(gòu)和非線性結(jié)構(gòu)）；而接受不同的儲(chǔ)備結(jié)構(gòu),其數(shù)據(jù)處理的效率是不同的；考點(diǎn)4：線性表的次序儲(chǔ)備結(jié)構(gòu)線性表的次序儲(chǔ)備結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：1 線性表中全部元素所占的儲(chǔ)備空間是連

3、續(xù)的2 線性表中各數(shù)據(jù)元素在儲(chǔ)備空間中是按規(guī)律次序依次存放的在程序設(shè)計(jì)語言中,通常定義一個(gè)一維數(shù)組來表示線性表的次序儲(chǔ)備空間第 1 頁,共 11 頁考點(diǎn)5：棧與隊(duì)列屬于線性結(jié)構(gòu) 1,棧棧是限定在一端進(jìn)行插入與刪除的線 性表；在棧中,答應(yīng)插入與刪除的一端稱為棧頂,不答應(yīng)插入與刪除的另一端稱為棧底；通常用指針top 指示棧頂?shù)奈恢?用指針bottom 指向棧底；top-bottom 的確定值加1 即為當(dāng)前棧中元素的個(gè)數(shù)；棧是依據(jù)“先進(jìn)后出”或“后進(jìn)先出”的原就組織數(shù)據(jù)的,用棧頂指針 top 動(dòng)態(tài)反映了棧中元素的變化情形,而不須轉(zhuǎn)變指針 bottom 的位置；棧具有記憶作用；2,隊(duì)列 隊(duì)列是指答應(yīng)在

4、一端進(jìn)行插入,而在另一端進(jìn)行刪除的線性表；答應(yīng)插入的一端稱為隊(duì)尾,通常用一個(gè)尾指針rear 指向隊(duì)尾元素,答應(yīng)刪除的一端稱為排頭（也稱隊(duì)頭）,通常用一個(gè)排頭指針front 指向排頭元素的前一個(gè)位置；隊(duì)列依據(jù)“先進(jìn)先出”或“后進(jìn)后出”的原就組織數(shù)據(jù),隊(duì)尾指針 同反映了隊(duì)列中元素動(dòng)態(tài)變化情形；在實(shí)際應(yīng)用中,隊(duì)列的次序儲(chǔ)備結(jié)構(gòu)一般接受循環(huán)隊(duì)列的形式,rear 和排頭指針front 共 循環(huán)隊(duì)列是規(guī)律上的環(huán)狀空間,但物理上仍然是線性結(jié)構(gòu)；從排頭指針front 指向的后一個(gè)位置直到隊(duì)尾指針rear 指向的位置之間全部的元素均為隊(duì)列中的元素；在一般隊(duì)列中,rear 指針位置減去 front 指針位置的差值

5、即為隊(duì)列中元素的個(gè)數(shù)；但在循環(huán)隊(duì)列中,rear 指針的位置可能大于 front 指針的位置,也可能小于 front 指針的位置,所以循環(huán)隊(duì)列的元素個(gè)數(shù)運(yùn)算方法如下：設(shè)循環(huán)隊(duì)列總?cè)萘繛?m假如rearfront ,就循環(huán)隊(duì)列的元素個(gè)數(shù)為 rear-front假如rearfront ,就循環(huán)隊(duì)列的元素個(gè)數(shù)為 m+rear-front棧與隊(duì)列的共同點(diǎn)：皆為線性結(jié)構(gòu),只答應(yīng)在端點(diǎn)處插入與刪除,而且不須移動(dòng)其他元素；第 2 頁,共 11 頁考點(diǎn)6：線性鏈表 線性表的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)稱為線性鏈表在鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)中,儲(chǔ)備數(shù)據(jù)結(jié)構(gòu)的儲(chǔ)備空間可以不連續(xù),素之間的規(guī)律關(guān)系可以不一樣；各數(shù)據(jù)結(jié)點(diǎn)的儲(chǔ)備次序與數(shù)據(jù)元鏈?zhǔn)絻?chǔ)備

6、結(jié)構(gòu)即可用于表示線性結(jié)構(gòu),也可用于表示非線性結(jié)構(gòu),棧與隊(duì)列也可以接受鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)；考點(diǎn)7：二叉樹的基本性質(zhì)樹是典型的非線性結(jié)構(gòu),在樹中,每個(gè)結(jié)點(diǎn)的前件稱為父結(jié)點(diǎn),沒有父結(jié)點(diǎn)的只有一個(gè),稱為根結(jié)點(diǎn)（有且僅有一個(gè)）；每個(gè)結(jié)點(diǎn)擁有的后件稱為子結(jié)點(diǎn),沒有子結(jié)點(diǎn)的稱為葉子結(jié)點(diǎn)；一個(gè)結(jié)點(diǎn)所擁有的子結(jié)點(diǎn)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度,葉子結(jié)點(diǎn)的度為 0；樹的最大層次稱為樹的深度；二叉樹：每個(gè)結(jié)點(diǎn)最大的度為 2,如下圖所示k-1 性質(zhì)1：在二叉樹的第 k 層上,最多有 2 個(gè)結(jié)點(diǎn)性質(zhì)2：深度為m 的二叉樹最多 有m 2 -1 個(gè)結(jié)點(diǎn)2 的結(jié)點(diǎn)多一個(gè)；性質(zhì)3：在任意一棵二叉樹中,度為0 的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總是比度為第 3

7、 頁,共 11 頁k-1 滿二叉樹：每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值,即第 k 層上有2 個(gè)結(jié)點(diǎn),且深度為 m 的滿二叉樹有 2 -1 個(gè)結(jié)點(diǎn)完全二叉樹：除最終一層外,每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最終一層上只缺少右邊的如干結(jié)點(diǎn)；當(dāng)完全二叉樹有n 個(gè)結(jié)點(diǎn),如n 為偶數(shù),就有n/2 個(gè)葉子結(jié)點(diǎn)；如n 為奇數(shù),就有n/2+1 個(gè)葉子結(jié)點(diǎn)（ 表示只取整數(shù)部分）； 考點(diǎn)8：二叉樹的遍歷（1）前序遍歷（DLR）,第一拜望根結(jié)點(diǎn),然后遍歷左子樹,最終遍歷右子樹；（2）中序遍歷（LDR）,第一遍歷左子樹,然后拜望根結(jié)點(diǎn),最終遍歷右子樹；（3）后序遍歷（LRD）第一遍歷左子樹,然后拜望遍歷右子樹,最終拜望根結(jié)點(diǎn)

8、；考點(diǎn)9：查找技術(shù)對(duì)于長(zhǎng)度為n 的線性表：次序查找在最壞情形下,需要比較 n 次；二分法查找只適用于次序儲(chǔ)備的有序表,在最壞情形下只需要比較 log2n 次；考點(diǎn)10：排序技術(shù)在最壞情形下,對(duì)于長(zhǎng)度為 n 的線性表,冒泡排序法,快速排序法,簡(jiǎn)潔插入排序法,簡(jiǎn)潔選擇排序法都需要比較 nn-1/2 次；希爾排序法需要比較 On1.5 次；堆排序法需要比較Onlog 2n次；在各種排序法中,冒泡排序法最簡(jiǎn)潔,比較次數(shù)最少（通常少于nn-1/2 次）；查找技術(shù)n最壞情形下的次數(shù)（時(shí)間復(fù)雜度）次序查找log 2 n 二分法查找排序技術(shù) 冒泡排序法nn-1/2 交換類排序快速排序法On 插入類排序簡(jiǎn)潔插入

9、排序法希爾排序法選擇類排序簡(jiǎn)潔選擇排序法Onlog 2 n 堆排序法其次章程序設(shè)計(jì)基礎(chǔ)考點(diǎn)1：程序設(shè)計(jì)風(fēng)格主要風(fēng)格：清晰第一,效率其次形成良好的程序設(shè)計(jì)風(fēng)格應(yīng)留意的因素：1. 源程序的文檔化：要包含必要的程序注釋2. 數(shù)據(jù)說明的方法：數(shù)據(jù)說明的次序規(guī)范化3. 語句的結(jié)構(gòu)4. 輸入與輸出考點(diǎn)2：結(jié)構(gòu)化程序設(shè)計(jì)的原就1. 自頂向下2. 逐步求精3. 模塊化4. 限制使用goto 語句結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)包括次序結(jié)構(gòu),選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)；考點(diǎn)3：面對(duì)對(duì)象的基本概念1,對(duì)象的特點(diǎn)：標(biāo)識(shí)唯獨(dú)性,分類性,多態(tài)性,封裝性（實(shí)現(xiàn)信息隱匿）2,類是具有共同屬性,共同方法的對(duì)象的集合,類具有繼承性 3,類與對(duì)

10、象的關(guān)系：類是對(duì)象的抽象,對(duì)象就是其對(duì)應(yīng)類的一個(gè)實(shí)例,模塊獨(dú)立性第三章軟件工程基礎(chǔ)考點(diǎn)1：軟件的定義及特點(diǎn)運(yùn)算機(jī)軟件是包括程序,數(shù)據(jù)及相關(guān)文檔的完整集合；軟件的特點(diǎn)包括：（1）軟件是一種規(guī)律實(shí)體,而不是物理實(shí)體；（2）軟件的生產(chǎn)與硬件不同,它沒有明顯的制作過程；（3）軟件在運(yùn)行,使用期間不存在磨損,老化問題；（4）軟件的開發(fā),運(yùn)行對(duì)運(yùn)算機(jī)系統(tǒng)具有依靠性,受運(yùn)算機(jī)系統(tǒng)的限制,這導(dǎo)致了軟件移第 5 頁,共 11 頁植的問題；（5）軟件復(fù)雜性高,成本昂貴；（6）軟件開發(fā)涉及諸多的社會(huì)因素；軟件按功能可以分為：應(yīng)用軟件,系統(tǒng)軟件和支撐軟件或工具軟件考點(diǎn)2：軟件工程的定義軟；件工程強(qiáng)調(diào)在軟件開發(fā)過程中應(yīng)

11、用工程化原就軟件工程包括3 個(gè)要素：方法,工具和過程；方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具支持軟件開發(fā),治理,文檔生成；過程支持軟件開發(fā)的各個(gè)環(huán)節(jié)的把握,治理考點(diǎn)3：軟件生命周期1. 定義階段：可行性爭(zhēng)論,需求分析2. 開發(fā)階段：概要設(shè)計(jì),詳細(xì)設(shè)計(jì),實(shí)現(xiàn),測(cè)試3. 愛惜階段：使用,愛惜,退役考點(diǎn)4：結(jié)構(gòu)化分析方法1,結(jié)構(gòu)化分析的常用工具1 數(shù)據(jù)流圖（DFD ）加工數(shù)據(jù)流儲(chǔ)備文件數(shù)據(jù)源 源,潭2 數(shù)據(jù)字典：作用是對(duì)DFD 中顯現(xiàn)的被命名的圖形元素的精確說明3 判定樹4 判定表2,軟件需求規(guī)格說明書：是需求分析階段的最終成果；其最重要的特點(diǎn)是無歧義性；考點(diǎn)5：結(jié)構(gòu)化設(shè)計(jì)方法1,軟件設(shè)計(jì)的分類從技

12、術(shù)觀點(diǎn)來看,軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì),數(shù)據(jù)設(shè)計(jì),接口設(shè)計(jì),過程設(shè)計(jì)從工程治理角度來看,軟件設(shè)計(jì)分兩步完成：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)2,衡量軟件模塊獨(dú)立性的兩個(gè)標(biāo)準(zhǔn)內(nèi)聚性：是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量耦合性：是模塊間相互連接的緊密程度的度量在程序結(jié)構(gòu)中,各模塊的內(nèi)聚性越強(qiáng),就耦合性越弱；優(yōu)秀的軟件設(shè)計(jì)應(yīng)盡量做到高內(nèi)聚,低耦合；第 6 頁,共 11 頁3,概要設(shè)計(jì)（軟件結(jié)構(gòu)設(shè)計(jì)）概要設(shè)計(jì)的常用工具是結(jié)構(gòu)圖（SC）結(jié)構(gòu)圖的有關(guān)術(shù)語：1 深度：結(jié)構(gòu)圖的最大層次數(shù)2 寬度：結(jié)構(gòu)圖橫向上最大模塊數(shù)3 扇出：一個(gè)模塊擁有的下級(jí)從屬模塊的個(gè)數(shù)4 扇入：一個(gè)模塊擁有的上級(jí)模塊的個(gè)數(shù)留意：軟件模塊的

13、規(guī)模要適中4,詳細(xì)設(shè)計(jì)（軟件過程設(shè)計(jì)）常用的過程設(shè)計(jì)工具有：圖形工具：程序流程圖,表格工具：判定表N-S 圖,PAD 圖,HIPO 圖語言工具：PDL （偽代碼）程序流程圖的基本圖符把握流加工步驟規(guī)律條件第 7 頁,共 11 頁考點(diǎn)6：軟件測(cè)試1,軟件測(cè)試的目的：盡可能多的發(fā)覺錯(cuò)誤,而不是證明程序是否正確；2,軟件測(cè)試的準(zhǔn)就1 全部測(cè)試都應(yīng)回溯到需求2 嚴(yán)格執(zhí)行方案,排除任憑性3 充分留意測(cè)試中的群集現(xiàn)象4 程序員應(yīng)防止檢查自己的程序5 窮舉測(cè)試不行能6 妥當(dāng)儲(chǔ)存測(cè)試方案3,軟件測(cè)試的方法1 靜態(tài)測(cè)試：包括代碼走查,靜態(tài)結(jié)構(gòu)分析,代碼質(zhì)量度量等,可以由人工進(jìn)行；2 動(dòng)態(tài)測(cè)試：是基于運(yùn)算機(jī)的測(cè)試

14、,設(shè)計(jì)合理的測(cè)試用例去運(yùn)行程序,以便發(fā)覺錯(cuò)誤；測(cè)試用例的格式為 （輸入值集）, 輸出值集 常用的動(dòng)態(tài)測(cè)試方法又分為：白盒測(cè)試：針對(duì)軟件程序內(nèi)部規(guī)律結(jié)構(gòu)進(jìn)行測(cè)試,其基本原就是保證所測(cè)模塊中每一獨(dú)立路徑至少執(zhí)行一次；白盒測(cè)試的主要方法有規(guī)律掩蓋,基本路徑測(cè)試；黑盒測(cè)試：完全不考慮程序內(nèi)部的規(guī)律結(jié)構(gòu)和內(nèi)部特性,只是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否中意需求進(jìn)行測(cè)試,檢查程序的功能是否符合它的功能說明；黑盒測(cè)試方法主要有等價(jià)類劃分法,邊界值分析法,錯(cuò)誤估量法,因果圖等；4,軟件測(cè)試的實(shí)施軟件測(cè)試分4 個(gè)步驟：?jiǎn)卧獪y(cè)試,集成測(cè)試,驗(yàn)收測(cè)試（確認(rèn)測(cè)試）和系統(tǒng)測(cè)試特別留意4 個(gè)步驟的次序考點(diǎn)7：程序的調(diào)試debug

15、程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤程序調(diào)試的基本步驟：1. 錯(cuò)誤定位2. 修改設(shè)計(jì)和代碼,以排除錯(cuò)誤3. 進(jìn)行回來測(cè)試,防止引進(jìn)新的錯(cuò)誤第四章數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)考點(diǎn)1：數(shù)據(jù)庫系統(tǒng)的基本概念1 數(shù)據(jù)庫設(shè)計(jì)的根本目標(biāo)：實(shí)現(xiàn)數(shù)據(jù)共享2 數(shù)據(jù)庫治理系統(tǒng)（DBMS ）：是數(shù)據(jù)庫系統(tǒng)的核心,是在操作系統(tǒng)支持下的系統(tǒng)軟件；是實(shí)現(xiàn)各種數(shù)據(jù)治理功能的核心軟件；數(shù)據(jù)庫治理系統(tǒng)通過供應(yīng)數(shù)據(jù)語言完成各項(xiàng)功能,主要包括：數(shù)據(jù)定義語言（DDL ）：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建 數(shù) 據(jù) 操 縱 語 言 DML ）：負(fù)責(zé)數(shù)據(jù)的操縱,包括查詢及增,刪,改等操作（數(shù)據(jù)把握語 DCL ）：負(fù)責(zé)數(shù)據(jù)完整性,安全性的定義與檢

16、查以及并發(fā)把握,故障恢 言（復(fù)等功能3 數(shù)據(jù)庫系統(tǒng)（DBS ）由五部分組成：數(shù)據(jù)庫,數(shù)據(jù)庫治理系統(tǒng),數(shù)據(jù)庫治理員,硬件平臺(tái),軟件平臺(tái) 數(shù)據(jù)庫系統(tǒng)需要操作系統(tǒng)（OS）的支持第 8 頁,共 11 頁考點(diǎn)2：數(shù)據(jù)庫系統(tǒng)的進(jìn)展 分三個(gè)階段：人工治理,文件系統(tǒng),數(shù)據(jù)庫系統(tǒng)；其中數(shù)據(jù)庫系統(tǒng)階段實(shí)現(xiàn)的數(shù)據(jù)共享程度最大,數(shù)據(jù)獨(dú)立性最高；考點(diǎn)3：數(shù)據(jù)庫系統(tǒng)的基本特點(diǎn)（1）數(shù)據(jù)的集成性如在關(guān)系數(shù)據(jù)庫中接受二維表作為統(tǒng)一的結(jié)構(gòu)方式；（2）數(shù)據(jù)的高共享性與低冗余性數(shù)據(jù)一樣性是指在系統(tǒng)中同一數(shù)據(jù)的 不同顯現(xiàn)應(yīng)保持相同的值；（3）數(shù)據(jù)獨(dú)立性數(shù)據(jù)獨(dú)立性是數(shù)據(jù)與程序間的互不依靠性,應(yīng)用程序；分為物理獨(dú)立性和規(guī)律獨(dú)立性；即數(shù)據(jù)

17、庫中數(shù)據(jù)獨(dú)立于應(yīng)用程序而不依靠于物理獨(dú)立性：數(shù)據(jù)的物理結(jié)構(gòu)（包括儲(chǔ)備結(jié)構(gòu),存取方式等）的轉(zhuǎn)變,不影響 數(shù)據(jù)庫的規(guī)律結(jié)構(gòu),從而不致引起應(yīng)用程序的變化；規(guī)律獨(dú)立性：數(shù)據(jù)庫總體規(guī)律結(jié)構(gòu)的轉(zhuǎn)變,不需要相應(yīng)修改應(yīng)用程序；（4）數(shù)據(jù)統(tǒng)一治理與把握 數(shù)據(jù)的完整性檢查數(shù)據(jù)的安全性愛惜 并發(fā)把握考點(diǎn)4：數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系 數(shù)據(jù)庫系統(tǒng)具有三級(jí)模式：（1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)規(guī)律結(jié)構(gòu)的描述,全體用戶公共數(shù)據(jù)視圖；（2）外模式：也稱子模式與用戶模式；是用戶的數(shù)據(jù)視圖,也就是用戶所見到的數(shù)據(jù)模式；一個(gè)概念模式可以推導(dǎo)出多個(gè)外模式；（3）內(nèi)模式：又稱物理模式,它給出了數(shù)據(jù)庫物理儲(chǔ)備結(jié)構(gòu)與物理存取方法；如索

18、引等考點(diǎn)5：E-R 模型 E-R 模型的三個(gè)要素：1. 實(shí)體：現(xiàn)實(shí)世界中的事物；在E-R 圖中用矩形框表示；2. 屬性：事物的特性；在E-R 圖中用橢圓表示；3. 聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)系；在E-R 圖中用菱形框表示；聯(lián)系類型有3 種：1 對(duì)1,1 對(duì)多,多對(duì)多；特別留意實(shí)體間聯(lián)系的舉例,如學(xué)校與校長(zhǎng),同學(xué)與宿舍,同學(xué)與課程等；考點(diǎn)6：關(guān)系模型的特點(diǎn)關(guān)系模型接受二維表（也稱為關(guān)系）表示,二維表中列稱為屬 性,行稱為元組,凡能惟一標(biāo)識(shí)元組的最小屬性集稱為該表的鍵或碼；二維表應(yīng)中意7 個(gè)性質(zhì)：二維表中元組個(gè)數(shù)是有限的元組個(gè)數(shù)有限性 二維表中元組均不相同元組的惟一性二維表中元組的次序可以 任意交換元組的次序無關(guān)性二維表中元組的重量是不行分割的 基本數(shù)據(jù)項(xiàng)元組重量的原子性二維表中屬性名各不相同屬性名惟一性二維表中屬性與 次序無關(guān),可任意交換屬性的次序無關(guān)性第 9 頁,共 11 頁二維表屬性的重量具有與該屬性相同的值域重量值域的同