【正文】 全國計算機等級考試公共基礎(chǔ)知識總結(jié) 第一章數(shù)據(jù)結(jié)構(gòu)與算法 算法 算法：是指解題方案的準(zhǔn)確而完整的描述。 算法不等于程序，也不等計算機方法，程序的編制不可能優(yōu)于算法的設(shè)計。 算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括： （ 1）可行性； （ 2）確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性； （ 3）有窮性，算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止，包括合理的執(zhí)行時間的含義； （ 4）擁 有足夠的情報。 算法的基本要素：一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。 指令系統(tǒng)：一個計算機系統(tǒng)能執(zhí)行的所有指令的集合。 基本運算和操作包括：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。 算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。 算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。 算法復(fù)雜度：算法時間復(fù)雜度和算法空間復(fù)雜度。 算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。 算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。 數(shù)據(jù)結(jié)構(gòu)的基本基本概念 數(shù)據(jù)結(jié)構(gòu)研究的三個方面： （ 1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； （ 2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)； （ 3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 數(shù)據(jù)的邏輯結(jié)構(gòu)包含： （ 1）表示數(shù)據(jù)元素的信息； （ 2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。 數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。 線性結(jié)構(gòu)條件： （ 1）有且只有一個根結(jié)點； （ 2）每一個結(jié)點最多有一個前件，也最多有一個后件。 非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。 1． 3 線性表及其 順序存儲結(jié)構(gòu) 線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。 在復(fù)雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個記錄構(gòu)成的線性表又稱為文件。 非空線性表的結(jié)構(gòu)特征： （ 1）且只有一個根結(jié)點 a1，它無前件； （ 2）有且只有一個終端結(jié)點 an，它無后件； （ 3）除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。結(jié)點個數(shù) n 稱為線性表的長度，當(dāng) n=0時，稱為空表。 線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點： （ 1）線性表中所有元素的所占的存 儲空間是連續(xù)的； （ 2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。 ai的存儲地址為： ADR(ai)=ADR(a1) (i1)k,， ADR(a1)為第一個元素的地址， k 代表每個元素占的字節(jié)數(shù)。 順序表的運算：插入、刪除。 （詳見 1416頁） 1． 4 棧和隊列 棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。 棧按照 “ 先進后出 ” （ FILO）或 “ 后進先出 ” （ LIFO）組織數(shù)據(jù)，棧具有記憶作用。用 top表示棧頂位置，用bottom表示棧底。 棧的基本運算：（ 1）插入元素稱為入棧運算；（ 2）刪除元素稱為退棧運算；（ 3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。 隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。 Rear指針指向隊尾， front指針指向隊頭。 隊列是 “ 先進行出 ” （ FIFO）或 “ 后進后出 ” （ LILO）的線性表。 隊列運算包括（ 1）入隊運算：從隊尾插入一個元素；（ 2）退隊運算：從隊頭刪除一個元素。 循環(huán)隊列： s=0表示隊列空， s=1且 front=rear表示隊 列滿 1． 5 線性鏈表 數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。 結(jié)點由兩部分組成：（ 1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（ 2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。 在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。 鏈?zhǔn)酱鎯Ψ绞郊纯捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。 線性鏈表， HEAD稱為頭指針， HEAD=NULL（或 0）稱為空表，如果是兩 指針：左指針（ Llink）指向前件結(jié)點，右指針（ Rlink）指向后件結(jié)點。 線性鏈表的基本運算：查找、插入、刪除。 1． 6 樹與二叉樹 樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。 在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。 在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。 二叉樹的特點：（ 1）非空二叉 樹只有一個根結(jié)點；（ 2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。 二叉樹的基本性質(zhì)： （ 1）在二叉樹的第 k 層上，最多有 2k1(k≥1) 個結(jié)點； （ 2）深度為 m 的二叉樹最多有 2m1 個結(jié)點； （ 3）度為 0 的結(jié)點（即葉子結(jié)點）總是比度為 2 的結(jié)點多一個； 英才家園 （ 4）具有 n 個結(jié)點的二叉樹，其深度至少為 [log2n] 1,其中 [log2n]表示取 log2n的整數(shù)部分； （ 5）具有 n 個結(jié)點的完全二叉樹的深度為 [log2n] 1； （ 6）設(shè)完全二叉樹共有 n 個結(jié)點 。如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù) 1， 2， ?.n 給結(jié)點進行編號（ k=1,2?.n ），有以下結(jié)論： ① 若 k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若 k1，則該結(jié)點的父結(jié)點編號為 INT(k/2)； ② 若 2k≤n ，則編號為 k 的結(jié)點的左子結(jié)點編號為 2k；否則該結(jié)點無左子結(jié)點（也無右子結(jié)點）； ③ 若 2k 1≤n ，則編號為 k 的結(jié)點的右子結(jié)點編號為 2k 1；否則該結(jié)點無右子結(jié)點。 滿二叉樹是指除最后一層外，每一層上的所有結(jié)點有兩個子結(jié)點，則 k 層上有 2k1 個結(jié)點深度為 m 的滿二叉樹有 2m1 個結(jié)點。 完全 二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結(jié)點。 二叉樹存儲結(jié)構(gòu)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與完全二叉樹可以按層序進行順序存儲。 二叉樹的遍歷： （ 1）前序遍歷（ DLR），首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹； （ 2）中序遍歷（ LDR），首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹； （ 3）后序遍歷（ LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點。 1． 7 查找技術(shù) 順序查找的使用情況： （ 1）線性表為無序表； （ 2）表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。 二分法查找只適用于順序存儲的有序表，對于長度為 n 的有序線性表，最壞情況只需比較 log2n次。 1． 8 排序技術(shù) 排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。 交換類排序法：（ 1）冒泡排序法，需要比較的次數(shù)為 n(n1)/2； （ 2）快速排序法。 插入類排序法：（ 1）簡單插入排序法，最壞情況需要 n(n1)/2次比較；（ 2）希爾排序法，最壞情況需要 O()次比較。 選擇類排序法：（ 1）簡單選擇排序法 , 最壞情況需要 n(n1)/2次比較；（ 2）堆排序法，最壞情況需要 O(nlog2n)次比 較。 第二章程序設(shè)計基礎(chǔ) 2． 1 程序設(shè)計設(shè)計方法和風(fēng)格 如何形成良好的程序設(shè)計風(fēng)格 源程序文檔化； 數(shù)據(jù)說明的方法； 語句的結(jié)構(gòu)； 輸入和輸出。 注釋分序言性注釋和功能性注釋，語句結(jié)構(gòu)清晰第一、效率第二。 2． 2 結(jié)構(gòu)化程序設(shè)計 結(jié)構(gòu)化程序設(shè)計方法的四條原則是： 1. 自頂向下； 2. 逐步求精； ； goto 語句。 結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點： （ 1）順序結(jié)構(gòu)：一種簡單的程序設(shè)計，最基本、最常用的結(jié)構(gòu)； （ 2）選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件 ，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列； （ 3）重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相同程序段。 2． 3 面向?qū)ο蟮某绦蛟O(shè)計 面向?qū)ο蟮某绦蛟O(shè)計：以 60年代末挪威奧斯陸大學(xué)和挪威計算機中心研制的 SIMULA 語言為標(biāo)志。 面向?qū)ο蠓椒ǖ膬?yōu)點： （ 1）與人類習(xí)慣的思維方法一致； （ 2）穩(wěn)定性好； （ 3）可重用性好； （ 4）易于開發(fā)大型軟件產(chǎn)品； （ 5）可維護性好。 對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實體，對象是實體的抽象。 面向?qū)ο蟮某绦蛟O(shè)計方法中的 對象是系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。 英才家園 屬性即對象所包含的信息，操作描述了對象執(zhí)行的功能，操作也稱為方法或服務(wù)。 對象的基本特點： （ 1）標(biāo)識惟一性；（ 2）分類性； （ 3）多態(tài)性； （ 4）封裝性； （ 5）模塊獨立性好。 類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應(yīng)類的一個實例。 消息是一個實例與另一個實例之間傳遞的信息。 消息的組成包括（ 1）接收消息的對象 的名稱；（ 2）消息標(biāo)識符，也稱消息名；（ 3）零個或多個參數(shù)。 繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。 繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。 多態(tài)性是指同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動的現(xiàn)象。 第三章軟件工程基礎(chǔ) 3． 1 軟件工程基本概念 計算機軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。 軟件的特點包括： （ 1）軟件是一種邏輯實體； （ 2）軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程； （ 3）軟件在運行、使用期間不存在磨損、 老化問題； （ 4）軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題； （ 5）軟件復(fù)雜性高，成本昂貴； （ 6）軟件開發(fā)涉及諸多的社會因素。 軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。 軟件危機主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率等問題。 軟件工程是應(yīng)用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標(biāo)準(zhǔn)和工序。 軟件工程包括 3 個要素：方法、工具和過程。 軟件工程過程是把軟件轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動，包含 4 種基本活動： （ 1） P—— 軟件規(guī)格說明； （ 2） D—— 軟件開發(fā)； （ 3） C—— 軟件確認(rèn)； （ 4） A—— 軟件演進。 軟件周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。 軟件生命周期三個階段 :軟件定義、軟件開發(fā)、運行維護，主要活動階段是： （ 1）可行性研究與計劃制定； （ 2）需求分析； （ 3）軟件設(shè)計； （ 4）軟件實現(xiàn)； （ 5）軟件測試； （ 6）運行和維護。 軟件工程的目標(biāo)和與原則： 目標(biāo)：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。 基 本目標(biāo)：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)軟件易于移植；需要較低的費用；能按時完成開發(fā)，及時交付使用。 基本原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。 軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)技術(shù)和軟件工程管理。 軟件開發(fā)技術(shù)包括：軟件開發(fā)方法學(xué)、開發(fā)過程、開發(fā)工具和軟件工程環(huán)境。 軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟學(xué)、軟件心理學(xué)等內(nèi)容。 軟件管理學(xué)包括人員組織、進度安排、質(zhì)量保證、配置管理、項目計劃等。 軟件工程原則包括抽象、信 息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。 3． 2 結(jié)構(gòu)化分析方法 結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計理論。 需求分析方法有（ 1）結(jié)構(gòu)化需求分析方法； （ 2）面向?qū)ο蟮姆治龅姆椒ā? 從需求分析建立的模型的特性來分：靜態(tài)分析和動態(tài)分析。 結(jié)構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具 ,建立系統(tǒng)的邏輯模型。 結(jié)構(gòu)化分析的常用工具 （ 1）數(shù)據(jù)流圖； （ 2）數(shù)據(jù)字典； （ 3）判定樹； （ 4）判定表。 數(shù)據(jù)流圖：描述數(shù)據(jù)處理過程的工具， 是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)功能建模。 數(shù)據(jù)字典：對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的列表，以及精確的、嚴(yán)格的定義，使得用戶和系統(tǒng)分析員對于輸入、輸出、存儲成分和中間計算結(jié)果有共同的理解。 判定樹：從問題定義的文字描述中分清哪些是判定的條件，哪些是判定的結(jié)論，根據(jù)描述材料中的連接詞找出判定