全國計算機等級考試二級公共基礎知識--復習提綱

1、1.1算法算法算法：是解題方案的準確而完整的描述。通俗地說，算法就是計算機解題的過程。算法不等于程序，也不等于計算方法，程序的編制不可能優(yōu)于算法的設計。(1)確定性，算法中每一步驟都必須有明確定義，不允許有模棱兩可的解釋，不允許有多義性；(2)有窮性，算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止；(3)可行性，算法原則上能夠精確地執(zhí)行；(4)擁有足夠的情報。算法效率的度量—算法復雜度：算法時間復雜度和算法空間復雜度?！铩铩锼?/p>

2、法時間復雜度：指執(zhí)行算法所需要的計算工作量。即算法執(zhí)行過程中所需要的基本運算次數(shù)。算法空間復雜度：指執(zhí)行這個算法所需要的內(nèi)存空間。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)：指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)研究的三個方面：(1)數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；(2)在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；(3)對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。線性結(jié)構(gòu)的條件，(一個非空數(shù)據(jù)

3、結(jié)構(gòu))：(1)有且只有一個根結(jié)點；(2)每一個結(jié)點最多有一個前件，也最多有一個后件。非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。1.3線性表及其順序存儲結(jié)構(gòu)線性表及其順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：(1)線性表中所有元素所占的存儲空間是連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。順序表的運算：查找、插入、刪除。1.4線性鏈表線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應于一個存儲單元，這種存儲單元稱為存儲

4、結(jié)點，簡稱結(jié)點。結(jié)點由兩部分組成：(1)用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；(2)用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。在鏈式存儲結(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。鏈式存儲方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。線性鏈表的基本運算：查找、插入、刪除。樹是一種簡單的非線性結(jié)構(gòu)，其所有元素之間具有明顯的層次特性。

5、在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點。沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度。來源：考試大所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。2、二叉樹及其基本性質(zhì)滿足下列兩個特點的樹即為二叉樹(1)非空二叉樹只有一個根結(jié)點；(2)每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右