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

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

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

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

5、構又稱為物理結構，是數(shù)據(jù)的邏輯結構在計算機存數(shù)據(jù)的存儲結構又稱為物理結構，是數(shù)據(jù)的邏輯結構在計算機存儲空間中的存放形式。儲空間中的存放形式?！粢粋€邏輯結構可以有多種存儲結構，且各種存儲結構影響數(shù)據(jù)處一個邏輯結構可以有多種存儲結構，且各種存儲結構影響數(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、線性鏈表、線性鏈表◆線性鏈表是線性表的鏈式存儲結

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

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

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