二級公共基礎知識考點總結

本文格式為Word版，下載可任意編輯——二級公共基礎知識考點總結二級公共基礎知識考點總結

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

考點1：算法的概念和基本特征

算法是指解題方案的確鑿而完整的描述。算法的基本特征包括：

（1）可行性：針對實際問題設計的算法，總是在某個特定計算工具上執(zhí)行，往往要受到計算工具的限制，使執(zhí)行結果產生偏差。

（2）確定性：算法中每一步驟都必需有明確定義，不充許有模棱兩可的解釋，不允許有多義性。

（3）有窮性：算法必需能在有限的時間內做完，即能在執(zhí)行有限個步驟后終止，包括合理的執(zhí)行時間的含義。

（4）擁有足夠的情報：擁有足夠的輸入。

考點2：算法繁雜度

算法的繁雜度主要包括時間繁雜度和空間繁雜度

算法的時間繁雜度是指執(zhí)行算法所需要的計算工作量(即算法執(zhí)行過程中所需基本運算的執(zhí)行次數(shù))。

算法的空間繁雜度是指執(zhí)行這個算法所需要的內存空間。

特別注意：時間繁雜度與空間繁雜度沒有必然的正比或反比的關系。

考點3：數(shù)據(jù)的規(guī)律結構與存儲結構

數(shù)據(jù)的規(guī)律結構是反映數(shù)據(jù)元素之間規(guī)律關系的數(shù)據(jù)結構，與它們在計算機中的存儲位置無關。

數(shù)據(jù)的存儲結構（也稱物理結構）是指數(shù)據(jù)的規(guī)律結構在計算機存儲空間中的存放形式。一種數(shù)據(jù)的規(guī)律結構根據(jù)需要可以表示成多種存儲結構，常用的存儲結構有順序、鏈接、索引等（包括線性結構和非線性結構）。而采用不同的存儲結構，其數(shù)據(jù)處理的效率是不同的。

考點4：線性表的順序存儲結構

線性表的順序存儲結構具有以下兩個基本特點：1)線性表中所有元素所占的存儲空間是連續(xù)的

2)線性表中各數(shù)據(jù)元素在存儲空間中是按規(guī)律順序依次存放的

在程序設計語言中，尋常定義一個一維數(shù)組來表示線性表的順序存儲空間

1

考點5：棧與隊列(屬于線性結構)1、棧

棧是限定在一端進行插入與刪除的線性表。

在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。尋常用指針top指示棧頂?shù)奈恢?，用指針bottom指向棧底。

top-bottom的絕對值加1即為當前棧中元素的個數(shù)。

棧是依照“先進后出〞或“后進先出〞的原則組織數(shù)據(jù)的，用棧頂指針top動態(tài)反映了棧中元素的變化狀況，而不須改變指針bottom的位置。棧具有記憶作用。

2、隊列

隊列是指允許在一端進行插入、而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，尋常用一個尾指針rear指向隊尾元素，允許刪除的一端稱為排頭（也稱隊頭），尋常用一個排頭指針front指向排頭元素的前一個位置。

隊列依照“先進先出〞或“后進后出〞的原則組織數(shù)據(jù)，隊尾指針rear和排頭指針front共同反映了隊列中元素動態(tài)變化狀況。在實際應用中，隊列的順序存儲結構一般采用循環(huán)隊列的形式，循環(huán)隊列是規(guī)律上的環(huán)狀空間，但物理上依舊是線性結構。從排頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素。

在普通隊列中，rear指針位置減去front指針位置的差值即為隊列中元素的個數(shù)。但在循環(huán)隊列中，rear指針的位置可能大于front指針的位置，也可能小于front指針的位置，所以循環(huán)隊列的元素個數(shù)計算方法如下：設循環(huán)隊列總容量為m

假使rear>front，則循環(huán)隊列的元素個數(shù)為rear-front

假使rear<front，則循環(huán)隊列的元素個數(shù)為m+(rear-front)

棧與隊列的共同點：皆為線性結構，只允許在端點處插入與刪除，而且不須移動其他元素。

2

考點6：線性鏈表

線性表的鏈式存儲結構稱為線性鏈表在鏈式存儲結構中，存儲數(shù)據(jù)結構的存儲空間可以不連續(xù)，各數(shù)據(jù)結點的存儲順序與數(shù)據(jù)元素之間的規(guī)律關系可以不一致。

鏈式存儲結構即可用于表示線性結構，也可用于表示非線性結構，棧與隊列也可以采用鏈式存儲結構。

★考點7：二叉樹的基本性質

樹是典型的非線性結構，在樹中，每個結點的前件稱為父結點，沒有父結點的只有一個，稱為根結點（有且僅有一個）。

每個結點擁有的后件稱為子結點，沒有子結點的稱為葉子結點。一個結點所擁有的子結點的個數(shù)稱為該結點的度，葉子結點的度為0。樹的最大層次稱為樹的深度。

二叉樹：每個結點最大的度為2，如下圖所示

性質1：在二叉樹的第k層上，最多有2性質2：深度為m的二叉樹最多有2

m

k-1

個結點

-1個結點

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

3

滿二叉樹：每一層上的結點數(shù)都達到最大值，即第k層上有二叉樹有2

m

2k-1個結點，且深度為m的滿

-1個結點

完全二叉樹：除最終一層外，每一層上的結點數(shù)均達到最大值；在最終一層上只缺少右邊的若干結點。當完全二叉樹有n個結點，若n為偶數(shù)，則有n/2個葉子結點；若n為奇數(shù)，則有[n/2]+1個葉子結點（[]表示只取整數(shù)部分）。

★考點8：二叉樹的遍歷（1）前序遍歷（DLR），首先訪問根結點，然后遍歷左子樹，最終遍歷右子樹；（2）中序遍歷（LDR），首先遍歷左子樹，然后訪問根結點，最終遍歷右子樹；（3）后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最終訪問根結點。

考點9：查找技術

對于長度為n的線性表：

順序查找在最壞狀況下，需要對比n次。

二分法查找只適用于順序存儲的有序表，在最壞狀況下只需要對比log2n次?？键c10：排序技術

在最壞狀況下，對于長度為n的線性表，冒泡排序法、快速排序法、簡單插入排序法、簡單項選擇擇排序法都需要對比n(n-1)/2次；希爾排序法需要對比O(n1.5)次；堆排序法需要對比O(nlog2n)次。

在各種排序法中，冒泡排序法最簡單，對比次數(shù)最少（尋常少于n(n-1)/2次）。

4

查找技術順序查找n最壞狀況下的次數(shù)（時間繁雜度）log2n二分法查找排序技術交換類排序冒泡排序法n(n-1)/2快速排序法插入類排序簡單插入排序法希爾排序法O(n1.5)選擇類排序簡單項選擇擇排序法堆排序法O(nlog2n)

其次章程序設計基礎

考點1：程序設計風格

主要風格：清楚第一，效率其次

形成良好的程序設計風格應重視的因素：1.源程序的文檔化：要包含必要的程序解釋2.數(shù)據(jù)說明的方法：數(shù)據(jù)說明的次序規(guī)范化3.語句的結構4.輸入與輸出

考點2：結構化程序設計的原則1.自頂向下2.逐步求精3.模塊化

4.限制使用goto語句

結構化程序設計的基本結構包括順序結構、選擇結構和循環(huán)結構?？键c3：面向對象的基本概念

1、對象的特點：標識唯一性、分類性、多態(tài)性、封裝性（實現(xiàn)信息隱蔽）、模塊獨立性2、類是具有共同屬性、共同方法的對象的集合，類具有繼承性

3、類與對象的關系：類是對象的抽象，對象則是其對應類的一個實例

第三章軟件工程基礎

考點1：軟件的定義及特點

計算機軟件是包括程序