第二章考試要點(diǎn)
　　
　　本章內(nèi)容主要是:數(shù)據(jù)結(jié)構(gòu)、算法的基本概念;線性表邏輯結(jié)構(gòu)，鏈表、數(shù)組的存儲(chǔ)和運(yùn)算;隊(duì)列與棧的定義，存儲(chǔ)及應(yīng)用;樹(shù)和二叉樹(shù)的定義，互相轉(zhuǎn)換，二叉樹(shù)的存儲(chǔ)，二叉樹(shù)的周游;圖的基本概念，圖的存儲(chǔ)的周游;排序的基本概念與排序算法（選擇排序，插入排序，交換排序，歸并排序）;檢索的基本概念與檢索算法（順序檢索，二分檢索，散列技術(shù)檢索，二叉排序樹(shù)）。

　　以下介紹一些常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示，以及在這些數(shù)據(jù)結(jié)構(gòu)上進(jìn)行的各種運(yùn)算和實(shí)際的執(zhí)行算法，并對(duì)算法的效率進(jìn)行簡(jiǎn)單的分析。

　　一、基本概念

　　1.什么是數(shù)據(jù)結(jié)構(gòu)

　　數(shù)據(jù)是描述客觀事物的數(shù)字、字符以及所有能直接輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合。
　　
　　數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。通常，一個(gè)數(shù)據(jù)對(duì)象中的數(shù)據(jù)元素不是孤立的，而是彼此之間存在著一定的聯(lián)系，這種聯(lián)系就是數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的聯(lián)系需要在對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)和加工中反映出來(lái)，因此，數(shù)據(jù)結(jié)構(gòu)概念一般包括三方面的內(nèi)容:數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式、以及在這些數(shù)據(jù)上定義的運(yùn)算的集合。

　�。�1）數(shù)據(jù)的邏輯結(jié)構(gòu)

　　數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。

　　數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類(lèi)，線性結(jié)構(gòu)的邏輯特征是:有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有的結(jié)點(diǎn)都最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼。線性表就是一個(gè)典型的線性結(jié)構(gòu)。非線性結(jié)構(gòu)的邏輯特征是:一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼。樹(shù)、圖等都是非線性結(jié)構(gòu)。

　�。�2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

　　數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器里的實(shí)現(xiàn)（亦稱(chēng)為映象）。它是依賴(lài)于計(jì)算機(jī)的，并有四種基本的存儲(chǔ)映象方法。它們是:
　　
　　①順序存儲(chǔ)方法 該方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元內(nèi)，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。順序存儲(chǔ)方法主要用于線性的數(shù)據(jù)結(jié)構(gòu)，非線性的數(shù)據(jù)結(jié)構(gòu)也可以通過(guò)某種線性化方法來(lái)實(shí)現(xiàn)順序存儲(chǔ)。

　　②鏈接存儲(chǔ)方法 在鏈接存儲(chǔ)方法中，邏輯上相鄰的結(jié)點(diǎn)在物理位置上未必相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。

　�、鬯饕�存儲(chǔ)方法 該方法通常是在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，還建立一個(gè)附加的索引表，索引表中的每一項(xiàng)稱(chēng)為索引項(xiàng)，索引項(xiàng)的一般形式是:（關(guān)鍵字，地址）。關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。
　　
　�、苌⒘写鎯�(chǔ)方法 在散列存儲(chǔ)方法中，結(jié)點(diǎn)的存儲(chǔ)地址是根據(jù)結(jié)點(diǎn)的關(guān)鍵字值直接計(jì)算出來(lái)的。上述四種基本的存儲(chǔ)方法也可以組合起來(lái)對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)映象。

　　（3）數(shù)據(jù)的運(yùn)算

　　數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。常用的運(yùn)算有:查找、插入、刪除、更新、排序等。顯然，對(duì)數(shù)據(jù)運(yùn)算的具體實(shí)現(xiàn)方法只有在確定了存儲(chǔ)結(jié)構(gòu)之后才能加以考慮。

　　2.算法

　�。�1）算法及其特征
　　
　　簡(jiǎn)單地說(shuō)，一個(gè)算法就是一種解題方法，更嚴(yán)格地說(shuō)，算法是由若干條指令組成的有窮序列，它必須具有以下特征:
　　
　　①有窮性 一個(gè)算法必須在執(zhí)行有窮步后結(jié)束。

　�、诖_定性 算法的每一步必須是確切地定義的，無(wú)二義性。

　�、劭尚行� 算法中的所有待實(shí)現(xiàn)的運(yùn)算必須在原則上能夠由人使用筆和紙?jiān)谧鲇懈F次運(yùn)算后完成。

　�、茌斎� 一個(gè)算法具有0個(gè)或多個(gè)輸入的外界量，它們是算法開(kāi)始前對(duì)算法最初給出的量。

　�、葺敵� 一個(gè)算法至少產(chǎn)生一個(gè)輸出，它們是與輸入有某種關(guān)系的量。
　　
　　算法的含義與程序十分相似，但二者又有區(qū)別。一個(gè)程序不一定滿足有窮性，操作系統(tǒng)就是如此，只要整個(gè)系統(tǒng)不被破壞，操作系統(tǒng)就永遠(yuǎn)不會(huì)停止，所以操作系統(tǒng)程序不是一個(gè)算法。另外，程序中的指令必須是機(jī)器可以執(zhí)行的，而算法中的指令則無(wú)此限制。但是，一個(gè)算法如果用機(jī)器可執(zhí)行的語(yǔ)言書(shū)寫(xiě)，則它就是一個(gè)程序。

　　對(duì)一個(gè)算法的描述可以采用自然語(yǔ)言、數(shù)學(xué)語(yǔ)言、約定的符號(hào)語(yǔ)言、以及圖解等方式

　�。�2）算法的分析
　　
　　求解同一個(gè)問(wèn)題可以有多種不同的算法，評(píng)價(jià)一個(gè)算法的優(yōu)劣除了正確性和簡(jiǎn)明性外，主要考慮兩點(diǎn):一是執(zhí)行算法所耗費(fèi)的時(shí)間，二是執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，特別是輔助存儲(chǔ)空間的耗費(fèi)。就這兩者而言，前者顯得比后者更為重要，在數(shù)據(jù)結(jié)構(gòu)中往往更注重對(duì)算法執(zhí)行時(shí)間的分析。
　　
　　一個(gè)算法所耗費(fèi)的時(shí)間是該算法中每條語(yǔ)句的執(zhí)行時(shí)間之和，而每條語(yǔ)句的執(zhí)行時(shí)間是該語(yǔ)句執(zhí)行次數(shù)（頻度）與該語(yǔ)句一次執(zhí)行所需時(shí)間的乘積。如果假定每條語(yǔ)句一次執(zhí)行所需的時(shí)間均為單位時(shí)間，則一個(gè)算法的時(shí)間耗費(fèi)就是該算法中所有語(yǔ)句的頻度之和。

希望與更多計(jì)算機(jī)等級(jí)考試的網(wǎng)友交流，請(qǐng)進(jìn)入計(jì)算機(jī)等級(jí)考試論壇

更多信息請(qǐng)?jiān)L問(wèn)：考試吧計(jì)算機(jī)等級(jí)考試欄目