|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
 |
 |
2010二級公共基礎知識復習綱要 |
公共基礎知識考試點 第 1 章 數(shù)據(jù)結構與算法 考點1:算法具有4個基本特征：可行性、確定性、有窮性、擁有足夠的情報。 確定性:是指算法中每一個步驟都必須是有明確定義的,不允許模棱兩可的定義 有窮性:是指算法必須能在有限的時間內做完 一個算法由兩種基本要素組成:一是對數(shù)據(jù)對象的運算和操作,二是算法的控制結構 考點2:算法復雜度包括時間復雜度和空間復雜度 時間復雜度 執(zhí)行算法所需要的計算工作量 空間復雜度 執(zhí)行這個算法所需要的內存空間 考點3:數(shù)據(jù)結構 一:討論的問題:1.數(shù)據(jù)元素之間的邏輯關系,即數(shù)據(jù)的邏輯結構 2.數(shù)據(jù)元素在計算機中的存儲關系,即數(shù)據(jù)的存儲結構 3.對各種數(shù)據(jù)結構進行的運算 考點4:數(shù)據(jù)結構分為兩大類型：線性結構與非線性結構。 （1）如果一個非空的數(shù)據(jù)結構滿足下列兩個條件： ① 有且只有一個根結點； ② 每一個結點最多有一個前件，也最多有一個后件。 則稱該數(shù)據(jù)結構為線性結構。 如果一個數(shù)據(jù)結構不是線性結構，則稱之為非線性結構。 考點5:線性表 特點: (1) 線性表中所有元素所占的存儲空間是連續(xù)的 (2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的 考點5: 棧的基本概念 棧（stack）是一種特殊的線性表，是限定只在一端進行插入與刪除的線性表。 棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。 考點6:隊列的基本概念 隊列是只允許在一端進行刪除,在另一端進行插入的順序表,通常將允許刪除的這一端稱為隊頭，允許插入的這一端稱為隊尾。當表中沒有元素時稱為空隊列。即先進先出表。循環(huán)隊列就是將隊列存儲空間的最后一個位置繞到第一個位置,形成邏輯上的環(huán)狀空間,供隊列循環(huán)使用 考點7: 鏈表 在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。其中指針用于指向該結點的前一個或后一個結點（即前件或后件）。 考點8:二叉樹性質 (1) 在樹結構中,每一個結點只有一個前件,稱為父結點,沒有父結點的只有一個,成為根結點 (2) 沒有后件的結點成為葉子結點 (3) 一個結點所擁有的后件個數(shù)稱為該結點的度,在樹中,所有結點中最大的度稱為樹的度 (4) 樹的最大層次稱為樹的深度 (5) 在二叉樹的第k層上,最多有2^(k-1)個結點 (6) 深度為m的二叉樹最多有2^m-1個結點 (7) 任意一棵二叉樹,度為0的結點(即葉子結點)總是比度為2的結點多一個 (8) 滿二叉樹:除最后一層外,每一層上的所有結點都有兩個子節(jié)點 (9) 完全二叉樹:除最后一層外,每一層上的結點數(shù)都達到最大值,在最后一層上只缺少右邊的若干結點 考點9: 二叉樹的遍歷 根據(jù)訪問根結點的次序，二叉樹的遍歷分為三類：前序遍歷、中序遍歷和后序遍歷。 （1）前序遍歷 先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；并且在遍歷左、右子樹 時，仍需先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。 （2）中序遍歷 先遍歷左子樹、然后訪問根結點，最后遍歷右子樹；并且，在遍歷左、右子 樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。例如，對圖 1-1 中的二叉樹進行中序遍歷的結果（或稱為該二叉樹的中序序列） （3）后序遍歷 先遍歷左子樹、然后遍歷右子樹，最后訪問根結點；并且，在遍歷左、右子 樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。 考點10:各種排序的復雜度 (1)順序查找需要比較n 次 (2)冒泡排序在最壞的情況下需要比較次數(shù)為n(n-1)/2 。 (3)簡單插入排序法，最壞情況需要n(n-1)/2 次比較； (4)希爾排序法，最壞情況需要O(n1.5)次比較。 (5) 簡單選擇排序法，最壞情況需要n(n-1)/2 次比較； (6)堆排序法，最壞情況需要O(nlog2n)次比較。 第二章:程序設計基礎 考點1:結構化程序設計的原則 (1) 自頂向上：先考慮整體，再考慮細節(jié)；先考慮全局目標，再考慮局部目標； (2) 逐步求精：對復雜問題應設計一些子目標作為過渡，逐步細化； (3) 模塊化：把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模塊。 (4) 限制使用goto 語句：在程序開發(fā)過程中要限制使用goto 語句。 考點2:結構化程序的基本結構 結構化程序的基本結構有三種類型：順序結構、選擇結構和循環(huán)結構。 考點3: 面向對象方法涵蓋對象及對象屬性與方法、類、繼承、多態(tài)性幾個基本要素。 對象是面向對象方法中最基本的概念,主要特點: (1)標識惟一型 (2)分類性（3）多態(tài)性 (4)封裝性 (5)模塊獨立性好 考點4:消息:對象間的相互合作需要一個機制來協(xié)助進行,這個機制就是消息 考點5:繼承是面向對象的方法的一個主要特征,分為單繼承和多重繼承 第三章:軟件工程基礎 考點1: 計算機軟件是包括程序、數(shù)據(jù)以及相關文檔的完整集合,軟件工程包括3 個要素：方法、工具和過程 考點2: 軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為軟件生命周期。 軟件生命周期還可以分為軟件定義、軟件開發(fā)、軟件運行維護階段 軟件定義階段包括:可行性研究、需求分析 軟件開發(fā)階段包括:概要設計、詳細設計、實現(xiàn)、測試 軟件維護階段包括:使用、維護、退役 考點3:軟件工程的理論和技術性研究主要包括:軟件開發(fā)技術和軟件工程管理 考點4:數(shù)據(jù)流圖圖符的含義 圓形表示加工,箭頭表示數(shù)據(jù)流,等于號表示存儲文件,矩形表示源、潭 考點5:數(shù)據(jù)字典:是結構化分析方法的核心,數(shù)據(jù)字典是對所有與系統(tǒng)相關的數(shù)據(jù)元素的一個有組織的列表 考點6:軟件需求規(guī)格說明書是需求分析階段的最后成果 考點7:模塊獨立性 衡量模塊獨立性的定性標準:內聚性與耦合性 內聚性:是一個模塊內部各個元素間彼此結合的緊密程度的度量 耦合性:模塊間互相連接的緊密程度的度量 一個優(yōu)秀的設計應盡量做到高內聚、低耦合 考點8:典型的數(shù)據(jù)流類型有兩種:變換型和事務型 考點9:程序流程圖圖符的含義 考點10:軟件測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程 靜態(tài)測試是由人工進行的測試 動態(tài)測試是基于計算機的測試 考點11:白盒測試主要方法:邏輯覆蓋、基本路徑測試 黑盒測試主要方法:等價類劃分法、邊界值分析法、錯誤推測法、因果圖等 軟件測試過程一般按4個步驟來進行:單元測試、集成測試、驗收測試、系統(tǒng)測試 考點12:程序調試的任務是診斷和改正程序中的錯誤,與測試不同,軟件測試是盡可能多的發(fā)現(xiàn)錯誤 第四章:數(shù)據(jù)庫設計基礎 考點1:數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)庫的機構,它是一種系統(tǒng)軟件,負責數(shù)據(jù)庫中的數(shù)據(jù)組織,數(shù)據(jù)操縱，數(shù)據(jù)維護,控制及保護和數(shù)據(jù)服務等 考點2:數(shù)據(jù)庫系統(tǒng)提供的數(shù)據(jù)語言: (1) 數(shù)據(jù)定義語言:該語言負責數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構建 (2) 數(shù)據(jù)操縱語言負責數(shù)據(jù)的操縱,包括查詢及增、刪、改等 (3) 數(shù)據(jù)控制語言負責數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復等 考點3:數(shù)據(jù)庫系統(tǒng)由如下幾部分組成:數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理員、硬件平臺與軟件平臺 考點4:數(shù)據(jù)獨立性是數(shù)據(jù)與程序間的互不依賴性,即數(shù)據(jù)庫中數(shù)據(jù)獨立于應用程序而不依賴于應用程序,數(shù)據(jù)獨立性分為物理獨立性和邏輯獨立性 考點5:數(shù)據(jù)庫的三級模式 (1) 概念模式:是數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結構的描述,是全體用戶公共數(shù)據(jù)視圖 (2) 外模式:是用戶的數(shù)據(jù)視圖,也就是用戶所見到的數(shù)據(jù)模式 (3) 內模式:它給出了數(shù)據(jù)庫物理存儲結構與物理存取方法 考點6:數(shù)據(jù)模型所描述的內容有三個方面: (1) 數(shù)據(jù)結構:主要描述數(shù)據(jù)的類型、內容、性質以及數(shù)據(jù)間的聯(lián)系 (2) 數(shù)據(jù)操作:主要描述在相應數(shù)據(jù)結構上的操作類型與操作方式 (3) 數(shù)據(jù)約束:主要描述數(shù)據(jù)結構內數(shù)據(jù)間的語法、語義聯(lián)系 考點7:E-R模型 (1)E-R模型由三個基本概念組成:實體、聯(lián)系和屬性 (2)在E-R圖示法中:矩形表示實體集,橢圓形表示屬性,菱形表示聯(lián)系 考點8:關系模型的約束包括實體完整性約束、參照完整性約束、用戶自定義完整性約束 考點9:關系代數(shù) 并運算:關系R與S經(jīng)并運算后所得到的關系是由那些在R內或在S內的有序組 交運算:關系R與S經(jīng)交運算后所得到的關系是由那些即在R內又在S內的有序組 差運算:關系R與S經(jīng)差運算后所得到的關系是由那些在R內但不在S內的有序組 自然連接: 考點10:E-R圖與關系的轉換 E-R圖中實體與聯(lián)系都可以轉換成關系,屬性也可以轉換成關系的屬性
|