1 全國計算機等級考試

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

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

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

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

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

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

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

8、類型3線性鏈表的基本運算a在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素b在線性鏈表中刪除包含指定元素的結(jié)點c將二個線性鏈表按要求合并成一個線性鏈表d將一個線性鏈表按要求進行分解e逆轉(zhuǎn)線性鏈表f復制線性鏈表g線性鏈表的排序h線性鏈表的查找4循環(huán)鏈表及其基本運算循環(huán)鏈表是另一種形式的鏈式存儲結(jié)構(gòu)，與線性鏈表相比，具有以下二個特點a在循環(huán)鏈表中增加了一個表頭結(jié)點，其數(shù)據(jù)域為任消息的組成包括：（1）（2）（3）接收消息的對象的名稱消息標識符

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

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

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

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

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

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

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