全國計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)--復(fù)習(xí)提綱

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

2、法時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量。即算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)。算法空間復(fù)雜度：指執(zhí)行這個(gè)算法所需要的內(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)研究的三個(gè)方面：(1)數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；(2)在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。線性結(jié)構(gòu)的條件，(一個(gè)非空數(shù)據(jù)

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

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

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