計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)重點(diǎn)

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