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