二級c語言基礎知識要點

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

2、指：算法程序的運行時間是有限的?！羲惴ǖ膹碗s度是衡量算法好壞的度量，分為【時間復雜度】和【空間復雜度】?！铩飼r間復雜度是指執(zhí)行算法所需要的【計算工作量】；算法的空間復雜度是指算法執(zhí)行過程中所需的【存儲空間】?！羲惴〞r間復雜度或空間復雜度中的一項的值，沒有辦法推出另一項的值。2、數據結構、數據結構◆數據結構分為【邏輯結構邏輯結構】和【存儲結構存儲結構】。線性結構和非線性結構屬于邏輯結構；順序、鏈式、索引屬于存儲結構(物理結構)。循環(huán)隊列屬

3、于【存儲結構】?！飻祿拇鎯Y構數據的存儲結構又稱為物理結構，是數據的邏輯結構在計算機存儲空間中的存放形式數據的邏輯結構在計算機存儲空間中的存放形式。◆一個邏輯結構可以有多種存儲結構，且各種存儲結構影響數據處理的效率。程序執(zhí)行的效率與數據的存儲結構密切相關?！魯祿Y構分為線性結構和非線性結構，帶鏈的隊列屬于【線性結構】?！艟€性表的存儲結構主要分為順序存儲結構和鏈式存儲結構。順序存儲結構的存儲一定是連續(xù)的，鏈式存儲的存儲空間不一定是連續(xù)的

4、?！粲行蚓€性表既可以采用順序存儲結構，也可以采用鏈式存儲結構。◆隊列是一種特殊的線性表，循環(huán)隊列按照【先進先出】原則組織數據。循環(huán)隊列是隊列的【順序】存儲結構?！魯祿莫毩⑿苑譃椤疚锢愍毩ⅰ啃院汀具壿嫪毩⑿浴?。當數據的存儲結構改變時，其邏輯結構可以不變，因此，基于邏輯結構的應用程序可以不用修改，稱為【物理獨立性】。件，必須是完全二叉樹，當然包括滿二叉樹)(3)滿二叉樹第K層上的結點數量為2K1；深度為K的滿二叉樹，結點總數為2K1。上述

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

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

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

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