計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)

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

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

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

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

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

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

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