二級(jí)ACCESS筆試之?dāng)?shù)據(jù)結(jié)構(gòu)基礎(chǔ)

1、二級(jí)公共基礎(chǔ)知識(shí)二級(jí)公共基礎(chǔ)知識(shí) 第一章第一章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 內(nèi)容提要內(nèi)容提要 n1.1.算法的基本概念算法的基本概念; ;算法復(fù)雜度的概念和意義算法復(fù)雜度的概念和意義( (時(shí)間復(fù)雜度時(shí)間復(fù)雜度 與空間復(fù)雜度與空間復(fù)雜度) )。 n2.2.數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)的定義; ;數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu); ;數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 的圖形表示的圖形表示; ;線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。 n3.3.線性表的定義線性表的定義; ;線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除 運(yùn)算。運(yùn)算。 n4.4.棧和隊(duì)列的定義棧和隊(duì)列的

2、定義; ;棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn) 算。算。 n5.5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。 n6.6.樹的基本概念樹的基本概念; ;二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)二叉樹的定義及其存儲(chǔ)結(jié)構(gòu); ;二叉樹的前二叉樹的前 序、中序和后序遍歷。序、中序和后序遍歷。 n7.7.順序查找與二分法查找算法順序查找與二分法查找算法; ;基本排序算法基本排序算法( (交換類排序，交換類排序， 選擇類排序，插入類排序選擇類排序，插入類排序) )。 1.1 1.1 算法算法 1.1.1 1.1.1 算法的基本概念算法的

3、基本概念 n算法是解題方案的準(zhǔn)確而完整的描述，它不等于程序，也算法是解題方案的準(zhǔn)確而完整的描述，它不等于程序，也 不等計(jì)算方法。不等計(jì)算方法。 n1 1算法的基本特征算法的基本特征 n可行性(effectiveness) n確定性(definiteness) n有窮性(finiteness) n擁有足夠的情報(bào) n2 2算法的基本要素算法的基本要素 n算法中對(duì)數(shù)據(jù)的運(yùn)算和操作 n算術(shù)運(yùn)算:包括加、減、乘、除等） n邏輯運(yùn)算:包括“與”、“或”、“非”等運(yùn)算） n關(guān)系運(yùn)算:包括“大于”、“小于”、“等于”、“不等于”等） n數(shù)據(jù)傳輸:包括賦值、輸入、輸出等操作 n算法的控制結(jié)構(gòu) 1.1.1 1.1

4、.1 算法的基本概念算法的基本概念 n3 3算法設(shè)計(jì)的基本方法算法設(shè)計(jì)的基本方法 n列舉法:列舉所有可能的情況 n歸納法：特殊-一般關(guān)系 n遞推：從初始條件逐次推出中間結(jié)果和最后結(jié)果 n遞歸：逐層分解，大問題變小問題 n減半遞推技術(shù):重復(fù)減半 n回溯法 1.1.2 1.1.2 算法復(fù)雜度算法復(fù)雜度 n算法復(fù)雜度：時(shí)間復(fù)雜度、空間復(fù)雜度算法復(fù)雜度：時(shí)間復(fù)雜度、空間復(fù)雜度 n1 1算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度 n執(zhí)行算法所需要的計(jì)算工作量，即所執(zhí)行的基 本運(yùn)算次數(shù)。 n與下列因素?zé)o關(guān)： n書寫算法的程序設(shè)計(jì)語言 n編譯產(chǎn)生的機(jī)器語言，代碼質(zhì)量 n機(jī)器執(zhí)行指令的速度 n與問題的規(guī)模有關(guān) 1.1.

5、2 1.1.2 算法復(fù)雜度算法復(fù)雜度 n問題的規(guī)模函數(shù)問題的規(guī)模函數(shù) 算法的工作量=f(n) n算法中基本操作重復(fù)執(zhí)行的頻率算法中基本操作重復(fù)執(zhí)行的頻率T(n)T(n)，是問題規(guī)，是問題規(guī) 模模n n的某個(gè)函數(shù)的某個(gè)函數(shù)f(n)f(n)，記作：，記作： T(n)=O(f(n) n記號(hào)“O”讀作“大O”。表示隨問題規(guī)模n的增加，算法 執(zhí)行時(shí)間的增長率和f(n)相應(yīng)增加。 n常見算法復(fù)雜度：常見算法復(fù)雜度： nO(1)：常數(shù)階 O(n)：作線性階 O(n2)：平方階 nO(n3)：立方階 O(logn)：對(duì)數(shù)階 O(2n)：指數(shù)階 1.1.2 1.1.2 算法復(fù)雜度算法復(fù)雜度 nn nn n矩陣相

6、乘算法：矩陣相乘算法： n時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(nO(n3 3) )。 1.1.2 1.1.2 算法復(fù)雜度算法復(fù)雜度 n分析算法的工作量兩種方法：分析算法的工作量兩種方法： n平均性態(tài) n最壞情況復(fù)雜性 1.1.2 1.1.2 算法復(fù)雜度算法復(fù)雜度 n2算法的空間復(fù)雜度 n算法執(zhí)行過程中所需的內(nèi)存空間 n存儲(chǔ)量包括以下三部分 n算法程序所占的空間 n輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間 n算法執(zhí)行過程中所要的額外空間 n算法空間復(fù)雜度可定義為： S(n)=O(f(n) n原地工作(in place)的算法：記作O(1) n壓縮存儲(chǔ)技術(shù) 1.2 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 1.2

7、.1 1.2.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) n1 1數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 n數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)之間的邏輯關(guān)系的結(jié)構(gòu)。 n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在計(jì)算機(jī)的存儲(chǔ)形式。 n對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算 n2 2研究數(shù)據(jù)結(jié)構(gòu)目的研究數(shù)據(jù)結(jié)構(gòu)目的 n提高數(shù)據(jù)處理的速度 n盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計(jì)算機(jī)存 儲(chǔ)空間 1.2.1 1.2.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) 1數(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ì) 樹形結(jié)構(gòu) 圖形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面 1.

8、2.1 1.2.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) n3數(shù)據(jù)結(jié)構(gòu)的定義 n相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合 n數(shù)據(jù)元素之間的關(guān)系可以用前后件關(guān)系來描述 n一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面信息： n表示數(shù)據(jù)元素的信息 n表示各數(shù)據(jù)元素之間的前后件關(guān)系（即邏輯關(guān)系） 1.2.1 1.2.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) n4 4數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) n對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描述 n只抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系，與計(jì) 算機(jī)中的存儲(chǔ)無關(guān) n兩個(gè)要素： n數(shù)據(jù)元素的集合，通常記為D； n前后件關(guān)系，通常記為R n一個(gè)數(shù)據(jù)結(jié)構(gòu)B可以表示為： B=B=（D D，R R） 1.2.1 1.2.1 什么是

9、數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) n5 5數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) n數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形 式 n常用的存儲(chǔ)結(jié)構(gòu)： n順序 n鏈?zhǔn)?n索引 n一種數(shù)據(jù)結(jié)構(gòu)可根據(jù)需要采用不同的存儲(chǔ)結(jié)構(gòu)。 采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不 同 1.2.2 1.2.2 數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)構(gòu)的圖形表示 n數(shù)據(jù)結(jié)點(diǎn)：用方框表示數(shù)據(jù)結(jié)點(diǎn)：用方框表示 n根結(jié)點(diǎn)（沒有前件）、終端結(jié)點(diǎn)（沒有后件）、內(nèi)部 結(jié)點(diǎn) n前后件關(guān)系：用有向線段表示前后件關(guān)系：用有向線段表示 n基本運(yùn)算：基本運(yùn)算： n插入、 刪除運(yùn)算 n查找、分類、合并、分解、復(fù)制、修改、 1.2.3 1.2.3 線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)

10、與非線性結(jié)構(gòu) n空的數(shù)據(jù)結(jié)構(gòu)：空的數(shù)據(jù)結(jié)構(gòu)：一個(gè)數(shù)據(jù)元素都沒有。線性結(jié)構(gòu)和 非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。 n線性結(jié)構(gòu)線性結(jié)構(gòu) n如果一個(gè)非空數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件： n有且只有一個(gè)根結(jié)點(diǎn)； n每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 n常見的線性結(jié)構(gòu)有：線性表、棧與隊(duì)列、線性鏈表 n非線性結(jié)構(gòu)非線性結(jié)構(gòu) n如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu) n常見的非線性結(jié)構(gòu)有：樹、二叉樹、圖 1.3 1.3 線性表及其順序存儲(chǔ)結(jié)構(gòu)線性表及其順序存儲(chǔ)結(jié)構(gòu) 1.3.1 1.3.1 線性表的基本概念線性表的基本概念 n線性表：由線性表：由n n(n0)(n0)個(gè)個(gè)相同類型數(shù)據(jù)元素相同類型數(shù)據(jù)元素構(gòu)成的有構(gòu)成的

11、有 限序列：限序列： nn n定義為線性表的表長；定義為線性表的表長；n n=0 =0 時(shí)的線性表被稱為空時(shí)的線性表被稱為空 表。稱表。稱i i為在線性表中的位序。為在線性表中的位序。 n例如：例如： n英文大寫字母表 （A，B，C，D，E，F(xiàn)，X，Y，Z） n同一花色的13張撲克牌 n(2,3,4,5,6,7,8,9,10,J,Q,K,A) ),( 21ni aaaa 1.3.1 1.3.1 線性表的基本概念線性表的基本概念 n線性表的結(jié)構(gòu)特征線性表的結(jié)構(gòu)特征 n數(shù)據(jù)元素在表中的位置由序號(hào)決定，數(shù)據(jù)元素 之間的相對(duì)位置是線性的； n對(duì)于一個(gè)非空線性表，有且只有一個(gè)根結(jié)點(diǎn)a1， 它無前件，有且

12、只有一個(gè)終端結(jié)點(diǎn)an，它無后 件，除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有 且只有一個(gè)前件，也有且只有一個(gè)后件。 n線性表的存儲(chǔ)結(jié)構(gòu)線性表的存儲(chǔ)結(jié)構(gòu) n順序存儲(chǔ) n鏈?zhǔn)酱鎯?chǔ) 1.3.2 1.3.2 線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu) n兩個(gè)基本特點(diǎn)：兩個(gè)基本特點(diǎn)： n線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的。 n線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。 n存儲(chǔ)示意圖存儲(chǔ)示意圖 kiaLocaLoc i *) 1()()( 1 1.3.3 1.3.3 順序表的插入運(yùn)算順序表的插入運(yùn)算 1.3.4 1.3.4 順序表的刪除運(yùn)算順序表的刪除運(yùn)算 順序表的插入和刪除分析順序表的插入和刪除

13、分析 n插入算法的分析插入算法的分析 n假設(shè)線性表中含有n個(gè)數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定在n+1個(gè)位 置上插入元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為： n刪除算法的分析刪除算法的分析 n在進(jìn)行刪除操作時(shí)，若假定刪除每個(gè)元素的可能性均等，則平均移動(dòng)元 素的個(gè)數(shù)為： n分析結(jié)論分析結(jié)論 n順序存儲(chǔ)結(jié)構(gòu)表示的線性表，在做插入或刪除操作時(shí)，平均需要移動(dòng)大 約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對(duì)其做插 入或刪除操作時(shí)，這一點(diǎn)需要值得考慮 n i idl n inp n E 1 2 1 )( 1 1 1 2 ) 1( 1 1 n i iis n inp n E 1.4 1.4 棧

14、和隊(duì)列棧和隊(duì)列 1.4.1 1.4.1 棧及其基本運(yùn)算棧及其基本運(yùn)算 n1 1棧的定義棧的定義 n棧（stack）：一種只允許在表的一端進(jìn)行插入或刪除 操作的特殊的線性表 n棧頂(top) ：允許進(jìn)行插入與刪除操作的一端 n棧底(bottom)：不允許插入與刪除操作的另一端 n先進(jìn)后出（FILO）或后進(jìn)先出(LIFO)的線性表 1.4.1 1.4.1 棧及其基本運(yùn)算棧及其基本運(yùn)算 n2棧的順序存儲(chǔ)及其運(yùn)算 ntop=0：?？?top=m：棧滿 n棧的基本運(yùn)算 n入棧運(yùn)算 n退棧運(yùn)算 n讀棧頂元素 1.4.2 1.4.2 隊(duì)列及其基本運(yùn)算隊(duì)列及其基本運(yùn)算 n1 1隊(duì)列的定義隊(duì)列的定義 n限定只能

15、在表的一端進(jìn)行插入和在另一端進(jìn)行刪除操作的線性表 n隊(duì)尾(rear)：允許插入的一端，指向插入的最后一個(gè)元素 n隊(duì)頭(front)：允許刪除的另一端，指向隊(duì)頭元素的前一個(gè)位置 n先進(jìn)先出（FIFO）表或后進(jìn)后出（LILO）線性表 n基本操作 n入隊(duì)運(yùn)算：往隊(duì)列的隊(duì)尾插入一個(gè)元素，隊(duì)尾指針rear的變化?！吧?溢” n退隊(duì)運(yùn)算：從隊(duì)列的排頭刪除一個(gè)元素，隊(duì)頭指針front的變化 1.4.2 1.4.2 隊(duì)列及其基本運(yùn)算隊(duì)列及其基本運(yùn)算 n2 2循環(huán)隊(duì)列及其運(yùn)算循環(huán)隊(duì)列及其運(yùn)算 n隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán) 狀空間，供隊(duì)列循環(huán)使用 n入隊(duì)運(yùn)算 ：隊(duì)尾指針加1，并當(dāng)re

16、ar=m+1時(shí)置rear=1 n出隊(duì)運(yùn)算：隊(duì)頭指針加1，并當(dāng)front=m+1時(shí)置front=1?！跋乱纭?1.5 1.5 線性鏈表線性鏈表 1.5.1 1.5.1 線性鏈表的基本概念線性鏈表的基本概念 n1 1線性表順序存儲(chǔ)的缺點(diǎn)線性表順序存儲(chǔ)的缺點(diǎn) n插入或刪除的運(yùn)算效率很低。在順序存儲(chǔ)的線 性表中，插入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量 的數(shù)據(jù)元素。 n線性表的順序存儲(chǔ)結(jié)構(gòu)下，線性表的存儲(chǔ)空間 不便于擴(kuò)充。 n線性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間的動(dòng) 態(tài)分配。 1.5.1 1.5.1 線性鏈表的基本概念線性鏈表的基本概念 n2 2線性鏈表線性鏈表 n線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) n物理存儲(chǔ)單元上非連續(xù)

17、、非順序的存儲(chǔ)結(jié)構(gòu)， 數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接 來實(shí)現(xiàn)的 n每個(gè)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域和指針域 n數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)的值數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)的值 n指針域：存放下一個(gè)元素的存儲(chǔ)序號(hào)（即指針域：存放下一個(gè)元素的存儲(chǔ)序號(hào)（即 存儲(chǔ)點(diǎn)的地址）存儲(chǔ)點(diǎn)的地址） n用專門的一個(gè)指針用專門的一個(gè)指針headhead指向線性表的一個(gè)指向線性表的一個(gè) 元素的結(jié)點(diǎn)，最后一個(gè)元素沒有后件，指元素的結(jié)點(diǎn)，最后一個(gè)元素沒有后件，指 針域?yàn)榭眨ㄡ樣驗(yàn)榭眨∟ULLNULL），表示鏈表終止。），表示鏈表終止。 nHead=NULLHead=NULL時(shí)為空表。時(shí)為空表。 1.5.1 1.5.1 線性鏈表的基本概念線

18、性鏈表的基本概念 n雙向鏈表：每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針雙向鏈表：每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針 n左指針：指向其前件結(jié)點(diǎn) n右指針：指向其后件結(jié)點(diǎn) 1.5.2 1.5.2 線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算 n插入插入 n刪除刪除 n合并合并 n分解分解 n逆轉(zhuǎn)逆轉(zhuǎn) n復(fù)制復(fù)制 n排序排序 n查找查找 1.5.2 1.5.2 線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算 n1 1在線性鏈表中查找指定元素在線性鏈表中查找指定元素 n鏈表不是隨機(jī)存取結(jié)構(gòu) n從鏈表的頭指針出發(fā)，順著鏈域next逐個(gè)結(jié)點(diǎn) 往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止 n2 2線性鏈表的插入線性鏈表的插入 1.5.2 1.5.2 線性鏈表的基本運(yùn)算

19、線性鏈表的基本運(yùn)算 n3 3線性鏈表的刪除線性鏈表的刪除 n與順序存儲(chǔ)相比，鏈表的優(yōu)點(diǎn)有：與順序存儲(chǔ)相比，鏈表的優(yōu)點(diǎn)有： n插入和刪除元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只 需要修改指針即可 1.5.3 1.5.3 棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) n1棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈棧 1.5.3 1.5.3 棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) n2隊(duì)列鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈隊(duì)列 1.5.4 1.5.4 循環(huán)鏈表及其基本運(yùn)算循環(huán)鏈表及其基本運(yùn)算 n循環(huán)鏈表特點(diǎn)：循環(huán)鏈表特點(diǎn)： n在鏈表中增加了一個(gè)表頭結(jié)點(diǎn) n最后一個(gè)結(jié)點(diǎn)的指針域指向表頭結(jié)點(diǎn)，構(gòu)成了一個(gè)環(huán) 狀鏈 n循環(huán)鏈表優(yōu)點(diǎn)：循環(huán)鏈表優(yōu)點(diǎn)： n從任

20、一結(jié)點(diǎn)出發(fā)來訪問表中其他所有結(jié)點(diǎn) n空表與非空表的運(yùn)算的統(tǒng)一 1.6 1.6 樹與二叉樹樹與二叉樹 n1樹的定義 n樹(Tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱為空 樹，否則它滿足如下兩個(gè)條件： （1）有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)； （2）其余的結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的子集T1，T2， T3，Tm，其中每個(gè)子集又是一棵樹，并稱其為子樹。 1.6 1.6 樹與二叉樹樹與二叉樹 n2 2樹中的基本概念樹中的基本概念 n父結(jié)點(diǎn)與樹的根：每個(gè)結(jié)點(diǎn)最多只允許有一個(gè)前件， 稱為該結(jié)點(diǎn)的父結(jié)點(diǎn)。沒有前件的結(jié)點(diǎn)中有一個(gè)，稱 為樹的根結(jié)點(diǎn)。 n子結(jié)點(diǎn)與葉子結(jié)點(diǎn)：在樹結(jié)構(gòu)中，每一個(gè)

21、結(jié)點(diǎn)可以有 多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的 結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。 n結(jié)點(diǎn)的度和樹的度：一個(gè)結(jié)點(diǎn)所擁有直接后件個(gè)數(shù)稱 為該結(jié)點(diǎn)的度。一棵樹中各個(gè)結(jié)點(diǎn)度數(shù)的最大值叫做 這棵樹的度。 n層和樹的深度：樹結(jié)構(gòu)是一種層次結(jié)構(gòu)，根結(jié)點(diǎn)為第 一層，根的子結(jié)點(diǎn)為第二層，其余各結(jié)點(diǎn)的層數(shù)逐層 由上而下計(jì)算。一棵樹中結(jié)點(diǎn)的最大層數(shù)叫做此樹的 深度。 1.6.1 1.6.1 樹的基本概念樹的基本概念 n樹的特點(diǎn)樹的特點(diǎn) n（1）樹中只有根結(jié)點(diǎn)沒有前件； n（2）除根外，其余結(jié)點(diǎn)都有且僅一個(gè)前件； n（3）樹的結(jié)點(diǎn)，可以有零個(gè)或多個(gè)后件； n（4）除根外的其他結(jié)點(diǎn)，都存在唯一條從根到該結(jié)點(diǎn) 的路徑； n

22、（5）樹是一種分支結(jié)構(gòu)（除根的結(jié)點(diǎn)外）每個(gè)元素都 有且僅有一個(gè)直接前件，有且僅有零個(gè)或多個(gè)直接后 件。 n樹的存儲(chǔ)樹的存儲(chǔ) n用多重鏈表來表示 1.6.2 1.6.2 二叉樹及其基本性質(zhì)二叉樹及其基本性質(zhì) n1 1二叉樹的定義二叉樹的定義 n一個(gè)二叉樹是n個(gè)結(jié)點(diǎn)的有限集合（n0），此集合或者是空集 （n=0），或者是由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱為左 子樹和右子樹的二叉樹組成，并且左右子樹都是二叉樹。 n特點(diǎn)： n非空二叉樹只有一個(gè)根結(jié)點(diǎn)； n每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。 1.6.2 1.6.2 二叉樹及其基本性質(zhì)二叉樹及其基本性質(zhì) n2 2二叉樹的性質(zhì)二

23、叉樹的性質(zhì) n性質(zhì)性質(zhì)1 在二叉樹的第k層上，最多有 個(gè)結(jié)點(diǎn)。 n性質(zhì)性質(zhì)2 深度為m的二叉樹最多有個(gè) 結(jié)點(diǎn)。 n性質(zhì)性質(zhì)3 在任意一棵二叉樹中，度數(shù)為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總 比度為2的結(jié)點(diǎn)多一個(gè)。即： 其中，n0表示度數(shù)為0的結(jié)點(diǎn)數(shù)，n2表示度數(shù)為2的結(jié)點(diǎn)數(shù)。 n性質(zhì)性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的二叉樹的深度至少為 ， 其中 表示取 的整數(shù)部分。 )1(2 1 k k 12 m 1 20 nn 1log2n log2nn 2 log 1.6.2 1.6.2 二叉樹及其基本性質(zhì)二叉樹及其基本性質(zhì) n3滿二叉樹和完全二叉樹 n滿二叉樹：除最后一層外，每一層上的所有結(jié) 點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。 n完全二叉樹：

24、除最后一層外，每一層上的結(jié)點(diǎn) 數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的 若干結(jié)點(diǎn)。 1.6.2 1.6.2 二叉樹及其基本性質(zhì)二叉樹及其基本性質(zhì) n性質(zhì)性質(zhì)5 5 具有具有n n個(gè)結(jié)點(diǎn)的完全二叉樹深度為個(gè)結(jié)點(diǎn)的完全二叉樹深度為 。 n性質(zhì)性質(zhì)6 6 設(shè)完全二叉樹共有設(shè)完全二叉樹共有n n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始， 按層序（每一層從左到右）用自然數(shù)按層序（每一層從左到右）用自然數(shù)1 1，2 2，n n給結(jié)點(diǎn)給結(jié)點(diǎn) 進(jìn)行編號(hào)，則對(duì)于進(jìn)行編號(hào)，則對(duì)于編號(hào)為編號(hào)為k k（k k=1=1，2 2，n n）的結(jié)點(diǎn)有以）的結(jié)點(diǎn)有以 下結(jié)論：下結(jié)論： 若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒

25、有父結(jié)點(diǎn)；若k1，則該結(jié)點(diǎn)的 父結(jié)點(diǎn)的編號(hào)為INT(k/2)。 若2kn，則編號(hào)為k的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無左子結(jié) 點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）。 若2k+1n，則編號(hào)為k的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無右 子結(jié)點(diǎn)。 補(bǔ)充：度為1的結(jié)點(diǎn)個(gè)數(shù)要么為0個(gè)，要么為1個(gè)。 1log2n 1.6.3 1.6.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu) n普通二叉樹普通二叉樹 n采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) n存儲(chǔ)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域與指針域 n兩個(gè)指針域： n左指針域 n右指針域 n滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹 n采用順序存儲(chǔ)結(jié)構(gòu) 1.6.4 1.6.4 二叉樹的遍歷二叉樹的遍歷 n二叉樹的遍

26、歷：不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)二叉樹的遍歷：不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn) n1 1前序遍歷（前序遍歷（DLRDLR） n首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在 遍歷左右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍 歷右子樹。 n2 2中序遍歷（中序遍歷（LDRLDR） n首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在 遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后 遍歷右子樹 n3 3后序遍歷（后序遍歷（LRDLRD） n首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，并且，在 遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后 訪問根結(jié)點(diǎn)

27、。 1.6.4 1.6.4 二叉樹的遍歷二叉樹的遍歷 n前序遍歷：前序遍歷： nA、B、D、G、C、E、F n中序遍歷：中序遍歷： nD、G、B、A、E、C、F n后序遍歷：后序遍歷： nG、D、B、E、F、C、A 1.7 1.7 查找技術(shù)查找技術(shù) 1.7 1.7 查找技術(shù)查找技術(shù) n查找（查找（SearchingSearching）：根據(jù)給定的某個(gè)值，）：根據(jù)給定的某個(gè)值， 在查找表中確定一個(gè)其關(guān)鍵字等于給定值在查找表中確定一個(gè)其關(guān)鍵字等于給定值 的數(shù)據(jù)元素。的數(shù)據(jù)元素。 n查找結(jié)果：查找結(jié)果： n查找成功：找到 n查找不成功：沒找到 n平均查找長度：查找過程中關(guān)鍵字和給定平均查找長度：查找

28、過程中關(guān)鍵字和給定 值比較的平均次數(shù)值比較的平均次數(shù) 1.7.1 1.7.1 順序查找順序查找 n基本思想：基本思想： n從表中的第一個(gè)元素開始，將給定的值與表中逐個(gè)元 素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的 元素為止。否則就是表中沒有要找的元素，查找不成 功。 n平均要與表中一半以上元素進(jìn)行比較，最壞情況平均要與表中一半以上元素進(jìn)行比較，最壞情況 下需要比較下需要比較n n次。次。 n下列兩種情況下只能采用順序查找：下列兩種情況下只能采用順序查找： n如果線性表是無序表（即表中的元素是無序的），則 不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順 序查找。 n即使是有序線性表，如果采用

29、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能 用順序查找。 1.7.2 1.7.2 二分法查找二分法查找 n思想：先確定待查找記錄所在的范圍，然后逐步 縮小范圍，直到找到或確認(rèn)找不到該記錄為止。 n前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。 n查找過程： 1）若中間項(xiàng)的值等于）若中間項(xiàng)的值等于x,則說明已查到。則說明已查到。 2）若）若x小于中間項(xiàng)的值，則在線性表的前半部分查找；小于中間項(xiàng)的值，則在線性表的前半部分查找； 3）若）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。大于中間項(xiàng)的值，則在線性表的后半部分查找。 n特點(diǎn)：比順序查找方法效率高。最壞的情況下， 需要比較 log2n次。 1.7.2 1.7.2 二

30、分法查找二分法查找 n例：查找元素例：查找元素2222過程：過程： 1.8 1.8 排序技術(shù)排序技術(shù) 1.8.1 1.8.1 交換類排序法交換類排序法 n基本思想基本思想 n兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄 的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記 錄為止。 n方法方法 n冒泡排序 n快速排序 1.1.冒泡排序冒泡排序 n基本思想基本思想 n對(duì)存放原始數(shù)據(jù)的數(shù)組，按從后往前的方向進(jìn) 行多次掃描，當(dāng)發(fā)現(xiàn)相鄰兩個(gè)數(shù)據(jù)的次序與排 序要求的“遞增次序”不符合時(shí)，即將這兩個(gè) 數(shù)據(jù)進(jìn)行互換。這樣，較小的數(shù)據(jù)就會(huì)逐單元 向前移動(dòng)，好象氣泡向上浮起一樣。 n性能分析性能分析 n假設(shè)線性表的長度n，則在

31、最壞情況下，需要 的比較次數(shù)為n(n-1)/2。 2 2快速排序快速排序 n基本思想基本思想 n任取待排序序列中的某個(gè)元素作為基準(zhǔn)（一般 取第一個(gè)元素），通過一趟排序，將待排元素 分為左右兩個(gè)子序列，左子序列元素的排序碼 均小于或等于基準(zhǔn)元素的排序碼，右子序列的 排序碼則大于基準(zhǔn)元素的排序碼，然后分別對(duì) 兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序。 n快速排序的平均時(shí)間復(fù)雜度為快速排序的平均時(shí)間復(fù)雜度為O(nlogO(nlog2 2n)n)。 2 2快速排序快速排序 1.8.2 1.8.2 插入類排序法插入類排序法 n基本思想：基本思想： n每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插 入到前面已經(jīng)

32、排好序的子序列中的適當(dāng)位置， 直到全部記錄插入完成為止。 n方法方法: : n簡單插入排序 n希爾排序 1 1簡單插入排序法簡單插入排序法 n基本思想：基本思想： n把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè) 無序表，開始時(shí)有序表中只包含一個(gè)元素，無 序表中包含有n-1個(gè)元素，排序過程中每次從無 序表中取出第一個(gè)元素，把它的排序碼依次與 有序表元素的排序碼進(jìn)行比較，將它插入到有 序表中的適當(dāng)位置，使之成為新的有序表。 n在最壞的情況下，需要在最壞的情況下，需要n(n-1)/2n(n-1)/2次比較。次比較。 2 2希爾排序希爾排序 n基本思想基本思想 n先將整個(gè)待排元素序列分割成若干個(gè)子序列（由

33、相隔 某個(gè)增量h的元素組成的）分別進(jìn)行直接插入排序，待 整個(gè)序列中的元素基本有序（增量足夠?。r(shí)，再對(duì) 全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判?在元素基本有序的情況下（接近最好情況），效率是 很高的。 n增量序列一般取 ，其中n為待排序 序列的長度 n在最壞情況下，希爾排序的時(shí)間復(fù)雜度為在最壞情況下，希爾排序的時(shí)間復(fù)雜度為 )log, 2 , 1(2/ 2 nknh k i )( 5 . 1 nO 1.8.3 1.8.3 選擇類排序法選擇類排序法 n基本思想：基本思想： n每一趟從待排序的記錄中選出關(guān)鍵字最小的記 錄，順序放在已排好序的子序列的最后，直到 全部記錄排序完畢。 n方法：方

34、法： n簡單選擇排序 n堆排序 1 1簡單選擇排序法簡單選擇排序法 n基本思想：基本思想： n掃描整個(gè)線性表，從中選出最小的元素，將它 交換到表的最前面；然后對(duì)剩下的子表采用同 樣的方法，直到子表空為止。 n最壞情況下，需要比較最壞情況下，需要比較n(n-1)/2n(n-1)/2次。次。 2 2堆排序法堆排序法 n堆的定義堆的定義 具有n個(gè)元素的序列，當(dāng)且僅當(dāng)滿足 或 時(shí)稱之為堆。稱為大根堆；稱為小根堆 。 12 2 ii ii hh hh 12 2 ii ii hh hh 2 2堆排序法堆排序法 n建堆建堆 n在建堆的過程中，總是將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行 比較，若不滿足堆的條件，

35、則將左、右子樹根結(jié)點(diǎn)值中的大者與 根結(jié)點(diǎn)值進(jìn)行交換。這個(gè)調(diào)整過程一直做到所有子樹均為堆為止。 n堆排序堆排序 n（1）首先將一個(gè)無序序列建成堆。 n（2）然后將堆頂元素(序列中的最大項(xiàng))與堆中最后一個(gè)元素交換 (最大項(xiàng)應(yīng)該在序列的最后)。不考慮已經(jīng)換到最后的那個(gè)元素， 只考慮前n-1個(gè)元素構(gòu)成的子序列，將該子序列調(diào)整為堆。 n反復(fù)做步驟（2），直到剩下的子序列空為止。 n在最壞情況下，堆排序法需要比較的次數(shù)為在最壞情況下，堆排序法需要比較的次數(shù)為O(nlogO(nlog2 2n)n)。 各種排序法比較各種排序法比較 典型考題分析典型考題分析 n【例例1-11-1】問題處理方案的正確而完整的描問

36、題處理方案的正確而完整的描 述稱為述稱為 。（。（20052005年年4 4月）月） n答案答案 算法算法 n【例例1-21-2】算法復(fù)雜度主要包括時(shí)間復(fù)雜度算法復(fù)雜度主要包括時(shí)間復(fù)雜度 和和 復(fù)雜度。（復(fù)雜度。（20052005年年9 9月）月） n答案答案 空間空間 n【例例1-31-3】算法的時(shí)間復(fù)雜度是指算法的時(shí)間復(fù)雜度是指_。 A）執(zhí)行算法程序所需要的時(shí)間 B）算法程序的長度 C）算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù) D）算法程序中的指令條數(shù) n答案答案C C n【例例1-41-4】算法的空間復(fù)雜度是指算法的空間復(fù)雜度是指_。 A）算法程序的長度 B）算法程序中的指令條數(shù) C）算法程序

37、所占的存儲(chǔ)空間 D）算法執(zhí)行過程中所需要的存儲(chǔ)空間 n答案答案D D n【例例1-51-5】下列敘述中正確的是下列敘述中正確的是 。 （20062006年年9 9月）月） A）一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大 B）一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小 C）一個(gè)算法的時(shí)間復(fù)雜度大，則其空間可復(fù)雜度必定小 D）上述三種說法都不對(duì) n答案答案 D D n【例例1-61-6】下列敘述中正確的是下列敘述中正確的是 。 （20052005年年9 9月）月） A）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu) B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬 于非線性結(jié)構(gòu) C）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種

38、存儲(chǔ)結(jié)構(gòu)，且 各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 D）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且 各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率 n答案答案 D D n【例例1-71-7】數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié) 構(gòu)，循環(huán)隊(duì)列屬于構(gòu)，循環(huán)隊(duì)列屬于 結(jié)構(gòu)。（結(jié)構(gòu)。（20052005年年9 9 月）月） n答案答案 邏輯邏輯 n【例例1-81-8】數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性 結(jié)構(gòu)，帶鏈的隊(duì)列屬于結(jié)構(gòu)，帶鏈的隊(duì)列屬于 。（。（20062006年年 9 9月）月） n答案答案 線性結(jié)構(gòu)線性結(jié)構(gòu) n【例例1-91-9】下列敘述中正確的是下列敘述中正確的是_。 （2

39、0062006年年4 4月）月） A）線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) B）棧與隊(duì)列是非線性結(jié)構(gòu) C）雙向鏈表是非線性結(jié)構(gòu) D）只有根結(jié)點(diǎn)的二叉樹是線性結(jié)構(gòu) n答案答案 A A n【例例1-101-10】某線性表采用順序存儲(chǔ)結(jié)構(gòu)，某線性表采用順序存儲(chǔ)結(jié)構(gòu)， 每個(gè)元素占每個(gè)元素占4 4個(gè)存儲(chǔ)單元，首地址為個(gè)存儲(chǔ)單元，首地址為200200， 則第則第1212個(gè)元素的存儲(chǔ)地址為個(gè)元素的存儲(chǔ)地址為 。 A）248 B）247 C）246 D）244 n答案答案 D D n【例例1-111-11】在長度為在長度為n n的順序表的第的順序表的第i i （11i in n+1+1）個(gè)位置上插入一個(gè)元素，元）個(gè)

40、位置上插入一個(gè)元素，元 素的移動(dòng)次數(shù)為素的移動(dòng)次數(shù)為 。 A）n-i+1 B）n-i C）i D）i-1 n答案答案 A A n【例例1-121-12】在一個(gè)長度為在一個(gè)長度為n n的順序表中，刪的順序表中，刪 除第除第i i（11i in n）個(gè)元素時(shí)，需要移動(dòng)的）個(gè)元素時(shí)，需要移動(dòng)的 元素個(gè)數(shù)為元素個(gè)數(shù)為 。 A）n-i+1 B）n-i C）i D）i-1 n答案答案 B B n【例例1-131-13】以下描述的中，不是線性表的以下描述的中，不是線性表的 順序存儲(chǔ)結(jié)構(gòu)的特征的是順序存儲(chǔ)結(jié)構(gòu)的特征的是 。 A）不便于插入和刪除 B）需要連續(xù)的存儲(chǔ)空間 C）可隨機(jī)訪問 D）需另外開辟空間來保存

41、元素之間的關(guān)系 n答案答案 D D n【例例1-141-14】下列關(guān)于棧的描述中錯(cuò)誤的是下列關(guān)于棧的描述中錯(cuò)誤的是 _。（。（20052005年年4 4月）月） A）棧是先進(jìn)后出的線性表 B）棧只能順序存儲(chǔ) C）棧具有記憶作用 D）對(duì)棧的插入與刪除操作中，不需要改變棧底 指針 n答案答案 B B n【例例1-151-15】棧和隊(duì)列的共同點(diǎn)是棧和隊(duì)列的共同點(diǎn)是_。 A）都是先進(jìn)先出 B）都是先進(jìn)后出 C）只允許在端點(diǎn)處插入和刪除元素 D）沒有共同點(diǎn) n答案答案 C C n【例例1-161-16】棧的輸入序列為棧的輸入序列為1 1，2 2，3 3， n n-1-1，n n，輸出序列的第，輸出序列的

42、第1 1個(gè)元素為個(gè)元素為n n，則第，則第 個(gè)輸出元素為個(gè)輸出元素為_。 A）n-i+1 B）n-1 C）i D）哪個(gè)元素?zé)o所謂 n答案答案 A A n【例例1-171-17】一個(gè)隊(duì)列的入隊(duì)序列是一個(gè)隊(duì)列的入隊(duì)序列是1 1、2 2、 3 3、4 4，則隊(duì)列的輸出序列是，則隊(duì)列的輸出序列是 。 A）4、3、2、1 B）1、2、3、4 C）1、4、3、2 D）3、2、4、1 n答案答案 B B n【例例1-181-18】隊(duì)列是限定只能在表的一端進(jìn)隊(duì)列是限定只能在表的一端進(jìn) 行插入和在另一端進(jìn)行刪除操作的線性表。行插入和在另一端進(jìn)行刪除操作的線性表。 允許插入的一端稱作允許插入的一端稱作_。 n答案

43、答案 隊(duì)尾隊(duì)尾 n【例例1-191-19】下列對(duì)于線性鏈表的描述中正下列對(duì)于線性鏈表的描述中正 確的是確的是 。（。（20052005年年4 4月）月） A）存儲(chǔ)空間不一定是連續(xù)，且各元素的存儲(chǔ)順序是任意的 B）存儲(chǔ)空間不一定是連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面 C）存儲(chǔ)空間必須連續(xù)，且各前件元素一定存儲(chǔ)在后件元素的前面 D）存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的 n答案答案 A A n【例例1-201-20】下列敘述中，錯(cuò)誤的是下列敘述中，錯(cuò)誤的是 。 A）線性表是由n個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列 B）線性表是一種線性結(jié)構(gòu)。 C）線性表的所有結(jié)點(diǎn)有且只有一個(gè)前件和一個(gè) 后件 D）

44、線性表可以是空表。 n答案答案 C C n【例例1-211-21】下列描述的不是鏈表的優(yōu)點(diǎn)是下列描述的不是鏈表的優(yōu)點(diǎn)是 _。 A）邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接 B）插入、刪除運(yùn)算操作方便，不必移動(dòng)結(jié)點(diǎn) C）所需存儲(chǔ)空間比線性表節(jié)省 D）無需事先估計(jì)存儲(chǔ)空間的大小 n答案答案 C C n【例例1-221-22】某線性表最常用的運(yùn)算是插入某線性表最常用的運(yùn)算是插入 和刪除，插入運(yùn)算是指在表尾插入一個(gè)新和刪除，插入運(yùn)算是指在表尾插入一個(gè)新 元素。刪除運(yùn)算是指刪除表頭第一個(gè)元素，元素。刪除運(yùn)算是指刪除表頭第一個(gè)元素， 那么采用那么采用 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 A）僅有尾指針

45、的單向循環(huán)鏈表 B）僅有頭指針的單向循環(huán)鏈表 C）單向鏈表 D）順序存儲(chǔ) n答案答案 A A n【例例1-231-23】一棵二叉樹第六層（根結(jié)點(diǎn)為一棵二叉樹第六層（根結(jié)點(diǎn)為 第一層）的結(jié)點(diǎn)數(shù)最多為第一層）的結(jié)點(diǎn)數(shù)最多為 個(gè)。個(gè)。 （20052005年年9 9月）月） n答案答案 3232 n【例例1-241-24】深度為深度為5 5的二叉樹至多有的二叉樹至多有 _個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 A）16 B）32 C）31 D）10 n答案答案 C C n【例例1-251-25】設(shè)樹設(shè)樹T T的度為的度為4 4，其中度為，其中度為1 1，2 2， 3 3，4 4的結(jié)點(diǎn)個(gè)數(shù)分別為的結(jié)點(diǎn)個(gè)數(shù)分別為4 4，2 2

46、，1 1，1 1。則。則T T中中 的葉子結(jié)點(diǎn)為的葉子結(jié)點(diǎn)為_。 A）8 B）7 C）6 D）5 n答案答案 A A n【例例1-261-26】某二叉樹中度為某二叉樹中度為2 2的結(jié)點(diǎn)有的結(jié)點(diǎn)有1818個(gè)，個(gè)， 則該二叉樹中有則該二叉樹中有 個(gè)葉子結(jié)點(diǎn)。個(gè)葉子結(jié)點(diǎn)。 （20052005年年4 4月）月） n答案答案 1919 n【例例1-271-27】具有具有8888個(gè)結(jié)點(diǎn)的二叉樹，其深個(gè)結(jié)點(diǎn)的二叉樹，其深 度至少為度至少為_。 n答案答案 7 7 n【例例1-281-28】在深度為在深度為7 7的滿二叉樹中，葉子的滿二叉樹中，葉子 結(jié)點(diǎn)的個(gè)數(shù)為（結(jié)點(diǎn)的個(gè)數(shù)為（20062006年年4 4月）月

47、） A）32 B）31 C）64 D）63 n答案答案 C C n【例例1-291-29】設(shè)一棵完全二叉樹共有設(shè)一棵完全二叉樹共有700700個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)， 則在該二叉樹中有則在該二叉樹中有_個(gè)葉子結(jié)點(diǎn)。個(gè)葉子結(jié)點(diǎn)。 n答案答案 350350 n【例例1-301-30】對(duì)如圖對(duì)如圖1-301-30所示的二叉樹，進(jìn)所示的二叉樹，進(jìn) 行后序遍歷的結(jié)果為行后序遍歷的結(jié)果為 。（。（20062006年年4 4 月）月） A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA n答案答案 D D n【例例1-311-31】假設(shè)一棵二叉樹的后序遍歷序假設(shè)一棵二叉樹的后序遍歷序 列為列為DGJHEBIFCADGJHEBIFCA，中序遍歷序列為，中序遍歷序列為 DBGEHJACIFDBGEHJACIF，則其前序遍歷序列為，則其前序遍歷序列為 。 n答案：答案：ABDEGHJCFIABDEGHJCFI n【例例1-321-32】對(duì)長度為對(duì)長度為n n的線性表進(jìn)行順序查的線性表進(jìn)行順序查 找，在最壞情況下所需要的比較次數(shù)為找，在最壞情況下所需要的比較次數(shù)為 _。（。（20052005年年4 4月）月） A）log2n B）n/2 C）n D）n+l n答案答案 C C n【例例1-331-33】下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法下列數(shù)據(jù)結(jié)構(gòu)中，能用