計(jì)算機(jī)二級(jí)公共基礎(chǔ)及C語(yǔ)言結(jié)構(gòu)基礎(chǔ)

1、2011全國(guó)計(jì)算機(jī)等級(jí)二級(jí)公共基礎(chǔ)精講班第1講：課程介紹、算法特征講義前言公共基礎(chǔ)只是的考核方式是筆試，與程序設(shè)計(jì)語(yǔ)言的筆試部分組合成一張?jiān)嚲?，公共基礎(chǔ)占30分（選擇題10個(gè)和填空題5個(gè)）； 一、基本數(shù)據(jù)結(jié)構(gòu)與算法 1.算法概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度和空間復(fù)雜度）； 2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)的概念。 3.線(xiàn)性表的定義；線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算。 4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)及基本運(yùn)算； 5.線(xiàn)性單鏈表與循環(huán)鏈表的結(jié)構(gòu)及基本運(yùn)算； 6.樹(shù)的基本概念；二叉樹(shù)的定義及存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的前序、中序和后序遍歷；

2、7.順序查找與二分法算法；基本排序算法； 二、程序設(shè)計(jì)基礎(chǔ) 1.程序設(shè)計(jì)方法與風(fēng)格； 2.結(jié)構(gòu)化程序設(shè)計(jì)； 3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性； 三、軟件工程基礎(chǔ) 1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開(kāi)發(fā)環(huán)境； 2.結(jié)構(gòu)化的分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說(shuō)明書(shū)； 3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)； 4.軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試，集成測(cè)試和系統(tǒng)測(cè)試； 5.程序的調(diào)試，靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試。 四、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) 1.數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)； 2.數(shù)據(jù)模型，實(shí)體聯(lián)

3、系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型； 3.關(guān)系代數(shù)運(yùn)算，包含集合運(yùn)算及選擇，投影，連接等運(yùn)算； 4.數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。 第1章 數(shù)據(jù)結(jié)構(gòu)與算法1.1算法 1.1.1算法的基本概念 所謂算法是指解題方案的準(zhǔn)確而完整的描述。1.算法的基本特征作為一個(gè)算法，一般應(yīng)具有以下幾個(gè)基本特征。 （1）可行性（effectiveness） 算法在執(zhí)行過(guò)程中往往要受到計(jì)算工具的限制，使執(zhí)行結(jié)果產(chǎn)生偏差。 （2)確定件(definiteness） 算法的確定性，是指算法中的每一個(gè)步驟都必須是有明確定義的，不允許有模棱兩可的解釋?zhuān)膊辉试S有多義性。 (

4、3)有窮性(finiteness) 算法的有窮性，是指算法必須能在有限的時(shí)間內(nèi)做完，即算法必須能在執(zhí)行有限個(gè)步驟之后終止。 算法的有窮性還應(yīng)包括合理的執(zhí)行時(shí)間的含義。 (4)擁有足夠的情報(bào)一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會(huì)有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯(cuò)誤時(shí)，算法本身也就無(wú)法執(zhí)行或?qū)е聢?zhí)行有錯(cuò)。 綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。 2算法的基本要素 一個(gè)算法通常由兩種基本要素組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。(1)算法中對(duì)數(shù)據(jù)的運(yùn)算和操作 通常，計(jì)算機(jī)可以執(zhí)行的基

5、本操作是以指令的形式描述的。一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合，稱(chēng)為該計(jì)算機(jī)系統(tǒng)的指令系統(tǒng)。在一般的計(jì)算機(jī)系統(tǒng)中，基本的運(yùn)算和操作有以下四類(lèi)： 算術(shù)運(yùn)算：主要包括加、減、乘、除等運(yùn)算。 邏輯運(yùn)算：主要包括“與”、“或”、“非”等運(yùn)算。 關(guān)系運(yùn)算：主要包括“大于”、“小于”、“等于”、“不等于”等運(yùn)算。 數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。 (2)算法的控制結(jié)構(gòu) 算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅決定了算法中各操作的執(zhí)行順序，而且也直接反映了算法的設(shè)計(jì)是否符合結(jié)構(gòu)化原則。描述算法的工具通常有傳統(tǒng)流程圖、N-s結(jié)構(gòu)化流程圖、算法描述語(yǔ)言等。一個(gè)算法一般都可以用順序、選擇、循環(huán)三種基

6、本控制結(jié)構(gòu)組合而成。 3算法設(shè)計(jì)基本方法 工程上常用的幾中算法設(shè)計(jì)方法有： （1）列舉法 根據(jù)所需要解決的問(wèn)題，把所有可能的情況一一列舉出來(lái)，并用問(wèn)題中給定的條件來(lái)檢驗(yàn)?zāi)男┦切枰?，哪些是不需要? 通常用來(lái)解決“有多少種可能”等類(lèi)型的問(wèn)題。(不能解決無(wú)線(xiàn)復(fù)雜的問(wèn)題) (2)歸納法（從特殊到一般） 通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。（解決列舉量為無(wú)限的問(wèn)題） (3)遞推 從條件到結(jié)論，逐次推出所要求的各種中間結(jié)果和最終結(jié)果。 (4)遞歸 函數(shù)的自調(diào)用：將問(wèn)題逐層分解，最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題。 (5)減半遞推技術(shù) 所謂分治法，就是對(duì)問(wèn)題分而治之。工程上常用的分治法是減半遞

7、推技術(shù)。所謂“減半”，是指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變；所謂“遞推”，是指重復(fù)“減半”的過(guò)程。 (6)回溯法 通過(guò)對(duì)問(wèn)題的分析，出一個(gè)解決問(wèn)題的線(xiàn)索，然后沿著這個(gè)線(xiàn)索逐步試探，對(duì)于每一步的試探，若試探成功，就得到f題的解，若試探失敗，就逐步回退，換別的路線(xiàn)再進(jìn)行試探。這種方法稱(chēng)為回溯法?；厮莘ㄔ谔幚韽?fù)雜數(shù)據(jù)結(jié)構(gòu)方面有著廣泛的應(yīng)用。 算法復(fù)雜度112算法復(fù)雜度 算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。 1算法的時(shí)間復(fù)雜度 所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。 度量算法工作量時(shí)：排除計(jì)算機(jī)、語(yǔ)言、程序員、算法實(shí)現(xiàn)過(guò)程的細(xì)節(jié)影響。 用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)

8、來(lái)度量算法的工作量。 算法所執(zhí)行的基本運(yùn)算次數(shù)與問(wèn)題的規(guī)模有關(guān)。 綜上所述，算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)，即 算法的工作量=f(n) 其中n是問(wèn)題的規(guī)模。 在同一個(gè)問(wèn)題規(guī)模下，如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一特定輸入時(shí)，可以用以下兩種方法來(lái)分析算法的工作量。 (1)平均性態(tài)(AverageBehavior) 所謂平均性態(tài)分析，是指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量算法的工作量。 設(shè)x是所有可能輸入中的某個(gè)特定輸入，P(x)是x出現(xiàn)的概率(即輸入為x的概率)，t(x)是算法在輸入為x時(shí)所執(zhí)行的基本運(yùn)算次數(shù)，則算法的

9、平均性態(tài)定義為(2)最壞情況復(fù)雜性(Worst-CaseComplexity) 所謂最壞情況分析，是指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。它定義為顯然，W(n)的計(jì)算要比A(n)的計(jì)算方便得多。由于w(n)實(shí)際上是給出了算法工作量的一個(gè)上界，因此，它比A(n)更具有實(shí)用價(jià)值。 2算法的空間復(fù)雜度 一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。 一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間。2011全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言精講班第1講：C語(yǔ)言程序結(jié)構(gòu)講義二級(jí)C考試大綱一、2010年計(jì)算機(jī)等級(jí)考試二級(jí)C考

10、試大綱基本要求1.熟悉VisualC+6.0集成開(kāi)發(fā)環(huán)境。2.掌握結(jié)構(gòu)化程序設(shè)計(jì)的方法，具有良好的程序設(shè)計(jì)風(fēng)格。3.掌握程序設(shè)計(jì)中簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)和算法并能閱讀簡(jiǎn)單的程序。4.在VisualC+6.0集成環(huán)境下，能夠編寫(xiě)簡(jiǎn)單的C程序，并具有基本的糾錯(cuò)和調(diào)試程序的能力?？荚噧?nèi)容，如下表考試方式1.筆試：90分鐘，滿(mǎn)分100分，其中含公共基礎(chǔ)知識(shí)部分的30分。2.上機(jī)：90分鐘，滿(mǎn)分100分3.上機(jī)操作包括：（1）填空。（2）改錯(cuò)。（3）編程。二、最近3次二級(jí)C真題分析（考核內(nèi)容、題型及分?jǐn)?shù)分布）2010年3月二級(jí)C真題考核內(nèi)容、題型及分?jǐn)?shù)分布2009年9月二級(jí)C真題考核內(nèi)容、題型及分?jǐn)?shù)分布2009

11、年3月二級(jí)C真題考核內(nèi)容、題型及分?jǐn)?shù)分布考試要點(diǎn)總結(jié)三、第一章考核知識(shí)點(diǎn)分析 第1章 程序設(shè)計(jì)基本概念1.1程序和程序設(shè)計(jì)1.1.1C程序連續(xù)執(zhí)行的一條條指令的集合稱(chēng)為“程序”。計(jì)算機(jī)并不能直接識(shí)別由高級(jí)語(yǔ)言編寫(xiě)的程序，它只能接受和處理由0和1的代碼構(gòu)成的二進(jìn)制指令或數(shù)據(jù)。這種形式的指令稱(chēng)為“機(jī)器語(yǔ)言”。每條C語(yǔ)句，經(jīng)過(guò)編譯(Compile)最終都將轉(zhuǎn)換成二進(jìn)制的機(jī)器指令。由C語(yǔ)言構(gòu)成的指令序列稱(chēng)為C源程序。C源程序經(jīng)過(guò)C編譯程序編譯之后生成一個(gè)后綴為OBJ的二進(jìn)制文件(稱(chēng)為目標(biāo)文件)，然后由“連接程序”(Link)，把此OBJ文件與C語(yǔ)言提供的各種庫(kù)函數(shù)連接起來(lái)生成一個(gè)后綴為EXE的可執(zhí)行文

12、件。在操作系統(tǒng)環(huán)境下，只需點(diǎn)擊或輸入此文件的名字(而不必輸入后綴EXE)，該可執(zhí)行文件就可運(yùn)行。1.1.2程序設(shè)計(jì)簡(jiǎn)單的程序設(shè)計(jì)一般包含以下幾個(gè)部分：確定數(shù)據(jù)結(jié)構(gòu)、確定算法、編碼、在計(jì)算機(jī)上調(diào)試程序、整理并寫(xiě)出文檔資料?！纠}分析】（2007.4試題）下列敘述中錯(cuò)誤的是( D )A）計(jì)算機(jī)不能直接執(zhí)行用C語(yǔ)言編寫(xiě)的源程序B）C程序經(jīng)C編譯程序編譯后，生成后綴為.obj的文件是一個(gè)二進(jìn)制文件C）后綴為.obj的文件，經(jīng)連接程序生成后綴為.exe的文件是一個(gè)二進(jìn)制文件D）后綴為.obj和.exe的二進(jìn)制文件都可以直接運(yùn)行（2009.9試題）以下敘述中正確的是( D )A）程序設(shè)計(jì)的任務(wù)就是編寫(xiě)程序

13、代碼并上機(jī)調(diào)試B）程序設(shè)計(jì)的任務(wù)就是確定所用數(shù)據(jù)結(jié)構(gòu)C）程序設(shè)計(jì)的任務(wù)就是確定所用算法D）以上三種說(shuō)法都不完整1.2算法 學(xué)習(xí)計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的目的，是要用語(yǔ)言作為工具，設(shè)計(jì)出可供計(jì)算機(jī)運(yùn)行的程序。有了一個(gè)好的算法，就可以用任何一種計(jì)算機(jī)高級(jí)語(yǔ)言把算法轉(zhuǎn)換為程序 (編寫(xiě)程序)。算法是指為解決某個(gè)特定問(wèn)題而采取的確定且有限的步驟。一個(gè)算法應(yīng)當(dāng)具有以下五個(gè)特性：有窮性、確定性、可行性、有零個(gè)或多個(gè)輸入、有一個(gè) 或多個(gè)輸出。算法可以用各種描述方法來(lái)進(jìn)行描述，最常用的是偽代碼、流程圖和N-S流程圖。1.3結(jié)構(gòu)化程序設(shè)計(jì)和模塊結(jié)構(gòu)1.3.1結(jié)構(gòu)化程序結(jié)構(gòu)化程序由三種基本結(jié)構(gòu)組成：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循

14、環(huán)結(jié)構(gòu)。1.3.2模塊化結(jié)構(gòu) 當(dāng)計(jì)算機(jī)在處理較復(fù)雜的任務(wù)時(shí)常常把這個(gè)復(fù)雜的任務(wù)分解為若干個(gè)子任務(wù)，每個(gè)子任務(wù)又分成很多個(gè)小子任務(wù)，每個(gè)小子任務(wù)只完成一項(xiàng)簡(jiǎn)單的功能。在程序設(shè) 計(jì)時(shí)，用一個(gè)個(gè)小模塊來(lái)實(shí)現(xiàn)這些功能，每個(gè)程序設(shè)計(jì)人員分別完成一個(gè)或多個(gè)小模塊。我們稱(chēng)這樣的程序設(shè)計(jì)方法為“模塊化”的方法，由一個(gè)個(gè)功能模塊構(gòu)成的 程序結(jié)構(gòu)為模塊化結(jié)構(gòu)。在進(jìn)行程序設(shè)計(jì)時(shí)，首先應(yīng)當(dāng)集中考慮主程序中的算法，寫(xiě)出主程序后再動(dòng)手逐步完成子程序的調(diào)用。對(duì)于這些子程序也可用調(diào)試主程序的同樣方法逐步完成其下一層子程序的調(diào)用。這就是自頂向下、逐步細(xì)化、模塊化的程序設(shè)計(jì)方法。 c語(yǔ)言是一種結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言。它提供了三種基本

15、結(jié)構(gòu)的語(yǔ)句；提供了定義“函數(shù)”的功能，在c語(yǔ)言中沒(méi)有子程序的概念，它提供的函數(shù)可以完成子程序的 所有功能；C語(yǔ)言允許對(duì)函數(shù)單獨(dú)進(jìn)行編譯，從而可以實(shí)現(xiàn)模塊化。另外，c語(yǔ)言還提供了豐富的數(shù)據(jù)類(lèi)型。這些都為結(jié)構(gòu)化程序設(shè)計(jì)提供了有力的工具。 第一章補(bǔ)充知識(shí)點(diǎn)四、第一章補(bǔ)充知識(shí)點(diǎn)1、C語(yǔ)言由函數(shù)組成，有且僅有一個(gè)主函數(shù)-main()，一個(gè)程序總是從主函數(shù)開(kāi)始執(zhí)行；2、C語(yǔ)言的語(yǔ)句由“;”結(jié)束，書(shū)寫(xiě)格式自由，一行可寫(xiě)多個(gè)語(yǔ)句，一個(gè)語(yǔ)句可分多行書(shū)寫(xiě)；3、C程序是大小寫(xiě)敏感的（嚴(yán)格區(qū)分字母大小寫(xiě)）；【例題分析】（2010.3試題）以下敘述正確的是( B )A）C語(yǔ)言程序是由過(guò)程和函數(shù)組成的B）C語(yǔ)言函數(shù)可以嵌套調(diào)用的，例如：fun(fun(x)C）C語(yǔ)言函數(shù)不可以單獨(dú)編譯D）C語(yǔ)言中除了main函數(shù)，其他函數(shù)不可作為單獨(dú)文件形式存在（習(xí)題）以下說(shuō)法中正確的是( C )A)C語(yǔ)言程序總是從第一個(gè)定義的函數(shù)開(kāi)始執(zhí)行B)在C語(yǔ)言程序中，要調(diào)用的函數(shù)必須在main()函數(shù)中定義C)C語(yǔ)言程序總是從main()函數(shù)開(kāi)始執(zhí)行D)C語(yǔ)言程序中的main()函數(shù)必須放在程序的開(kāi)始部分4、C程序的文件擴(kuò)展名必須是.c；5、C語(yǔ)言的兩種注釋方式：/