【正文】 2. 數(shù)據(jù)說明 ? 數(shù)據(jù)說明的次序應(yīng)該規(guī)范化 ? 變量安排有序化 ? 對復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說明 3. 語句的結(jié)構(gòu) ? 每條語句簡單明了 ? 盡量不用或少用 GOTO語。 3. 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對象，方法，屬性及繼承與多態(tài)性。 0 nlog2n交換排序 第 115頁 ?在下列幾種排序方法中，要求內(nèi)存量最大的是 A) 插入排序 B) 選擇排序 C) 快速排序 D) 歸并排序 ?在待排序的元素序列基本有序的前提下，效率最高的排序方法是 A) 冒泡排序 B) 選擇排序 C) 快速排序 D) 歸并排序 ?希爾排序?qū)儆? A) 交換排序 B) 歸并排序 C) 選擇排序 D) 插入排序 ?對長度為 n的線性表進(jìn)行順序查找，在最壞的情況下所需要的比較次數(shù)為 Ａ ) n+1 B) n C) (n+1)/2 D) n/2 第 116頁 第 117頁 第二章 程序設(shè)計(jì)基礎(chǔ) 內(nèi)容： 1. 程序設(shè)計(jì)方法與風(fēng)格。 ?在最壞情況下，堆排序需要比較的次數(shù)為 【 2】 。 ?長度為 n的順序存儲(chǔ)線性表中，當(dāng)在任何位置上插入一個(gè)元素概率都相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為 【 1】 。（ 06年 9月 ） A） 63 B） 64 C） 6 D） 7 (3) 下列數(shù)據(jù)結(jié)構(gòu)中 ， 能用二分法進(jìn)行查找的是 （ 2022年 9月 ） A） 順序存儲(chǔ)的有序線性表 B） 線性鏈表 C） 二叉鏈表 D） 有序線性鏈表 (4) 下列排序方法中 ， 最壞情況下比較次數(shù)最少的是 （ 09年 3月 ） A） 冒泡排序 B） 簡單選擇排序 C） 直接插入排序 D） 堆排序 D B A D 第 113頁 ?在長度為 n的有序線性表中進(jìn)行二分查找。 ? 若待排序的記錄已基本有序，可采用簡單插入和起泡 排序。 ? 若待排序的記錄個(gè)數(shù) n較小時(shí)，可采用簡單排序方法。 時(shí)間復(fù)雜度： O(log2n) 當(dāng)待排序列逆序時(shí) ， 蛻變成冒泡排序 ， 時(shí)間復(fù)雜度 : O(n(n1)/2) 第 109頁 內(nèi)部排序方法的選擇 各種排序方法各有優(yōu)缺點(diǎn)，故在不同情況下可作不同的選擇。 第 105頁 冒泡排序的方法 ?設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（ 18， 20， 15， 32， 4， 25），第一趟 冒泡排序后的序列狀態(tài)如圖所示 ： ? 18 20 15 32 4 25 ? 18 20 15 32 4 25 ? 18 15 20 32 4 25 ? 18 15 20 32 4 25 ? 18 15 20 4 32 25 ? 18 15 20 4 25 32 最大數(shù) ?第二趟冒泡排序 第 106頁 Q：第二趟冒泡排序后的結(jié)果是什么樣的？達(dá)到了最終的排序目標(biāo)嗎？一共需要多少次能夠最后成為有序序列？ Q：你覺得冒泡排序的效率如何？如果是你，你會(huì)用什么方法來排序？ 冒泡排序比較簡單，當(dāng)初始序列基本有序時(shí)，冒泡排序有較高的效率，反之效率較低。 第一趟：第 1個(gè)與第 2個(gè)比較 ， 大則交換；第 2個(gè)與第 3個(gè)比較 ， 大則交換 ， …… 關(guān)鍵字最大的記錄交換到最后一個(gè)位置上； 第二趟：對前 n1個(gè)記錄進(jìn)行同樣的操作 ， 關(guān)鍵字次大的記錄交換 到第 n1個(gè) 位置上； 依次類推 ， 則完成排序 。 冒泡排序（起泡排序） 思想： 小的浮起 ， 大的沉底 。 89 76 24 33 15 10 11 25 36 49 78 56 (a):堆頂元素取最大值 (b):堆頂元素取最小值 堆排序需要比較的次數(shù)為 O(nlog2n) (1) 堆的示例 第 103頁 交 換 排 序 交換排序的特點(diǎn)在于 交換 。 選擇排序 簡單選擇排序、堆排序 簡單選擇排序法 , 最壞情況需要 n(n1)/2次比較； 時(shí)間復(fù)雜度為 O(n2)， 適用于 待排序元素較少 的情況。 第 98頁 該算法適合于 n 較小的情況 ， 時(shí)間復(fù)雜度為 O(n2). 待排元素序列： [53] 27 36 15 69 42 第一次排序： [27 53] 36 15 69 42 第二次排序： [27 36 53] 15 69 42 第三次排序： [15 27 36 53] 69 42 第四次排序： [15 27 36 53 69] 42 第五次排序： [15 27 36 42 53 69] 直接插入排序示例 對于有 n個(gè)數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行 n1趟 最壞情況下： 需要 n(n1)/2次比較 最好： n1次比較 第 99頁 希爾排序： 希爾排序的基本思想 : 先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行 直接插入排序 ,待整個(gè)序列中的記錄“基本有序”時(shí) ,再對全 體記錄進(jìn)行一次直接插入排序 . 最壞情況下：需要 O( )次比較 第 100頁 簡單選擇排序 ? 思想：首先從 1~n個(gè)元素中選出關(guān)鍵字 最小 的記錄交換到 第一個(gè) 位置上。 排序過程的組成步驟： ? 首先 比較 兩個(gè)關(guān)鍵字的大??； ? 然后將記錄從一個(gè)位置 移動(dòng) 到另一個(gè)位置。 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 第 1次： { 3， 5， 11， 17， 21， 23， 28， 30， 32， 50 } K=30 mid1=（ 1+10） /2 = 5 ka(mid1)=a(5)=21 第 2次： { 23， 28， 30， 32， 50 } mid2 = （ 6+10） /2 = 8 K=a(mid2)=a(8)=30 low high mid low high mid 第 94|92頁 ? 練習(xí) 假設(shè)待查有序（升序）順序表中數(shù)據(jù)元素的關(guān)鍵字序列為（ 8,18,27,42,47,50,56, 68,95,120），用折半查找方法查找關(guān)鍵字值為 27的數(shù)據(jù)元素 . 對于長度為 n的有序線性表，最壞情況只需比較 log2n次。最壞的情況下，需要比較 log2n次。 2）若 x小于中間項(xiàng)的值 ,則在線性表的前半部分查找； 3）若 x大于中間項(xiàng)的值，則在線性表的后半部分查找。 ?前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的 有序表中進(jìn)行 。 最好情況： 1 最壞情況： n ◆ 在下面兩種情況下只能采取順序查找： a. 線性表為無序表（元素排列是無序的）； b. 即使是有序線性表，但采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 ◆ 在平均情況下，大約要與表中一半以上元素進(jìn)行比較，效率較低。 ? 通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法： ? 順序查找 ? 二分查找 第 91頁 順序查找（線性查找） ◆ 查找過程： 對給定的一關(guān)鍵字 K，從線性表的一端開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和 K的比較，直到找到關(guān)鍵字等于 K的記錄或到達(dá)表的另一端。 ? 若找到了滿足條件的結(jié)點(diǎn)，稱查找成功；否則稱查找失敗。 350 3 DEBFCA 第 90頁 ⒌ 查找技術(shù) 查找是數(shù)據(jù)處理的重要內(nèi)容。 ?在一個(gè)容量為 15的循環(huán)隊(duì)列中，若頭指針 front=6，尾指針 rear=9，則該循環(huán)隊(duì)列中共有（ ）個(gè)元素。 ? 具有 3個(gè)結(jié)點(diǎn)的二叉樹有 A) 2種形態(tài) B) 4種形態(tài) C) 7種形態(tài) D) 5種形態(tài) ? 設(shè)一棵二叉樹中有 3個(gè)葉子結(jié)點(diǎn)，有 8個(gè)度為 1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為 A) 12 B) 13 C) 14 D) 15 雙親結(jié)點(diǎn) ? 設(shè)有下列二叉樹： 對此二叉樹前序遍歷的結(jié)果為 A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT ? 設(shè)有下列二叉樹： 對此二叉樹的中序遍歷的結(jié)果為 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA ?設(shè)樹 T的度為 4,其中度為 4的結(jié)點(diǎn)個(gè)數(shù)分別為 1。 中序遍歷的結(jié)果： E B A F H G C D （ 3）后序遍歷（ LRD） 右根左 若二叉樹為空，則結(jié)束遍歷操作；否則 ? 后序遍歷左子樹； ? 后序遍歷右子樹； ? 訪問根結(jié)點(diǎn)。 （ 1）先（前）序遍歷（ DLR） 根左右 若二叉樹為空，則結(jié)束遍歷操作；否則 ? 訪問根結(jié)點(diǎn)； ? 先序 遍歷左子樹； ? 先序 遍歷右子樹。 ? 二叉樹的遍歷的次序與樹型結(jié)構(gòu)上的大多數(shù)運(yùn)算有聯(lián)系。 例： A B C D E F G A ^ B ^ C ^ D ^ E ^ F ^ ^ G ^ 第 80頁 三叉鏈表： 三叉鏈表的結(jié)點(diǎn)包含四個(gè)域： 數(shù)據(jù)域、左、右、雙親指針域。 0 0 0 0 F E 0 0 0 D C 0 B A 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 一般二叉樹必須按完全二叉樹的形式存儲(chǔ) ， 將造成存儲(chǔ)的浪費(fèi) 。 11 A B c F E D ● ● ● ● ● ● ● ● ● 1 2 4 8 9 10 5 6 3 7 12 13 14 15 (1) 順序存儲(chǔ)結(jié)構(gòu) (1) 順序存儲(chǔ)結(jié)構(gòu) 2h1= 241 = 15 用一組連續(xù)的存儲(chǔ)單元存放二叉樹的數(shù)據(jù)元素 。對于滿二叉樹和完全二叉樹可以按層進(jìn)行順序存儲(chǔ)。 4答案： 19。 5答案： 32。 （ 2022年 9月 ） 樹型結(jié)構(gòu)方面的考題 1答案： C。 (07年 4月 ） 3：一棵二叉樹中共有 70個(gè)葉子結(jié)點(diǎn)與 80個(gè)度為 1的結(jié)點(diǎn) ， 則該二叉樹中的總結(jié)點(diǎn)數(shù)為 （ 07年 9月 ） A） 219 B） 221 C） 229 D） 231 4： 某二叉樹中度為 2的結(jié)點(diǎn)有 18個(gè) ， 則該二叉樹中有 【 】 個(gè)葉子結(jié)點(diǎn) 。 ∵ 2*i+1=1312 ∴ 其無右子結(jié)點(diǎn)。 i=1 是樹的根 ,無雙親 。 總之：如 i1它的雙親是 i/2取整，左子結(jié)點(diǎn)是 2*i，右子結(jié)點(diǎn)是 2*i+總數(shù)民 N，則為沒有。 (2)如果 2i=n,則編號 i的左子結(jié)點(diǎn)為 2 i，否則無左子結(jié)點(diǎn)，顯然也就沒有右子結(jié)點(diǎn)。 第 70頁 滿二叉樹 完全二叉樹 完全二叉樹是滿二叉樹 滿二叉樹也是完全二叉樹 第 71頁 非完全二叉樹 深度為 4的完全二叉樹 第 72頁 【 性質(zhì) 4】 具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 ?log2 (n+1) ?其中， ?log2n? 的結(jié)果是不大于 log2n的最大整數(shù) 深度為 4的滿二叉樹 深度為 4的完全二叉樹 深度為 3的完全二叉樹具有 4～ 7個(gè)結(jié)點(diǎn) 深度為 4的完全二叉樹 具有 8～ 15 深度為 5的完全二叉樹 具有 15～ 31 ?log2(