c++二級(jí)公共基礎(chǔ)知識(shí)點(diǎn)

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

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

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

4、儲(chǔ)空間】。◆算法時(shí)間復(fù)雜度或空間復(fù)雜度中的一項(xiàng)的值，沒(méi)有辦法推出另一算法時(shí)間復(fù)雜度或空間復(fù)雜度中的一項(xiàng)的值，沒(méi)有辦法推出另一項(xiàng)的值。項(xiàng)的值。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)】和【存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)】。線(xiàn)性。線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)屬于邏輯結(jié)構(gòu)；順序、鏈?zhǔn)?、索引屬于存?chǔ)結(jié)構(gòu)結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)屬于邏輯結(jié)構(gòu)；順序、鏈?zhǔn)?、索引屬于存?chǔ)結(jié)構(gòu)(物理結(jié)構(gòu)物理結(jié)構(gòu))。循環(huán)隊(duì)列屬于循環(huán)隊(duì)列屬于【存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)】。★數(shù)據(jù)的存儲(chǔ)結(jié)

5、構(gòu)又稱(chēng)為物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱(chēng)為物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。儲(chǔ)空間中的存放形式?！粢粋€(gè)邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處一個(gè)邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處存儲(chǔ)方式。存儲(chǔ)方式?！铩铩铩镪?duì)列隊(duì)列是允許在一段插入，在另一端進(jìn)行刪除的線(xiàn)性表，其特點(diǎn)是允許在一段插入，在另一端進(jìn)行刪除的線(xiàn)性表，其特點(diǎn)是【先進(jìn)先出先進(jìn)先出】。◆循環(huán)隊(duì)列中元素的個(gè)數(shù)是由

6、隊(duì)頭指針和隊(duì)尾指針共同決定。循環(huán)循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定。循環(huán)隊(duì)列的頭指針為隊(duì)列的頭指針為frontfront，尾指針為，尾指針為rearrear，容量為，容量為maxSizemaxSize，則循環(huán)，則循環(huán)隊(duì)列中元素的個(gè)數(shù)是隊(duì)列中元素的個(gè)數(shù)是【(rearfrontmaxSize)(rearfrontmaxSize)modmodmaxSize】maxSize】。4、線(xiàn)性鏈表、線(xiàn)性鏈表◆線(xiàn)性鏈表是線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)

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

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

9、任意的二叉樹(shù)，葉子結(jié)點(diǎn)的數(shù)量，比度為2的結(jié)點(diǎn)數(shù)量多一個(gè)的結(jié)點(diǎn)數(shù)量多一個(gè)(換言之，已知葉子結(jié)點(diǎn)的數(shù)量，減去換言之，已知葉子結(jié)點(diǎn)的數(shù)量，減去1則是度為則是度為2的結(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ù)量)(2)(2)完全二叉樹(shù)如果有完全二叉樹(shù)如果有N個(gè)結(jié)點(diǎn)，當(dāng)個(gè)結(jié)點(diǎn)，當(dāng)N為奇數(shù)的時(shí)候，葉子結(jié)點(diǎn)數(shù)為為奇數(shù)的時(shí)候，葉子結(jié)點(diǎn)數(shù)為(N1)2(N1)2，此時(shí)二叉樹(shù)只有度為，此時(shí)二叉樹(shù)只