【文章內(nèi)容簡(jiǎn)介】 ? Ａ )在棧中只能插入數(shù)據(jù) B） 在棧中只能刪除數(shù)據(jù) ? C） 棧是先進(jìn)先出的線性表 D） 棧是后進(jìn)先出的線性表 ? 答案： D ? 下列關(guān)于隊(duì)列的敘述中正確的是（ ） ? Ａ）在隊(duì)列中只能插入數(shù)據(jù) B） 在隊(duì)列中只能刪除數(shù)據(jù) ? C） 隊(duì)列是先進(jìn)先出的線性表 D） 隊(duì)列是后進(jìn)先出的線性表 ? 答案： C 線性鏈表 線性鏈表的基本概念 數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。 結(jié)點(diǎn)由兩部分組成： （ 1）用于存儲(chǔ)數(shù)據(jù)元素值，稱為數(shù)據(jù)域； （ 2）用于存放指針，稱為指針域，用于指向前一個(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ǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。 線性表中存儲(chǔ)結(jié)點(diǎn)的結(jié)構(gòu) 線性鏈表的基本運(yùn)算 線性鏈表的運(yùn)算主要有以下幾個(gè)： ① 在線性鏈表中包含指定元素的結(jié)點(diǎn)之前 插入 一個(gè)新元素。 ② 在線性鏈表中 刪除 包含指定元素的結(jié)點(diǎn)。 ③ 將兩個(gè)線性鏈表按要求 合并 成一個(gè)線性 鏈表。 插入 線性鏈表的插入 是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下 的線性表中插入一個(gè)新元素。 為了要在線性鏈表中插入一個(gè)新元素， 首先要給該元素分配一個(gè)新結(jié)點(diǎn)，然后將存 放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的 位置。 刪除 線性鏈表的刪除 指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的 線性表中刪除包含指定元素的結(jié)點(diǎn)。 為了在線性鏈表中刪除包含指定元素的 結(jié)點(diǎn)，首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn)， 然后將要?jiǎng)h除結(jié)點(diǎn)放回到可利用棧。 循環(huán)鏈表及其基本運(yùn)算 前面所討論的線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問(wèn)題。在運(yùn)算過(guò)程中，對(duì)于空表和對(duì)一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。為了克服線性表的這個(gè)缺點(diǎn)，可以采用另外一種鏈接方式，即循環(huán)鏈表（ Circular Linked List）。循環(huán)鏈表是另一種形式的 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。它是將單鏈表的表中最后一個(gè)結(jié)點(diǎn)指針指向鏈表的表頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，這樣從表中任一結(jié)點(diǎn)出發(fā)都可找到表中其他的結(jié)點(diǎn)。 循環(huán)鏈表 循環(huán)鏈表具有以下兩個(gè)特點(diǎn)：（ 1）在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來(lái)設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。（ 2）循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問(wèn)到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這點(diǎn)。 由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因此在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表的運(yùn)算統(tǒng)一 。 在實(shí)際應(yīng)用中，循環(huán)鏈表與線性單鏈表相比主要有以下兩個(gè)方面的優(yōu)點(diǎn)： ① 在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn) 的位置，就可以從它出發(fā)訪問(wèn)到表中其他所 有的結(jié)點(diǎn)。 ② 由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因 此，在任何情況下，循環(huán)鏈表中至少有一個(gè) 結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。 歷年考題 （ 5）下列對(duì)于線性鏈表的描述中正確的是 A）存儲(chǔ)空間不一定是連續(xù)，且各元素的存儲(chǔ)順序是任意的 B）存儲(chǔ)空間不一定是連續(xù)，且前件與元素一定存儲(chǔ)在后件元素的前面 C）存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面 D）存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的 解析：在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。 樹(shù)與二叉樹(shù) 樹(shù)的基本概念 樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。 在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱樹(shù)的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。 在樹(shù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹(shù)的度。樹(shù)的最大層次稱為樹(shù)的深度。 二叉樹(shù)及其基本性質(zhì) 二叉樹(shù)的特點(diǎn)： （ 1）非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)； （ 2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。 二叉樹(shù)的基本性質(zhì)： 性質(zhì)一：度為 0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為 2的結(jié)點(diǎn)多一個(gè)； 例子 1：某二叉樹(shù)中度為 2的結(jié)點(diǎn)有 18個(gè)，則該二叉樹(shù)中有 19 個(gè)葉子結(jié)點(diǎn)。 二叉樹(shù)的基本性質(zhì)： 性質(zhì) 2：二叉樹(shù)的第 i層上至多有 2 i1（ i ?1） 個(gè) 結(jié)點(diǎn) 。 4 2 3 1 6 7 8 9 10 11 12 13 14 15 5 第三層上 (i=3)， 有 231=4個(gè)節(jié)點(diǎn)。 第四層上 (i=4)， 有 241=8個(gè)節(jié)點(diǎn)。 二叉樹(shù)的基本性質(zhì)： 性質(zhì) 3： 深度為 h的二叉樹(shù)中至多含有 2h1個(gè) 結(jié)點(diǎn) 。 4 2 3 1 6 7 8 9 10 11 12 13 14 15 5 此樹(shù)的深度 h=4， 共有 241=15個(gè)節(jié)點(diǎn)。 滿二叉樹(shù) 滿二叉樹(shù)是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，則 k層上有 2k1個(gè)結(jié)點(diǎn)深度為 m的滿二叉樹(shù)有 2m1個(gè)結(jié)點(diǎn)。 ? 滿二叉樹(shù)的特點(diǎn)： 每一層上都含有最大結(jié)點(diǎn)數(shù)。 完全二叉樹(shù) 完全二叉樹(shù)是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。 注意： 滿二叉樹(shù)是完全二叉樹(shù)，完全二叉樹(shù) 不一定是滿二叉樹(shù)。 ?完全二叉樹(shù)的特點(diǎn)： 除最后一層外，每一層都取最大 結(jié)點(diǎn)數(shù)，最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置。 規(guī)律總結(jié)： 對(duì)于 完全二叉樹(shù) 而言，如果它的結(jié)點(diǎn)個(gè)數(shù)為 偶 數(shù)，則該二叉樹(shù)中：葉子結(jié)點(diǎn)的個(gè)數(shù) =非葉子結(jié)點(diǎn)的個(gè)數(shù)；如果它的結(jié)點(diǎn)個(gè)數(shù)為 奇 數(shù)，則該二叉樹(shù)中：葉子結(jié)點(diǎn)的個(gè)數(shù) =非葉子結(jié)點(diǎn)的個(gè)數(shù) +1，即葉子結(jié)點(diǎn)數(shù)比非葉子結(jié)點(diǎn)數(shù) 多一個(gè) 。 簡(jiǎn)單例題： 設(shè)一棵完全二叉樹(shù)共有 700個(gè)結(jié)點(diǎn)，則 在該二叉樹(shù)中有 350 個(gè)葉子結(jié)點(diǎn)。 在深度為 5的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的 個(gè)數(shù)為（ C ） A) 32 B) 31 C) 16 D) 15 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 在計(jì)算機(jī)中，二叉樹(shù)存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 對(duì)于滿二叉樹(shù)與完全二叉樹(shù)可以按 層序 進(jìn)行順序存儲(chǔ)。 二叉樹(shù)的遍歷 二叉樹(shù)的遍歷是指不重復(fù)地訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。 二叉樹(shù)的遍歷： （ 1）前序遍歷（ DLR），首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)； （ 2）中序遍歷（ LDR），首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)； （ 3）后序遍歷（ LRD）首先遍歷左子樹(shù)，然后訪問(wèn)遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。 1. 前序遍歷（ DLR） 前序遍歷首先訪問(wèn)根結(jié)點(diǎn)然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。在遍歷左、右子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。即： 若二叉樹(shù)為空則結(jié)束返回，否則： （ 1）訪問(wèn)根結(jié)點(diǎn) （ 2）前序遍歷左子樹(shù) （ 3）前序遍歷右子樹(shù) 注意的是：遍歷左右子樹(shù)時(shí)仍然采用前序遍歷方法。 例：如圖二叉樹(shù)， 則前序遍歷結(jié)果是： A B D E C F 2. 中序遍歷（ LDR） 中序遍歷首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。即： 若二叉樹(shù)為空則結(jié)束返回，否則： （ 1）中序遍歷左子樹(shù) （ 2）訪問(wèn)根結(jié)點(diǎn) （ 3）中序遍歷右子樹(shù)。 注意的是：遍歷左右子樹(shù)時(shí)仍然采用中序遍歷方法。 例：如圖二叉樹(shù)， 則中序遍歷結(jié)果是： D B E A F C 3. 后序遍歷（ LRD） 后序遍歷首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。即： 若二叉樹(shù)為空則結(jié)束返回，否則： （ 1）后序遍歷左子樹(shù)， （ 2）后序遍歷右子樹(shù) （ 3）最后訪問(wèn)根結(jié)點(diǎn)。 注意的是：遍歷左右子樹(shù)時(shí)仍然采用后序遍歷方法。 例：如圖二叉樹(shù)， 例 : A B D E C F G D B E A F G C D E B G F C A 前序遍歷： 中序遍歷： 后序遍歷： 歷年考題 【 2022年 4月填空第 1題 】 （ 1）某二叉樹(shù)中度為 2的結(jié)點(diǎn)有 18個(gè)，則該二叉樹(shù)中有 ___19___個(gè)葉子結(jié)點(diǎn)。 在任意一棵二叉樹(shù)中，度為零的節(jié)點(diǎn)總比度為二的節(jié)點(diǎn)多一 【 2022年 9月填空第 4題 】 （ 4）一棵二叉樹(shù)第六層（根結(jié)點(diǎn)為第一層）的結(jié)點(diǎn)數(shù)最多為 ___32___個(gè)。 對(duì)于深度為 6的二叉樹(shù)來(lái)說(shuō)，第 6層的節(jié)點(diǎn)數(shù)最多為二的六減一次方即 32 【 2022年 4月選擇第 7題 】 （ 7）某二叉樹(shù)中有 n個(gè)度為 2的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為 A） n+1 B） n1 C） 2n D） n/2 對(duì)于任何一顆二叉樹(shù) T，如果其葉子節(jié)點(diǎn)數(shù)為 N1，度為 2的節(jié)點(diǎn)數(shù)為 N2，則 N1=N2+1。 歷年考題 提示：注意度和深度的區(qū)別，度是橫向的子節(jié)點(diǎn)數(shù)，深度是縱向的輩分 【 2022年 4月填空第 1題 】 （ 1）在深度為 7的滿二叉樹(shù)中，度為 2的結(jié)點(diǎn)個(gè)數(shù)為 63 。 解析：深度為七的滿二叉樹(shù)有 271=127個(gè)節(jié)點(diǎn)，又因?yàn)樵谌我舛鏄?shù)中，若終端節(jié)點(diǎn)個(gè)數(shù)為 N0，度為 2的節(jié)點(diǎn)數(shù)為 N2,則 N0=N2+1，即總結(jié)點(diǎn)數(shù)為 N0+N2=2N2+1=127,N2=63 【 2022年 9月選擇第 8題 】 （ 8）一棵二叉樹(shù)中共有 70個(gè)葉子結(jié)點(diǎn)與 80個(gè)度為 1的結(jié)點(diǎn)，則該二叉樹(shù)中的總結(jié)點(diǎn)數(shù)為 A)219 B)221 C)229 D)231 解析：任意二叉樹(shù)度為 0的節(jié)點(diǎn)數(shù)始終是比度為 2的節(jié)點(diǎn)數(shù)多一個(gè)，總結(jié)點(diǎn)數(shù) =度為 0的節(jié)點(diǎn)數(shù) +度為 1的節(jié)點(diǎn)數(shù) +度為 2的節(jié)點(diǎn)數(shù) 【 2022年 4月填空第 2題 】 （ 2）深度為 5的滿二叉樹(shù)有 16 個(gè)葉子結(jié)點(diǎn)。 解析： 2的五減一次方 【 2022年 4月選擇第 6題 】 （ 6）對(duì)下列二叉樹(shù) 進(jìn)行后序遍歷的結(jié)果為 A） ABCDEF B） DBEAFC C） ABDECF D） DEBFCA 【 2022年 4月選擇第 6題 】 （ 6）對(duì)下列二叉樹(shù) 進(jìn)行前序遍歷的結(jié)果為 A） DYBEAFCZX B） YDEBFZXCA C） ABDYECFXZ D） ABCDEFXYZ 【 2022年 9月填空第 4題 】 （ 4）對(duì)下列二叉樹(shù)進(jìn)行中序遍歷的結(jié)果為 【 4】 。 答案： ACBDFEHGP 二叉樹(shù)的遍歷 模擬題 ?設(shè)一棵二叉樹(shù)的中序遍歷結(jié)果為 DBEAFC, 前序遍歷結(jié)果為ABDECF， 則后序遍歷結(jié) ? 果為： DEBFCA 已知一棵二叉樹(shù)前序遍歷和中序遍歷分別 為 ABDEGCFH和DBGEACHF， 則該二叉樹(shù) 的后序遍歷為（ B ） A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG 二叉樹(shù)的遍歷 模擬題 ? 具有 3個(gè)結(jié)點(diǎn)的二叉樹(shù)有（ D ） A) 2種形態(tài) B) 4種形態(tài) C) 7種形態(tài) D) 5種形態(tài) ? 設(shè)有下列二叉樹(shù)： 對(duì)此二叉樹(shù)前序遍歷的結(jié)果為（ B ） A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT 查找技術(shù) 查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。 順序查找 順序查找是一種最基本和最簡(jiǎn)單的查找方法。它的思路是，從表中的第一個(gè)元素開(kāi)始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比