計算機二年級基礎知識數據結構與算法◆算法的基本概念1.算法：是對問題處理方案的正確而完整的描述,是求解問題的方法,是指令的有效序列;2.具有5個特性：1有窮性在有窮步后完成算法程序的運行時間是有限的2確定性每一步都有確定的含義3可行性4輸入一個算法有零個或多個輸入5輸出一個算法有一個或多個輸出3.算法的復雜度包括：時間復雜度和空間復雜度;二者沒有必然的聯系;時間復雜度：執行算法所需要的計算工作量或基本運算次數;空間復雜度：算法所需要的空間的度量;◆數據結構的定義1.數據結構包括數據的邏輯結構、數據的存儲結構、數據的操作數據的邏輯結構：數據的外部結構,指各數據元素之間的邏輯關系,反映人們對數據含義的解釋;包括：線性結構線性表、棧、隊列和非線性結構樹和圖數據的存儲結構：數據的物理結構,指數據的邏輯結構在計算機中的表示;一個邏輯結構可以有多種存儲結構;◆線性表：線性表中元素的個數nn>=0定義為線性表的長度;順序存儲是線性表的一種最常用的存儲方式;線性表的順序存儲結構和線性表的鏈式存儲結構分別是隨機存取的存儲結構和順序存取的存儲結構;1.棧：是限定在表尾進行插入和刪除操作的線性表;具有記憶功能只能順序存儲錯允許插入和刪除的一端叫棧頂;另一端叫棧底;計算機二年級基礎知識全文共8頁，當前為第1頁。后進先出的線性表計算機二年級基礎知識全文共8頁，當前為第1頁。2隊列：是限定在一端插入而在另一端刪除,插入端叫隊尾,刪除端叫對頭;先進先出的線性表3棧和隊列的順序存儲結構循環隊列屬于線性表存儲結構中順序存儲結構和鏈式存儲結構的前者;◆樹1.定義:樹的結點、度結點的度、葉子終端結點、數的度、深度、有序樹和無序數2.二叉樹：結點至多有兩棵子樹,并且二叉樹的子樹有之分,次序不能顛倒;性質：★在二叉樹的第i層上至多有2i-1個結點★深度為k的二叉樹至多有2k-1個結點;★對任一個二叉樹T,如果其葉子終端結點數為n,度為二的結點數為m,則n=m+1.★具有n個結點的完全二叉樹的深度為k+1,其中k是㏒2n的整數部分;2.二叉樹的遍歷▼先序遍歷根—左—右▼中序遍歷左—根—右▼后序遍歷左—右—根◆查找算法1順序查找順序查找的平均查找長度為n+1／2,最壞的情況下比較的次數為n2二分查找最壞情況下次數為log2n限定于順序存儲的有序線性表◆排序算法1插入類排序▲直接插入排序▲折半插入排序▲希爾排序ｎ^１.５計算機二年級基礎知識全文共8頁，當前為第2頁。2交換類排序計算機二年級基礎知識全文共8頁，當前為第2頁。▲冒泡排序最壞情況下的比較次數nn-1／2▲快速排序最壞情況下的比較次數nn-1／23選擇類排序例題精選:1.設一棵完全二叉樹共有699個結點,則在該二叉樹中的葉子結點數為:3502.已知二叉樹后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列為：cedba3.要求內存量最大的是：歸并排序4.在數據結構中,與所使用的計算機無關的是數據的是：邏輯結構5.6.已知數據表A中每個元素距其最終位置不遠,為節省時間,應采取的算法是：直接插入排序7.用鏈式表示線性表的優點是：便于插入和刪除操作;程序設計基礎1.程序設計風格好的程序設計風格有利于提高程序的正確性、可讀性、可維護性和可用性;要是程序有良好的風格概括起來可以分為4部分：源程序文檔化、數據說明、語句結構、輸入輸出方法;用戶所定義的標示符必須以字母或下劃線開頭;大、小寫字母代表不同標識;2.結構化程序設計1結構化程序設計的基本特征：▼程序有3中基本結構組成：順序結構、選擇結構、循環結構▼整個程序采用模塊化結構;模塊劃分的原則：模塊內具有高內聚度、模塊間具有低耦合度;▼有限的使用轉移語句,只限定在一個結構的內部跳轉,不允許從一個結構跳到另一結構;▼程序設計時采用“至頂向下、逐步詳細”的實施方法;計算機二年級基礎知識全文共8頁，當前為第3頁。2結構化程序設計的3種基本結構：順序結構、選擇結構、循環結構計算機二年級基礎知識全文共8頁，當前為第3頁。3種基本結構組成的算法只能完成符合結構化的任務3結構化程序設計的方法：逐步求精和模塊化程序設計方法;結構化設計的總體思想是采用模塊化結構,自上而下,逐步求精;3.面向對象程序設計●基本概念對象：系統中運行的實體,是有特殊屬性數據和方法的實體類：由屬性和方法構成;一組具有相同的數據結構和相同的行為特征的對象的集合稱為類在面對對象的方法中,類的實例稱為對象面向對象程序設計特征的是：繼承性、多態性、封裝性在面向對象的方法中,實現信息隱蔽是依靠對象的封裝任何對象都必須有繼承性錯例題精選:1.在面對對象的方法中,一個對象請求另一個對象為其服務的方式是通過發送：信息2.面對對象的設計方法與傳統的面向過程的方法有本質的區別,它的基本原理是:使用現實世界的概念抽象的思考問題從而自然地解決問題.3.結構化方法中,軟件功能分解屬于軟件開發階段中的總體設計4.結構化程序設計主要強調的是:程序的易讀性5.面向對象的設計程序主要考慮的是:提高軟件的可重用性6.類通過接口與外界發生關系.軟件工程基礎1.軟件工程的基本概念1定義:軟件是程序、數據與相關文檔的集合;軟件包括系統軟件和應用軟件2軟件工程的基本思想是軟件開發中,應用工程化原則進行軟件開發,并將這個思想貫穿在軟件開發的整個過程中;計算機二年級基礎知識全文共8頁，當前為第4頁。軟件工程的3要素：方法、工具和過程計算機二年級基礎知識全文共8頁，當前為第4頁。3軟件的生命周期：從軟件定義、開發、使用、維護到報廢為止的整個過程;分三階段：設計階段、開發階段、維護階段包括：問題定義、可行性分析、需求分析、總體設計、詳細設計、編碼、測試和維護問題定義：確定開發的任務可行性分析：確定問題的可行性需求分析：對用戶要求進行分析,明確目標系統要做什么總體設計：把軟件功能轉化為所需要的體系結構,即如何解決問題;詳細設計：怎樣具體的解決問題2.結構化分析方法1結構化分析SA是面向數據流進行需求分析的方法SA方法的基本思想正是運用了分解和抽象兩個基本手段,采用：自頂向下,逐步分解的分析思路;2數據流圖基本圖形符號：在結構化方法中,用數據流程圖DFD作為描述工具的軟件開發階段是:需求分析3數據字典在結構化分析的數據流圖中,利用數據字典對其中的圖形元素進行確切解釋.3.軟件設計1概要設計總體設計◆包括兩個主要階段：系統設計確定具體的實現方案和結構設計確定每個系統的模塊組成及模塊間的關系◆模塊之間聯系越緊密,其耦合性就越強,模塊的獨立性就越差;一個模塊內個要素聯系越緊密,則它的內聚性就越高;模塊劃分原則：高內聚低耦合計算機二年級基礎知識全文共8頁，當前為第5頁。2詳細設計計算機二年級基礎知識全文共8頁，當前為第5頁。◆結構化程序設計的要點：采用自頂向下、逐步求精的程序設計方法,一個程序只有一個入口和一個出口;◆詳細設計的常用工具：程序流程圖、盒圖、PAD和PDL3軟件測試目的◆軟件測試的目的是盡可能多的發現程序中的錯誤;◆軟件測試方法：靜態測試和動態測試黑盒測試法和白盒測試法黑盒測試包括：等價分析法、邊值分析法、因果圖法和錯誤推測法白盒測試法測試的原則之一就是保證所測模塊中的每一個獨立的路徑至少執行一次;4程序調試分為靜態調試和動態調試調試的目的:改正錯誤經調試后還必須進行再測試5軟件維護軟件維護就是在軟件已經交付使用以后,為改正錯誤或滿足新的需求而修改軟件的過程;例題精選：1．分析的結果是產生需求規格說明書;2．軟件詳細設計的主要任務是確定每一個模塊的算法和使用的數據結構;3．進行單元測試時,常用的方法時采用白盒測試,輔以黑盒測試;4．軟件工程的出現是由于軟件危機的出現,人們提出了軟件工程學的原理設計軟件;5．數據字典是各類數據描述的集合,通常包括4個部分：數據項、數據流、數據存儲和數據加工;數據庫設計基礎1.數據庫1數據庫設計的根本目的是要解決數據共享的問題;2數據庫的特點：計算機二年級基礎知識全文共8頁，當前為第6頁。▼數據按一定的數據模型組織和存儲;計算機二年級基礎知識全文共8頁，當前為第6頁。▼冗余度較小▼數據的獨立性較高;數據獨立性：數據的組織結構和存儲方法與應用程序互不依賴、彼此獨立;▼易擴展▼可為多種用戶共享2.數據庫管理系統DBMS位于用戶與操作系統之間的完成數據管理的系統軟件;3.數據庫系統由數據庫、數據庫管理系統、應用系統、數據庫管理員和用戶組成;最核心的部分是數據庫管理系統;4.數據模型1實體聯系模型及E-R圖3部分：實體、聯系和屬性實體集間的聯系：一對一聯系、一對多聯系和多對多聯系2層次、網狀、關系模型層次模型：有且只有一個結點無雙親,其他結點只有一個雙親;用樹形結構來表示各實體與實體之間的聯系;在關系數據庫中,把數據表示成二維表,每個二維表稱為關系;一個關系對應一張二維表;關系的屬性名稱為關系模式;5.關系運算1并2差3交4笛卡爾積×6.專門關系運算：選擇、連接和投影1從關系中找到滿足條件的所有元組稱為選擇2從關系中挑選若干屬性組成新的關系稱為投影7.數據庫設計步驟：計算機二年級基礎知識全文共8頁，當前為第7頁。1需求分析階段