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

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,計(jì)算機(jī)等級(jí)考試培訓(xùn)公共基礎(chǔ)算法與數(shù)據(jù)結(jié)構(gòu),計(jì)算機(jī)基礎(chǔ)教研室,內(nèi)容提要,算法的基本概念,數(shù)據(jù)結(jié)構(gòu)的基本概念,線性表,棧和隊(duì)列,線性鏈表,二叉樹(shù)極其遍歷,查找技術(shù),排序技術(shù),算法的基本概念,算法,對(duì)解決問(wèn)題方案的準(zhǔn)確而完整的描述（解決問(wèn)題的操作步驟），流程圖、,N-S,圖、文字說(shuō)明和偽代碼。,對(duì)數(shù)據(jù)對(duì)象的運(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ì)算機(jī)資源量的多少,時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量，即算法執(zhí)行的基本運(yùn)算次數(shù)，特別提醒，它和算法執(zhí)行的時(shí)間長(zhǎng)短是無(wú)關(guān)的，復(fù)雜度,=,f(n,),，一般考慮平局復(fù)雜度和最壞情況復(fù)雜度。,（,1,）,s=0 O(1),(2),for(i,=1;i=0),個(gè)數(shù)據(jù)元素構(gòu)成的有限序列，表中除第一個(gè)元素，有且只有一個(gè)前件，除最后一個(gè)元素，有且只有一個(gè)后件。表示為,(a,1,a,2,a,i-1,a,i,a,n,),。,基本特征有：,元素個(gè)數(shù),n,表長(zhǎng)度，,n=0,空表,1,i0),個(gè)結(jié)點(diǎn)的有限集,T,，,其中：,有且僅有一個(gè)特定的

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

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

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

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

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

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

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

10、點(diǎn)，則該二叉樹(shù)中的總結(jié)點(diǎn)數(shù)為,A,219 B,221 C,229 D,231,程序流程圖中帶有箭頭的線段表示的是：,A,圖元關(guān)系,B,數(shù)據(jù)流,C,控制流,D,調(diào)用關(guān)系,算法的有窮性是指,A,算法程序的運(yùn)行時(shí)間是有限的,B,算法程序所處理的數(shù)據(jù)量是有限的,C,算法程序的長(zhǎng)度是有限的,D,算法只能被有限的用戶使用,思考題目,對(duì)長(zhǎng)度為,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ù),一個(gè)

11、棧的初始狀態(tài)為空。現(xiàn)將元素,1,、,2,、,3,、,4,、,5,、,A,、,B,、,C,、,D,、,E,依次入棧，然后再依次出棧，則元素出棧的順序是,A,）,12345ABCDE B,）,EDCBA54321 C)ABCDE12345 D,）,54321EDCBA,下列敘述中正確的是,A,）循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，因此，循環(huán)隊(duì)列是非線性結(jié)構(gòu),B,）在循環(huán)隊(duì)列中，只需要隊(duì)頭指針就能反應(yīng)隊(duì)列中元素的動(dòng)態(tài)變化情況,C,）在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反應(yīng)隊(duì)列中元素的動(dòng)態(tài)變化情況,D,）循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭和隊(duì)尾指針共同決定,在長(zhǎng)度為,n,的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是,A,）,O(N)B,）,O(n2)C,）,O(log2n)D,）,O(n,log2n),思考題目,下列敘述中正確的是,A,）順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的,B,）順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu),C,）順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表,D,）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間,以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性表的結(jié)構(gòu)是,A),隊(duì)列,B),鏈表,C),二叉樹(shù),D),棧,對(duì)如下所示的二叉樹(shù)進(jìn)行遍歷,A,B,C,D,E,F,G,