數(shù)據(jù)結(jié)構(gòu)與算法講義

數(shù)據(jù)結(jié)構(gòu)與算法講義數(shù)據(jù)結(jié)構(gòu)與算法講義數(shù)據(jù)結(jié)構(gòu)與算法講義學習目標objective1了解《公共基礎(chǔ)知識》的內(nèi)容2掌握算法的基本概念

《公共基礎(chǔ)知識》的內(nèi)容01數(shù)據(jù)結(jié)構(gòu)與算法程序設計基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫設計基礎(chǔ)四個部分1234第一章數(shù)據(jù)結(jié)構(gòu)及算法1算法的概念、時間復雜度與空間復雜度2數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的定義3棧的定義及其運算、線性鏈表的存儲方式4樹與二叉樹的相關(guān)概念5查找與排序方法重要知識點：第二章程序設計基礎(chǔ)重要知識點：結(jié)構(gòu)化程序設計方法的四個原則01對象、類、消息、繼承的概念類與實例的區(qū)別02經(jīng)?？疾榻Y(jié)構(gòu)化程序設計的原則、面向?qū)ο蠓椒ǖ幕靖拍钴浖母拍睢④浖芷诩案麟A段所包含的活動1概要設計與詳細設計的概念、模塊獨立性及其度量的標準、詳細設計常用的工具2軟件測試的目的和4個步驟3軟件調(diào)試的任務4第三章軟件工程基礎(chǔ)重要知識點：01請02請02數(shù)據(jù)模型3個描述內(nèi)容、E-R模型的概念及其E-R圖表示法、關(guān)系操縱、關(guān)系模型三類數(shù)據(jù)約束第四章數(shù)據(jù)庫設計基礎(chǔ)01數(shù)據(jù)庫及其相關(guān)的概念03關(guān)系模型的基本操作、關(guān)系代數(shù)中的擴充運算04數(shù)據(jù)庫設計的4個階段重要知識點：算法的概念029算法復雜度算法的基本概念0102兩個考點考核幾率30%，分值為2分，此考點為識記內(nèi)容，了解算法中對數(shù)據(jù)的基本運算。考試情況算法的基本概念1.算法的定義對解題方案準確而完整的描述稱為算法算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則,是計算機解題的過程(計算的方法)。在這個過程中，無論是形成解題思路(推理實現(xiàn)的算法),還是編寫程序(操作實現(xiàn)的算法)，都是在實施某種算法。2.算法的基本特征一個算法應該具有以下五個重要的特征。一個算法必須保證執(zhí)行有限步之后結(jié)束有窮性確定性輸入輸出可行性算法的每一步驟必須有確切的定義0個或多個輸入，運算對象的初始情況有一個或多個輸出，沒有輸出的算法是毫無意義的算法原則上能夠精確地運行，用筆和紙做有限次運算后即可完成圖形法偽碼描述法3.算法的表示方法1.流程圖2.N-S圖輸入園的半徑，計算園的面積問題計算園面積輸入半徑的值給rS=3.14*r*r輸出S的值N-S圖：

已知半徑，求園的面積INPUTrS=3.14*r*rPTINTS求園面積對數(shù)據(jù)對象的運算和操作01算法的控制結(jié)構(gòu)024.算法的兩個基本要素算術(shù)運算邏輯運算關(guān)系運算數(shù)據(jù)傳輸基本的運算和操作順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)控制結(jié)構(gòu)考點2：算法的復雜度考試幾率70%，分值為2分，此考點為重點識記內(nèi)容，掌握算法時間復雜度、空間復雜度的概念?？荚嚽闆r執(zhí)行這個算法所需要的計算工作量時間復雜度空間復雜度執(zhí)行這個算法所需要的內(nèi)存算法在執(zhí)行過程中臨時占用的存儲空間算法優(yōu)劣的主要標準大致等于計算機執(zhí)行一種簡單操作所需的平均時間與算法中進行簡單操作的次數(shù)的乘積。時間復雜度存儲算法本身所占用的存儲空間、算法中的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個部