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