2019年全國計算機等級考試四級復(fù)習(xí)綱要5

1、2019 年全國計算機等級考試四級復(fù)習(xí)綱要 5第二章考試要點本章內(nèi)容主要是：數(shù)據(jù)結(jié)構(gòu)、算法的基本概念 ; 線性表邏輯結(jié)構(gòu)，鏈 表、數(shù)組的存儲和運算 ;隊列與棧的定義，存儲及應(yīng)用 ; 樹和二叉樹的 定義，互相轉(zhuǎn)換，二叉樹的存儲，二叉樹的周游 ; 圖的基本概念，圖的 存儲的周游 ; 排序的基本概念與排序算法（選擇排序，插入排序，交換 排序，歸并排序） ; 檢索的基本概念與檢索算法（順序檢索，二分檢索， 散列技術(shù)檢索，二叉排序樹）。以下介紹一些常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系， 討論它們在計算機中的存儲表示，以及在這些數(shù)據(jù)結(jié)構(gòu)上實行的各種 運算和實際的執(zhí)行算法，并對算法的效率實行簡單的

2、分析。一、基本概念1. 什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)是描述客觀事物的數(shù)字、字符以及所有能直接輸入到計算機中 并被計算機程序處理的符號的集合。數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。通常，一個數(shù)據(jù)對象 中的數(shù)據(jù)元素不是孤立的，而是彼此之間存有著一定的聯(lián)系，這種聯(lián) 系就是數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)對象中數(shù)據(jù)元素之間的聯(lián)系需要在對數(shù)據(jù)實行 存儲和加工中反映出來，所以，數(shù)據(jù)結(jié)構(gòu)概念一般包括三方面的內(nèi)容： 數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計算機中的存儲方式、以及在這些數(shù)據(jù) 上定義的運算的集合。（1）數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系，它與數(shù)據(jù) 的存儲無關(guān)，是獨立于計算機的。數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非

3、線性結(jié)構(gòu)兩大類，線性結(jié)構(gòu)的邏 輯特征是：有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有的結(jié)點 都最多有一個直接前驅(qū)和一個直接后繼。線性表就是一個典型的線性 結(jié)構(gòu)。非線性結(jié)構(gòu)的邏輯特征是：一個結(jié)點可能有多個直接前驅(qū)和直 接后繼。樹、圖等都是非線性結(jié)構(gòu)。 來源： （2）數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器里的實現(xiàn)（亦稱 為映象）。它是依賴于計算機的，并有四種基本的存儲映象方法。它 們是： 順序存儲方法 該方法是把邏輯上相鄰的結(jié)點存儲在物理位置上相 鄰的存儲單元內(nèi)，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。 順序存儲方法主要用于線性的數(shù)據(jù)結(jié)構(gòu)，非線性的數(shù)據(jù)結(jié)構(gòu)也能夠通 過某種線

4、性化方法來實現(xiàn)順序存儲。 鏈接存儲方法 在鏈接存儲方法中，邏輯上相鄰的結(jié)點在物理位置 上未必相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。 索引存儲方法 該方法通常是在存儲結(jié)點信息的同時，還建立一個 附加的索引表，索引表中的每一項稱為索引項，索引項的一般形式是： （關(guān)鍵字，地址）。關(guān)鍵字是能標(biāo)識一個結(jié)點的那些數(shù)據(jù)項。 散列存儲方法 在散列存儲方法中，結(jié)點的存儲地址是根據(jù)結(jié)點的 關(guān)鍵字值直接計算出來的。上述四種基本的存儲方法也能夠組合起來 對數(shù)據(jù)結(jié)構(gòu)實行存儲映象。（3）數(shù)據(jù)的運算數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上，每種邏輯結(jié)構(gòu)都有一個運 算的集合。常用的運算有：查找、插入、刪除、更新、排序等。

5、顯然， 對數(shù)據(jù)運算的具體實現(xiàn)方法只有在確定了存儲結(jié)構(gòu)之后才能加以考慮。2. 算法1）算法及其特征簡單地說，一個算法就是一種解題方法，更嚴(yán)格地說，算法是由若 干條指令組成的有窮序列，它必須具有以下特征： 有窮性 一個算法必須在執(zhí)行有窮步后結(jié)束。 確定性 算法的每一步必須是確切地定義的，無二義性。 可行性 算法中的所有待實現(xiàn)的運算必須在原則上能夠由人使用筆 和紙在做有窮次運算后完成。 輸入 一個算法具有 0 個或多個輸入的外界量，它們是算法開始前 對算法最初給出的量。 輸出 一個算法至少產(chǎn)生一個輸出，它們是與輸入有某種關(guān)系的量。算法的含義與程序十分相似，但二者又有區(qū)別。一個程序不一定滿 足有窮性，操作系統(tǒng)就是如此，只要整個系統(tǒng)不被破壞，操作系統(tǒng)就 永遠(yuǎn)不會停止，所以操作系統(tǒng)程序不是一個算法。另外，程序中的指 令必須是機器能夠執(zhí)行的，而算法中的指令則無此限制。但是，一個 算法如果用機器可執(zhí)行的語言書寫，則它就是一個程序。對一個算法的描述能夠采用自然語言、數(shù)學(xué)語言、約定的符號語言、 以及圖解等方式。（2）算法的分析求解同一個問題能夠有多種不同的算法，評價一個算法的優(yōu)劣除了 準(zhǔn)確性和簡明性外，主要考慮兩點：一是執(zhí)行算法所耗費的時間，二 是執(zhí)行算法所耗費的存儲空間，特別是輔助存儲空間的耗費。就這兩 者來說，前者顯