二級(jí)c語言基礎(chǔ)知識(shí)要點(diǎn)

1、下面分為四個(gè)部分進(jìn)行組織。文中標(biāo)注了三個(gè)星號(hào)的，表示非常重要，基本每次考試都是必考；標(biāo)注了兩個(gè)星號(hào)或一個(gè)星號(hào)的，表示也較重要，很容易考到。出現(xiàn)在【】括號(hào)中的內(nèi)容，表示要很精確的背下來的。第一部分第一部分算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)(歷年比例歷年比例41%)1、算法、算法◆問題處理方案的正確而完整的描述稱為【算法】。算法分析的目的是，分析算法的效率以求改進(jìn)。算法的基本特征是【可行性】、【確定性】、【有窮性】和擁有足夠情報(bào)。◆算法的有窮性是

2、指：算法程序的運(yùn)行時(shí)間是有限的?！羲惴ǖ膹?fù)雜度是衡量算法好壞的度量，分為【時(shí)間復(fù)雜度】和【空間復(fù)雜度】。★★時(shí)間復(fù)雜度是指執(zhí)行算法所需要的【計(jì)算工作量】；算法的空間復(fù)雜度是指算法執(zhí)行過程中所需的【存儲(chǔ)空間】。◆算法時(shí)間復(fù)雜度或空間復(fù)雜度中的一項(xiàng)的值，沒有辦法推出另一項(xiàng)的值。2、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)◆數(shù)據(jù)結(jié)構(gòu)分為【邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)】和【存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)】。線性結(jié)構(gòu)和非線性結(jié)構(gòu)屬于邏輯結(jié)構(gòu)；順序、鏈?zhǔn)健⑺饕龑儆诖鎯?chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))。循環(huán)隊(duì)列屬

3、于【存儲(chǔ)結(jié)構(gòu)】?！飻?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。◆一個(gè)邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率。程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)?！魯?shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于【線性結(jié)構(gòu)】?！艟€性表的存儲(chǔ)結(jié)構(gòu)主要分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)空間不一定是連續(xù)的

4、?！粲行蚓€性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?！絷?duì)列是一種特殊的線性表，循環(huán)隊(duì)列按照【先進(jìn)先出】原則組織數(shù)據(jù)。循環(huán)隊(duì)列是隊(duì)列的【順序】存儲(chǔ)結(jié)構(gòu)。◆數(shù)據(jù)的獨(dú)立性分為【物理獨(dú)立】性和【邏輯獨(dú)立性】。當(dāng)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)改變時(shí)，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應(yīng)用程序可以不用修改，稱為【物理獨(dú)立性】。件，必須是完全二叉樹，當(dāng)然包括滿二叉樹)(3)滿二叉樹第K層上的結(jié)點(diǎn)數(shù)量為2K1；深度為K的滿二叉樹，結(jié)點(diǎn)總數(shù)為2K1。上述

5、的計(jì)算公式，關(guān)鍵要能夠應(yīng)用，例如，深度為上述的計(jì)算公式，關(guān)鍵要能夠應(yīng)用，例如，深度為7的滿二叉樹，度為的滿二叉樹，度為2的結(jié)點(diǎn)數(shù)量是多的結(jié)點(diǎn)數(shù)量是多少？既然是滿二叉樹，葉子結(jié)點(diǎn)的數(shù)量就是第少？既然是滿二叉樹，葉子結(jié)點(diǎn)的數(shù)量就是第7層的結(jié)點(diǎn)數(shù)量，也就是層的結(jié)點(diǎn)數(shù)量，也就是26，可以算出葉子，可以算出葉子結(jié)點(diǎn)為結(jié)點(diǎn)為64，因此度為，因此度為2的結(jié)點(diǎn)數(shù)是的結(jié)點(diǎn)數(shù)是63(葉子結(jié)點(diǎn)數(shù)減去葉子結(jié)點(diǎn)數(shù)減去1)?！铩铩锒鏄涞那靶虮闅v、中序遍歷、后續(xù)遍

6、歷：前中后三個(gè)詞是相對(duì)于根來講的，前序是【根左右】，中序是【左根右】，后續(xù)是【左右根】。具體操作為：先序遍歷(DLR):訪問根結(jié)點(diǎn)，按先序遍歷左子樹，按先序遍歷右子樹。中序遍歷(LDR):按中序遍歷左子樹，訪問根結(jié)點(diǎn)，按中序遍歷右子樹。后序遍歷(LRD):按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點(diǎn)。下面以中序遍歷為例，來講解實(shí)際的解題方法：對(duì)一棵樹，將根結(jié)點(diǎn)下的左子樹用一個(gè)橢圓圈起來，右子樹也用一個(gè)橢圓圈起來。之后，在左子樹上標(biāo)記上

7、1，在根結(jié)點(diǎn)標(biāo)記上2，在右子樹上標(biāo)記上3。對(duì)在左邊橢圓內(nèi)的左子樹，現(xiàn)在把它單獨(dú)拿出來分析。把它的左子樹圈起來標(biāo)上1.1，根結(jié)點(diǎn)標(biāo)記上1.2，右子樹標(biāo)上1.3。按照上述方法依次往下，直到樹不能拆分，然后按照“左根右”的順序?qū)懗鼋Y(jié)點(diǎn)的訪問先后即可。6、查找技術(shù)、查找技術(shù)◆對(duì)于長度為n的線性表，順序查找順序查找最壞情況下需要比較比較n次。(對(duì)數(shù)據(jù)是否有序沒有要求)?！繇樞虿檎易詈们闆r下查詢次數(shù)是1，最壞情況下是n，平均為(1n)2?！铩飳?duì)于長

8、度為n的有序線性表有序線性表，二分法二分法最壞情況下只需要比較log2n次。(數(shù)據(jù)必須有序)◆能用二分法進(jìn)行查找的是【順序存儲(chǔ)的有序線性表】。7、排序技術(shù)、排序技術(shù)★★對(duì)于長度為n的線性表，【冒泡排序、快速排序、簡單插入排序、簡單選擇排序冒泡排序、快速排序、簡單插入排序、簡單選擇排序】這四種排序方式在最壞情況下的比較次數(shù)相同，都是【n(n1)2】。堆排序堆排序的效率最高，是【nlog2n】?！铩锵柵判蜃顗那闆r下需要次比較【n1.5】。