二級公共基礎(chǔ)知識總結(jié)(特精)

1、二級公共基礎(chǔ) - 1 -二級公共基礎(chǔ)知識總結(jié)第一章 數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法 算法不等于程序, 也不等計算機(jī)方法,(1可行性;(2解釋,不允許有多義性;(3 算法基本設(shè)計方法:列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯 法。 算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。二級公共基礎(chǔ) - 2 - 1.2 數(shù)據(jù)結(jié)構(gòu)的基本基本概念數(shù)據(jù)結(jié)構(gòu)研究的三個方面:(1 數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系, ( 2 (3對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 數(shù)據(jù)的邏輯結(jié)構(gòu)包含:(1表示數(shù)據(jù)元素的信息;(2表示各數(shù)據(jù)元素之

2、間的前后件關(guān)系。線性結(jié)構(gòu)條件:(1有且只有一個根結(jié)點; 非空線性表的結(jié)構(gòu)特征:(1且只有一個根結(jié)點 a1,它無前件;(2有且只有一個終端結(jié)點 an ,它無后件;二級公共基礎(chǔ) - 3 -(3除根結(jié)點與終端結(jié)點外,其他所有結(jié)點有且只有一個前件,也有且只有一個后件。結(jié)點個數(shù) n n=0 線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點:(1線性表中所有元素的所占的存儲空間是連續(xù)的;(2線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。 ai 的存儲地址為:ADR(ai=ADR(a1+(i-1k,素的地址, k 代表每個元素占的字節(jié)數(shù)。 隊列運(yùn)算包括(1入隊運(yùn)算:從隊尾插入一個元素; (2退隊運(yùn)算:從 隊

3、頭刪除一個元素。循環(huán)隊列:s=0表示隊列空, s=1且 front=rear表示隊列滿1. 5 線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元,這種存儲單元稱為存儲結(jié)二級公共基礎(chǔ) - 4 - 結(jié)點由兩部分組成:(1 (2 用于存在鏈?zhǔn)酱鎯Y(jié)構(gòu)中,存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù),各數(shù)據(jù)結(jié)點的 存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致,而數(shù)據(jù)元素之間的邏輯 關(guān)系是由指針域來確定的。 兩棵子樹,且分別稱為該結(jié)點的左子樹與右子樹。二叉樹的基本性質(zhì):(1在二叉樹的第 k 層上,最多有 2k-1(k1 個結(jié)點;(2深度為 m 的二叉樹最多有 2m-1個結(jié)點;(3度為 0的結(jié)點(即葉子結(jié)點總是比度為

4、2的結(jié)點多一個;二級公共基礎(chǔ) - 5 -(4具有 n 個結(jié)點的二叉樹,其深度至少為 log2n+1,其中 log2n表 示取 log2n 的整數(shù)部分;(5具有 n 個結(jié)點的完全二叉樹的深度為 log2n+1;(6設(shè)完全二叉樹共有 n 個結(jié)點。如果從根結(jié)點開始,按層序(每一層 從左到右用自然數(shù) 1, 2, .n 給結(jié)點進(jìn)行編號(k=1,2.n ,有以下 結(jié)論:若 k=1,則該結(jié)點為根結(jié)點,它沒有父結(jié)點;若 二叉樹的遍歷: 子樹; 子樹;二級公共基礎(chǔ) - 6 - 問根結(jié)點。1. 7 查找技術(shù)順序查找的使用情況:(1線性表為無序表;(2表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。對于長度為 n 最 壞情況只需比較 1. 8

5、 排序技術(shù)交換類排序法:(1 (2快速排序法。 插入類排序法:(1(2選擇類排序法:(, 最壞情況需要 (2 第二章 程序設(shè)計基礎(chǔ)2. 1 程序設(shè)計設(shè)計方法和風(fēng)格如何形成良好的程序設(shè)計風(fēng)格1、源程序文檔化; 2、數(shù)據(jù)說明的方法;3、語句的結(jié)構(gòu); 4、輸入和輸出。 二級公共基礎(chǔ) - 7 -2. 2 結(jié)構(gòu)化程序設(shè)計 結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點:(1順序結(jié)構(gòu):一種簡單的程序設(shè)計,最基本、最常用的結(jié)構(gòu);(2(3段。2. 3 面向?qū)ο蟮某绦蛟O(shè)計面向?qū)ο蟮某绦蛟O(shè)計:以 60制的 SIMULA 語言為標(biāo)志。面向?qū)ο蠓椒ǖ膬?yōu)點:(1(2穩(wěn)定性好; (3(4(5 可以用來表示客觀世界中的任何實 體,對象是實體的

6、抽象。面向?qū)ο蟮某绦蛟O(shè)計方法中的對象是系統(tǒng)中用來描述客觀事物的一個實 體,是構(gòu)成系統(tǒng)的一個基本單位,由一組表示其靜態(tài)特征的屬性和它可執(zhí) 行的一組操作組成。二級公共基礎(chǔ) - 8 - 對象的基本特點: (1標(biāo)識惟一性; (2分類性;(3多態(tài)性;(4封裝性; 第三章 軟件工程基礎(chǔ)3. 1 軟件工程基本概念 軟件的特點包括:二級公共基礎(chǔ) - 9 -(1軟件是一種邏輯實體;(2軟件的生產(chǎn)與硬件不同,它沒有明顯的制作過程;(3軟件在運(yùn)行、使用期間不存在磨損、老化問題;(4軟件的開發(fā)、運(yùn)行對計算機(jī)系統(tǒng)具有依賴性,受計算機(jī)系統(tǒng)的限制, 這導(dǎo)致了軟件移植的問題;(5軟件復(fù)雜性高,成本昂貴;(6軟件開發(fā)涉及諸多的

7、社會因素。 (1 P (2 D (3 C(4 A 是:(1可行性研究與計劃制定;(2需求分析;二級公共基礎(chǔ) - 10 -(3軟件設(shè)計;(4軟件實現(xiàn);(5軟件測試;(6運(yùn)行和維護(hù)。軟件工程的目標(biāo)和與原則: 軟件管理學(xué)包括人員組織、 進(jìn)度安排、 質(zhì)量保證、 配置管理、 項目計劃等。 軟件工程原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、 完備性和可驗證性。3. 2 結(jié)構(gòu)化分析方法 二級公共基礎(chǔ) - 11 - 結(jié)構(gòu)化分析方法的實質(zhì):著眼于數(shù)據(jù)流,自頂向下,逐層分解,建立系統(tǒng) 的處理流程,以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具 , 建立系統(tǒng)的邏輯模型。 數(shù)據(jù)流圖:描述數(shù)據(jù)處理過程的工具,它直接支持系

8、統(tǒng)功能建模。間計算結(jié)果有共同的理解。結(jié)論, 并列關(guān)系、 軟件需求規(guī)格說明書的特點:(1正確性;(2無岐義性;(3完整性;二級公共基礎(chǔ) - 12 -(4可驗證性;(5一致性;(6可理解性;(7可追蹤性。3. 3 結(jié)構(gòu)化設(shè)計方法 設(shè)計;后進(jìn)行低層次的過程設(shè)計;穿插進(jìn)行數(shù)據(jù)設(shè)計和接口設(shè)計。 軟件概要設(shè)計的基本任務(wù)是:二級公共基礎(chǔ) - 13 -(1設(shè)計軟件系統(tǒng)結(jié)構(gòu); (2數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計;(3編寫概要設(shè)計文檔; (4概要設(shè)計文檔評審。模塊用一個矩形表示,箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息。 還可用帶實心圓的箭頭表示傳遞的是控制信息,空心圓箭心表

9、示傳遞的是 數(shù)據(jù)。 的在于檢驗它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實際結(jié)果之間的 差別。 軟件測試的目的:發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。靜態(tài)測試包括代碼檢查、 靜態(tài)結(jié)構(gòu)分析、 代碼質(zhì)量度量。 不實際運(yùn)行軟件,二級公共基礎(chǔ) - 14 -主要通過人工進(jìn)行。動態(tài)測試:是基本計算機(jī)的測試, 主要包括白盒測試方法和黑盒測試方法。 CAO 作的驗證。主要方法有邏輯覆蓋、基本基路徑測試。軟件測試過程一般按 4認(rèn)測試和系統(tǒng)測試。3. 5 程序的調(diào)試程序調(diào)試的基本步驟:(1錯誤定位;(2(3是主要的設(shè)計手段, 而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。(1強(qiáng)行排錯法;(2回溯法;(3原因排除法。第四章 數(shù)據(jù)庫設(shè)計基礎(chǔ)二級公共基礎(chǔ)

10、 - 15 -4. 1 數(shù)據(jù)庫系統(tǒng)的基本概念數(shù)據(jù):實際上就是描述事物的符號記錄。數(shù)據(jù)的特點:有一定的結(jié)構(gòu),有型與值之分,如整型、實型、字符型等。 而數(shù)據(jù)的值給出了符合定型的值,如整型值 15。 是多種應(yīng)用數(shù)據(jù)的集成,并可被各個應(yīng)用程序共享。 點。數(shù)據(jù)庫管理系統(tǒng)功能:(1(2取方法與手段;(3(4(5(6數(shù)據(jù)的服務(wù):如拷貝、轉(zhuǎn)存、重組、性能監(jiān)測、分析等。為完成以上六個功能,數(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ā)控二級公共基礎(chǔ) -

11、 16 -制、故障恢復(fù)等。數(shù)據(jù)語言按其使用方式具有兩種結(jié)構(gòu)形式:交互式命令 (又稱自含型或自 主型語言 宿主型語言(一般可嵌入某些宿主語言中 。數(shù)據(jù)庫管理員:對數(shù)據(jù)庫進(jìn)行規(guī)劃、 設(shè)計、 維護(hù)、 監(jiān)視等的專業(yè)管理人員。 完整的、統(tǒng)一的、管理和數(shù)據(jù)共享的能力。層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段關(guān)系數(shù)據(jù)庫系統(tǒng)階段、數(shù)據(jù)的高共享性與低冗余性 、 、數(shù)據(jù)統(tǒng)一管理與控制。(3內(nèi)模式:又稱物理模式,它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取 方法。數(shù)據(jù)庫系統(tǒng)的兩級映射:(1概念模式到內(nèi)模式的映射;(2外模式到概念模式的映射。二級公共基礎(chǔ) - 17 -4.2 數(shù)據(jù)模型數(shù)據(jù)模型的概念:是數(shù)據(jù)特征的抽象,從抽象層次上描述了

12、系統(tǒng)的靜態(tài)特 征、動態(tài)行為和約束條件,為數(shù)據(jù)庫系統(tǒng)的信息表與操作提供一個抽象的 框架。描述了數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作及數(shù)據(jù)約束。(1 (2 從所有侯選健中選 取一個作為用戶使用的鍵稱主鍵。 表 A 中的某屬性是某表 B 的鍵, 則稱該 屬性集為 A 的外鍵或外碼。二級公共基礎(chǔ) - 18 -關(guān)系中的數(shù)據(jù)約束:(1實體完整性約束:約束關(guān)系的主鍵中屬性值不能為空值;(2參照完全性約束:是關(guān)系之間的基本約束;(3用戶定義的完整性約束:它反映了具體應(yīng)用中數(shù)據(jù)的語義要求。4.3關(guān)系代數(shù) SA 方 法用自頂向下、逐層分解的方式分析系統(tǒng)。用數(shù)據(jù)流圖表達(dá)數(shù)據(jù)和處理過 程的關(guān)系。對數(shù)據(jù)庫設(shè)計來講,數(shù)據(jù)字典是進(jìn)行詳細(xì)的數(shù)據(jù)收集和數(shù)據(jù)分 析所獲得的主要結(jié)果。 二級公共基礎(chǔ) - 19 -據(jù)流(可以是數(shù)據(jù)項,也可以是數(shù)據(jù)結(jié)構(gòu) 、數(shù)據(jù)存儲、處理過程。 (1集中式模式設(shè)計法(適用于小型或并不復(fù)雜的單位或部門 ;(2視圖集成設(shè)計法。設(shè)計方法:E-R 模型與視圖集成。 關(guān)系視圖的主要作用:(1提供數(shù)據(jù)邏輯獨立性;(2能適應(yīng)用戶對數(shù)據(jù)的不同需求;(3有一定數(shù)據(jù)保密功能。存取路徑, 一般 RDBMS 中留(1(2(3數(shù)據(jù)庫