公共基礎(chǔ)知識(shí)

第一章 數(shù)據(jù)結(jié)構(gòu)與算法

【考點(diǎn)1】算法的基本概念

1、算法：是指一組有窮的指令集，是解題方案的準(zhǔn)確而完整的描述。算法不等于程序，也不等于計(jì)算方法。

2、算法的基本特征：

1）確定性，算法中每一步驟都必須有明確定義，不允許有多義性；

2）有窮性，算法必須能在有限的時(shí)間內(nèi)做完，即能在執(zhí)行有限個(gè)步驟后終止；

3）可行性，算法原則上能夠精確地執(zhí)行；

4）擁有足夠的情報(bào)。

3、算法的組成要素：一個(gè)算法由數(shù)據(jù)對(duì)象的運(yùn)算和操作以及其控制結(jié)構(gòu)這兩部分組成。

4、算法的基本運(yùn)算和操作：算術(shù)運(yùn)算，邏輯運(yùn)算，關(guān)系運(yùn)算，數(shù)據(jù)傳輸。

5、算法的基本控制結(jié)構(gòu)：順序，選擇，循環(huán)。

6、算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)。

【考點(diǎn)2】算法的復(fù)雜度

1、算法效率的度量——算法的復(fù)雜度：時(shí)間復(fù)雜度和空間復(fù)雜度。

1）算法時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量。通常，一個(gè)算法所用的時(shí)間包括編譯時(shí)間和運(yùn)行時(shí)間。

2）算法空間復(fù)雜度：指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的空間，算法執(zhí)行過程中所需的額外空間。

空間復(fù)雜度和時(shí)間復(fù)雜度并不相關(guān)。

【考點(diǎn)3】數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)：數(shù)據(jù)是客觀事物的符號(hào)表示，是能輸入到計(jì)算機(jī)中并被計(jì)算程序識(shí)別和處理的符號(hào)的總稱，如文檔，聲音，視頻等。

數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。

數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合。

數(shù)據(jù)結(jié)構(gòu)：是指由某一數(shù)據(jù)對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成的集合。

【考點(diǎn)4】邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)可分為數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。

1）數(shù)據(jù)的邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描述，與數(shù)據(jù)的存儲(chǔ)無關(guān)，是面向問題的，是獨(dú)立于計(jì)算機(jī)的。它包括數(shù)據(jù)對(duì)象和數(shù)據(jù)對(duì)象之間的關(guān)系。

2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)也稱為數(shù)據(jù)的物理結(jié)構(gòu)，是數(shù)據(jù)在計(jì)算機(jī)中的存放的方式，是面向計(jì)算機(jī)的，它包括數(shù)據(jù)元素的存儲(chǔ)方式和關(guān)系的存儲(chǔ)方式。

2、存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)的關(guān)系：一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示成多種存儲(chǔ)結(jié)構(gòu)即數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)不一定一一對(duì)應(yīng)。

3、常見的存儲(chǔ)結(jié)構(gòu)有：順序，鏈接，索引等。采用不同的存儲(chǔ)結(jié)構(gòu)其數(shù)據(jù)處理的效率是不同的。

【考點(diǎn)5】線性結(jié)構(gòu)和非線性結(jié)構(gòu)

1、線性結(jié)構(gòu)的條件（一個(gè)非空數(shù)據(jù)結(jié)構(gòu))：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。

2、非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。

棧、隊(duì)列、雙向鏈表是線性結(jié)構(gòu)，樹、二叉樹為非線性結(jié)構(gòu)。

【考點(diǎn)6】線性表及其順序存儲(chǔ)結(jié)構(gòu)

1、線性表是由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。

2、在復(fù)雜線性表中，由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄；由多個(gè)記錄構(gòu)成的線性表稱為文件。

3、非空線性表的結(jié)構(gòu)特征：

（1）有且只有一個(gè)根結(jié)點(diǎn)a1，它無前件；

（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無后件；

（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。

結(jié)點(diǎn)個(gè)數(shù)n稱為線性表的長度，當(dāng)n=0時(shí)，稱為空表。

4、線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：

（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；

（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。

元素ai的存儲(chǔ)地址為：ADR(ai)=ADR(a1)+(i-1)*k，ADR(a1)為第一個(gè)元素的地址，k代表每個(gè)元素占的字節(jié)數(shù)。

5、順序表的運(yùn)算：查找、插入、刪除。

【考點(diǎn)7】線性鏈表

線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡稱結(jié)點(diǎn)。結(jié)點(diǎn)由兩部分組成：(1) 用于存儲(chǔ)數(shù)據(jù)元素值，稱為數(shù)據(jù)域；(2) 用于存放指針，稱為指針域，用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn)。

在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。

鏈?zhǔn)酱鎯?chǔ)方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。

線性單鏈表中，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表。

雙向鏈表有兩個(gè)指針：左指針（Llink）指向前件結(jié)點(diǎn)，右指針（Rlink）指向后件結(jié)點(diǎn)。

循環(huán)鏈表：循環(huán)鏈表與單鏈表的不同的是它的最后一個(gè)結(jié)點(diǎn)的指針域存放的事指向第一個(gè)結(jié)點(diǎn)的指針而單鏈表存放的是空指針。

線性鏈表的基本運(yùn)算：查找、插入、刪除。

【考點(diǎn)8】棧

1、棧的基本概念

棧是一種特殊的線性表，只允許在表的一端進(jìn)行插入和刪除的線性表；插入，刪除的一端為棧頂，另一端為棧底；當(dāng)表中沒有元素時(shí)為空棧。

棧是一種后進(jìn)先出（或先進(jìn)后出Last In First Out）的線性表。棧具有記憶功能。棧的實(shí)例：火車調(diào)度，子彈夾。

2、棧的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)：用一組地址連續(xù)的存儲(chǔ)單元即一維數(shù)組來存儲(chǔ)；

鏈?zhǔn)酱鎯?chǔ)：用線性鏈表來存儲(chǔ)；

3、棧的基本運(yùn)算

(1) 入棧運(yùn)算，在棧頂位置插入元素；

(2) 退棧運(yùn)算，刪除元素(取出棧頂元素并賦給一個(gè)指定的變量)；

(3) 讀棧頂元素，將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無變化。

【考點(diǎn)9】隊(duì)列

1.隊(duì)列的基本概念

隊(duì)列是一種特殊的線性表，只允許在表的一端插入，在另一端刪除，允許插入的一端是隊(duì)尾（rear），允許刪除的一端為隊(duì)頭（front）；當(dāng)表中沒有元素是空隊(duì)列；隊(duì)列是一種先進(jìn)先出的線性表。(FIFO)

2、隊(duì)列的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)：一維數(shù)組。

鏈?zhǔn)酱鎯?chǔ)：線性鏈表。

3、隊(duì)列的運(yùn)算:

(1) 入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素； (2) 退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。

4、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。循環(huán)隊(duì)列s=0表示隊(duì)列為空；s=1且front=rear表示隊(duì)滿。

5、計(jì)算循環(huán)隊(duì)列的元素個(gè)數(shù)：“尾指針減頭指針”，若為負(fù)數(shù)，再加其容量即可。

【考點(diǎn)10】樹的基本概念

樹是一種非線性結(jié)構(gòu)，是n個(gè)結(jié)點(diǎn)的有限集。當(dāng)n=0 時(shí)為空樹，n>0時(shí)為非空樹。結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。

葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)。

分支結(jié)點(diǎn)：除葉子結(jié)點(diǎn)以外的結(jié)點(diǎn)。

結(jié)點(diǎn)的層次：根結(jié)點(diǎn)在第一層，同一層上左右結(jié)點(diǎn)的子結(jié)點(diǎn)在下一層。

樹的深度：所處層次最大的那個(gè)結(jié)點(diǎn)的層次。

樹的度：樹中所有結(jié)點(diǎn)的度的最大值。

【考點(diǎn)11】二叉樹及其基本性質(zhì)

1、二叉樹的概念

二叉樹是一種特殊的樹形結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)最多只有兩棵子樹，且有左右之分不能互換，因此，二叉樹有五種不同的形態(tài)。

2、二叉樹的性質(zhì)

性質(zhì)1 在二叉樹的第k層上，最多有2k-1(k≥1）個(gè)結(jié)點(diǎn)。

性質(zhì)2 深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)。

性質(zhì)3 在任意一棵二叉樹中，度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。

性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度不小于[log2n]+1,其中[log2n]表示為log2n的整數(shù)部分。

【考點(diǎn)12】滿二叉樹與完全二叉樹

滿二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m－1個(gè)結(jié)點(diǎn)。

完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。

滿二叉樹是完全二叉樹，而完全二叉樹一般不是滿二叉樹。

【考點(diǎn)13】完全二叉樹的性質(zhì)

性質(zhì)1 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。

性質(zhì)2 完全二叉樹中度為1的結(jié)點(diǎn)數(shù)為0或1。

【考點(diǎn)14】二叉樹的遍歷

1、前序遍歷：先訪問根結(jié)點(diǎn)、然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。

前序遍歷圖5可得：ABCDFHEG。

2、中序遍歷：先遍歷左子樹、然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。

中序遍歷圖5可得：BAFHDCGE。

3、后序遍歷：先遍歷左子樹、然后遍歷右子樹，最后訪問根結(jié)點(diǎn)；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。

后序遍歷圖5可得：BHFDGECA。

1. 算法的有窮性是指算法必須能執(zhí)行有限個(gè)步驟之后終止.

2. 算法的時(shí)間復(fù)雜度是指算法在執(zhí)行過程中所需要的基本運(yùn)算次數(shù)

3. 隊(duì)列、棧、線性表屬于線性數(shù)據(jù)結(jié)構(gòu)，二叉樹不屬于

4. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指： 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示

5. 一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率

6. 線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

7. 棧是先進(jìn)后出、后進(jìn)先出的線性鏈表，具有記憶作用，對(duì)棧的插入與刪除操作中，不需要改變棧底指針，是特殊的線性表，只能在一端插入或者刪除元素

8. 線性鏈表存儲(chǔ)空間不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的

9. 在深度為7的滿二叉樹中，葉子節(jié)點(diǎn)的個(gè)數(shù)為： 64

10. 能用二分法查找的是順序存儲(chǔ)的有序線性表

11. 對(duì)長度為N 的線性表進(jìn)行順序查找，在壞的情況下需要比較的次數(shù)為：N

12. 對(duì)于長度為N 的線性表，在壞的情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是： 快速排序?yàn)镹(N-1)/2

13. 算法的復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度

14. 算法在執(zhí)行過程中所需要的存儲(chǔ)空間稱為算法的空間復(fù)雜度

15. 問題處理方案的正確而完整的描述稱為算法

16. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)控件中的存放方式稱為數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu)或者物理結(jié)構(gòu)或者物理存儲(chǔ)結(jié)構(gòu)

17. 按照邏輯結(jié)構(gòu)分類，數(shù)據(jù)結(jié)構(gòu)可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，二叉樹屬于 非線性結(jié)構(gòu)

18. 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列屬于存儲(chǔ)結(jié)構(gòu)

19. 某二叉樹中度為2的結(jié)點(diǎn)有18個(gè)，則該二叉樹中共有 19個(gè)葉子結(jié)點(diǎn)

20. 一顆二叉樹第六層（根節(jié)點(diǎn)為層）的結(jié)點(diǎn)數(shù)多為32個(gè)

1. 在結(jié)構(gòu)化方法中，軟件功能分解屬于 總體設(shè)計(jì)階段

2. 軟件工程的三要素：工具 過程 方法

3. 若按功能劃分，軟件測試的方法通常分為 白盒測試和黑盒測試

4. 在進(jìn)行模塊測試時(shí)，要為每個(gè)被測試的模塊另外設(shè)計(jì)兩類模塊：驅(qū)動(dòng)模塊和承接模塊（樁模塊），其中 驅(qū)動(dòng)模塊的作用是將測試數(shù)據(jù)傳送給被測試的模塊，并顯示被測試模塊的測試結(jié)果

5. 程序測試分為靜態(tài)分析和報(bào)考測試，其中靜態(tài)分析（靜態(tài)測試）是指不執(zhí)行程序，而只是對(duì)程序文本進(jìn)行檢查，通過閱讀和討論，分析和發(fā)現(xiàn)程序中的錯(cuò)誤

6. 診斷和改正程序中錯(cuò)誤的工作通常稱為調(diào)試

7. 軟件是程序、數(shù)據(jù)和文檔的集合

8. 軟件工程研究的內(nèi)容主要是 軟件開發(fā)技術(shù)和軟件工程管理

9. 數(shù)據(jù)庫系統(tǒng)的核心是 數(shù)據(jù)庫管理系統(tǒng)

10. 數(shù)據(jù)庫系統(tǒng)的根本目標(biāo)是解決數(shù)據(jù)共享問題

11. 能給出數(shù)據(jù)庫物理存儲(chǔ)與物理存取方法的是內(nèi)模式

12. 在數(shù)據(jù)庫的兩極映射中，從概念模式到內(nèi)模式的映射一般由數(shù)據(jù)庫管理系統(tǒng)實(shí)現(xiàn)

13. 支持?jǐn)?shù)據(jù)庫各種操作的軟件系統(tǒng)叫作 數(shù)據(jù)庫管理系統(tǒng)

14. 數(shù)據(jù)庫（DB ）\數(shù)據(jù)庫系統(tǒng)（DBS ）、數(shù)據(jù)庫管理系統(tǒng)（DBMS ）之間的關(guān)系是：DBS 包含DB 和DBMS

15. 在關(guān)系數(shù)據(jù)庫模型中，通常可以把 字段 稱為屬性，其值稱為屬性值

16. 用樹形結(jié)構(gòu)來表示實(shí)體之間聯(lián)系的模型稱為 層次模型

17. 在E-R 圖中，用來表示實(shí)體的圖形是 矩形

18. 商品與顧客兩個(gè)實(shí)體之間的聯(lián)系一般是 多對(duì)多

19. 數(shù)據(jù)庫系統(tǒng)在其內(nèi)部分為三級(jí)模式，即概念模式、內(nèi)模式和外模式，其中 內(nèi)模式 給出了數(shù)據(jù)庫中物理存儲(chǔ)結(jié)構(gòu)與物理存取方法

20. 數(shù)據(jù)管理技術(shù)發(fā)展過程經(jīng)過人工管理、文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)三個(gè)階段，其中數(shù)據(jù)獨(dú)立性的階段是 數(shù)據(jù)庫系統(tǒng)

21. 數(shù)據(jù)獨(dú)立性分為邏輯獨(dú)立性和物理獨(dú)立性，當(dāng)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)改變時(shí)，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應(yīng)用程序不必修改，稱為 物理獨(dú)立性

22. 如果一個(gè)工人可以管理多臺(tái)設(shè)備，而一個(gè)設(shè)備只被一個(gè)工人管理，則實(shí)體工人與實(shí)體設(shè)備之間存在 一對(duì)多的關(guān)系

23. 關(guān)系模型的完整性規(guī)則是對(duì)關(guān)系的某種約束條件，包括實(shí)體完整性、參照完整性和自定義完整性

24. 在關(guān)系數(shù)據(jù)庫中，把數(shù)據(jù)表示成二維表，每一個(gè)二維表稱為 關(guān)系或關(guān)系表

25. 關(guān)系數(shù)據(jù)庫管理系統(tǒng)能實(shí)現(xiàn)的專門關(guān)系運(yùn)算包括 選擇、連接和投影