《計算機(jī)等級考試公共基礎(chǔ)(一)》由會員分享，可在線閱讀，更多相關(guān)《計算機(jī)等級考試公共基礎(chǔ)(一)（19頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

2、性和有窮性（解密算法）,算法的基本概念,算法的復(fù)雜度,運(yùn)行算法所消耗的計算機(jī)資源量的多少,時間復(fù)雜度：執(zhí)行算法所需要的計算工作量，即算法執(zhí)行的基本運(yùn)算次數(shù)，特別提醒，它和算法執(zhí)行的時間長短是無關(guān)的，復(fù)雜度,=,f(n,),，一般考慮平局復(fù)雜度和最壞情況復(fù)雜度。,（,1,）,s=0 O(1),(2),for(i,=1;i=0),個數(shù)據(jù)元素構(gòu)成的有限序列，表中除第一個元素，有且只有一個前件，除最后一個元素，有且只有一個后件。表示為,(a,1,a,2,a,i-1,a,i,a,n,),。,基本特征有：,元素個數(shù),n,表長度，,n=0,空表,1,i0),個結(jié)點的有限集,T,，,其中：,有且僅有一個特定的

3、結(jié)點，稱為樹的,根,(root),當(dāng),n1,時，其余結(jié)點可分為,m(m,0),個,互不相交,的有限集,T,1,T,2,T,m,，,其中每一個集合本身又是一棵樹，稱為根的,子樹,(,subtree,),特點,：,樹中至少有一個結(jié)點,根,樹中各子樹是互不相交的集合,樹的基本概念,結(jié)點,(node),表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支,根（,root),無前件的節(jié)點,度,一個節(jié)點擁有的后件個數(shù)，樹中節(jié)點的最大度數(shù),葉子,(leaf),度為,0,的結(jié)點,深度,樹的層次數(shù),A,B,C,D,E,F,G,H,I,J,K,L,M,二叉樹,二叉樹,二叉樹是,n(n,0),個結(jié)點的有限集，它或為空樹

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

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

6、雜度為,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,簡單插入排序法：將某一元素插入到前面已經(jīng)排好的有序子表中,O(n,2,),n(n-1)/2,希爾排序法：將元素分為若干組，組內(nèi)簡單插入排序，縮小分組，再繼續(xù)，直

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

8、述中正確的是,A,算法的效率只與問題的規(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,隊列按“先進(jìn)后出”原則組織數(shù)據(jù),C,隊列在隊尾刪除數(shù)據(jù),D,隊列按“先進(jìn)先出”原則組織數(shù)據(jù),某二叉樹中有,n,個度為,2,的結(jié)點，則該二叉樹中的葉子結(jié)點為,A,n+1 B,n-1 C,2n D,n/2,下列敘述中，不符合良好程序設(shè)計風(fēng)格要求的是,A,程序的效率第一，清晰第二,B,程序的可讀性好,C,程序中要有必要的注釋,D,輸入數(shù)據(jù)前要有提

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

10、點，則該二叉樹中的總結(jié)點數(shù)為,A,219 B,221 C,229 D,231,程序流程圖中帶有箭頭的線段表示的是：,A,圖元關(guān)系,B,數(shù)據(jù)流,C,控制流,D,調(diào)用關(guān)系,算法的有窮性是指,A,算法程序的運(yùn)行時間是有限的,B,算法程序所處理的數(shù)據(jù)量是有限的,C,算法程序的長度是有限的,D,算法只能被有限的用戶使用,思考題目,對長度為,n,的線性表排序，在最壞情況下，比較次數(shù)不是,n(n-1)/2,的排序方法是,A,快速排序,B,冒泡排序,C,直線插入排序,D,堆排序,下列關(guān)于棧的敘述正確的是,A,棧按“先進(jìn)先出”組織數(shù)據(jù),B,棧按“先進(jìn)后出”組織數(shù)據(jù),C,只能在棧底插入數(shù)據(jù),D,不能刪除數(shù)據(jù),一個

11、棧的初始狀態(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,的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是,A,）,O(N)B,）,O(n2)C,）,O(log2n)D,）,O(n,log2n),思考題目,下列敘述中正確的是,A,）順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的,B,）順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu),C,）順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表,D,）鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間,以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性表的結(jié)構(gòu)是,A),隊列,B),鏈表,C),二叉樹,D),棧,對如下所示的二叉樹進(jìn)行遍歷,A,B,C,D,E,F,G,