《全國計算機等級考試 計算機二級考試 公共基礎(chǔ)知識老師給的資料》由會員分享，可在線閱讀，更多相關(guān)《全國計算機等級考試 計算機二級考試 公共基礎(chǔ)知識老師給的資料（138頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、考點一 算法的基本概念 考點1在筆試考試中考核的幾率為30%，主要是以選擇題的形式出現(xiàn)，分值為2分，此考點為識記內(nèi)容。算法算法: 指解題方案準確而完整的描述指解題方案準確而完整的描述。算法的基本特征：算法的基本特征：可行性可行性確定性確定性有窮性有窮性擁有足夠的情報。擁有足夠的情報?？键c2 算法復(fù)雜度算法的時間復(fù)雜度算法的時間復(fù)雜度 -執(zhí)行算法所需要的計算工作量,即所需基本運算的執(zhí)行次數(shù)算法的空間復(fù)雜度算法的空間復(fù)雜度 -執(zhí)行算法所需要的內(nèi)存空間DAAD考點3 數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)集合中各數(shù)據(jù)的邏輯關(guān)系,即邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)各數(shù)據(jù)元素在計算機中的存儲關(guān)系,即存儲結(jié)構(gòu)存儲結(jié)構(gòu)考點4 線性結(jié)構(gòu)與非線性

2、結(jié)構(gòu)如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：（1）有且只有一個根結(jié)點；（2）每一個結(jié)點最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu) 線性結(jié)構(gòu)又稱線性表。在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)是線性結(jié)構(gòu)。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)?？键c5 棧及其基本運算棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當(dāng)表中沒有元素時稱為空棧。 棧6F5E4D3C2B1Abottomtop出棧出棧入入棧棧棧頂棧頂棧底棧底棧的特點：先進后出先進后出(FILO,fist in last out).棧中元素個數(shù)的求法：棧中元素個數(shù)的求法：T

3、op-bottom+1BCBBA隊列ABCDE退隊退隊入隊入隊frontrear隊頭隊頭隊尾隊列的特點：隊列的特點：先進先出先進先出(FIFO,fist in last out)隊列中元素個數(shù)求法隊列中元素個數(shù)求法rear-frontD線性表的存儲結(jié)構(gòu)：線性表的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)順序表的操作優(yōu)點：讀取方便缺點：插入、刪除操作 時需要移動1234567線性鏈表當(dāng)元素(數(shù)據(jù))變化頻繁度大線性表不宜用順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)：每個結(jié)點由兩部分組成：數(shù)據(jù)域、指針域a1a2a3a1a2a3heada4a5a60a1a2a3heada4a5a6單鏈表單鏈表循環(huán)鏈表循

4、環(huán)鏈表a1a2a3雙向鏈表雙向鏈表D考點7 樹與二叉樹及其基本性質(zhì)樹是一種簡單的非線性結(jié)構(gòu)ABCDEFHG根根結(jié)點的度結(jié)點的度樹的度樹的度層層深度深度11-911-310-909-909-308-908-307-907-306-3結(jié)點擁有的子樹數(shù)稱為結(jié)點的度度。樹的度樹的度是樹內(nèi)各結(jié)點的度的最大值。樹中結(jié)點的最大層次稱為樹的深度深度或高度。度為0的結(jié)點稱為葉子結(jié)點葉子結(jié)點。二叉樹：二叉樹：它的特點是每個結(jié)點至多只有兩棵子樹(二叉樹中不存在度大于2的結(jié)點)并且，二叉樹的子樹有左右之分，其次是次序不能任意顛倒?？荚囈c： (1)結(jié)點個數(shù) (2)遍歷順序 ABEFCKML二叉樹的性質(zhì)：性質(zhì)1：在二叉

5、樹的第i層上至多有 個結(jié)點。性質(zhì)2：深度為k的二叉樹的最多結(jié)點數(shù)為i 12滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹ABEFCKMABEFCKCBAC25H滿二叉樹滿二叉樹是指這樣的一種二叉樹：是指這樣的一種二叉樹：除最后一層外，每一層上的所除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。有結(jié)點都有兩個子結(jié)點。 完全二叉樹完全二叉樹是指這樣的二叉樹：除最后一層是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊大值；在最后一層上只缺少右邊的若干結(jié)點。的若干結(jié)點。滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹ABEFCKMABEFCK考點考點1

6、 二叉樹的遍歷（重點）二叉樹的遍歷（重點）1.先根遍歷(前序遍歷)特點是：先訪問根結(jié)點，接著訪問左子樹，最后訪問右子樹。ABEFCK2.中跟遍歷(中序遍歷)特點是：先訪問左子樹，再訪問根結(jié)點，最后訪問右子樹。EBFAKC3.后根遍歷(后序遍歷)特點是：先訪問左子樹，再訪問右子樹，最后訪問根結(jié)點。EFBKCA先根遍歷先根遍歷(根左右根左右)中根遍歷中根遍歷(左根右左根右)后根遍歷后根遍歷(左右根左右根)ABCDEFHGABEFCKML先根遍歷：ABEFLCKM中根遍歷：EBLFAKMC后根遍歷：ELFBMKCADBXEAYFZCD21 37 88 19 92 05 64 56 80 75 13

7、0 1 2 3 4 5 6 7 8 9 10 11 ST.Length順序表的查找過程：順序表的查找過程：假設(shè)給定值假設(shè)給定值 e = 64,e = 64,問問: i = ?: i = ?ii66ii線性表為無序表時，對于長度為n的無序表，最壞的情況下比較n次。表采用鏈式存儲結(jié)構(gòu)時，對于長度為n的無序表，最壞的情況下比較n次。B二分法查找(對半查找)查找只適合用于順序存儲的有序表，對于長度為n的有序線性表，最壞的情況下比較 次。05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elemST.length例如例如: : k

8、ey = 64key = 64 的查找過程如下的查找過程如下lowhighmidlow mid high midlowlow 指示查找區(qū)間的下界指示查找區(qū)間的下界; ;highhigh 指示查找區(qū)間的上界指示查找區(qū)間的上界; ;midmid = (low+high)/2 = (low+high)/2。05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elemST.length例如例如: : key = 66key = 66 的查找過程如下的查找過程如下lowhighmidlow mid high midlowlow 指示

9、查找區(qū)間的下界指示查找區(qū)間的下界; ;highhigh 指示查找區(qū)間的上界指示查找區(qū)間的上界; ;midmid = (low+high)/2 = (low+high)/2。high lowmidhighlow1、什么是排序？、什么是排序？ 排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組將一組“無序無序”的記錄序列調(diào)整為的記錄序列調(diào)整為“有序有序”的記錄的記錄序列。序列。例如例如：將下列關(guān)鍵字序列將下列關(guān)鍵字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75調(diào)整為調(diào)整為:14, 23, 36, 49, 52, 58, 61

10、 ,75, 80, 9713 38 49 65 76 97 6 69776654938130 1 2 3 4 5 6 70 1 2 3 4 5 6 76簡單插入排序法簡單插入排序法：最壞的情況需要比較的次數(shù)為n(n-1)2D程序設(shè)計原則：清晰第一，效率第二。注重易讀性，易理解，可以添加注釋。結(jié)構(gòu)化程序設(shè)計方法的主要原則為：自頂向下逐步求精模塊化限制使用goto語句。AA模塊獨立性要高，有兩原則高內(nèi)聚（模塊內(nèi)）低耦合（兩模塊之間）BAB對象對象具有如下特征：標識惟一性、分類性、多態(tài)性、封裝性、模塊獨立性。A類是具有共同屬性、共同方法的對象的集合。它描述了屬于該對象類型的所有對象的性質(zhì)，而一個對象

11、則是其對應(yīng)類的一個實例。消息消息是一個實例和另一個實例之間傳遞的信息。繼承繼承繼承是指類之間共享的屬性和操作機制。繼承分單繼承和雙繼承。單繼承指一個類只允許有一個父類，多重繼承是指一個類允許有多個父類。D多態(tài)性多態(tài)性多態(tài)性是指同樣的消息被不同的對象接受時可以導(dǎo)致完全不同的行動現(xiàn)象。1 軟件定義與軟件特點軟件指的是程序程序、數(shù)據(jù)數(shù)據(jù)和相關(guān)文檔相關(guān)文檔的完整集合。根據(jù)應(yīng)用目標的不同，軟件可分應(yīng)應(yīng)用軟件用軟件、系統(tǒng)軟件系統(tǒng)軟件和和支撐軟件支撐軟件（或工具軟件）。程程序序DCB軟件工程包括三個三個要素：方法、工方法、工具、過程。具、過程。 軟件工程包括3個要素：方法、工具和過程。軟件工程方法為軟件開發(fā)

12、提供了如何做的技術(shù)。工具支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。過程過程2 軟件工程過程與軟件生命周期軟件工程過程與軟件生命周期軟件生命周期軟件生命周期是指軟件產(chǎn)品從提出、實是指軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程現(xiàn)、使用維護到停止使用退役的過程一般包括可行性分析研究與需求分析、設(shè)計、實現(xiàn)、測試、交付使用以及維護等活動，A可行性研究可行性研究初步項目計劃初步項目計劃需求分析需求分析使用使用測試測試詳細設(shè)計詳細設(shè)計概要設(shè)計概要設(shè)計實現(xiàn)實現(xiàn)維護維護退役退役開發(fā)開發(fā)階段階段定義定義階段階段維護維護階段階段C開發(fā)開發(fā)需求需求分析分析軟件生命周期分三個階段：

13、軟件定義、軟件開發(fā)、運行維護。生命周期的主要活動階段是：可行性研究與計劃制定、需求分析、軟件設(shè)計、軟件實施、軟件測試及運行與維護。面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法，就是使用數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典（DD）、結(jié)構(gòu)化英語、判定表和判定樹等工具，來建立一種新的、稱為結(jié)構(gòu)化規(guī)格說明的目標文檔。結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法的常用工具：的常用工具：數(shù)據(jù)流圖（數(shù)據(jù)流圖（DFD）數(shù)據(jù)字典（數(shù)據(jù)字典（DD）判定表判定表判定樹判定樹C從工程管理角度來看，軟件設(shè)計包括：概要設(shè)計概要設(shè)計詳細設(shè)計詳細設(shè)計AB典型的數(shù)據(jù)流類型有兩種：典型的數(shù)據(jù)流類型有兩種：變變換型換型和和事物型事物型。詳細過程設(shè)計的常用工具有：詳細過程設(shè)

14、計的常用工具有：（1）圖形工具：）圖形工具：程序流程圖程序流程圖，N-S，PAD，HIPO。（2）表格工具：判定表。）表格工具：判定表。（3）語言工具：）語言工具：PDL（偽碼）。（偽碼）。B數(shù)據(jù)流數(shù)據(jù)流程圖程圖3 軟件測試軟件測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。軟件測試的軟件測試的目的目的是：是：發(fā)現(xiàn)軟件中的錯誤發(fā)現(xiàn)軟件中的錯誤。軟件測試分為軟件測試分為靜態(tài)測試靜態(tài)測試和動態(tài)測試動態(tài)測試。也可分為也可分為：白盒測試白盒測試和黑盒測試黑盒測試。靜態(tài)測試無須執(zhí)行被測代碼。靜態(tài)測試無須執(zhí)行被測代碼。靜態(tài)測試一般是指人工評審軟件文檔或程序，借以發(fā)現(xiàn)其中的錯誤。由于被評審的文檔或程序不必運行，所以稱為

15、靜態(tài)測試。動態(tài)測試是使被測代碼在相對真實環(huán)境動態(tài)測試是使被測代碼在相對真實環(huán)境下運行。下運行。靜態(tài)測試靜態(tài)測試白盒測試的主要方法有邏輯覆蓋邏輯覆蓋、基本路徑基本路徑等。黑盒測試方法有等價劃分法，邊界黑盒測試方法有等價劃分法，邊界值分析法、錯誤推測法、因果圖等。值分析法、錯誤推測法、因果圖等。黑盒黑盒測試測試白盒白盒白盒白盒測試測試軟件測試過程分4個步驟，即單元測試單元測試集成測試集成測試驗收測試驗收測試系統(tǒng)測試系統(tǒng)測試單元單元軟件調(diào)試在對程序進行了成功的測試之后將進入程序調(diào)試（通常稱Debug，即排錯）。程序的調(diào)試任務(wù)是診斷和改正程序中的錯誤。軟件測試的目的是發(fā)現(xiàn)軟件中的錯軟件測試的目的是發(fā)現(xiàn)

16、軟件中的錯誤。誤。軟件調(diào)試目的是發(fā)現(xiàn)并改正程序中軟件調(diào)試目的是發(fā)現(xiàn)并改正程序中的錯誤。的錯誤。軟件測試貫穿整個軟件生命周期。軟件測試貫穿整個軟件生命周期。軟件調(diào)試主要在開發(fā)階段。軟件調(diào)試主要在開發(fā)階段。ABDAA基本概念數(shù)據(jù)（Data）數(shù)據(jù)庫（Database）數(shù)據(jù)庫管理系統(tǒng)（DBMS）數(shù)據(jù)定義語言（DDL）、數(shù)據(jù)操縱語言（DML）、數(shù)據(jù)控制語言（DCL）C數(shù)據(jù)模型數(shù)據(jù)模型 數(shù)據(jù)庫系統(tǒng)的三級模式：（1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶公共數(shù)據(jù)視圖；（2）外模式：也稱子模式與用戶模式。是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式；（3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物

17、理存儲結(jié)構(gòu)與物理存取方法。數(shù)據(jù)庫系統(tǒng)的兩級映射：（1）概念模式到內(nèi)模式的映射；（2）外模式到概念模式的映射。 外模式（用戶數(shù)據(jù)庫）概念模式（概念數(shù)據(jù)庫）外模式（用戶數(shù)據(jù)庫）外模式（用戶數(shù)據(jù)庫）內(nèi)模式（物理數(shù)據(jù)庫）應(yīng)用數(shù)據(jù)庫應(yīng)用應(yīng)用外模式-概念模式映射概念模式-內(nèi)模式映射層次模型基本結(jié)構(gòu)：樹形結(jié)構(gòu)特性：每棵樹的且僅的一個無雙親結(jié)點（根）；樹中除根外所有結(jié)點有且僅有一個雙親支持的操作主要有：查詢、插入、刪除、更新網(wǎng)狀模型基本結(jié)構(gòu)：簡單二級樹（系），其基本數(shù)據(jù)單位為記錄（實體集）OM1M2M4M31nnnn一個系的實例成員記錄首記錄關(guān)系模型數(shù)據(jù)結(jié)構(gòu)：采用二維表二維表來表示，其由表框架及表的元組組成；

18、表框架由n（屬性元數(shù)）個命名的屬性組成。關(guān)系模型：以二維表為基本所建立的模型S#2001001SnSdSa200100220010032001004張浩然張浩然EE李一明李一明王王 偉偉趙堅強趙堅強EEEEEE18191820二維表數(shù)據(jù)庫設(shè)計生命周期需求分析概念設(shè)計邏輯設(shè)計物理設(shè)計DBMS模型DBMS模型硬件、OS支持需求說明書概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型數(shù)據(jù)庫內(nèi)模式概念設(shè)計方法：集中式模式設(shè)計法、視圖集成設(shè)計法過程（E-R模型與視圖集成設(shè)計法進行設(shè)計）：選擇局部應(yīng)用、視圖設(shè)計（自頂向下、由底向上、由內(nèi)向外）、視圖集成（需要解決幾種沖突以及消除冗余-命名沖突、概念沖突、域沖突、約束沖突）邏輯設(shè)計從

19、E-R模型向關(guān)系模式轉(zhuǎn)換：會遇到的轉(zhuǎn)換問題-命名與屬性域的處理、非原子屬性處理、聯(lián)系的轉(zhuǎn)換關(guān)系聯(lián)系元組實體關(guān)系實體集屬性屬性關(guān)系E-R模型關(guān)系E-R模型E-R模型與關(guān)系間的比較表關(guān)系運算 關(guān)系的基本運算有兩類：傳統(tǒng)的集合運算有：并、差、交專門的關(guān)系運算有：選擇、投影、聯(lián)接傳統(tǒng)的集合運算舉例ABC ABCa1b1c1 a1b1c1a1b1c2 a2b2c1a2b2c1 a2b3c2(a)(b)RSABCa1b1c1a2b2c1RS(e)RSABCABCa1b1c1a1b1c1a1b1c1a2b2c1a1b1c1a2b3c2a1b1c2a1b1c1a1b1c2a2b2c1a1b1c2a2b3c2a2b2c1a1b1c1a2b2c1a2b2c1a2b2c1a2b3c2笛卡爾乘積(f)RSR-SABC ABCa1b1c1 a1b1c2a1b1c2 a2b2c1 a2b3c2 (c)(d)CBDADCD