1 全國(guó)計(jì)算機(jī)等級(jí)考試

1、1全國(guó)計(jì)算機(jī)等級(jí)考試—全國(guó)計(jì)算機(jī)等級(jí)考試—公共基礎(chǔ)知識(shí)部分復(fù)習(xí)簡(jiǎn)綱全國(guó)計(jì)算機(jī)全國(guó)計(jì)算機(jī)二級(jí)二級(jí)VB復(fù)習(xí)知識(shí)點(diǎn)知識(shí)點(diǎn)綱要在二級(jí)考試中公共基礎(chǔ)知識(shí)占30%考察題型選擇填空，下面我就結(jié)合幾年考試原題，小結(jié)一下這一部分的考點(diǎn)。第一章數(shù)據(jù)結(jié)構(gòu)與算法本章應(yīng)考重點(diǎn)：本章內(nèi)容在二級(jí)筆試中會(huì)出現(xiàn)5—6題，是公共基礎(chǔ)知識(shí)部分出題量比較多的一章，所占分值也比較大約10分1.1算法1.2.算法是指解題方案的準(zhǔn)確而完整的描述。算法的基本特征a可行性b確定性c有窮

2、性d擁有足夠的情報(bào)3.算法的復(fù)雜度a算法時(shí)間復(fù)雜度：是指執(zhí)行算法所需要的計(jì)算工作量，可以用執(zhí)行算法的過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量b算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1數(shù)據(jù)結(jié)構(gòu)是指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合2數(shù)據(jù)結(jié)構(gòu)a數(shù)據(jù)的邏輯結(jié)構(gòu)b數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)1表示數(shù)據(jù)元素的信息2表示各數(shù)據(jù)元素之間的前后件關(guān)系順序存儲(chǔ)鏈接存儲(chǔ)索引存儲(chǔ)c對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算3數(shù)據(jù)結(jié)構(gòu)的圖形表示一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系

3、外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對(duì)于數(shù)據(jù)集合點(diǎn)D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱(chēng)之為數(shù)據(jù)結(jié)點(diǎn)，并簡(jiǎn)稱(chēng)結(jié)點(diǎn)：為了進(jìn)以步表示數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線(xiàn)段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。4數(shù)據(jù)結(jié)構(gòu)分為二大類(lèi)線(xiàn)性結(jié)構(gòu)a有且只有一個(gè)根結(jié)點(diǎn)b每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件常見(jiàn)的線(xiàn)性結(jié)構(gòu)有線(xiàn)性表，隊(duì)列，線(xiàn)性鏈表，棧非線(xiàn)性結(jié)構(gòu)不滿(mǎn)足線(xiàn)性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)常見(jiàn)的非線(xiàn)性結(jié)構(gòu)有

4、樹(shù)，二叉樹(shù)，和圖等1.3線(xiàn)性表及其順序存儲(chǔ)結(jié)構(gòu)1線(xiàn)性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線(xiàn)性的。表中的每個(gè)數(shù)據(jù)元素，除了第一個(gè)外，由且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。線(xiàn)性表中數(shù)據(jù)元素的個(gè)數(shù)稱(chēng)為線(xiàn)性表的長(zhǎng)度。線(xiàn)性表可以是空表2線(xiàn)性表是一種存儲(chǔ)結(jié)構(gòu)順序結(jié)構(gòu)a線(xiàn)性表中所有元素所占的存儲(chǔ)空間是連續(xù)的b線(xiàn)性表中個(gè)數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的鏈?zhǔn)浇Y(jié)構(gòu)3順序表的插入，刪除運(yùn)算a順序

5、表的插入運(yùn)算，插入結(jié)束后，線(xiàn)性表的長(zhǎng)度增加了1，順序表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)n2個(gè)元素。b順序表的刪除運(yùn)算，刪除結(jié)束后，線(xiàn)性表的長(zhǎng)度減少了1，順序表的刪除運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)（n1）2個(gè)元素。插入刪除運(yùn)算不方便1.4棧和隊(duì)列1棧及其基本運(yùn)算棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線(xiàn)性表。棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則來(lái)組織數(shù)據(jù)的。棧具有記憶作用棧的基本運(yùn)算a入棧運(yùn)算b出棧運(yùn)

6、算c讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化2隊(duì)列及其基本運(yùn)算隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)行插入，一端（隊(duì)頭）進(jìn)行刪除的線(xiàn)性表隊(duì)列是“先進(jìn)先出”或“后進(jìn)后出”的線(xiàn)性表隊(duì)列運(yùn)算包括a入隊(duì)運(yùn)算b出隊(duì)運(yùn)算醉石居主人私有物23循環(huán)隊(duì)列及其運(yùn)算循環(huán)隊(duì)列的初始狀態(tài)為空，即rear=front=m循環(huán)隊(duì)列的基本運(yùn)算分為入隊(duì)運(yùn)算和退隊(duì)運(yùn)算隊(duì)列空的條件：s=0隊(duì)列滿(mǎn)的條件：s=1front=rear1.5線(xiàn)性鏈表1線(xiàn)性表順序存儲(chǔ)缺點(diǎn)A插入

7、或刪除的運(yùn)算效率很低B線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)下，線(xiàn)性表的存儲(chǔ)空間不便擴(kuò)充C線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配全國(guó)計(jì)算機(jī)二級(jí)全國(guó)計(jì)算機(jī)二級(jí)VB復(fù)習(xí)知識(shí)點(diǎn)知識(shí)點(diǎn)綱要Datanext左指針數(shù)據(jù)域右指針2線(xiàn)性鏈表：線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線(xiàn)性鏈表，是一種物理存儲(chǔ)單元上非連續(xù)，非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接來(lái)實(shí)現(xiàn)的。在鏈?zhǔn)酱鎯?chǔ)方式中每個(gè)結(jié)點(diǎn)由二部分組成：數(shù)據(jù)域，指針域線(xiàn)性鏈表分為單鏈表，雙向鏈表和循環(huán)鏈表三種

8、類(lèi)型3線(xiàn)性鏈表的基本運(yùn)算a在線(xiàn)性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素b在線(xiàn)性鏈表中刪除包含指定元素的結(jié)點(diǎn)c將二個(gè)線(xiàn)性鏈表按要求合并成一個(gè)線(xiàn)性鏈表d將一個(gè)線(xiàn)性鏈表按要求進(jìn)行分解e逆轉(zhuǎn)線(xiàn)性鏈表f復(fù)制線(xiàn)性鏈表g線(xiàn)性鏈表的排序h線(xiàn)性鏈表的查找4循環(huán)鏈表及其基本運(yùn)算循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，與線(xiàn)性鏈表相比，具有以下二個(gè)特點(diǎn)a在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿蜗⒌慕M成包括：（1）（2）（3）接收消息的對(duì)象的名稱(chēng)消息標(biāo)識(shí)符

9、也稱(chēng)消息名零個(gè)或多個(gè)參數(shù)繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們多態(tài)性是對(duì)象根據(jù)所接受的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)。在面向?qū)ο蠹夹g(shù)中，多態(tài)性是指子類(lèi)對(duì)象可以像父類(lèi)對(duì)象那樣使用，同樣的消息可以發(fā)送給父類(lèi)對(duì)象也可以發(fā)送給子類(lèi)對(duì)象。多態(tài)性機(jī)制增加了面向?qū)ο筌浖到y(tǒng)的靈活性，減少了信息的，而且顯著提高了軟件的可重用性可擴(kuò)充性。第三章軟件工程基礎(chǔ)本章應(yīng)考點(diǎn)撥：本章在筆試中一般占8分左右，約3道

10、選擇題，1道填空題，是公共基礎(chǔ)部分比較重要的一章。本章主要考察對(duì)基本概念的識(shí)記，有少量對(duì)基本原理的理解，沒(méi)有實(shí)際運(yùn)用，因此在復(fù)習(xí)本章時(shí)，重點(diǎn)應(yīng)放在基本概念的記憶和基本原理的理解。3.1軟件工程基本概念1軟件的相關(guān)概念計(jì)算機(jī)軟件是包括程序，數(shù)據(jù)及相關(guān)文檔的完整集合軟件的特點(diǎn)包括（1）（2）（3）（4）（5）（6）軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具有抽象性軟件的生產(chǎn)與硬件不同，他沒(méi)有明顯的制作過(guò)程軟件在運(yùn)行，使用期間不存在磨損和老化問(wèn)題

11、軟件的開(kāi)發(fā)，運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴(lài)性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問(wèn)題軟件復(fù)雜性高，成本昂貴軟件開(kāi)發(fā)涉及諸多的社會(huì)因素2軟件危機(jī)與軟件工程軟件工程源于軟件危機(jī)軟件危機(jī)表現(xiàn)為（1）（2）（3）（4）（5）（6）軟件工程（1）（2）軟件開(kāi)發(fā)技術(shù)軟件工程管理軟件需求的增長(zhǎng)得不到滿(mǎn)足軟件開(kāi)發(fā)成本和進(jìn)度無(wú)法控制軟件質(zhì)量難以保證軟件不可維護(hù)或維護(hù)程度非常低軟件的成本不斷提高軟件開(kāi)發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)總之可以將軟

12、件危機(jī)歸結(jié)為成本，質(zhì)量，生產(chǎn)率等問(wèn)題軟件工程的主要思想是將工程化原則運(yùn)用到軟件開(kāi)發(fā)過(guò)程，他包括3個(gè)要素：方法，工具，過(guò)程軟件工程過(guò)程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)3軟件的生命周期軟件生命周期：軟件產(chǎn)品從提出，實(shí)現(xiàn)，使用維護(hù)到停止使用退役的過(guò)程。生命周期分為軟件定義，軟件開(kāi)發(fā)，軟件運(yùn)行維護(hù)三個(gè)階段（1）（2）（3）軟件定義階段：包括制定計(jì)劃和需求分析軟件開(kāi)發(fā)階段：軟件設(shè)計(jì)（概要設(shè)計(jì)，詳細(xì)設(shè)計(jì)），軟件實(shí)現(xiàn)，軟件測(cè)試軟件運(yùn)行維護(hù)

13、階段：軟件生命周期中所花費(fèi)最多的階段醉石居主人私有物54軟件工程的目標(biāo)和原則（1）（2）（3）（1）（2）全國(guó)計(jì)算機(jī)二級(jí)全國(guó)計(jì)算機(jī)二級(jí)VB復(fù)習(xí)知識(shí)點(diǎn)知識(shí)點(diǎn)綱要軟件工程目標(biāo)：在給定成本，進(jìn)度的前提下，開(kāi)發(fā)出具有有效性，可靠性，可理解性，可維護(hù)性，可重用性，可適應(yīng)性，可移植性，可追蹤性和可互操作性且滿(mǎn)足用戶(hù)需求的產(chǎn)品軟件工程需要達(dá)到的基本目標(biāo)是：付出較低的開(kāi)發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟件的軟件性能；開(kāi)發(fā)的軟件易于移植；需要較低的

14、維護(hù)費(fèi)用；能按時(shí)完成開(kāi)發(fā)，及時(shí)交付使用軟件工程的原則：抽象，信息隱蔽，模塊化，局部化，確定性，一致性，完備性和可驗(yàn)證性。軟件開(kāi)發(fā)工具軟件開(kāi)發(fā)環(huán)境3.2結(jié)構(gòu)化分析方法5軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境軟件開(kāi)發(fā)環(huán)境（或稱(chēng)軟件工程環(huán)境）是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具的集合結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論1需求分析需求方法方法有（1）（2）【說(shuō)明】1○需求分析的任務(wù)就是導(dǎo)出目標(biāo)系統(tǒng)的邏輯模型2○需求分析一般分為需求獲取，需求分析，編寫(xiě)需

15、求規(guī)格說(shuō)明書(shū)和需求評(píng)審2結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的應(yīng)用結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流，自頂而下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工具a數(shù)據(jù)流圖（DFD）b數(shù)據(jù)字典（DD）c判定樹(shù)d判定表3軟件需求規(guī)格說(shuō)明書(shū)（SRS）軟件需求規(guī)格說(shuō)明書(shū)是需求分析階段的最后成果，通過(guò)建立完整的信息描述，詳細(xì)的功能和行為描述，性能需求和設(shè)計(jì)約束的說(shuō)明，合適的驗(yàn)收