信息學奧賽輔導數(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ù)元素的存儲方式稱之為鏈式存儲結(jié)構(gòu)。.數(shù)組的存儲一般采用的是順序存儲結(jié)構(gòu)，如一維數(shù)組和多維數(shù)組。按照順序往下存儲數(shù)據(jù)。如圖1.棧結(jié)構(gòu)的特點是“先進后出”，如圖2舉例說明。5.隊列結(jié)構(gòu)的特點是“先進先出5.隊列結(jié)構(gòu)的特點是“先進先出，比如排隊買票等，如圖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)就像底部不封閉的線線性表，比如進棧元素的生表，比如進隊列元素的順序是序分別為、2、3,則出棧元1、2、3,則出隊列元素的順序素的順序分別配2、1,滿也是1、2、3,滿足“先進先出”足“先進后出”原則。的原則。進隊列出隊列（圖3）進隊列出隊列（圖3）.樹結(jié)構(gòu)：樹是n(n>=0)個結(jié)點的有限集。任意一棵樹，只有一個特定白稱為根的結(jié)點(如圖4中的A);當n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集，其中每一個集合本身又是一棵樹，并且稱為根的子樹。結(jié)點擁有的子樹數(shù)稱為結(jié)點的度。(如圖4中的B所擁有的度為2)度為0的結(jié)點稱為葉子或終端節(jié)點。(如圖4中的H、I、J、K等都是葉子結(jié)點)度不為0的結(jié)點稱為非終端結(jié)點或分支結(jié)點。結(jié)點的層次從根開始定義起，根為第一層，根的分支為第二層，依此類推(如圖4的樹結(jié)構(gòu)最大層次為4層)。樹中結(jié)點的最大層次稱為樹的深度或高度。(如圖4的樹結(jié)構(gòu)的深度或高度為4)二叉樹是一種特殊的樹形結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點)，并且二叉樹的子樹有左右之分，其次序不能任意顛倒，所以二叉樹是由根節(jié)點、左子樹、右子樹三個基本單元構(gòu)成。一棵深度為k的二叉樹至多只有2k—1個結(jié)點，此二叉樹稱為滿二叉樹(如圖4為深度為

4的滿二叉樹)，最少也有K個結(jié)點(如圖5為深度為4的最小二叉樹)?？梢则炞C具有n個葉子結(jié)點的滿二叉樹共有2n—1個結(jié)點(如圖5的滿二叉樹)。在二叉機^勺第i層上至多有2i1個結(jié)點。樹的遍歷：按照根節(jié)點在訪問中的先后位置，我們有三種樹的遍歷方式。(當然每次訪問都是左子樹在右子樹的前面。)TOC\o"1-5"\h\z先序遍歷(先訪問根節(jié)點，再訪問左子樹，最后訪問右子樹)：如圖4的先序遍歷為：A、B、D、H、I、E、J、K、C、F、L、M、G、N、O。中序遍歷(先訪問左子樹，再訪問根節(jié)點，最后訪問右子樹)：如圖4的中序遍歷為：H、D、I、B、J、E、K、A、L、F、M、C、N、G、O。后序遍歷(先訪問左子樹，再訪問右子樹，最后訪問根節(jié)點)：如圖4的后序遍歷為：H、I、D、J、K、E、B、L、M、F、N、O、G、C、A。由上面三種遍歷樹結(jié)構(gòu)的方式可知，先序遍歷最先訪問的是根節(jié)點；后序遍歷最后訪問的是根節(jié)點；由中序遍歷的根節(jié)點的位置可知，在根節(jié)點的左邊全部都是根節(jié)點的左子樹，在根節(jié)點的右邊全部都是根節(jié)點的右子樹。必須掌握，由任意兩種樹的遍歷結(jié)果，能夠畫出該二叉樹，然后根據(jù)該二叉樹，寫出另一種遍歷結(jié)果。(10)哈夫曼樹稱為最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。.圖結(jié)構(gòu)：圖是由頂點集V和邊集E組成，一般把圖在圖6中，邊有方向性，我們稱之為有向圖，有向圖的邊稱之為弧。在圖7中，邊沒有方向性，即邊＜v1,v2＞和＜v2,v1＞指的是同一條邊，我們稱之為無向圖。在有向圖中，從某頂點出發(fā)的弧的數(shù)目稱為該頂點的出度，到達某頂點的有向弧的數(shù)目稱為該頂點的入度。(如圖6的有向圖中，頂點V1的出度為2,入度為1。)在無向圖中，與頂點依附的邊的條數(shù)稱為該頂點的度。(如圖7中，頂點V1的度為2。)完全圖定義：如果用n表示圖中頂點數(shù)目，用e表示邊或者弧的數(shù)目，則有：對于有向圖，具有n(n-1)條弧的有向圖稱為有向完全圖(任意兩個頂點之間都有2條有向弧)對于無向圖，具有n(n-1)/2條邊的無向圖稱為完全圖(任意兩個頂點之間都有一條邊。)連通圖定義：在無向圖中，若圖中任意兩個頂點之間都存在路徑，則稱該無向圖為連通圖。在有向圖中，對于任意兩個頂點Vi和Vj(ViwVj)，若從Vi到Vj和從Vj到Vi之間均存在路徑，則稱該有向圖為強連通圖。帶權(quán)圖定義：有時圖的邊往往與具有一定意義的數(shù)值有關(guān)，我們把這種與圖的邊相關(guān)的數(shù)稱為邊上的權(quán)。權(quán)可以表示從一個頂點到另一個頂點的距離、費用或代價等，由這種帶權(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,接著進行判斷：如果x=a[mid],則表示找到；如果x<a[mid],則說明待查找數(shù)在top至1Jmid—1之間，改變bot=mid—1;如果x>a[mid],則說明待查找數(shù)在mid+1到bot之間，改變top=mid+1;重復以上過程直到已經(jīng)找到或無法查找為止。例如查找41,則只需查找3次即可找到。假設(shè)用二分法在有1000個數(shù)據(jù)的有序數(shù)組中查找某個數(shù)據(jù)，則最多只需查找10次即可。(因為210>1000).排序：在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是選擇排序。在待排序的數(shù)據(jù)表已經(jīng)為有序時，快速排序算法花費時間反而多。.設(shè)循環(huán)隊列中數(shù)組的下標范圍是1?n,其頭尾指針分別為f和r,則其元素個數(shù)為(r-f+n)MODn。.哈希表：.相關(guān)練習習題：數(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棧上依次進行如下操作(從序列中的1開始，出棧后不在進棧):進棧，出棧，進棧，進棧，進棧，進棧，出棧，進棧，問出棧的元素序列是：,棧頂指針的值為棧頂元素為:把中綴表達式寫成后綴及前綴表達式(P+Q)*(A-B)/((C+D)/(E-F))-G后:A-C*D+B/E*(D/A)后:根據(jù)后綴表達式，寫出前綴及中綴表達式ABC/DE+GH-/*+刖：中：ABC/DE+GH-/*+刖：中：備注：以上這兩題實際上考查了數(shù)據(jù)結(jié)構(gòu)中的表達式樹給出一棵二叉樹的中序遍歷：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)進行從小到大的排序時，采用快速排序的第一趟掃描的結(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é)點的完全二叉樹，則二叉樹的高度h為A)n/2O)(log2n)/20)[log2n]+1D)2n-1設(shè)有一個含有13個元素的Hash表(0~12),Hash函數(shù)是：H(key)=key%13,其中％是求余數(shù)運算。用二次探查法解決沖突，則對于序列(8、31、20、33、18、53、27),則下列說法正確的是()。A)27在1號格子中B)33在6號格子中0)31在5號格子中D)20在7號格子中E)18在4號格子中.歷屆信息學奧賽試題中的數(shù)據(jù)結(jié)構(gòu)試題:選擇題中的數(shù)據(jù)結(jié)構(gòu)試題:(第10屆)某車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時該車站站臺為空，從這一時刻開始出入記錄為：“進出進進出進進進出出進出”。假設(shè)車輛入站的順序為1,2,3……，則車輛出站的順序為(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é)點為N,則它的節(jié)點總數(shù)為(0)A、A、NB、2NC、2N-1D、2N+1E、2AN-1(4)(4)(第10屆)在下圖，從端點(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),第一個進入隊列的元素是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ù)組的下標范圍是數(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下列排序算法中花費時間反而多的是(D)A.堆排序B.C.冒泡排序D.快速排序(13)(第6屆)某數(shù)列有1000個各不相同的單元，由低至高按序排列；現(xiàn)要對該數(shù)列進行二分法檢索(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.隊列的操作方式是先進后出C.棧的操作方式是先進先出D.二維數(shù)組是指它的每個數(shù)據(jù)元素為一個線性表的線性表問題求解中的數(shù)據(jù)結(jié)構(gòu)知識