計算機二級公共基礎知識

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

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

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

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

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

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

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