全國計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)點(diǎn)總結(jié)

1、秋風(fēng)清，秋月明,落葉聚還散,寒鴉棲復(fù)驚。1、 算法是指解決方案的準(zhǔn)確而完整的描述2、 算法的四個(gè)基本特性： 可行性 確定性 有窮性 擁有足夠的情報(bào)3、 算法有兩個(gè)基本的要素組成： 一、數(shù)據(jù)對(duì)象的運(yùn)算和操作 二、算法的控制結(jié)構(gòu)4、 計(jì)算機(jī)中的基本操作 算術(shù)運(yùn)算 邏輯運(yùn)算 關(guān)系運(yùn)算 數(shù)據(jù)運(yùn)算5、 算法的控制結(jié)構(gòu)給出了算法的基本框架，不僅決定了算法中各操作的執(zhí)行順序，而且也直接反應(yīng)了算法的設(shè)計(jì)是否符合結(jié)構(gòu)化的原則。一個(gè)算法都可以用順序、選擇、循環(huán)3鐘基本控制結(jié)構(gòu)組成6、 算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度7、 算法的時(shí)間復(fù)雜度是執(zhí)行算法所需要的計(jì)算工作量。 他不僅應(yīng)該與使用的計(jì)算機(jī)、程序設(shè)計(jì)

2、語言及程序編制者無關(guān)，而且應(yīng)該與算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)無關(guān)。8、 算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。9、 如果一個(gè)數(shù)據(jù)結(jié)構(gòu)中沒有一個(gè)數(shù)據(jù)元素，則稱該數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu)。10、 根據(jù)數(shù)據(jù)結(jié)構(gòu)中個(gè)數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu)11、 如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足 1、有且只有一個(gè)根結(jié)點(diǎn)； 2、 每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件，則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。12、 在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還是線性結(jié)構(gòu)。13、 在計(jì)算機(jī)中存放線性表，一種最簡單的方法是順序存儲(chǔ)。、14、 線性表的順序存儲(chǔ)結(jié)構(gòu)

3、具有兩個(gè)基本的特點(diǎn)：一、線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的。二、線性表中各數(shù)據(jù)在存儲(chǔ)空間中是按邏輯順序依次存放的。15、 線性表的插入運(yùn)算和刪除運(yùn)算 P.8-916、 棧是一種特殊的線性表，其插入和刪除只能在表的一端進(jìn)行。17、 在棧中允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的一端稱為棧底，棧的修改原則是先進(jìn)后出或后進(jìn)先出。18、 入棧運(yùn)算： 1、首先將棧頂指針進(jìn)1，然后將新元素入到棧頂指針指向的位置。19、 退棧預(yù)算：首先將棧頂元素賦予一個(gè)指定的變量，然后將棧頂指針退1。20、 隊(duì)列：是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表，允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為排

4、頭。隊(duì)列又稱 先進(jìn)先出 或 后進(jìn)后出的線性表，體現(xiàn)了“先來先服務(wù)的原則”21、 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。即 將隊(duì)列的存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供列隊(duì)循環(huán)使用。22、 線性表的順序存儲(chǔ)結(jié)構(gòu)具有簡單、運(yùn)算方便等優(yōu)點(diǎn)。但是對(duì)于大的線性表，特別是元素變動(dòng)頻繁的大線性表不宜采用順序的存儲(chǔ)結(jié)構(gòu)，二是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)23、 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，要求每個(gè)結(jié)點(diǎn)有兩部分組成： 一 用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域。 另一部分用于存放指針，稱為指針域。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)。24、 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)之間

5、的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。鏈?zhǔn)酱鎯?chǔ)方式既可以用于表示線性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)25、 線性鏈表： 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。26、 樹： 樹是一種簡單的非線性結(jié)構(gòu)。在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前結(jié)點(diǎn)的只有1個(gè)，稱為根結(jié)點(diǎn)，簡稱為樹的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，他們都稱為子結(jié)點(diǎn)。27、 二叉樹是一種重要的非線性結(jié)構(gòu)。二叉樹具有兩個(gè)特點(diǎn)： 非空二叉樹只有一個(gè)根結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)最多有兩顆子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。28、 在二叉樹的第K層上，最多有2k-1（k>=1）個(gè)結(jié)點(diǎn)29、 深度為M 的二叉樹最多有2

6、M-1個(gè)結(jié)點(diǎn)。深度為M 的二叉樹是指二叉樹共有M 層。30、 在任意一顆二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)。31、 具有N個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為log2n+1,32、 滿二叉樹，除了最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的二叉樹為滿二叉樹。即深度為K 的滿二叉樹，其第K層上有2k-1個(gè)結(jié)點(diǎn)，且深度為M 的滿二叉樹共有2M-1個(gè)結(jié)點(diǎn)。33、 在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。與線性鏈表類似，用于存儲(chǔ)二叉樹中各元素的存儲(chǔ)結(jié)點(diǎn)也有兩部分組成：數(shù)據(jù)域和指針域。34、 二叉樹的遍歷可以分為三種： 前序遍歷 中序遍歷 后序遍歷35、 前序遍歷： 首先訪問根結(jié)點(diǎn)，然

7、后遍歷左子樹，最后遍歷右子樹。36、 中序遍歷：首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。37、 后序遍歷：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。38、 順序查找：又稱順序搜索，一般指在線性表中查找指定元素。對(duì)于大的線性表來說，順序查找效率很低。但在以下兩種情況只能用順序查找： 1、如果線性表是無序的（即表中的元素是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能順序查找。2、即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。39、 二分法查找: 二分法查找只能用于順序存儲(chǔ)的有序表。對(duì)于長度為N 的有序線性表，在最壞的情況下，二分查找只需要比較log2n次，而順序

8、查找則需要比較N 次。40、 交換類排序法：是指借助數(shù)據(jù)元素之間的相互交換進(jìn)行排序的一種方法。包括 冒泡排序法和 快速排序法。41、 冒泡排序法：一種最簡單的交換類排序方法，它是通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序。假設(shè)線性表的長度為N,則在最壞的情況下，冒泡排序需要經(jīng)過N/2遍從前往后的掃描和N/2遍從后往前的掃描，需要的比較次數(shù)為n(n-1)/2.但一般情況下要小于這個(gè)工作量。42、 快速排序法：是一種交換類的排序方法，但由于它比冒泡排序法的速度快，因此稱為快速排序法。43、 插入類排序法 包括 簡單插入類排序法 希爾排序法 44、 簡單插入排序法的效率與冒泡排序法相同。在最壞的情況

9、下需要n(n-1)/2 次比較45、 希爾排序的效率與所選取的增量序列有關(guān)。在最壞的情況下，希爾排序所需要的比較次數(shù)為 O(n1.5)46、 選擇類排序法 包括 簡單選擇排序法 和 堆排序法47、 簡單排序法在最壞的情況下需要比較N(n-1)/2次48、 堆排序法在最壞情況下需要比較O(nlog2n)49、 就程序設(shè)計(jì)方法和技術(shù)的發(fā)展而言，主要經(jīng)過了結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)兩個(gè)階段。50、 面向?qū)ο笤O(shè)計(jì)的主要優(yōu)點(diǎn)是：與人類習(xí)慣的思維方法一致；穩(wěn)定性好；可重用性好；易于開發(fā)大型軟件產(chǎn)品；可維護(hù)性好。51、 清晰第一，效率第二 的論點(diǎn)已經(jīng)成為當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格。52、 結(jié)構(gòu)化程序?qū)嶋H

10、方法的主要原則為自頂向下，逐步求精，模塊化，限制使用GOTO語句53、 結(jié)構(gòu)化程序語言僅使用順序、選擇、重復(fù)3鐘基本控制結(jié)構(gòu)就足以表達(dá)出各種其他形式的程序設(shè)計(jì)方法。54、 順序就夠是一種簡單的程序設(shè)計(jì)結(jié)構(gòu)，它是最基本、最常用的結(jié)構(gòu)。55、 選擇結(jié)構(gòu)又稱為分支結(jié)構(gòu)，它包括簡單選擇結(jié)構(gòu)和分支選擇結(jié)構(gòu)。56、 重復(fù)結(jié)構(gòu)又稱為循環(huán)結(jié)構(gòu)。在程序設(shè)計(jì)語言中，重復(fù)結(jié)構(gòu)對(duì)應(yīng)兩類循環(huán)語句，對(duì)先判斷后執(zhí)行循環(huán)體的稱為當(dāng)型循環(huán)結(jié)構(gòu)。對(duì)先執(zhí)行循環(huán)體后判斷的稱為直到型循環(huán)結(jié)構(gòu)。即直到型循環(huán)至少執(zhí)行一次運(yùn)算。57、 遵循結(jié)構(gòu)化程序的設(shè)計(jì)原則，按結(jié)構(gòu)化程序設(shè)計(jì)方法設(shè)計(jì)出的程序具有明顯的特點(diǎn)。一、程序結(jié)構(gòu)良好、易讀、易理解、

11、易維護(hù)。二、可以提高編程工作的效率，降低軟件開發(fā)成本。58、 對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜酶拍?。?duì)象具有以下的一些基本特點(diǎn)：1、標(biāo)識(shí)的唯一性。2、分類性。3、多態(tài)性。、4、封裝性。5、模塊獨(dú)立性好。59、 類：將屬性、操作相似的對(duì)象歸為類。即類是具有共同屬性、共同方法的對(duì)象的集合。60、 消息：一個(gè)消息有三部分組成：1、接受消息的對(duì)象名稱、2、消息標(biāo)識(shí)符3、零個(gè)或多個(gè)參數(shù)。61、 在面向?qū)ο蠓椒ㄖ?，?shí)現(xiàn)信息隱蔽是依靠對(duì)象的封裝。62、 程序中添加的必要注釋：程序的代碼要層次分明，清晰明了，滿足視覺要求。注釋一般分為序言性注釋和功能性注釋。序言性注釋通常位于程序的開頭部分，他給出了程序的整體說明

12、。功能性注釋一般嵌在源程序體之中，主要描述其后的語句或程序。63、 從程序行文角度，編寫程序源代碼應(yīng)該注意 源程序文檔化、程序的語句結(jié)構(gòu)、數(shù)據(jù)的說明和輸入輸出等方面的要求。64、 衡量模塊的獨(dú)立程度使用耦合性和內(nèi)聚性兩個(gè)度量標(biāo)準(zhǔn)。模塊的內(nèi)聚程度越高越獨(dú)立，耦合程序越低越獨(dú)立。65、 繼承性是面向?qū)ο蟮姆椒ǖ囊粋€(gè)主要特性。繼承是使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。已有的類可以當(dāng)作基類來引用，新類相應(yīng)的可當(dāng)做派生類來引用。這種層次結(jié)構(gòu)系統(tǒng)的一個(gè)重要性質(zhì)是繼承性，一個(gè)類直接繼承其父類的描述或特性，子類自動(dòng)的共享基類中定義的數(shù)據(jù)和方法。66、 通常，將軟件產(chǎn)品從提出、實(shí)行、使用維護(hù)到停止使用退

13、役的過程稱為軟件的生命周期。軟件生存期一般包括可行性研究與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測試、交付使用以及維護(hù)等活動(dòng)。67、 軟件工程的概念出現(xiàn)源自 軟件危機(jī)。 而軟件危機(jī)歸結(jié)為成本、質(zhì)量、生產(chǎn)率的問題。68、 軟件工程是建立并使用完善的工程化原則。軟件工程主要包括3個(gè)要素：方法、工具、過程。69、 軟件工程的核心思想是把軟件產(chǎn)品看做是一個(gè)工程產(chǎn)品來處理。70、 軟件工程的原則： 抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。71、 結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的運(yùn)用。72、 結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流、自頂向下、逐層分解、建立系統(tǒng)的流程。以數(shù)據(jù)流圖

14、和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。73、 數(shù)據(jù)流圖 從數(shù)據(jù)傳遞和加工的角度來刻畫數(shù)據(jù)流從輸入到輸出的移動(dòng)變換過程。74、 數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。數(shù)據(jù)字典是對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，具有精確、嚴(yán)格的定義，使得用戶和系統(tǒng)分析員對(duì)于輸入、存儲(chǔ)成分和中間的計(jì)算結(jié)構(gòu)有共同的理解。符號(hào)含義示例及說明=被定義為+與X=a+b 表示 X 由 a 和 b 組成 | 或X=a|b 表示 X 由 a 或 b 組成 重復(fù)X=a 表示 X 由 0 個(gè)或多個(gè) a 組成m n重復(fù)X=2a5 表示 X 中最少出現(xiàn) 2 次 a ，最多出現(xiàn) 5 次 a ， 5 、 2 為重復(fù)次數(shù)的上下限（ ）可選X= （ a ） 表示 a 可在 X 中出現(xiàn)，也可不出現(xiàn)“ ”數(shù)據(jù)元素X= “ a” 表示 X 是取值為字符 a 的數(shù)據(jù)元素連接符X=19 表示 X 可取 1 到 9 中的任意一個(gè)值* *注釋*a* 表示 a 為說明或注釋75、 表 4-6 數(shù)據(jù)字典中采用的符號(hào)76、 判定樹和判定表77、 軟件需求規(guī)格說明書 是需求分析階段的最后成果，是軟件開發(fā)的重要文檔之一。78、 軟件需求規(guī)格說明書的作用。1、便于用戶、開發(fā)人員進(jìn)行理解和交流。2、反映出用戶問題的結(jié)構(gòu)?？梢宰鳛檐浖_發(fā)工具的基礎(chǔ)和依據(jù)。3、作為確認(rèn)測試和驗(yàn)收的依據(jù)