計算機二級考試-二級公共基礎(chǔ)知識

1、1234567891 1、算法的基本概念、算法的基本概念 算法算法是指解題方案準(zhǔn)確而完整的描述。算法具有4個重要特性:可行性、確定性、有窮性、擁有足夠的情報（輸入和可行性、確定性、有窮性、擁有足夠的情報（輸入和輸出）輸出） 綜上所述綜上所述, ,所謂所謂算法算法是一組嚴(yán)謹(jǐn)?shù)囟x運算順序的規(guī)則是一組嚴(yán)謹(jǐn)?shù)囟x運算順序的規(guī)則, ,并且每一個規(guī)則都是有效的并且每一個規(guī)則都是有效的, ,且明確的且明確的, ,此順序?qū)⒃谟邢薜拇螖?shù)此順序?qū)⒃谟邢薜拇螖?shù)下終止下終止. .102 2、算法的基本要素、算法的基本要素v 對數(shù)據(jù)對象的運算運算和操作操作： 算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸 算法中各操作之間的

2、執(zhí)行順序； 描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等； 一個算法一般可以用順序、選擇、循環(huán)順序、選擇、循環(huán)三種基本結(jié)構(gòu)組合而成。v 算法的控制結(jié)構(gòu)控制結(jié)構(gòu)： 113 3、算法設(shè)計的基本方法、算法設(shè)計的基本方法v 列舉法列舉法v 歸納法歸納法v 遞推遞推v 遞歸（直接遞歸，間接遞歸）遞歸（直接遞歸，間接遞歸）v 減半遞推技術(shù)減半遞推技術(shù)（將問題的規(guī)模減半，問題的性質(zhì)不變）（將問題的規(guī)模減半，問題的性質(zhì)不變） （P4P4例例1.11.1）v 回溯法回溯法121 1、時間復(fù)雜度、時間復(fù)雜度v 算法的算法的時間復(fù)雜度時間復(fù)雜度是指執(zhí)行算法所需要的計是指執(zhí)行算法所需要的計算工作

3、量。算工作量。v用算法執(zhí)行過程所需要的用算法執(zhí)行過程所需要的基本運算基本運算來度量算法來度量算法的工作量。的工作量。v 算法所執(zhí)行的基本次數(shù)還與算法所執(zhí)行的基本次數(shù)還與問題的規(guī)模問題的規(guī)模有關(guān)。有關(guān)。v基本運算次數(shù)還與基本運算次數(shù)還與特定的輸入特定的輸入有關(guān)有關(guān)13時間復(fù)雜度時間復(fù)雜度- -分析方法分析方法v 平均性態(tài)。平均性態(tài)。v 最壞情況復(fù)雜性（更有實用價值）最壞情況復(fù)雜性（更有實用價值）142 2、空間復(fù)雜度、空間復(fù)雜度v 一般是指執(zhí)行這個算法所需要的內(nèi)存空間內(nèi)存空間。v 一個算法所占用的存儲空間包括算法程序算法程序所占的空間、輸入的初始數(shù)據(jù)輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行執(zhí)行過

4、程中需要的額外空間額外空間。15v 算法的時間復(fù)雜度是指算法的時間復(fù)雜度是指( )( ) A A、執(zhí)行算法程序所需要的時間執(zhí)行算法程序所需要的時間 B B、算法程序的長度算法程序的長度 C C、算法執(zhí)行過程中所需要的基本運算次數(shù)算法執(zhí)行過程中所需要的基本運算次數(shù) D D、算法程序中的指令條數(shù)算法程序中的指令條數(shù)v 算法的基本特征是可行性、確定性、算法的基本特征是可行性、確定性、 和擁有足夠和擁有足夠 的情報。的情報。v 算法的空間復(fù)雜度是指算法的空間復(fù)雜度是指( ( ) ) A) A) 算法程序的長度算法程序的長度 B) B) 算法程序中的指令條數(shù)算法程序中的指令條數(shù) C) C) 算法程序所占

5、的存儲空間算法程序所占的存儲空間 D) D) 執(zhí)行過程中所需要的存儲空間執(zhí)行過程中所需要的存儲空間例題講解例題講解 有窮性有窮性16v 算法分析的目的是( ) A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 找出算法中輸入和輸出之間的關(guān)系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改進v 算法的工作量大小和實現(xiàn)算法所需的存儲單元多少分別稱 為算法的 【 1 1 】v 在計算機中，算法是指（ ） A) 加工方法 B) 解題方案的準(zhǔn)確而完整的描述 C) 排序方法 D) 查詢方法 【答案】【答案】: :時間復(fù)雜度和空間復(fù)雜度時間復(fù)雜度和空間復(fù)雜度例題講解例題講解17數(shù)據(jù)結(jié)構(gòu)研究的基本概念數(shù)據(jù)結(jié)構(gòu)研究

6、的基本概念 （1 1）、所處理的數(shù)據(jù)量大且具有一定的關(guān)系；）、所處理的數(shù)據(jù)量大且具有一定的關(guān)系； （2 2）、對其操作不再是單純的數(shù)值計算，而更多地）、對其操作不再是單純的數(shù)值計算，而更多地是需要對其進行組織、管理和檢索。是需要對其進行組織、管理和檢索。 對數(shù)據(jù)的討論不單單是數(shù)據(jù)本身，還要包括數(shù)據(jù)與對數(shù)據(jù)的討論不單單是數(shù)據(jù)本身，還要包括數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系。數(shù)據(jù)之間的關(guān)系。18數(shù)據(jù)結(jié)構(gòu)引例數(shù)據(jù)結(jié)構(gòu)引例 uP8P8例例1.3 1.3 數(shù)據(jù)元素在表中的排列順序?qū)Σ檎倚视袛?shù)據(jù)元素在表中的排列順序?qū)Σ檎倚视泻艽笥绊?。很大影響。uP9P9例例1.4 1.4 針對不同運算需求，可將數(shù)據(jù)組織成不同針對不

7、同運算需求，可將數(shù)據(jù)組織成不同形式，以方便該運算的執(zhí)行效率。形式，以方便該運算的執(zhí)行效率。樹形結(jié)構(gòu)樹形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面數(shù)據(jù)結(jié)構(gòu)的三個方面 1 1、數(shù)據(jù)的、數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 2 2、數(shù)據(jù)的、數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu) 3 3、數(shù)據(jù)的、數(shù)據(jù)的運算運算：檢索、排序、插入、刪除、修改等檢索、排序、插入、刪除、修改等。 A A線性結(jié)構(gòu)線性結(jié)構(gòu)B B非線性結(jié)構(gòu)非線性結(jié)構(gòu)A A順序存儲順序存儲 B B鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?線性表線性表棧棧隊隊圖形結(jié)構(gòu)圖形結(jié)構(gòu)(亦稱物理結(jié)構(gòu)亦稱物理結(jié)構(gòu))數(shù)據(jù)結(jié)構(gòu)的主要數(shù)據(jù)結(jié)構(gòu)的主要研究問題：研究問題：P7P71920 1 1、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)

8、構(gòu)是反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合。通俗的說，即帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。結(jié)構(gòu)是指數(shù)據(jù)元素之間的前后件（前驅(qū)、后繼）關(guān)系。 一個數(shù)據(jù)結(jié)構(gòu)應(yīng)該包含以下信息： 表示數(shù)據(jù)元素的信息 表示各數(shù)據(jù)元素之間的前后件關(guān)系 數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)據(jù)結(jié)構(gòu)。 一個數(shù)據(jù)結(jié)構(gòu)可以表示為一個數(shù)據(jù)結(jié)構(gòu)可以表示為B=(DB=(D，R)R)21數(shù)據(jù)結(jié)構(gòu)可描述為數(shù)據(jù)結(jié)構(gòu)可描述為 B=（D，R） 例例1：一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成：一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成B=（D，R） D=春，夏，秋，冬春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）（春，

9、夏），（夏，秋），（秋，冬） 例例2：家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成：家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成B=（D，R）D=父親，兒子，女兒父親，兒子，女兒 R=（父親，兒子），（父親，女兒）（父親，兒子），（父親，女兒）2223 2 2、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)存儲結(jié)構(gòu)數(shù)據(jù)存儲結(jié)構(gòu)是在計算機存儲空間中的存放形式，也稱為數(shù)據(jù)的物理結(jié)構(gòu)。 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)( (有有順序、鏈接、索引順序、鏈接、索引等等) )24一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成冬冬春春夏夏秋秋父親父親兒子兒子女兒女兒（ 概念：結(jié)點、前件、后件、根結(jié)點、葉子概

10、念：結(jié)點、前件、后件、根結(jié)點、葉子 ）25有且只有一個根節(jié)點有且只有一個根節(jié)點每個節(jié)點最多有一個前件，也最多只有每個節(jié)點最多有一個前件，也最多只有一個后件一個后件冬冬春春夏夏秋秋父親父親兒子兒子女兒女兒26例題講解例題講解v 數(shù)據(jù)處理的最小單位是數(shù)據(jù)處理的最小單位是( ( ) ) A)A)數(shù)據(jù)數(shù)據(jù) B)B)數(shù)據(jù)元素數(shù)據(jù)元素 C) C) 數(shù)據(jù)項數(shù)據(jù)項 D) D) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)v 數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進行的運算，以及對各種數(shù)據(jù)結(jié)構(gòu)進行的運算，以及( ( ) ) A) A) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的

11、存儲結(jié)構(gòu) B) B) 計算方法計算方法 C) C) 數(shù)據(jù)映象數(shù)據(jù)映象 D) D) 邏輯存儲邏輯存儲v 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 【4 4】 以及對數(shù)據(jù)的以及對數(shù)據(jù)的操作運算。操作運算?！敬鸢浮敬鸢浮课锢斫Y(jié)構(gòu)（或存儲結(jié)構(gòu)）物理結(jié)構(gòu)（或存儲結(jié)構(gòu)）學(xué)號學(xué)號姓名姓名出生日期出生日期性別性別001藍楓1991.3.5女002寶寶1990.8.1男 27線性表的基本概念線性表的基本概念 線性表線性表是最簡單、最常見的數(shù)據(jù)結(jié)構(gòu)?？梢允故亲詈唵?、最常見的數(shù)據(jù)結(jié)構(gòu)?？梢允褂庙樞虼鎯Y(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)。用順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)。非空線性表的非空線性表的結(jié)構(gòu)特征結(jié)構(gòu)特

12、征：有且只有一個根節(jié)點有且只有一個根節(jié)點有且只有一個終端節(jié)點有且只有一個終端節(jié)點除根節(jié)點與終端節(jié)點之外，其它所有節(jié)點有且只除根節(jié)點與終端節(jié)點之外，其它所有節(jié)點有且只有一個前件，也有且只有一個后件有一個前件，也有且只有一個后件節(jié)點個數(shù)節(jié)點個數(shù)n n為線性表的長度，為線性表的長度，n=0n=0為空表為空表28線性表線性表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)： 有以下兩個基本特點有以下兩個基本特點：線性表中所有元素所占的存儲空間是連續(xù)的線性表中所有元素所占的存儲空間是連續(xù)的線性表中各數(shù)據(jù)元素在存儲空間中按邏輯順序依次存放線性表中各數(shù)據(jù)元素在存儲空間中按邏輯順序依次存放主要運算有：插入、刪除、查找、排序、分解、合

13、并、復(fù)制、逆轉(zhuǎn)主要運算有：插入、刪除、查找、排序、分解、合并、復(fù)制、逆轉(zhuǎn)29 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu) 存儲地址存儲內(nèi)容元素n.元素i.元素2元素1Lo + mLo+(i-1)mLo+（n-1)m 線性表中所有元線性表中所有元素所占的存儲空間是素所占的存儲空間是連續(xù)的連續(xù)的 線性表中各數(shù)據(jù)線性表中各數(shù)據(jù)元素在存儲空間中按元素在存儲空間中按邏輯順序依次存放邏輯順序依次存放 前前后件兩后件兩個元素個元素在存儲在存儲空間中空間中是緊鄰是緊鄰的的30 31 32v 順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置 【1 1】 的存儲單元中。的

14、存儲單元中。v 長度為長度為n n的順序存儲線性表中，當(dāng)在任何位置上插入一個元的順序存儲線性表中，當(dāng)在任何位置上插入一個元 素概率都相等時，插入一個元素所需移動元素的平均個數(shù)素概率都相等時，插入一個元素所需移動元素的平均個數(shù) 為為【2 2】 。v 線性表線性表L=(a1,a2,a3,L=(a1,a2,a3,aiai，an)an)，下列說法正確的是（下列說法正確的是（ ） A) A) 每個元素都有一個直接前件和直接后件每個元素都有一個直接前件和直接后件 B) B) 線性表中至少要有一個元素線性表中至少要有一個元素 C) C) 表中諸元素的排列順序必須是由小到大或由大到小表中諸元素的排列順序必須是

15、由小到大或由大到小 D) D) 除第一個元素和最后一個元素外，其余每個元素都有一除第一個元素和最后一個元素外，其余每個元素都有一 個且只有一個直接前件和直接后件個且只有一個直接前件和直接后件【答案【答案】相鄰相鄰【答案【答案】 n/2 33例題講解例題講解v 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的( ( ) ) A) A) 存儲結(jié)構(gòu)存儲結(jié)構(gòu)B) B) 物理結(jié)構(gòu)物理結(jié)構(gòu) C) C) 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)D) D) 物理和存儲結(jié)構(gòu)物理和存儲結(jié)構(gòu) 下列敘述中，錯誤的是（下列敘述中，錯誤的是（ ） A) A) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān)數(shù)據(jù)的存儲結(jié)

16、構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) B) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān)數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) C) 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機中所占的空間不一定是連續(xù)的數(shù)據(jù)的存儲結(jié)構(gòu)在計算機中所占的空間不一定是連續(xù)的 D) D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)（一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)（P13P13） 數(shù)據(jù)的存儲結(jié)構(gòu)是指（數(shù)據(jù)的存儲結(jié)構(gòu)是指（ ） A A）數(shù)據(jù)所占的存儲空間數(shù)據(jù)所占的存儲空間 B B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示 C C）數(shù)據(jù)在計算機中的順序存儲方式數(shù)據(jù)在計算機中的順序存儲方式 D D）存儲在外存中的數(shù)據(jù)存儲在外存中的數(shù)據(jù) 3

17、4 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成將數(shù)據(jù)結(jié)構(gòu)分成( ( ) ) A) A) 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B) B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 【2 2】兩大類。兩大類。 當(dāng)線性表采用順序存儲結(jié)構(gòu)實現(xiàn)存儲時，其主要特點是當(dāng)線性表采用順序存儲結(jié)構(gòu)實現(xiàn)存儲時，其主要特點是【1】。 非線性結(jié)構(gòu)非線性結(jié)構(gòu)【答案【答案】邏輯結(jié)構(gòu)中相鄰

18、的結(jié)點在存儲結(jié)構(gòu)中仍相鄰。邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰。P16351 1、4 4、1 1 棧及其基本運算棧及其基本運算 入棧退棧 數(shù)據(jù)組織形式：數(shù)據(jù)組織形式： 先進后出（先進后出（FILOFILO）或后進先出）或后進先出（LIFOLIFO） 在棧的順序存儲空間在棧的順序存儲空間S(1:m)S(1:m)中，中， S(bottomS(bottom）為棧底元素，）為棧底元素， S(top)S(top)為棧頂元素，為棧頂元素， top=0top=0表示?？眨槐硎緱？?； top=mtop=m表示棧滿。表示棧滿。36Top=0表示空棧入棧運算：在棧頂位置插入一個新元素。首先將棧頂指針進一，然后將

19、新元素插入到棧頂指針指向的位置。入棧運算入棧運算 37Top=0表示空棧入棧運算：在棧頂位置插入一個新元素。首先將棧頂指針進一，然后將新元素插入到棧頂指針指向的位置。入棧運算入棧運算 38Top=0表示空棧入棧運算：在棧頂位置插入一個新元素。首先將棧頂指針進一，然后將新元素插入到棧頂指針指向的位置。入棧運算入棧運算 39Top=0表示空棧入棧運算：在棧頂位置插入一個新元素。首先將棧頂指針進一，然后將新元素插入到棧頂指針指向的位置。入棧運算入棧運算 40Top=0表示空棧入棧運算：在棧頂位置插入一個新元素。首先將棧頂指針進一，然后將新元素插入到棧頂指針指向的位置。top=m表示棧滿，不能再進行入

20、棧操作，否則“上溢”入棧運算入棧運算 41退棧運算退棧運算 退棧運算：取出棧頂元素并賦給一個指定變量。首先將棧頂元素賦給一個指定變量，然后將棧頂指針退一。a=“T”42退棧運算退棧運算 退棧運算：取出棧頂元素并賦給一個指定變量。首先將棧頂元素賦給一個指定變量，然后將棧頂指針退一。b=“S”43退棧運算退棧運算 退棧運算：取出棧頂元素并賦給一個指定變量。首先將棧頂元素賦給一個指定變量，然后將棧頂指針退一。當(dāng)top=0，表示?？?，不能退棧，否則產(chǎn)生?！跋乱纭卞e誤。44讀棧運算讀棧運算 讀棧運算：將棧頂元素并賦給一個指定變量。棧頂指針不會改變。 當(dāng)top=0，表示?？?，讀不到棧元素。45入隊 數(shù)據(jù)組

21、織形式：數(shù)據(jù)組織形式： 先進先出（先進先出（FIFOFIFO）或后進后出（）或后進后出（LILOLILO）退隊46入隊 數(shù)據(jù)組織形式：數(shù)據(jù)組織形式： 先進先出（先進先出（FIFOFIFO）或后進后出（）或后進后出（LILOLILO）退隊47 將隊列存儲空間的最后一個位置繞到將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。隊列循環(huán)使用。 隊尾指針隊尾指針rear指向隊列中的隊尾元素，指向隊列中的隊尾元素，排頭指針排頭指針front指向排頭元素的前一個位指向排頭元素的前一個位置置 實際應(yīng)用中使用實際應(yīng)用中使用48入隊運算：在循環(huán)

22、隊列的隊尾加入一個新元素。首先將隊尾指針進一，即rear=rear+1。（排頭指針front不變）入隊運算入隊運算 49入隊運算：在循環(huán)隊列的隊尾加入一個新元素。首先將隊尾指針進一，即rear=rear+1。（排頭指針front不變） 元素的個數(shù)元素的個數(shù)=rear-front=rear-front入隊運算入隊運算 50退隊運算：在排頭位置退出一個元素并賦值給指定的變量。首先將排頭指針進一，即front=front+1。（rear不變）。退隊運算退隊運算 51在一個容量為15的循環(huán)隊列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊列中有 個元素。352在一個容量為15的循環(huán)隊列中，

23、若頭指針front=9，尾指針rear=6，則該循環(huán)隊列中有 個元素。1253當(dāng)循環(huán)隊列滿時有front=rear；當(dāng)循環(huán)隊列空時也有front=rear；因此當(dāng)front=rear時，不能確定隊列滿或空。標(biāo)記s定義如下：s=0 表示隊列空s=1 表示隊列非空（并不代表滿）因此：隊列空條件為s=0，此時front=rear=m隊列滿條件為s=1且front=rear隊列滿時，不能進行入隊運算，否則“上溢”；隊列空時，不能進行退隊運算，否則“下溢”。54v棧和隊列的共同特點是（棧和隊列的共同特點是（ ） A)A)都是先進先出都是先進先出 B) B) 都是先進后出都是先進后出 C) C) 只允許在

24、端點處插入和刪除元素只允許在端點處插入和刪除元素 D) D) 沒有共同點沒有共同點v如果進棧序列為如果進棧序列為e1,e2,e3,e4e1,e2,e3,e4，則可能的出棧序列是（則可能的出棧序列是（ ） A) e3,e1,e4,e2 B) e4,e3,e2,e1 A) e3,e1,e4,e2 B) e4,e3,e2,e1 C) e3,e4,e1,e2 C) e3,e4,e1,e2 D) D) 任意順序任意順序 55v 棧底至棧頂依次存放元素棧底至棧頂依次存放元素A A、B B、C C、D D，在第五個元素在第五個元素E E 入棧前，棧中元素可以出棧，則出棧序列可能是（入棧前，棧中元素可以出棧，

25、則出棧序列可能是（ ） A) ABCEDA) ABCED B) DCBEA B) DCBEA C) DBCEA C) DBCEA D) CDABE D) CDABE v 棧通常采用的兩種存儲結(jié)構(gòu)是（棧通常采用的兩種存儲結(jié)構(gòu)是（ ） A) A) 順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B) B) 散列方式和索引方式散列方式和索引方式 C) C) 鏈表存儲結(jié)構(gòu)和數(shù)組鏈表存儲結(jié)構(gòu)和數(shù)組 D) D) 線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)v 棧和隊列通常采用的存儲結(jié)構(gòu)是棧和隊列通常采用的存儲結(jié)構(gòu)是 【1 1】。 【答案【答案】鏈?zhǔn)酱鎯晚樞虼鎯︽準(zhǔn)酱鎯晚樞虼鎯?56v

26、 下列關(guān)于棧的敘述中正確的是（下列關(guān)于棧的敘述中正確的是（ ）) )在棧中只能插入數(shù)據(jù)在棧中只能插入數(shù)據(jù) B B）在棧中只能刪除數(shù)據(jù)在棧中只能刪除數(shù)據(jù)C C）棧是先進先出的線性表棧是先進先出的線性表 D D）棧是后進先出的線性表棧是后進先出的線性表v 下列關(guān)于隊列的敘述中正確的是（下列關(guān)于隊列的敘述中正確的是（ ）在隊列中只能插入數(shù)據(jù)）在隊列中只能插入數(shù)據(jù) B B）在隊列中只能刪除數(shù)據(jù)在隊列中只能刪除數(shù)據(jù)C C）隊列是先進先出的線性表隊列是先進先出的線性表 D D）隊列是后進先出的線性表隊列是后進先出的線性表v 下列數(shù)據(jù)結(jié)構(gòu)中，按先進后出原則組織數(shù)據(jù)的是（下列數(shù)據(jù)結(jié)構(gòu)中，按先進后出原則組織數(shù)據(jù)

27、的是（ ） A) A) 線性鏈表線性鏈表 B) B) 棧棧 C) C) 循環(huán)鏈表循環(huán)鏈表 D) D) 順序表順序表 57 上溢上溢 581 1、5 5、1 1 線性鏈表的基本概念線性鏈表的基本概念 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表線性鏈表。 將存儲空間中的每一個存儲結(jié)點分為兩部分：v數(shù)據(jù)域：用于存儲數(shù)據(jù)元素的值；v指針域：用于存放下一個數(shù)據(jù)元素的存儲序號（即存儲結(jié)點的地址），也就是指向后件結(jié)點. HEADHEAD591、比順序存儲結(jié)構(gòu)的存儲密度小 (每個節(jié)點都由數(shù)據(jù)域和指針域組成，所以相同空間內(nèi)假設(shè)全存滿的話順序比鏈?zhǔn)酱鎯Ω?。2、邏輯上相鄰的節(jié)點物理上不必相鄰。3、插入、刪除靈活 (不必移

28、動節(jié)點，只要改變節(jié)點中的指針)。4、查找結(jié)點時鏈?zhǔn)酱鎯σ软樞虼鎯β?鏈接存儲結(jié)構(gòu)特點：鏈接存儲結(jié)構(gòu)特點：60 指向線性表中第一個結(jié)點的指針HEAD稱為頭指針。 當(dāng)HEAD=NULL（或0）時稱為空表。 對于線性鏈表，可以從頭指針開始，沿著各個結(jié)點的指針掃描到鏈表中的所有結(jié)點。線性鏈表的邏輯結(jié)構(gòu)線性鏈表的邏輯結(jié)構(gòu)HEADHEAD61 線性單鏈表 線性鏈表的分類線性鏈表的分類HEADHEADnulla1a2annull 雙向鏈表 HEADHEAD6263線性鏈表的運算主要有以下幾個：線性鏈表的運算主要有以下幾個： 在線性鏈表中包含指定元素的結(jié)點之前在線性鏈表中包含指定元素的結(jié)點之前 插入插入一

29、個新元素。一個新元素。 在線性鏈表中在線性鏈表中刪除刪除包含指定元素的結(jié)點。包含指定元素的結(jié)點。 將兩個線性鏈表按要求將兩個線性鏈表按要求合并合并成一個線性成一個線性 鏈表。鏈表。64 線性鏈表的插入線性鏈表的插入是指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下是指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性表中插入一個新元素。的線性表中插入一個新元素。 為了要在線性鏈表中插入一個新元素，為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個新結(jié)點，然后將存首先要給該元素分配一個新結(jié)點，然后將存放新元素值的結(jié)點鏈接到線性鏈表中指定的放新元素值的結(jié)點鏈接到線性鏈表中指定的位置。位置。65 線性鏈表的刪除線性鏈表的刪除指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的指在鏈

30、式存儲結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點。線性表中刪除包含指定元素的結(jié)點。 為了在線性鏈表中刪除包含指定元素的為了在線性鏈表中刪除包含指定元素的結(jié)點，首先要在線性鏈表中找到這個結(jié)點，結(jié)點，首先要在線性鏈表中找到這個結(jié)點，然后將要刪除結(jié)點放回到可利用棧。然后將要刪除結(jié)點放回到可利用棧。66p pb b67 循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下兩個特點：循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下兩個特點： 增加一個增加一個表頭結(jié)點表頭結(jié)點，頭指針指向表頭結(jié)點。，頭指針指向表頭結(jié)點。 最后一個結(jié)點的指針域不空最后一個結(jié)點的指針域不空，指向表頭結(jié)點，所有結(jié)，指向表頭結(jié)點，所有

31、結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。點的指針構(gòu)成了一個環(huán)狀鏈。 循環(huán)鏈表的示意圖循環(huán)鏈表的示意圖68 在實際應(yīng)用中，循環(huán)鏈表與線性單鏈表相在實際應(yīng)用中，循環(huán)鏈表與線性單鏈表相比主要有以下比主要有以下兩個方面的優(yōu)點兩個方面的優(yōu)點： 在循環(huán)鏈表中，只要指出表中任何一個結(jié)點在循環(huán)鏈表中，只要指出表中任何一個結(jié)點 的位置，就可以從它出發(fā)訪問到表中其他所的位置，就可以從它出發(fā)訪問到表中其他所 有的結(jié)點。有的結(jié)點。 由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，因由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，因 此，在任何情況下，循環(huán)鏈表中至少有一個此，在任何情況下，循環(huán)鏈表中至少有一個 結(jié)點存在，從而使空表與非空表的運算統(tǒng)一。結(jié)點

32、存在，從而使空表與非空表的運算統(tǒng)一。69 存儲結(jié)構(gòu)存儲結(jié)構(gòu)70鏈表不具有的特點是（鏈表不具有的特點是（ ） A) A) 不必事先估計存儲空間不必事先估計存儲空間 B) B) 可隨機訪問任一元素可隨機訪問任一元素 C) C) 插入刪除不需要移動元素插入刪除不需要移動元素 D) D) 所需空間與線性表長度成正比所需空間與線性表長度成正比 線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是( ( ) ) A) A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) B) 隨機存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)隨機存取的存

33、儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) C) 隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu)隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu) D) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu) 71 前面我們討論的線性表，棧、隊列等都是線性結(jié)構(gòu)。而前面我們討論的線性表，棧、隊列等都是線性結(jié)構(gòu)。而樹樹是一種是一種非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu)。在樹這種圖形結(jié)構(gòu)中，結(jié)點間有。在樹這種圖形結(jié)構(gòu)中，結(jié)點間有明明顯的層次結(jié)構(gòu)顯的層次結(jié)構(gòu)關(guān)系。關(guān)系。 A C G T2D H I T3J M B E L KT1 F72v關(guān)于樹的基本術(shù)語：關(guān)于樹的基本術(shù)語： 父結(jié)點：每一個結(jié)點只有一個前件，稱為（

34、該結(jié)點的）父結(jié)點：每一個結(jié)點只有一個前件，稱為（該結(jié)點的）父結(jié)點父結(jié)點。根結(jié)點：沒有前件的結(jié)點只有一個，稱為根結(jié)點：沒有前件的結(jié)點只有一個，稱為根結(jié)點根結(jié)點，簡稱為樹的，簡稱為樹的根。根。子結(jié)點：每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點：每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點子結(jié)點。葉子結(jié)點：沒有后件的結(jié)點稱為葉子結(jié)點：沒有后件的結(jié)點稱為葉子結(jié)點葉子結(jié)點。結(jié)點的度：一個結(jié)點擁有后件的個數(shù)稱為結(jié)點的度：一個結(jié)點擁有后件的個數(shù)稱為該結(jié)點的度該結(jié)點的度。（葉子。（葉子結(jié)點的度為結(jié)點的度為0 0）。）。樹的度：在樹中，所有結(jié)點中最大的度稱為樹的樹的度：在樹中，所有結(jié)點中最大的度稱為樹的度度。

35、樹的深度：樹的最大層次稱為樹的深度：樹的最大層次稱為樹的深度樹的深度。子樹：以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的子樹：以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的子樹子樹。73FCEADGBHPK根結(jié)點根結(jié)點葉子結(jié)點葉子結(jié)點度為度為3度為度為2度為度為1樹的度為樹的度為3樹的深度為樹的深度為47475 二叉樹二叉樹是一種很有用的非線性結(jié)構(gòu)。是一種很有用的非線性結(jié)構(gòu)。 二叉樹具有以下兩個特點：二叉樹具有以下兩個特點：（1 1）非空二叉樹只有一個根結(jié)點；）非空二叉樹只有一個根結(jié)點；（2 2）每一個結(jié)點最多有兩棵子樹，且分別）每一個結(jié)點最多有兩棵子樹，且分別 稱為該結(jié)點的左子樹與右子樹。稱為

36、該結(jié)點的左子樹與右子樹。 二叉樹每個結(jié)點最大的度為二叉樹每個結(jié)點最大的度為2 2，且子樹有左，且子樹有左右之分，次序不能顛倒。右之分，次序不能顛倒。7676 空二叉樹空二叉樹 僅有僅有根結(jié)點根結(jié)點 右子樹右子樹為空為空 左子樹左子樹為空為空左右子樹左右子樹均非空均非空兩棵不同的二叉數(shù)兩棵不同的二叉數(shù)77性質(zhì)性質(zhì)1 1：二叉樹的第：二叉樹的第k k層上至多有層上至多有2 2 k-1k-1（k k 1 1）個結(jié)點個結(jié)點423167891011121314155第三層上(k=3)，有2k-1=4個節(jié)點。第四層上(k=4)，有24-1=8個節(jié)點。78性質(zhì)性質(zhì)2 2：深度為：深度為mm的二叉樹中至多含有

37、的二叉樹中至多含有2 2m-1m-1個結(jié)點個結(jié)點423167891011121314155此樹的深度此樹的深度m=4m=4，共有共有2 24 4-1 -1個個節(jié)點。節(jié)點。79性質(zhì)性質(zhì)3 3：在任意一棵二叉樹中，度為：在任意一棵二叉樹中，度為0 0的結(jié)點的結(jié)點 （即葉子結(jié)點）總是比度為（即葉子結(jié)點）總是比度為2 2的結(jié)點多的結(jié)點多 一個。一個。例子例子1 1：某二叉樹中度為：某二叉樹中度為2 2的結(jié)點有的結(jié)點有1818個，則個，則 該二叉樹中有該二叉樹中有 個葉子結(jié)點。個葉子結(jié)點。1980性質(zhì)性質(zhì)4 4：具有：具有n n個結(jié)點的二叉樹，其深度至少個結(jié)點的二叉樹，其深度至少為為loglog2 2n

38、+1 n+1 ，其中，其中 loglog2 2n n 表示表示loglog2 2n n取取 的整數(shù)部分。的整數(shù)部分。 81 滿二叉樹滿二叉樹是指除最后一層外，每一層上的所是指除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。有結(jié)點都有兩個子結(jié)點。 423167891011121314155231423167582 完全二叉樹完全二叉樹是指：除最后一層外，每一層上是指：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。右邊的若干結(jié)點。 4231678910 11125 非完全二叉樹非完全二叉樹4231678910 11125 完全

39、二叉樹完全二叉樹83423165 深度為深度為3的完全二叉樹的完全二叉樹42315 深度為深度為4的完全二叉樹的完全二叉樹4231678910 111254231678584注意：注意：滿二叉樹是完全二叉樹，完全二叉樹滿二叉樹是完全二叉樹，完全二叉樹一般不是滿二叉樹。一般不是滿二叉樹。4231678910111213141554231678910 11125 完全二叉樹完全二叉樹滿二叉樹滿二叉樹85性質(zhì)性質(zhì)5 5： 具有具有n n個結(jié)點的個結(jié)點的完全完全二叉樹的深度為二叉樹的深度為loglog2 2n+1n+1。86性質(zhì)性質(zhì)6 6：設(shè)完全二叉樹有n個結(jié)點。如果從根結(jié)點開始，按層序（每一層從左到

40、右）用自然數(shù)1,2,n給結(jié)點進行編號，則對于編號為k(k=1,2,n)的結(jié)點有如下結(jié)論：若若k=1k=1，則該結(jié)點為根結(jié)點，其沒有父結(jié)點；若，則該結(jié)點為根結(jié)點，其沒有父結(jié)點；若k1k1，則該，則該結(jié)點的父結(jié)點編號為結(jié)點的父結(jié)點編號為INT(k/2)INT(k/2)。若若2k n2k n，則編號為，則編號為k k的結(jié)點的左子結(jié)點編號為的結(jié)點的左子結(jié)點編號為2k2k；否則該；否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。若若2k+1 n2k+1 n，則編號為，則編號為k k的結(jié)點的右子結(jié)點編號為的結(jié)點的右子結(jié)點編號為2k+12k+1；否；否則該結(jié)點無右子結(jié)點。則

41、該結(jié)點無右子結(jié)點。87性質(zhì)性質(zhì)6 6：示例示例 n=12n=12簡單記憶：簡單記憶：父結(jié)點父結(jié)點=int=int（k/2k/2）左子結(jié)點左子結(jié)點=2k=2k右子結(jié)點右子結(jié)點=2k+1=2k11125 完全二叉樹完全二叉樹88 在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為（ ） A) 32 B) 31 C) 16 D) 15 89n在計算機中，二叉樹在計算機中，二叉樹通常通常采用采用鏈?zhǔn)芥準(zhǔn)酱鎯Y(jié)構(gòu)。存儲結(jié)構(gòu)。n每個存儲結(jié)點由兩部分組成：每個存儲結(jié)點由兩部分組成：數(shù)據(jù)域數(shù)據(jù)域和和指針域指針域。其中其中指針域有兩個指針域有兩個：左指針域和右指針域。：左指針域和右指針域。二叉樹

42、存儲結(jié)點的結(jié)構(gòu)n對于滿二叉樹與完全二叉樹來說，可以按層序進對于滿二叉樹與完全二叉樹來說，可以按層序進行順序存儲，但順序存儲結(jié)構(gòu)對于一般的二叉樹不行順序存儲，但順序存儲結(jié)構(gòu)對于一般的二叉樹不適用，通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)適用，通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)90 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。 二叉樹的遍歷可以分為三種：前序前序遍歷、中序中序遍歷、后序后序遍歷。 總原則：先左后右總原則：先左后右 前序：前序： DLRDLR（即即根根左右）左右） 中序：中序： LDRLDR（即左即左根根右）右） 后序：后序： LRDLRD（即左右即左右根根）91FCEADGBHP92FCEADGBHPF93FC

43、EADGBHPFC94FCEADGBHPFCA95FCEADGBHPFCAD96FCEADGBHPFCADB97FCEADGBHPFCADBE98FCEADGBHPFCADBEG99FCEADGBHPFCADBEGH100FCEADGBHPFCADBEGHP101CEFCEADGBHPFCADBEGHPACBFDHEGPABDH GPF1021 1、設(shè)一棵二叉樹的中序遍歷結(jié)果為、設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC,DBEAFC, 前序遍歷結(jié)果為前序遍歷結(jié)果為ABDECFABDECF，則后序遍歷結(jié)則后序遍歷結(jié) 果為：果為：2 2、已知一棵二叉樹前序遍歷和中序遍歷分別、已知一棵二叉樹前序遍歷

44、和中序遍歷分別 為為ABDEGCFHABDEGCFH和和DBGEACHFDBGEACHF，則該二叉樹則該二叉樹 的后序遍歷為（的后序遍歷為（ ） A) GEDHFBCA A) GEDHFBCA B) DGEBHFCA B) DGEBHFCA C) ABCDEFGH C) ABCDEFGH D) ACBFEDHG D) ACBFEDHG DEBFCADEBFCA 103v 具有具有3 3個結(jié)點的二叉樹有（個結(jié)點的二叉樹有（ ） A) 2A) 2種形態(tài)種形態(tài) B) 4B) 4種形態(tài)種形態(tài) C) 7C) 7種形態(tài)種形態(tài) D) 5D) 5種形態(tài)種形態(tài) v 設(shè)有下列二叉樹：設(shè)有下列二叉樹： 對此二叉樹前

45、序遍歷的結(jié)果為（對此二叉樹前序遍歷的結(jié)果為（ ） A) ZBTTCPXA B) ATBZXCTP A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT C) ZBTACTXP D) ATBZXCPT 104數(shù)據(jù)結(jié)構(gòu)的三個方面數(shù)據(jù)結(jié)構(gòu)的三個方面 1 1、數(shù)據(jù)的、數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 2 2、數(shù)據(jù)的、數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu) 3 3、數(shù)據(jù)的、數(shù)據(jù)的運算運算：檢索、排序、插入、刪除、修改等檢索、排序、插入、刪除、修改等。 A A線性結(jié)構(gòu)線性結(jié)構(gòu)B B非線性結(jié)構(gòu)非線性結(jié)構(gòu)A A順序存儲順序存儲 B B鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?線性表線性表棧棧隊隊圖形結(jié)構(gòu)圖形結(jié)構(gòu)(亦稱

46、物理結(jié)構(gòu)亦稱物理結(jié)構(gòu))樹形結(jié)構(gòu)樹形結(jié)構(gòu)105 順序查找順序查找又稱又稱順序搜索順序搜索。順序查找一般。順序查找一般是指在線性表表中查找指定元素。是指在線性表表中查找指定元素。 基本思想：從表中第一條記錄開始，逐基本思想：從表中第一條記錄開始，逐個進行記錄的關(guān)鍵字和給定值的比較，查個進行記錄的關(guān)鍵字和給定值的比較，查到所要找的元素為止。到所要找的元素為止。u最壞情況：查找元素在最后或沒有最壞情況：查找元素在最后或沒有u最好情況：查找元素在最前最好情況：查找元素在最前u平均情況：與線性表中一半元素比較平均情況：與線性表中一半元素比較106 下列兩種情況下只能采用順序查找：下列兩種情況下只能采用順序

47、查找：n（1 1）如果線性表是無序表。）如果線性表是無序表。n（2 2）有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)）有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。構(gòu)，也只能用順序查找。107 二分查找二分查找又稱又稱折半查找折半查找。 只適用于只適用于順序存儲的有序表順序存儲的有序表，即各記錄的，即各記錄的次序是按其關(guān)鍵字的大小順序（以下假定按次序是按其關(guān)鍵字的大小順序（以下假定按從小到大的順序）排列的表。從小到大的順序）排列的表。 108例：查找元素22過程： 109 二分查找的思想：先確定待查找記錄所在二分查找的思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確的范圍，然后逐步縮小

48、范圍，直到找到或確認(rèn)找不到該記錄為止。認(rèn)找不到該記錄為止。 特點特點：比順序查找方法效率高。最壞的：比順序查找方法效率高。最壞的情況下，需要比較情況下，需要比較 loglog2 2n n次。次。110 排序排序排序是指將一個無序序列整理成按值排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。非遞減順序排列的有序序列。 111 交換類排序交換類排序：借助數(shù)據(jù)元素之間的互借助數(shù)據(jù)元素之間的互相交換進行排序的方法相交換進行排序的方法交換類排序法：交換類排序法：冒泡排序法冒泡排序法：需要比較的次數(shù)為：需要比較的次數(shù)為n(n-1)/2n(n-1)/2快速排序法快速排序法：是對冒泡排序的改進，是：是對冒泡排序的改進，是目目 前內(nèi)部排序中速度最快的一種。前內(nèi)部排序中速度最快的一種。 11211311446464646115 插入類排序：將無序序列中的各元素