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

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

在二叉樹的第k層上，最多有個結點。性質2

深度為m的二叉樹最多有個結點。性質3

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

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

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

8126576976三次交換:23135157

8126666976四次交換:23135157

66

2681

6976五次交換:23135157

26

6681

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