計算機二級公共基礎知識

1、第1頁第一章第一章數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法1.算法算法算法:是指解題方案的準確而完整的描述。算法不等于程序，也不等于計算方法，程序的編制不可能優(yōu)于算法的設計。算法的基本特征:是一組嚴謹?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括:(1)可行性；(2)確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；(3)有窮性，算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個

2、步驟后終止，包括合理的執(zhí)行時間的含義；(4)擁有足夠的情報。算法的基本要素:一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構。算法的三種基本控制結(jié)構:順序結(jié)構、選擇結(jié)構、循環(huán)結(jié)構。算法復雜度包括:算法時間復雜度和算法空間復雜度。算法時間復雜度是指執(zhí)行算法所需要的計算工作量。算法空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。案例案例0.算法的有窮性是指(D)A.算法只能被有限的用戶使用B.算法程序的長度是有限的C.算法程序所處理的數(shù)據(jù)量是有限

3、的D.算法程序的運行時間是有限的算法程序的運行時間是有限的案例案例1.下列敘述中正確的是(BG)A.一個算法的時間復雜度大，則其空間復雜度必定小B.算法的時間復雜度與空間復雜度沒有直接關系算法的時間復雜度與空間復雜度沒有直接關系C.一個算法的空間復雜度大，則其時間復雜度也必定大D.算法的時間復雜度與空間復雜度一定相關E.算法的效率只與問題的規(guī)模有關，而與數(shù)據(jù)的存儲結(jié)構無關F.數(shù)據(jù)的邏輯結(jié)構與存儲結(jié)構是一一對應的G.算法的時間復雜度是指執(zhí)

4、行算法所需要的計算工作量算法的時間復雜度是指執(zhí)行算法所需要的計算工作量2.棧及其基本運算棧及其基本運算棧是限定在一端進行插入與刪除運算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。第3頁1.如果大于如果大于0，rearfront即為元素的個數(shù)。即為元素的個數(shù)。2.如果小于如果小于0，rea

5、rfront空間容量空間容量即為元素個數(shù)。即為元素個數(shù)。3.如果等于如果等于0，元素個數(shù)為，元素個數(shù)為0或空間容量?；蚩臻g容量。5.二叉樹及其基本性質(zhì)二叉樹及其基本性質(zhì)二叉樹是一種非線性結(jié)構，它具有以下兩個特點:1)非空二叉樹只有一個根結(jié)點2)每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。根據(jù)二叉樹的概念可知，二叉樹的度可以為0(葉結(jié)點)、1(只有一棵子樹)或2(有2棵子樹)。二叉樹考點1:在任意一棵二叉樹中，度數(shù)為0的結(jié)

6、點(即葉子結(jié)點)總比度為2的結(jié)點多一個。葉子數(shù)(度為0)=度為2結(jié)點數(shù)1二叉樹考點2:二叉樹的深度即二叉樹的層次數(shù)二叉樹考點3:總結(jié)點數(shù)=度為2的結(jié)點數(shù)度為1的結(jié)點數(shù)度為0的結(jié)點數(shù)(葉子)案例案例6.某二叉樹共有7個結(jié)點，其中葉子結(jié)點只有1個，則該二叉樹的深度為(假設根結(jié)點在第1層)_____。(7)案例案例7.一棵二叉樹共有25個結(jié)點，其中5個是葉子結(jié)點，則度為1的結(jié)點數(shù)為____。(16)_解析解析:葉子結(jié)點數(shù)葉子結(jié)點數(shù)=度為度為2

7、的結(jié)點數(shù)的結(jié)點數(shù)15=？1求得度為求得度為2的結(jié)點數(shù)為的結(jié)點數(shù)為4總結(jié)點數(shù)總結(jié)點數(shù)=度為度為2的結(jié)點數(shù)的結(jié)點數(shù)度為度為1的結(jié)點數(shù)的結(jié)點數(shù)度為度為0的結(jié)點數(shù)的結(jié)點數(shù)(葉子)25=4？5求得度為求得度為1的結(jié)點數(shù)為的結(jié)點數(shù)為16二叉樹考點4:二叉樹的遍歷二叉樹的遍歷是指不重復地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷可以分為以下三種:(1)前序遍歷:若二叉樹為空，則結(jié)束返回。否則:首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。(2)中序遍歷: