【正文】 ? 18 15 20 4 32 25 ? 18 15 20 4 25 32 最大數(shù) ?第二趟冒泡排序 第 106頁 Q：第二趟冒泡排序后的結(jié)果是什么樣的？達(dá)到了最終的排序目標(biāo)嗎？一共需要多少次能夠最后成為有序序列？ Q：你覺得冒泡排序的效率如何？如果是你，你會(huì)用什么方法來排序？ 冒泡排序比較簡(jiǎn)單，當(dāng)初始序列基本有序時(shí)，冒泡排序有較高的效率，反之效率較低。（ 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） 簡(jiǎn)單選擇排序 C） 直接插入排序 D） 堆排序 D B A D 第 113頁 ?在長(zhǎng)度為 n的有序線性表中進(jìn)行二分查找。 3. 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。 0 nlog2n交換排序 第 115頁 ?在下列幾種排序方法中，要求內(nèi)存量最大的是 A) 插入排序 B) 選擇排序 C) 快速排序 D) 歸并排序 ?在待排序的元素序列基本有序的前提下，效率最高的排序方法是 A) 冒泡排序 B) 選擇排序 C) 快速排序 D) 歸并排序 ?希爾排序?qū)儆? A) 交換排序 B) 歸并排序 C) 選擇排序 D) 插入排序 ?對(duì)長(zhǎng)度為 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)格。 ? 若待排序的記錄已基本有序，可采用簡(jiǎn)單插入和起泡 排序。 第一趟：第 1個(gè)與第 2個(gè)比較 ， 大則交換；第 2個(gè)與第 3個(gè)比較 ， 大則交換 ， …… 關(guān)鍵字最大的記錄交換到最后一個(gè)位置上； 第二趟：對(duì)前 n1個(gè)記錄進(jìn)行同樣的操作 ， 關(guān)鍵字次大的記錄交換 到第 n1個(gè) 位置上； 依次類推 ， 則完成排序 。 第 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] 直接插入排序示例 對(duì)于有 n個(gè)數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行 n1趟 最壞情況下： 需要 n(n1)/2次比較 最好： n1次比較 第 99頁 希爾排序： 希爾排序的基本思想 : 先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行 直接插入排序 ,待整個(gè)序列中的記錄“基本有序”時(shí) ,再對(duì)全 體記錄進(jìn)行一次直接插入排序 . 最壞情況下：需要 O( )次比較 第 100頁 簡(jiǎn)單選擇排序 ? 思想：首先從 1~n個(gè)元素中選出關(guān)鍵字 最小 的記錄交換到 第一個(gè) 位置上。 2）若 x小于中間項(xiàng)的值 ,則在線性表的前半部分查找； 3）若 x大于中間項(xiàng)的值，則在線性表的后半部分查找。 ? 通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法： ? 順序查找 ? 二分查找 第 91頁 順序查找（線性查找） ◆ 查找過程： 對(duì)給定的一關(guān)鍵字 K，從線性表的一端開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和 K的比較，直到找到關(guān)鍵字等于 K的記錄或到達(dá)表的另一端。 ? 具有 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è)有下列二叉樹： 對(duì)此二叉樹前序遍歷的結(jié)果為 A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT ? 設(shè)有下列二叉樹： 對(duì)此二叉樹的中序遍歷的結(jié)果為 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA ?設(shè)樹 T的度為 4,其中度為 4的結(jié)點(diǎn)個(gè)數(shù)分別為 1。 例： A B C D E F G A ^ B ^ C ^ D ^ E ^ F ^ ^ G ^ 第 80頁 三叉鏈表： 三叉鏈表的結(jié)點(diǎn)包含四個(gè)域： 數(shù)據(jù)域、左、右、雙親指針域。 4答案： 19。 ∵ 2*i+1=1312 ∴ 其無右子結(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(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是二叉樹的根 ,無雙親 。稱左子樹和右子樹 二叉樹的 5種基本形態(tài) 第 65頁 ★ 樹與二叉樹的區(qū)別 A． 樹和二叉樹的結(jié)點(diǎn)個(gè)數(shù)最少都可為 0。（ 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)。 ? 用鏈表表示線性表的突出優(yōu)點(diǎn)是 【 1】 。 ? 數(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)算。 7. 一個(gè)隊(duì)列的初始狀態(tài)為空。 4. 下列數(shù)據(jù)結(jié)構(gòu)中 ， 屬于非線性結(jié)構(gòu)的是 A） 循環(huán)隊(duì)列 B) 帶鏈隊(duì)列 C) 二叉樹 D） 帶鏈棧 答案： D。 基本運(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)行刪除的線性表 。 ? 棧（ Stack）及其基本運(yùn)算 ? 隊(duì)列（ Queue）及其基本運(yùn)算 ? 循環(huán)隊(duì)列及其基本運(yùn)算 第 36頁 1 .棧 棧 —— 是限定僅在表尾進(jìn)行插入或刪除操作的線性表。 在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前趨。 ? 鏈?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 zhou 指針 43 13 1 null 37 7 19 25 31 頭指針 單鏈表 第 31頁 單鏈表的插入運(yùn)算 在 P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn) 單鏈表 刪除運(yùn)算 P b a x S b a P La … ai an ^ … ai1 ai+1 要求 :刪除結(jié)點(diǎn) ai。 簡(jiǎn)單的線性表 春 夏 秋 冬 復(fù)雜的線性表 記錄 1 02022001 張三 男 … 記錄 2 02022003 李四 女 … 記錄 3 記錄 4 第 24頁 線性表的順序存儲(chǔ)結(jié)構(gòu) 特點(diǎn)： 順序存儲(chǔ)結(jié)構(gòu)把 邏輯上相鄰 的數(shù)據(jù)元素存儲(chǔ)在 物理上相鄰的存儲(chǔ)單元里，順序存儲(chǔ)結(jié)構(gòu) 只存儲(chǔ)結(jié)點(diǎn)的值 ，不存儲(chǔ)結(jié)點(diǎn)間的關(guān)系，結(jié)點(diǎn)間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)