計算機二級考試公共基礎知識要點.doc

計算機二級考試公共基礎知識要點.txt老子忽悠孩子叫教育，孩子忽悠老子叫欺騙，互相忽悠叫代溝。男人這花花世界，我要用什么顏色來吸引你。 本文由伊然880貢獻 doc文檔可能在WAP端瀏覽體驗不佳。建議您優(yōu)先選擇TXT，或下載源文件到本機查看。 第一章 數(shù)據(jù)結構與算法 一、學習目標與要求 1了解算法的基本概念和一些常用的算法，學會計算算法的時間復雜度； 2掌握數(shù)據(jù)結構的基本概念，并了解數(shù)據(jù)的邏輯結構和存儲結構，學會利 用圖形的方式表示數(shù)據(jù)結構； 3了解線性表的基本概念，并掌握線性表的順序存儲結構以及順序存儲的 線性表的基本運算； 4了解棧和隊列的基本概念，并掌握它們的基本運算； 5了解線性鏈表的基本概念，并掌握線性鏈表的基本運算，同時，了解循 環(huán)鏈表的基本概念和基本操作； 6理解樹的概念，尤其是二叉樹的基本概念和相關性質，掌握二叉樹的存 儲結構和遍歷技術； 7 掌握查找技術， 學會利用順序查找和二分查找在數(shù)列中查找指定的數(shù)據(jù)； 8學會利用相關的排序技術實現(xiàn)無序數(shù)列的排序操作。 二、內容要點 （一）算法 1算法的基本概念 算法是指解題方案的準確而完整的描述。 即是一組嚴謹?shù)囟x運算順序的規(guī) 則，并且每一個規(guī)則都是有效的，且是明確的，沒有二義性，同時該規(guī)則將在有 限次運算后可終止。 1）算法的基本特征 （1）可行性 由于算法的設計是為了在某一個特定的計算工具上解決某一個實際的問題 而設計的，因此，它總是受到計算工具的限制，使執(zhí)行產生偏差。 如：計算機的數(shù)值有效位是有限的，當大數(shù)和小數(shù)進行運算時，往往會因為 有效位數(shù)的影響而使小數(shù)丟失，因此，在算法設計時，應該考慮到這一點。 （2）確定性 算法的設計必須是每一個步驟都有明確的定義，不允許有模糊的解釋，也不 能有多義性。 例如，一個實際的問題，小寶和萍萍共有 12 個蘋果，小寶比萍萍多 4 個， 請問小寶和萍萍各有幾個蘋果？這個問題，我們可以立一個方程 來求解，要求 x 和 y 的值，公式是正確的，但如何讓計算能夠進行計算，我們的 算法不能把公式直接輸進去，而應該設計出解題的步驟和過程。 即設計的算法是計算工具所能夠正常解決問題的過程。 （3）有窮性 算法的有窮性，即在一定的時間是能夠完成的，即算法應該在計算有限個步 驟后能夠正常結束。 例如，在數(shù)學中的無窮級數(shù)，在計算機中只能求有限項，即計算的過程是有 窮的。 （4）擁有足夠的情報 算法的執(zhí)行與輸入的數(shù)據(jù)和提供的初始條件相關， 不同的輸入或初始條件會 有不同的輸出結果，提供準確的初始條件和數(shù)據(jù)，才能使算法正確執(zhí)行。 2）算法的基本要素 一是數(shù)據(jù)對象的運算和操作，二是算法的控制結構。 （1）算法中對數(shù)據(jù)的運算和操作 算法實際上是按解題要求從環(huán)境能進行的所有操作中選擇合適的操作所組 成的一組指令序列。即算法是計算機所能夠處理的操作所組成的指令序列。 （2）算法的控制結構 算法的功能不僅取決于所選用的操作，而且還與各操作之間的順序有關。 在算法中，操作的執(zhí)行順序又稱算法的控制結構，一般的算法控制結構有三 種：順序結構、選擇結構和循環(huán)結構。 在算法描述是，有相關的工具對這三種結構進行描述，常用的描述工具有： 流程圖、N-S 結構圖和算法描述語言等。 3）算法設計的基本方法 為用計算機解決實際問題而設計的算法，即是計算機算法。 通常的算法設計有如下幾種： （1）列舉法 列舉法的基本思想是，根據(jù)提出的問題，列舉出所有可能的情況，并用問題 中給定的條件檢驗哪些是滿足條件的，哪些是不滿足條件的。列舉法通常用于解 決“是否存在”或“有哪些可能”等問題。 例如，我國古代的趣味數(shù)學題：“百錢買百雞”、“雞兔同籠”等，均可采 用列舉法進行解決。 使用列舉法時，要對問題進行詳細的分析，將與問題有關的知識條理化、完 備化、系統(tǒng)化，從中找出規(guī)律。 （2）歸納法 歸納法的基本思想是，通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般 的關系。歸納是一種抽象，即從特殊現(xiàn)象中找出一般規(guī)律。但由于在歸納法中不 可能對所有的情況進行列舉，因此，該方法得到的結論只是一種猜測，還需要進 行證明。 （3）遞推 遞推，即是從已知的初始條件出發(fā)，逐次推出所要求的各個中間環(huán)節(jié)和最后 結果。 其中初始條件或問題本身已經(jīng)給定， 或是通過對問題的分析與化簡而確定。 遞推的本質也是一種歸納，遞推關系式通常是歸納的結果。 例如，裴波那契數(shù)列，是采用遞推的方法解決問題的。 （4）遞歸 在解決一些復雜問題時， 為了降低問題的復雜程序， 通常是將問題逐層分解， 最后歸結為一些最簡單的問題。這種將問題逐層分解的過程，并沒有對問題進行 求解，而只是當解決了最后的問題那些最簡單的問題后，再沿著原來分解的逆過 程逐步進行綜合，這就是遞歸的方法。 遞歸分為直接遞歸和間接遞歸兩種方法。如果一個算法直接調用自己，稱為 直接遞歸調用；如果一個算法 A 調用另一個算法 B，而算法 B 又調用算法 A，則 此種遞歸稱為間接遞歸調用。 （5）減半遞推技術 減半遞推即將問題的規(guī)模減半，然后，重復相同的遞推操作。 例如，一元二次方程的求解。 （6）回溯法 有些實際的問題很難歸納出一組簡單的遞推公式或直觀的求解步驟， 也不能 使用無限的列舉。對于這類問題，只能采用試探的方法，通過對問題的分析，找 出解決問題的線索，然后沿著這個線索進行試探，如果試探成功，就得到問題的 解， 如果不成功， 再逐步回退， 換別的路線進行試探。 這種方法， 即稱為回溯法。 如人工智能中的機器人下棋。 2算法復雜度 算法的復雜度包括時間復雜度和空間復雜度。 1）時間復雜度 即實現(xiàn)該算法需要的計算工作量。 算法的工作量用算法所執(zhí)行的基本運算次 數(shù)來計算。 同一個問題規(guī)模下， 如果算法執(zhí)行所需要的基本次數(shù)取決于某一特定輸入時， 可以用以下兩種方法來分析算法的工作量： 算法工作量=f(n) （1）平均性態(tài) 用各種特定輸入下的基本運算次數(shù)的加權平均值來度量算法的工作量。 設 x 是某個可能輸入中的某個特定輸入，p(x)是 x 出現(xiàn)的概率，t(x)是算法 在輸入為 x 時所執(zhí)行的基本運算次數(shù)，則算法的平均性態(tài)定義為： Dn 表示當規(guī)模為 n 時，算法執(zhí)行時所有可能輸入的集合。 （2）最壞情況復雜度 指在規(guī)模為 n 時，算法所執(zhí)行的基本運算的最大次數(shù)。它定義為： 第二章 程序設計基礎 一、學習目標與要求 1了解程序設計的方法，以及程序設計風格確立的一些因素，掌握程序設 計的基本規(guī)則； 2了解結構化程序設計的基本原則，掌握結構化程序設計的基本結構與特 點； 3了解面向對象的程序設計方法，并理解面向對象方法的一些基本概念。 二、內容要點 （一）程序設計方法與風格 程序設計方法： 主要經(jīng)過了面向過程的結構化程序設計和面向對象的程序設 計方法。 程序設計風格， 是指編寫程序時所表現(xiàn)出來的特點、 習慣和邏輯思路。 通常， 要求程序設計的風格應強調簡單和清晰，必須是可以讀的，可以理解的。 要形成良好的程序設計的風格，應考慮如下因素： 1源程序文檔化 （1）符號名的命名：符號名的命名要具有一定的實際含義，便于對程序的 理解，即通常說的見名思義； （2）程序注釋：正確的程序注釋能夠幫助他人理解程序。注釋一般包括序 言性注釋和功能性注釋； （3）視覺組織：為了使程序一目了然，可以對程序的格式進行設置，適當 地通過空格、空行、縮進等使程序層次清晰。 2數(shù)據(jù)說明方法 （1）數(shù)據(jù)說明的次序規(guī)范化； （2）說明語句中變量安排有序化； （3）使用注釋來說明復雜的數(shù)據(jù)結構。 3語句的結構 （1）在一行內只寫一條語句； （2）程序的編寫應該優(yōu)先考慮清晰性； （3）除非對效率有特殊的要求，否則，應做到清晰第一，效率第二； （4）首先保證程序的正確，然后再要求速度； （5）避免使用臨時變量使程序的可讀性下降； （7）盡量使用庫函數(shù)，即盡量使用系統(tǒng)提供的資源； （8）避免采用復雜的條件語句； （9）盡量減少使用“否定”條件的條件語句； （10）數(shù)據(jù)結構要有利于程序的簡化； （11）要模塊化，使模塊功能盡可能單一化； （12）利用信息隱蔽，確保每一個模塊的獨立性； （13）從數(shù)據(jù)出發(fā)去構造程序； （14）不要修補不好的程序，要重新編寫。 4輸入和輸出 （1）對所有的輸入輸出數(shù)據(jù)都要檢驗數(shù)據(jù)的合法性； （2）檢查輸入項的各種重要組合的合理性； （3）輸入格式要簡單，以使得輸入的步驟和操作盡可能簡單； （4）輸入數(shù)據(jù)時，應允許自由格式； （5）應允許缺省值； （6）輸入一批數(shù)據(jù)時，最好使用輸入結束標志； （7）以交互式輸入輸出方式進行輸入時，要在屏幕上使用提示符明確輸入 的請求，同時在數(shù)據(jù)輸入過程中和輸入結束時，應在屏幕上給出狀態(tài)信息； （8）當程序設計語言對輸入格式有嚴格要求時，應保持輸入格式與輸入語 句的一致性；給所有的輸出加注釋，并設計輸出報表格式。 （二）結構化程序設計 1結構化程序設計的原則 結構化程序設計方法的主要原則：自頂而下、逐步求精，模塊化，限制使用 goto 語句。 1）自頂而下 程序設計時，應先考慮總體，后考慮細節(jié)；先考慮全局，后考慮局部目標。 即先從最上層總目標開始設計，逐步使問題具體化。 2）逐步求精 對復雜問題，應設計一些子目標作為過渡，逐步細化。 3）模塊化 一個復雜問題，都是由若干個稍簡單的問題構成的。模塊化即是將復雜問題 進行分解，即將解決問題的總目標分解成若干個分目標，再進一步分解為具體的 小目標，把每一個小目標稱作一個模塊。 4）限制使用 goto 語句 goto 語句可以提高效率，但對程序的可讀性、維護性都造成影響，因此應 盡量不用 goto 語句。 2結構化程序設計的基本結構與特點 結構化程序設計是程序設計的先進方法和工具， 采用結構化程序設計可以使 程序結構良好、易讀、易理解、易維護。 1）順序結構 順序結構即是順序執(zhí)行的結構，是按照程序語句行的自然順序，一條一條語 句地執(zhí)行程序。 2）選擇結構 選擇結構又稱分支結構，它包括簡單選擇和多分支選擇結構。程序的執(zhí)行是 根據(jù)給定的條件，選擇相應的分支來執(zhí)行。 3）重復結構 重復結構又稱循環(huán)結構，根據(jù)給定的條件，決定是否重復執(zhí)行某一相同的或 類似的程序段。利用重復結構可以大量簡化程序行。 3結構化程序設計原則和方法的應用 1使用程序設計語言中的順序、選擇、循環(huán)等有限的控制結構表示程序的 控制邏輯； 2選用的控制結構只允許有一個入口和一個出口； 3程序語句組成容易識別的塊，每塊只有一個入口和一個出口； 4復雜結構應該用嵌套的基本控制結構進行組合嵌套來實現(xiàn)； 5語言中所有沒有的控制結構，應該采用前后一致的方法來模擬； 6嚴格控制 goto 語句的使用： （1）用一個非結構化的程序設計語言去實現(xiàn)一個結構化的構造； （2）若不使用 goto 語句會使功能模糊； （3）在某種可以改善而不是損害程序可讀性的情況下。 第三章 軟件工程基礎 一、學習目標與要求 1了解軟件工程的基本概念； 2了解軟件工程過程與軟件的生命周期，以及軟件工程的目標和原則； 3了解利用結構化分析法進行軟件工程中的需求分析的方法，并了解需求 分析的方法和需要完成的任務； 4了解數(shù)據(jù)流圖的使用方法； 5了解如何利用結構化設計方法進行軟件設計，并了解軟件設計的一些常 用用工具； 6了解軟件測試的目的和方法，以及軟件測試的準則，了解常用的軟件測 試方法的區(qū)別和各自的功能與特點； 7了解程序調試的方法和原則。 二、內容要點 （一）軟件工程基本概念 1軟件定義與軟件特點 1）軟件的定義 與計算機系統(tǒng)的操作有關的計算機程序、規(guī)程、規(guī)則，以及可能有的文件、 文檔及數(shù)據(jù)。 2）軟件的特點 （1）軟件是一種邏輯實體，而不是物理實體，具有抽象性； （2）軟件的生產與硬件不同，它沒有明顯的制作過程； （3）軟件在運行、使用期間不存在磨損、老化問題；但為了適應硬件、環(huán) 境以及需求的變化要進行修改，會導致一些錯誤的引入，導致軟件失效率升高， 從而使得軟件退化； （4） 軟件的開發(fā)、 運行對計算機系統(tǒng)具有依賴性， 受到計算機系統(tǒng)的限制， 這導致了軟件移植的問題； （5）軟件復雜性高，成本昂貴。軟件開發(fā)需要投入大量、高強度的腦力勞 動，成本高，風險大； （6）軟件開發(fā)涉及諸多的社會因素。許多軟件的開發(fā)和運行涉及軟件用戶 的機構設置，體制問題以及管理方式等，甚至涉及到人們的觀念和心理，軟件知 識產權及法律等問題。 3）軟件的分類 按功能分，可分為： 應用軟件：為解決特定領域的應用而開發(fā)的軟件 系統(tǒng)軟件：是計算機管理自身資源，提高計算機使用效率并為計算機用戶提 供各種服務的軟件 支撐軟件（或工具軟件）：介于系統(tǒng)軟件和應用軟件之間，協(xié)助用戶開發(fā)軟 件的工具性軟件，包括輔助和支持開發(fā)和維護應用軟件的工具軟件 2軟件危機與軟件工程 1）軟件危機 泛指在計算機軟件的開發(fā)和維護過程中所遇到的一系列嚴重問題。 它主要表 現(xiàn)在： （1）軟件需求的增長得不到滿足，用戶對系統(tǒng)不滿意的情況經(jīng)常發(fā)生； （2）軟件開發(fā)成本和進度無法控制。開發(fā)的成本超預算和開發(fā)周期的超期 經(jīng)常出現(xiàn)； （3）軟件質量難以保證； （4）軟件不可維護或維護程度非常低； （5）軟件成本不斷提高； （6）軟件開發(fā)生產率的提高趕不上硬件的發(fā)展和應用需求的增長。 2）軟件工程 軟件工程的定義：是應用于計算機軟件的定義、開發(fā)和維護的一整套方法、 工具、文檔、實踐標準和工序。 軟件工程包括 3 個要素：方法、工具和過程。 方法：完成軟件工程項目的技術手段； 工具：支持軟件的開發(fā)、管理、文檔生成； 過程：支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。 3軟件工程過程與軟件生命周期 1）軟件工程過程 軟件工程過程把輸入轉化為輸出的一組彼此相關的資源和活動。 支持軟件工 程過程的兩方面內涵： （1）軟件工程過程是指為獲得軟件產品，在軟件工具支持下由軟件工程師 完成的一系列軟件工程活動。它包括 4 種基本活動： P軟件規(guī)格說明。規(guī)定軟件的功能及其運行時的限制； D軟件開發(fā)。產生滿足規(guī)格說明的軟件； C軟件確認。確認軟件能夠滿足客戶提出的要求； A軟件演進過程。 為滿足客戶的變更要求， 軟件必須在使用的過程中演進。 （2）使用適當?shù)馁Y源（包括人員、硬軟件工具、時間等），為開發(fā)軟件進 行的一組開發(fā)活動， 在過程結束時將輸入 （用戶要求） 轉化為輸出 （軟件產品） 。 軟件工程過程是將軟件工程的方法和工具綜合起來，以達到合理、及時地進 行計算機軟件開發(fā)的目的。 2）軟件生命周期 將軟件產品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為軟件生命周 期。即軟件的生命周期就是軟件產品從開始考慮其概念開始，到軟件產品不能使 用為止的整個時期都屬于軟件生命周期。 一般包括可行性研究與需求分析、 設計、 實現(xiàn)、測試、交付使用以及維護等活動。這些活動可以有重復，執(zhí)行時也可以有 迭代。 生命周期的主要階段： 軟件定義 軟件開發(fā) 軟件維護 軟件生命周期的主要活動階段是： （1） 可行性研究與計劃制定： 確定待開發(fā)軟件系統(tǒng)的開發(fā)目標和總的要求， 給出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成開發(fā)任務的 實話計劃； （2）需要分析。對待開發(fā)軟件提出的需求進行分析并給出詳細的定義； （3）軟件設計。系統(tǒng)設計人員和程序設計人員給出軟件的結構、模塊的劃 分、功能的分配以及處理流程； （4）軟件實現(xiàn)。把軟件設計轉換成計算機可以接受的程序代碼。即完成源 程序的編碼，編寫用戶手冊、操作手冊等面向用戶的文檔，編寫單元測試計劃； （5）軟件測試。在設計測試用例的基礎上，檢驗軟件的各個組成部分，編 寫測試分析報告； （6） 運行和維護。 將已交付的軟件投入運行， 并在運行使用中不斷地維護， 根據(jù)新提出的需求進行必要且可能的擴充和刪改。 4軟件工程的目標與原則 1）軟件工程的目標 軟件工程的目標： 在給定成本、 進度的情況下， 開發(fā)出具有有效性、 可靠性、 可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性 且滿足用戶需求的產品。 軟件工程需要達到的基本目標： 付出較低的開發(fā)成本 達到要求的軟件功能 取得較好的軟件性能 開發(fā)的軟件易于移植 需要較低的維護費用 能按時完成開發(fā)，及時交付使用 軟件工程的理論和技術性研究的內容包括：軟件開發(fā)技術和軟件工程管理。 （1）軟件開發(fā)技術 軟件開發(fā)方法學、開發(fā)過程、開發(fā)工具和軟件工程環(huán)境，其主體內容是軟件 開發(fā)方法學。軟件開發(fā)方法學是根據(jù)不同的軟件類型，按不同的觀點和原則，對 軟件開發(fā)中應遵循的策略、原則、步驟和必須產生的文檔資料都做出規(guī)定，從而 使軟件開發(fā)能夠進入規(guī)范化和工程化的階段。 （2）軟件工程管理 軟件工程管理：軟件管理學、軟件工程經(jīng)濟學、軟件心理學等內容。 軟件工程管理學包括：人員組織、進度安排、質量保證、配置管理、項目計 劃等。 軟件工程經(jīng)濟學：是研究軟件開發(fā)中成本的估算、成本效益分析的方法和技 術，用經(jīng)濟學的基本原理事研究軟件工程開發(fā)中的經(jīng)濟效益問題。 軟件心理學：從個體心理、人類行為、組織行為和企業(yè)文化等角度來研究軟 件管理和軟件工程。 第四章 數(shù)據(jù)庫設計基礎 一、學習目標與要求 1了解數(shù)據(jù)庫系統(tǒng)的基本概念，以及數(shù)據(jù)庫系統(tǒng)的發(fā)展； 2了解數(shù)據(jù)模型的基本概念，并對 E-R 模型、層次模型、網(wǎng)狀模型和關系 模型進行了解，并掌握關系模型的數(shù)據(jù)結構、關系的操作和數(shù)據(jù)約束等知識； 3了解關系模型的基本操作，掌握關系模型的基本運算及擴充運算； 4了解數(shù)據(jù)庫的設計與管理，掌握數(shù)據(jù)庫設計的幾個階段的方法和特點。 二、內容要點 （一）數(shù)據(jù)庫系統(tǒng)的基本概念 1數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng) 1）數(shù)據(jù) 數(shù)據(jù)是指存儲在某一種媒體上能夠被識別的物理符號， 即描述事物的符號記 錄。 數(shù)據(jù)是有結構的。首先，數(shù)據(jù)有型與值的區(qū)別，型即類型，值是符合指定類 型的值。 數(shù)據(jù)的概念在數(shù)據(jù)處理領域中已經(jīng)大大地拓寬了。 數(shù)據(jù)不僅包括數(shù)字、 字母、 文字和其他特殊字符組成的文本形式的數(shù)據(jù)，而且還包括圖形、圖像、動畫、影 像、聲音等多媒體數(shù)據(jù)。但是使用最多、最基本的仍然是文字數(shù)據(jù)。 2）數(shù)據(jù)庫 數(shù)據(jù)庫（DataBase，DB），是存儲在計算機存儲設備上，結構化的相互關聯(lián) 的數(shù)據(jù)的集合。它不僅包括描述事物的數(shù)據(jù)本身，而且還包括相關事物之間的聯(lián) 系。 它用綜合的方法組織和管理數(shù)據(jù)， 具有較小的數(shù)據(jù)冗余， 可供多個用戶共享， 具有較高的數(shù)據(jù)獨立性，具有安全機制，能夠保證數(shù)據(jù)的安全、可靠，允許并發(fā) 地使用數(shù)據(jù)庫，能有效、及時地處理數(shù)據(jù)，并能保證數(shù)據(jù)的一致性和完整性。 例如，某個學校的相關數(shù)據(jù)，如學生基本情況、選課情況、學籍管理等所涉 及的相關數(shù)據(jù)的集合。 3）數(shù)據(jù)庫管理系統(tǒng) 數(shù)據(jù)庫管理系統(tǒng)（DataBase Management System，DBMS）是對數(shù)據(jù)庫進行管 理的系統(tǒng)軟件，它的職能是有效地組織和存儲數(shù)據(jù)、獲取和管理數(shù)據(jù)，接受和完 成用戶提出的訪問數(shù)據(jù)的各種請求。同時還能保證數(shù)據(jù)的安全性、可靠性、完整 性、一致性，還要保證數(shù)據(jù)的高度獨立性。 數(shù)據(jù)庫管理系統(tǒng)主要功能包括以下幾個方面： （1）數(shù)據(jù)模式定義 數(shù)據(jù)庫管理系統(tǒng)負責為數(shù)據(jù)庫構建模式，也為數(shù)據(jù)庫構建其數(shù)據(jù)框架。 （2）數(shù)據(jù)存取的物理構建 數(shù)據(jù)庫管理系統(tǒng)負責為數(shù)據(jù)模式的物理存取及構建提供有效的存取方法和 手段。 （3）數(shù)據(jù)操縱 數(shù)據(jù)庫管理系統(tǒng)為用戶使用數(shù)據(jù)庫中的數(shù)據(jù)提供方便， 一般提供查詢、 插入、 修改和刪除數(shù)據(jù)的功能，此外，還具有簡單的算術運算和統(tǒng)計功能，還具有專長 強大的程序控制功能。 （4）數(shù)據(jù)的完整性、安全性定義與檢查 數(shù)據(jù)庫中的數(shù)據(jù)具有內存語義