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