計算機二級考(筆試)復(fù)習(xí)資料 公共基礎(chǔ)知識.doc

1、 算法1. 算法基本概念：算法是在有限的步驟內(nèi) 求解某一問題 所使用的一組 定義明確的法則。通俗的說就是計算機解決問題的過程（計算方法），這個過程中無論是形成解題思路（推理實現(xiàn)的算法）還是編寫程序（操作實現(xiàn)的算法），都是實施某種算法。 算法是一組邏輯步驟 程序是用計算機語言描述的算法2.算法特征：輸入（初始條件）、確定性（每一計算步驟都有確切的定義）、有窮性（算法必須保證執(zhí)行有限步結(jié)束）、可行性（算法原則上能精確計算，而且人用紙筆做有限次運算后即可完成）、輸出（沒輸出的結(jié)果無意義）。3.算法的表示：傳統(tǒng)算法-圖形法（如流程圖） 目前常用方法-偽代碼表示4. 算法的基本要素：對數(shù)據(jù)對象的運算和操作（算數(shù)運算、關(guān)系運算、邏輯運算、數(shù)據(jù)傳輸）算法的控制結(jié)構(gòu)（順序、選擇、循環(huán)）5. 算法的基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法6. 算法的評價：時間復(fù)雜度（執(zhí)行這個算法所需的計算工作量）空間復(fù)雜度（執(zhí)行這個算法所需的內(nèi)存空間） 算法不等于程序，也不等于計算機方法，程序的編制不可能優(yōu)于算法的設(shè)計。二、數(shù)據(jù)結(jié)構(gòu) 程序=算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。包括三個方面：數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； 在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的儲存關(guān)系，即數(shù)據(jù)的儲存結(jié)構(gòu)； 對各種數(shù)據(jù)結(jié)構(gòu)進行計算。1. 邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息 2）表示各數(shù)據(jù)元素之間的前后關(guān)系。 常見的邏輯結(jié)構(gòu)有：線性結(jié)構(gòu)（結(jié)構(gòu)中每個元素存在一個對一個的關(guān)系）、樹形結(jié)構(gòu)（存在一個對多個的關(guān)系）、圖形結(jié)構(gòu)（存在多個對多個的關(guān)系）。其中樹形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為 非線性結(jié)構(gòu)。2. 存儲結(jié)構(gòu)（物理結(jié)構(gòu)） 儲存結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在存儲空間中的具體實現(xiàn)。 只抽象的反應(yīng)數(shù)據(jù)元素之間的關(guān)系的結(jié)構(gòu)，而不管其儲存方式的數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。 各數(shù)據(jù)元素在計算機中的儲存位置與他們的邏輯關(guān)系不一定是相同的。而且一般是不同的。 一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要而選擇一種或多種存儲結(jié)構(gòu) 常見的存儲結(jié)構(gòu)有：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、索引存儲結(jié)構(gòu)。3.數(shù)據(jù)的運算 檢索、插入、刪除、更新、排序常見的數(shù)據(jù)結(jié)構(gòu)1. 線性表 線性表是由n(n=0)個數(shù)據(jù)元素組成的一個有限的序列（如：春夏秋冬） 線性表的存儲結(jié)構(gòu)有兩種：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。 鏈?zhǔn)酱鎯Y(jié)構(gòu)不要求邏輯上相鄰的數(shù)據(jù)元素物理位置也相鄰，而且個數(shù)據(jù)元素的存儲位置也是任意的。各數(shù)據(jù)元素的先后關(guān)系是由各節(jié)點的指針域指示。 鏈?zhǔn)酱鎯Y(jié)構(gòu)每一個存儲結(jié)點不僅是存儲節(jié)點的值，而且存儲結(jié)點之間的關(guān)系 采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，存儲空間開銷較大，但是進行插入和刪除運算不會造成大量的域元素移動。 循環(huán)鏈表是鏈?zhǔn)酱鎯Y(jié)構(gòu)的一種，特點是表中最后一個節(jié)點的指針域指向頭結(jié)點。 雙向鏈表的結(jié)點中有兩個指針域，其中一個直接指向直接后繼，另一個直接指向直接前趨。 線性表的存儲結(jié)構(gòu)有兩種：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)。 數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系域與他們的邏輯關(guān)系不一定是相同的。 一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)而且不同的存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率。2. 棧和隊列 A）棧是一種特殊的線性表其特點是插入和刪除運算都只能在線性表的一端進行。 棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的線性表。 棧的物理存儲結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈表結(jié)構(gòu)。 棧的基本運算只有三種：入棧、退棧、和讀棧項元素。 B）隊列是一種特殊的線性表其特點是：所有的插入在線性表的一端進行，所有的刪除運算都在表的另一端進行。即在表的前端進行插入操作，在表的后端進行刪除操作。（隊列進行插入運算的是隊首，進行刪除運算的隊尾） 隊列是按照“先進先出”或“后進后出”的原則組織數(shù)據(jù)的線性表。即最先插入的元素是最先刪除的元素，最后插入的是最后刪除的。 隊列有三種運算：入隊、出隊、讀隊首元素。 循環(huán)隊列：把隊列的存儲空間在邏輯上看成一個環(huán)，當(dāng)R指向存儲空間的末端時，就把它重新置于始端。 線性表（線性結(jié)構(gòu)）、棧（特殊的線性表）、隊列（是一種操作受限制的線性表）、樹（是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)） 非線性結(jié)構(gòu)：一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)就是非線性結(jié)構(gòu)。 線性結(jié)構(gòu)的特點：有且僅有一個根節(jié)點 除第一個結(jié)點外，每一個結(jié)點最多有一個直接前驅(qū)節(jié)點 除最后一個接點外，每一個結(jié)點最多有一個直接后綴結(jié)點。3.樹與二叉樹 樹的概念 樹的定義，n個結(jié)點的有限集。 根只有一個。 如果n=0則稱之為空樹，否則當(dāng)n1時，其余結(jié)點被分成m(m0)個互不相交的子集，每個子集又是有一棵樹。 樹型結(jié)構(gòu)的常用術(shù)語： 結(jié)點的度（一個結(jié)點子樹的個數(shù)）；樹的度（樹中所有結(jié)點度的最大值）；終端結(jié)點（度為零的結(jié)點）；非終端結(jié)點（度不為零的結(jié)點）；節(jié)點的層次（樹中根節(jié)點的層次為1，根結(jié)點子樹的根為第2層，以此類推）；樹的深度（樹中所有結(jié)點層次的最大值）；有序樹，無序樹（如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱之為有序樹，否則稱之為無序樹） 二叉樹的概念 定義 二叉樹是一種有序的樹形結(jié)構(gòu)，它與一般的樹形結(jié)構(gòu)的區(qū)別是：每個結(jié)點最多有兩個子樹；子樹有左右之分，次序不能任意顛倒。 性質(zhì) 在二叉樹的第i層最多有2(i-1)個結(jié)點 深度為h的二叉樹最多有2h-1個結(jié)點(h=1) 二叉樹上葉子結(jié)點數(shù)比度為2的結(jié)點數(shù)多1 滿二叉樹：如果一個深度為h的二叉樹擁有2h-1個結(jié)點，則將它稱為滿二叉樹。 完全二叉樹：有一顆深度為h，具有n個結(jié)點的二叉樹，若將他與一顆同深度的滿二叉樹中的所有結(jié)點按從上到下，從左到右的順序分別進行編號，且該二叉樹中的每個結(jié)點分別與滿二叉樹中編號為1n的結(jié)點位置一一對應(yīng)，則稱這顆二叉樹為完全二叉樹。 二叉樹的存儲：在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。 二叉樹的遍歷： 遍歷指不重復(fù)的訪問二叉樹的所有節(jié)點； 二叉樹的遍歷的次序與樹型結(jié)構(gòu)上的大多數(shù)運算有聯(lián)系； 遍歷的方式有三種(1)前序遍歷（DLR） (2)中序遍歷（LDR） (3)后序遍歷（LRD）4. 查找技術(shù) 查找指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找指定的元素，該元素也稱關(guān)鍵字。 若查找到了滿足條件的結(jié)點，則稱查找成功；否則稱之為查找失敗。 衡量一個查找算法的主要標(biāo)準(zhǔn)是查找過程中對關(guān)鍵字進行的平均比較次數(shù)。 通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)采取不同的查找方法：順序查找、二分查找。 順序查找：從第一個元素開始依次比較。適用場合，對線性表中元素的排列次序沒有要求 對線性表的存儲結(jié)構(gòu)沒有要求，鏈?zhǔn)胶晚樞蚪Y(jié)構(gòu)都可。 二分查找：首先在表的中間位置查找比較大小，然后根據(jù)比較的大小再確定在那=哪個子表中查找。重復(fù)上述過程，直至查找完畢。適用場合，線性表中關(guān)鍵字值以遞增或遞減的次序排列，線性表采用順序存儲結(jié)構(gòu)。5.排序技術(shù) 冒泡排序：A.掃描整個線性表，逐次對相鄰的兩個元素進行比較，若為逆序，則交換，第一趟掃描完則使最大的數(shù)排到表的最后；B.重復(fù)A過程，除開最后一個元素，以此類推。對于長度為N的線性列表要掃描N-1遍。 選擇排序：從表中找出最小的元素，排在第一位。然后從第二位開始查找最小的元素，排在第二位，以此類推。對于長度為N的線性列表要掃描N-1遍。 最壞情況需要的次數(shù)：簡單選擇排序，最壞要n(n-1)/2次；冒泡排序，最壞要n(n-1)/2次；希爾排序法，最壞要O(n1.5)次比較。堆排序，最壞要O(n乘以 以2為底n的對數(shù)）次比較）。3、 程序設(shè)計基礎(chǔ)結(jié)構(gòu)化程序設(shè)計 四條原則：自頂向下；逐步求精；模塊化；限制使用goto語句。 基本結(jié)構(gòu)及特點：順序結(jié)構(gòu)（簡單程序設(shè)計最基本最常用的結(jié)構(gòu)）；選擇結(jié)構(gòu) 又稱分支結(jié)構(gòu)（包括簡單選擇和多分支選擇結(jié)構(gòu)）；重復(fù)結(jié)構(gòu) 又稱循環(huán)結(jié)構(gòu)（可根據(jù)給定條件判斷是否重復(fù)執(zhí)行某一相同程序段）。面向?qū)ο蟮某绦蛟O(shè)計 對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睢?對象是系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。 屬性即對象所包含的信息 操作描述了對象執(zhí)行的功能，操作也稱為方法或服務(wù)。 類是指具有共同屬性、共同方法的對象的集合。 所以類是對象的抽象，對象是對應(yīng)類的一個實例。 消息是一個實例與另一個實例之間傳遞的信息。（消息的組成包括：接受對象的名稱；消息標(biāo)識符，也稱消息名；零個或多個參數(shù)） 繼承是指能夠直接獲獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。 多態(tài)性是指同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動的現(xiàn)象。4、 軟件工程基礎(chǔ) 軟件工程概念 軟件工程是應(yīng)用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標(biāo)準(zhǔn)和工序。 軟件工程包括3個要素：方法、工具和過程。 軟件周期：軟件產(chǎn)品從提出、實現(xiàn)、使用和維護到停止使用退役的過程。 軟件生命周期三個階段：軟件定義（可行性研究，需求分析）、軟件開發(fā)（概念設(shè)計、詳細(xì)設(shè)計、研究、測試）、運行維護（使用、維護、退役）。主要活動階段：可行性研究與計劃的制定；需求分析；軟件設(shè)計；軟件實現(xiàn)；軟件測試；運行和維護。結(jié)構(gòu)化分析方法 結(jié)構(gòu)化分析方法：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。 結(jié)構(gòu)化分析的常用工具：數(shù)據(jù)流圖；數(shù)據(jù)字典；判定樹，判定表；軟件需求規(guī)格說明書。結(jié)構(gòu)化設(shè)計方法 軟件設(shè)計包括：總體設(shè)計與詳細(xì)設(shè)計 在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強，則耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。 常見的過程設(shè)計工具有：圖形工具（程序流程圖，N-S，PAD）；表格工具（判定表）；語言工具（PDL偽碼）。軟件測試 目的：發(fā)現(xiàn)錯誤而執(zhí)行程序的過程 軟件測試方法： 靜態(tài)測試：包括檢查代碼，靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實際運行軟件主要通過人工進行。 動態(tài)測試：是基本的計算機測試，主要包括白盒測試方法（邏輯覆蓋、基于路基測試）和黑盒測試方法（等價類劃分法、邊界值分析法、錯誤推測法、因果圖法、判定表驅(qū)動法 ）。 軟件測試過程一般按四個步驟進行：單元測試、集成測試、驗收測試和系統(tǒng)測試。程序調(diào)試 程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤，主要在開發(fā)階段進行。 軟件調(diào)試，靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和排錯，是主要的設(shè)計手段。動態(tài)調(diào)試是輔靜態(tài)調(diào)試，主要調(diào)試方法（強行排錯法，回溯法，原因排除法）五、數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)：實際上就是描述事物的符號記錄數(shù)據(jù)庫（DB）：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個應(yīng)用程序共享。數(shù)據(jù)庫管理系統(tǒng)（DBMS）：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操作、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫的核心。數(shù)據(jù)庫系統(tǒng)（DBS）：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構(gòu)成的運行實體。數(shù)據(jù)庫應(yīng)用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件、應(yīng)用界面三者組成。 數(shù)據(jù)庫系統(tǒng)層次示意圖：數(shù)據(jù)庫應(yīng)用系統(tǒng)最終用戶 操作系統(tǒng)計算機硬件數(shù)據(jù)庫管理系統(tǒng) 開發(fā)人員數(shù)據(jù)庫管理員 常見的關(guān)系數(shù)據(jù)庫軟件，小型：Visual FoxPro 、Access 大型：Oracle、Informix、SYBASE、SQL server 等數(shù)據(jù)系統(tǒng)的基本概念 數(shù)據(jù)管理系統(tǒng)提供的數(shù)據(jù)語言，數(shù)據(jù)定義語言：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；數(shù)據(jù)操作語言：負(fù)責(zé)數(shù)據(jù)的操縱，如查詢、增、刪、減、改；等；數(shù)據(jù)控制語言：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復(fù)等。 數(shù)據(jù)管理系統(tǒng)的發(fā)展，文件系統(tǒng)階段：提供了簡單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但它無法提供完整的、統(tǒng)一的。管理數(shù)據(jù)和數(shù)據(jù)共享能力。層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段：為統(tǒng)一于共享數(shù)據(jù)提供了有力的支撐。關(guān)系數(shù)據(jù)庫系統(tǒng)階段 關(guān)系數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)據(jù)的集成性，數(shù)據(jù)的高共享性與低冗余性，數(shù)據(jù)的獨立性，數(shù)據(jù)的統(tǒng)一管理與控制。 數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點。 數(shù)據(jù)庫的三級模式：概念模式；外模式；內(nèi)模式。數(shù)據(jù)庫內(nèi)模式(物理數(shù)據(jù)庫)概念模式（概念數(shù)據(jù)庫）外模式（用戶數(shù)據(jù)庫）外模式（用戶數(shù)據(jù)庫）外模式（用戶數(shù)據(jù)庫）應(yīng)用應(yīng)用應(yīng)用 數(shù)據(jù)庫的兩級映射：概念模式到內(nèi)模式的映射；概念模式到外模式的映射。外模式到概念模式映射 概念模式到內(nèi)模式映射數(shù)據(jù)模型 數(shù)據(jù)模型是對客觀事物及其關(guān)系的客觀描述。數(shù)據(jù)庫中的數(shù)據(jù)模型可以將復(fù)雜的現(xiàn)實世界要求反映到計算機數(shù)據(jù)庫中的物理世界。 數(shù)據(jù)模型是數(shù)據(jù)特征的抽象，從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件。 數(shù)據(jù)模型所描述的內(nèi)容包含：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)約束。 E-R模型的基本概念：實體，現(xiàn)實世界中的事物；屬性，事物的特征；聯(lián)系，現(xiàn)實世界中事物的關(guān)系，實體集的關(guān)系有一對一、一對多、多對多的聯(lián)系。 E-R模型的圖示法：用簡單的幾何圖形表示實體集、屬性與聯(lián)系。 實體集的表示法：在E-R圖中用矩形表表示實體集，在矩形內(nèi)寫上實體集的名字。屬性表示法：在E-R圖中用橢圓形表示屬性，在橢圓形內(nèi)寫上該屬性的名稱。聯(lián)系表示法：在E-R圖中用菱形（內(nèi)寫上聯(lián)系名）表示聯(lián)系。實體集與屬性間的聯(lián)系關(guān)系：屬性依附于實體集它們之間