國家計算機二級考試第一章

1二級公共基礎(chǔ)知識第一章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)2內(nèi)容提要算法:算法的基本概念、算法復(fù)雜度數(shù)據(jù)結(jié)構(gòu)的基本概念：什么是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)的圖形表示、線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性表及其順序存儲結(jié)構(gòu)：線性表的基本概念、順序存儲結(jié)構(gòu)、插入運算、刪除運算棧和隊列：棧及其基本運算、隊列及其基本運算線性鏈表：基本概念、基本運算、循環(huán)鏈表及其基本運算樹與二叉樹：樹的基本概念、二叉樹及其基本性質(zhì)、二叉樹的存儲結(jié)構(gòu)、二叉樹的遍歷查找技術(shù)：順序查找、二分法查找排序技術(shù)：交換類排序法、插入類排序法、選擇類排序法31.1算法41.1.1算法的基本概念算法是解題方案的準確而完整的描述，它不等于程序，也不等計算方法。1．算法的基本特征可行性(effectiveness)確定性(definiteness)有窮性(finiteness)擁有足夠的情報2．算法的基本要素算法中對數(shù)據(jù)的運算和操作算術(shù)運算:包括加、減、乘、除等）邏輯運算:包括“與”、“或”、“非”等運算）關(guān)系運算:包括“大于”、“小于”、“等于”、“不等于”等）數(shù)據(jù)傳輸:包括賦值、輸入、輸出等操作算法的控制結(jié)構(gòu):順序、選擇、循環(huán)51.1.1算法的基本概念3．算法設(shè)計的基本方法列舉法歸納法遞推遞歸減半遞推技術(shù)回溯法61.1.1算法的基本概念4．算法設(shè)計的設(shè)計要求正確性可讀性健壯性效率和低存儲量需求71.1.2算法復(fù)雜度算法復(fù)雜度：時間復(fù)雜度、空間復(fù)雜度1．算法的時間復(fù)雜度執(zhí)行算法所需要的計算工作量與下列因素有關(guān)：書寫算法的程序設(shè)計語言編譯產(chǎn)生的機器語言，代碼質(zhì)量機器執(zhí)行指令的速度問題的規(guī)模81.1.2算法復(fù)雜度問題的規(guī)模函數(shù)算法的工作量=f(n)算法中基本操作重復(fù)執(zhí)行的頻率T(n)，是問題規(guī)模n的某個函數(shù)f(n)，記作：T(n)=O(f(n))記號“O”讀作“大O”。表示隨問題規(guī)模n的增加，算法執(zhí)行時間的增長率和f(n)相應(yīng)增加。常見算法復(fù)雜度：O(1)：常數(shù)階O(n)：作線性階O(n2)：平方階O(n3)：立方階O(logn)：對數(shù)階O(2n)：指數(shù)階91.1.2算法復(fù)雜度n×n矩陣相乘算法：時間復(fù)雜度為O(n3)。101.1.2算法復(fù)雜度分析算法的工作量兩種方法：平均性態(tài)最壞情況復(fù)雜性111.1.2算法復(fù)雜度2．算法的空間復(fù)雜度算法執(zhí)行過程中所需的最大存儲空間存儲量包括以下三部分算法程序所占的空間輸入的初始數(shù)據(jù)所占的存儲空間算法執(zhí)行過程中所要的額外空間算法空間復(fù)雜度可定義為：S(n)=O(f(n))原地工作(inplace)的算法：記作O(1)壓縮存儲技術(shù)121.2數(shù)據(jù)結(jié)構(gòu)的基本概念131.2.1什么是數(shù)據(jù)結(jié)構(gòu)1．數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)對各種數(shù)據(jù)結(jié)構(gòu)進行的運算2．研究數(shù)據(jù)結(jié)構(gòu)目的提高數(shù)據(jù)處理的速度盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間141.2.1什么是數(shù)據(jù)結(jié)構(gòu)1．數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)對各種數(shù)據(jù)結(jié)構(gòu)進行的運算2．研究數(shù)據(jù)結(jié)構(gòu)目的提高數(shù)據(jù)處理的速度盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間151.2.1什么是數(shù)據(jù)結(jié)構(gòu)1．數(shù)據(jù)的邏輯結(jié)構(gòu)2、數(shù)據(jù)的存儲結(jié)構(gòu)3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)B．非線性結(jié)構(gòu)A順序存儲B鏈式存儲線性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面161.2.1什么是數(shù)據(jù)結(jié)構(gòu)3．數(shù)據(jù)結(jié)構(gòu)的定義相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合數(shù)據(jù)元素之間的關(guān)系可以用前后件關(guān)系來描述一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面信息：表示數(shù)據(jù)元素的信息表示各數(shù)據(jù)元素之間的前后件關(guān)系171.2.1什么是數(shù)據(jù)結(jié)構(gòu)4．數(shù)據(jù)的邏輯結(jié)構(gòu)對數(shù)據(jù)元素之間的邏輯關(guān)系的描述只抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系，與計算機中的存儲無關(guān)兩個要素：數(shù)據(jù)元素的集合，通常記為D；前后件關(guān)系，通常記為R一個數(shù)據(jù)結(jié)構(gòu)B可以表示為：B=（D，R）181.2.1什么是數(shù)據(jù)結(jié)構(gòu)5．數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式常用的存儲結(jié)構(gòu)：順序鏈式索引一種數(shù)據(jù)結(jié)構(gòu)可根據(jù)需要采用不同的存儲結(jié)構(gòu)。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同191.2.2數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)點：用方框表示根結(jié)點、終端結(jié)點前后件關(guān)系：用有向線段表示基本運算：插入運算刪除運算查找、分類、合并、分解、復(fù)制、修改、……201.2.3線性結(jié)構(gòu)與非線性結(jié)構(gòu)空的數(shù)據(jù)結(jié)構(gòu)：一個數(shù)據(jù)元素都沒有線性結(jié)構(gòu)如果一個非空數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：有且只有一個根結(jié)點；每一個結(jié)點最多有一個前件，也最多有一個后件。常見的線性結(jié)構(gòu)有：線性表、棧與隊列、線性鏈表非線性結(jié)構(gòu)如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)常見的非線性結(jié)構(gòu)有：樹、二叉樹、圖211.3線性表及其順序存儲結(jié)構(gòu)221.3.1線性表的基本概念線性表：由n(n≥0)個相同類型數(shù)據(jù)元素構(gòu)成的有限序列：n定義為線性表的表長；n=0時的線性表被稱為空表。稱i為在線性表中的位序。例如：英文大寫字母表（A，B，C，D，E，F(xiàn)，…X，Y，Z）同一花色的13張撲克牌(2,3,4,5,6,7,8,9,10,J,Q,K,A)231.3.1線性表的基本概念線性表的結(jié)構(gòu)特征數(shù)據(jù)元素在表中的位置由序號決定，數(shù)據(jù)元素之間的相對位置是線性的；對于一個非空線性表，有且只有一個根結(jié)點a1，它無前件，有且只有一個終端結(jié)點an，它無后件，除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。線性表的存儲結(jié)構(gòu)順序存儲鏈式存儲241.3.2線性表的順序存儲結(jié)構(gòu)兩個基本特點：線性表中所有元素所占的存儲空間是連續(xù)的。線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。存儲示意圖251.3.3順序表的插入運算261.3.4順序表的刪除運算27順序表的插入和刪除分析插入算法的分析假設(shè)線性表中含有n個數(shù)據(jù)元素，在進行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：刪除算法的分析在進行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為：分析結(jié)論順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，這一點需要值得考慮281.4棧和隊列291.4.1棧及其基本運算1．棧的定義棧（stack）：一種只允許在表的一端進行插入或刪除操作的特殊的線性表棧頂(top)：允許進行插入與刪除操作的一端棧底(bottom)：不允許插入與刪除操作的另一端先進后出（FILO）或后進先出(LIFO)的線性表301.4.1棧及其基本運算2．棧的順序存儲及其運算top=0：?？誸op=m：棧滿棧的基本運算入棧運算退棧運算讀棧頂元素311.4.2隊列及其基本運算1．隊列的定義限定只能在表的一端進行插入和在另一端進行刪除操作的線性表隊尾(rear)：允許插入的一端隊頭(front)：允許刪除的另一端先進先出（FIFO）表或后進后出（LILO）線性表基本操作入隊運算：往隊列的隊尾插入一個元素，隊尾指針rear的變化退隊運算：從隊列的排頭刪除一個元素，隊頭指針front的變化321.4.2隊列及其基本運算2．循環(huán)隊列及其運算隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用入隊運算：隊尾指針加1，并當rear=m+1時置rear=1出隊運算：隊頭指針加1，并當front=m+1時置front=1331.5線性鏈表341.5.1線性鏈表的基本概念1．線性表順序存儲的缺點插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數(shù)據(jù)元素時需要移動大量的數(shù)據(jù)元素。線性表的順序存儲結(jié)構(gòu)下，線性表的存儲空間不便于擴充。線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。351.5.1線性鏈表的基本概念2．線性鏈表線性表的鏈式存儲結(jié)構(gòu)物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實現(xiàn)的每個結(jié)點由兩部分組成：數(shù)據(jù)域和指針域361.5.1線性鏈表的基本概念雙向鏈表：每個結(jié)點設(shè)置兩個指針左指針：指向其前件結(jié)點右指針：指向其后件結(jié)點371.5.2線性鏈表的基本運算插入刪除合并分解逆轉(zhuǎn)復(fù)制排序查找381.5.2線性鏈表的基本運算1．在線性鏈表中查找指定元素鏈表不是隨機存取結(jié)構(gòu)從鏈表的頭指針出發(fā)，順著鏈域next逐個結(jié)點往下搜索，直至搜索到第i個結(jié)點為止2．線性鏈表的插入391.5.2線性鏈表的基本運算3．線性鏈表的刪除與順序存儲相比，鏈表的優(yōu)點有：插入和刪除元素時，不需要移動數(shù)據(jù)元素，只需要修改指針即可401.5.3棧和隊列的鏈式存儲結(jié)構(gòu)1．棧的鏈式存儲結(jié)構(gòu)——鏈棧411.5.3棧和隊列的鏈式存儲結(jié)構(gòu)2．隊列鏈式存儲結(jié)構(gòu)——鏈隊列421.5.4循環(huán)鏈表及其基本運算循環(huán)鏈表特點：在鏈表中增加了一個表頭結(jié)點最后一個結(jié)點的指針域指向表頭結(jié)點，構(gòu)成了一個環(huán)狀鏈循環(huán)鏈表優(yōu)點：從任一結(jié)點出發(fā)來訪問表中其他所有結(jié)點空表與非空表的運算的統(tǒng)一431.6樹與二叉樹1．樹的定義樹(Tree)是n(n≥0)個結(jié)點的有限集T，T為空時稱為空樹，否則它滿足如下兩個條件：（1）有且僅有一個特定的稱為根(Root)的結(jié)點；（2）其余的結(jié)點可分為m(m≥0)個互不相交的子集T1，T2，T3，…，Tm，其中每個子集又是一棵樹，并稱其為子樹。44ABCDEFGHIJKL(b)一般的樹451.6樹與二叉樹2．樹中的基本概念父結(jié)點與樹的根：每個結(jié)點最多只允許有一個前件，稱為該結(jié)點的父結(jié)點。沒有前件的結(jié)點中有一個，稱為樹的根結(jié)點。子結(jié)點與葉子結(jié)點：在樹結(jié)構(gòu)中，每一個結(jié)點可以有多個后件，它們都稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。結(jié)點的度和樹的度：一個結(jié)點所擁有后件個數(shù)稱為該結(jié)點的度。一棵樹中各個結(jié)點度數(shù)的最大值叫做這棵樹的度。層和樹的深度：樹結(jié)構(gòu)是一種層次結(jié)構(gòu)，根結(jié)點為第一層，根的子結(jié)點為第二層，其余各結(jié)點的層數(shù)逐層由上而下計算。一棵樹中結(jié)點的最大層數(shù)叫做此樹的深度。461.6.1樹的基本概念樹的特點（1）樹中只有根結(jié)點沒有前件；（2）除根外，其余結(jié)點都有且僅一個前件；（3）樹的結(jié)點，可以有零個或多個后件；（4）除根外的其他結(jié)點，都存在唯一條從根到該結(jié)點的路徑；（5）樹是一種分支結(jié)構(gòu)（除根的結(jié)點外）每個元素都有且僅有一個直接前件，有且僅有零個或多個直接后件。樹的存儲用多重鏈表來表示471.6.2二叉樹及其基本性質(zhì)1．二叉樹的定義一個二叉樹是n個結(jié)點的有限集合（n≥0），此集合或者是空集（n=0），或者是由一個根結(jié)點及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成，并且左右子樹都是二叉樹。特點：非空二叉樹只有一個根結(jié)點；每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。481.6.2二叉樹及其基本性質(zhì)2．二叉樹的性質(zhì)性質(zhì)1

在二叉樹的第k層上，最多有個結(jié)點。性質(zhì)2

深度為m的二叉樹最多有個結(jié)點。性質(zhì)3

在任意一棵二叉樹中，度數(shù)為0的結(jié)點（即葉子結(jié)點）總比度為2的結(jié)點多一個。即：其中，n0表示度數(shù)為0的結(jié)點數(shù)，n2表示度數(shù)為2的結(jié)點數(shù)。性質(zhì)4

具有n個結(jié)點的二叉樹的深度至少為，其中表示取的整數(shù)部分。491.6.2二叉樹及其基本性質(zhì)3．滿二叉樹和完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。完全二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。501.6.2二叉樹及其基本性質(zhì)性質(zhì)5具有n個結(jié)點的完全二叉樹深度為。性質(zhì)6設(shè)完全二叉樹共有n個結(jié)點，如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點進行編號，則對于編號為k（k=1，2，…，n）的結(jié)點有以下結(jié)論：①若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>1，則該結(jié)點的父結(jié)點的編號為INT(k/2)。②若2k≤n，則編號為k的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。③若2k+1≤n，則編號為k的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。511.6.3二叉樹的存儲結(jié)構(gòu)普通二叉樹采用鏈式存儲結(jié)構(gòu)存儲結(jié)點由兩部分組成：數(shù)據(jù)域與指針域兩個指針域：左指針域右指針域滿二叉樹與完全二叉樹采用順序存儲結(jié)構(gòu)521.6.4二叉樹的遍歷二叉樹的遍歷：不重復(fù)地訪問二叉樹中的所有結(jié)點1．前序遍歷（DLR）首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。2．中序遍歷（LDR）首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹3．后序遍歷（LRD）首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。531.6.4二叉樹的遍歷前序遍歷：A、B、D、G、C、E、F中序遍歷：D、G、B、A、E、C、F后序遍歷：G、D、B、E、F、C、AP16-33圖54ABCDEF551.7查找技術(shù)561.7查找技術(shù)查找（Searching）：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。查找結(jié)果：查找成功：找到查找不成功：沒找到平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)571.7.1順序查找基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。平均要與表中一半以上元素進行比較，最壞情況下需要比較n次。下列兩種情況下只能采用順序查找：如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，都只能用順序查找。即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找。581.7.2二分法查找思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進行。查找過程：1）若中間項的值等于x,則說明已查到。2）若x小于中間項的值，則在線性表的前半部分查找；3）若x大于中間項的值，則在線性表的后半部分查找。特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。591.7.2二分法查找例：查找元素22過程：601.8排序技術(shù)611.8.1交換類排序法基本思想兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個記錄的次序相反時即進行交換，直到?jīng)]有反序的記錄為止。方法冒泡排序快速排序621.冒泡排序基本思想對存放原始數(shù)據(jù)的數(shù)組，按從后往前的方向進行多次掃描，當發(fā)現(xiàn)相鄰兩個數(shù)據(jù)的次序與排序要求的“遞增次序”不符合時，即將這兩個數(shù)據(jù)進行互換。這樣，較小的數(shù)據(jù)就會逐單元向前移動，好象氣泡向上浮起一樣。性能分析假設(shè)線性表的長度n，則在最壞情況下，需要的比較次數(shù)為n(n-1)/2。631.冒泡排序642．快速排序基本思想任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基準元素的排序碼，然后分別對兩個子序列繼續(xù)進行排序，直至整個序列有序?？焖倥判虻钠骄鶗r間復(fù)雜度為O(nlog2n)。652．快速排序P66-5:快速排序法初始順序:661351768126576923

一次交換:231351768126576966二次交換:23135166

8126576976三次交換:23135157

8126666976四次交換:23135157

66

2681

6976五次交換:23135157

26

6681

697666671.8.2插入類排序法基本思想：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當位置，直到全部記錄插入完成為止。方法:簡單插入排序希爾排序681．簡單插入排序法基本思想：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。在最壞的情況下，需要n(n-1)/2次比較