二級(jí)公共基礎(chǔ)知識(shí)精華

1、公共基礎(chǔ)補(bǔ)充知識(shí)點(diǎn)公共基礎(chǔ)復(fù)習(xí)方法：第一：請(qǐng)把10頁(yè)紙背下來(lái)；第二：把習(xí)題冊(cè)的公共基礎(chǔ)題目做好；第三：結(jié)合考前公共基礎(chǔ)補(bǔ)充知識(shí)復(fù)習(xí)好；（注意：下劃線的一般是選擇題目，框起來(lái)的一般是填空題目，沒(méi)有下劃線和方框標(biāo)識(shí)的一般也是選擇題目）數(shù)據(jù)結(jié)構(gòu)與算法算法的基本特性：可行性，確定性，有窮性，擁有足夠的情報(bào)。算法是指解題方案準(zhǔn)確而完善的描述。算法復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算機(jī)工作量?？臻g復(fù)雜度：執(zhí)行算法所要的內(nèi)存空間。數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。常用的存儲(chǔ)結(jié)構(gòu)有順序結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：

2、數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。隊(duì)：FIFO，一頭進(jìn)，另一頭出來(lái)。循環(huán)隊(duì)列，一般題型：概念、計(jì)算隊(duì)列中還有幾個(gè)元素（尾指針減去頭指針）。棧：FILO，只能從一個(gè)頭進(jìn)，出。一般題型：概念、問(wèn)A B C D四個(gè)選項(xiàng)中不能出棧的次序。線性表的基本概念。記住線性表頂多有一個(gè)頭節(jié)點(diǎn)和一個(gè)后繼節(jié)點(diǎn)。所以棧、隊(duì)列、單向鏈表都是線性表，樹(shù)、雙向鏈表不是線性表。樹(shù)；葉子節(jié)點(diǎn)最多的個(gè)數(shù)：n-1個(gè)節(jié)點(diǎn)。一共的節(jié)點(diǎn)數(shù)目2n-1，節(jié)點(diǎn)為的數(shù)目為節(jié)點(diǎn)為1的數(shù)目減一。也就是n2=n0-1滿二叉樹(shù)： .完全二叉樹(shù)： . 二叉樹(shù)中，度為的數(shù)目比度為2的數(shù)目多一個(gè)。 n0=n2+1二叉樹(shù)的前序遍歷、中序遍歷、后序遍歷

3、是考試重點(diǎn)。順序查找：長(zhǎng)度為的線性表，平均要進(jìn)行，最壞要進(jìn)行次比較。（?？迹┒植檎遥簩?duì)于長(zhǎng)度為的線性表，在最壞情況進(jìn)行l(wèi)og2n次。要背的話：算法的時(shí)間復(fù)雜度和空間復(fù)雜度沒(méi)有必然的聯(lián)系。一個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)根據(jù)需要可以有多個(gè)存儲(chǔ)結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)的不同，會(huì)造成處理的效率不同。棧具有記憶性。如果要存的數(shù)據(jù)是1 2 3 4 5，?？梢圆豁樞虼鎯?chǔ)。我們存放數(shù)據(jù)的時(shí)候，存儲(chǔ)空間不一定是連續(xù)的，并且各個(gè)元素的存儲(chǔ)順序可以是任意的。如：鏈表。 在線性鏈表中查找一個(gè)元素比在順序表中查找一個(gè)元素要快，冒泡排序、選擇排序、交換排序、堆排序中平均排序次數(shù)最快的是堆排序。能夠用二分查找的是順序存儲(chǔ)的有序線性表。邏輯

4、結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)線性表鏈表，順序存放棧鏈表，順序存放隊(duì)列鏈表，順序存放樹(shù)鏈?zhǔn)酱娣哦鏄?shù)鏈?zhǔn)酱娣懦绦蛟O(shè)計(jì)基礎(chǔ)1、 程序設(shè)計(jì)方法和技術(shù)的發(fā)展經(jīng)過(guò)了結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο笤O(shè)計(jì)兩個(gè)階段。2、 當(dāng)今程序設(shè)計(jì)的風(fēng)格是“清晰第一，效率第二”。3、 程序可以沒(méi)有輸入，但是一定要有輸出。4、 結(jié)構(gòu)化程序設(shè)計(jì)遵循：自頂向下，逐步求精，模塊化，限制使用goto語(yǔ)句（?？迹?、 面向?qū)ο蟮幕咎攸c(diǎn)：標(biāo)志唯一性，分類性，多態(tài)性，封裝性，模塊獨(dú)立性。尤其重要的是多態(tài)性和封裝性。沒(méi)有類比性。6、 多態(tài)性：統(tǒng)一操作可以是不同對(duì)象的行為。同樣的消息被不同的對(duì)象接收時(shí)可導(dǎo)致不同的動(dòng)作的現(xiàn)象。7、 封裝性：從外面看不到對(duì)象的內(nèi)部，

5、只能看到對(duì)象的外部特性。8、 類：是具有共同屬性、共同方法的對(duì)象的集合。描述了屬于該對(duì)象類型的所有對(duì)象的性質(zhì)，而一個(gè)對(duì)象則是對(duì)應(yīng)類的一個(gè)實(shí)例。（常考）9、 消息：是指對(duì)象間的相互合作的協(xié)作機(jī)制，是一個(gè)對(duì)象與另一個(gè)對(duì)象之間的傳遞的消息。10、 繼承：是指使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。繼承分為單繼承和多繼承。單繼承只有一個(gè)父親，多繼承可以有多個(gè)父親。11、 面向?qū)ο笾?，類的?shí)例叫做對(duì)象。12、 源程序文檔化要求程序應(yīng)該加上注釋。注釋一般為序言性注釋和功能性注釋。13、 面向?qū)ο蠓椒ê图夹g(shù)是以對(duì)象為核心。軟件工程基礎(chǔ)1、 軟件工程的核心思想是把軟件當(dāng)作一個(gè)工程產(chǎn)品來(lái)處理。2、 軟件開(kāi)發(fā)

6、的三個(gè)階段以及每個(gè)階段的任務(wù)：可行性研究初步項(xiàng)目計(jì)劃需求分析概要設(shè)計(jì)詳細(xì)分析實(shí)現(xiàn)測(cè)試使用維護(hù)退役定義階段開(kāi)發(fā)階段維護(hù)階段這個(gè)表請(qǐng)大家抽時(shí)間背下。軟件開(kāi)發(fā)的三個(gè)階段，每個(gè)階段的工程。3、 軟件開(kāi)發(fā)方法包括分析方法，設(shè)計(jì)方法，程序設(shè)計(jì)方法。4、 結(jié)構(gòu)化方法包括結(jié)構(gòu)化分析方法，結(jié)構(gòu)化設(shè)計(jì)方法，結(jié)構(gòu)化編程方法。5、 結(jié)構(gòu)化分析方法在軟件需求分析階段的應(yīng)用。6、 結(jié)構(gòu)化分析常用的工具中最重要的工具是數(shù)據(jù)流圖。表示加工，表示數(shù)據(jù)流，數(shù)據(jù)源，表示源。7、 軟件規(guī)格說(shuō)明書(shū)（SRS）是需求分析階段的最后結(jié)果，是軟件開(kāi)發(fā)文檔重要的文檔之一。8、 軟件設(shè)計(jì)要求低耦合性和高內(nèi)聚性是考試的重點(diǎn),要知道什么是耦合,什么是

7、內(nèi)聚。9、 軟件測(cè)試和程序調(diào)試的區(qū)別。軟件測(cè)試的過(guò)程涵蓋了整個(gè)軟件生命周期。目的是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。10、 從是否要執(zhí)行被測(cè)試軟件的角度，軟件測(cè)試分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。11、 從功能上劃分，軟件測(cè)試分為白盒測(cè)試和黑盒測(cè)試。12、 白盒測(cè)試是檢查內(nèi)部成分，方法有：邏輯覆蓋測(cè)試方法，基本路徑測(cè)試。13、 黑盒測(cè)試是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿足需求進(jìn)行測(cè)試和驗(yàn)證。方法有：等價(jià)類劃分法，邊界值劃分法，錯(cuò)誤推測(cè)法。14、 軟件測(cè)試的四個(gè)步驟。自己默寫一遍。15、 程序調(diào)試的任務(wù)：診斷和改正程序中錯(cuò)誤，它和軟件測(cè)試不同，調(diào)試主要在開(kāi)發(fā)階段。16、 軟件調(diào)試方法：強(qiáng)制排錯(cuò)法，回朔法，原因排除法

8、。17、 軟件維護(hù)不屬于軟件生命周期開(kāi)發(fā)階段的任務(wù)。18、 軟件進(jìn)行了程序調(diào)試后還要進(jìn)行測(cè)試。19、 軟件工程的主要思想是：強(qiáng)調(diào)在軟件開(kāi)發(fā)過(guò)程中需要應(yīng)用工程化的原則。20、 軟件設(shè)計(jì)中，不屬于過(guò)程設(shè)計(jì)工具的是：DFD圖。21、 結(jié)構(gòu)化分析常見(jiàn)的工具：DFD圖，DD（數(shù)據(jù)字典），判定樹(shù)，判定表。22、 程序和軟件是不同的，軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合。23、 軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性。24、 軟件工程的三要素：工具、過(guò)程、方法。25、 軟件生命周期中，能夠準(zhǔn)確確定軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是：需求分析。26、 數(shù)據(jù)流圖只含有數(shù)據(jù)流，不含有控制流。數(shù)據(jù)流圖用于抽象

9、描述一個(gè)軟件的邏輯模型。27、 數(shù)據(jù)流的類型有兩種：事務(wù)型和變換型。在很多軟件應(yīng)用中，存在某種作業(yè)數(shù)據(jù)流，它可以引發(fā)一個(gè)或多個(gè)處理，這些處理能夠完成該作業(yè)要求的功能，這種數(shù)據(jù)流叫做事務(wù)型數(shù)據(jù)流。28、 程序流程圖中的箭頭代表的是：控制流。29、 在結(jié)構(gòu)化方法中，軟件功能分解屬于總體設(shè)計(jì)階段。30、 內(nèi)聚型中內(nèi)聚性最強(qiáng)的是：功能內(nèi)聚。31、 檢查軟件產(chǎn)品是否符合需求定義的過(guò)程是：確認(rèn)測(cè)試。32、 軟件危機(jī)：泛指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)過(guò)程中遇到的一系列嚴(yán)重的問(wèn)題。33、 Jackson 方法是一種面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化方法。34、 軟件開(kāi)發(fā)環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件開(kāi)發(fā)工具集合。35、 軟

10、件需求是指用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能設(shè)計(jì)約束等方面的期望。36、 為每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)的是詳細(xì)設(shè)計(jì)階段的任務(wù)。數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)1、 關(guān)系運(yùn)算是考試的重點(diǎn)，考的多的是并和笛卡爾積。不改變屬性但減少元組個(gè)數(shù)的是并。投影也是比較喜歡考的，一般的意思是從4、5個(gè)列中選出2、3個(gè)。笛卡爾積則是會(huì)增加元組的個(gè)數(shù)。2、 E-R圖中，矩形、菱形、橢圓形等代表的意思是考試的重點(diǎn)。3、 數(shù)據(jù)庫(kù)系統(tǒng)中，數(shù)據(jù)的物理結(jié)構(gòu)不一定要和邏輯結(jié)構(gòu)一致。4、 數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問(wèn)題。5、 數(shù)據(jù)庫(kù)系統(tǒng)中，用戶所見(jiàn)的數(shù)據(jù)模式為：外模式。6、 數(shù)據(jù)庫(kù)設(shè)計(jì)的四個(gè)階段是：需求分析、概念設(shè)計(jì)、邏輯

11、設(shè)計(jì)和物理設(shè)計(jì)。7、 兩個(gè)實(shí)體間的關(guān)系是：一對(duì)一，多對(duì)多，一對(duì)多等，這種題目根據(jù)具體的題目分析。（?？碱}目）8、 數(shù)據(jù)庫(kù)DB，數(shù)據(jù)庫(kù)系統(tǒng)DBS，數(shù)據(jù)庫(kù)管理系統(tǒng)DBMS之間的關(guān)系：DBS包含DB和DBMS。9、 數(shù)據(jù)庫(kù)系統(tǒng)的核心：數(shù)據(jù)庫(kù)管理系統(tǒng)。10、數(shù)據(jù)獨(dú)立性：是指數(shù)據(jù)與程序的互不依賴性。他包括數(shù)據(jù)的物理獨(dú)立性和邏輯獨(dú)立性。物理獨(dú)立性是數(shù)據(jù)的物理結(jié)構(gòu)（包括存儲(chǔ)結(jié)構(gòu)、存取方式）的改變，不影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)。11、數(shù)據(jù)的邏輯獨(dú)立性是指數(shù)據(jù)庫(kù)總體邏輯結(jié)構(gòu)的改變，不需要相應(yīng)修改應(yīng)用程序。12、用樹(shù)形結(jié)構(gòu)表示實(shí)體之間聯(lián)系的模型是：層次模型。13、數(shù)據(jù)庫(kù)系統(tǒng)中修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、改變數(shù)據(jù)間的

12、聯(lián)系等，不需要相應(yīng)修改應(yīng)用程序這一特點(diǎn)是邏輯獨(dú)立性。14、不涉及具體的硬件環(huán)境和平臺(tái)，也與具體的軟件環(huán)境無(wú)關(guān)的模式是：概念模型。15、用戶數(shù)據(jù)是建立在外模式的框架上的。16、給出數(shù)據(jù)的全局邏輯結(jié)構(gòu)到數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)間的對(duì)應(yīng)關(guān)系的映射是：概念模式到內(nèi)模式的映射。17、網(wǎng)狀模型：不加任何的限制的無(wú)向圖。18、不準(zhǔn)關(guān)系應(yīng)用不存在的元組的約束是：參照完整性約束。19、數(shù)據(jù)庫(kù)設(shè)計(jì)包括兩個(gè)方面的設(shè)計(jì)內(nèi)容，它們是：概念設(shè)計(jì)和邏輯設(shè)計(jì)。20、數(shù)據(jù)庫(kù)設(shè)計(jì)中的主流方法是：面向數(shù)據(jù)的設(shè)計(jì)方法。21、數(shù)據(jù)庫(kù)概念設(shè)計(jì)過(guò)程分三個(gè)步驟進(jìn)行：首先選擇局部應(yīng)用，在局部視圖設(shè)計(jì)，最后進(jìn)行視圖集成。22、數(shù)據(jù)庫(kù)系統(tǒng)中，實(shí)現(xiàn)各種數(shù)據(jù)管理功能的核心軟件稱為數(shù)據(jù)庫(kù)管理系統(tǒng)。23、一個(gè)關(guān)系表的行稱為元組。24、在關(guān)系模型中，數(shù)據(jù)看成是二維表，每一個(gè)二維表稱為一個(gè)關(guān)系。25、數(shù)據(jù)管理技術(shù)經(jīng)歷了三個(gè)階段：人工管理、文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)。26、數(shù)據(jù)庫(kù)的基本特點(diǎn)：數(shù)據(jù)的集成性、數(shù)據(jù)的高共享性和低冗余性（?？迹?、數(shù)據(jù)的獨(dú)立性（?？迹?shù)據(jù)統(tǒng)一管理和控制。