公共基礎知識

第一章 數(shù)據結構與算法

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

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

2、算法的基本特征：

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

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

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

4）擁有足夠的情報。

3、算法的組成要素：一個算法由數(shù)據對象的運算和操作以及其控制結構這兩部分組成。

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

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

6、算法基本設計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術。

【考點2】算法的復雜度

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

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

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

空間復雜度和時間復雜度并不相關。

【考點3】數(shù)據結構的基本概念

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

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

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

數(shù)據結構：是指由某一數(shù)據對象中所有數(shù)據成員之間的關系組成的集合。

【考點4】邏輯結構和存儲結構

1、數(shù)據結構可分為數(shù)據的邏輯結構和存儲結構。

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

2）數(shù)據的存儲結構也稱為數(shù)據的物理結構，是數(shù)據在計算機中的存放的方式，是面向計算機的，它包括數(shù)據元素的存儲方式和關系的存儲方式。

2、存儲結構和邏輯結構的關系：一種數(shù)據的邏輯結構可以表示成多種存儲結構即數(shù)據的邏輯結構和存儲結構不一定一一對應。

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

【考點5】線性結構和非線性結構

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

2、非線性結構：不滿足線性結構條件的數(shù)據結構。

棧、隊列、雙向鏈表是線性結構，樹、二叉樹為非線性結構。

【考點6】線性表及其順序存儲結構

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

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

3、非空線性表的結構特征：

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

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

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

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

4、線性表的順序存儲結構具有以下兩個基本特點：

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

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

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

5、順序表的運算：查找、插入、刪除。

【考點7】線性鏈表

線性鏈表是線性表的鏈式存儲結構，數(shù)據結構中的每一個結點對應于一個存儲單元，這種存儲單元稱為存儲結點，簡稱結點。結點由兩部分組成：(1) 用于存儲數(shù)據元素值，稱為數(shù)據域；(2) 用于存放指針，稱為指針域，用于指向前一個或后一個結點。

在鏈式存儲結構中，存儲數(shù)據結構的存儲空間可以不連續(xù)，各數(shù)據結點的存儲順序與數(shù)據元素之間的邏輯關系可以不一致，而數(shù)據元素之間的邏輯關系是由指針域來確定的。

鏈式存儲方式既可用于表示線性結構，也可用于表示非線性結構。

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

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

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

線性鏈表的基本運算：查找、插入、刪除。

【考點8】棧

1、棧的基本概念

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

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

2、棧的存儲結構

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

鏈式存儲：用線性鏈表來存儲；

3、棧的基本運算

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

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

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

【考點9】隊列

1.隊列的基本概念

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

2、隊列的存儲結構

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

鏈式存儲：線性鏈表。

3、隊列的運算:

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

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

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

【考點10】樹的基本概念

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

葉子結點：度為0的結點。

分支結點：除葉子結點以外的結點。

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

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

樹的度：樹中所有結點的度的最大值。

【考點11】二叉樹及其基本性質

1、二叉樹的概念

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

2、二叉樹的性質

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

性質2 深度為m的二叉樹最多有2m-1個結點。

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

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

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

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

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

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

【考點13】完全二叉樹的性質

性質1 具有n個結點的完全二叉樹的深度為[log2n]+1。

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

【考點14】二叉樹的遍歷

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

前序遍歷圖5可得：ABCDFHEG。

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

中序遍歷圖5可得：BAFHDCGE。

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

后序遍歷圖5可得：BHFDGECA。

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

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

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

4. 數(shù)據的存儲結構是指： 數(shù)據的邏輯結構在計算機中的表示

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

6. 線性鏈表是線性表的鏈式存儲結構

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

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

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

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

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

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

13. 算法的復雜度包括時間復雜度和空間復雜度

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

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

16. 數(shù)據的邏輯結構在計算機存儲控件中的存放方式稱為數(shù)據的 存儲結構或者物理結構或者物理存儲結構

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

18. 數(shù)據結構分為邏輯結構和存儲結構，循環(huán)隊列屬于存儲結構

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

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

1. 在結構化方法中，軟件功能分解屬于 總體設計階段

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

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

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

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

6. 診斷和改正程序中錯誤的工作通常稱為調試

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21. 數(shù)據獨立性分為邏輯獨立性和物理獨立性，當數(shù)據的存儲結構改變時，其邏輯結構可以不變，因此，基于邏輯結構的應用程序不必修改，稱為 物理獨立性

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

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

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

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