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