信息學(xué)奧賽輔導(dǎo)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識.根據(jù)數(shù)據(jù)元素間關(guān)系的基本特征，有四種基本數(shù)據(jù)結(jié)構(gòu)：集合：數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系。線性結(jié)構(gòu)：一個對一個，如線性表、棧、隊列。樹形結(jié)構(gòu)：一個對多個，如樹。圖狀結(jié)構(gòu)：多個對多個，如圖。.數(shù)據(jù)的存儲結(jié)構(gòu)一般有兩種，用一組物理地址相鄰的存儲單元來存儲數(shù)據(jù)元素的存儲方式稱之為順序存儲結(jié)構(gòu)；借助于動態(tài)數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)元素的存儲方式稱之為鏈?zhǔn)酱鎯Y(jié)構(gòu)。.數(shù)組的存儲一般采用的是順序存儲結(jié)構(gòu)，如一維數(shù)組和多維數(shù)組。按照順序往下存儲數(shù)據(jù)。如圖1.棧結(jié)構(gòu)的特點(diǎn)是“先進(jìn)后出”，如圖2舉例說明。5.隊列結(jié)構(gòu)的特點(diǎn)是“先進(jìn)先出5.隊列結(jié)構(gòu)的特點(diǎn)是“先進(jìn)先出，比如排隊買票等，如圖3舉例說明。Vars:array[1..4,1..10]ofinteger;則說明數(shù)組Vars:array[1..4,1..10]ofinteger;則說明數(shù)組s是二維的整型數(shù)組，每個元素占2字節(jié)，假設(shè)存儲第一個元素的起始地址為100,則它的存儲結(jié)構(gòu)如下：棧結(jié)構(gòu)就像一個底部封瞅列結(jié)構(gòu)就像底部不封閉的線線性表，比如進(jìn)棧元素的生表，比如進(jìn)隊列元素的順序是序分別為、2、3,則出棧元1、2、3,則出隊列元素的順序素的順序分別配2、1,滿也是1、2、3,滿足“先進(jìn)先出”足“先進(jìn)后出”原則。的原則。進(jìn)隊列出隊列（圖3）進(jìn)隊列出隊列（圖3）.樹結(jié)構(gòu)：樹是n(n>=0)個結(jié)點(diǎn)的有限集。任意一棵樹，只有一個特定白稱為根的結(jié)點(diǎn)(如圖4中的A);當(dāng)n>1時，其余結(jié)點(diǎn)可分為m(m>0)個互不相交的有限集，其中每一個集合本身又是一棵樹，并且稱為根的子樹。結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度。(如圖4中的B所擁有的度為2)度為0的結(jié)點(diǎn)稱為葉子或終端節(jié)點(diǎn)。(如圖4中的H、I、J、K等都是葉子結(jié)點(diǎn))度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。結(jié)點(diǎn)的層次從根開始定義起，根為第一層，根的分支為第二層，依此類推(如圖4的樹結(jié)構(gòu)最大層次為4層)。樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。(如圖4的樹結(jié)構(gòu)的深度或高度為4)二叉樹是一種特殊的樹形結(jié)構(gòu)，它的特點(diǎn)是每個結(jié)點(diǎn)至多只有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點(diǎn))，并且二叉樹的子樹有左右之分，其次序不能任意顛倒，所以二叉樹是由根節(jié)點(diǎn)、左子樹、右子樹三個基本單元構(gòu)成。一棵深度為k的二叉樹至多只有2k—1個結(jié)點(diǎn)，此二叉樹稱為滿二叉樹(如圖4為深度為

4的滿二叉樹)，最少也有K個結(jié)點(diǎn)(如圖5為深度為4的最小二叉樹)?？梢则?yàn)證具有n個葉子結(jié)點(diǎn)的滿二叉樹共有2n—1個結(jié)點(diǎn)(如圖5的滿二叉樹)。在二叉機(jī)^勺第i層上至多有2i1個結(jié)點(diǎn)。樹的遍歷：按照根節(jié)點(diǎn)在訪問中的先后位置，我們有三種樹的遍歷方式。(當(dāng)然每次訪問都是左子樹在右子樹的前面。)TOC\o"1-5"\h\z先序遍歷(先訪問根節(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹)：如圖4的先序遍歷為：A、B、D、H、I、E、J、K、C、F、L、M、G、N、O。中序遍歷(先訪問左子樹，再訪問根節(jié)點(diǎn)，最后訪問右子樹)：如圖4的中序遍歷為：H、D、I、B、J、E、K、A、L、F、M、C、N、G、O。后序遍歷(先訪問左子樹，再訪問右子樹，最后訪問根節(jié)點(diǎn))：如圖4的后序遍歷為：H、I、D、J、K、E、B、L、M、F、N、O、G、C、A。由上面三種遍歷樹結(jié)構(gòu)的方式可知，先序遍歷最先訪問的是根節(jié)點(diǎn)；后序遍歷最后訪問的是根節(jié)點(diǎn)；由中序遍歷的根節(jié)點(diǎn)的位置可知，在根節(jié)點(diǎn)的左邊全部都是根節(jié)點(diǎn)的左子樹，在根節(jié)點(diǎn)的右邊全部都是根節(jié)點(diǎn)的右子樹。必須掌握，由任意兩種樹的遍歷結(jié)果，能夠畫出該二叉樹，然后根據(jù)該二叉樹，寫出另一種遍歷結(jié)果。(10)哈夫曼樹稱為最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。.圖結(jié)構(gòu)：圖是由頂點(diǎn)集V和邊集E組成，一般把圖在圖6中，邊有方向性，我們稱之為有向圖，有向圖的邊稱之為弧。在圖7中，邊沒有方向性，即邊＜v1,v2＞和＜v2,v1＞指的是同一條邊，我們稱之為無向圖。在有向圖中，從某頂點(diǎn)出發(fā)的弧的數(shù)目稱為該頂點(diǎn)的出度，到達(dá)某頂點(diǎn)的有向弧的數(shù)目稱為該頂點(diǎn)的入度。(如圖6的有向圖中，頂點(diǎn)V1的出度為2,入度為1。)在無向圖中，與頂點(diǎn)依附的邊的條數(shù)稱為該頂點(diǎn)的度。(如圖7中，頂點(diǎn)V1的度為2。)完全圖定義：如果用n表示圖中頂點(diǎn)數(shù)目，用e表示邊或者弧的數(shù)目，則有：對于有向圖，具有n(n-1)條弧的有向圖稱為有向完全圖(任意兩個頂點(diǎn)之間都有2條有向弧)對于無向圖，具有n(n-1)/2條邊的無向圖稱為完全圖(任意兩個頂點(diǎn)之間都有一條邊。)連通圖定義：在無向圖中，若圖中任意兩個頂點(diǎn)之間都存在路徑，則稱該無向圖為連通圖。在有向圖中，對于任意兩個頂點(diǎn)Vi和Vj(ViwVj)，若從Vi到Vj和從Vj到Vi之間均存在路徑，則稱該有向圖為強(qiáng)連通圖。帶權(quán)圖定義：有時圖的邊往往與具有一定意義的數(shù)值有關(guān)，我們把這種與圖的邊相關(guān)的數(shù)稱為邊上的權(quán)。權(quán)可以表示從一個頂點(diǎn)到另一個頂點(diǎn)的距離、費(fèi)用或代價等，由這種帶權(quán)的邊構(gòu)成的圖稱為帶權(quán)圖。圖的遍歷方式有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索。

(圖6有向圖)(圖6有向圖).二分法查找：具體方法見課本P147?P148面。二分法查找(又稱折半查找)算法如下：首先需要設(shè)三個指示器top、bot、mid,分別指向查找范圍的頂部、底部和中間位置。假定有11個元素的有序數(shù)列(2,5,7,10,14,15,18,23,35,41,52),待查找數(shù)為41,則一開始top=1、bot=11、mid=(top+bot)div2=6,這是一定要bot大于top,接著進(jìn)行判斷：如果x=a[mid],則表示找到；如果x<a[mid],則說明待查找數(shù)在top至1Jmid—1之間，改變bot=mid—1;如果x>a[mid],則說明待查找數(shù)在mid+1到bot之間，改變top=mid+1;重復(fù)以上過程直到已經(jīng)找到或無法查找為止。例如查找41,則只需查找3次即可找到。假設(shè)用二分法在有1000個數(shù)據(jù)的有序數(shù)組中查找某個數(shù)據(jù)，則最多只需查找10次即可。(因?yàn)?10>1000).排序：在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是選擇排序。在待排序的數(shù)據(jù)表已經(jīng)為有序時，快速排序算法花費(fèi)時間反而多。.設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是1?n,其頭尾指針分別為f和r,則其元素個數(shù)為(r-f+n)MODn。.哈希表：.相關(guān)練習(xí)習(xí)題：數(shù)組A[30..100,20..100]以行優(yōu)先的方式存儲，每個元素占8個字節(jié)，且已知A[40,30]的地址為2000,則A[60,90]的地址為：如果以列優(yōu)先存儲，則為:設(shè)棧S的初始狀態(tài)為空，現(xiàn)有6個元素組成的序列{1,3,5,7,9,11},對該序列在S棧上依次進(jìn)行如下操作(從序列中的1開始，出棧后不在進(jìn)棧):進(jìn)棧，出棧，進(jìn)棧，進(jìn)棧，進(jìn)棧，進(jìn)棧，出棧，進(jìn)棧，問出棧的元素序列是：,棧頂指針的值為棧頂元素為:把中綴表達(dá)式寫成后綴及前綴表達(dá)式(P+Q)*(A-B)/((C+D)/(E-F))-G后:A-C*D+B/E*(D/A)后:根據(jù)后綴表達(dá)式，寫出前綴及中綴表達(dá)式ABC/DE+GH-/*+刖：中：ABC/DE+GH-/*+刖：中：備注：以上這兩題實(shí)際上考查了數(shù)據(jù)結(jié)構(gòu)中的表達(dá)式樹給出一棵二叉樹的中序遍歷：DBGEACHF與后序遍歷：DGEBHIFCA,畫出此二叉樹A=11001010B,B=00001111B,C=01011100B,則AVBAC=()BA)01011110B)00001111C)01011100D)11001110E)11001010對給定的整數(shù)序列(54,73,21,35,67,78,63,24,89)進(jìn)行從小到大的排序時，采用快速排序的第一趟掃描的結(jié)果是

A)(24,21,35,54,67,78,63,73,89)B)(24,35,21,54,67,78,63,73,89)0)(24,21,35,54,67,63,73,78,89)D)(21,24,35,54,63,67,73,78,89)一棵n個結(jié)點(diǎn)的完全二叉樹，則二叉樹的高度h為A)n/2O)(log2n)/20)[log2n]+1D)2n-1設(shè)有一個含有13個元素的Hash表(0~12),Hash函數(shù)是：H(key)=key%13,其中％是求余數(shù)運(yùn)算。用二次探查法解決沖突，則對于序列(8、31、20、33、18、53、27),則下列說法正確的是()。A)27在1號格子中B)33在6號格子中0)31在5號格子中D)20在7號格子中E)18在4號格子中.歷屆信息學(xué)奧賽試題中的數(shù)據(jù)結(jié)構(gòu)試題:選擇題中的數(shù)據(jù)結(jié)構(gòu)試題:(第10屆)某車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時該車站站臺為空，從這一時刻開始出入記錄為：“進(jìn)出進(jìn)進(jìn)出進(jìn)進(jìn)進(jìn)出出進(jìn)出”。假設(shè)車輛入站的順序?yàn)?,2,3……，則車輛出站的順序?yàn)?E)A、1,2,3,4,5B、1,2,4,5,7C、1,3,5,4,6D、1,3,5,6,7E、1,3,6,5,7(第10屆)二叉樹T,已知其前序遍歷序列為1243576,中序遍歷序列為4215736,其后序遍歷序列為(B)A、4257631B、4275631C、4275361D、4723561E、4526371(第10屆)滿二叉樹的葉節(jié)點(diǎn)為N,則它的節(jié)點(diǎn)總數(shù)為(0)A、A、NB、2NC、2N-1D、2N+1E、2AN-1(4)(4)(第10屆)在下圖，從端點(diǎn)(E)出發(fā)存在一條路徑可以遍歷圖中的每條邊一次，而且(第9屆)一個高度為h的二叉樹最小元素數(shù)目是(B)。A)2h+lB)h0)2h-1D)2hE)2h-lTOC\o"1-5"\h\z(第9屆)已知隊列(13,2,11,34,41,77,5,7,18,26,15),第一個進(jìn)入隊列的元素是13,則第五個出隊列的元素是(B)。A)5B)410)77D)13E)18(第8屆)一個向量第一個元素的存儲地址是100，每個元素的長度是2,則第5個元素的地址是(B)A)110B)1080)100D)109(第8屆)在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是(D)。A)希爾排序B)起泡排序0)插入排序D)選擇排序

(9)(第7屆)在順序表(2,5,7,10,14,15,18,23,35,41,52)中，用二分法查找12,所需的關(guān)鍵碼比較的次數(shù)為(C),用二分法查找41,所需的關(guān)鍵碼比較此數(shù)為(B)。A)2B)3A)2B)3C)4(10)(第7屆)若已知一個棧的入棧順序是Pn,若P1是n,則Pi是(C)A)iB)n-1C)n-i+1(11)(第6屆)設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是數(shù)為(D)A.r-fB.r-f+1C.(r-f)MOD(12)(第6屆)在待排序的數(shù)據(jù)表已經(jīng)為有序時,1,2,3,…，n,其輸出序列為P1,P2,P3,…，D)不確定1?n,其頭尾指針分別為f和r,則其元素個n+1D.(r-f+n)MODn下列排序算法中花費(fèi)時間反而多的是(D)A.堆排序B.C.冒泡排序D.快速排序(13)(第6屆)某數(shù)列有1000個各不相同的單元，由低至高按序排列；現(xiàn)要對該數(shù)列進(jìn)行二分法檢索(binarysearch),在最壞的情況下，需檢視(B)個單元A.1000B.10C.100D.500(14)(第6屆)已知數(shù)組A中，每個元素A[I,J]在存貯日^要占3個字節(jié)，設(shè)I從1變化到8,J從1變化到10,分配內(nèi)存時是從地址SA開始連續(xù)按行存貯分配的。試問：A[5,8]的起始地址為(A)A.SA+141B.SA+180C.SA+222D.SA+225(15)(第6屆)線性表若采用鏈表存貯結(jié)構(gòu)，要求內(nèi)存中可用存貯單元地址(D)A.必須連續(xù)B.部分地址必須連續(xù)C.一定不連續(xù)D.連續(xù)不連續(xù)均可(16)(第6屆)下列敘述中，正確的是(D)A.線性表的線性存貯結(jié)構(gòu)優(yōu)于鏈表存貯結(jié)構(gòu)B.隊列的操作方式是先進(jìn)后出C.棧的操作方式是先進(jìn)先出D.二維數(shù)組是指它的每個數(shù)據(jù)元素為一個線性表的線性表問題求解中的數(shù)據(jù)結(jié)構(gòu)知識