《計(jì)算機(jī)等級(jí)考試培訓(xùn)公共基礎(chǔ)》由會(huì)員分享，可在線閱讀，更多相關(guān)《計(jì)算機(jī)等級(jí)考試培訓(xùn)公共基礎(chǔ)（19頁珍藏版）》請(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ù),算法的基本概念,算法,對(duì)解決問題方案的準(zhǔn)確而完整的描述（解決問題的操作步驟），流程圖、N-S圖、文字說明和偽代碼。,對(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í)間長短是無關(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,表長度，n=0空表,1i0),個(gè)結(jié)點(diǎn)的有限集T，其中：,有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的,根,(root),當(dāng)n1,時(shí)，其余結(jié)

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

4、二叉樹的K層上，最多有2,K-1,(K=1)個(gè)節(jié)點(diǎn),深度為K的二叉樹中，最多有2,K,-1個(gè)節(jié)點(diǎn),葉子節(jié)點(diǎn)比度數(shù)為2的節(jié)點(diǎn)多1個(gè),完全二叉樹：除最后一層外，每層上的節(jié)點(diǎn)數(shù)達(dá)到最大值，最后一層上只缺少右邊若干節(jié)點(diǎn),滿二叉樹：每層的節(jié)點(diǎn)數(shù)都達(dá)到其最大值，i層上的節(jié)點(diǎn)數(shù)為2,i-1,二叉樹的遍歷,先序遍歷：先訪問根結(jié)點(diǎn),然后分別先序遍歷左子樹、右子樹,中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹,后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn),按層次遍歷：從上到下、從左到右訪問各結(jié)點(diǎn),-,+,/,a,*,b,-,e,f,c,d,查找,查找在某數(shù)據(jù)結(jié)構(gòu)中，找出滿足指定條件的元素,順序

5、查找,從線性表的第一個(gè)元素開始，逐一的將表中的每個(gè)元素與查找元素比較，若成功，便停止，若到表尾都未找出，查找失敗,若有n個(gè)元素，平均查找次數(shù)為n/2，時(shí)間復(fù)雜度為O(n)，一般用于無序表和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的查找,二分查找（折半查找）,要求查找的數(shù)據(jù)結(jié)構(gòu)必須是有序的順序結(jié)構(gòu)，對(duì)于元素個(gè)數(shù)為n的有序表，查找過程是：先找出中間元素，若匹配，查找成功；若比中間值大，則丟掉前半部分，在后半部繼續(xù)二分查找；若比中間值小，則丟掉后半部分，在前半部分繼續(xù)二分查找，時(shí)間復(fù)雜度為O(lon,2,n),比順序查找少。,排序,排序?qū)⒁粋€(gè)無序序列整理成按值非遞減排列的有序序列,方法很多，主要的方法有：,冒泡排序法：比較相鄰

6、元素，若逆序，則交換，O(n,2,),n(n-1)/2,快速排序法：指定一個(gè)K元素，HIGH從后向前掃描，遇見第一個(gè)小于K的元素，和K元素交換，接著LOW從前往后掃描，遇見第一個(gè)大于K的元素，和K交換，直到H和L相等，O(nlon,2,n),n,2,簡單插入排序法：將某一元素插入到前面已經(jīng)排好的有序子表中,O(n,2,),n(n-1)/2,希爾排序法：將元素分為若干組，組內(nèi)簡單插入排序，縮小分組，再繼續(xù)，直到一個(gè)元素一組,簡單選擇排序法：在元素中選擇最小的，和第一個(gè)元素交換，然后在剩下的n-1個(gè)元素中，重復(fù)此操作 O(n,2,),n(n-1)/2,排序效率的評(píng)估,很難說哪種排序是最好的，各種排

7、序方式都有自己的優(yōu)缺點(diǎn),考慮的因素有：元素個(gè)數(shù) n的長度；穩(wěn)定性要求；存儲(chǔ)輔助空間的大?。粩?shù)據(jù)元素本身的大小等等。,若n比較小，采用直接插入排序和選擇排序,若元素已經(jīng)基本有序，只有個(gè)別的逆序，采用簡單插入排序和冒泡排序,若n比較大，采用快速排序和堆排序,穩(wěn)定性：選擇排序、快速排序、希爾排序、堆排序不是穩(wěn)定的排序算法，而冒泡排序、插入排序、歸并排序和基數(shù)排序是穩(wěn)定的排序算法。,思考題目,下列敘述中正確的是,A,算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(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)

8、,下列對(duì)列的敘述正確的是,A,隊(duì)列屬于非線性表,B,隊(duì)列按“先進(jìn)后出”原則組織數(shù)據(jù),C,隊(duì)列在隊(duì)尾刪除數(shù)據(jù),D,隊(duì)列按“先進(jìn)先出”原則組織數(shù)據(jù),某二叉樹中有,n,個(gè)度為,2,的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)為,A,n+1 B,n-1 C,2n D,n/2,下列敘述中，不符合良好程序設(shè)計(jì)風(fēng)格要求的是,A,程序的效率第一，清晰第二,B,程序的可讀性好,C,程序中要有必要的注釋,D,輸入數(shù)據(jù)前要有提示信息,下列敘述中正確的是,A,程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān),B,程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu),C,程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量,D,以上三種說法都不對(duì),思考題目,下列敘述中正確的

9、是,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ì)語言中的數(shù)組一般是順序存儲(chǔ)結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu),D,以上三種說法都不對(duì),冒泡排序在最壞情況下的比較次數(shù)是,A,(n,1)/2 B,nlog2 n C,n(n,1)/2 D,/2,一棵二叉樹中共有,70,個(gè)葉子結(jié)點(diǎn)與,80,個(gè)度為,1,的結(jié)點(diǎn)，則該二叉樹中的總結(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í)

10、間是有限的,B,算法程序所處理的數(shù)據(jù)量是有限的,C,算法程序的長度是有限的,D,算法只能被有限的用戶使用,思考題目,對(duì)長度為,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è)棧的初始狀態(tài)為空?，F(xiàn)將元素,1,、,2,、,3,、,4,、,5,、,A,、,B,、,C,、,D,、,E,依次入棧，然后再依次出棧，則元素出棧的順序是,A,）,12345ABCDE B,）,EDCBA5432

11、1 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ì)尾指針共同決定,在長度為,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),二叉樹,D),棧,對(duì)如下所示的二叉樹進(jìn)行遍歷,A,B,C,D,E,F,G,