【正文】 續(xù)的 B) 部分地址必須是連續(xù)的 C) 一定是不連續(xù)的 D) 連續(xù)不連續(xù)都可以 例題講解 相鄰 ? 線性表 L=(a1,a2,a3,…ai ， …an) ，下列說法正確的是 A) 每個元素都有一個直接前件和直接后件 B) 線性表中至少要有一個元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一個 且只有一個直接前件和直接后件 ? 線性表的順序存儲結構和線性表的鏈式存儲結構分別是 A) 順序存取的存儲結構、順序存取的存儲結構 B) 隨機存取的存儲結構、順序存取的存儲結構 C) 隨機存取的存儲結構、隨機存取的存儲結構 D) 任意存取的存儲結構、任意存取的存儲結構 ? 下列敘述中，錯誤的是 A) 數(shù)據(jù)的存儲結構與數(shù)據(jù)處理的效率密切相關 B) 數(shù)據(jù)的存儲結構與數(shù)據(jù)處理的效率無關 C) 數(shù)據(jù)的存儲結構在計算機中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結構可以有多種存儲結構 ?根據(jù)數(shù)據(jù)結構中各數(shù)據(jù)元素之間前后件關系的復雜程度，一般將數(shù)據(jù)結構分成 A) 動態(tài)結構和靜態(tài)結構 B) 緊湊結構和非緊湊結構 C) 線性結構和非線性結構 D) 內部結構和外部結構 ?當線性表采用順序存儲結構實現(xiàn)存儲時，其主要特點是 【 1】 。 ? 用鏈表表示線性表的突出優(yōu)點是 【 1】 。這種情況稱為 【 2】 。（ n=0） A B D F E C G H I J K M ?結點： ?根結點： 沒有前件的結點只有一個稱為根結點。可以有多個。稱左子樹和右子樹 二叉樹的 5種基本形態(tài) 第 65頁 ★ 樹與二叉樹的區(qū)別 A． 樹和二叉樹的結點個數(shù)最少都可為 0。最后一層的結點均為 0度。 第 70頁 滿二叉樹 完全二叉樹 完全二叉樹是滿二叉樹 滿二叉樹也是完全二叉樹 第 71頁 非完全二叉樹 深度為 4的完全二叉樹 第 72頁 【 性質 4】 具有 n個結點的完全二叉樹的深度為 ?log2 (n+1) ?其中， ?log2n? 的結果是不大于 log2n的最大整數(shù) 深度為 4的滿二叉樹 深度為 4的完全二叉樹 深度為 3的完全二叉樹具有 4～ 7個結點 深度為 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頁 性質 5：具有 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頁 性質 6：如果對一棵有 n個結點的完全二叉樹的結點按層 序編號，則對任一結點 i(1=i=n)有： (1)如果 i=1,則結點 i是二叉樹的根 ,無雙親 。 總之：如 i1它的雙親是 i/2取整，左子結點是 2*i，右子結點是 2*i+總數(shù)民 N，則為沒有。 ∵ 2*i+1=1312 ∴ 其無右子結點。 （ 2022年 9月 ） 樹型結構方面的考題 1答案： C。 4答案： 19。 11 A B c F E D ● ● ● ● ● ● ● ● ● 1 2 4 8 9 10 5 6 3 7 12 13 14 15 (1) 順序存儲結構 (1) 順序存儲結構 2h1= 241 = 15 用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素 。 例： A B C D E F G A ^ B ^ C ^ D ^ E ^ F ^ ^ G ^ 第 80頁 三叉鏈表： 三叉鏈表的結點包含四個域： 數(shù)據(jù)域、左、右、雙親指針域。 （ 1）先（前）序遍歷（ DLR） 根左右 若二叉樹為空，則結束遍歷操作；否則 ? 訪問根結點； ? 先序 遍歷左子樹； ? 先序 遍歷右子樹。 ? 具有 3個結點的二叉樹有 A) 2種形態(tài) B) 4種形態(tài) C) 7種形態(tài) D) 5種形態(tài) ? 設一棵二叉樹中有 3個葉子結點，有 8個度為 1的結點，則該二叉樹中總的結點數(shù)為 A) 12 B) 13 C) 14 D) 15 雙親結點 ? 設有下列二叉樹： 對此二叉樹前序遍歷的結果為 A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT ? 設有下列二叉樹： 對此二叉樹的中序遍歷的結果為 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA ?設樹 T的度為 4,其中度為 4的結點個數(shù)分別為 1。 350 3 DEBFCA 第 90頁 ⒌ 查找技術 查找是數(shù)據(jù)處理的重要內容。 ? 通常根據(jù)不同的數(shù)據(jù)結構，采用不同的查找方法： ? 順序查找 ? 二分查找 第 91頁 順序查找（線性查找） ◆ 查找過程： 對給定的一關鍵字 K，從線性表的一端開始，逐個進行記錄的關鍵字和 K的比較，直到找到關鍵字等于 K的記錄或到達表的另一端。 最好情況： 1 最壞情況： n ◆ 在下面兩種情況下只能采取順序查找： a. 線性表為無序表（元素排列是無序的）； b. 即使是有序線性表，但采用的是鏈式存儲結構。 2）若 x小于中間項的值 ,則在線性表的前半部分查找； 3）若 x大于中間項的值，則在線性表的后半部分查找。 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頁 ? 練習 假設待查有序（升序）順序表中數(shù)據(jù)元素的關鍵字序列為（ 8,18,27,42,47,50,56, 68,95,120），用折半查找方法查找關鍵字值為 27的數(shù)據(jù)元素 . 對于長度為 n的有序線性表，最壞情況只需比較 log2n次。 第 98頁 該算法適合于 n 較小的情況 ， 時間復雜度為 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個數(shù)據(jù)元素的待排序列，插入操作要進行 n1趟 最壞情況下： 需要 n(n1)/2次比較 最好： n1次比較 第 99頁 希爾排序： 希爾排序的基本思想 : 先將整個待排記錄序列分割成為若干子序列分別進行 直接插入排序 ,待整個序列中的記錄“基本有序”時 ,再對全 體記錄進行一次直接插入排序 . 最壞情況下：需要 O( )次比較 第 100頁 簡單選擇排序 ? 思想：首先從 1~n個元素中選出關鍵字 最小 的記錄交換到 第一個 位置上。 89 76 24 33 15 10 11 25 36 49 78 56 (a):堆頂元素取最大值 (b):堆頂元素取最小值 堆排序需要比較的次數(shù)為 O(nlog2n) (1) 堆的示例 第 103頁 交 換 排 序 交換排序的特點在于 交換 。 第一趟：第 1個與第 2個比較 ， 大則交換；第 2個與第 3個比較 ， 大則交換 ， …… 關鍵字最大的記錄交換到最后一個位置上； 第二趟：對前 n1個記錄進行同樣的操作 ， 關鍵字次大的記錄交換 到第 n1個 位置上； 依次類推 ， 則完成排序 。 時間復雜度： O(log2n) 當待排序列逆序時 ， 蛻變成冒泡排序 ， 時間復雜度 : O(n(n1)/2) 第 109頁 內部排序方法的選擇 各種排序方法各有優(yōu)缺點，故在不同情況下可作不同的選擇。 ? 若待排序的記錄已基本有序，可采用簡單插入和起泡 排序。 ?長度為 n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為 【 1】 。 0 nlog2n交換排序 第 115頁 ?在下列幾種排序方法中，要求內存量最大的是 A) 插入排序 B) 選擇排序 C) 快速排序 D) 歸并排序 ?在待排序的元素序列基本有序的前提下，效率最高的排序方法是 A) 冒泡排序 B) 選擇排序 C) 快速排序 D) 歸并排序 ?希爾排序屬于 A) 交換排序 B) 歸并排序 C) 選擇排序 D) 插入排序 ?對長度為 n的線性表進行順序查找，在最壞的情況下所需要的比較次數(shù)為 Ａ ) n+1 B) n C) (n+1)/2 D) n/2 第 116頁 第 117頁 第二章 程序設計基礎 內容： 1. 程序設計方法與風格。 2. 數(shù)據(jù)說明 ? 數(shù)據(jù)說明的次序應該規(guī)范化 ? 變量安排有序化 ? 對復雜數(shù)據(jù)結構應注釋說明 3. 語句的結構 ? 每條語句簡單明了 ? 盡量不用或少用 GOTO語。 3. 面向對象的程序設計方法，對象，方法，屬性及繼承與多態(tài)性。 ?在最壞情況下，堆排序需要比較的次數(shù)為 【 2】 。（ 06年 9月 ） A） 63 B） 64 C） 6 D） 7 (3) 下列數(shù)據(jù)結構中 ， 能用二分法進行查找的是 （ 2022年 9月 ） A） 順序存儲的有序線性表 B） 線性鏈表 C） 二叉鏈表 D） 有序線性鏈表 (4) 下列排序方法中 ， 最壞情況下比較次數(shù)最少的是 （ 09年 3月 ） A） 冒泡排序 B） 簡單選擇排序 C） 直接插入排序 D） 堆排序 D B A D 第 113頁 ?在長度為 n的有序線性表中進行二分查找。 ? 若待排序的記錄個數(shù) n較小時，可采用簡單排序方法