單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,計算機等級考試培訓公共基礎算法與數據結構,計算機基礎教研室,內容提要,算法的基本概念,數據結構的基本概念,線性表,棧和隊列,線性鏈表,二叉樹極其遍歷,查找技術,排序技術,算法的基本概念,算法,對解決問題方案的準確而完整的描述（解決問題的操作步驟），流程圖、N-S圖、文字說明和偽代碼。,對數據對象的運算和操作。包括算數運算、邏輯運算、關系運算和數據賦值傳輸。,運算和操作的控制結構。確定運算和操作的執(zhí)行順序，有三種基本結構：順序結構、選擇結構和循環(huán)結構，C和VF都支持這三種結構。,特征可行性、確切性和有窮性（解密算法）,算法的基本概念,算法的復雜度,運行算法所消耗的計算機資源量的多少,時間復雜度：執(zhí)行算法所需要的計算工作量，即算法執(zhí)行的基本運算次數，特別提醒，它和算法執(zhí)行的時間長短是無關的，復雜度=f(n)，一般考慮平局復雜度和最壞情況復雜度。,（1）s=0 O(1),(2)for(i=1;i=0)個數據元素構成的有限序列，表中除第一個元素，有且只有一個前件，除最后一個元素，有且只有一個后件。表示為(a,1,a,2,a,i-1,a,i,a,n,)。,基本特征有：,元素個數n,表長度，n=0空表,1i0),個結點的有限集T，其中：,有且僅有一個特定的結點，稱為樹的,根,(root),當n1,時，其余結點可分為m(m0)個,互不相交,的有限集T,1,T,2,T,m,，,其中每一個集合本身又是一棵樹，稱為根的,子樹,(subtree),特點,：,樹中至少有一個結點根,樹中各子樹是互不相交的集合,樹的基本概念,結點(node)表示樹中的元素，包括數據項及若干指向其子樹的分支,根（root)無前件的節(jié)點,度一個節(jié)點擁有的后件個數，樹中節(jié)點的最大度數,葉子(leaf)度為0的結點,深度樹的層次數,A,B,C,D,E,F,G,H,I,J,K,L,M,二叉樹,二叉樹,二叉樹是n(n,0),個結點的有限集，它或為空樹(n=0)，或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成,基本性質：在二叉樹的K層上，最多有2,K-1,(K=1)個節(jié)點,深度為K的二叉樹中，最多有2,K,-1個節(jié)點,葉子節(jié)點比度數為2的節(jié)點多1個,完全二叉樹：除最后一層外，每層上的節(jié)點數達到最大值，最后一層上只缺少右邊若干節(jié)點,滿二叉樹：每層的節(jié)點數都達到其最大值，i層上的節(jié)點數為2,i-1,二叉樹的遍歷,先序遍歷：先訪問根結點,然后分別先序遍歷左子樹、右子樹,中序遍歷：先中序遍歷左子樹，然后訪問根結點，最后中序遍歷右子樹,后序遍歷：先后序遍歷左、右子樹，然后訪問根結點,按層次遍歷：從上到下、從左到右訪問各結點,-,+,/,a,*,b,-,e,f,c,d,查找,查找在某數據結構中，找出滿足指定條件的元素,順序查找,從線性表的第一個元素開始，逐一的將表中的每個元素與查找元素比較，若成功，便停止，若到表尾都未找出，查找失敗,若有n個元素，平均查找次數為n/2，時間復雜度為O(n)，一般用于無序表和鏈式存儲結構的查找,二分查找（折半查找）,要求查找的數據結構必須是有序的順序結構，對于元素個數為n的有序表，查找過程是：先找出中間元素，若匹配，查找成功；若比中間值大，則丟掉前半部分，在后半部繼續(xù)二分查找；若比中間值小，則丟掉后半部分，在前半部分繼續(xù)二分查找，時間復雜度為O(lon,2,n),比順序查找少。,排序,排序將一個無序序列整理成按值非遞減排列的有序序列,方法很多，主要的方法有：,冒泡排序法：比較相鄰元素，若逆序，則交換，O(n,2,),n(n-1)/2,快速排序法：指定一個K元素，HIGH從后向前掃描，遇見第一個小于K的元素，和K元素交換，接著LOW從前往后掃描，遇見第一個大于K的元素，和K交換，直到H和L相等，O(nlon,2,n),n,2,簡單插入排序法：將某一元素插入到前面已經排好的有序子表中,O(n,2,),n(n-1)/2,希爾排序法：將元素分為若干組，組內簡單插入排序，縮小分組，再繼續(xù)，直到一個元素一組,簡單選擇排序法：在元素中選擇最小的，和第一個元素交換，然后在剩下的n-1個元素中，重復此操作 O(n,2,),n(n-1)/2,排序效率的評估,很難說哪種排序是最好的，各種排序方式都有自己的優(yōu)缺點,考慮的因素有：元素個數 n的長度；穩(wěn)定性要求；存儲輔助空間的大?。粩祿乇旧淼拇笮〉鹊?。,若n比較小，采用直接插入排序和選擇排序,若元素已經基本有序，只有個別的逆序，采用簡單插入排序和冒泡排序,若n比較大，采用快速排序和堆排序,穩(wěn)定性：選擇排序、快速排序、希爾排序、堆排序不是穩(wěn)定的排序算法，而冒泡排序、插入排序、歸并排序和基數排序是穩(wěn)定的排序算法。,思考題目,下列敘述中正確的是,A,算法的效率只與問題的規(guī)模有關，而與數據的存儲結構無關,B,算法的時間復雜度是指執(zhí)行算法所需要的計算工作量,C,數據的邏輯結構與存儲結構是一一對應的,D,算法的時間復雜度與空間復雜度一定相關,下列對列的敘述正確的是,A,隊列屬于非線性表,B,隊列按“先進后出”原則組織數據,C,隊列在隊尾刪除數據,D,隊列按“先進先出”原則組織數據,某二叉樹中有,n,個度為,2,的結點，則該二叉樹中的葉子結點為,A,n+1 B,n-1 C,2n D,n/2,下列敘述中，不符合良好程序設計風格要求的是,A,程序的效率第一，清晰第二,B,程序的可讀性好,C,程序中要有必要的注釋,D,輸入數據前要有提示信息,下列敘述中正確的是,A,程序執(zhí)行的效率與數據的存儲結構密切相關,B,程序執(zhí)行的效率只取決于程序的控制結構,C,程序執(zhí)行的效率只取決于所處理的數據量,D,以上三種說法都不對,思考題目,下列敘述中正確的是,A,數據的邏輯結構與存儲結構必定是一一對應的,B,由于計算機存儲空間是向量式的存儲結構，因此，數據的存儲結構一定是線性結構,C,程序設計語言中的數組一般是順序存儲結構，因此，利用數組只能處理線性結構,D,以上三種說法都不對,冒泡排序在最壞情況下的比較次數是,A,(n,1)/2 B,nlog2 n C,n(n,1)/2 D,/2,一棵二叉樹中共有,70,個葉子結點與,80,個度為,1,的結點，則該二叉樹中的總結點數為,A,219 B,221 C,229 D,231,程序流程圖中帶有箭頭的線段表示的是：,A,圖元關系,B,數據流,C,控制流,D,調用關系,算法的有窮性是指,A,算法程序的運行時間是有限的,B,算法程序所處理的數據量是有限的,C,算法程序的長度是有限的,D,算法只能被有限的用戶使用,思考題目,對長度為,n,的線性表排序，在最壞情況下，比較次數不是,n(n-1)/2,的排序方法是,A,快速排序,B,冒泡排序,C,直線插入排序,D,堆排序,下列關于棧的敘述正確的是,A,棧按“先進先出”組織數據,B,棧按“先進后出”組織數據,C,只能在棧底插入數據,D,不能刪除數據,一個棧的初始狀態(tài)為空?，F將元素,1,、,2,、,3,、,4,、,5,、,A,、,B,、,C,、,D,、,E,依次入棧，然后再依次出棧，則元素出棧的順序是,A,）,12345ABCDE B,）,EDCBA54321 C)ABCDE12345 D,）,54321EDCBA,下列敘述中正確的是,A,）循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結構,B,）在循環(huán)隊列中，只需要隊頭指針就能反應隊列中元素的動態(tài)變化情況,C,）在循環(huán)隊列中，只需要隊尾指針就能反應隊列中元素的動態(tài)變化情況,D,）循環(huán)隊列中元素的個數是由隊頭和隊尾指針共同決定,在長度為,n,的有序線性表中進行二分查找，最壞情況下需要比較的次數是,A,）,O(N)B,）,O(n2)C,）,O(log2n)D,）,O(n,log2n),思考題目,下列敘述中正確的是,A,）順序存儲結構的存儲一定是連續(xù)的，鏈式存儲結構的存儲空間不一定是連續(xù)的,B,）順序存儲結構只針對線性結構，鏈式存儲結構只針對非線性結構,C,）順序存儲結構能存儲有序表，鏈式存儲結構不能存儲有序表,D,）鏈式存儲結構比順序存儲結構節(jié)省存儲空間,以下數據結構中不屬于線性表的結構是,A),隊列,B),鏈表,C),二叉樹,D),棧,對如下所示的二叉樹進行遍歷,A,B,C,D,E,F,G,