【正文】 計算機等級考試 公共基礎(chǔ)知識 第 2頁 計算機二級考試公共基礎(chǔ)知識 大綱 ? 數(shù)據(jù)結(jié)構(gòu)與算法 ? 程序設(shè)計基礎(chǔ) ? 軟件工程基礎(chǔ) ? 數(shù)據(jù)庫設(shè)計基礎(chǔ) 這四個方面在試卷中出現(xiàn)的情況是：選擇題 10個（ 20分），填空題 5個（ 10分），總分值占到了試卷卷面分的 30％，是一個不小的比例。 第 3頁 計算機二級考試公共基礎(chǔ)知識試卷分析 章節(jié) 考試時間 數(shù)據(jù)結(jié)構(gòu) 與算法 程序設(shè)計基礎(chǔ) 軟件工程基礎(chǔ) 數(shù)據(jù)庫設(shè)計基礎(chǔ) 2022年 4月 10分 2分 10分 8分 2022年 9月 12分 4分 8分 6分 2022年 4月 10分 2分 8分 10分 2022年 9月 10分 2分 8分 10分 2022年 3月 10分 2分 8分 10分 2022年 9月 10分 2分 8分 10分 2022年 3月 10分 0分 10分 10分 第 4頁 算法 ⒈ 算法的基本概念 度的概念和意義 一、基本數(shù)據(jù)結(jié)構(gòu)與算法 數(shù)據(jù)結(jié)構(gòu) ⒈ 數(shù)據(jù)結(jié)構(gòu)的概念 ⒉ 線性表 ⒊ 棧和隊列 ⒋ 樹與二叉樹 ⒌ 查找技術(shù) ⒍ 排序技術(shù) 對于等級考試，這個部分的考核 重點主要 在 算法和數(shù)據(jù)結(jié)構(gòu)的基本概念 、 二叉樹 (遍歷、結(jié)點）， 還有 排序和查找 考試中也經(jīng)常會涉及到。 第 5頁 算法的定義 ?對解題方案準確而完整的描述稱為算法。 算法是程序設(shè)計的核心 ⒈ 算法的基本概念 算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點說，就是計算機 解題的過程 (計算的方法 )。在這個過程中，無論是形成解題思路 (推理實現(xiàn)的算法 )還是編寫程序 (操作實現(xiàn)的算法 )，都是在實施某種算法。 例： n個數(shù)從大到小進行排序。 有多種排序方法 ，常用的有冒泡排序、選擇排序等。 算法不等于程序，也不等計算機方法，程序的編制不可能優(yōu)于算法的設(shè)計。 講課 說課 第 6頁 2 . 算法的基本特征 一個算法應該具有以下五個重要的特征： ? 有窮性 ? 確定性 ? 輸入 ? 輸出 ? 可行性 一個算法必須保證執(zhí)行有限步之后結(jié)束； 算法的每一步驟必須有確切的定義； 一個算法有 0個或多個輸入，以刻畫運算對象的初始情況，所謂 0個輸入是指算法本身定出了初始條件； 一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的； 算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成 擁有足夠的情報 第 7頁 ? 算法與計算機程序 算法 ____是一組邏輯步驟 程序 —— 用計算機語言描述的算法 3. 算法的表示 INPUT r S= * r*r PTINT S 開始 輸入 R S= * R*R 輸出 S 結(jié)束 問題： 輸入園的半徑，計算園的面積 一個算法的表示需要使用一些語言形式。 傳統(tǒng)的算法 圖形法，如“流程圖”和 NS圖 目前常用的方法 使用偽碼描述算法。 第 8頁 冒泡排序的方法： ，逐次對相鄰的兩個元素進行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大的元素排到表的最后 ； ，對剩余的元素重復上述過程，將次大的數(shù)排到表的倒數(shù)第二個位置； ； 對于長度為 n的線性表，冒泡排序需要對表掃描 n1遍。 算法舉例： n個數(shù)排序 第 9頁 4. 算法的兩個基本要素： 基本運算和操作 ? 算術(shù)運算 ? 關(guān)系運算 ? 邏輯運算 ? 數(shù)據(jù)傳輸 控制結(jié)構(gòu) ? 順序 ? 選擇 ? 循環(huán) ?一是對數(shù)據(jù)對象的運算和操作； ?二是算法的控制結(jié)構(gòu)。 ?算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法 第 10頁 5. 算法的復雜度 評價一個算法優(yōu)劣的主要標準是算法的執(zhí)行效率和存儲需求： ? 時間復雜度：執(zhí)行這個算法所需要的 計算工作量 一般可以用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量計算工作量 ? 空間復雜度：執(zhí)行這個算法所需要的 內(nèi)存空間 算法在執(zhí)行過程中臨時占用的存儲空間 時間復雜度 它大致等于計算機 執(zhí)行一種簡單操作所需的平均時間 與算法中進行 簡單操作的次數(shù)的乘積 。 一個算法在計算機存儲器上所占用的存儲空間，包括 存儲算法本身所占用的存儲空間 、 算法中的輸入輸出數(shù)據(jù)所占用的存儲空間 和 算法在運行過程中臨時占用的存儲空間 這三個部分 第 11頁 (1) 在計算機中，算法是指 ______。 A. 查詢方法 B. 加工方法 C. 解題方案的準確而完整的描述 D. 排序方法 (2)下列敘述中正確的是 （ 07年 4月 ） A)算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) B)算法的時間復雜度是指執(zhí)行算法所需要的計算工作量 C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應的 D)算法的時間復雜度與空間復雜度一定相關(guān) (3)算法的有窮性是指 (08年 4月 ) A）算法程序的運行時間是有限的 B）算法程序所處理的數(shù)據(jù)量是有限的 C）算法程序的長度是有限的 D）算法只能被有限的用戶使用 (c) (B) 算法習題 : (A) 第 12頁 (4) 算法的時問復雜度是指 (2022年 3月 ) A)算法的執(zhí)行時間 B)算法所處理的數(shù)據(jù)量 C)算法程序中的語句或指令條數(shù) D)算法在執(zhí)行過程中所需要的基本運算次數(shù) (5) 算法的空間復雜度是指 (09年 9月 ) A）算法在執(zhí)行過程中所需要的計算機存儲空間 B）算法所處理的數(shù)據(jù)量 C）算法程序中的語句或指令條數(shù) D）算法在執(zhí)行過程中所需要的臨時工作單元數(shù) (6) 下列敘述中正確的是 (06年 9月 ) A）一個算法的空間復雜度大，則其時間復雜度也必定大 B）一個算法的空間復雜度大，則其時間復雜度必定小 C）一個算法的時間復雜度大，則其空間復雜度必定小 D）上述三種說法都不對 (D) 計算工作量 (A) (D) ? 算法的時間復雜度是指 A) 執(zhí)行算法程序所需要的時間 B) 算法程序的長度 C) 算法執(zhí)行過程中所需要的基本運算次數(shù) D) 算法程序中的指令條數(shù) ? 算法的基本特征是可行性、確定性、 【 1】 和擁有足夠的情報。 ? 算法的空間復雜度是指 A) 算法程序的長度 B) 算法程序中的指令條數(shù) C) 算法程序所占的存儲空間 D) 執(zhí)行過程中所需要的存儲空間 ? 在計算機中，算法是指 A) 加工方法 B) 解題方案的準確而完整的描述 C) 排序方法 D) 查詢方法 例題講解 有窮性 ?算法分析的目的是 A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 找出算法中輸入和輸出之間的關(guān)系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改進 ?算法的工作量大小和實現(xiàn)算法所需的存儲單元多少分別稱為算法的 【 1】 。 時間復雜度和空間復雜度 第 15頁 計算機在進行數(shù)據(jù)處理時，實際需要處理的數(shù)據(jù)元素一般有很多，而這些大量的數(shù)據(jù)元素都需要存放在計算機中，因此，大量的 數(shù)據(jù)元素在計算機中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計算機的存儲空間， 這是進行數(shù)據(jù)處理的關(guān)鍵問題。 二、數(shù)據(jù)結(jié)構(gòu) 程序 =算法 +數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 一般來說，人們不會同時處理特征完全不同且互相之間沒有任何關(guān)系的各類數(shù)據(jù)元素，對于具有不同特征的數(shù)據(jù)元素總是分別進行處理。 一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在有某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。 超市的物品如何存放才好找且節(jié)省空間呢？ 第 16頁 二 . 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學科，它包括三個方面。 （ 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)進行的運算。 第 17頁 ? 1. 邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)包含： （ 1）表示數(shù)據(jù)元素的信息； （ 2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。 例： 1. 一年四季的數(shù)據(jù)結(jié)構(gòu) B=(D,R) D={春，夏，秋，冬 } R={(春，夏 ) ,(夏，秋 ),(秋，冬 )} 2. 家庭成員的數(shù)據(jù)結(jié)構(gòu) B=(D,R) D={父親，兒子，女兒 } R={(父親，兒子 ) ,(父親，女兒 )} 春 夏 秋 冬 數(shù)據(jù)結(jié)構(gòu)的圖形表示 父親 兒子 女兒 第 18頁 ?常見的 邏輯結(jié)構(gòu) 有： 線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖形結(jié)構(gòu) ? ① 線性結(jié)構(gòu) 結(jié)構(gòu)中的每個元素之間存在一個對一個的關(guān)系； ? ② 樹形結(jié)構(gòu) 結(jié)構(gòu)中的每個元素之間存在一個對多個的關(guān)系； ? ③ 圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的每個元素之間存在多個對多個的關(guān)系。 其中， 樹形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為非線形結(jié)構(gòu) 。數(shù)據(jù)的邏輯結(jié)構(gòu)可以用二元關(guān)系表示，也可以直觀地用圖形來表示。 第 19頁 ? 2. 存儲結(jié)構(gòu)（物理結(jié)構(gòu) ） 計算機在實際進行數(shù)據(jù)處理時，被處理的各數(shù)據(jù)元素總是被存放在計算機的存儲空間中，并且，各數(shù)據(jù)元素在計算機存儲空間中的位置與它們的邏輯關(guān)系不一定是相同的，而且一般也不可能相同。 如： 一年四季 家庭成員 計算機存儲空間怎樣存放？ 存儲結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計算機存儲空間中的具體實現(xiàn)。 常見的存儲結(jié)構(gòu)有： ? 順序存儲結(jié)構(gòu) ? 鏈式存儲結(jié)構(gòu) ? 索引存儲結(jié)構(gòu) ? 只抽象地反映數(shù)據(jù)元素之間的關(guān)系的結(jié)構(gòu)，而不管其存儲方式的數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。 ? 一種 數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要表示成一種或多種存儲結(jié)構(gòu) 。 第 20頁 ? 3. 數(shù)據(jù)的運算 ? 檢索 ? 插入 ? 刪除 ? 更新 ? 排序 通常，一個數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點可能是動態(tài)變化的。根據(jù)需要或在處理過程中，可以在一個數(shù)據(jù)結(jié)構(gòu)中增加一個新結(jié)點（插入運算），也可以刪除某個結(jié)點（刪除運算），除此之外，對數(shù)據(jù)結(jié)構(gòu)的運算還有查找、分類、合并、分解、復制和修改。 在對數(shù)據(jù)結(jié)構(gòu)的處理過程中，不僅數(shù)據(jù)結(jié)構(gòu)中結(jié)點的個數(shù)在動態(tài)變化，而且，各數(shù)據(jù)元素之間的關(guān)系也有可能在動態(tài)地變化。 如：無序表變有序表 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學科，研究以下三方面內(nèi)容： ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 數(shù)據(jù)的存儲結(jié)構(gòu) ? 數(shù)據(jù)的運算 父親 兒子 女兒 第 21|92頁 常見的數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu)分類 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 兩大類型 線性結(jié)構(gòu)： 一個非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的兩個條件，則這種數(shù)據(jù)結(jié)構(gòu)即為 線性結(jié)構(gòu) 。 ① 有且僅有一個根結(jié)點； ② 除第一個結(jié)點外，每一個結(jié)點最多有一個前件； 除最后一個結(jié)點外，每一個結(jié)點最多有一個后件。 常見的線性結(jié)構(gòu)有： 線性表、棧、隊列、線性鏈表等 第 22|92頁 a1 a2 a5 a3 a4 HEAD 3 1 9 5 10 線性鏈表的邏輯狀態(tài) 常見的非線性結(jié)構(gòu)有樹、 二叉樹、圖等 非線性結(jié)構(gòu) ： 一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)。 第 23頁 １． 線性表（ Linear List） 線性表是由 n（ n≥0）個數(shù)據(jù)元素 a1， a2， … ， ai， … ， an組成的一個有限序列。 簡單的線性表 春 夏 秋 冬 復雜的線性表 記錄 1 02022001 張三 男 … 記錄 2 02022003 李四