【正文】 8+1) ? = ln9/In2=4 ?log2 (15+ 1)? =In16/In2=4 深度為 6的完全二叉樹 具有 32～ 63 深度為 7的完全二叉樹 具有 64～ 127 深度為 8的完全二叉樹 具有 128～ 255 深度為 9的完全二叉樹 具有 256～ 511 深度為 10的完全二叉樹 具有 512～ 1023 深度為 11的完全二叉樹 具有 1024～ 2047 第 73頁 性質(zhì) 5：具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 11 2 3 4 5 6 7 8 9 10 12 1 例： n=2 k=2 n=6 k=3 n=7 k=3 n=8 k=4 n=12 k=4 1lo g 2 ?n第 74頁 性質(zhì) 6：如果對(duì)一棵有 n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層 序編號(hào)，則對(duì)任一結(jié)點(diǎn) i(1=i=n)有： (1)如果 i=1,則結(jié)點(diǎn) i是二叉樹的根 ,無雙親 。則稱這棵二叉樹為 完全二叉樹 。最后一層的結(jié)點(diǎn)均為 0度。 C． 樹的結(jié)點(diǎn)無左 、 右之分 ， 二叉樹的 結(jié)點(diǎn) 子樹有明確的左 、 右之分 。稱左子樹和右子樹 二叉樹的 5種基本形態(tài) 第 65頁 ★ 樹與二叉樹的區(qū)別 A． 樹和二叉樹的結(jié)點(diǎn)個(gè)數(shù)最少都可為 0。 ① ② ③ ④ 第 64頁 二叉樹的概念 定義： 二叉 樹是一種有序的樹形結(jié)構(gòu)?？梢杂卸鄠€(gè)。 ?空樹： 無結(jié)點(diǎn)則稱為空樹； ? 父結(jié)點(diǎn)： 結(jié)點(diǎn)的前件稱該結(jié)點(diǎn)的父結(jié)點(diǎn)。（ n=0） A B D F E C G H I J K M ?結(jié)點(diǎn)： ?根結(jié)點(diǎn)： 沒有前件的結(jié)點(diǎn)只有一個(gè)稱為根結(jié)點(diǎn)。 ? 樹的概念 ? 二叉樹的概念 ? 二叉樹的存儲(chǔ) ? 二叉樹的遍歷 3. 樹與二叉樹 第 61頁 樹的概念 ? 樹的定義：是一種簡單的非線性結(jié)構(gòu)。這種情況稱為 【 2】 。而實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用 A) 棧 B) 堆 C) 數(shù)組 D) 鏈表 例題講解 ? 棧底至棧頂依次存放元素 A、 B、 C、 D，在第五個(gè)元素 E入棧前，棧中元素可以出棧，則出棧序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE ? 棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是 A) 線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu) B) 散列方式和索引方式 C) 鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組 D) 線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu) ? 棧和隊(duì)列通常采用的存儲(chǔ)結(jié)構(gòu)是 【 1】 。 ? 用鏈表表示線性表的突出優(yōu)點(diǎn)是 【 1】 。 ? 在單鏈表中，增加頭結(jié)點(diǎn)的目的是 A) 方便運(yùn)算的實(shí)現(xiàn) B) 使單鏈表至少有一個(gè)結(jié)點(diǎn) C) 標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置 D) 說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn) 例題講解 ? 非空的循環(huán)單鏈表 head的尾結(jié)點(diǎn) (由 p所指向 ) ，滿足 A) pnext==NULL B) p==NULL C) pnext=head D) p=head ? 循環(huán)鏈表的主要優(yōu)點(diǎn)是 A) 不再需要頭指針了 B) 從表中任一結(jié)點(diǎn)出發(fā)都能訪問到整個(gè)鏈表 C) 在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開 D) 已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易的找到它的直接前件 ? 當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。 ? 線性表若采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址 A) 必須是連續(xù)的 B) 部分地址必須是連續(xù)的 C) 一定是不連續(xù)的 D) 連續(xù)不連續(xù)都可以 例題講解 相鄰 ? 線性表 L=(a1,a2,a3,…ai ， …an) ，下列說法正確的是 A) 每個(gè)元素都有一個(gè)直接前件和直接后件 B) 線性表中至少要有一個(gè)元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè) 且只有一個(gè)直接前件和直接后件 ? 線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是 A) 順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu) B) 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu) C) 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) D) 任意存取的存儲(chǔ)結(jié)構(gòu)、任意存取的存儲(chǔ)結(jié)構(gòu) ? 下列敘述中，錯(cuò)誤的是 A) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu) ?根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成 A) 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) ?當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)時(shí)，其主要特點(diǎn)是 【 1】 。 ? 下列敘述中，錯(cuò)誤的是 A) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)元素 ? 鏈表不具有的特點(diǎn)是 A) 不必事先估計(jì)存儲(chǔ)空間 B) 可隨機(jī)訪問任一元素 C) 插入刪除不需要移動(dòng)元素 D) 所需空間與線性表長度成正比 ? 順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置 【 2】 的存儲(chǔ)單元中。 ? 數(shù)據(jù)處理的最小單位是 A) 數(shù)據(jù) B) 數(shù)據(jù)元素 C) 數(shù)據(jù)項(xiàng) D) 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及 A) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) B) 計(jì)算方法 C) 數(shù)據(jù)映象 D) 邏輯存儲(chǔ) ? 線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是 A) 順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu) B) 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu) C) 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) D) 任意存取的存儲(chǔ)結(jié)構(gòu)、任意存取的存儲(chǔ)結(jié)構(gòu) 相鄰 ? 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成 A) 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 【 2】 以及對(duì)數(shù)據(jù)的操作運(yùn)算。 ? 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的 A) 存儲(chǔ)結(jié)構(gòu) B) 物理結(jié)構(gòu) C) 邏輯結(jié)構(gòu) D) 物理和存儲(chǔ)結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 【 1】 兩大類。假設(shè)用一個(gè)長度為 50的數(shù)組（數(shù)組元索的下標(biāo)從 0到 49）作為棧的存儲(chǔ)空間，棧底指針 bottom指間棧底元素，棧頂指針 top指向棧頂元素，如果 bottom=49，top=30（數(shù)組下標(biāo)），則棧中具有 【 】 個(gè)元素。（ 2022年 3月） 答案： A， B， C， D， E， F， 5， 4， 3， 2， 1 第 48頁 9. 設(shè)某循環(huán)隊(duì)列的容量為 50，如果頭指針 front=45(指向隊(duì)頭元素的前一位置 )，尾指針 rear=10(指向隊(duì)尾元素 )，則該循環(huán)隊(duì)列中共有 【 2】 個(gè)元素。 7. 一個(gè)隊(duì)列的初始狀態(tài)為空。 6。 下列敘述中正確的是 （ ） 。 答案：線性結(jié)構(gòu)。 4. 下列數(shù)據(jù)結(jié)構(gòu)中 ， 屬于非線性結(jié)構(gòu)的是 A） 循環(huán)隊(duì)列 B) 帶鏈隊(duì)列 C) 二叉樹 D） 帶鏈棧 答案： D。（ 2022年 9月） 答案：存儲(chǔ)結(jié)構(gòu)。 ? 循環(huán)隊(duì)列的運(yùn)算 隊(duì)列中進(jìn)行插入的一端稱做隊(duì)尾 (rear),進(jìn)行刪除的一端稱做隊(duì)首 (front)。 a1 , a2 , a3 , a4 , ………… an1 , an 隊(duì) 列 示 意 圖 隊(duì)頭 隊(duì)尾 先進(jìn)先出后進(jìn)后出（ LIFO） 第 41頁 e3 e4 (c) (c) e1,e2出隊(duì)， e4入隊(duì) 隊(duì) 滿 rear =3 front e1 e2 e3 (b) rear front (b)e1,e2,e3入隊(duì) 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算 3 2 1 0 (a) rear=front=1(隊(duì)空） rear front 空隊(duì)列 : 非空隊(duì)列 : 隊(duì)列元素個(gè)數(shù) : rear=front=1 front始終指向隊(duì)頭元素前一個(gè)位置，而 rear始終指向隊(duì)尾元素的位置 rearfront 第 42頁 隊(duì)列的物理存儲(chǔ)結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈?zhǔn)浇Y(jié)構(gòu)。 基本運(yùn)算： 壓（進(jìn)）棧： PUSH 出棧： POP 讀棧頂元素： gettop 第 39頁 例子： top base EDCBA top base CBA base top A base top 空桟： top＝ base 非空桟： top始終在桟頂元素的后一個(gè)位置 桟的元素個(gè)數(shù)： topbase 上溢 下溢 第 40頁 隊(duì)列 定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在 表的另一端進(jìn)行刪除的線性表 。 ? 順序棧的進(jìn)棧和出棧運(yùn)算 ? 棧的基本運(yùn)算有三種：入棧、退棧和讀棧頂元素 在順序棧中插入和刪除運(yùn)算不需要移動(dòng)表中其他數(shù)據(jù)元素 。 … a1 a2 an 棧底 棧頂 進(jìn)棧 出棧 棧 s=(a1,a2,…,an) 后進(jìn)先出或先進(jìn)后出（ LIFO） 第 37頁 ?棧的物理存儲(chǔ)結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈表結(jié)構(gòu)。 棧底 —— 表頭。 ? 棧（ Stack）及其基本運(yùn)算 ? 隊(duì)列（ Queue）及其基本運(yùn)算 ? 循環(huán)隊(duì)列及其基本運(yùn)算 第 36頁 1 .棧 棧 —— 是限定僅在表尾進(jìn)行插入或刪除操作的線性表。各種事務(wù)處理（ 可采用順序表或單鏈表結(jié)構(gòu) ） 。計(jì)算機(jī)的目錄系統(tǒng)； ? ? .高級(jí)語言中的數(shù)組； ? 在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前趨。 HEAD 3 1 5 10 a2 a3 a4 a1 提問：單向鏈表的缺點(diǎn)是什么？ 提示：如何尋找結(jié)點(diǎn)的直接前趨。 可直接確定一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn) 。 將最后一個(gè)結(jié)點(diǎn)的空指針改為指向頭結(jié)點(diǎn) ， 從任一結(jié)點(diǎn)出發(fā)均可找到其它結(jié)點(diǎn) 。 ? 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅存儲(chǔ)結(jié)點(diǎn)的值，而且存儲(chǔ)結(jié)點(diǎn)之間的關(guān)系： ?鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分為單鏈表、雙向鏈表、循環(huán)鏈表 ?線性鏈表不能隨機(jī)存取 數(shù)據(jù)域 指針域 第 29頁 設(shè)線性表為 （ a1， a2， a3， a4， a5） 1 a2 9 2 3 a1 1 4 5 a4 10 6 7 8 9 a3 5 10 a5 0 HEAD 3 a1 a2 a5 a3 a4 HEAD 3 1 9 5 10 線性鏈表的邏輯狀態(tài) 線性鏈表 的物理狀態(tài) 1 a1 2 a2 3 a3 4 a4 5 a5 6 7 線性表的 順序存儲(chǔ) 結(jié)構(gòu) 注意 :1 2 3 此類編號(hào)不代表所在的地址單元的地址編碼 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 及其插入與刪除操作 第 30頁 zhao qian sun li zhou wu zheng wang / H 存儲(chǔ)地址 數(shù)據(jù) 1 7 13 19 25 31 37 43 li qian sun wang wu zhao zheng