《全國(guó)計(jì)算機(jī)等級(jí)考試 計(jì)算機(jī)二級(jí)考試 公共基礎(chǔ)知識(shí)老師給的資料》由會(huì)員分享，可在線閱讀，更多相關(guān)《全國(guó)計(jì)算機(jī)等級(jí)考試 計(jì)算機(jī)二級(jí)考試 公共基礎(chǔ)知識(shí)老師給的資料（138頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、考點(diǎn)一 算法的基本概念 考點(diǎn)1在筆試考試中考核的幾率為30%，主要是以選擇題的形式出現(xiàn)，分值為2分，此考點(diǎn)為識(shí)記內(nèi)容。算法算法: 指解題方案準(zhǔn)確而完整的描述指解題方案準(zhǔn)確而完整的描述。算法的基本特征：算法的基本特征：可行性可行性確定性確定性有窮性有窮性擁有足夠的情報(bào)。擁有足夠的情報(bào)?？键c(diǎn)2 算法復(fù)雜度算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度 -執(zhí)行算法所需要的計(jì)算工作量,即所需基本運(yùn)算的執(zhí)行次數(shù)算法的空間復(fù)雜度算法的空間復(fù)雜度 -執(zhí)行算法所需要的內(nèi)存空間DAAD考點(diǎn)3 數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)集合中各數(shù)據(jù)的邏輯關(guān)系,即邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系,即存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)考點(diǎn)4 線性結(jié)構(gòu)與非線性
2、結(jié)構(gòu)如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu) 線性結(jié)構(gòu)又稱線性表。在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)?？键c(diǎn)5 棧及其基本運(yùn)算棧是限定只在一端進(jìn)行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當(dāng)表中沒有元素時(shí)稱為空棧。 棧6F5E4D3C2B1Abottomtop出棧出棧入入棧棧棧頂棧頂棧底棧底棧的特點(diǎn)：先進(jìn)后出先進(jìn)后出(FILO,fist in last out).棧中元素個(gè)數(shù)的求法：棧中元素個(gè)數(shù)的求法：T
3、op-bottom+1BCBBA隊(duì)列ABCDE退隊(duì)退隊(duì)入隊(duì)入隊(duì)frontrear隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)列的特點(diǎn)：隊(duì)列的特點(diǎn)：先進(jìn)先出先進(jìn)先出(FIFO,fist in last out)隊(duì)列中元素個(gè)數(shù)求法隊(duì)列中元素個(gè)數(shù)求法rear-frontD線性表的存儲(chǔ)結(jié)構(gòu)：線性表的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序表的操作優(yōu)點(diǎn)：讀取方便缺點(diǎn)：插入、刪除操作 時(shí)需要移動(dòng)1234567線性鏈表當(dāng)元素(數(shù)據(jù))變化頻繁度大線性表不宜用順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：每個(gè)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域、指針域a1a2a3a1a2a3heada4a5a60a1a2a3heada4a5a6單鏈表單鏈表循環(huán)鏈表循
4、環(huán)鏈表a1a2a3雙向鏈表雙向鏈表D考點(diǎn)7 樹與二叉樹及其基本性質(zhì)樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)ABCDEFHG根根結(jié)點(diǎn)的度結(jié)點(diǎn)的度樹的度樹的度層層深度深度11-911-310-909-909-308-908-307-907-306-3結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度度。樹的度樹的度是樹內(nèi)各結(jié)點(diǎn)的度的最大值。樹中結(jié)點(diǎn)的最大層次稱為樹的深度深度或高度。度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)。二叉樹：二叉樹：它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(二叉樹中不存在度大于2的結(jié)點(diǎn))并且，二叉樹的子樹有左右之分，其次是次序不能任意顛倒?？荚囈c(diǎn)： (1)結(jié)點(diǎn)個(gè)數(shù) (2)遍歷順序 ABEFCKML二叉樹的性質(zhì)：性質(zhì)1：在二叉
5、樹的第i層上至多有 個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為k的二叉樹的最多結(jié)點(diǎn)數(shù)為i 12滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹ABEFCKMABEFCKCBAC25H滿二叉樹滿二叉樹是指這樣的一種二叉樹：是指這樣的一種二叉樹：除最后一層外，每一層上的所除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。 完全二叉樹完全二叉樹是指這樣的二叉樹：除最后一層是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。的若干結(jié)點(diǎn)。滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹ABEFCKMABEFCK考點(diǎn)考點(diǎn)1
6、 二叉樹的遍歷（重點(diǎn)）二叉樹的遍歷（重點(diǎn)）1.先根遍歷(前序遍歷)特點(diǎn)是：先訪問根結(jié)點(diǎn)，接著訪問左子樹，最后訪問右子樹。ABEFCK2.中跟遍歷(中序遍歷)特點(diǎn)是：先訪問左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹。EBFAKC3.后根遍歷(后序遍歷)特點(diǎn)是：先訪問左子樹，再訪問右子樹，最后訪問根結(jié)點(diǎn)。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線性表為無(wú)序表時(shí)，對(duì)于長(zhǎng)度為n的無(wú)序表，最壞的情況下比較n次。表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，對(duì)于長(zhǎng)度為n的無(wú)序表，最壞的情況下比較n次。B二分法查找(對(duì)半查找)查找只適合用于順序存儲(chǔ)的有序表，對(duì)于長(zhǎng)度為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、什么是排序？、什么是排序？ 排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組將一組“無(wú)序無(wú)序”的記錄序列調(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簡(jiǎn)單插入排序法簡(jiǎn)單插入排序法：最壞的情況需要比較的次數(shù)為n(n-1)2D程序設(shè)計(jì)原則：清晰第一，效率第二。注重易讀性，易理解，可以添加注釋。結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則為：自頂向下逐步求精模塊化限制使用goto語(yǔ)句。AA模塊獨(dú)立性要高，有兩原則高內(nèi)聚（模塊內(nèi)）低耦合（兩模塊之間）BAB對(duì)象對(duì)象具有如下特征：標(biāo)識(shí)惟一性、分類性、多態(tài)性、封裝性、模塊獨(dú)立性。A類是具有共同屬性、共同方法的對(duì)象的集合。它描述了屬于該對(duì)象類型的所有對(duì)象的性質(zhì)，而一個(gè)對(duì)象
11、則是其對(duì)應(yīng)類的一個(gè)實(shí)例。消息消息是一個(gè)實(shí)例和另一個(gè)實(shí)例之間傳遞的信息。繼承繼承繼承是指類之間共享的屬性和操作機(jī)制。繼承分單繼承和雙繼承。單繼承指一個(gè)類只允許有一個(gè)父類，多重繼承是指一個(gè)類允許有多個(gè)父類。D多態(tài)性多態(tài)性多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可以導(dǎo)致完全不同的行動(dòng)現(xiàn)象。1 軟件定義與軟件特點(diǎn)軟件指的是程序程序、數(shù)據(jù)數(shù)據(jù)和相關(guān)文檔相關(guān)文檔的完整集合。根據(jù)應(yīng)用目標(biāo)的不同，軟件可分應(yīng)應(yīng)用軟件用軟件、系統(tǒng)軟件系統(tǒng)軟件和和支撐軟件支撐軟件（或工具軟件）。程程序序DCB軟件工程包括三個(gè)三個(gè)要素：方法、工方法、工具、過程。具、過程。 軟件工程包括3個(gè)要素：方法、工具和過程。軟件工程方法為軟件開發(fā)
12、提供了如何做的技術(shù)。工具支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理。過程過程2 軟件工程過程與軟件生命周期軟件工程過程與軟件生命周期軟件生命周期軟件生命周期是指軟件產(chǎn)品從提出、實(shí)是指軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程現(xiàn)、使用維護(hù)到停止使用退役的過程一般包括可行性分析研究與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測(cè)試、交付使用以及維護(hù)等活動(dòng)，A可行性研究可行性研究初步項(xiàng)目計(jì)劃初步項(xiàng)目計(jì)劃需求分析需求分析使用使用測(cè)試測(cè)試詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)概要設(shè)計(jì)概要設(shè)計(jì)實(shí)現(xiàn)實(shí)現(xiàn)維護(hù)維護(hù)退役退役開發(fā)開發(fā)階段階段定義定義階段階段維護(hù)維護(hù)階段階段C開發(fā)開發(fā)需求需求分析分析軟件生命周期分三個(gè)階段：
13、軟件定義、軟件開發(fā)、運(yùn)行維護(hù)。生命周期的主要活動(dòng)階段是：可行性研究與計(jì)劃制定、需求分析、軟件設(shè)計(jì)、軟件實(shí)施、軟件測(cè)試及運(yùn)行與維護(hù)。面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法，就是使用數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典（DD）、結(jié)構(gòu)化英語(yǔ)、判定表和判定樹等工具，來(lái)建立一種新的、稱為結(jié)構(gòu)化規(guī)格說(shuō)明的目標(biāo)文檔。結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法的常用工具：的常用工具：數(shù)據(jù)流圖（數(shù)據(jù)流圖（DFD）數(shù)據(jù)字典（數(shù)據(jù)字典（DD）判定表判定表判定樹判定樹C從工程管理角度來(lái)看，軟件設(shè)計(jì)包括：概要設(shè)計(jì)概要設(shè)計(jì)詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)AB典型的數(shù)據(jù)流類型有兩種：典型的數(shù)據(jù)流類型有兩種：變變換型換型和和事物型事物型。詳細(xì)過程設(shè)計(jì)的常用工具有：詳細(xì)過程設(shè)
14、計(jì)的常用工具有：（1）圖形工具：）圖形工具：程序流程圖程序流程圖，N-S，PAD，HIPO。（2）表格工具：判定表。）表格工具：判定表。（3）語(yǔ)言工具：）語(yǔ)言工具：PDL（偽碼）。（偽碼）。B數(shù)據(jù)流數(shù)據(jù)流程圖程圖3 軟件測(cè)試軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。軟件測(cè)試的軟件測(cè)試的目的目的是：是：發(fā)現(xiàn)軟件中的錯(cuò)誤發(fā)現(xiàn)軟件中的錯(cuò)誤。軟件測(cè)試分為軟件測(cè)試分為靜態(tài)測(cè)試靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試動(dòng)態(tài)測(cè)試。也可分為也可分為：白盒測(cè)試白盒測(cè)試和黑盒測(cè)試黑盒測(cè)試。靜態(tài)測(cè)試無(wú)須執(zhí)行被測(cè)代碼。靜態(tài)測(cè)試無(wú)須執(zhí)行被測(cè)代碼。靜態(tài)測(cè)試一般是指人工評(píng)審軟件文檔或程序，借以發(fā)現(xiàn)其中的錯(cuò)誤。由于被評(píng)審的文檔或程序不必運(yùn)行，所以稱為
15、靜態(tài)測(cè)試。動(dòng)態(tài)測(cè)試是使被測(cè)代碼在相對(duì)真實(shí)環(huán)境動(dòng)態(tài)測(cè)試是使被測(cè)代碼在相對(duì)真實(shí)環(huán)境下運(yùn)行。下運(yùn)行。靜態(tài)測(cè)試靜態(tài)測(cè)試白盒測(cè)試的主要方法有邏輯覆蓋邏輯覆蓋、基本路徑基本路徑等。黑盒測(cè)試方法有等價(jià)劃分法，邊界黑盒測(cè)試方法有等價(jià)劃分法，邊界值分析法、錯(cuò)誤推測(cè)法、因果圖等。值分析法、錯(cuò)誤推測(cè)法、因果圖等。黑盒黑盒測(cè)試測(cè)試白盒白盒白盒白盒測(cè)試測(cè)試軟件測(cè)試過程分4個(gè)步驟，即單元測(cè)試單元測(cè)試集成測(cè)試集成測(cè)試驗(yàn)收測(cè)試驗(yàn)收測(cè)試系統(tǒng)測(cè)試系統(tǒng)測(cè)試單元單元軟件調(diào)試在對(duì)程序進(jìn)行了成功的測(cè)試之后將進(jìn)入程序調(diào)試（通常稱Debug，即排錯(cuò)）。程序的調(diào)試任務(wù)是診斷和改正程序中的錯(cuò)誤。軟件測(cè)試的目的是發(fā)現(xiàn)軟件中的錯(cuò)軟件測(cè)試的目的是發(fā)現(xiàn)
16、軟件中的錯(cuò)誤。誤。軟件調(diào)試目的是發(fā)現(xiàn)并改正程序中軟件調(diào)試目的是發(fā)現(xiàn)并改正程序中的錯(cuò)誤。的錯(cuò)誤。軟件測(cè)試貫穿整個(gè)軟件生命周期。軟件測(cè)試貫穿整個(gè)軟件生命周期。軟件調(diào)試主要在開發(fā)階段。軟件調(diào)試主要在開發(fā)階段。ABDAA基本概念數(shù)據(jù)（Data）數(shù)據(jù)庫(kù)（Database）數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）數(shù)據(jù)定義語(yǔ)言（DDL）、數(shù)據(jù)操縱語(yǔ)言（DML）、數(shù)據(jù)控制語(yǔ)言（DCL）C數(shù)據(jù)模型數(shù)據(jù)模型 數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式：（1）概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶公共數(shù)據(jù)視圖；（2）外模式：也稱子模式與用戶模式。是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式；（3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫(kù)物
17、理存儲(chǔ)結(jié)構(gòu)與物理存取方法。數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射：（1）概念模式到內(nèi)模式的映射；（2）外模式到概念模式的映射。 外模式（用戶數(shù)據(jù)庫(kù)）概念模式（概念數(shù)據(jù)庫(kù)）外模式（用戶數(shù)據(jù)庫(kù)）外模式（用戶數(shù)據(jù)庫(kù)）內(nèi)模式（物理數(shù)據(jù)庫(kù)）應(yīng)用數(shù)據(jù)庫(kù)應(yīng)用應(yīng)用外模式-概念模式映射概念模式-內(nèi)模式映射層次模型基本結(jié)構(gòu)：樹形結(jié)構(gòu)特性：每棵樹的且僅的一個(gè)無(wú)雙親結(jié)點(diǎn)（根）；樹中除根外所有結(jié)點(diǎn)有且僅有一個(gè)雙親支持的操作主要有：查詢、插入、刪除、更新網(wǎng)狀模型基本結(jié)構(gòu)：簡(jiǎn)單二級(jí)樹（系），其基本數(shù)據(jù)單位為記錄（實(shí)體集）OM1M2M4M31nnnn一個(gè)系的實(shí)例成員記錄首記錄關(guān)系模型數(shù)據(jù)結(jié)構(gòu)：采用二維表二維表來(lái)表示，其由表框架及表的元組組成；
18、表框架由n（屬性元數(shù)）個(gè)命名的屬性組成。關(guān)系模型：以二維表為基本所建立的模型S#2001001SnSdSa200100220010032001004張浩然張浩然EE李一明李一明王王 偉偉趙堅(jiān)強(qiáng)趙堅(jiān)強(qiáng)EEEEEE18191820二維表數(shù)據(jù)庫(kù)設(shè)計(jì)生命周期需求分析概念設(shè)計(jì)邏輯設(shè)計(jì)物理設(shè)計(jì)DBMS模型DBMS模型硬件、OS支持需求說(shuō)明書概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型數(shù)據(jù)庫(kù)內(nèi)模式概念設(shè)計(jì)方法：集中式模式設(shè)計(jì)法、視圖集成設(shè)計(jì)法過程（E-R模型與視圖集成設(shè)計(jì)法進(jìn)行設(shè)計(jì)）：選擇局部應(yīng)用、視圖設(shè)計(jì)（自頂向下、由底向上、由內(nèi)向外）、視圖集成（需要解決幾種沖突以及消除冗余-命名沖突、概念沖突、域沖突、約束沖突）邏輯設(shè)計(jì)從
19、E-R模型向關(guān)系模式轉(zhuǎn)換：會(huì)遇到的轉(zhuǎn)換問題-命名與屬性域的處理、非原子屬性處理、聯(lián)系的轉(zhuǎn)換關(guān)系聯(lián)系元組實(shí)體關(guān)系實(shí)體集屬性屬性關(guān)系E-R模型關(guān)系E-R模型E-R模型與關(guān)系間的比較表關(guān)系運(yùn)算 關(guān)系的基本運(yùn)算有兩類：傳統(tǒng)的集合運(yùn)算有：并、差、交專門的關(guān)系運(yùn)算有：選擇、投影、聯(lián)接傳統(tǒng)的集合運(yùn)算舉例ABC ABCa1b1c1 a1b1c1a1b1c2 a2b2c1a2b2c1 a2b3c2(a)(b)RSABCa1b1c1a2b2c1RS(e)RSABCABCa1b1c1a1b1c1a1b1c1a2b2c1a1b1c1a2b3c2a1b1c2a1b1c1a1b1c2a2b2c1a1b1c2a2b3c2a2b2c1a1b1c1a2b2c1a2b2c1a2b2c1a2b3c2笛卡爾乘積(f)RSR-SABC ABCa1b1c1 a1b1c2a1b1c2 a2b2c1 a2b3c2 (c)(d)CBDADCD
全國(guó)計(jì)算機(jī)等級(jí)考試 計(jì)算機(jī)二級(jí)考試 公共基礎(chǔ)知識(shí)老師給的資料
