計(jì)算機(jī)2級公共基礎(chǔ)知

1、計(jì)算機(jī)等級考試公共基礎(chǔ)知識 溫俊香1計(jì)算機(jī)二級考試公共基礎(chǔ)知識大綱 數(shù)據(jù)結(jié)構(gòu)與算法 程序設(shè)計(jì)基礎(chǔ) 軟件工程基礎(chǔ) 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)這四個方面在試卷中出現(xiàn)的情況是：選擇題10個（20分），填空題5個（10分），總分值占到了試卷卷面分的30，是一個不小的比例。 2計(jì)算機(jī)二級考試公共基礎(chǔ)知識試卷分析 章節(jié)考試時(shí)間數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計(jì)基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)2007年4月10分2分10分8分2007年9月12分4分8分6分2008年4月10分2分8分10分2008年9月10分2分8分10分2009年3月10分2分8分10分2009年9月10分2分8分10分2010年3月10分0分10分10分3算法

2、 算法的基本概念 2.算法復(fù)雜度的概念和意義 一、基本數(shù)據(jù)結(jié)構(gòu)與算法 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的概念 線性表 棧和隊(duì)列 樹與二叉樹 查找技術(shù) 排序技術(shù) 對于等級考試，這個部分的考核重點(diǎn)主要在算法和數(shù)據(jù)結(jié)構(gòu)的基本概念、二叉樹(遍歷、結(jié)點(diǎn)），還有排序和查找考試中也經(jīng)常會涉及到。4算法的定義對解題方案準(zhǔn)確而完整的描述稱為算法。算法是程序設(shè)計(jì)的核心 算法的基本概念 算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說，就是計(jì)算機(jī)解題的過程(計(jì)算的方法)。在這個過程中，無論是形成解題思路(推理實(shí)現(xiàn)的算法)還是編寫程序(操作實(shí)現(xiàn)的算法)，都是在實(shí)施某種算法。例： n個數(shù)從大到小進(jìn)行排序。 有多種排

3、序方法 ，常用的有冒泡排序、選擇排序等。算法不等于程序，也不等計(jì)算機(jī)方法，程序的編制不可能優(yōu)于算法的設(shè)計(jì)。講課說課5 2 . 算法的基本特征一個算法應(yīng)該具有以下五個重要的特征： 有窮性 確定性 輸入 輸出 可行性一個算法必須保證執(zhí)行有限步之后結(jié)束；算法的每一步驟必須有確切的定義；一個算法有0個或多個輸入，以刻畫運(yùn)算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件；一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成 擁有足夠的情報(bào)6算法與計(jì)算機(jī)程序 算法_是一組邏輯步驟 程序用計(jì)算機(jī)語言描述的

4、算法3. 算法的表示INPUT rS=3.14 * r*rPTINT S開始輸入RS=3.14 * R*R輸出S結(jié)束問題：輸入園的半徑，計(jì)算園的面積 一個算法的表示需要使用一些語言形式。傳統(tǒng)的算法-圖形法，如“流程圖”和N-S圖目前常用的方法-使用偽碼描述算法。7冒泡排序的方法：1.掃描整個線性表，逐次對相鄰的兩個元素進(jìn)行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大的元素排到表的最后 ；2.除最后一個元素，對剩余的元素重復(fù)上述過程，將次大的數(shù)排到表的倒數(shù)第二個位置；3.重復(fù)上述過程；對于長度為n的線性表，冒泡排序需要對表掃描n-1遍。 算法舉例：n個數(shù)排序84. 算法的兩個基本要素：基本運(yùn)算

5、和操作 算術(shù)運(yùn)算 關(guān)系運(yùn)算 邏輯運(yùn)算 數(shù)據(jù)傳輸控制結(jié)構(gòu) 順序 選擇 循環(huán)一是對數(shù)據(jù)對象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)。算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法 95. 算法的復(fù)雜度 評價(jià)一個算法優(yōu)劣的主要標(biāo)準(zhǔn)是算法的執(zhí)行效率和存儲需求： 時(shí)間復(fù)雜度：執(zhí)行這個算法所需要的計(jì)算工作量一般可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量計(jì)算工作量 空間復(fù)雜度：執(zhí)行這個算法所需要的內(nèi)存空間 算法在執(zhí)行過程中臨時(shí)占用的存儲空間 時(shí)間復(fù)雜度它大致等于計(jì)算機(jī)執(zhí)行一種簡單操作所需的平均時(shí)間與算法中進(jìn)行簡單操作的次數(shù)的乘積。 一個算法在計(jì)算機(jī)存儲器上所占用的存儲空間，包括存儲算法本

6、身所占用的存儲空間、算法中的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運(yùn)行過程中臨時(shí)占用的存儲空間這三個部分10(1) 在計(jì)算機(jī)中，算法是指_。 A. 查詢方法 B. 加工方法 C. 解題方案的準(zhǔn)確而完整的描述 D. 排序方法(2)下列敘述中正確的是 （07年4月）A)算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B)算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的D)算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)(3)算法的有窮性是指 (08年4月)A）算法程序的運(yùn)行時(shí)間是有限的 B）算法程序所處理的數(shù)據(jù)量是有限的 C）算法程序的長度是有限的 D）算法只能被有限的

7、用戶使用(c)(B)算法習(xí)題:(A)11(4) 算法的時(shí)問復(fù)雜度是指 (2010年3月)A)算法的執(zhí)行時(shí)間B)算法所處理的數(shù)據(jù)量C)算法程序中的語句或指令條數(shù)D)算法在執(zhí)行過程中所需要的基本運(yùn)算次數(shù)(5) 算法的空間復(fù)雜度是指 (09年9月) A）算法在執(zhí)行過程中所需要的計(jì)算機(jī)存儲空間B）算法所處理的數(shù)據(jù)量C）算法程序中的語句或指令條數(shù)D）算法在執(zhí)行過程中所需要的臨時(shí)工作單元數(shù)(6) 下列敘述中正確的是 (06年9月)A）一個算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大B）一個算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小C）一個算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小 D）上述三種說法都不對(D)計(jì)

8、算工作量(A)(D)12 算法的時(shí)間復(fù)雜度是指A) 執(zhí)行算法程序所需要的時(shí)間 B) 算法程序的長度C) 算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù) D) 算法程序中的指令條數(shù)算法的基本特征是可行性、確定性、 【1】 和擁有足夠的情報(bào)。算法的空間復(fù)雜度是指 A) 算法程序的長度 B) 算法程序中的指令條數(shù) C) 算法程序所占的存儲空間 D) 執(zhí)行過程中所需要的存儲空間在計(jì)算機(jī)中，算法是指 A) 加工方法B) 解題方案的準(zhǔn)確而完整的描述 C) 排序方法D) 查詢方法例題講解有窮性13算法分析的目的是 A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 找出算法中輸入和輸出之間的關(guān)系 C) 分析算法的易懂性和可靠性 D) 分

9、析算法的效率以求改進(jìn)算法的工作量大小和實(shí)現(xiàn)算法所需的存儲單元多少分別稱為算法的 【1】 。時(shí)間復(fù)雜度和空間復(fù)雜度14 計(jì)算機(jī)在進(jìn)行數(shù)據(jù)處理時(shí)，實(shí)際需要處理的數(shù)據(jù)元素一般有很多，而這些大量的數(shù)據(jù)元素都需要存放在計(jì)算機(jī)中，因此，大量的數(shù)據(jù)元素在計(jì)算機(jī)中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計(jì)算機(jī)的存儲空間，這是進(jìn)行數(shù)據(jù)處理的關(guān)鍵問題。二、數(shù)據(jù)結(jié)構(gòu)程序=算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 一般來說，人們不會同時(shí)處理特征完全不同且互相之間沒有任何關(guān)系的各類數(shù)據(jù)元素，對于具有不同特征的數(shù)據(jù)元素總是分別進(jìn)行處理。一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在有某種

10、關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。超市的物品如何存放才好找且節(jié)省空間呢？15二. 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)科，它包括三個方面。（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；（3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。161. 邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。例：1. 一年四季的數(shù)據(jù)結(jié)構(gòu) B=(D,R)

11、D=春，夏，秋，冬 R=(春，夏) ,(夏，秋),(秋，冬)2. 家庭成員的數(shù)據(jù)結(jié)構(gòu) B=(D,R) D=父親，兒子，女兒 R=(父親，兒子) ,(父親，女兒)春夏秋冬數(shù)據(jù)結(jié)構(gòu)的圖形表示父親兒子女兒17常見的邏輯結(jié)構(gòu)有：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。線性結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu) 線性結(jié)構(gòu) 結(jié)構(gòu)中的每個元素之間存在一個對一個的關(guān)系； 樹形結(jié)構(gòu) 結(jié)構(gòu)中的每個元素之間存在一個對多個的關(guān)系； 圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的每個元素之間存在多個對多個的關(guān)系。其中，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為非線形結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以用二元關(guān)系表示，也可以直觀地用圖形來表示。18 2. 存儲結(jié)構(gòu)（物理結(jié)構(gòu)） 計(jì)算機(jī)在實(shí)際進(jìn)行數(shù)

12、據(jù)處理時(shí)，被處理的各數(shù)據(jù)元素總是被存放在計(jì)算機(jī)的存儲空間中，并且，各數(shù)據(jù)元素在計(jì)算機(jī)存儲空間中的位置與它們的邏輯關(guān)系不一定是相同的，而且一般也不可能相同。如：一年四季 家庭成員 計(jì)算機(jī)存儲空間怎樣存放？ 存儲結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的具體實(shí)現(xiàn)。常見的存儲結(jié)構(gòu)有： 順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu) 索引存儲結(jié)構(gòu)只抽象地反映數(shù)據(jù)元素之間的關(guān)系的結(jié)構(gòu)，而不管其存儲方式的數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要表示成一種或多種存儲結(jié)構(gòu)。193. 數(shù)據(jù)的運(yùn)算 檢索 插入 刪除 更新 排序 通常，一個數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點(diǎn)可能是動態(tài)變化的。根據(jù)需要或在處理過程中，可以在一個數(shù)據(jù)結(jié)構(gòu)中增加一個新結(jié)點(diǎn)（

13、插入運(yùn)算），也可以刪除某個結(jié)點(diǎn)（刪除運(yùn)算），除此之外，對數(shù)據(jù)結(jié)構(gòu)的運(yùn)算還有查找、分類、合并、分解、復(fù)制和修改。 在對數(shù)據(jù)結(jié)構(gòu)的處理過程中，不僅數(shù)據(jù)結(jié)構(gòu)中結(jié)點(diǎn)的個數(shù)在動態(tài)變化，而且，各數(shù)據(jù)元素之間的關(guān)系也有可能在動態(tài)地變化。如：無序表變有序表數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)科，研究以下三方面內(nèi)容： 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算父親兒子女兒20常見的數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)分類 線性結(jié)構(gòu)與非線性結(jié)構(gòu)兩大類型線性結(jié)構(gòu)：一個非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的兩個條件，則這種數(shù)據(jù)結(jié)構(gòu)即為線性結(jié)構(gòu)。 有且僅有一個根結(jié)點(diǎn)； 除第一個結(jié)點(diǎn)外，每一個結(jié)點(diǎn)最多有一個前件； 除最后一個結(jié)點(diǎn)外，每一個結(jié)點(diǎn)最多

14、有一個后件。常見的線性結(jié)構(gòu)有：線性表、棧、隊(duì)列、線性鏈表等21a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)常見的非線性結(jié)構(gòu)有樹、二叉樹、圖等非線性結(jié)構(gòu)：一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)。22 線性表（Linear List） 線性表是由n（n0）個數(shù)據(jù)元素 a1，a2，ai，an組成的一個有限序列。簡單的線性表春夏秋冬復(fù)雜的線性表記錄1 02011001 張三 男記錄2 02011003 李四 女 記錄3記錄423線性表的順序存儲結(jié)構(gòu)特點(diǎn)： 順序存儲結(jié)構(gòu)把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里，順序存儲結(jié)構(gòu)只存儲結(jié)點(diǎn)的值，不存儲結(jié)點(diǎn)間的關(guān)系，結(jié)點(diǎn)間的關(guān)系由存儲單元的鄰接關(guān)系來體

15、現(xiàn)。a1a2aian存儲地址200020042000+4*(i-1)2000+4*(n-1)占4個字節(jié)Loa（ai）=Loa（a1）+L*（i-1）第i個數(shù)的地址第一個數(shù)的地址L為該類型數(shù)所占的字節(jié)線性表的存儲結(jié)構(gòu)線性表的存儲結(jié)構(gòu)有兩種： 順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu)24 順序表的插入運(yùn)算 順序表的刪除運(yùn)算順序表的插入和刪除運(yùn)算 在線性表順序存儲情況下，要插入或刪除一個元素，都會由于數(shù)據(jù)元素的移動而消耗大量的處理時(shí)間，所以這種存儲方式對于小線性表或其中數(shù)據(jù)元素不經(jīng)常變動的線性表是合適的。線性表的順序存儲結(jié)構(gòu)稱為順序表。25插入運(yùn)算ai-1.a2a1alengthai+1ai xai-1.a2a1

16、alengthai+1ai X 插入算法的分析: 假設(shè)線性表中含有n個數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：26 刪除運(yùn)算ai-1.a2a1alengthai+1aiai-1.a2a1alengthai+1刪除算法的分析: 在進(jìn)行刪除操作時(shí)，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為：總結(jié): 順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時(shí)，平均需要移動大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時(shí)，這一點(diǎn)需要值得考慮。27線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。 鏈?zhǔn)酱鎯Y(jié)構(gòu)不

17、要求邏輯上相鄰的數(shù)據(jù)元素物理位置也相鄰，而且各數(shù)據(jù)元素的存儲順序也是任意的。各數(shù)據(jù)元素的先后關(guān)系是由各結(jié)點(diǎn)的指針域指示。 鏈?zhǔn)酱鎯Y(jié)構(gòu)的每一個存儲結(jié)點(diǎn)不僅存儲結(jié)點(diǎn)的值，而且存儲結(jié)點(diǎn)之間的關(guān)系：鏈?zhǔn)酱鎯Y(jié)構(gòu)分為單鏈表、雙向鏈表、循環(huán)鏈表線性鏈表不能隨機(jī)存取數(shù)據(jù)域指針域28設(shè)線性表為（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)線性鏈表的物理狀態(tài)1a12a23a34a45a567線性表的順序存儲結(jié)構(gòu)注意:1 2 3 此類編號不代表所在的地址單元的地址編碼線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其插入與刪除操作

18、29zhaoqiansunlizhouwuzhengwang /H存儲地址數(shù)據(jù)17131925313743liqiansunwangwuzhaozhengzhou指針43131null377192531頭指針單鏈表30單鏈表的插入運(yùn)算在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)單鏈表刪除運(yùn)算PbaxSbaPLaaianai-1ai+1要求:刪除結(jié)點(diǎn)ai。31循環(huán)鏈表: 首尾相接的鏈表。 將最后一個結(jié)點(diǎn)的空指針改為指向頭結(jié)點(diǎn)，從任一結(jié)點(diǎn)出發(fā)均可找到其它結(jié)點(diǎn)。a1a2ana3L.帶頭結(jié)點(diǎn)的單鏈表a1a2ana3L.循環(huán)單鏈表特點(diǎn): 可以從任何一個結(jié)點(diǎn)開始訪問鏈表的所有結(jié)點(diǎn).32雙向鏈表的存儲結(jié)構(gòu) 在每個結(jié)點(diǎn)中

19、設(shè)置兩個指針，一個指向后繼，一個指向前驅(qū)?？芍苯哟_定一個結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)。可提高效率。HEAD31510 a2 a3 a4 a1提問：單向鏈表的缺點(diǎn)是什么？ 提示：如何尋找結(jié)點(diǎn)的直接前趨。 雙向鏈表可以克服單鏈表的單向性的缺點(diǎn)。 在雙向鏈表的結(jié)點(diǎn)中有兩個指針域，其一指向直接后繼，另一指向直接前趨。 雙向循環(huán)鏈表 33線性表的應(yīng)用：應(yīng)用最廣的數(shù)據(jù)結(jié)構(gòu)。.高級語言中的數(shù)組；計(jì)算機(jī)的文件系統(tǒng)；計(jì)算機(jī)的目錄系統(tǒng)；電話號碼查詢系統(tǒng)（可采用順序表或單鏈表結(jié)構(gòu)）；各種事務(wù)處理（可采用順序表或單鏈表結(jié)構(gòu)）;342. 棧和隊(duì)列棧和隊(duì)列是兩種特殊的線性表，它們是運(yùn)算時(shí)要受到某些限制的線性表，故也稱為限定性的數(shù)

20、據(jù)結(jié)構(gòu)。 棧（Stack）及其基本運(yùn)算 隊(duì)列（Queue）及其基本運(yùn)算 循環(huán)隊(duì)列及其基本運(yùn)算351 .棧棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。棧頂表尾。棧底表頭?？諚２缓氐目毡?。a1a2an棧底棧頂進(jìn)棧出棧棧s=(a1,a2,an)后進(jìn)先出或先進(jìn)后出（LIFO）36棧的物理存儲結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈表結(jié)構(gòu)。下面討論順序存儲結(jié)構(gòu)中棧元素的插入和刪除運(yùn)算。 順序棧的進(jìn)棧和出棧運(yùn)算 棧的基本運(yùn)算有三種：入棧、退棧和讀棧頂元素 在順序棧中插入和刪除運(yùn)算不需要移動表中其他數(shù)據(jù)元素。372. 棧的順序存儲結(jié)構(gòu)及其基本運(yùn)算 a2 a1 a1 a2 top 用順序存儲結(jié)構(gòu)表示的棧: 順序棧用

21、一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設(shè)置一個簡單變量top指示棧頂位置，稱為針棧頂指，它始終指向待插入元素的位置?；具\(yùn)算：壓（進(jìn)）棧：PUSH出棧：POP讀棧頂元素：gettop38例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空桟：topbase非空桟：top始終在桟頂元素的后一個位置桟的元素個數(shù)：top-base上溢下溢392、隊(duì)列定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在 表的另一端進(jìn)行刪除的線性表 。此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）表。 a1 , a2 , a3 , a4 , an-1 , an 隊(duì) 列 示

22、 意 圖隊(duì)頭隊(duì)尾先進(jìn)先出后進(jìn)后出（LIFO）40 e3 e4 (c)e1,e2出隊(duì)，e4入隊(duì) 隊(duì) 滿rear =3front e1 e2 e3 (b)rearfront(b)e1,e2,e3入隊(duì)隊(duì)列的順序存儲結(jié)構(gòu)及其基本運(yùn)算 3 2 1 0 (a)rear=front=-1(隊(duì)空）rearfront空隊(duì)列:非空隊(duì)列:隊(duì)列元素個數(shù):rear=front=-1front始終指向隊(duì)頭元素前一個位置，而rear始終指向隊(duì)尾元素的位置rear-front41 隊(duì)列的物理存儲結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈?zhǔn)浇Y(jié)構(gòu)。 順序隊(duì)列的運(yùn)算 棧有三種操作： 入棧出棧讀棧頂元素隊(duì)列有三種操作：入隊(duì)出隊(duì)讀隊(duì)首元素例：有入

23、棧元素序列：ABCD，求可能的出棧序列如是隊(duì)列又是什么情況呢？42 循環(huán)隊(duì)列 把隊(duì)列的存儲空間在邏輯上看作一個環(huán)，當(dāng)R指向存儲空間的末端后，就把它重新置于始端。 循環(huán)隊(duì)列的運(yùn)算隊(duì)列中進(jìn)行插入的一端稱做隊(duì)尾(rear),進(jìn)行刪除的一端稱做隊(duì)首(front)。 習(xí)題：數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，循環(huán)隊(duì)列屬于【 】結(jié)構(gòu)。（2005年9月）答案：存儲結(jié)構(gòu)。43frontrearMaxsize-101 e3 e4 rear =3front440012345frontABCDEFrear上溢0012345frontrear下溢front=rear隊(duì)滿front=rear隊(duì)空45數(shù)據(jù)存儲結(jié)構(gòu)方面的考題

24、1：數(shù)據(jù)的存儲結(jié)構(gòu)是指 （2005年4月）A) 存儲在外存中的數(shù)據(jù) B) 數(shù)據(jù)所占的存儲空間量C) 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲方式 D) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示2. 下列敘述中正確的是 （2009年3月） A）棧是“先進(jìn)先出”的線性表 B）隊(duì)列是“先進(jìn)后出”的線性表 C）循環(huán)隊(duì)列是非線性結(jié)構(gòu) D）有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu) 3. 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于 。4. 下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是A）循環(huán)隊(duì)列 B) 帶鏈隊(duì)列C) 二叉樹 D）帶鏈棧答案：D。答案：D。答案：線性結(jié)構(gòu)。答案：c465。下列敘述中正確的是（ ）。 （200

25、8年9月） A）順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的 B）順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu) C）順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表 D）鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間答案：A。6。下列關(guān)于棧的敘述正確的是 （2008年4月） A）棧按“先進(jìn)先出”組織數(shù)據(jù) B)棧按“先進(jìn)后出”組織數(shù)據(jù) C）只能在棧底插入數(shù)據(jù) D）不能刪除數(shù)據(jù) 答案：B。7. 一個隊(duì)列的初始狀態(tài)為空?，F(xiàn)將元素A，B，C，D，E，F(xiàn)，5，4，3，2，1依次入隊(duì)，然后再依次退隊(duì)，則元素退隊(duì)的順序?yàn)?【1】 。（2010年3月） 答案：A，B，C，D，E

26、，F(xiàn)，5，4，3，2，1479. 設(shè)某循環(huán)隊(duì)列的容量為50，如果頭指針front=45(指向隊(duì)頭元素的前一位置)，尾指針rear=10(指向隊(duì)尾元素)，則該循環(huán)隊(duì)列中共有 【2】 個元素。 （2010年3月） 8。假設(shè)用一個長度為50的數(shù)組（數(shù)組元索的下標(biāo)從0到49）作為棧的存儲空間，棧底指針bottom指間棧底元素，棧頂指針top指向棧頂元素，如果bottom=49，top=30（數(shù)組下標(biāo)），則棧中具有【 】個元素。 （2009年3月） 答案：19答案表不具有的特點(diǎn)是A) 不必事先估計(jì)存儲空間 B) 可隨機(jī)訪問任一元素C) 插入刪除不需要移動元素D) 所需空間與線性

27、表長度成正比數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于 【1】 。 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的 A) 存儲結(jié)構(gòu)B) 物理結(jié)構(gòu) C) 邏輯結(jié)構(gòu)D) 物理和存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 【1】 兩大類。數(shù)據(jù)的存儲結(jié)構(gòu)是指A）數(shù)據(jù)所占的存儲空間B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示C）數(shù)據(jù)在計(jì)算機(jī)中的順序存儲方式D）存儲在外存中的數(shù)據(jù) 例題講解存儲結(jié)構(gòu) 非線性結(jié)構(gòu)49順序存儲方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置 【2】 的存儲單元中。 數(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)、對各種數(shù)據(jù)結(jié)

28、構(gòu)進(jìn)行的運(yùn)算，以及 A) 數(shù)據(jù)的存儲結(jié)構(gòu) B) 計(jì)算方法 C) 數(shù)據(jù)映象 D) 邏輯存儲線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是 A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu) 相鄰50根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成 A) 動態(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】 以及對數(shù)據(jù)的操作運(yùn)算。數(shù)據(jù)的基本單位是 【5】

29、。下列敘述中，錯誤的是 A) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) 數(shù)據(jù)的存儲結(jié)構(gòu)在計(jì)算機(jī)中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)存儲結(jié)構(gòu)數(shù)據(jù)元素51鏈表不具有的特點(diǎn)是A) 不必事先估計(jì)存儲空間 B) 可隨機(jī)訪問任一元素C) 插入刪除不需要移動元素D) 所需空間與線性表長度成正比順序存儲方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置 【2】 的存儲單元中。長度為n的順序存儲線性表中，當(dāng)在任何位置上插入一個元素概率都相等時(shí)，插入一個元素所需移動元素的平均個數(shù)為 【1】 。線性表若采用順序存儲結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地

30、址 A) 必須是連續(xù)的 B) 部分地址必須是連續(xù)的 C) 一定是不連續(xù)的 D) 連續(xù)不連續(xù)都可以例題講解相鄰52線性表L=(a1,a2,a3,ai，an)，下列說法正確的是 A) 每個元素都有一個直接前件和直接后件 B) 線性表中至少要有一個元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一個 且只有一個直接前件和直接后件線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是 A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、

31、任意存取的存儲結(jié)構(gòu) 下列敘述中，錯誤的是 A) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) 數(shù)據(jù)的存儲結(jié)構(gòu)在計(jì)算機(jī)中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu) 53根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成 A) 動態(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)當(dāng)線性表采用順序存儲結(jié)構(gòu)實(shí)現(xiàn)存儲時(shí)，其主要特點(diǎn)是 【1】 。隨機(jī)存取54鏈表不具有的特點(diǎn)是A) 不必事先估計(jì)存儲空間 B) 可隨機(jī)訪問任一元素C) 插入刪除不需要移動元素D) 所需空間與線性

32、表長度成正比用鏈表表示線性表的優(yōu)點(diǎn)是A) 便于隨機(jī)存取 B) 花費(fèi)的存儲空間較順序存儲少C) 便于插入和刪除操作 D) 數(shù)據(jù)元素的物理順序與邏輯順序相同長度為n的順序存儲線性表中,當(dāng)在任何位置上插入一個元素概率都相等時(shí),插入一個元素所需移動元素的平均個數(shù)為 【1】 。在單鏈表中，增加頭結(jié)點(diǎn)的目的是 A) 方便運(yùn)算的實(shí)現(xiàn) B) 使單鏈表至少有一個結(jié)點(diǎn) C) 標(biāo)識表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置 D) 說明單鏈表是線性表的鏈?zhǔn)酱鎯?shí)現(xiàn)例題講解55非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向) ，滿足 A) p-next=NULLB) p=NULL C) p-next=head D) p=head 循環(huán)鏈表的主

33、要優(yōu)點(diǎn)是 A) 不再需要頭指針了 B) 從表中任一結(jié)點(diǎn)出發(fā)都能訪問到整個鏈表 C) 在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開 D) 已知某個結(jié)點(diǎn)的位置后，能夠容易的找到它的直接前件當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為 【2】 。用鏈表表示線性表的突出優(yōu)點(diǎn)是 【1】 。上溢插入、刪除靈活56棧和隊(duì)列的共同特點(diǎn)是 A)都是先進(jìn)先出 B) 都是先進(jìn)后出 C) 只允許在端點(diǎn)處插入和刪除元素 D) 沒有共同點(diǎn)如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是 A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1

34、,e2D) 任意順序一些重要的程序語言(如C語言和Pascal語言) 允許過程的遞歸調(diào)用。而實(shí)現(xiàn)遞歸調(diào)用中的存儲分配通常用 A) 棧B) 堆 C) 數(shù)組 D) 鏈表例題講解57棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE 棧通常采用的兩種存儲結(jié)構(gòu)是 A) 線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)B) 散列方式和索引方式 C) 鏈表存儲結(jié)構(gòu)和數(shù)組 D) 線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)棧和隊(duì)列通常采用的存儲結(jié)構(gòu)是 【1】 。下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是 A) 線性鏈表 B) 棧

35、C) 循環(huán)鏈表 D) 順序表當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為 【2】 。鏈表存儲結(jié)構(gòu)和數(shù)組上溢58由兩個棧共享一個存儲空間的好處是A) 減少存取時(shí)間，降低下溢發(fā)生的機(jī)率 B) 節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率C) 減少存取時(shí)間，降低上溢發(fā)生的機(jī)率 D) 節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率下列關(guān)于棧的敘述中正確的是）在棧中只能插入數(shù)據(jù) B）在棧中只能刪除數(shù)據(jù)C）棧是先進(jìn)先出的線性表 D）棧是后進(jìn)先出的線性表下列關(guān)于隊(duì)列的敘述中正確的是）在隊(duì)列中只能插入數(shù)據(jù) B）在隊(duì)列中只能刪除數(shù)據(jù)C）隊(duì)列是先進(jìn)先出的線性表 D）隊(duì)列是后進(jìn)先出的線性表59樹型

36、結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。 樹的概念 二叉樹的概念 二叉樹的存儲 二叉樹的遍歷3. 樹與二叉樹60樹的概念 樹的定義：是一種簡單的非線性結(jié)構(gòu)。 n個結(jié)點(diǎn)的有限集。（n=0） ABDFECGHIJKM結(jié)點(diǎn)：根結(jié)點(diǎn)：沒有前件的結(jié)點(diǎn)只有一個稱為根結(jié)點(diǎn)。 簡稱樹的根?？諛洌簾o結(jié)點(diǎn)則稱為空樹； 父結(jié)點(diǎn)：結(jié)點(diǎn)的前件稱該結(jié)點(diǎn)的父結(jié)點(diǎn)。A只有一個結(jié)點(diǎn)的樹61樹型結(jié)構(gòu)的常用術(shù)語ABDFECGHIJKM子結(jié)點(diǎn)：結(jié)點(diǎn)的后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。可以有多個。葉子結(jié)點(diǎn) 沒有后件的結(jié)點(diǎn)； Q：圖中葉子結(jié)點(diǎn)有幾個？7結(jié)點(diǎn)的度 一個結(jié)點(diǎn)的子樹的個數(shù)；(有幾個分叉) Q：結(jié)點(diǎn)A、G的度數(shù)？3，2. Q：度數(shù)為0、1、2、3的

37、結(jié)點(diǎn)分別有幾個？ 樹的度 樹中所有結(jié)點(diǎn)度的最大值；Q：右圖中樹的度？362樹型結(jié)構(gòu)的常用術(shù)語ABDFECGHIJKM 結(jié)點(diǎn)的層次 樹中根結(jié)點(diǎn)的層次為1，根結(jié)點(diǎn)子樹的根為第2層，以此類推； Q：圖中結(jié)點(diǎn)F的層次？ 樹的深度 樹中所有結(jié)點(diǎn)層次的最大值； Q：圖中樹的深度？ 有序樹、無序樹 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。63二叉樹的概念 定義：二叉樹是一種有序的樹形結(jié)構(gòu)。它與一般樹形結(jié)構(gòu)的區(qū)別是： 每個結(jié)點(diǎn)最多有兩棵子樹； 子樹有左右之分，次序不能任意顛倒。稱左子樹和右子樹 二叉樹的5種基本形態(tài)64第65頁樹與二叉樹的區(qū)別A樹和二叉樹的結(jié)點(diǎn)個數(shù)

38、最少都可為0。B樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，二叉樹結(jié)點(diǎn)最大度數(shù)為2。C樹的結(jié)點(diǎn)無左、右之分，二叉樹的結(jié)點(diǎn)子樹有明確的左、右之分。3個結(jié)點(diǎn)的樹3個結(jié)點(diǎn)的二叉樹65二叉樹的性質(zhì)【性質(zhì)1】 在二叉樹的第i層上最多有2i-1個結(jié)點(diǎn)（i1）ABCDFEHG12131415891011456712366【性質(zhì)2】深度為h的二叉樹最多有2h -1個結(jié)點(diǎn)（h 1）ABCDFEHG12131415891011456712367【性質(zhì)3】二叉樹上葉子結(jié)點(diǎn)數(shù)比度為2的結(jié)點(diǎn)數(shù)多1ABCDFEHG度為2的結(jié)點(diǎn)葉子結(jié)點(diǎn)68滿二叉樹和完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)。最后一層的結(jié)點(diǎn)均為0度

39、。完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。則稱這棵二叉樹為完全二叉樹。完全二叉樹中度數(shù)為1的結(jié)點(diǎn)的個數(shù)為0或1。69121314158910114567123滿二叉樹完全二叉樹12138910114567123 完全二叉樹是滿二叉樹 滿二叉樹也是完全二叉樹701213891011456123非完全二叉樹深度為4的完全二叉樹8456712371【性質(zhì)4】具有n個結(jié)點(diǎn)的完全二叉樹的深度為 log2 (n+1) 其中，log2n 的結(jié)果是不大于log2n的最大整數(shù)121314158910114567123深度為4的滿二叉樹深度為4的完全二叉樹8456

40、7123深度為3的完全二叉樹具有47個結(jié)點(diǎn)深度為4的完全二叉樹具有815深度為5的完全二叉樹具有1531log2(8+1) = ln9/In2=4log2 (15+ 1) =In16/In2=4深度為6的完全二叉樹 具有3263深度為7的完全二叉樹 具有64127深度為8的完全二叉樹 具有128255深度為9的完全二叉樹 具有256511深度為10的完全二叉樹具有5121023深度為11的完全二叉樹具有1024204772性質(zhì)5：具有n個結(jié)點(diǎn)的完全二叉樹的深度為112345678910121例：n=2 k=2 n=6 k=3 n=7 k=3 n=8 k=4 n=12 k=473性質(zhì)6：如果對一

41、棵有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層 序編號，則對任一結(jié)點(diǎn)i(1=i=1,則雙親Parent(i)是結(jié)點(diǎn)|i/2|。(2)如果2i=n,則編號i的左子結(jié)點(diǎn)為2 i，否則無左子結(jié)點(diǎn)，顯然也就沒有右子結(jié)點(diǎn)。 (3)如果2i+11它的雙親是i/2取整，左子結(jié)點(diǎn)是2*i，右子結(jié)點(diǎn)是2*i+1.當(dāng)然如果算下來超過總數(shù)民N，則為沒有。74例：112345678910121i=6 其雙親為|i/2|= 3；其左子結(jié)點(diǎn)為2*i=12;i=1 是樹的根,無雙親;其左子結(jié)點(diǎn)為2*i=2,右子結(jié)點(diǎn)為2*i+1=3 .2*i=1812 2*i+1=1912 其無左、右子結(jié)點(diǎn)。2*i+1=1312 其無右子結(jié)點(diǎn)。i=9

42、其雙親為|i/2|= 4 ；751：在深度為7的滿二叉樹中,葉子結(jié)點(diǎn)的個數(shù)為（2006年4月） A)32 B)31 C)64 D)632：在深度為7的滿二叉樹中，度為2的結(jié)點(diǎn)個數(shù)為【 】 。(07年4月）3：一棵二叉樹中共有70個葉子結(jié)點(diǎn)與80個度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為 （07年9月） A）219 B）221 C）229 D）2314： 某二叉樹中度為2的結(jié)點(diǎn)有18個，則該二叉樹中有 【 】個葉子結(jié)點(diǎn)。（2005年4月）5：一棵二叉樹第六層（根結(jié)點(diǎn)為第一層）的結(jié)點(diǎn)數(shù)最多為【 】個。（2005年9月） 樹型結(jié)構(gòu)方面的考題 1答案：C。3答案：A。5答案：32。2答案：63。4答案：

43、19。76二叉樹的存儲 在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。對于滿二叉樹和完全二叉樹可以按層進(jìn)行順序存儲。LlinkinfoRlink二叉樹的存儲結(jié)點(diǎn)的結(jié)構(gòu)ABDCFGE A G E F B C Dt772、二叉樹的存儲結(jié)構(gòu) (2) 鏈?zhǔn)酱鎯Y(jié)構(gòu)T16若父結(jié)點(diǎn)在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。11 A B c F E D 1 2 4 8 910 5 6 3 712131415(1) 順序存儲結(jié)構(gòu)(1) 順序存儲結(jié)構(gòu)2h-1=24-1 = 15用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。0000FE000DC0BA15141

44、312111098765432100一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費(fèi)。78(2) 鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉鏈表三叉鏈表二叉鏈表：二叉鏈表的結(jié)點(diǎn)包含三個域：數(shù)據(jù)域、左、右指針域。例：ABCDEFG A B C D E F G 79三叉鏈表：三叉鏈表的結(jié)點(diǎn)包含四個域： 數(shù)據(jù)域、左、右、雙親指針域。例：ABCDEFG A B C D E F G 鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)： （1）操作便于實(shí)現(xiàn) （2）結(jié)構(gòu)復(fù)雜80二叉樹的遍歷 遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。 二叉樹的遍歷的次序與樹型結(jié)構(gòu)上的大多數(shù)運(yùn)算有聯(lián)系。遍歷的方式有三種（1）先（前）序遍歷（DLR）（2）中序遍歷（LDR

45、）（3）后序遍歷（LRD）ABCDFEHG81二叉樹的遍歷 遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。（1）先（前）序遍歷（DLR）根左右 若二叉樹為空，則結(jié)束遍歷操作；否則訪問根結(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹。ABCDFEHG先序遍歷的結(jié)果： A B E C F G H D82（2）中序遍歷（LDR）左根右 若二叉樹為空，則結(jié)束遍歷操作；否則中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。中序遍歷的結(jié)果： E B A F H G C D（3）后序遍歷（LRD）右根左 若二叉樹為空，則結(jié)束遍歷操作；否則后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)。后序遍歷的結(jié)果： E B H G F D C AA

46、BCDFEHG83先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCAABCFHDEG下圖所示的二叉樹經(jīng)過三種遍歷得到的順序分別為？練習(xí)：根據(jù)先序遍歷序列，建立二叉樹841:設(shè)二叉樹如下： （2010年3月）對該二叉樹進(jìn)行后序遍歷的結(jié)果為 【3】 樹型結(jié)構(gòu)方面的考題 22: 對如下二叉樹（2006年4月）進(jìn)行后序遍歷的結(jié)果為A) ABCDEFB) DBEAFC C) ABDECFD) DEBFCA EDBGHFCA DABCFHDGE85已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是 A) acbed B) decab C) deab

47、c D) cedba 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為 A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是 A) 有且只有1B) 1或多于1 C) 0或1D) 至少2下列敘述中正確的是 A) 線性表是線性結(jié)構(gòu)B) 棧與隊(duì)列是非線性結(jié)構(gòu) C) 線性鏈表是非線性結(jié)構(gòu)D) 二叉樹是線性結(jié)構(gòu)例題講解86在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為 A) 32 B) 31 C) 16 D) 15 若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgba

48、echf，則其后序遍歷的結(jié)點(diǎn)訪問順序是 A) bdgcefha B) gdbecfha C) bdgaechf D) gdbehfca在樹結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 【1】 。具有3個結(jié)點(diǎn)的二叉樹有 A) 2種形態(tài) B) 4種形態(tài) C) 7種形態(tài) D) 5種形態(tài)設(shè)一棵二叉樹中有3個葉子結(jié)點(diǎn)，有8個度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為 A) 12 B) 13 C) 14D) 15 雙親結(jié)點(diǎn)87設(shè)有下列二叉樹： 對此二叉樹前序遍歷的結(jié)果為A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT設(shè)有下列二叉樹：對此二叉樹的中序遍歷的結(jié)果為A) ABCDEF B) D

49、BEAFC C) ABDECF D) DEBFCA88設(shè)樹T的度為4,其中度為1、2、3、4的結(jié)點(diǎn)個數(shù)分別為4、2、1、1。則T中的葉子結(jié)點(diǎn)數(shù)為A）8 B）7 C）6 D）5設(shè)一棵完全二叉樹共有700個結(jié)點(diǎn)，則該二叉樹中有（ ）個葉子結(jié)點(diǎn)。 在一個容量為15的循環(huán)隊(duì)列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊(duì)列中共有（ ）個元素。設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為（ ）。3503DEBFCA89 查找技術(shù) 查找是數(shù)據(jù)處理的重要內(nèi)容。 查找指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找指定的元素，該元素也稱關(guān)鍵字。 若找到了滿足條件的結(jié)點(diǎn)，稱查找

50、成功；否則稱查找失敗。 衡量一個查找算法的主要標(biāo)準(zhǔn)是查找過程中對關(guān)鍵字進(jìn)行的平均比較次數(shù)。 通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法： 順序查找 二分查找901.7.1.1 順序查找（線性查找）查找過程： 對給定的一關(guān)鍵字K，從線性表的一端開始，逐個進(jìn)行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端。可以采用從前向后查，也可采用從后向前查的方法。在平均情況下，大約要與表中一半以上元素進(jìn)行比較，效率較低。平均查找長度較大。 最好情況：1 最壞情況：n在下面兩種情況下只能采取順序查找： a. 線性表為無序表（元素排列是無序的）； b. 即使是有序線性表，但采用的是鏈?zhǔn)酱鎯Y(jié)構(gòu)

51、。911.7.1.2 折半查找（二分法查找）思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。 前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進(jìn)行。分三種情況： 1）若中間項(xiàng)的值等于x,則說明已查到。 2）若x小于中間項(xiàng)的值,則在線性表的前半部分查找； 3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較 log2n次。92折半查找算法舉例對給定數(shù)列（有序） 3，5，11，17，21，23，28，30，32，50，按折半查找算法，查找關(guān)鍵字值為30的數(shù)據(jù)元素。 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10

52、 第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)=30lowhighmidlowhighmid93練習(xí)假設(shè)待查有序（升序）順序表中數(shù)據(jù)元素的關(guān)鍵字序列為（8,18,27,42,47,50,56, 68,95,120），用折半查找方法查找關(guān)鍵字值為27的數(shù)據(jù)元素.對于長度為n的有序線性表，最壞情況只需比較log2n次。 941.7.2 排序1.7.2.1 概述 1、排序的功能： 將一個數(shù)據(jù)

53、元素（或記錄）的 任意序 列，重新排成 一個按關(guān)鍵字有序的序列。 2、排序過程的組成步驟： 首先比較兩個關(guān)鍵字的大?。?然后將記錄從一個位置移動到另一個位置。95排序方法插入排序選擇排序交換排序歸并排序簡單插入排序希爾排序簡單選擇排序堆排序起泡排序快速排序961.7.2.2 插入排序 簡單插入、希爾排序1、簡單插入排序: 基本思想：從數(shù)組的第2號元素開始，順序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當(dāng)位置上。97該算法適合于n 較小的情況，時(shí)間復(fù)雜度為O(n2).待排元素序列：53 27 36 15 69 42第一次排序： 27 53 36 15 69 42第二次排序： 27

54、 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ù)元素的待排序列，插入操作要進(jìn)行n-1趟最壞情況下： 需要n(n-1)/2次比較最好： n-1次比較98希爾排序：希爾排序的基本思想: 先將整個待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序,待整個序列中的記錄“基本有序”時(shí),再對全體記錄進(jìn)行一次直接插入排序.最壞情況下：需要O(n1.5 )次比較99 1、簡單選擇排序 思想：首先從1n個元素中選出關(guān)鍵字最小的記錄交換到第一個位置上。然后再

55、從第2 個到第n個元素中選出次小的記錄交換到第二個位置上，依次類推。1.7.2.3 選擇排序 簡單選擇排序、堆排序簡單選擇排序法,最壞情況需要n(n-1)/2次比較； 時(shí)間復(fù)雜度為O(n2)， 適用于待排序元素較少的情況。100第101|92頁初態(tài)： 15，14，22，30，37，15，11第一趟： 11 14，22，30，37，15，15第二趟： 11，14 22，30，37，15，15第三趟： 11，14，15 30，37，22，15第四趟： 11，14，15，15 37，22，30第五趟： 11，14，15，15，22 37，30第六趟： 11，14，15，15，22，30 37 有序序

56、列例：設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（15，14，22，30，37，11），每一趟排序后的序列狀態(tài)如圖所示：1012、堆排序（也是一種選擇排序） 堆是具有特定條件的順序存儲的完全二叉樹，其特定條件是：任何一個非葉子結(jié)點(diǎn)的關(guān)鍵字大于等于（或小于等于）子女的關(guān)鍵字的值。897624331510112536497856(a):堆頂元素取最大值(b):堆頂元素取最小值堆排序需要比較的次數(shù)為O(nlog2n) (1) 堆的示例 1021.7.2.4 交 換 排 序交換排序的特點(diǎn)在于交換。有冒泡和快速排序兩種。 1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。從左端開始比較。第一趟：第1個與第2個比較，大則交

57、換；第2個與第3個比較， 大則交換，關(guān)鍵字最大的記錄交換到最后一個位置上；第二趟：對前n-1個記錄進(jìn)行同樣的操作，關(guān)鍵字次大的記錄交換 到第n-1個位置上； 依次類推，則完成排序。103冒泡排序 冒泡排序的方法：掃描整個線性表，逐次對相鄰的兩個元素進(jìn)行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大(或最小)的元素排到表的最后(或最前) ；除最后(或最前)一個元素，對剩余的元素重復(fù)上述過程，將次大(或次小)的數(shù)排到表的倒數(shù)(或正數(shù))第二個位置；重復(fù)上述過程；對于長度為n的線性表，冒泡排序需要對表掃描n-1遍。 104冒泡排序的方法設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（18，20，15，32，4，25），第一

58、趟冒泡排序后的序列狀態(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ù)第二趟冒泡排序105Q：第二趟冒泡排序后的結(jié)果是什么樣的？達(dá)到了最終的排序目標(biāo)嗎？一共需要多少次能夠最后成為有序序列？Q：你覺得冒泡排序的效率如何？如果是你，你會用什么方法來排序？ 冒泡排序比較簡單，當(dāng)初始序列基本有序時(shí)，冒泡排序有較高的效率，反之效率較低。冒泡排序終止條件: 本趟排序未發(fā)生交換，終止排序算法 106初始 第一趟 第二趟 第三趟 第四趟 第

59、五趟序列 排序后 排序后 排序后 排序后 排序后26 18 18 18 18 918 26 26 26 9 1532 32 32 9 15 1854 47 9 15 2647 9 15 329 15 4715 54設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（26,18,32,54,47,9,15 )冒泡排序法，需要比較的次數(shù)為n(n-1)/2； 1072、快速排序 (對冒泡排序的改進(jìn)） 思想：通過一趟排序?qū)⒋判蛄蟹殖蓛刹糠?，使其中一部分記錄的關(guān)鍵字均比另一部分小，再分別對這兩部分排序，以達(dá)到整個序列有序。時(shí)間復(fù)雜度：O(log2n) 當(dāng)待排序列逆序時(shí)，蛻變成冒泡排序，時(shí)間復(fù)雜度: O(n(n-1)/2)108

60、1.7.2.5 內(nèi)部排序方法的選擇各種排序方法各有優(yōu)缺點(diǎn)，故在不同情況下可作不同的選擇。通常需考慮的因素有：待排序的記錄個數(shù)；記錄本身的大??；記錄的鍵值分布情況等。 若待排序的記錄個數(shù)n較小時(shí)，可采用簡單排序方法。 若n 較大時(shí)，應(yīng)采用快速排序或堆排序。 若待排序的記錄已基本有序，可采用簡單插入和起泡 排序。109方法歸并排序簡單插入希爾排序簡單選擇堆排序起泡排序快速排序插入選擇交換比較次數(shù)使用建議查找:方法順序折半比較次數(shù)log2n最好:1最壞:n平均:(n+1)/2使用條件順序存儲結(jié)構(gòu)的有序表任何表排序:n-1n(n-1)/2n1.5n(n-1)/2nlog2nn-1n(n-1)/2log