2011年計算機等級考試二級公共基礎考前背誦版 來源

1、20112011 年計算機等級考試二級公共基礎考前背誦版年計算機等級考試二級公共基礎考前背誦版來源： 胡明輝的日志下面分為四個部分進行組織。 文中標注了三個星號的， 表示非常重要，基本每次考試都是必考；標注了兩個星號或一個星號的， 表示也較重要， 很容易考到。出現(xiàn)在【】括號中的內(nèi)容，表示要很精確的背下來的。整個文檔中的五頁，建議考前都要認真的記憶。第一部分第一部分 算法與數(shù)據(jù)結構算法與數(shù)據(jù)結構 ( (歷年比例歷年比例 41%)41%)1 1、算法、算法 問題處理方案的正確而完整的描述稱為【算法】。算法分析的目的是，分析算法的效率以求改進。算法的基本特征是【可行性】、【確定性】、【有窮性】和擁有

2、足夠情報。 算法的有窮性是指：算法程序的運行時間是有限的。 算法的復雜度是衡量算法好壞的度量，分為【時間復雜度】和【空間復雜度】。 時間復雜度是指執(zhí)行算法所需要的【計算工作量】；算法的空間復雜度是指算法執(zhí)行過程中所需的【存儲空間】。 算法時間復雜度或空間復雜度中的一項的值，沒有辦法推出另一項的值。2 2、數(shù)據(jù)結構、數(shù)據(jù)結構 數(shù)據(jù)結構分為【邏輯結構邏輯結構】和【存儲結構存儲結構】。線性結構和非線性結構屬于邏輯結構；順序、鏈式、索引屬于存儲結構(物理結構)。循環(huán)隊列屬于【存儲結構】。 數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構又稱為物理結構，是數(shù)據(jù)的邏輯結構在計算機存儲空間中的存放形式數(shù)據(jù)的邏輯結構在計算機存儲

3、空間中的存放形式。 一個邏輯結構可以有多種存儲結構，且各種存儲結構影響數(shù)據(jù)處理的效率。程序執(zhí)行的效率與數(shù)據(jù)的存儲結構密切相關。 數(shù)據(jù)結構分為線性結構和非線性結構，帶鏈的隊列屬于【線性結構】。 線性表的存儲結構主要分為順序存儲結構和鏈式存儲結構。順序存儲結構的存儲一定是連續(xù)的，鏈式存儲的存儲空間不一定是連續(xù)的。 有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構。 隊列是一種特殊的線性表，循環(huán)隊列按照【先進先出】原則組織數(shù)據(jù)。循環(huán)隊列是隊列的【順序】存儲結構。 數(shù)據(jù)的獨立性分為【物理獨立】性和【邏輯獨立性】。當數(shù)據(jù)的存儲結構改變時，其邏輯結構可以不變，因此，基于邏輯結構的應用程序可以不用修

4、改，稱為【物理獨立性】。3 3、棧和隊列、棧和隊列 棧是一種特殊的線性表，是只能在一端進行插入和刪除只能在一端進行插入和刪除的線性表，特點是filo(firstin last out)。 棧是【先進后出】的線性表先進后出】的線性表；棧具有記憶作用；對棧的插入與刪除操作中，不需要改變【棧底指針】。假定讓元素1、2、3、a、b 依次入棧，則出棧的順序是：b、a、3、2、1。 棧與隊列都是線性結構，樹是非線性結構。支持子程序調用的數(shù)據(jù)結構是【?！俊?棧與隊列的共同點是，都只允許在【端點處】插入和刪除元素。 棧只能順序存儲棧只能順序存儲的描述是錯誤錯誤的。?？梢杂小卷樞蚝玩準健績煞N存儲方式。 隊列是允

5、許在一段插入，在另一端進行刪除的線性表，其特點是【先進先出先進先出】。 循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定由隊頭指針和隊尾指針共同決定。循環(huán)隊列的頭指針為front，尾指針為 rear，容量為 maxsize，則循環(huán)隊列中元素的個數(shù)是 【 (rear-front+maxsize) modmaxsize】。4 4、線性鏈表、線性鏈表 線性鏈表是線性表的鏈式存儲結構。 用鏈表表示線性表的優(yōu)點是 【便于插入和刪除操作】 。 線性鏈表的存儲空間不一定連續(xù)，且個元素的存儲順序是任意的。5 5、樹與二叉樹、樹與二叉樹 在樹結構中，一個結點所擁有的后件（繼）的個數(shù)稱為該結點的度，所有結點中最

6、大的度稱為樹的度。二叉樹各結點的度只可能取值只可能取值 0 0、1 1、2 2，不可能是其它值。換言之，知道了度為 1 結點數(shù)量的前提下，葉子結點或度為2 的結點中知道其一，就可以求出總的結點數(shù)。下面關于計算結點數(shù)量的幾個性質，非常重要：(1)對任意的二叉樹，葉子結點的數(shù)量，比度為葉子結點的數(shù)量，比度為 2 2 的結點數(shù)量多一個的結點數(shù)量多一個(換言之，已知葉子結點的數(shù)量，減去1 則是度為 2 的結點數(shù)量；已知度為 2 的結點數(shù)量，加上 1 就是葉子結點數(shù)量)(2)完全二叉樹如果有 n 個結點，當n 為奇數(shù)的時候，葉子結點數(shù)為(n+1)/2，此時二叉樹只有度為0 的葉子結點及度為 2 的結點，

7、沒有度為1 的結點；當n 為偶數(shù)的時候，葉子結點的數(shù)量為n/2。(注意條件，必須是完全二叉樹，當然包括滿二叉樹)(3)滿二叉樹第 k 層上的結點數(shù)量為 2k-1k-1；深度為 k 的滿二叉樹，結點總數(shù)為 2 2k k-1。上述的計算公式，關鍵要能夠應用，例如，深度為上述的計算公式，關鍵要能夠應用，例如，深度為 7 7 的滿二叉樹，度為的滿二叉樹，度為 2 2 的結點數(shù)量是多的結點數(shù)量是多少？既然是滿二叉樹，葉子結點的數(shù)量就是第少？既然是滿二叉樹，葉子結點的數(shù)量就是第 7 7 層的結點數(shù)量，也就是層的結點數(shù)量，也就是 2 26 6，可以算出葉子，可以算出葉子結點為結點為 6464，因此度為，因此

8、度為 2 2 的結點數(shù)是的結點數(shù)是 63(63(葉子結點數(shù)減去葉子結點數(shù)減去 1)1)。 二叉樹的前序遍歷、中序遍歷、后續(xù)遍歷：前中后三個詞是相對于根來講的，前序是【根根-左左-右右】，中序是【左左-根根-右右】，后續(xù)是【左左-右右-根根】。具體操作為：先序遍歷(d l r): 訪問根結點，按先序遍歷左子樹，按先序遍歷右子樹。中序遍歷(l d r): 按中序遍歷左子樹，訪問根結點，按中序遍歷右子樹。后序遍歷(l r d): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結點。下面以中序遍歷為例，來講解實際的解題方法： 對一棵樹，將根結點下的左子樹用一個橢圓圈起來，右子樹也用一個橢圓圈起來。之后，在

9、左子樹上標記上1，在根結點標記上2，在右子樹上標記上 3。對在左邊橢圓內(nèi)的左子樹，現(xiàn)在把它單獨拿出來分析。把它的左子樹圈起來標上 1.1，根結點標記上1.2，右子樹標上1.3。按照上述方法依次往下，直到樹不能拆分，然后按照“左左-根根-右右”的順序寫出結點的訪問先后即可。6 6、查找技術、查找技術 對于長度為 n 的線性表，順序查找順序查找最壞情況下需要比較比較 n n 次次。(對數(shù)據(jù)是否有序沒有要求)。 順序查找最好情況下查詢次數(shù)是1，最壞情況下是 n，平均為(1+n)/2。 對于長度為 n 的有序線性表有序線性表， 二分法二分法最壞情況下只需要比較 log2n 次。 (數(shù)據(jù)必須有序) 能用

10、二分法進行查找的是【順序存儲的有序線性表】。7 7、排序技術、排序技術 對于長度為 n 的線性表，【冒泡排序、快速排序、簡單插入排序、簡單選擇排序冒泡排序、快速排序、簡單插入排序、簡單選擇排序】這四種排序方式在最壞情況下的比較次數(shù)相同，都是【n(n-1)/2n(n-1)/2】。堆排序堆排序的效率最高，是【nlognlog2 2n n】。 希爾排序最壞情況下需要次比較【n n1.51.5】。希爾排序屬于【插入類排序法】。 已知數(shù)據(jù)表 a 中每個元素距最終位置不遠，為節(jié)省時間，應該采用的算法是【直接插入排序】。選擇排序、插入排序、快速排序、歸并排序中對內(nèi)存要求最大的是【歸并排序】。第二部分第二部分

11、 軟件工程基礎軟件工程基礎 ( (歷年比例歷年比例 27%)27%)1 1、軟件工程基本概念、軟件工程基本概念 軟件是包括【程序】、【數(shù)據(jù)】及【相關文檔】的完整集合，軟件是一種邏輯產(chǎn)品。軟件工程三要素包括【方法、工具和過程】，其中【過程】支持軟件開發(fā)的各個環(huán)節(jié)的控制和管理。 軟件工程的核心思想：把軟件產(chǎn)品當作是一個工程產(chǎn)品來處理，強調在軟件開發(fā)過程中應用【工程化】工程化】原則。 從工程管理角度，軟件設計一般分為兩步完成，它們是【概要設計】和【詳細設計】。 軟件生命周期可分為多個階段，一般分為【定義】階段、【開發(fā)】階段和【維護】階段，編碼和測試屬于【開發(fā)階段】。 需求分析階段產(chǎn)生的主要文檔是【軟

12、件需求規(guī)格說明書】。軟件需求的規(guī)格說明書應該有完整性、無歧義性、正確性、可驗證性、可修改性等特征，其中最重要的是【正確性】。2 2、結構化分析與設計、結構化分析與設計 需求分析的分發(fā)有： 【結構化】需求分析方法， 【面向對象】的分析方法。dfd 是【需求分析階段】可以使用的工具之一。 結構化分析的常用工具：數(shù)據(jù)流圖(dfd)；數(shù)據(jù)字典；判定樹；判定表。 在結構化分析使用數(shù)據(jù)流圖(dfd)時候，利用【數(shù)據(jù)字典】對其中的圖形元素進行確切的解釋?！緮?shù)據(jù)字典】是結構化分析的核心。 典型的數(shù)據(jù)流類型有兩種，【交換性】和【事務型】。 常見的過程設計工具有： 圖形工具(程序流程圖、n-s，pad，hipo)

13、、表格工具(判定表)、語言工具(pdl 偽碼)。 內(nèi)聚性是模塊內(nèi)部的聯(lián)系，耦合性模塊之間的相互聯(lián)系的緊密程度。 追求目標是： 模塊的內(nèi)聚程度要高，模塊的內(nèi)聚程度要高，模塊間的耦合程度要盡量弱模塊間的耦合程度要盡量弱。即高內(nèi)聚低耦合高內(nèi)聚低耦合。 程序流程圖程序流程圖中帶有箭頭的線段表示的是【控制流控制流】。【平行四邊形】代表輸入輸出，【矩形】代表處理，菱形代表【判斷】(注意，數(shù)據(jù)流圖中的箭頭，代表【數(shù)據(jù)流】)。 符合結構化原則的三種基本控制結構是：【順序結構】，【選擇結構】和【循環(huán)結構】。3 3、軟件測試與維護、軟件測試與維護 軟件測試的目的是盡可能多的發(fā)現(xiàn)程序中的錯誤， 但是不包括改正錯誤不

14、包括改正錯誤。(軟件調試的目的才是改正錯誤) 軟件測試分為靜態(tài)測試和動態(tài)測試，其中【靜態(tài)測試】是指不執(zhí)行程序，只對程序文本進行檢查。軟件的動態(tài)測試主要包括【黑盒測試】和【白盒測試】。 黑盒測試的方法有等價類劃分法，邊界值分析法，錯誤推測法，因果圖；白盒測試主要方法有邏輯覆蓋、基本路徑測試。(考試時給出一種方法的名字，你要知道屬于白盒還是黑盒)【白盒測試】 的原則之一是保證所測模塊的每一個獨立路徑至少要執(zhí)行一次。 白盒測試將程序看做是【路徑的集合】。 軟件測試一般按照四個步驟進行：單元測試，集成測試，驗收測試和系統(tǒng)測試。集成測試應該在【單元測試】之后進行。 在模塊測試中，需要為每個被測試的模塊設

15、計【驅動模塊】和【承接模塊】。其中，驅動模塊的作用是將測試的數(shù)據(jù)傳給被測試的模塊，并顯示結果。 【測試用例】是為某個目標而編制的一組測試輸入、執(zhí)行條件及預期結果。測試用例包括輸入值集和【輸出值集】。 診斷和改正程序中的錯誤稱為【程序調試】(或軟件調試)，通常也稱為 debug。軟件調試可分為【靜態(tài)調試】和【動態(tài)調試】。 在軟件已經(jīng)交付使用之后，為了改正錯誤或滿足新的需要而修改軟件的過程稱為【軟件維護】。注意軟件維護不屬于軟件生命周期【開發(fā)階段】的任務。第三部分第三部分 數(shù)據(jù)庫設計基礎數(shù)據(jù)庫設計基礎 ( (歷年比例歷年比例 24%)24%)1 1、數(shù)據(jù)庫系統(tǒng)基本概念、數(shù)據(jù)庫系統(tǒng)基本概念 數(shù)據(jù)庫設

16、計的根本目標是要解決【數(shù)據(jù)共享問題】。在數(shù)據(jù)庫管理技術發(fā)展的三個階段中，數(shù)據(jù)共享最好的是 【數(shù)據(jù)庫系統(tǒng)階段】 。數(shù)據(jù)獨立性最高的階段是 【數(shù)據(jù)庫系統(tǒng)階段】 。 數(shù)據(jù)庫系統(tǒng)與文件系統(tǒng)的區(qū)別是前者具有【特定的數(shù)據(jù)模型】。 數(shù)據(jù)庫系統(tǒng)常見的數(shù)據(jù)模型有層次模型，網(wǎng)絡模型和【關系模型】。 數(shù)據(jù)庫系統(tǒng)的核心是【數(shù)據(jù)庫管理系統(tǒng)】。dbs 包括 db 和 dbms。完整講，數(shù)據(jù)庫系統(tǒng)dbs 由數(shù)據(jù)庫 db、數(shù)據(jù)庫管理系統(tǒng)dbms、數(shù)據(jù)庫管理員 dba、硬件平臺和軟件平臺組成。 數(shù)據(jù)庫應用系統(tǒng)應用系統(tǒng)的核心核心是【數(shù)據(jù)庫維護】。 數(shù)據(jù)庫系統(tǒng)的三級模式結構：內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計算機物理結構中的實際存

17、儲形式；概念模式處于中層，它放映了設計者的數(shù)據(jù)全局邏輯要求， 與軟硬件環(huán)境無關；外模式處于最外層，它反映了用戶對數(shù)據(jù)的要求。 在數(shù)據(jù)庫系統(tǒng)中，用戶所見的數(shù)據(jù)模式為【外模式】。 數(shù)據(jù)庫設計的四個階段是：需求分析、概念設計、【邏輯設計】和【物理設計】。將e-r 圖轉換成關系數(shù)據(jù)模型屬于【邏輯設計】階段。 數(shù)據(jù)庫管理系統(tǒng)提供的數(shù)據(jù)語言：數(shù)據(jù)定義語言ddl，數(shù)據(jù)操縱語言dml，數(shù)據(jù)控制語言 dcl。sql 的全稱是 structured query language，中文意思是【結構化查詢語言結構化查詢語言】。2 2、數(shù)據(jù)模型、數(shù)據(jù)模型 實體之間的聯(lián)系用樹形結構樹形結構來表示的模型是【層次模型】。采用

18、二維表來表示的是【關系模型】。在關系數(shù)據(jù)庫中，把數(shù)據(jù)表示成二維表，每一個二維表稱為【關系】。 在關系數(shù)據(jù)庫中，用來表示實體之間聯(lián)系的是【關系】。 將 e-r 圖轉化為關系模式時，實體和聯(lián)系都可以表示為【關系】。 確定兩個實體之間是一對一、一對多、還是多對多的方法是：選擇實體a，看是否有多個實體 b 與之對應；選擇實體b，看是否有多個實體 a 與之對應。例如在“學生學習課程”中的兩個實體，學生與課程，一個學生可以學習多門課程，一門課程可以被多個學生學習，所以二者是一種多對多的關系。 在 e-r 圖中，用來表示實體的圖形是【矩形】。用來表示【屬性】的圖形是橢圓。用菱形來表示聯(lián)系。 一個關系表的行稱為【元組元組】(或記錄)，列稱為【屬性屬性】(或字段)。 在二維表中，元組的【分量】不能再分為更小的數(shù)據(jù)線。 為了建立一個關系，首先要構造數(shù)據(jù)的【邏輯關系】。3 3、關系代數(shù)、關系代數(shù) 在交、差、投影中，不改變關系表中的屬性個數(shù)但是能減少元組個數(shù)的是【交】運算。 關系運算的規(guī)則(下面介紹的 7 種運算，考試的時候一般會考察一種，都要背)(1)并運算 rs：并運算是兩個表行上的合并兩個表行上的合并，重復的行只出現(xiàn)一次。(2)交運算 rs：交運算是選出兩個表中的公共行選出兩個表中的公共行。(3)差運算 r-s：差運算是從表 r 中，刪除 r 與