全國計算機等級考試 計算機二級考試 公共基礎(chǔ)知識老師給的資料

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

2、 即存儲結(jié)構(gòu)存儲結(jié)構(gòu) 考點4 線性結(jié)構(gòu)與非線性結(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)。 考點5 棧及其基本運算 棧是限定只在一端進行插入與刪除 的線性表，通常稱插入、刪除的這 一端為棧頂，另一端為棧底。當(dāng)表 中沒有元素時稱為空棧。 棧 6f 5e 4d 3c 2b 1a bottom top 出棧出棧 入入 棧棧 棧頂棧頂 棧底棧底 棧的特點：

3、先進后出先進后出(filo,fist in last out). 棧中元素個數(shù)的求法：棧中元素個數(shù)的求法： top-bottom+1 b c b b a 隊列 abcde 退隊退隊 入隊入隊 front rear 隊頭隊頭 隊尾 隊列的特點：隊列的特點： 先進先出先進先出(fifo,fist in last out) 隊列中元素個數(shù)求法隊列中元素個數(shù)求法 rear-front d 線性表的存儲結(jié)構(gòu)：線性表的存儲結(jié)構(gòu)： 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu) 順序表的操作 優(yōu)點：讀取方便 缺點：插入、刪除操作 時需要移動 1 2 3 4 5 6 7 線性鏈表 當(dāng)元素(數(shù)據(jù))變化頻繁度

4、大線性表 不宜用順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu)： 每個結(jié)點由兩部分組成：數(shù)據(jù)域、 指針域 a1a2a3 a1a2a3 head a4a5a60 a1a2a3 head a4a5a6 單鏈表單鏈表 循環(huán)鏈表循環(huán)鏈表 a1a2a3 雙向鏈表雙向鏈表 d 考點7 樹與二叉樹及其基 本性質(zhì) 樹是一種簡單的非線性 結(jié)構(gòu) a bcd efhg 根根 結(jié)點的度結(jié)點的度 樹的度樹的度 層層 深度深度 11-9 11-3 10-9 09-9 09-3 08-9 08-3 07-9 07-3 06-3 結(jié)點擁有的子樹數(shù)稱為結(jié)點的度度。 樹的度樹的度是樹內(nèi)各結(jié)點的度的最大值。 樹中結(jié)點的最大層次稱為樹的深度深度 或高度

5、。 度為0的結(jié)點稱為葉子結(jié)點葉子結(jié)點。 二叉樹：二叉樹：它的特點是每個結(jié)點至多只有 兩棵子樹(二叉樹中不存在度大于2的結(jié) 點)并且，二叉樹的子樹有左右之分， 其次是次序不能任意顛倒。 考試要點： (1)結(jié)點個數(shù) (2)遍歷順序 a b ef c k m l 二叉樹的性質(zhì)： 性質(zhì)1：在二叉樹的第i層上至多有 個結(jié)點。 性質(zhì)2：深度為k的二叉樹的最多 結(jié)點數(shù)為 i 1 2 滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹 a b ef c k m a b ef c k c b a c 25 h 滿二叉樹滿二叉樹 是指這樣的一種二叉樹：是指這樣的一種二叉樹： 除最后一層外，每一層上的所除最后一層外，每一層上

6、的所 有結(jié)點都有兩個子結(jié)點。有結(jié)點都有兩個子結(jié)點。 完全二叉樹完全二叉樹 是指這樣的二叉樹：除最后一層是指這樣的二叉樹：除最后一層 外，每一層上的結(jié)點數(shù)均達到最外，每一層上的結(jié)點數(shù)均達到最 大值；在最后一層上只缺少右邊大值；在最后一層上只缺少右邊 的若干結(jié)點。的若干結(jié)點。 滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹 a b ef c k m a b ef c k 考點考點1 二叉樹的遍歷（重點）二叉樹的遍歷（重點） 1.先根遍歷(前序遍歷)特點是：先 訪問根結(jié)點，接著訪問左子樹， 最后訪問右子樹。 abefck 2.中跟遍歷(中序遍歷)特點是：先 訪問左子樹，再訪問根結(jié)點，最后 訪問右子樹。 e

7、bfakc 3.后根遍歷(后序遍歷)特點是：先 訪問左子樹，再訪問右子樹，最后 訪問根結(jié)點。 efbkca 先根遍歷先根遍歷(根左右根左右) 中根遍歷中根遍歷(左根右左根右) 后根遍歷后根遍歷(左右根左右根) a bcd efhg a b ef c k m l 先根遍歷： abeflckm 中根遍歷： eblfak mc 后根遍歷： elfbmkc a dbxea yfzc d 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 st.length 順序表的查找過程：順序表的查找過程： 假設(shè)給定值假設(shè)給定值 e = 64,e =

8、 64, 問問: i = ?: i = ? ii 66 ii 線性表為無序表時，對于長度為n的 無序表，最壞的情況下比較n次。 表采用鏈?zhǔn)酱鎯Y(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.elem st.length 例如例如: : key = 64key = 64 的查找過程如下的查找過程如下 lowhigh mid low mid high mid

9、 lowlow 指示查找區(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.elem st.length 例如例如: : key = 66key = 66 的查找過程如下的查找過程如下 lowhigh mid low mid high mid lowlow 指示查找區(qū)間的下界指示查找區(qū)間的下界; ; highhigh 指示查找區(qū)間的上界指示查找區(qū)間的上

10、界; ; midmid = (low+high)/2 = (low+high)/2。 high low mid highlow 1、什么是排序？、什么是排序？ 排序是計算機內(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 ,75, 80, 97 13 38 49 65 76 97 6 6

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

12、對象則是其對 應(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)用目標(biāo)的不同，軟件可分應(yīng)應(yīng) 用軟件用軟件、系統(tǒng)軟件系統(tǒng)軟件和和支撐軟件支撐軟件（或 工具軟件）。 程程 序序 d c b 軟件工程包括三個三個要素：方法、工方法、工 具、過程。具、過程。

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

14、 退役退役 開發(fā)開發(fā) 階段階段 定義定義 階段階段 維護維護 階段階段 c 開發(fā)開發(fā) 需求需求 分析分析 軟件生命周期分三個階段：軟件定 義、軟件開發(fā)、運行維護。 生命周期的主要活動階段是：可行 性研究與計劃制定、需求分析、軟 件設(shè)計、軟件實施、軟件測試及運 行與維護。 面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法，就是 使用數(shù)據(jù)流圖（dfd）、數(shù)據(jù)字典 （dd）、結(jié)構(gòu)化英語、判定表和判 定樹等工具，來建立一種新的、稱 為結(jié)構(gòu)化規(guī)格說明的目標(biāo)文檔。 結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法的常用工具：的常用工具： 數(shù)據(jù)流圖（數(shù)據(jù)流圖（dfd） 數(shù)據(jù)字典（數(shù)據(jù)字典（dd） 判定表判定表 判定樹判定樹 c 從工程管理角度來看，

15、軟件設(shè)計包 括： 概要設(shè)計概要設(shè)計 詳細(xì)設(shè)計詳細(xì)設(shè)計 a b 典型的數(shù)據(jù)流類型有兩種：典型的數(shù)據(jù)流類型有兩種：變變 換型換型和和事物型事物型。 詳細(xì)過程設(shè)計的常用工具有：詳細(xì)過程設(shè)計的常用工具有： （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)測試。

16、 也可分為也可分為：白盒測試白盒測試和黑盒測試黑盒測試。 靜態(tài)測試無須執(zhí)行被測代碼。靜態(tài)測試無須執(zhí)行被測代碼。靜態(tài)測試 一般是指人工評審軟件文檔或程序，借 以發(fā)現(xiàn)其中的錯誤。由于被評審的文檔 或程序不必運行，所以稱為靜態(tài)測試。 動態(tài)測試是使被測代碼在相對真實環(huán)境動態(tài)測試是使被測代碼在相對真實環(huán)境 下運行。下運行。 靜態(tài)測試靜態(tài)測試 白盒測試的主要方法有邏輯覆蓋邏輯覆蓋、 基本路徑基本路徑等。 黑盒測試方法有等價劃分法，邊界黑盒測試方法有等價劃分法，邊界 值分析法、錯誤推測法、因果圖等。值分析法、錯誤推測法、因果圖等。 黑盒黑盒 測試測試 白盒白盒 白盒白盒 測試測試 軟件測試過程分4個步驟，即

17、 單元測試單元測試 集成測試集成測試 驗收測試驗收測試 系統(tǒng)測試系統(tǒng)測試 單元單元 軟件調(diào)試 在對程序進行了成功的測試之后將 進入程序調(diào)試（通常稱debug，即 排錯）。程序的調(diào)試任務(wù)是診斷和 改正程序中的錯誤。 軟件測試的目的是發(fā)現(xiàn)軟件中的錯軟件測試的目的是發(fā)現(xiàn)軟件中的錯 誤。誤。 軟件調(diào)試目的是發(fā)現(xiàn)并改正程序中軟件調(diào)試目的是發(fā)現(xiàn)并改正程序中 的錯誤。的錯誤。 軟件測試貫穿整個軟件生命周期。軟件測試貫穿整個軟件生命周期。 軟件調(diào)試主要在開發(fā)階段。軟件調(diào)試主要在開發(fā)階段。 a b d a a 基本概念 數(shù)據(jù)（data） 數(shù)據(jù)庫（database） 數(shù)據(jù)庫管理系統(tǒng)（dbms） 數(shù)據(jù)定義語言（dd

18、l）、數(shù)據(jù)操縱語 言（dml）、數(shù)據(jù)控制語言（dcl） c 數(shù)據(jù)模型數(shù)據(jù)模型 數(shù)據(jù)庫系統(tǒng)的三級模式： （1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu) 的描述，全體用戶公共數(shù)據(jù)視圖； （2）外模式：也稱子模式與用戶模式。是用戶的 數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式； （3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物 理存儲結(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)用 外模式-概念模式映射 概念

19、模式-內(nèi)模式映射 層次模型 基本結(jié)構(gòu)：樹形結(jié)構(gòu) 特性：每棵樹的且僅的一個無雙親結(jié)點 （根）；樹中除根外所有結(jié)點有且僅有 一個雙親 支持的操作主要有：查詢、插入、刪除、 更新 網(wǎng)狀模型 基本結(jié)構(gòu)：簡單二級樹（系），其基本 數(shù)據(jù)單位為記錄（實體集） o m1m2m4m3 1 nnnn 一個系的實例 成員 記錄 首記錄 關(guān)系模型 數(shù)據(jù)結(jié)構(gòu)：采用二維表二維表來表示，其由表 框架及表的元組組成；表框架由n（屬 性元數(shù)）個命名的屬性組成。 關(guān)系模型：以二維表為基本所建立的模 型 s# 2001001 snsdsa 2001002 2001003 2001004 張浩然張浩然ee 李一明李一明 王王 偉偉 趙堅強趙堅強 ee ee ee 18 19 18 20 二維表 數(shù)據(jù)庫設(shè)計生命周期 需求分析 概念