6．棧與隊(duì)列
要深刻領(lǐng)會(huì)二者的概念，以及對(duì)二者進(jìn)行插入、刪除運(yùn)算的特點(diǎn)，這是考試的重點(diǎn)。
棧實(shí)際上也是線性表，只不過是一種特殊的線性表。在這種特殊的線性表中，其插入與刪除運(yùn)算都只在線性表的一端進(jìn)行。即在這種線性表的結(jié)構(gòu)中，一端是封閉的，不允許進(jìn)行插入與刪除元素；另一端是開口的，允許插入與刪除元素。允許插入與刪除運(yùn)算的一端稱為棧頂，而不允許插入與刪除運(yùn)算的一端稱為棧底。棧頂元素總是最后被插入的元素，從而也是最先能被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。即棧是按照“先進(jìn)后出”（First In Last Out，F(xiàn)ILO）或“后進(jìn)先出”（Last In First Out，LIFO）的原則組織數(shù)據(jù)的，因此，棧也被稱為“先進(jìn)后出”表或“后進(jìn)先出”表。由此可以看出，棧具有記憶作用。對(duì)棧?？梢赃M(jìn)行進(jìn)棧、出棧、讀取棧頂元素的運(yùn)算。
隊(duì)列是指允許在一端進(jìn)行插入運(yùn)算、而在另一端進(jìn)行刪除運(yùn)算的線性表。允許插入運(yùn)算的一端稱為隊(duì)尾，通常用一個(gè)稱為隊(duì)尾指針的指針指向隊(duì)尾元素，即隊(duì)尾指針總是指向最后被插入的元素。允許刪除運(yùn)算的一端稱為隊(duì)頭，通常也用一個(gè)隊(duì)頭指針指向隊(duì)頭的元素。顯然，在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除，反之，最后插入的元素將最后才能被刪除。因此，隊(duì)列又稱為“先進(jìn)先出”（First In First Out，F(xiàn)IFO）或“后進(jìn)后出”（Last In Last Out，LILO）的線性表。對(duì)隊(duì)列可以進(jìn)行入隊(duì)、退隊(duì)運(yùn)算。
7．循環(huán)隊(duì)列
重點(diǎn)注意循環(huán)隊(duì)列的概念、存儲(chǔ)方式。
循環(huán)隊(duì)列是隊(duì)列順序存儲(chǔ)結(jié)構(gòu)的一種，它將m個(gè)物理上連續(xù)的存儲(chǔ)單元，在邏輯上形成一個(gè)環(huán)狀，供隊(duì)列循環(huán)使用。
具體來說，在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，因此，從隊(duì)頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。
8．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（線性鏈表）
（1）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其有關(guān)運(yùn)算
在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，一個(gè)元素用一個(gè)結(jié)點(diǎn)來存儲(chǔ)，每個(gè)結(jié)點(diǎn)含有兩個(gè)域，一個(gè)數(shù)據(jù)域用于存放數(shù)據(jù)元素值，一個(gè)指針域，用于存放指針，該指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)（即前件或后件）。
在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序（即存儲(chǔ)空間位置）與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。要特別注意，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)方式的不同。
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)又稱為線性鏈表。
對(duì)線性鏈表的運(yùn)算主要包括：查找指定元素、插入、刪除運(yùn)算等。不像順序存儲(chǔ)結(jié)構(gòu)那樣，對(duì)線性鏈表的插入與刪除運(yùn)算不需要移動(dòng)數(shù)據(jù)元素，而只需改變有關(guān)結(jié)點(diǎn)的指針即可。
（2）循環(huán)鏈表
在對(duì)線性鏈表進(jìn)行運(yùn)算的過程中，雖然其插入與刪除運(yùn)算比較方便，但還存在一個(gè)問題，即對(duì)于空表和對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。為了克服線性鏈表的這個(gè)缺點(diǎn)，可以采用另一種鏈接方式，即循環(huán)鏈表的結(jié)構(gòu)，使整個(gè)鏈成為一個(gè)環(huán)狀結(jié)構(gòu)。在此，需要注意線性鏈表與循環(huán)鏈表在存儲(chǔ)方式上的不同。
循環(huán)鏈表的結(jié)構(gòu)與線性鏈表相比，具有以下兩個(gè)特點(diǎn)：
① 在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。
② 循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。
9．樹與二叉樹
樹是一種非線性結(jié)構(gòu)，在這種結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。而二叉樹也是一種非線性結(jié)構(gòu)，它與樹結(jié)構(gòu)相似，并且樹結(jié)構(gòu)的所有術(shù)語都可以用到二叉樹這種數(shù)據(jù)結(jié)構(gòu)上。
二叉樹具有以下兩個(gè)特點(diǎn)：
① 非空二叉樹只有一個(gè)根結(jié)點(diǎn)。
② 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。
因此，二叉樹中每一個(gè)結(jié)點(diǎn)的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹。
對(duì)于二叉樹，其概念與性質(zhì)是考試的重點(diǎn)。要特別注意二叉樹的有關(guān)性質(zhì)。
10．滿二叉樹與完全二叉樹
滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹，對(duì)這兩種二叉樹的概念上的理解是考試的重點(diǎn)。
（1）滿二叉樹
滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)，也就是說，在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第k層有2k–1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m–1個(gè)結(jié)點(diǎn)。
（2）完全二叉樹
完全二叉樹是這樣的二叉樹，除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值。
11．二叉樹的遍歷
二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷可以分為三種：前序遍歷、中序遍歷、后序遍歷。這三種遍歷方式是每次考試的重點(diǎn)，要求對(duì)于某一棵二叉樹應(yīng)能寫出對(duì)應(yīng)的遍歷序列。
（1）交換類排序法
交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。冒泡排序法與快速排序法都屬于交換類排序方法。
冒泡排序法是一種最簡(jiǎn)單的交換類排序方法，它是通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序。假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n–1)/2。但這個(gè)工作量不是必需的，一般情況下要小于這個(gè)工作量。
快速排序法也是一種交換類的排序方法，但由于它比冒泡排序法的速度快，因此稱之為快速排序法。其關(guān)鍵是對(duì)線性表進(jìn)行分割，以及對(duì)各分割出的子表再進(jìn)行分割。