【正文】 。 第 105頁 冒泡排序的方法 ?設待排數據元素的關鍵字為（ 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 最大數 ?第二趟冒泡排序 第 106頁 Q：第二趟冒泡排序后的結果是什么樣的？達到了最終的排序目標嗎？一共需要多少次能夠最后成為有序序列？ Q：你覺得冒泡排序的效率如何？如果是你，你會用什么方法來排序？ 冒泡排序比較簡單，當初始序列基本有序時，冒泡排序有較高的效率，反之效率較低。 冒泡排序（起泡排序） 思想： 小的浮起 ， 大的沉底 。 選擇排序 簡單選擇排序、堆排序 簡單選擇排序法 , 最壞情況需要 n(n1)/2次比較； 時間復雜度為 O(n2)， 適用于 待排序元素較少 的情況。 排序過程的組成步驟： ? 首先 比較 兩個關鍵字的大??； ? 然后將記錄從一個位置 移動 到另一個位置。最壞的情況下，需要比較 log2n次。 ?前提：必須在具有順序存儲結構的 有序表中進行 。 ◆ 在平均情況下，大約要與表中一半以上元素進行比較，效率較低。 ? 若找到了滿足條件的結點，稱查找成功；否則稱查找失敗。 ?在一個容量為 15的循環(huán)隊列中，若頭指針 front=6，尾指針 rear=9，則該循環(huán)隊列中共有（ ）個元素。 中序遍歷的結果： E B A F H G C D （ 3）后序遍歷（ LRD） 右根左 若二叉樹為空，則結束遍歷操作；否則 ? 后序遍歷左子樹； ? 后序遍歷右子樹； ? 訪問根結點。 ? 二叉樹的遍歷的次序與樹型結構上的大多數運算有聯系。 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 一般二叉樹必須按完全二叉樹的形式存儲 ， 將造成存儲的浪費 。對于滿二叉樹和完全二叉樹可以按層進行順序存儲。 5答案： 32。 (07年 4月 ） 3：一棵二叉樹中共有 70個葉子結點與 80個度為 1的結點 ， 則該二叉樹中的總結點數為 （ 07年 9月 ） A） 219 B） 221 C） 229 D） 231 4： 某二叉樹中度為 2的結點有 18個 ， 則該二叉樹中有 【 】 個葉子結點 。 i=1 是樹的根 ,無雙親 。 (2)如果 2i=n,則編號 i的左子結點為 2 i，否則無左子結點，顯然也就沒有右子結點。則稱這棵二叉樹為 完全二叉樹 。 C． 樹的結點無左 、 右之分 ， 二叉樹的 結點 子樹有明確的左 、 右之分 。 ① ② ③ ④ 第 64頁 二叉樹的概念 定義： 二叉 樹是一種有序的樹形結構。 ?空樹： 無結點則稱為空樹； ? 父結點： 結點的前件稱該結點的父結點。 ? 樹的概念 ? 二叉樹的概念 ? 二叉樹的存儲 ? 二叉樹的遍歷 3. 樹與二叉樹 第 61頁 樹的概念 ? 樹的定義：是一種簡單的非線性結構。而實現遞歸調用中的存儲分配通常用 A) 棧 B) 堆 C) 數組 D) 鏈表 例題講解 ? 棧底至棧頂依次存放元素 A、 B、 C、 D，在第五個元素 E入棧前，棧中元素可以出棧，則出棧序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE ? 棧通常采用的兩種存儲結構是 A) 線性存儲結構和鏈表存儲結構 B) 散列方式和索引方式 C) 鏈表存儲結構和數組 D) 線性存儲結構和非線性存儲結構 ? 棧和隊列通常采用的存儲結構是 【 1】 。 ? 在單鏈表中，增加頭結點的目的是 A) 方便運算的實現 B) 使單鏈表至少有一個結點 C) 標識表結點中首結點的位置 D) 說明單鏈表是線性表的鏈式存儲實現 例題講解 ? 非空的循環(huán)單鏈表 head的尾結點 (由 p所指向 ) ，滿足 A) pnext==NULL B) p==NULL C) pnext=head D) p=head ? 循環(huán)鏈表的主要優(yōu)點是 A) 不再需要頭指針了 B) 從表中任一結點出發(fā)都能訪問到整個鏈表 C) 在進行插入、刪除運算時，能更好的保證鏈表不斷開 D) 已知某個結點的位置后，能夠容易的找到它的直接前件 ? 當循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。 ? 下列敘述中，錯誤的是 A) 數據的存儲結構與數據處理的效率密切相關 B) 數據的存儲結構與數據處理的效率無關 C) 數據的存儲結構在計算機中所占的空間不一定是連續(xù)的 D) 一種數據的邏輯結構可以有多種存儲結構 存儲結構 數據元素 ? 鏈表不具有的特點是 A) 不必事先估計存儲空間 B) 可隨機訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比 ? 順序存儲方法是把邏輯上相鄰的結點存儲在物理位置 【 2】 的存儲單元中。 ? 數據結構中，與所使用的計算機無關的是數據的 A) 存儲結構 B) 物理結構 C) 邏輯結構 D) 物理和存儲結構 ? 數據的邏輯結構有線性結構和 【 1】 兩大類。（ 2022年 3月） 答案： A， B， C， D， E， F， 5， 4， 3， 2， 1 第 48頁 9. 設某循環(huán)隊列的容量為 50，如果頭指針 front=45(指向隊頭元素的前一位置 )，尾指針 rear=10(指向隊尾元素 )，則該循環(huán)隊列中共有 【 2】 個元素。 6。 答案：線性結構。（ 2022年 9月） 答案：存儲結構。 a1 , a2 , a3 , a4 , ………… an1 , an 隊 列 示 意 圖 隊頭 隊尾 先進先出后進后出（ LIFO） 第 41頁 e3 e4 (c) (c) e1,e2出隊， e4入隊 隊 滿 rear =3 front e1 e2 e3 (b) rear front (b)e1,e2,e3入隊 隊列的順序存儲結構及其基本運算 3 2 1 0 (a) rear=front=1(隊空） rear front 空隊列 : 非空隊列 : 隊列元素個數 : rear=front=1 front始終指向隊頭元素前一個位置，而 rear始終指向隊尾元素的位置 rearfront 第 42頁 隊列的物理存儲結構可以用順序結構，也可以用鏈式結構。 ? 順序棧的進棧和出棧運算 ? 棧的基本運算有三種：入棧、退棧和讀棧頂元素 在順序棧中插入和刪除運算不需要移動表中其他數據元素 。 棧底 —— 表頭。各種事務處理（ 可采用順序表或單鏈表結構 ） 。 ? .高級語言中的數組； ? HEAD 3 1 5 10 a2 a3 a4 a1 提問：單向鏈表的缺點是什么？ 提示：如何尋找結點的直接前趨。 將最后一個結點的空指針改為指向頭結點 ， 從任一結點出發(fā)均可找到其它結點 。 ? 鏈式存儲結構不要求邏輯上相鄰的數據元素物理位置也相鄰，而且各數據元素的存儲順序也是任意的。 線性表的順序存儲結構稱為順序表。 常見的線性結構有： 線性表、棧、隊列、線性鏈表等 第 22|92頁 a1 a2 a5 a3 a4 HEAD 3 1 9 5 10 線性鏈表的邏輯狀態(tài) 常見的非線性結構有樹、 二叉樹、圖等 非線性結構 ： 一個數據結構不是線性結構。根據需要或在處理過程中，可以在一個數據結構中增加一個新結點（插入運算），也可以刪除某個結點（刪除運算），除此之外，對數據結構的運算還有查找、分類、合并、分解、復制和修改。 如： 一年四季 家庭成員 計算機存儲空間怎樣存放？ 存儲結構指數據結構在計算機存儲空間中的具體實現。 線性結構 樹形結構 圖形結構 ? ① 線性結構 結構中的每個元素之間存在一個對一個的關系； ? ② 樹形結構 結構中的每個元素之間存在一個對多個的關系； ? ③ 圖形結構或網狀結構 結構中的每個元素之間存在多個對多個的關系。 （ 1）數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構； （ 2）在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構； （ 3）對各種數據結構進行的運算。 一般來說，人們不會同時處理特征完全不同且互相之間沒有任何關系的各類數據元素，對于具有不同特征的數據元素總是分別進行處理。 A. 查詢方法 B. 加工方法 C. 解題方案的準確而完整的描述 D. 排序方法 (2)下列敘述中正確的是 （ 07年 4月 ） A)算法的效率只與問題的規(guī)模有關，而與數據的存儲結構無關 B)算法的時間復雜度是指執(zhí)行算法所需要的計算工作量 C)數據的邏輯結構與存儲結構是一一對應的 D)算法的時間復雜度與空間復雜度一定相關 (3)算法的有窮性是指 (08年 4月 ) A）算法程序的運行時間是有限的 B）算法程序所處理的數據量是有限的 C）算法程序的長度是有限的 D）算法只能被有限的用戶使用 (c) (B) 算法習題 : (A) 第 12頁 (4) 算法的時問復雜度是指 (2022年 3月 ) A)算法的執(zhí)行時間 B)算法所處理的數據量 C)算法程序中的語句或指令條數 D)算法在執(zhí)行過程中所需要的基本運算次數 (5) 算法的空間復雜度是指 (09年 9月 ) A）算法在執(zhí)行過程中所需要的計算機存儲空間 B）算法所處理的數據量 C）算法程序中的語句或指令條數 D）算法在執(zhí)行過程中所需要的臨時工作單元數 (6) 下列敘述中正確的是 (06年 9月 ) A）一個算法的空間復雜度大，則其時間復雜度也必定大 B）一個算法的空間復雜度大，則其時間復雜度必定小 C）一個算法的時間復雜度大，則其空間復雜度必定小 D）上述三種說法都不對 (D) 計算工作量 (A) (D) ? 算法的時間復雜度是指 A) 執(zhí)行算法程序所需要的時間 B) 算法程序的長度 C) 算法執(zhí)行過程中所需要的基本運算次數 D) 算法程序中的指令條數 ? 算法的基本特征是可行性、確定性、 【 1】 和擁有足夠的情報。 第 8頁 冒泡排序的方法： ，逐次對相鄰的兩個元素進行比較，若為逆序，則交換；第一趟掃描的結果使最大的元素排到表的最后 ； ，對剩余的元素重復上述過程，將次大的數排到表的倒數第二個位置； ； 對于長度為 n的線性表，冒泡排序需要對表掃描 n1遍。 算法不等于程序，也不等計算機方法，程序的編制不可能優(yōu)于算法的設計。通俗點說，就是計算機 解題的過程 (計算的方法 )。計算機等級考試 公共基礎知識 第 2頁 計算機二級考試公共基礎知識 大綱 ? 數據結構與算法 ? 程序設計基礎 ? 軟件工程基礎 ? 數據庫設計基礎 這四個方面在試卷中出現的情況是：選擇題 10個（ 20分），填空題 5個（ 10分），總分值占到了試卷卷面分的 30％，是一個不小的比例。 算法是程序設計的核心