公共基礎(chǔ)知識

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

【考點1】算法的基本概念

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

2、算法的基本特征：

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

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

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

4）擁有足夠的情報。

3、算法的組成要素：一個算法由數(shù)據(jù)對象的運(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è)計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)。

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

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

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

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

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

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

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

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

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

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

【考點4】邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【考點7】線性鏈表

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

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

鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒硎揪�性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。

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

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

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

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

【考點8】棧

1、棧的基本概念

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

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

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

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

鏈?zhǔn)酱鎯Γ河镁�性鏈表來存儲；

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

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

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

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

【考點9】隊列

1.隊列的基本概念

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

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

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

鏈?zhǔn)酱鎯Γ壕�性鏈表。

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

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

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

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

【考點10】樹的基本概念

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

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

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

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

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

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

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

1、二叉樹的概念

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

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

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

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

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

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

【考點12】滿二叉樹與完全二叉樹

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

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

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

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

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

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

【考點14】二叉樹的遍歷

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

前序遍歷圖5可得：ABCDFHEG。

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

中序遍歷圖5可得：BAFHDCGE。

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

后序遍歷圖5可得：BHFDGECA。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲控件中的存放方式稱為數(shù)據(jù)的 存儲結(jié)構(gòu)或者物理結(jié)構(gòu)或者物理存儲結(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)和存儲結(jié)構(gòu)，循環(huán)隊列屬于存儲結(jié)構(gòu)

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

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

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

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

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

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

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

6. 診斷和改正程序中錯誤的工作通常稱為調(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ù)庫物理存儲與物理存取方法的是內(nèi)模式

12. 在數(shù)據(jù)庫的兩極映射中，從概念模式到內(nèi)模式的映射一般由數(shù)據(jù)庫管理系統(tǒng)實現(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)來表示實體之間聯(lián)系的模型稱為 層次模型

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

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

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

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

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

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

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

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

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