c++二級公共基礎(chǔ)知識點

1、計算機等級考試二級公共基礎(chǔ)考前背誦版計算機等級考試二級公共基礎(chǔ)考前背誦版下面分為四個部分進行組織。文中標注了三個星號的，表示非常重下面分為四個部分進行組織。文中標注了三個星號的，表示非常重要，基本每次考試都是必考；標注了兩個星號或一個星號的，表示要，基本每次考試都是必考；標注了兩個星號或一個星號的，表示也較重要，很容易考到。出現(xiàn)在也較重要，很容易考到。出現(xiàn)在【】【】括號中的內(nèi)容，表示要很精確括號中的內(nèi)容，表示要很精確的背下來的。整個文檔

2、中的五頁，建議考前都要認真的記憶。的背下來的。整個文檔中的五頁，建議考前都要認真的記憶。第一部分第一部分算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)(歷年比例歷年比例41%)141%)1、算法、算法◆問題處理方問題處理方案的正確而完整的描述稱為案的正確而完整的描述稱為【算法算法】。算法分析的目的是，分析算。算法分析的目的是，分析算法的效率以求改進。算法的基本特征是法的效率以求改進。算法的基本特征是【可行性可行性】、【確定性確定性】、【有窮性有窮性】和擁

3、有足夠情報。和擁有足夠情報?！羲惴ǖ挠懈F性是指：算法程序的運行時間是有限的。算法的有窮性是指：算法程序的運行時間是有限的?！羲惴ǖ膹?fù)雜度是衡量算法好壞的度量，分為算法的復(fù)雜度是衡量算法好壞的度量，分為【時間復(fù)雜度時間復(fù)雜度】和【空間復(fù)雜度空間復(fù)雜度】?！铩铩铩飼r間復(fù)雜度是指執(zhí)行算法所需要的時間復(fù)雜度是指執(zhí)行算法所需要的【計算工作量計算工作量】；算法的空；算法的空間復(fù)雜度是指算法執(zhí)行過程中所需的間復(fù)雜度是指算法執(zhí)行過程中所需的【存儲空間存

4、儲空間】?！羲惴〞r間復(fù)雜度或空間復(fù)雜度中的一項的值，沒有辦法推出另一算法時間復(fù)雜度或空間復(fù)雜度中的一項的值，沒有辦法推出另一項的值。項的值。2、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)◆數(shù)據(jù)結(jié)構(gòu)分為數(shù)據(jù)結(jié)構(gòu)分為【邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)】和【存儲結(jié)構(gòu)存儲結(jié)構(gòu)】。線性。線性結(jié)構(gòu)和非線性結(jié)構(gòu)屬于邏輯結(jié)構(gòu)；順序、鏈式、索引屬于存儲結(jié)構(gòu)結(jié)構(gòu)和非線性結(jié)構(gòu)屬于邏輯結(jié)構(gòu)；順序、鏈式、索引屬于存儲結(jié)構(gòu)(物理結(jié)構(gòu)物理結(jié)構(gòu))。循環(huán)隊列屬于循環(huán)隊列屬于【存儲結(jié)構(gòu)存儲結(jié)構(gòu)】。★數(shù)據(jù)的存儲結(jié)

5、構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存數(shù)據(jù)的存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。儲空間中的存放形式。◆一個邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處一個邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處存儲方式。存儲方式?！铩铩铩镪犃嘘犃惺窃试S在一段插入，在另一端進行刪除的線性表，其特點是允許在一段插入，在另一端進行刪除的線性表，其特點是【先進先出先進先出】?！粞h(huán)隊列中元素的個數(shù)是由

6、隊頭指針和隊尾指針共同決定。循環(huán)循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定。循環(huán)隊列的頭指針為隊列的頭指針為frontfront，尾指針為，尾指針為rearrear，容量為，容量為maxSizemaxSize，則循環(huán)，則循環(huán)隊列中元素的個數(shù)是隊列中元素的個數(shù)是【(rearfrontmaxSize)(rearfrontmaxSize)modmodmaxSize】maxSize】。4、線性鏈表、線性鏈表◆線性鏈表是線性表的鏈式存儲結(jié)

7、構(gòu)。用鏈表表示線線性鏈表是線性表的鏈式存儲結(jié)構(gòu)。用鏈表表示線性表的優(yōu)點是性表的優(yōu)點是【便于插入和刪除操作便于插入和刪除操作】?！艟€性鏈表的存儲空間不一定連續(xù)，且個元素的存儲順序是任意的。線性鏈表的存儲空間不一定連續(xù)，且個元素的存儲順序是任意的。5、樹與二叉樹、樹與二叉樹◆在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件（繼）的個在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件（繼）的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。二叉樹各結(jié)數(shù)稱為該結(jié)點的度，所有結(jié)點

8、中最大的度稱為樹的度。二叉樹各結(jié)點的度只可能取值點的度只可能取值0、1、2，不可能是其它值。換言之，知道了度，不可能是其它值。換言之，知道了度為1結(jié)點數(shù)量的前提下，葉子結(jié)點或度為結(jié)點數(shù)量的前提下，葉子結(jié)點或度為2的結(jié)點中知道其一，就的結(jié)點中知道其一，就可以求出總的結(jié)點數(shù)?？梢郧蟪隹偟慕Y(jié)點數(shù)?！铩铩铩铩铩锵旅骊P(guān)于計算結(jié)點數(shù)量的幾個性質(zhì)，非常重要：下面關(guān)于計算結(jié)點數(shù)量的幾個性質(zhì)，非常重要：(1)(1)對任意的二叉樹，葉子結(jié)點的數(shù)量，比度為對

9、任意的二叉樹，葉子結(jié)點的數(shù)量，比度為2的結(jié)點數(shù)量多一個的結(jié)點數(shù)量多一個(換言之，已知葉子結(jié)點的數(shù)量，減去換言之，已知葉子結(jié)點的數(shù)量，減去1則是度為則是度為2的結(jié)點數(shù)量；已的結(jié)點數(shù)量；已知度為知度為2的結(jié)點數(shù)量，加上的結(jié)點數(shù)量，加上1就是葉子結(jié)點數(shù)量就是葉子結(jié)點數(shù)量)(2)(2)完全二叉樹如果有完全二叉樹如果有N個結(jié)點，當個結(jié)點，當N為奇數(shù)的時候，葉子結(jié)點數(shù)為為奇數(shù)的時候，葉子結(jié)點數(shù)為(N1)2(N1)2，此時二叉樹只有度為，此時二叉樹只