【正文】 30 全國計算機二級VB知識點總結(jié)全國計算機等級考試—公共基礎(chǔ)知識部分復習簡綱在二級考試中公共基礎(chǔ)知識占30%,考察題型選擇填空，下面我就結(jié)合幾年考試原題，小結(jié)一下這一部分的考點。第一章 數(shù)據(jù)結(jié)構(gòu)與算法本章應(yīng)考重點：本章內(nèi)容在二級筆試中會出現(xiàn)5—6題，是公共基礎(chǔ)知識部分出題量比較多的一章，所占分值也比較大,約10分 算法1. 算法是指解題方案的準確而完整的描述。2. 算法的基本特征a可行性b確定性c有窮性d擁有足夠的情報3. 算法的復雜度a算法時間復雜度：是指執(zhí)行算法所需要的計算工作量，可以用執(zhí)行算法的過程中所需基本運算的執(zhí)行次數(shù)來度量b 算法的空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。 數(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) 1表示數(shù)據(jù)元素的信息 2 表示各數(shù)據(jù)元素之間的前后件關(guān)系 b 數(shù)據(jù)的存儲結(jié)構(gòu) 順序存儲 鏈接存儲 索引存儲 c 對各種數(shù)據(jù)結(jié)構(gòu)進行的運算3數(shù)據(jù)結(jié)構(gòu)的圖形表示 一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合點D中的每一個數(shù)據(jù)元素用中間標有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點，并簡稱結(jié)點：為了進以步表示數(shù)據(jù)元素之間的前后件關(guān)系，對于關(guān)系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)有樹，二叉樹，和圖等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 順序表的插入運算，插入結(jié)束后，線性表的長度增加了1，順序表的插入運算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。b 順序表的刪除運算，刪除結(jié)束后，線性表的長度減少了1，順序表的刪除運算時需要移動元素，在等概率情況下，平均需要移動（n1）/2個元素。插入刪除運算不方便1棧及其基本運算棧是限定在一端進行插入與刪除運算的線性表。棧是按照“先進后出”或“后進先出”的原則來組織數(shù)據(jù)的。棧具有記憶作用棧的基本運算 a入棧運算 b出棧運算 c讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化2隊列及其基本運算隊列是指允許在一端（隊尾）進行插入，一端（隊頭）進行刪除的線性表隊列是“先進先出”或“后進后出”的線性表隊列運算包括 a入隊運算 b出隊運算3循環(huán)隊列及其運算循環(huán)隊列的初始狀態(tài)為空，即rear=front=m循環(huán)隊列的基本運算分為入隊運算和退隊運算隊列空的條件：s=0隊列滿的條件：s=1 front=rear1線性表順序存儲缺點Data next左指針 數(shù)據(jù)域 右指針A插入或刪除的運算效率很低B線性表的順序存儲結(jié)構(gòu)下，線性表的存儲空間不便擴充C線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配2線性鏈表：線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表，是一種物理存儲單元上非連續(xù)，非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實現(xiàn)的。在鏈式存儲方式中每個結(jié)點由二部分組成：數(shù)據(jù)域，指針域線性鏈表分為單鏈表，雙向鏈表和循環(huán)鏈表三種類型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ù)域為任意或者根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點，循環(huán)鏈表的頭指向表頭結(jié)點。b 循環(huán)鏈表中最后一個結(jié)點的指針域不為空，而是指向表頭結(jié)點，即在循環(huán)表中，所有結(jié)點的指針構(gòu)成一個環(huán)狀鏈在對循環(huán)鏈表進行插入與刪除的過程中，實現(xiàn)了空表與非空表的運算統(tǒng)一 1樹的基本概念樹是一種簡單的非線性結(jié)構(gòu)。在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度2二叉樹及其基本性質(zhì)（1）什么是二叉樹二叉樹是一種很有用的非線性結(jié)構(gòu) a 非空二叉樹只有一個根結(jié)點 b 每個結(jié)點最多有二棵子樹，且分別稱為左子樹和右子樹二叉樹的度可以是0，1，2（2）二叉樹的基本性質(zhì)性質(zhì)1 在二叉樹的第k層上，最多有2k1（k=1）個結(jié)點性質(zhì)2 深度為m的二叉樹最多有2m1個結(jié)點性質(zhì)3 在任意一棵二叉樹中度數(shù)為0的結(jié)點總比度為2的結(jié)點多一個性質(zhì)4 具有n個結(jié)點的二叉樹，其深度至少為[ log2n ]表示取log2n的整數(shù)部分3滿二叉樹：除最后一層外，每層上的所有結(jié)點都有二個子結(jié)點 完全二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結(jié)點4 二叉樹的存儲結(jié)構(gòu)，二叉樹通常采用鏈式存儲結(jié)構(gòu)5 二叉樹的遍歷（1）前序遍歷（DLR）根左右（2）中序遍歷（LDR）左根右（3）后序遍歷（LRD）左右根1順序查找2二分法查找類別排序方法基本思想時間復雜度交換類冒泡排序相鄰元素比較，不滿足條件交換n(n1)/2快速排序選擇基準元素，通過交換，劃分成二個子序列O(nlog2n)插入類簡單插入排序待排序的元素看成為一個有序表和無序表，將無序表中元素插入到有序表中n(n1)/2希爾排序分割成若干個子序列分別進行直接插入排序O()選擇類簡單選擇排序掃描整個線性表，從中選出最小的元素，將他交換到表的最前面n(n1)/2堆排序選建堆，然后建堆頂元素與堆中最后一個元素交換，再調(diào)整為堆O(nlog2n)第二章 程序設(shè)計基礎(chǔ)本章在考試中會出現(xiàn)一題左右，所占分值大約占2分，是出題量較小的一章。本章內(nèi)容較少，所以大家盡量不要失分??！這樣會比較可惜。程序設(shè)計的風格主要強調(diào)：“清晰第一，效率第二”（1） 源程序文檔化符號名的命名。符號名能反映它所代表的實際東西，應(yīng)有一定的實際含義程序的注釋，分為序言性注釋和功能性注釋視覺組織（2） 數(shù)據(jù)說明數(shù)據(jù)說明的次序規(guī)范化說明語句中變量安排有序化使用注釋來說明復雜數(shù)據(jù)的結(jié)構(gòu)（3） 語句的結(jié)構(gòu)（4） 輸入和輸出注意點信息隱蔽是指采用封裝技術(shù)，將程序模塊的實施細節(jié)隱藏起來，使模塊接口盡量簡單。即指在設(shè)計和確定模塊時，使得一個模塊的內(nèi)包含的信息（過程或數(shù)據(jù)），對于不需要這些信息的其他模塊來說，是不能訪問的。（面向過程的程序設(shè)計方法）a 自頂而下b 逐步求精c 模塊化d 限制使用 goto 語句：順序結(jié)構(gòu)，選擇結(jié)構(gòu)（分支結(jié)構(gòu)），重復結(jié)構(gòu)（循環(huán)結(jié)構(gòu)）面向?qū)ο蠓椒ǖ谋举|(zhì)就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡人們在現(xiàn)實生活中常用的思維來認識，理解和描述客觀事物，強調(diào)最終建立的系統(tǒng)能夠映射問題域。面向?qū)ο蠓椒ǖ闹饕獌?yōu)點（1） 與人類習慣的思維方法一致（2） 穩(wěn)定性好（3） 可重用性好（4） 易于開發(fā)大型軟件產(chǎn)品（5） 可維護性好.【注意】面向?qū)ο蟮某绦蛟O(shè)計主要考慮的是提高軟件的的可重用性對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，對象是屬性和方法的封裝體屬性即對象所包含的信息，它在設(shè)計對象時確定，一般只能通過執(zhí)行對象的操作來改變操作描述了對象執(zhí)行的功能，操作也稱為方法或服務(wù)。操作是對象的動態(tài)屬性。一個對象由對象名，屬性和操作三個部分組成對象的基本特點:標識唯一性，分類性，多態(tài)性，封裝性，模塊獨立性好類是指具有共同屬性，共同屬性，共同方法的對象的集合。所有類是對象的抽象，對象是對應(yīng)類的一個實例消息是一個實例與另一個實例之間傳遞的信息。消息的組成包括：（1） 接收消息的對象的名稱（2） 消息標識符也稱消息名（3） 零個或多個參數(shù)繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復定義他們多態(tài)性是對象根據(jù)所接受的消息而做出動作，同樣的消息被不同的對象接受時可導致完全不同的行動。在面向?qū)ο蠹夹g(shù)中，多態(tài)性是指子類對象可以像父類對象那樣使用，同樣的消息可以發(fā)送給父類對象也可以發(fā)送給子類對象。多態(tài)性機制增加了面向?qū)ο筌浖到y(tǒng)的靈活性，減少了信息的，而且顯著提高了軟件的可重用性可擴充性。第三章 軟件工程基礎(chǔ)本章應(yīng)考點撥：本章在筆試中一般占8分左右，約3道選擇題，1道填空題，是公共基礎(chǔ)部分比較重要的一章。本章主要考察對基本概念的識記，有少量對基本原理的理解，沒有實際運用，因此在復習本章時，重點應(yīng)放在基本概念的記憶和基本原理的理解。1軟件的相關(guān)概念計算機軟件是包括程序，數(shù)據(jù)及相關(guān)文檔的完整集合軟件的特點包括（1） 軟件是一種邏輯實體，而不是物理實體，具有抽象性（2） 軟件的生產(chǎn)與硬件不同，他沒有明顯的制作過程（3） 軟件在運行，使用期間不存在磨損和老化問題（4） 軟件的開發(fā)，運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制，這導致了軟件移植的問題（5） 軟件復雜性高，成本昂貴（6） 軟件開發(fā)涉及諸多的社會因素2軟件危機與軟件工程軟件工程源于軟件危機軟件危機表現(xiàn)為（1） 軟件需求的增長得不到滿足（2） 軟件開發(fā)成本和進度無法控制（3） 軟件質(zhì)量難以保證（4） 軟件不可維護或維護程度非常低（5） 軟件的成本不斷提高（6） 軟件開發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長總之可以將軟件危機歸結(jié)為成本，質(zhì)量，生產(chǎn)率等問題軟件工程（1） 軟件開發(fā)技術(shù)（2） 軟件工程管理軟件工程的主要思想是將工程化原則運用到軟件開發(fā)過程，他包括3個要素：方法，工具，過程軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動3軟件的生命周期軟件生命周期：軟件產(chǎn)品從提出，實現(xiàn)，使用維護到停止使用退役的過程。生命周期分為軟件定義，軟件開發(fā)，軟件運行維護三個階段（1） 軟件定義階段：包括制定計劃和需求分析（2） 軟件開發(fā)階段：軟件設(shè)計（概要設(shè)計，詳細設(shè)計），軟件實現(xiàn)，軟件測試（3） 軟件運行維護階段：軟件生命周期中所花費最多的階段4軟件工程的目標和原則（1） 軟件工程目標：在給定成本，進度的前提下，開發(fā)出具有有效性，可靠性，可理解性，可維護性，可重用性，可適應(yīng)性，可移植性，可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品（2） 軟件工程需要達到的基本目標是：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件的軟件性能；開發(fā)的軟件易于移植；需要較低的維護費用；能按時完成開發(fā)，及時交付使用（3） 軟件工程的原則：抽象，信息隱蔽，模塊化，局部化，確定性，一致性，完備性和可驗證性。5軟件開發(fā)工具與軟件開發(fā)環(huán)境（1） 軟件開發(fā)工具（2） 軟件開發(fā)環(huán)境軟件開發(fā)環(huán)境（或稱軟件工程環(huán)境）是全面支持軟件開發(fā)全過程的軟件工具的集合結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計理論1需求分析需求方法方法有（1） 結(jié)構(gòu)化需求分析方法（2） 面向?qū)ο蟮姆治龇椒ā菊f明】需求分析的任務(wù)就是導出目標系統(tǒng)的邏輯模型需求分析一般分為需求獲取，需求分析，編寫需求規(guī)格說明書和需求評審2結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計理論在軟件需求分析階段的應(yīng)用結(jié)構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流，自頂而下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工具 a數(shù)據(jù)流圖（DFD） 基本圖形要素：加工（轉(zhuǎn)換），數(shù)據(jù)流，存儲文件，源潭 畫數(shù)據(jù)流圖的基本步驟：自外向內(nèi)，自頂向下，逐層細化，完善求精b數(shù)據(jù)字典（DD） 數(shù)據(jù)字典的作用是對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋 數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心c判定樹d判定表3軟件需求規(guī)格說明書（SRS）軟件需求規(guī)格說明書是需求分析階段的最后成果，通過建立完整的信息描述，詳細的功能和行為描述，性能需求和設(shè)計約束的說明，合適的驗收標準，給出對目標軟件的各種需求。1軟件設(shè)計的基礎(chǔ)軟件設(shè)計包括軟件結(jié)構(gòu)設(shè)計，數(shù)據(jù)設(shè)計，接口設(shè)計，過程設(shè)計從工程角度來看，軟件設(shè)計分成二步完成，概要設(shè)計和詳細設(shè)計軟件設(shè)計的基本原理包括：抽象，模塊化，信息隱蔽和模塊獨立性【注意】模塊分解的主要指導思想是信息隱蔽和模塊獨立性模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨立性的二個定性指標【注意】一個設(shè)計良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚，低耦合的特征在結(jié)構(gòu)化程序設(shè)計中，模塊劃分的原則是：模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦合度2總體設(shè)計（概要設(shè)計）和詳細設(shè)計（1） 總體設(shè)計（概要設(shè)