計算機二級公共基礎(chǔ)知識重點

計算機二次公共基礎(chǔ)知識焦點計算機二次公共基礎(chǔ)一、數(shù)據(jù)結(jié)構(gòu)和算法1.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)表示彼此相關(guān)的數(shù)據(jù)元素的集合。數(shù)據(jù)邏輯結(jié)構(gòu)反映了數(shù)據(jù)元素之間的邏輯關(guān)系。存儲結(jié)構(gòu)是將數(shù)據(jù)保存在計算機存儲空間中的邏輯結(jié)構(gòu)，它分為四種類型：順序存儲、鏈存儲、索引存儲和散列存儲。數(shù)據(jù)結(jié)構(gòu)可以分為兩種：具體取決于元素之間前后關(guān)系的復(fù)雜性(1)線性結(jié)構(gòu)：有根節(jié)點，每個節(jié)點最多有一個直接前兆和一個直接后繼非空數(shù)據(jù)結(jié)構(gòu)。(2)非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)。1.1.2算法1.算法的基本概念(1)概念：算法意味著對解決問題的方法的準(zhǔn)確、完整的說明。(2)基本特征：可行性、確定性、貧窮性和充分的信息。(3)基本要素：數(shù)據(jù)對象的計算和操作、算法和控制結(jié)構(gòu)。(4)設(shè)計的基本方法：枚舉方法、歸納方法、遞歸方法、半遞歸技術(shù)、回溯方法。算法的復(fù)雜性(1)算法的時間復(fù)雜性：運行算法所需的計算工作量。(2)算法的空間復(fù)雜性：運行算法所需的內(nèi)存空間。1.1.3線性表及其順序存儲結(jié)構(gòu)1.定線表格的基本概念定線結(jié)構(gòu)也稱為定線表格，定線表格是最簡單、最常用的資料結(jié)構(gòu)。2.線性表的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)具有以下特點：(1)元素占用的存儲空間必須連接在一起。(2)元素按邏輯順序存儲在存儲空間中的位置。3.插入路線表操作在I元素之前插入新元素時，首先將原始I節(jié)點向后移動一個元素位置，直到第n個節(jié)點。然后將新節(jié)點放置在第I個位置，最后修改線性表中的節(jié)點數(shù)。4.刪除定線表格要刪除I位置的元素，請先將I后不包含第I個元素的n-i元素向前移動一個位置，然后修改線性表格中的節(jié)點數(shù)。1.1.4堆棧和隊列1.堆棧和基本運算堆棧是特殊的線表，插入和刪除操作只在線性表的一端進行，也稱為先進先出表或后進先出表。堆棧頂部是允許插入和刪除的一端，堆棧底部是堆棧頂部的另一端。空堆棧是堆棧中沒有元素的堆棧。堆棧具有以下特征：(1)堆棧頂層元素藝術(shù)家最后插入的、最早刪除的元素。(2)插入到堆棧的第一個、最后刪除的元素。(3)棧起記憶作用。(4)在順序存儲結(jié)構(gòu)中，堆棧的插入和刪除操作不需要移動表中的其他數(shù)據(jù)元素。(5)堆棧頂部指針top動態(tài)反映堆棧中元素的更改。順序存儲和運算包括人堆棧運算、反向堆棧運算和讀堆棧鋸運算。2.隊列和基本運算隊列是可以在一端插入并在另一端刪除的線性表，也稱為先進先出(first-out)的線性表。尾部是允許插入的一端，通常用尾部指針指向頁腳元素。頭是允許刪除的一端，通常用頭指針指向頭元素以前的位置。循環(huán)隊列及其操作包括入隊和出隊操作。1.1.5樹和二進制樹1.樹的基本概念樹是簡單的非線性結(jié)構(gòu)，樹沒有前導(dǎo)節(jié)點，其馀節(jié)點不相交的有限點被劃分為不相交的m個有限集合T1、t2tm，每個集合稱為T1，t2tm是與節(jié)點的子樹。(1)父節(jié)點：每個節(jié)點只有一個前置節(jié)點，沒有前置節(jié)點的節(jié)點只有一個稱為樹的根節(jié)點(2)子節(jié)點：每個節(jié)點可以有多個背面項目，沒有背面項目的節(jié)點稱為葉節(jié)點。(3)樹的度：因此節(jié)點的最大度(4)樹的深度：樹的最大級別。二叉樹和基本特性二叉樹是非線性結(jié)構(gòu)，是有限節(jié)點集，由兩個左叉樹和右叉樹組成，這兩個叉樹是空的或與一個根節(jié)點不相交的?？梢苑譃橥暾亩鏄浜屯暾亩鏄洹Ｍ暾亩M制樹必須是完整的二進制樹，但整個二進制樹不一定是完整的二進制樹。二進制樹的特征包括：(1)二進制樹可以為空，空的二進制樹沒有節(jié)點，非空的二進制樹只有一個根節(jié)點。(2)每個節(jié)點最多可以有兩個子樹：左子樹和右子樹。二叉樹存儲結(jié)構(gòu)二進制樹使用鏈存儲結(jié)構(gòu)，通常由數(shù)據(jù)域和指針字段組成。完整的二進制樹和完整的二進制樹可以按層次順序存儲。二叉樹遍歷二進制樹的遍歷不重復(fù)訪問二進制樹的節(jié)點，主要表示非空的二進制樹，對于空的二進制樹，結(jié)束返回。二叉樹遍歷分為預(yù)遍歷、中間遍歷和后遍歷。1.1.6尋找技術(shù)(1)順序查找：在路線表中查找指定的元素。(2)二進制查找：此查找僅適用于連續(xù)存儲結(jié)構(gòu)的線性表，它必須是連續(xù)表，如果需要二分查找，則重復(fù)查找成功或子表長度為零時結(jié)束。1.1.7校準(zhǔn)技術(shù)(1)交換類排序方法：通過數(shù)據(jù)元素(例如冒泡和快速排序)之間的相互交換進行排序。(2)插入類排序方法：將未排序序列中的每個元素按順序插入到已排序的線性表中，例如簡單插入排序方法和跟排序方法。(3)選擇類排序方法，例如，選擇整個路線表中最小的元素并將其交換到表的開頭，查找其馀元素中最小的元素并將其交換到最小元素的后面。包括簡單選擇排序方法和推式排序方法。1.2編程基礎(chǔ)1.2.1編程方法和風(fēng)格(1)編程主要是指具有結(jié)構(gòu)化編程方法、軟件過程方法和面向?qū)ο蠓椒ǖ某绦虻脑O(shè)計、準(zhǔn)備、調(diào)試方法和過程。(2)好的設(shè)計風(fēng)格應(yīng)該集中在源代碼文檔、數(shù)據(jù)描述方法、語句的結(jié)構(gòu)和輸入輸出等因素上。1.2.2面向?qū)ο蟮木幊堂嫦驅(qū)ο蠓椒ǖ谋举|(zhì)是強調(diào)，從客觀世界固有的事物構(gòu)建系統(tǒng)，構(gòu)建的系統(tǒng)可以映射問題領(lǐng)域。面向?qū)ο蠓椒梢院w的主要概念如下：(1)目標(biāo)：用來表示客觀世界的任何實體，可以是有明確界限和意義的任何東西。(。(2)類：具有公共屬性和公共方法的對象的集合。(3)消息：在實例之間傳遞的消息，它整合了數(shù)據(jù)流和控制流。(4)繼承：基于現(xiàn)有類定義創(chuàng)建新類的定義技術(shù)。(5)例如，特定對象是分類的實例。(6)多態(tài)：對象根據(jù)自己接受的信息行事，當(dāng)同一信息被接受到其他對象中時，對象的行為會有所不同。(。面向?qū)ο缶幊痰膬?yōu)點：思維方式與人類習(xí)慣一致，穩(wěn)定性好，可重用性好，開發(fā)大型軟件產(chǎn)品的簡便性好，可維護性好。1.3軟件工程基礎(chǔ)1.3.1軟件工程基本概念1.軟件定義和特性軟件表示與計算機系統(tǒng)運行相關(guān)的計算機程序、領(lǐng)域、規(guī)則和可能的文件、文檔和數(shù)據(jù)。軟件具有以下特征：(1)邏輯實體和抽象。(2)生產(chǎn)沒有明顯的制作過程。(3)運行過程中沒有磨損和老化問題。(4)由于依賴于計算機系統(tǒng)的開發(fā)和運行，軟件存在遷移問題。(5)復(fù)雜性高，成本高。(6)發(fā)展包括很多社會因素。2.軟件危機和軟件工程(1)軟件危機：是指計算機軟件開發(fā)和維護中出現(xiàn)的一系列嚴(yán)重問題。(2)軟件工程：適用于定義、開發(fā)和維護計算機軟件的整套方法、工具、手冊、實踐標(biāo)準(zhǔn)和程序。(3)軟件工程由開發(fā)技術(shù)和軟件工程管理兩部分組成。(4)軟件工程流程：將輸入轉(zhuǎn)換為輸出的一組相關(guān)資源和活動。(5)軟件生命周期：軟件產(chǎn)品從建議、實施、使用維護到停止使用的過程。(6)軟件工程的目標(biāo)：以給定的成本、進度為前提，開發(fā)符合用戶要求的產(chǎn)品，具有有效性、可靠性、可理解性、可維護性、可重用性、可移植性、可追溯性和互操作性。(7)軟件工程的最終原則：抽象、信息隱藏、模塊化、本地化、確定性、一致性、完整性和可驗證性。(8)軟件開發(fā)工具：要從早期單向工具發(fā)展到集成工具，軟件開發(fā)方法必須得到該工具的支持。(9)軟件開發(fā)環(huán)境：全面支持開發(fā)過程的軟件工具欄。計算機輔助軟件工程是當(dāng)前的研究工作和開發(fā)方向。1.3.2結(jié)構(gòu)化分析方法需求分析可以匯總為需求獲取、需求分析、需求規(guī)格說明和需求復(fù)查。典型的分析方法包括：(1)結(jié)構(gòu)化分析方法：實質(zhì)上側(cè)重于數(shù)據(jù)流，由上而下、按層次分解，建立系統(tǒng)的處理流，使用典型的數(shù)據(jù)流圖、數(shù)字詞典、判斷樹和判斷表等工具。(2)面向?qū)ο蟮姆治龇椒ā?.3.3結(jié)構(gòu)化設(shè)計方法1.軟件設(shè)計的基本概念和方法軟件設(shè)計是將軟件要求轉(zhuǎn)換為軟件表示的過程。(1)基本原則：抽象、模塊化、信息隱藏、模塊獨立性。(2)基本思路：將軟件設(shè)計成相對獨立、具有單一功能的模塊的結(jié)構(gòu)。2.摘要設(shè)計(1)摘要設(shè)計包括設(shè)計軟件系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫設(shè)計、摘要設(shè)計文檔創(chuàng)建、摘要設(shè)計文檔審閱等四項任務(wù)。(2)數(shù)據(jù)流導(dǎo)向設(shè)計方法：數(shù)據(jù)流圖中的信息分為交換和事務(wù)形式的交換流和事務(wù)物流。3.詳細設(shè)計的工具(1)圖形工具：流程圖、N-S、pad、HIPO。(2)表格工具：決定表格。(3)語言工具：偽代碼(PDL)。1.3.4軟件測試軟件測試的目的是發(fā)現(xiàn)錯誤，其說明如下：(1)因此，測試應(yīng)追溯到用戶要求。(2)嚴(yán)格執(zhí)行測試計劃，排除測試的隨機性。(3)充分注意測試的集群現(xiàn)象。(4)程序員不得確認(rèn)自己的程序。(5)徹底的測試是不可能的。(6)適當(dāng)保存設(shè)計計劃、測試案例、錯誤統(tǒng)計和最終分析報告。軟件測試方法可以從被測試軟件是否需要運行的角度分為靜態(tài)測試和動態(tài)測試，按功能分為白盒測試和黑盒測試。(1)白盒測試：也稱為結(jié)構(gòu)測試，根據(jù)軟件的內(nèi)部邏輯設(shè)計和工作過程檢查軟件的內(nèi)部組件。主要方法包括邏輯覆蓋測試、基本路徑測試等。(2)黑盒測試：也稱為功能測試，根據(jù)規(guī)格的功能設(shè)計測試，包括等效分割、邊界值分析、錯誤估計方法、原因圖等。1.3.5程序調(diào)試程序調(diào)試的主要任務(wù)是診斷和更正程序中的錯誤，應(yīng)用的主要方法是強制誤行方法、回溯方法和原因排除。1.4數(shù)據(jù)庫設(shè)計基礎(chǔ)1.4.1數(shù)據(jù)庫系統(tǒng)的基本概念(1)數(shù)據(jù)：描述事物的符號記錄，分為臨時數(shù)據(jù)和永久數(shù)據(jù)。(2)數(shù)據(jù)庫：長期存儲在計算機內(nèi)部的有組織的、可共享的數(shù)據(jù)集合。(3)數(shù)據(jù)庫管理系統(tǒng)：負責(zé)數(shù)據(jù)庫的系統(tǒng)軟件，如數(shù)據(jù)組織、數(shù)據(jù)操作、數(shù)據(jù)維護、控制和保護、數(shù)據(jù)服務(wù)等。(4)數(shù)據(jù)庫技術(shù)開發(fā)經(jīng)歷了手動管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫系統(tǒng)階段等三個階段。(5)數(shù)據(jù)庫系統(tǒng)具有整合、高共享、低冗馀、數(shù)據(jù)集成管理和控制功能。(6)三階段模式(概念模式、內(nèi)部模式、外部模式)和輔助模式(外部模式/概念模式的映射、概念模式/內(nèi)部模式的映射)構(gòu)成了數(shù)據(jù)庫系統(tǒng)內(nèi)部的抽象結(jié)構(gòu)系統(tǒng)。1.4.2數(shù)據(jù)模型數(shù)據(jù)模型以抽象層次描述系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件，所描述的內(nèi)容是數(shù)據(jù)機制、數(shù)據(jù)操作和數(shù)據(jù)約束條件。概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型和物理數(shù)據(jù)模型是數(shù)據(jù)模型的三層。(1)E-R模型：提供表示實體、屬性和連接的方法。實體和實體之間有“一對一”、“一對多”和“多對一”的關(guān)聯(lián)。(2)層次模型：使用樹結(jié)構(gòu)表示實體及其之間的連接。其中節(jié)點是實體，分支是連接，從上到下是一對多關(guān)系。(3)網(wǎng)格模型：對以網(wǎng)格結(jié)構(gòu)表示實體及其之間連接的層次模型的擴展。網(wǎng)格模型是記錄型節(jié)點，反映了現(xiàn)實中更復(fù)雜的事物連接。(4)關(guān)系模型：顯示為二維表，您可以在其中查詢、添加、刪除和修改數(shù)據(jù)。關(guān)系模型允許定義三種約束：實體完整性、參照完整性和用戶定義的完整性。1.索引鍵：在2d表格中唯一識別祖系的一組最小屬性。2.候選關(guān)鍵字：二維表中可能存在一些關(guān)鍵字。3.主鍵：二維表中所有關(guān)鍵字使用的鍵之一。1.4.3關(guān)系代數(shù)(1)典型的集合運算包括關(guān)系和運算、關(guān)系交叉運算、關(guān)系差異運算和廣義笛卡爾乘積；(2)特殊關(guān)系運算包括選擇、投影和連接。1.4.4數(shù)據(jù)庫設(shè)計和管理1.數(shù)據(jù)庫設(shè)計概述數(shù)據(jù)庫設(shè)計通常是通過應(yīng)用面向數(shù)據(jù)的方法和面向流程的方法來完成的，并以流程迭代和逐步細化為基本思路資料庫的設(shè)計階段為需求分析-概念設(shè)計-邏輯設(shè)計-實體資料-代碼-測試執(zhí)行-進一步修改2.分析數(shù)據(jù)庫設(shè)計要求需求收集和分析員數(shù)據(jù)庫設(shè)計的第一步。此階段使用了很多結(jié)構(gòu)化分析方法和面向?qū)ο蟮姆椒?，主要用于?shù)據(jù)流程圖、數(shù)據(jù)分析、功能分析、功能處理模塊以及確定數(shù)據(jù)之間的關(guān)系。數(shù)據(jù)字典