計算機二級基礎知識.doc

計算機二級基礎知識風飛雪未揚數(shù)據(jù)結構與算法算法的基本概念1. 算法：是對問題處理方案的正確而完整的描述，是求解問題的方法，是指令的有效序列。2. 具有5個特性：（1） 有窮性（在有窮步后完成）算法程序的運行時間是有限的（2） 確定性（每一步都有確定的含義）（3） 可行性（4） 輸入（一個算法有零個或多個輸入）（5） 輸出（一個算法有一個或多個輸出）3. 算法的復雜度包括：時間復雜度和空間復雜度。 二者沒有必然的聯(lián)系。時間復雜度：執(zhí)行算法所需要的計算工作量或基本運算次數(shù)?？臻g復雜度：算法所需要的空間的度量。數(shù)據(jù)結構的定義1. 數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構、數(shù)據(jù)的操作數(shù)據(jù)的邏輯結構：數(shù)據(jù)的外部結構，指各數(shù)據(jù)元素之間的邏輯關系，反映人們對數(shù)據(jù)含義的解釋。 包括：線性結構（線性表、棧、隊列）和非線性結構（樹和圖）數(shù)據(jù)的存儲結構：數(shù)據(jù)的物理結構，指數(shù)據(jù)的邏輯結構在計算機中的表示。一個邏輯結構可以有多種存儲結構。 線性表：線性表中元素的個數(shù)n（n=0）定義為線性表的長度。順序存儲是線性表的一種最常用的存儲方式。線性表的順序存儲結構和線性表的鏈式存儲結構分別是隨機存取的存儲結構和順序存取的存儲結構。1.棧：是限定在表尾進行插入和刪除操作的線性表。 具有記憶功能 只能順序存儲（錯）允許插入和刪除的一端叫棧頂。另一端叫棧底。后進先出的線性表2隊列：是限定在一端插入而在另一端刪除，插入端叫隊尾，刪除端叫對頭。先進先出的線性表3棧和隊列的順序存儲結構循環(huán)隊列屬于線性表存儲結構中順序存儲結構和鏈式存儲結構的前者。 樹1.定義:樹的結點、度（結點的度）、葉子（終端結點）、數(shù)的度、深度、有序樹和無序數(shù)2.二叉樹：結點至多有兩棵子樹，并且二叉樹的子樹有之分，次序不能顛倒。性質：在二叉樹的第i層上至多有2i-1個結點 深度為k的二叉樹至多有2k-1個結點。 對任一個二叉樹T，如果其葉子（終端結點數(shù)）為n，度為二的結點數(shù)為m,則n=m+1. 具有n個結點的完全二叉樹的深度為k+1，其中k是2n的整數(shù)部分。2. 二叉樹的遍歷先序遍歷（根左右）中序遍歷（左根右）后序遍歷（左右根）查找算法（1）順序查找順序查找的平均查找長度為（n+1）2，最壞的情況下比較的次數(shù)為n(2) 二分查找最壞情況下次數(shù)為log2n限定于順序存儲的有序線性表排序算法（1）插入類排序直接插入排序折半插入排序希爾排序.（2）交換類排序冒泡排序 最壞情況下的比較次數(shù)n(n-1)2快速排序 最壞情況下的比較次數(shù)n(n-1)2(3)選擇類排序例題精選:1. 設一棵完全二叉樹共有699個結點,則在該二叉樹中的葉子結點數(shù)為:3502. 已知二叉樹后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列為：cedba3. 要求內存量最大的是：歸并排序4. 在數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的是：邏輯結構5. 棧底至棧頂依次存放元素A.B.C.D,在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是：DCBEA6. 已知數(shù)據(jù)表A 中每個元素距其最終位置不遠，為節(jié)省時間，應采取的算法是：直接插入排序7. 用鏈式表示線性表的優(yōu)點是：便于插入和刪除操作。程序設計基礎1.程序設計風格好的程序設計風格有利于提高程序的正確性、可讀性、可維護性和可用性。要是程序有良好的風格概括起來可以分為4部分：源程序文檔化、數(shù)據(jù)說明、語句結構、輸入輸出方法。用戶所定義的標示符必須以字母或下劃線開頭。大、小寫字母代表不同標識。2.結構化程序設計（1）結構化程序設計的基本特征：程序有3中基本結構組成：順序結構、選擇結構、循環(huán)結構整個程序采用模塊化結構。模塊劃分的原則：模塊內具有高內聚度、模塊間具有低耦合度。有限的使用轉移語句，只限定在一個結構的內部跳轉，不允許從一個結構跳到另一結構。程序設計時采用“至頂向下、逐步詳細”的實施方法。（2）結構化程序設計的3種基本結構：順序結構、選擇結構、循環(huán)結構3種基本結構組成的算法只能完成符合結構化的任務（3）結構化程序設計的方法：逐步求精和模塊化程序設計方法。結構化設計的總體思想是采用模塊化結構，自上而下，逐步求精。3. 面向對象程序設計 基本概念對象：系統(tǒng)中運行的實體，是有特殊屬性（數(shù)據(jù)）和方法的實體類：由屬性和方法構成。一組具有相同的數(shù)據(jù)結構和相同的行為特征的對象的集合稱為類在面對對象的方法中，類的實例稱為對象面向對象程序設計特征的是：繼承性、多態(tài)性、封裝性在面向對象的方法中，實現(xiàn)信息隱蔽是依靠對象的封裝任何對象都必須有繼承性（錯）例題精選:1. 在面對對象的方法中，一個對象請求另一個對象為其服務的方式是通過發(fā)送：信息2. 面對對象的設計方法與傳統(tǒng)的面向過程的方法有本質的區(qū)別,它的基本原理是:使用現(xiàn)實世界的概念抽象的思考問題從而自然地解決問題.3. 結構化方法中,軟件功能分解屬于軟件開發(fā)階段中的總體設計4. 結構化程序設計主要強調的是:程序的易讀性5. 面向對象的設計程序主要考慮的是:提高軟件的可重用性6. 類通過接口與外界發(fā)生關系.軟件工程基礎1.軟件工程的基本概念(1)定義:軟件是程序、數(shù)據(jù)與相關文檔的集合。軟件包括系統(tǒng)軟件和應用軟件(2)軟件工程的基本思想是軟件開發(fā)中，應用工程化原則進行軟件開發(fā)，并將這個思想貫穿在軟件開發(fā)的整個過程中。軟件工程的3要素：方法、工具和過程(3)軟件的生命周期：從軟件定義、開發(fā)、使用、維護到報廢為止的整個過程。分三階段：設計階段、開發(fā)階段、維護階段包括：問題定義、可行性分析、需求分析、總體設計、詳細設計、編碼、測試和維護問題定義：確定開發(fā)的任務可行性分析：確定問題的可行性需求分析：對用戶要求進行分析，明確目標系統(tǒng)要做什么總體設計：把軟件功能轉化為所需要的體系結構，即如何解決問題。詳細設計：怎樣具體的解決問題2.結構化分析方法（1）結構化分析（SA）是面向數(shù)據(jù)流進行需求分析的方法SA方法的基本思想正是運用了分解和抽象兩個基本手段，采用：自頂向下，逐步分解的分析思路。（2）數(shù)據(jù)流圖基本圖形符號：在結構化方法中,用數(shù)據(jù)流程圖(DFD)作為描述工具的軟件開發(fā)階段是:需求分析(3)數(shù)據(jù)字典在結構化分析的數(shù)據(jù)流圖中,利用數(shù)據(jù)字典對其中的圖形元素進行確切解釋.3.軟件設計（1）概要設計（總體設計）包括兩個主要階段：系統(tǒng)設計（確定具體的實現(xiàn)方案）和結構設計（確定每個系統(tǒng)的模塊組成及模塊間的關系）模塊之間聯(lián)系越緊密,其耦合性就越強,模塊的獨立性就越差;一個模塊內個要素聯(lián)系越緊密，則它的內聚性就越高。模塊劃分原則：高內聚低耦合（2）詳細設計結構化程序設計的要點：采用自頂向下、逐步求精的程序設計方法，一個程序只有一個入口和一個出口。詳細設計的常用工具：程序流程圖、盒圖、PAD和PDL（3）軟件測試目的軟件測試的目的是盡可能多的發(fā)現(xiàn)程序中的錯誤。軟件測試方法：靜態(tài)測試和動態(tài)測試（黑盒測試法和白盒測試法）黑盒測試包括：等價分析法、邊值分析法、因果圖法和錯誤推測法白盒測試法測試的原則之一就是保證所測模塊中的每一個獨立的路徑至少執(zhí)行一次。（4）程序調試分為靜態(tài)調試和動態(tài)調試調試的目的:改正錯誤經調試后還必須進行再測試（5）軟件維護軟件維護就是在軟件已經交付使用以后，為改正錯誤或滿足新的需求而修改軟件的過程。例題精選：1 分析的結果是產生需求規(guī)格說明書。2 軟件詳細設計的主要任務是確定每一個模塊的算法和使用的數(shù)據(jù)結構。3 進行單元測試時，常用的方法時采用白盒測試，輔以黑盒測試。4 軟件工程的出現(xiàn)是由于軟件危機的出現(xiàn)，人們提出了軟件工程學的原理設計軟件。5 數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，通常包括4個部分：數(shù)據(jù)項、數(shù)據(jù)流、數(shù)據(jù)存儲和數(shù)據(jù)加工。數(shù)據(jù)庫設計基礎1. 數(shù)據(jù)庫（1） 數(shù)據(jù)庫設計的根本目的是要解決數(shù)據(jù)共享的問題。（2） 數(shù)據(jù)庫的特點：數(shù)據(jù)按一定的數(shù)據(jù)模型組織和存儲。 冗余度較小 數(shù)據(jù)的獨立性較高。數(shù)據(jù)獨立性：數(shù)據(jù)的組織結構和存儲方法與應用程序互不依賴、彼此獨立。易擴展可為多種用戶共享2. 數(shù)據(jù)庫管理系統(tǒng)（DBMS）位于用戶與操作系統(tǒng)之間的完成數(shù)據(jù)管理的系統(tǒng)軟件。3. 數(shù)據(jù)庫系統(tǒng)由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、應用系統(tǒng)、數(shù)據(jù)庫管理員和用戶組成。最核心的部分是數(shù)據(jù)庫管理系統(tǒng)。4. 數(shù)據(jù)模型（1） 實體聯(lián)系模型及E-R圖3部分：實體、聯(lián)系和屬性實體集間的聯(lián)系：一對一聯(lián)系、一對多聯(lián)系和多對多聯(lián)系（2） 層次、網狀、關系模型層次模型：有且只有一個結點無雙親，其他結點只有一個雙親。用樹形結構來表示各實體與實體之間的聯(lián)系。在關系數(shù)據(jù)庫中，把數(shù)據(jù)表示成二維表，每個二維表稱為關系。一個關系對應一張二維表。 關系的屬性名稱為關系模式。5. 關系運算（1）并（2）差（3）交（4）笛卡爾積（）6.專門關系運算：選擇、連接和投影（1）從關系中找到滿足條件的所有元組稱