查看匯總：2014年計(jì)算機(jī)二級mysql數(shù)據(jù)庫重點(diǎn)匯總

　　下面分為四個(gè)部分進(jìn)行組織。文中標(biāo)注了三個(gè)星號的，表示非常重要，基本每次考試都是必考;標(biāo)注了兩個(gè)星號或一個(gè)星號的，表示也較重要，很容易考到。出現(xiàn)在【】括號中的內(nèi)容，表示要很精確的背下來的。

　　第一部分 算法與數(shù)據(jù)結(jié)構(gòu) (歷年比例41%)

　　1、算法

　　◆ 問題處理方案的正確而完整的描述稱為【算法】。算法分析的目的是，分析算法的效率以求改進(jìn)。算法的基本特征是【可行性】、【確定性】、【有窮性】和擁有足夠情報(bào)。

　　◆ 算法的有窮性是指：算法程序的運(yùn)行時(shí)間是有限的。

　　◆ 算法的復(fù)雜度是衡量算法好壞的度量，分為【時(shí)間復(fù)雜度】和【空間復(fù)雜度】。

　　★★ 時(shí)間復(fù)雜度是指執(zhí)行算法所需要的【計(jì)算工作量】;算法的空間復(fù)雜度是指算法執(zhí)行過程中所需的【存儲空間】。

　　◆ 算法時(shí)間復(fù)雜度或空間復(fù)雜度中的一項(xiàng)的值，沒有辦法推出另一項(xiàng)的值。

　　2、數(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);順序、鏈?zhǔn)健⑺饕龑儆诖鎯�結(jié)構(gòu)(物理結(jié)構(gòu))。循環(huán)隊(duì)列屬于【存儲結(jié)構(gòu)】。

　　★ 數(shù)據(jù)的存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的存放形式。

　　◆ 一個(gè)邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率。程序執(zhí)行的效率與數(shù)據(jù)的存儲結(jié)構(gòu)密切相關(guān)。

　　◆ 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于【線性結(jié)構(gòu)】。

　　◆ 線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯�結(jié)構(gòu)。順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Φ拇鎯�空間不一定是連續(xù)的。

　　◆ 有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯�結(jié)構(gòu)。

　　◆ 隊(duì)列是一種特殊的線性表，循環(huán)隊(duì)列按照【先進(jìn)先出】原則組織數(shù)據(jù)。循環(huán)隊(duì)列是隊(duì)列的【順序】存儲結(jié)構(gòu)。

　　◆ 數(shù)據(jù)的獨(dú)立性分為【物理獨(dú)立】性和【邏輯獨(dú)立性】。當(dāng)數(shù)據(jù)的存儲結(jié)構(gòu)改變時(shí)，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應(yīng)用程序可以不用修改，稱為【物理獨(dú)立性】。

　　3、棧和隊(duì)列

　　★★ 棧是一種特殊的線性表，是只能在一端進(jìn)行插入和刪除的線性表，特點(diǎn)是FILO(First In Last Out)。

　　★★ 棧是【先進(jìn)后出】的線性表;棧具有記憶作用;對棧的插入與刪除操作中，不需要改變【棧底指針】。假定讓元素1、2、3、A、B依次入棧，則出棧的順序是：B、A、3、2、1。

　　◆ 棧與隊(duì)列都是線性結(jié)構(gòu)，樹是非線性結(jié)構(gòu)。支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是【�！�。

　　◆ 棧與隊(duì)列的共同點(diǎn)是，都只允許在【端點(diǎn)處】插入和刪除元素。

　　◆ 棧只能順序存儲的描述是錯(cuò)誤的。�？梢杂小卷樞蚝玩�?zhǔn)健績煞N存儲方式。

　　★★ 隊(duì)列是允許在一段插入，在另一端進(jìn)行刪除的線性表，其特點(diǎn)是【先進(jìn)先出】。

　　◆ 循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定。循環(huán)隊(duì)列的頭指針為front，尾指針為rear，容量為maxSize，則循環(huán)隊(duì)列中元素的個(gè)數(shù)是【 (rear-front+maxSize) mod maxSize】。

　　4、線性鏈表

　　◆ 線性鏈表是線性表的鏈?zhǔn)酱鎯�結(jié)構(gòu)。用鏈表表示線性表的優(yōu)點(diǎn)是【便于插入和刪除操作】。

　　◆ 線性鏈表的存儲空間不一定連續(xù)，且個(gè)元素的存儲順序是任意的。

　　5、樹與二叉樹

　　◆ 在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件(繼)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。二叉樹各結(jié)點(diǎn)的度只可能取值0、1、2，不可能是其它值。換言之，知道了度為1結(jié)點(diǎn)數(shù)量的前提下，葉子結(jié)點(diǎn)或度為2的結(jié)點(diǎn)中知道其一，就可以求出總的結(jié)點(diǎn)數(shù)。

　　★★★下面關(guān)于計(jì)算結(jié)點(diǎn)數(shù)量的幾個(gè)性質(zhì)，非常重要：

　　(1)對任意的二叉樹，葉子結(jié)點(diǎn)的數(shù)量，比度為2的結(jié)點(diǎn)數(shù)量多一個(gè)(換言之，已知葉子結(jié)點(diǎn)的數(shù)量，減去1則是度為2的結(jié)點(diǎn)數(shù)量;已知度為2的結(jié)點(diǎn)數(shù)量，加上1就是葉子結(jié)點(diǎn)數(shù)量)

　　(2)完全二叉樹如果有N個(gè)結(jié)點(diǎn)，當(dāng)N為奇數(shù)的時(shí)候，葉子結(jié)點(diǎn)數(shù)為(N+1)/2，此時(shí)二叉樹只有度為0的葉子結(jié)點(diǎn)及度為2的結(jié)點(diǎn)，沒有度為1的結(jié)點(diǎn);當(dāng)N為偶數(shù)的時(shí)候，葉子結(jié)點(diǎn)的數(shù)量為N/2。(注意條件，必須是完全二叉樹，當(dāng)然包括滿二叉樹)

　　(3)滿二叉樹第K層上的結(jié)點(diǎn)數(shù)量為2K-1;深度為K的滿二叉樹，結(jié)點(diǎn)總數(shù)為2K-1。

　　上述的計(jì)算公式，關(guān)鍵要能夠應(yīng)用，例如，深度為7的滿二叉樹，度為2的結(jié)點(diǎn)數(shù)量是多少?既然是滿二叉樹，葉子結(jié)點(diǎn)的數(shù)量就是第7層的結(jié)點(diǎn)數(shù)量，也就是26，可以算出葉子結(jié)點(diǎn)為64，因此度為2的結(jié)點(diǎn)數(shù)是63(葉子結(jié)點(diǎn)數(shù)減去1)。

　　★★★ 二叉樹的前序遍歷、中序遍歷、后續(xù)遍歷：前中后三個(gè)詞是相對于根來講的，前序是【根-->左-->右】，中序是【左-->根-->右】，后續(xù)是【左-->右-->根】。具體操作為：

　　先序遍歷(D L R): 訪問根結(jié)點(diǎn)，按先序遍歷左子樹，按先序遍歷右子樹。

　　中序遍歷(L D R): 按中序遍歷左子樹，訪問根結(jié)點(diǎn)，按中序遍歷右子樹。

　　后序遍歷(L R D): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點(diǎn)。

　　下面以中序遍歷為例，來講解實(shí)際的解題方法：對一棵樹，將根結(jié)點(diǎn)下的左子樹用一個(gè)橢圓圈起來，右子樹也用一個(gè)橢圓圈起來。之后，在左子樹上標(biāo)記上1，在根結(jié)點(diǎn)標(biāo)記上2，在右子樹上標(biāo)記上3。對在左邊橢圓內(nèi)的左子樹，現(xiàn)在把它單獨(dú)拿出來分析。把它的左子樹圈起來標(biāo)上1.1，根結(jié)點(diǎn)標(biāo)記上1.2，右子樹標(biāo)上1.3。按照上述方法依次往下，直到樹不能拆分，然后按照“左-->根--->右”的順序?qū)懗鼋Y(jié)點(diǎn)的訪問先后即可。

　　6、查找技術(shù)

　　◆ 對于長度為n的線性表，順序查找最壞情況下需要比較n次。(對數(shù)據(jù)是否有序沒有要求)�！� 順序查找最好情況下查詢次數(shù)是1，最壞情況下是n，平均為(1+n)/2。

　　★★ 對于長度為n的有序線性表，二分法最壞情況下只需要比較log2n次。(數(shù)據(jù)必須有序)

　　◆ 能用二分法進(jìn)行查找的是【順序存儲的有序線性表】。

　　7、排序技術(shù)

　　★★ 對于長度為n的線性表，【冒泡排序、快速排序、簡單插入排序、簡單選擇排序】這四種排序方式在最壞情況下的比較次數(shù)相同，都是【n(n-1)/2】。堆排序的效率最高，是【nlog2n】�！铩� 希爾排序最壞情況下需要次比較【n1.5】。希爾排序?qū)儆凇静迦腩惻判蚍ā俊?/P>

　　◆ 已知數(shù)據(jù)表A中每個(gè)元素距最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)該采用的算法是【直接插入排序】。選擇排序、插入排序、快速排序、歸并排序中對內(nèi)存要求最大的是【歸并排序】。

　　相關(guān)推薦：

　　2014年計(jì)算機(jī)等考上機(jī)六大注意事項(xiàng)

　　2014年計(jì)算機(jī)二級MySQL數(shù)據(jù)庫考點(diǎn)練習(xí)匯總

　　2014年計(jì)算機(jī)二級mysql數(shù)據(jù)庫模擬試題及答案匯總