



版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、精品文檔數(shù)據(jù)結(jié)構(gòu)與算法算法的基本概念1. 算法:是對問題處理方案的正確而完整的描述,是求解問題的方法,是指令的有效序列。2. 具有 5 個特性:( 1) 有窮性(在有窮步后完成)算法程序的運行時間是有限的( 2) 確定性(每一步都有確定的含義)( 3) 可行性( 4) 輸入(一個算法有零個或多個輸入)( 5) 輸出(一個算法有一個或多個輸出)3. 算法的復雜度包括:時間復雜度和空間復雜度。二者沒有必然的聯(lián)系。時間復雜度:執(zhí)行算法所需要的計算工作量或基本運算次數(shù)??臻g復雜度:算法所需要的空間的度量。數(shù)據(jù)結(jié)構(gòu)的定義1. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的操作數(shù)據(jù)的邏輯結(jié)構(gòu): 數(shù)據(jù)的
2、外部結(jié)構(gòu), 指各數(shù)據(jù)元素之間的邏輯關(guān)系, 反映人們對數(shù)據(jù)含義的解釋。 包括:線性結(jié)構(gòu)(線性表、棧、隊列)和非線性結(jié)構(gòu)(樹和圖)數(shù)據(jù)的存儲結(jié)構(gòu):數(shù)據(jù)的物理結(jié)構(gòu),指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示。一個邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)。 線性表:線性表中元素的個數(shù)n( n>=0)定義為線性表的長度。順序存儲是線性表的一種最常用的存儲方式。線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是隨機存取的存儲結(jié)構(gòu)和順序存取的存儲結(jié)構(gòu)。1. 棧:是限定在表尾進行插入和刪除操作的線性表。具有記憶功能只能順序存儲 (錯)允許插入和刪除的一端叫棧頂。另一端叫棧底。后進先出的線性表2 隊列:是限定在一端插入而在另一端刪
3、除,插入端叫隊尾,刪除端叫對頭。先進先出的線性表.精品文檔3 棧和隊列的順序存儲結(jié)構(gòu)循環(huán)隊列屬于線性表存儲結(jié)構(gòu)中順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的前者。 樹1. 定義 : 樹的結(jié)點、度(結(jié)點的度)、葉子(終端結(jié)點) 、數(shù)的度、深度、有序樹和無序數(shù)2. 二叉樹:結(jié)點至多有兩棵子樹,并且二叉樹的子樹有之分,次序不能顛倒。性質(zhì):在二叉樹的第 i 層上至多有 2i-1 個結(jié)點 深度為 k 的二叉樹至多有 2k-1 個結(jié)點。 對任一個二叉樹T,如果其葉子(終端結(jié)點數(shù))為n,度為二的結(jié)點數(shù)為m,則 n=m+1. 具有 n 個結(jié)點的完全二叉樹的深度為k+1,其中 k 是 2n 的整數(shù)部分。2. 二叉樹的遍歷先序遍
4、歷(根左右)中序遍歷(左根右)后序遍歷(左右根)查找算法( 1)順序查找順序查找的平均查找長度為(n+1) 2,最壞的情況下比較的次數(shù)為n(2)二分查找最壞情況下次數(shù)為log2n限定于順序存儲的有序線性表排序算法( 1)插入類排序直接插入排序折半插入排序希爾排序 . ( 2)交換類排序冒泡排序最壞情況下的比較次數(shù)n(n-1) 2快速排序最壞情況下的比較次數(shù)n(n-1) 2(3) 選擇類排序.精品文檔例題精選 :1.設(shè)一棵完全二叉樹共有 699個結(jié)點 , 則在該二叉樹中的葉子結(jié)點數(shù)為 :3502.已知二叉樹后序遍歷序列是dabec, 中序遍歷序列是debac, 它的前序遍歷序列為:cedba3.
5、 要求內(nèi)存量最大的是:歸并排序4. 在數(shù)據(jù)結(jié)構(gòu)中,與所使用的計算機無關(guān)的是數(shù)據(jù)的是:邏輯結(jié)構(gòu)5. 棧底至棧頂依次存放元素在第五個元素 E 入棧前,棧中元素可以出棧,則出棧序列可能是: DCBEA6. 已知數(shù)據(jù)表 A 中每個元素距其最終位置不遠,為節(jié)省時間,應(yīng)采取的算法是:直接插入排序7. 用鏈式表示線性表的優(yōu)點是:便于插入和刪除操作。程序設(shè)計基礎(chǔ)1. 程序設(shè)計風格好的程序設(shè)計風格有利于提高程序的正確性、可讀性、 可維護性和可用性。要是程序有良好的風格概括起來可以分為4 部分:源程序文檔化、 數(shù)據(jù)說明、 語句結(jié)構(gòu)、 輸入輸出方法。用戶所定義的標示符必須以字母或下劃線開頭。大、小寫字母代表不同標識
6、。2.結(jié)構(gòu)化程序設(shè)計( 1)結(jié)構(gòu)化程序設(shè)計的基本特征:程序有 3 中基本結(jié)構(gòu)組成:順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)整個程序采用模塊化結(jié)構(gòu)。模塊劃分的原則:模塊內(nèi)具有高內(nèi)聚度、模塊間具有低耦合度。有限的使用轉(zhuǎn)移語句,只限定在一個結(jié)構(gòu)的內(nèi)部跳轉(zhuǎn),不允許從一個結(jié)構(gòu)跳到另一結(jié)構(gòu)。程序設(shè)計時采用“至頂向下、逐步詳細”的實施方法。( 2)結(jié)構(gòu)化程序設(shè)計的3 種基本結(jié)構(gòu):順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)3 種基本結(jié)構(gòu)組成的算法只能完成符合結(jié)構(gòu)化的任務(wù)( 3)結(jié)構(gòu)化程序設(shè)計的方法:逐步求精和模塊化程序設(shè)計方法。結(jié)構(gòu)化設(shè)計的總體思想是采用模塊化結(jié)構(gòu),自上而下,逐步求精。3. 面向?qū)ο蟪绦蛟O(shè)計 基本概念.精品文檔對象:系
7、統(tǒng)中運行的實體,是有特殊屬性(數(shù)據(jù))和方法的實體類:由屬性和方法構(gòu)成。一組具有相同的數(shù)據(jù)結(jié)構(gòu)和相同的行為特征的對象的集合稱為類在面對對象的方法中,類的實例稱為對象面向?qū)ο蟪绦蛟O(shè)計特征的是:繼承性、多態(tài)性、封裝性在面向?qū)ο蟮姆椒ㄖ?,實現(xiàn)信息隱蔽是依靠對象的封裝任何對象都必須有繼承性(錯)例題精選 :1. 在面對對象的方法中,一個對象請求另一個對象為其服務(wù)的方式是通過發(fā)送:信息2.面對對象的設(shè)計方法與傳統(tǒng)的面向過程的方法有本質(zhì)的區(qū)別, 它的基本原理是: 使用現(xiàn)實世界的概念抽象的思考問題從而自然地解決問題.3. 結(jié)構(gòu)化方法中 , 軟件功能分解屬于軟件開發(fā)階段中的總體設(shè)計4. 結(jié)構(gòu)化程序設(shè)計主要強調(diào)的
8、是 : 程序的易讀性5. 面向?qū)ο蟮脑O(shè)計程序主要考慮的是: 提高軟件的可重用性6. 類通過接口與外界發(fā)生關(guān)系 .軟件工程基礎(chǔ)1. 軟件工程的基本概念(1) 定義 : 軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合。軟件包括系統(tǒng)軟件和應(yīng)用軟件(2) 軟件工程的基本思想是軟件開發(fā)中,應(yīng)用工程化原則進行軟件開發(fā),并將這個思想貫穿在軟件開發(fā)的整個過程中。軟件工程的 3 要素:方法、工具和過程(3) 軟件的生命周期:從軟件定義、開發(fā)、使用、維護到報廢為止的整個過程。分三階段:設(shè)計階段、開發(fā)階段、維護階段包括:問題定義、可行性分析、需求分析、總體設(shè)計、詳細設(shè)計、編碼、測試和維護問題定義:確定開發(fā)的任務(wù)可行性分析:確定問
9、題的可行性需求分析:對用戶要求進行分析,明確目標系統(tǒng)要做什么總體設(shè)計:把軟件功能轉(zhuǎn)化為所需要的體系結(jié)構(gòu),即如何解決問題。詳細設(shè)計:怎樣具體的解決問題.精品文檔2. 結(jié)構(gòu)化分析方法( 1)結(jié)構(gòu)化分析(SA)是面向數(shù)據(jù)流進行需求分析的方法SA 方法的基本思想正是運用了分解和抽象兩個基本手段,采用:自頂向下,逐步分解的分析思路。( 2)數(shù)據(jù)流圖基本圖形符號:在結(jié)構(gòu)化方法中, 用數(shù)據(jù)流程圖(DFD)作為描述工具的軟件開發(fā)階段是: 需求分析(3) 數(shù)據(jù)字典在結(jié)構(gòu)化分析的數(shù)據(jù)流圖中, 利用數(shù)據(jù)字典對其中的圖形元素進行確切解釋.3. 軟件設(shè)計( 1)概要設(shè)計(總體設(shè)計)包括兩個主要階段:系統(tǒng)設(shè)計 (確定具體
10、的實現(xiàn)方案) 和結(jié)構(gòu)設(shè)計(確定每個系統(tǒng)的模塊組成及模塊間的關(guān)系)模塊之間聯(lián)系越緊密, 其耦合性就越強, 模塊的獨立性就越差;一個模塊內(nèi)個要素聯(lián)系越緊密,則它的內(nèi)聚性就越高。模塊劃分原則:高內(nèi)聚低耦合( 2)詳細設(shè)計結(jié)構(gòu)化程序設(shè)計的要點:采用自頂向下、 逐步求精的程序設(shè)計方法,一個程序只有一個入口和一個出口。詳細設(shè)計的常用工具:程序流程圖、盒圖、PAD和 PDL( 3)軟件測試目的軟件測試的目的是盡可能多的發(fā)現(xiàn)程序中的錯誤。軟件測試方法:靜態(tài)測試和動態(tài)測試(黑盒測試法和白盒測試法)黑盒測試包括:等價分析法、邊值分析法、因果圖法和錯誤推測法.精品文檔白盒測試法測試的原則之一就是保證所測模塊中的每一
11、個獨立的路徑至少執(zhí)行一次。( 4)程序調(diào)試分為靜態(tài)調(diào)試和動態(tài)調(diào)試調(diào)試的目的 : 改正錯誤經(jīng)調(diào)試后還必須進行再測試( 5)軟件維護軟件維護就是在軟件已經(jīng)交付使用以后,為改正錯誤或滿足新的需求而修改軟件的過程。例題精選:1 分析的結(jié)果是產(chǎn)生需求規(guī)格說明書。2 軟件詳細設(shè)計的主要任務(wù)是確定每一個模塊的算法和使用的數(shù)據(jù)結(jié)構(gòu)。3 進行單元測試時,常用的方法時采用白盒測試,輔以黑盒測試。4 軟件工程的出現(xiàn)是由于軟件危機的出現(xiàn),人們提出了軟件工程學的原理設(shè)計軟件。5 數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合,通常包括4 個部分:數(shù)據(jù)項、數(shù)據(jù)流、數(shù)據(jù)存儲和數(shù)據(jù)加工。數(shù)據(jù)庫設(shè)計基礎(chǔ)1. 數(shù)據(jù)庫( 1) 數(shù)據(jù)庫設(shè)計的根本目的
12、是要解決數(shù)據(jù)共享的問題。( 2) 數(shù)據(jù)庫的特點:數(shù)據(jù)按一定的數(shù)據(jù)模型組織和存儲。 冗余度較小 數(shù)據(jù)的獨立性較高。 數(shù)據(jù)獨立性: 數(shù)據(jù)的組織結(jié)構(gòu)和存儲方法與應(yīng)用程序互不依賴、彼此獨立。易擴展可為多種用戶共享2. 數(shù)據(jù)庫管理系統(tǒng)( DBMS)位于用戶與操作系統(tǒng)之間的完成數(shù)據(jù)管理的系統(tǒng)軟件。3. 數(shù)據(jù)庫系統(tǒng)由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、應(yī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) 層次、網(wǎng)狀、關(guān)系模型層次模型:有且只有一個結(jié)點無雙親,其他結(jié)點只有一個雙親。用樹形結(jié)構(gòu)來表示各實體與實體之間的聯(lián)系。在關(guān)系數(shù)據(jù)庫中, 把數(shù)據(jù)表示成二維表, 每個二維表稱為關(guān)系。 一個關(guān)系對應(yīng)一張二維表。關(guān)系的屬性名稱為關(guān)系模式。5. 關(guān)系運算( 1)并( 2)差( 3)交( 4)笛卡爾積(×)6. 專門關(guān)系運算:選擇、連接和投影( 1)從關(guān)系中找到滿足條件的所有元組
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- T/SHPTA 046-2023木工封邊用反應(yīng)型聚氨酯熱熔膠
- 教育機構(gòu)中數(shù)字化圖書館的建設(shè)與發(fā)展
- 2025設(shè)備租賃合同新范文
- 2025水果買賣合同模板
- 以數(shù)據(jù)為基礎(chǔ)的老年健康管理與研究應(yīng)用
- 一建承攬合同解除協(xié)議書
- 教育數(shù)字化資源的優(yōu)化與共享策略
- 公司改制資產(chǎn)移交協(xié)議書
- 合作銷售紅木家私協(xié)議書
- 婚前財產(chǎn)轉(zhuǎn)讓合同范本
- 批判教育學的流派和代表人物及其觀點
- 三年級下學期音樂復習題
- 農(nóng)網(wǎng)配電營業(yè)工復習題
- 電氣畢業(yè)論文-基于-plc自動門控制設(shè)計
- 煉鋼廠風險分級管控清單連鑄區(qū)域
- 新時期農(nóng)村初中語文教學中滲透心理健康教育的研究 論文
- 女性中醫(yī)保健智慧樹知到答案章節(jié)測試2023年暨南大學
- 餐飲員工入職登記表
- GA 1808-2022軍工單位反恐怖防范要求
- -衛(wèi)生資格-副高-護理學-副高-章節(jié)練習-??谱o理學-內(nèi)科疾病患者護理(多選題)(共42題)
- 一帶一路 匠心織竹-計劃書
評論
0/150
提交評論