二級(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í)際問(wèn)題設(shè)計(jì)的算法，總是在某個(gè)特定計(jì)算工具上執(zhí)行，往往要受到計(jì)算工具的限制，使執(zhí)行結(jié)果產(chǎn)生偏差。

（2）確定性：算法中每一步驟都必需有明確定義，不充許有模棱兩可的解釋?zhuān)辉试S有多義性。

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

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

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

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

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

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

特別注意：時(shí)間繁雜度與空間繁雜度沒(méi)有必然的正比或反比的關(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ǔ)位置無(wú)關(guān)。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱(chēng)物理結(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)有順序、鏈接、索引等（包括線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)）。而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。

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

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

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

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

1

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

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

在棧中，允許插入與刪除的一端稱(chēng)為棧頂，不允許插入與刪除的另一端稱(chēng)為棧底。尋常用指針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)行刪除的線(xiàn)性表。允許插入的一端稱(chēng)為隊(duì)尾，尋常用一個(gè)尾指針rear指向隊(duì)尾元素，允許刪除的一端稱(chēng)為排頭（也稱(chēng)隊(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)狀空間，但物理上依舊是線(xià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)：皆為線(xiàn)性結(jié)構(gòu)，只允許在端點(diǎn)處插入與刪除，而且不須移動(dòng)其他元素。

2

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

線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線(xiàn)性鏈表在鏈?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)即可用于表示線(xiàn)性結(jié)構(gòu)，也可用于表示非線(xiàn)性結(jié)構(gòu)，棧與隊(duì)列也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

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

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

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

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

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

m

k-1

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

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

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

3

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

m

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

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

完全二叉樹(shù)：除最終一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最終一層上只缺少右邊的若干結(jié)點(diǎn)。當(dāng)完全二叉樹(shù)有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：二叉樹(shù)的遍歷（1）前序遍歷（DLR），首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最終遍歷右子樹(shù)；（2）中序遍歷（LDR），首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最終遍歷右子樹(shù)；（3）后序遍歷（LRD）首先遍歷左子樹(shù)，然后訪問(wèn)遍歷右子樹(shù)，最終訪問(wèn)根結(jié)點(diǎn)。

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

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

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

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

在最壞狀況下，對(duì)于長(zhǎng)度為n的線(xià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ù)交換類(lèi)排序冒泡排序法n(n-1)/2快速排序法插入類(lèi)排序簡(jiǎn)單插入排序法希爾排序法O(n1.5)選擇類(lèi)排序簡(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ù)說(shuō)明的方法：數(shù)據(jù)說(shuō)明的次序規(guī)范化3.語(yǔ)句的結(jié)構(gòu)4.輸入與輸出

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

4.限制使用goto語(yǔ)句

結(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í)唯一性、分類(lèi)性、多態(tài)性、封裝性（實(shí)現(xiàn)信息隱蔽）、模塊獨(dú)立性2、類(lèi)是具有共同屬性、共同方法的對(duì)象的集合，類(lèi)具有繼承性

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

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

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

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