第二章考試要點
　　
　　本章內容主要是:數據結構、算法的基本概念;線性表邏輯結構，鏈表、數組的存儲和運算;隊列與棧的定義，存儲及應用;樹和二叉樹的定義，互相轉換，二叉樹的存儲，二叉樹的周游;圖的基本概念，圖的存儲的周游;排序的基本概念與排序算法（選擇排序，插入排序，交換排序，歸并排序）;檢索的基本概念與檢索算法（順序檢索，二分檢索，散列技術檢索，二叉排序樹）。

　　以下介紹一些常用的數據結構，闡明各種數據結構內在的邏輯關系，討論它們在計算機中的存儲表示，以及在這些數據結構上進行的各種運算和實際的執行算法，并對算法的效率進行簡單的分析。

　　一、基本概念

　　1.什么是數據結構

　　數據是描述客觀事物的數字、字符以及所有能直接輸入到計算機中并被計算機程序處理的符號的集合。
　　
　　數據對象是具有相同性質的數據元素的集合。通常，一個數據對象中的數據元素不是孤立的，而是彼此之間存在著一定的聯系，這種聯系就是數據結構。數據對象中數據元素之間的聯系需要在對數據進行存儲和加工中反映出來，因此，數據結構概念一般包括三方面的內容:數據之間的邏輯關系、數據在計算機中的存儲方式、以及在這些數據上定義的運算的集合。

　　（1）數據的邏輯結構

　　數據的邏輯結構只抽象地反映數據元素之間的邏輯關系，它與數據的存儲無關，是獨立于計算機的。

　　數據的邏輯結構分為線性結構和非線性結構兩大類，線性結構的邏輯特征是:有且僅有一個開始結點和一個終端結點，并且所有的結點都最多有一個直接前驅和一個直接后繼。線性表就是一個典型的線性結構。非線性結構的邏輯特征是:一個結點可能有多個直接前驅和直接后繼。樹、圖等都是非線性結構。

　　（2）數據的存儲結構

　　數據的存儲結構是數據的邏輯結構在計算機存儲器里的實現（亦稱為映象）。它是依賴于計算機的，并有四種基本的存儲映象方法。它們是:
　　
　　①順序存儲方法 該方法是把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元內，結點間的邏輯關系由存儲單元的鄰接關系來體現。順序存儲方法主要用于線性的數據結構，非線性的數據結構也可以通過某種線性化方法來實現順序存儲。

　　②鏈接存儲方法 在鏈接存儲方法中，邏輯上相鄰的結點在物理位置上未必相鄰，結點間的邏輯關系是由附加的指針字段表示的。

　　③索引存儲方法 該方法通常是在存儲結點信息的同時，還建立一個附加的索引表，索引表中的每一項稱為索引項，索引項的一般形式是:（關鍵字，地址）。關鍵字是能唯一標識一個結點的那些數據項。
　　
　　④散列存儲方法 在散列存儲方法中，結點的存儲地址是根據結點的關鍵字值直接計算出來的。上述四種基本的存儲方法也可以組合起來對數據結構進行存儲映象。

　　（3）數據的運算

　　數據的運算定義在數據的邏輯結構之上，每種邏輯結構都有一個運算的集合。常用的運算有:查找、插入、刪除、更新、排序等。顯然，對數據運算的具體實現方法只有在確定了存儲結構之后才能加以考慮。

　　2.算法

　　（1）算法及其特征
　　
　　簡單地說，一個算法就是一種解題方法，更嚴格地說，算法是由若干條指令組成的有窮序列，它必須具有以下特征:
　　
　　①有窮性 一個算法必須在執行有窮步后結束。

　　②確定性 算法的每一步必須是確切地定義的，無二義性。

　　③可行性 算法中的所有待實現的運算必須在原則上能夠由人使用筆和紙在做有窮次運算后完成。

　　④輸入 一個算法具有0個或多個輸入的外界量，它們是算法開始前對算法最初給出的量。

　　⑤輸出 一個算法至少產生一個輸出，它們是與輸入有某種關系的量。
　　
　　算法的含義與程序十分相似，但二者又有區別。一個程序不一定滿足有窮性，操作系統就是如此，只要整個系統不被破壞，操作系統就永遠不會停止，所以操作系統程序不是一個算法。另外，程序中的指令必須是機器可以執行的，而算法中的指令則無此限制。但是，一個算法如果用機器可執行的語言書寫，則它就是一個程序。

　　對一個算法的描述可以采用自然語言、數學語言、約定的符號語言、以及圖解等方式

　　（2）算法的分析
　　
　　求解同一個問題可以有多種不同的算法，評價一個算法的優劣除了正確性和簡明性外，主要考慮兩點:一是執行算法所耗費的時間，二是執行算法所耗費的存儲空間，特別是輔助存儲空間的耗費。就這兩者而言，前者顯得比后者更為重要，在數據結構中往往更注重對算法執行時間的分析。
　　
　　一個算法所耗費的時間是該算法中每條語句的執行時間之和，而每條語句的執行時間是該語句執行次數（頻度）與該語句一次執行所需時間的乘積。如果假定每條語句一次執行所需的時間均為單位時間，則一個算法的時間耗費就是該算法中所有語句的頻度之和。

希望與更多計算機等級考試的網友交流，請進入計算機等級考試論壇

更多信息請訪問：考試吧計算機等級考試欄目