筆試數(shù)據(jù)結(jié)構(gòu)與算法

1、第1章基本數(shù)據(jù)結(jié)構(gòu)與算法,主講：曾慶尚煙臺(tái)大學(xué)文經(jīng)學(xué)院電子系,,,二級(jí)ACCESS—數(shù)據(jù)庫(kù)基礎(chǔ)知識(shí),本章的重要性,2007年4月-2010年9月共8次計(jì)算機(jī)等級(jí)考試涉及到本章內(nèi)容的題目有40題，平均每次接近10分，因此本章還是很重要的。本章在考試中只涉及筆試題目，上機(jī)不考。,,,二級(jí)ACCESS—數(shù)據(jù)訪問(wèn)頁(yè),關(guān)鍵考點(diǎn),順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的基本概念 棧、隊(duì)列的基本概念與基本操作 循環(huán)隊(duì)列元素個(gè)數(shù)的計(jì)算 算法時(shí)間、空間復(fù)雜度

2、的概念幾種查找與排序的比較次數(shù)二叉樹(shù)的遍歷二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)的計(jì)算,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,本章主要內(nèi)容,算法 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 基本概念和術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)類型 線性結(jié)構(gòu)和非線性結(jié)構(gòu) 順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ) 線性表 棧和隊(duì)列 線性鏈表 樹(shù)與二叉樹(shù) 查找和排序 圖,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.1 算法,算法的基本概念 算法：解題方案的準(zhǔn)確而完整的描述。 算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則

3、，每一個(gè)規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法不等于程序，程序不可能優(yōu)于算法。 基本特性 可行性：根據(jù)實(shí)際問(wèn)題設(shè)計(jì)的算法，執(zhí)行得到滿意結(jié)果 確定性：每一步驟必須有明確定義，不允許有多義性。 有窮性：算法必須能在有限的時(shí)間內(nèi)做完。 擁有足夠的情報(bào)：輸入和輸出，方可執(zhí)行。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.1 算法,算法的基本要素 1.算法中對(duì)數(shù)據(jù)的運(yùn)算和操作 算術(shù)運(yùn)算：＋、－、×、÷等 邏

4、輯運(yùn)算：>、=、<=、!=等 關(guān)系運(yùn)算：and、or、not等 數(shù)據(jù)傳輸：w、r等 2.算法的控制結(jié)構(gòu) 算法中各操作之間的執(zhí)行順序 描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語(yǔ)言等 算法可以用順序、選擇、循環(huán)三種基本機(jī)構(gòu)組合而成。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.1 算法,算法設(shè)計(jì)基本方法 （1）列舉法：根據(jù)問(wèn)題，列舉所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰?，哪些是不需要的?（2）

5、歸納法：通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。 （3）遞推：是指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。 （4）遞歸：將問(wèn)題逐層分解的過(guò)程。 （5）減半遞推技術(shù)： “減半”，是指將問(wèn)題規(guī)模減半，而問(wèn)題性質(zhì)不變； “遞推”，是指重復(fù)“減半”過(guò)程。 （6）回溯法：分析問(wèn)題，找出一個(gè)解決總線索，然后沿著這個(gè)線索逐步試探。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.1 算法,算法的復(fù)雜度：時(shí)間復(fù)雜度、空間復(fù)雜度 （

6、P5）算法的時(shí)間復(fù)雜度 算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。 工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)，即 算法的工作量=f(n) 算法空間復(fù)雜度 算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。 存儲(chǔ)空間包括：①算法程序所占的空間、 ②輸入數(shù)據(jù)所占的空間、③算法執(zhí)行過(guò)程中所需要的額外空間。。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,3.2.1 數(shù)據(jù)結(jié)構(gòu)研究的

7、主要內(nèi)容,當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn) 所處理的數(shù)據(jù)量大且具有一定的關(guān)系； 對(duì)其操作不再是單純的數(shù)值計(jì)算，而更多地是需要對(duì)其進(jìn)行組織、管理和檢索。 應(yīng)用舉例1——學(xué)籍檔案管理 假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,特點(diǎn) 每個(gè)學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號(hào)順序依次排列構(gòu)成一張表格； 表中每個(gè)學(xué)生的信息依據(jù)學(xué)號(hào)的大小存在著一種前后關(guān)系. 對(duì)它的操作通常是插入某個(gè)學(xué)生的信息，刪除某個(gè)

8、學(xué)生的信息，更新某個(gè)學(xué)生的信息，按條件檢索某個(gè)學(xué)生的信息等等。,數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,應(yīng)用舉例2—制定教學(xué)計(jì)劃 在制定教學(xué)計(jì)劃時(shí)，需要考慮各門課程的開(kāi)設(shè)順序。有些課程需要先導(dǎo)課程，有些則不需要;而有些課程又是其他課程的先導(dǎo)課程。比如，計(jì)算機(jī)專業(yè)課程的開(kāi)設(shè)情況如下表所示：,數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容,特點(diǎn) 課程的先后關(guān)系用圖結(jié)構(gòu)描述； 通過(guò)實(shí)施創(chuàng)建圖結(jié)構(gòu)，

9、按要求將圖結(jié)構(gòu)中的頂點(diǎn)進(jìn)行線性排序。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)主要研究以下三個(gè)方面的問(wèn)題(P7) 數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)集合中各元素的信息，及元素之間所固有的邏輯關(guān)系（前后件關(guān)系） 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系 對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算 主要目的是為了提高數(shù)據(jù)的效率。所謂提高數(shù)據(jù)處理的效率，主要包括兩個(gè)方面：一是提高數(shù)據(jù)處理的速度，二是盡量節(jié)省在數(shù)據(jù)處理過(guò)程中所占用的計(jì)算機(jī)存儲(chǔ)空間。,數(shù)據(jù)結(jié)構(gòu)研究

10、的主要內(nèi)容,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。是相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,能輸入到計(jì)算機(jī)中 并能被計(jì)算機(jī)程序處理的 符號(hào)的集合。,整數(shù)(1,2)、實(shí)數(shù)(1.1,1.2) 字符串(Beijing)、 圖形、聲音。,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,計(jì)算

11、機(jī)管理圖書(shū)問(wèn)題 圖書(shū)館里有各種卡片：有按書(shū)名編排的、有按作者編排的、有按分類編排。 如何將查詢圖書(shū)的這些信息存入計(jì)算機(jī)中既要考慮查詢時(shí)間短，又要考慮節(jié)省空間,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,最簡(jiǎn)單的辦法之一是建立一張表，每一本書(shū)的信息在表中占一行，如,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的

12、學(xué)科。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,如何將0,1,2,3,4,5,6,7,8,9這10個(gè)數(shù)存放在 計(jì)算機(jī)中能最快地達(dá)到你所需要的目的？ 目的不同，最佳的存儲(chǔ)方方法就不同。 從大到小排列：9,8,7,6,5,4,3,2,1,0 輸出偶數(shù)：0,2,4,6,8,1,3,5,7,9,數(shù)據(jù)元素在 計(jì)算機(jī)中的表示,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。,1.2 數(shù)據(jù)結(jié)構(gòu)

13、的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,對(duì)數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行操作處理 (插入、刪除、修改、查找、排序),數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)元素(Data Element) 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體。 有時(shí)一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)(Data Item)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。,數(shù)據(jù)元素亦稱節(jié)點(diǎn)或記錄。,1.2 數(shù)

14、據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,有限個(gè)數(shù)據(jù)元素的集合,有限個(gè)節(jié)點(diǎn)間關(guān)系的集合,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,,1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,,,,,A．線性結(jié)構(gòu),B．非線性結(jié)構(gòu),A 順序存儲(chǔ),B 鏈?zhǔn)酱鎯?chǔ),線性表,棧,隊(duì),樹(shù)形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面,數(shù)據(jù)結(jié)構(gòu)類型,,,基本數(shù)據(jù)結(jié)

15、構(gòu)與算法,線性結(jié)構(gòu)和非線性結(jié)構(gòu),線性結(jié)構(gòu)條件 （1）有且只有一個(gè)根結(jié)點(diǎn)； （2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 （3）首節(jié)點(diǎn)無(wú)前件，尾節(jié)點(diǎn)無(wú)后件。 非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu) 注意：在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)節(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)；否則，不能稱為線性結(jié)構(gòu)。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,線性結(jié)構(gòu)和非線性結(jié)構(gòu),樹(shù)形結(jié)構(gòu),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,樹(shù)形結(jié)構(gòu) —結(jié)點(diǎn)間具有分層次的連接關(guān)系,線性結(jié)構(gòu)和非線性

16、結(jié)構(gòu),樹(shù)形結(jié)構(gòu),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,線性結(jié)構(gòu)和非線性結(jié)構(gòu),圖形結(jié)構(gòu)：節(jié)點(diǎn)間的連接任意,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ),順序存儲(chǔ) 常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里。 三個(gè)弱點(diǎn) 插入或刪除操作時(shí)，需移動(dòng)大量元數(shù)。 長(zhǎng)度變化較大時(shí)，需按最大空間分配。 表的容量難以擴(kuò)充,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,每個(gè)節(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。 數(shù)據(jù)域：存放元素本身的數(shù)據(jù)， 指針域：存放

17、指針，體現(xiàn)數(shù)據(jù)元素之間的邏輯聯(lián)系,順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ),鏈接存儲(chǔ)結(jié)構(gòu)特點(diǎn) 比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小 (每個(gè)節(jié)點(diǎn)都由數(shù)據(jù)域和指針愈組成)。 邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。 插入、刪除靈活(不必移動(dòng)節(jié)點(diǎn)，僅改變節(jié)點(diǎn)中的指針)。,鏈接存儲(chǔ)結(jié)構(gòu),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ),鏈?zhǔn)酱鎯?chǔ)的地址映射表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.3 線性表,線性表的基本概念 （P15） 線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決

18、于自己的序號(hào)，元素之間的相對(duì)位置是線性的。 非空線性表的結(jié)構(gòu)特征 有且只有一個(gè)根結(jié)點(diǎn)a1，它無(wú)前件；有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件； 除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。結(jié)點(diǎn)個(gè)數(shù)n稱為線性表的長(zhǎng)度，當(dāng)n=0時(shí)，稱為空表。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,在線性表上常用的運(yùn)算有 初始化、求長(zhǎng)度、取元素、修改、插入、刪除、檢索、排序。 線性表的插入操作 （P17） 在線性表L中第i個(gè)數(shù)據(jù)元素之

19、前插入數(shù)據(jù)元素e 檢查插入要求的有關(guān)參數(shù)的合理性 把原來(lái)第n個(gè)數(shù)據(jù)元素至第i個(gè)元素（共n-i+1)依次后移一個(gè)數(shù)組元素的位置。 把新數(shù)據(jù)元素放在第i個(gè)位置上 修正線性表的數(shù)據(jù)元素個(gè)數(shù)。 線性表中含有n個(gè)數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定在n+1個(gè)位置上插入元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：n/2,1.3 線性表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,線性表的插入操作（時(shí)間復(fù)雜度O(n)）,1.3 線性表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,線性

20、表的刪除操作（時(shí)間復(fù)雜度O(n)）（P18）,1.3 線性表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.4 棧和隊(duì)列（P19）,棧和隊(duì)列是兩種運(yùn)算時(shí)要受到某些特殊限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。 棧：限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表,此種結(jié)構(gòu)稱為后進(jìn)先出。 設(shè)棧s=（a1，a2，…,ai，…，an） 其中a1是棧底元素， an是棧頂元素。 棧頂（top)：允許插入和刪除的一端； 約定top始終指向新數(shù)據(jù)元素將存放

21、的位置。 棧底（bottom):不允許插入和刪除的一端。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,隊(duì)列的主要運(yùn)算 設(shè)置一個(gè)空隊(duì)列； 插入一個(gè)新的隊(duì)尾（rear）元素，稱為進(jìn)隊(duì)； 刪除隊(duì)頭（front）元素，稱為出隊(duì)； 讀取隊(duì)頭元素；,,,a1 , a2 , a3 , a4 , ………… an-1 , an,,,,,隊(duì)頭,隊(duì)尾,1.4 棧和隊(duì)列,隊(duì)列：限

22、定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）表。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,1.4 棧和隊(duì)列,隊(duì)列的主要運(yùn)算 隊(duì)空時(shí)，令rear=front=0; 元素個(gè)數(shù)＝rear-front 當(dāng)有新元素入隊(duì)時(shí)，尾指針加1，當(dāng)有元素出隊(duì)時(shí)，頭指針加1。故在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素前一個(gè)位置，而尾指針始終指向隊(duì)尾元素的位置,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,循環(huán)隊(duì)列元素個(gè)數(shù)=(rear-front+n

23、) mod n,,,a1 , a2 , a3 , a4 , ………… an-1 , an,,,,,隊(duì)頭,隊(duì)尾,1.4 棧和隊(duì)列,循環(huán)隊(duì)列：首尾相接的隊(duì)列，邏輯上形成一個(gè)環(huán)狀。,,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.5 線性鏈表（P24）,線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn) 簡(jiǎn)單、方便，要求數(shù)據(jù)元素依次存放在連續(xù)的存儲(chǔ)單元中，從而利用數(shù)據(jù)元素的存

24、儲(chǔ)順序表示相應(yīng)的邏輯順序，這種存儲(chǔ)方式屬于靜態(tài)存儲(chǔ)形式。 暴露的問(wèn)題 在做插入或刪除元素的操作時(shí)，會(huì)產(chǎn)生大量的數(shù)據(jù)元素移動(dòng)； 對(duì)于長(zhǎng)度變化較大的線性表，要一次性地分配足夠的存儲(chǔ)空間，但這些空間常常又得不到充分的利用； 線性表的容量難以擴(kuò)充。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,將線性表的元素放到一個(gè)具有頭指針的鏈表中，鏈表中每個(gè)結(jié)點(diǎn)包含數(shù)據(jù)域和指針域。   數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結(jié)點(diǎn)的地址，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭铡?/p>

25、邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存中的物理存儲(chǔ)空間不一定相鄰。 線性鏈表分為：?jiǎn)捂湵?、雙鏈表、循環(huán)鏈表,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,單鏈表：每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由該指針只能找到其后件結(jié)點(diǎn)。,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.5 線性鏈表,線性鏈表的計(jì)算 在指定節(jié)點(diǎn)前插入一個(gè)元素(不必移動(dòng)節(jié)點(diǎn)，僅改變節(jié)點(diǎn)中的指針，且不會(huì)出現(xiàn)“上溢”現(xiàn)象) 刪除指定節(jié)點(diǎn)(不必移動(dòng)節(jié)點(diǎn)，僅改變節(jié)點(diǎn)中的指針) 合并兩

26、個(gè)線性鏈表 逆轉(zhuǎn)線性鏈表 復(fù)制線性鏈表 線性鏈表排序 線性鏈表查找,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,,P,P,,,,單鏈表的插入運(yùn)算：在節(jié)點(diǎn)a之后插入一新節(jié)點(diǎn),,S,,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,L,,,,,,,p,,,,,,,,單鏈表的刪除運(yùn)算：刪除節(jié)點(diǎn)ai,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,循環(huán)鏈表: 首尾相接的鏈表 （P30） 循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針?lè)强?，而是指向頭結(jié)點(diǎn)，使鏈表

27、構(gòu)成環(huán)狀。 特點(diǎn)： 2、增加了頭結(jié)點(diǎn)，使得任何時(shí)候循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)。 1、從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率。,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,雙向鏈表：在每個(gè)結(jié)點(diǎn)中設(shè)置兩個(gè)指針，一個(gè)指向后繼，一個(gè)指向前驅(qū)?？芍苯哟_定一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)?？商岣咝?。,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.5 線性鏈表,線性鏈表的特點(diǎn) 插入、刪除節(jié)點(diǎn)方便(不必移動(dòng)節(jié)點(diǎn)，僅改變節(jié)

28、點(diǎn)中的指針) 只能順序存?。ú檎抑荒軓念^指針開(kāi)始），不能隨即存取。 適應(yīng)于數(shù)據(jù)的動(dòng)態(tài)變化,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,樹(shù)的定義：由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合。僅有一個(gè)根結(jié)點(diǎn)，結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系。,,,,現(xiàn)實(shí)世界中，能用樹(shù)的結(jié)構(gòu)表示：學(xué)校的行政關(guān)系、書(shū)的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。,1.6 樹(shù)與二叉樹(shù),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,樹(shù)的基本概念： 結(jié)點(diǎn)（Node）：樹(shù)中的元素 結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。

29、結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開(kāi)始算起，根為第一層。 葉子（Leaf）：度為零的結(jié)點(diǎn)，也稱端結(jié)點(diǎn)。 孩子（Child）：結(jié)點(diǎn)子樹(shù)的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。 兄弟（Sibling）：同一雙親的孩子。 雙親（Parent）：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)，稱為其的雙親。 深度（Depth)： 樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。 森林（Forest）：M棵互不相交的樹(shù)的集合。,1.6 樹(shù)與二叉樹(shù)（P31）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,二叉樹(shù)（Binary Tree

30、）的定義(P34),二叉樹(shù)的五種基本形態(tài),因?yàn)闃?shù)的每個(gè)結(jié)點(diǎn)的度不同，存儲(chǔ)困難，使對(duì)樹(shù)的處理算法很復(fù)雜。所以引出二叉樹(shù)的理論。,1.6 樹(shù)與二叉樹(shù),二叉樹(shù)一種特殊的樹(shù)型結(jié)構(gòu)，特點(diǎn)是樹(shù)中每個(gè)結(jié)點(diǎn)只有兩棵子樹(shù)，且子樹(shù)有左右之分，次序不能顛倒。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,滿二叉樹(shù) （P35）,特點(diǎn)：所有分支結(jié)點(diǎn)都存在左右子樹(shù)，且所有葉子結(jié)點(diǎn)都在同一層上。,1.6 樹(shù)與二叉樹(shù),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,完全二叉樹(shù) （P35）,特點(diǎn)：除最后一層外，

31、每一層都取最大結(jié)點(diǎn)數(shù)，最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置。,1.6 樹(shù)與二叉樹(shù),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,A、二叉樹(shù)的第i層上至多有2k-1（k ?1）個(gè)結(jié)點(diǎn)。 B、深度為h的二叉樹(shù)中至多含有2m-1個(gè)結(jié)點(diǎn)。 C、若在任意一棵二叉樹(shù)中，有n0個(gè)葉子結(jié)點(diǎn)（度為0），有n2個(gè)度為2的結(jié)點(diǎn)，則：n0=n2+1 D、具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1，其中 [log2n]表示log2n 的整數(shù)部分。,二叉樹(shù)的基本性質(zhì)

32、（P34）,1.6 樹(shù)與二叉樹(shù),第三層 (i=3)，有23-1=4個(gè)節(jié)點(diǎn) 深度h=4，共有24-1=15個(gè)節(jié)點(diǎn) n0=8,n2=7,n0=n2+1 15個(gè)節(jié)點(diǎn)，深度=[log215]+1=4,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,E、設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)，如從根結(jié)點(diǎn)開(kāi)始，按層序（每一層從左到右）用自然數(shù)1,2,…,n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k（k=1,2,…,n）的結(jié)點(diǎn)有以下結(jié)論： ①若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；若k&

33、gt;1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為INT(k/2)。 ②若2k≤n，則結(jié)點(diǎn)k的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（顯然也沒(méi)有右子結(jié)點(diǎn)）。 ③若2k+1≤n，則結(jié)點(diǎn)k的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。,二叉樹(shù)的基本性質(zhì),1.6 樹(shù)與二叉樹(shù),例如結(jié)點(diǎn)6，其父結(jié)點(diǎn)為3，左子結(jié)點(diǎn)為12，左子結(jié)點(diǎn)為13,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.6 樹(shù)與二叉樹(shù),二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) (P36)順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)

34、構(gòu) （不需掌握）用一組連續(xù)的存儲(chǔ)單元存放二叉樹(shù)的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。 用數(shù)組存儲(chǔ)時(shí)，若父結(jié)點(diǎn)在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。 順序存儲(chǔ)二叉樹(shù)必須按完全二叉樹(shù)的形式存儲(chǔ)，將造成存儲(chǔ)的浪費(fèi)。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)（不需掌握）,,,T[16],2h-1=,24-1 = 15,1.6 樹(shù)與二叉樹(shù),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.6 樹(shù)與二叉樹(shù),二叉樹(shù)鏈?zhǔn)?/p>

35、存儲(chǔ)結(jié)構(gòu)（不需掌握） 在順序存儲(chǔ)結(jié)構(gòu)中，對(duì)于非完全二叉樹(shù)，需要將空缺的位置用特定的符號(hào)填補(bǔ)，若空缺結(jié)點(diǎn)較多，勢(shì)必造成空間利用率的下降。在這種情況下，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。常見(jiàn)的二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)如下所示：,A,B,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.6 樹(shù)與二叉樹(shù),二叉樹(shù)的鏈接存儲(chǔ)結(jié)構(gòu)（不需掌握）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,二叉樹(shù)的遍歷（P38） 遍歷是指按某條搜索路線尋訪樹(shù)中每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。 按

36、先左后右的原則，一般使用三種遍歷： 前序遍歷(D L R): 訪問(wèn)根結(jié)點(diǎn)，按先序遍歷左子樹(shù)，按先序遍歷右子樹(shù)。 中序遍歷(L D R): 按中序遍歷左子樹(shù)，訪問(wèn)根結(jié)點(diǎn)，按中序遍歷右子樹(shù)。 后序遍歷(L R D): 按后序遍歷左子樹(shù)，按后序遍歷右子樹(shù)，訪問(wèn)根結(jié)點(diǎn)。 二叉樹(shù)為空時(shí)，執(zhí)行空操作，即空二叉樹(shù)已遍歷完。,1.6 樹(shù)與二叉樹(shù),,,基本數(shù)據(jù)結(jié)構(gòu)與

37、算法,遍歷算法,先序遍歷：D L R 中序遍歷：L D R 后序遍歷：L R D,A,,,,D,B,,C,,,,T1,T2,T3,D L R,以先序遍歷D L R為例演示遍歷過(guò)程,ABDC,BDAC,DBCA,1.6 樹(shù)與二叉樹(shù),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,查找：在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件找到滿足條件的結(jié)點(diǎn)。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。 平

38、均查找長(zhǎng)度：查找過(guò)程中比較的次數(shù) 查找的結(jié)果 查找成功：找到滿足條件的結(jié)點(diǎn) 查找失敗：找不到滿足條件的結(jié)點(diǎn)。,1.7 查找技術(shù)（P39）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,順序查找（線性查找） 對(duì)給定的一關(guān)鍵字K，從線性表的一端開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端。 可以采用從前向后查，也可采用從后向前查的方法。 在平均情況下，大約要與表中一半以上元素進(jìn)行比較，效率較低。平均查找長(zhǎng)

39、度=(n+1)/2。 時(shí)間復(fù)雜度＝O(n) 在下面兩種情況下只能采取順序查找： 線性表為無(wú)序表（元素排列是無(wú)序的）； 即使是有序線性表，但采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,1.7 查找技術(shù)（P39）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,折半查找（二分法查找）,思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。 前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。 分三種情況： 若中間項(xiàng)的值等于x,則說(shuō)明已查到。 若

40、x小于中間項(xiàng)的值，則在線性表的前半部分查找； 若x大于中間項(xiàng)的值，則在線性表的后半部分查找。 特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較 log2n次。,1.7 查找技術(shù)（P39）,折半查找（二分法查找）算法,假設(shè)查找表存放在數(shù)組a的a[1]～a[n]中，且升序，查找關(guān)鍵字值為k。折半查找的主要步驟為： （1）置初始查找范圍：low=1，high=n; （2）求查找范圍中間項(xiàng)：mid=(low+high)/2 （3

41、）將指定的關(guān)鍵字值k與中間項(xiàng)a[mid].key比較。 若相等，查找成功，找到的數(shù)據(jù)元素為此時(shí)mid 指向的位置； 若小于，查找范圍的低端數(shù)據(jù)元素指針low不變，高端數(shù)據(jù)元素指針high更新為mid-1; 若大于，查找范圍的高端數(shù)據(jù)元素指針high不變，低端數(shù)據(jù)元素指針low更新為mid+1; （4）重復(fù)步驟（2）、（3）直到查找成功或查找范圍空（low>high），即查找失敗為止。 （5）

42、如果查找成功，返回找到元素的存放位置，即當(dāng)前的中間項(xiàng)位置指針mid；否則返回查找失敗標(biāo)志。,查找23和79的過(guò)程如下圖：9元素,mid=(low+high)/2不進(jìn)位取整,( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37

43、, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55,

44、 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79,

45、 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,排序的功能：將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排成一個(gè)按關(guān)鍵字有序的序列。 排序過(guò)程的組成步驟 1、首先比較兩個(gè)關(guān)鍵字的大??； 2、然后將記錄從一個(gè)位置移動(dòng)到

46、另一個(gè)位置。,1.8 排序技術(shù)（P40）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,交換排序的特點(diǎn)在于交換，有冒泡和快速排序兩種。 冒泡排序（起泡排序） 思想：小的浮起，大的沉底。從左端開(kāi)始比較。 第一趟：第1個(gè)與第2個(gè)比較，大則交換；第2個(gè)與第3個(gè)比較，大則交換，…關(guān)鍵字最大的記錄交換到最后一個(gè)位置上； 第二趟：對(duì)前n-1個(gè)記錄進(jìn)行同樣的操作，關(guān)鍵字次大的記錄交換到第n-1個(gè)位置上； 依次類推，則完成排序。

47、 正序：時(shí)間復(fù)雜度為O(n) 逆序：時(shí)間復(fù)雜度為O(n2) 排序n個(gè)記錄的文件最多需要n-1趟冒泡排序。,1.8.1 交換類排序法（P40）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,第 六 趟 排 序 后,第 五 趟 排 序 后,第 四 趟 排 序 后,第 三 趟 排 序 后,第 二 趟 排 序 后,第 一 趟 排 序 后,初 始 關(guān) 鍵 字,,,,,1.8.1 交換類

48、排序法—示例,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,該算法適合于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 第四次排序：

49、 [15 27 36 53 69] 42 第五次排序： [15 27 36 42 53 69] 直接插入排序示例,對(duì)于有n個(gè)數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行n-1次,,1.8.2 直接插入排序（P42）,從數(shù)組的第2號(hào)元素開(kāi)始，順序取出后續(xù)元素，并將該元素插入到其左端已排好序數(shù)組的適當(dāng)位置。需比較n(n-1)/2次,,,基本數(shù)據(jù)

50、結(jié)構(gòu)與算法,例：有6個(gè)記錄，前5 個(gè)已排序的基礎(chǔ)上，對(duì)第6個(gè)記錄排序。 [ 15 27 36 53 69 ] 42 ? low ?mid ? high [ 15 27 36 53 69 ] 42 ?low ? hi

51、gh ?mid [ 15 27 36 53 69 ] 42 ?high ?low [ 15 27 36 42 53 69 ]

52、,,(high<low ，查找結(jié)束，插入位置為low 或high+1 ),( 42>36 ),( 42<53 ),折半插入排序,折半插入排序在尋找插入位置時(shí)，不是逐個(gè)比較而是利用折半查找的原理尋找插入位置 。待排序元素越多，改進(jìn)效果越明顯。,思想：首先從1～n個(gè)元素中選出關(guān)鍵字最小的記錄交換到第一個(gè)位置上。然后再?gòu)牡? 個(gè)到第n個(gè)元素中選出次小的記錄交換到第二個(gè)位置上，依次類推。 時(shí)間復(fù)雜度為O(n2)，最壞情況下

53、需要比較 n(n-1)/2次 適用于待排序元素較少的情況。,1.8.3 簡(jiǎn)單選擇排序（P44）,初態(tài),8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,1 3

54、 9 8 6,1 3 9 8 6,1 3 9 8 6,,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,各種排序法比較,,,二級(jí)ACCESS—查詢,過(guò)關(guān)練習(xí),,【2010.9】(1) 下列敘述中正確的是【 】A) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的B) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的

55、存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)C) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu) D) 上述三種說(shuō)法都不對(duì)【2010.9】(2)下列敘述中正確的是【 】A）在棧中，棧中元素隨棧底指針與棧頂指針的變化而動(dòng)態(tài)變化B）在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動(dòng)態(tài)變化C）在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化 D）上述三種說(shuō)法都不對(duì),√,√

56、,,,二級(jí)ACCESS—查詢,過(guò)關(guān)練習(xí),,【2010.9】(3)一個(gè)棧的初始狀態(tài)為空。首先將元素5,4,3,2,1依次入棧，然后退棧一次，再將元素A,B,C,D依次入棧，之后將所有元素全部退棧，則所有元素退棧（包括中間退棧的元素)的順序?yàn)椤?】?！?【2010.9】(4)在長(zhǎng)度為n的線性表中，尋找最大項(xiàng)至少需要比較【 】次?！?010.9】(5)一棵二叉樹(shù)

57、有10個(gè)度為1的結(jié)點(diǎn)，7個(gè)度為2的結(jié)點(diǎn)，則該二義樹(shù)共有【 】個(gè)結(jié)點(diǎn)。,1DCBA2345,1,25,,,二級(jí)ACCESS—查詢,過(guò)關(guān)練習(xí),,【2010.3】(6)下列敘述中正確的是【 】　　A)對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行查找，最壞情況下需要的比較次數(shù)為n　　B)對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(n/2)　　C)對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(lo

58、g2n)　　D)對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(n log2n)【2010.3】(7)算法的時(shí)間復(fù)雜度是指【 】　　A)算法的執(zhí)行時(shí)間　　B)算法所處理的數(shù)據(jù)量　　C)算法程序中的語(yǔ)句或指令條數(shù)　　D)算法在執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù),√,√,,,二級(jí)ACCESS—查詢,過(guò)關(guān)練習(xí),,【2010.3】(8)一個(gè)隊(duì)列的初始狀態(tài)為空。現(xiàn)將元素A,B,C,D,E,F,5,4,3,2,1依次入

59、隊(duì)，然后再依次退隊(duì)，則元素退隊(duì)的順序?yàn)椤?】?！?010.3】(9)設(shè)某循環(huán)隊(duì)列的容量為50，如果頭指針front=45(指向隊(duì)頭元素的前一位置)，尾指針rear=10(指向隊(duì)尾元素)，則該循環(huán)隊(duì)列中共有【 】 個(gè)元素。【2010.3】(10)設(shè)二叉樹(shù)如下：對(duì)該二叉樹(shù)進(jìn)行后序遍歷的結(jié)果為【

60、 】 。,A,B,C,D,E,F,5,4,3,2,1,15,EDBGHFCA,,,二級(jí)ACCESS—查詢,過(guò)關(guān)練習(xí),,【2009.9】(11) 下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是【 】 A）循環(huán)隊(duì)列　　 B）帶鏈隊(duì)列　　 C）二叉樹(shù)　　 D）帶鏈?！?009.9】(12)下列數(shù)據(jù)結(jié)果中，能夠按照“先進(jìn)后出”原則存取數(shù)據(jù)的是【 】A）循環(huán)隊(duì)列　　B）?！　）隊(duì)列

61、　　D）二叉樹(shù)【2009.9】(13) 對(duì)于循環(huán)隊(duì)列，下列敘述中正確的是【 】Ａ）隊(duì)頭指針是固定不變的 Ｂ）隊(duì)頭指針一定大于隊(duì)尾指針Ｃ）隊(duì)頭指針一定小于隊(duì)尾指針Ｄ）隊(duì)頭指針可以大于隊(duì)尾指針，也可以小于隊(duì)尾指針,√,√,√,,,二級(jí)ACCESS—查詢,過(guò)關(guān)練習(xí),,【2009.9】（14）算法的空間復(fù)雜度是指【 】 Ａ）算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間　?。拢┧惴ㄋ幚淼臄?shù)據(jù)量　?。茫┧惴ǔ?/p>

62、序中的語(yǔ)句或指令條數(shù)　?。模┧惴ㄔ趫?zhí)行過(guò)程中所需要的臨時(shí)工作單元數(shù)【2009.9】（15）某二叉樹(shù)由5個(gè)度為2的結(jié)點(diǎn)以及3個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中共有 【 】 個(gè)結(jié)點(diǎn)。,14,√,,,二級(jí)ACCESS—查詢,過(guò)關(guān)練習(xí),,【2009.3】(16)下面敘述中正確的是【 】 A）棧是“先進(jìn)先出”的線性表 B）隊(duì)列是“先進(jìn)后出”的線性表 C）循環(huán)隊(duì)列是非線性結(jié)構(gòu) D）有序線性表既可以采用順

63、序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)【2009.3】(17)支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是【 】 A）棧 B）樹(shù) C）隊(duì)列 D）二叉樹(shù),√,√,,,二級(jí)ACCESS—查詢,過(guò)關(guān)練習(xí),,【2009.3】(18)某二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)是【 C 】 A）10 B） 8 C）6

64、 D）4【2009.3】(19)下列排序方法中，最壞情況下比較次數(shù)最少的是【 D 】 A）冒泡排序 B）簡(jiǎn)單選擇排序 C）直接插入排序 D）堆排序【2009.3】（20）假如用一個(gè)長(zhǎng)度為50的數(shù)組（數(shù)組元素的下標(biāo)從0到49）作為棧的存儲(chǔ)空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom=49,top=30（數(shù)組下標(biāo)）