計算機等級考試培訓(xùn)公共基礎(chǔ)(一).ppt

1、計算機等級考試培訓(xùn)公共基礎(chǔ)算法與數(shù)據(jù)結(jié)構(gòu),計算機基礎(chǔ)教研室,內(nèi)容提要,算法的基本概念 數(shù)據(jù)結(jié)構(gòu)的基本概念 線性表 棧和隊列 線性鏈表 二叉樹極其遍歷 查找技術(shù) 排序技術(shù),算法的基本概念,算法對解決問題方案的準確而完整的描述（解決問題的操作步驟），流程圖、N-S圖、文字說明和偽代碼。 對數(shù)據(jù)對象的運算和操作。包括算數(shù)運算、邏輯運算、關(guān)系運算和數(shù)據(jù)賦值傳輸。 運算和操作的控制結(jié)構(gòu)。確定運算和操作的執(zhí)行順序，有三種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，C和VF都支持這三種結(jié)構(gòu)。 特征可行性、確切性和有窮性（解密算法）,算法的基本概念,算法的復(fù)雜度運行算法所消耗的計算機資源量的多少 時間復(fù)雜度：執(zhí)行

2、算法所需要的計算工作量，即算法執(zhí)行的基本運算次數(shù)，特別提醒，它和算法執(zhí)行的時間長短是無關(guān)的，復(fù)雜度=f(n)，一般考慮平局復(fù)雜度和最壞情況復(fù)雜度。 （1）s=0 O(1) (2) for(i=1;i=n;i+) s=s+I O(n) 空間復(fù)雜度：執(zhí)行一個算法所需要的內(nèi)存空間，包括三個方面：數(shù)據(jù)占用空間、程序占用空間、額外空間占用。,數(shù)據(jù)結(jié)構(gòu)的基本概念,數(shù)據(jù)結(jié)構(gòu)研究非數(shù)值計算的程序設(shè)計問題中的數(shù)據(jù)以及它們之間的關(guān)系和運算 邏輯關(guān)系（結(jié)構(gòu)）：數(shù)據(jù)元素本身和它們的前后件關(guān)系 物理關(guān)系（結(jié)構(gòu)）：邏輯結(jié)構(gòu)在計算機存儲空間的存儲方式，順序結(jié)構(gòu)和鏈式結(jié)構(gòu) 運算：實現(xiàn)的處理方法,線性表,線性表n(n=0)個數(shù)

3、據(jù)元素構(gòu)成的有限序列，表中除第一個元素，有且只有一個前件，除最后一個元素，有且只有一個后件。表示為(a1,a2,ai-1,ai,an)。 基本特征有： 元素個數(shù)n表長度，n=0空表 1in時 ai的直接前驅(qū)是ai-1，a1無直接前驅(qū) ai的直接后繼是ai+1，an無直接后繼 元素同構(gòu)，且不能出現(xiàn)缺項 順序存儲結(jié)構(gòu)：邏輯上相鄰，物理存儲上也相鄰（數(shù)組） 鏈式存儲結(jié)構(gòu)：用節(jié)點來存儲數(shù)據(jù)和邏輯相鄰數(shù)據(jù)的地址，邏輯上相鄰，物理上未必相鄰（線性鏈表，雙向鏈表,循環(huán)鏈表）,棧和隊列,棧和隊列是兩種特殊的線性表，是操作受限的線性表 棧（stack）限定在表的一端插入和刪除元素的線性表，遵循“先進后出，后進先

4、出”原則，可以逆序改變元素的順序 出棧操作和進棧操作,棧和隊列,隊列限定只能在表的一端進行插入，在表的另一端進行刪除的線性表，遵循“先進先出，后進后出”原則，入隊操作和進隊操作。,樹的基本概念,定義：樹(tree)是n(n0)個結(jié)點的有限集T，其中： 有且僅有一個特定的結(jié)點，稱為樹的根(root) 當n1時，其余結(jié)點可分為m(m0)個互不相交的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree) 特點： 樹中至少有一個結(jié)點根 樹中各子樹是互不相交的集合,樹的基本概念,結(jié)點(node)表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支 根（root)無前件的節(jié)點 度

5、一個節(jié)點擁有的后件個數(shù)，樹中節(jié)點的最大度數(shù) 葉子(leaf)度為0的結(jié)點 深度樹的層次數(shù),二叉樹,二叉樹二叉樹是n(n0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成 基本性質(zhì)：在二叉樹的K層上，最多有2K-1(K=1)個節(jié)點 深度為K的二叉樹中，最多有2K-1個節(jié)點 葉子節(jié)點比度數(shù)為2的節(jié)點多1個 完全二叉樹：除最后一層外，每層上的節(jié)點數(shù)達到最大值，最后一層上只缺少右邊若干節(jié)點 滿二叉樹：每層的節(jié)點數(shù)都達到其最大值，i層上的節(jié)點數(shù)為2i-1,二叉樹的遍歷,先序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹 中序遍歷：先中序遍歷左子

6、樹，然后訪問根結(jié)點，最后中序遍歷右子樹 后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點 按層次遍歷：從上到下、從左到右訪問各結(jié)點,查找,查找在某數(shù)據(jù)結(jié)構(gòu)中，找出滿足指定條件的元素 順序查找 從線性表的第一個元素開始，逐一的將表中的每個元素與查找元素比較，若成功，便停止，若到表尾都未找出，查找失敗 若有n個元素，平均查找次數(shù)為n/2，時間復(fù)雜度為O(n)，一般用于無序表和鏈式存儲結(jié)構(gòu)的查找 二分查找（折半查找） 要求查找的數(shù)據(jù)結(jié)構(gòu)必須是有序的順序結(jié)構(gòu)，對于元素個數(shù)為n的有序表，查找過程是：先找出中間元素，若匹配，查找成功；若比中間值大，則丟掉前半部分，在后半部繼續(xù)二分查找；若比中間值小，則丟掉后

7、半部分，在前半部分繼續(xù)二分查找，時間復(fù)雜度為O(lon2n),比順序查找少。,排序,排序?qū)⒁粋€無序序列整理成按值非遞減排列的有序序列 方法很多，主要的方法有： 冒泡排序法：比較相鄰元素，若逆序，則交換， O(n2) ,n(n-1)/2 快速排序法：指定一個K元素，HIGH從后向前掃描，遇見第一個小于K的元素，和K元素交換，接著LOW從前往后掃描，遇見第一個大于K的元素，和K交換，直到H和L相等， O(nlon2n), n2 簡單插入排序法：將某一元素插入到前面已經(jīng)排好的有序子表中, O(n2), n(n-1)/2 希爾排序法：將元素分為若干組，組內(nèi)簡單插入排序，縮小分組，再繼續(xù)，直到一個元素一

8、組 簡單選擇排序法：在元素中選擇最小的，和第一個元素交換，然后在剩下的n-1個元素中，重復(fù)此操作 O(n2), n(n-1)/2,排序效率的評估,很難說哪種排序是最好的，各種排序方式都有自己的優(yōu)缺點 考慮的因素有：元素個數(shù) n的長度；穩(wěn)定性要求；存儲輔助空間的大小；數(shù)據(jù)元素本身的大小等等。 若n比較小，采用直接插入排序和選擇排序 若元素已經(jīng)基本有序，只有個別的逆序，采用簡單插入排序和冒泡排序 若n比較大，采用快速排序和堆排序 穩(wěn)定性： 選擇排序、快速排序、希爾排序、堆排序不是穩(wěn)定的排序算法，而冒泡排序、插入排序、歸并排序和基數(shù)排序是穩(wěn)定的排序算法。,思考題目,下列敘述中正確的是A算法的效率只與

9、問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量C數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的D算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān) 下列對列的敘述正確的是A隊列屬于非線性表 B隊列按“先進后出”原則組織數(shù)據(jù)C隊列在隊尾刪除數(shù)據(jù) D隊列按“先進先出”原則組織數(shù)據(jù) 某二叉樹中有n個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點為An+1 Bn-1 C2n Dn/2 下列敘述中，不符合良好程序設(shè)計風格要求的是A程序的效率第一， 清晰第二 B程序的可讀性好C程序中要有必要的注釋 D輸入數(shù)據(jù)前要有提示信息 下列敘述中正確的是A程序執(zhí)行的效率與數(shù)據(jù)的存儲結(jié)構(gòu)密切相關(guān)B程序執(zhí)行的效率只

10、取決于程序的控制結(jié)構(gòu)C程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量D以上三種說法都不對,思考題目,下列敘述中正確的是A數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的B由于計算機存儲空間是向量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)C程序設(shè)計語言中的數(shù)組一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu)D以上三種說法都不對 冒泡排序在最壞情況下的比較次數(shù)是A(n1)/2 Bnlog2 n Cn(n1)/2 D/2 一棵二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為A219 B221 C229 D231 程序流程圖中帶有箭頭的線段表示的是：A圖元關(guān)系 B數(shù)據(jù)流 C控制流 D調(diào)用

11、關(guān)系 算法的有窮性是指A算法程序的運行時間是有限的 B算法程序所處理的數(shù)據(jù)量是有限的 C算法程序的長度是有限的 D算法只能被有限的用戶使用,思考題目,對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)/2的排序方法是A快速排序 B冒泡排序 C直線插入排序 D堆排序 下列關(guān)于棧的敘述正確的是A棧按“先進先出”組織數(shù)據(jù) B棧按“先進后出”組織數(shù)據(jù) C只能在棧底插入數(shù)據(jù) D不能刪除數(shù)據(jù) 一個棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是 A）12345ABCDE B）EDCBA54321 C )ABCDE12345 D）54321EDCBA 下列敘述中正確的是 A）循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu) B）在循環(huán)隊列中，只需要隊頭指針就能反應(yīng)隊列中元素的動態(tài)變化情況 C）在循環(huán)隊列中，只需要隊尾指針就能反應(yīng)隊列中元素的動態(tài)變化情況 D）循環(huán)隊列中元素的個數(shù)是由隊頭和隊尾指針共同決定 在長度為n的有序線性表中進行二分查找，最壞情況下需要比較的次數(shù)是 A）O(N) B）O(n2) C）O(log2n) D）O(n log2n),思考題目,下列敘述中正確的是