二級(jí)公共基礎(chǔ)知識(shí)考點(diǎn)總結(jié)

本文格式為Word版，下載可任意編輯——二級(jí)公共基礎(chǔ)知識(shí)考點(diǎn)總結(jié)二級(jí)公共基礎(chǔ)知識(shí)考點(diǎn)總結(jié)

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

考點(diǎn)1：算法的概念和基本特征

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

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

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

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

（4）擁有足夠的情報(bào)：擁有足夠的輸入。

考點(diǎn)2：算法繁雜度

算法的繁雜度主要包括時(shí)間繁雜度和空間繁雜度

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

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

特別注意：時(shí)間繁雜度與空間繁雜度沒有必然的正比或反比的關(guān)系。

考點(diǎn)3：數(shù)據(jù)的規(guī)律結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的規(guī)律結(jié)構(gòu)是反映數(shù)據(jù)元素之間規(guī)律關(guān)系的數(shù)據(jù)結(jié)構(gòu)，與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無關(guān)。

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

考點(diǎn)4：線性表的順序存儲(chǔ)結(jié)構(gòu)

線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：1)線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的

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

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

1

考點(diǎn)5：棧與隊(duì)列(屬于線性結(jié)構(gòu))1、棧

棧是限定在一端進(jìn)行插入與刪除的線性表。

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

top-bottom的絕對(duì)值加1即為當(dāng)前棧中元素的個(gè)數(shù)。

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

2、隊(duì)列

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

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

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

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

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

棧與隊(duì)列的共同點(diǎn)：皆為線性結(jié)構(gòu)，只允許在端點(diǎn)處插入與刪除，而且不須移動(dòng)其他元素。

2

考點(diǎn)6：線性鏈表

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的規(guī)律關(guān)系可以不一致。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)，棧與隊(duì)列也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

★考點(diǎn)7：二叉樹的基本性質(zhì)

樹是典型的非線性結(jié)構(gòu)，在樹中，每個(gè)結(jié)點(diǎn)的前件稱為父結(jié)點(diǎn)，沒有父結(jié)點(diǎn)的只有一個(gè)，稱為根結(jié)點(diǎn)（有且僅有一個(gè)）。

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

二叉樹：每個(gè)結(jié)點(diǎn)最大的度為2，如下圖所示

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

m

k-1

個(gè)結(jié)點(diǎn)

-1個(gè)結(jié)點(diǎn)

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

3

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

m

2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿

-1個(gè)結(jié)點(diǎn)

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

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

考點(diǎn)9：查找技術(shù)

對(duì)于長(zhǎng)度為n的線性表：

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

二分法查找只適用于順序存儲(chǔ)的有序表，在最壞狀況下只需要對(duì)比log2n次。考點(diǎn)10：排序技術(shù)

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

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

4

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

其次章程序設(shè)計(jì)基礎(chǔ)

考點(diǎn)1：程序設(shè)計(jì)風(fēng)格

主要風(fēng)格：清楚第一，效率其次

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

考點(diǎn)2：結(jié)構(gòu)化程序設(shè)計(jì)的原則1.自頂向下2.逐步求精3.模塊化

4.限制使用goto語句

結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)包括順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)?？键c(diǎn)3：面向?qū)ο蟮幕靖拍?/p>

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

3、類與對(duì)象的關(guān)系：類是對(duì)象的抽象，對(duì)象則是其對(duì)應(yīng)類的一個(gè)實(shí)例

第三章軟件工程基礎(chǔ)

考點(diǎn)1：軟件的定義及特點(diǎn)

計(jì)算機(jī)軟件是包括程序