數據結構基礎知識課件

數據結構基礎知識NOIP提高組初賽解析數據結構基礎知識NOIP提高組初賽解析什么是數據結構？數據元素相互之間的關系稱為數據結構。其中數據元素是個廣義概念，是所有能輸入到計算機中并被計算機程序處理的符號的總稱。什么是數據結構？數據元素相互之間的關系稱為數據結構。其中數據四大類基本數據結構集合（無相互關系）線性結構（一對一）樹（一對多）圖（多對多）四大類基本數據結構集合（無相互關系）集合運算(NOIp2005)字符串“ababacbab”和字符串“abcba”的最長公共子串是（）。

A.abcbaB.cbaC.abcD.abE.bcba（NOIp2008）.設字符串S=”O(jiān)lympic”，S的非空子串的數目是（）。選B非空分別是OlympicOlympilympic。。。即1+2+3+4+5+6+7=28先算長為一的有七個,這個你會吧.接著是大等二的,還記的小學奧數的數線段題吧,其實這題就是讓數有七個點的線段,那么公式是...點數乘段數除以二.即:7*6/2=21.再加上那個七A.29B.28C.16D.17E.7(NOIp2005)設全集I={a,b,c,d,e,f,g,h}，集合A∪B={a,b,c,d,e,f}，A∩C={c,d,e}，A∩～B={a,d}，那么集合A∩B∩C為（）。

A.{c,e}B.{d,e}C.{e}D.{c,d,e}E.{d,f}一般地，對于給定的兩個集合A和集合B的交集是指含有所有既屬于A又屬于B的元素，而沒有其他元素的集合。一組集合的并集是這些集合的所有元素構成的集合，而不包含其他元素。交集就是兩個集合都有的部分，并集就是兩個集合的加起來的全部。交集:表示方法∩。交集是集合的公共部分。并集:表示方法∪。并集是所有空集是不含任何元素

U=全班同學A=班上男同學B=班上女同學A的補集就是B（在U中）BAB集合運算(NOIp2005)字符串“ababacbab”和字線性結構線性表隊列棧線性結構線性表線性表n個數據元素的的有限序列。其特點是除了表頭和表尾外，表中的每一個元素有且僅有唯一的前驅和唯一的后繼，表頭有且只有一個后繼，表尾有且只有一個前驅。線性表n個數據元素的的有限序列。其特點是除了表頭和表尾外，表線性表的修改存入數據下一個元素的地址鏈表順序表線性表的修改存入數據下一個元素的地址鏈表順序表隊列隊列是一種特殊的線性表，對這種線性表，刪除操作只在表頭(稱為隊頭)進行，插入操作只在表尾(稱為隊尾)進行。隊列的修改是按先進先出的原則進行的。隊列隊列是一種特殊的線性表，對這種線性表，刪除操作只在表頭(隊列的修改隊列的修改棧棧是另一種特殊的線性表。這種表只在表頭進行插入和刪除操作。因此，表頭對于棧來說具有特殊的意義，稱為棧頂。相應地，表尾稱為棧底。不含任何元素的棧稱為空棧。棧的修改是按后進先出的原則進行的。棧棧是另一種特殊的線性表。這種表只在表頭進行插入和刪除操作。棧的修改棧的修改歷屆試題(NOIp2005).設棧S的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次入棧，以下出棧序列不可能出現的有（）。A.a,b,c,e,d,f,gB.b,c,a,f,e,g,dC.a,e,c,b,d,f,gD.d,c,f,e,b,a,gE.g,e,f,d,c,b,a(NOIp2006)．某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態(tài)為空，從這一時刻開始的出入記錄為：“進，出，進，進，進，出，出，進，進，進，出,出”。假設車輛入站的順序為1，2，3，……，則車輛出站的順序為（）。A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2E.1,4,3,7,5CEC歷屆試題(NOIp2005).設棧S的初始狀態(tài)為空，元素a,歷屆試題（NOIp2007).地面上有標號為A、B、C的3根細柱,在A柱上放有10個直徑相同中間有孔的圓盤,從上到下次依次編號為1,2,3,……，將A柱上的部分盤子經過B柱移入C柱,也可以在B柱上暫存。如果B柱上的操作記錄為：“進，進，出，進，進，出，出，進，進，出，進，出，出”。那么,在C柱上,從下到上的盤子的編號為（

）。A.243657

B.241257

C.243176D.243675

E.214375（NOIp2008)．設棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，c，f，e，a，則棧S的容量至少應該是（）。A.6B.5C.4D.3E.2DD歷屆試題（NOIp2007).地面上有標號為A、B、C的3歷屆試題（NOIp2006）.設棧S的初始狀態(tài)為空，元素a,b,c,d,e依次入棧，以下出棧序列不可能出現的有（）。A.a,b,c,e,dB.b,c,a,e,dC.a,e,c,b,dD.d,c,e,b,a(NOIP2010)元素R1、R2、R3、R4、R5入棧的順序為R1、R2、R3、R4、R5。如果第1個出棧的是R3，那么第5個出棧的可能是(

)。

A.R1

B.R2

C.R4

D.R5CACD歷屆試題（NOIp2006）.設棧S的初始狀態(tài)為空，元素a樹樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如下圖的樹，其度為3。樹的深度——組成該樹各結點的最大層次，如下圖的樹，其深度為4。樹樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該二叉樹二叉樹是樹的一種重要形態(tài)，只有左、右子樹且順序不能顛倒。邏輯上二叉樹有五種基本形態(tài)：(1)空二叉樹——(a)；(2)只有一個根結點的二叉樹——(b)；(3)右子樹為空的二叉樹——(c)；(4)左子樹為空的二叉樹——(d)；(5)完全二叉樹——(e)

二叉樹二叉樹是樹的一種重要形態(tài)，只有左、右子樹且順序不能顛倒關于二叉樹的兩個重要概念滿二叉樹，一棵深度為K的二叉樹有2K-1個結點，則稱為滿二叉樹。關于二叉樹的兩個重要概念滿二叉樹，一棵深度為K的二叉樹有2K關于二叉樹的兩個重要概念和滿二叉樹對照，只有最下面的兩層結點度小于2，并且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹，稱為完全二叉樹。結論：滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。關于二叉樹的兩個重要概念和滿二叉樹對照，只有最下面的兩層結點歷屆試題（NOIp2005）.完全二叉樹的結點個數為4*N+3，則它的葉結點個數為（）。A.2*NB.2*N-1C.2*N+1D.2*N-2E.2*N+2（NOIp2008）．完全二叉樹共有2*N-1個結點，則它的葉節(jié)點數是（）。A.N-1B.2*NC.ND.2N-1E.N/2（NOIp2006）．高度為n的均衡的二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是高度為n-1的滿二叉樹。在這里，樹高等于葉結點的最大深度，根結點的深度為0，如果某個均衡的二叉樹共有2381個結點，則該樹的樹高為（）。A.10B.11C.12D.13E.210–1ECB歷屆試題（NOIp2005）.完全二叉樹的結點個數為4*歷屆試題(NOIP2009)一個包含n個分支結點（非葉結點）的非空滿k叉樹，k>=1，它的葉結點數目為：()A)nk+1B)nk-1C)(k+1)n-1D.(k-1)n+1(NOIP2010)完全二叉樹的順序存儲方案，是指將完全二叉樹的結點從上到下、從左到右依次存放到一個順序結構的數組中。假定根結點存放在數組的1號位置上，則第k號結點的父結點如果存在的話，應當存放在數組中的（

）號位置。

A.2k

B.2k+1

C.k/2下取整

D.(k+1)/2DC歷屆試題(NOIP2009)一個包含n個分支結點（非葉結點）樹的遍歷（訪問）先序遍歷中序遍歷后序遍歷樹的遍歷（訪問）先序遍歷歷屆試題（NOIp2005）.二叉樹T的寬度優(yōu)先遍歷序列為ABCDEFGHI，已知A是C的父結點，D是G的父結點，F是I的父結點，樹中所有結點的最大深度為3（根結點深度設為0），可知E的父結點可能是（）。A.AB.BC.CD.DE.F（NOIp2006）.已知6個結點的二叉樹的先根遍歷是123456（數字為結點的編號，以下同），后根遍歷是325641，則該二叉樹的可能的中根遍歷是（）A.321465B.321546C.231546D.231465(NOIP2010)一顆二叉樹的前序遍歷序列是ABCDEFG，后序遍歷序列是CBFEGDA，則根結點的左子樹的結點個數可能是（

）。

A．0

B.2

C.4

D.6

BCBCB歷屆試題（NOIp2005）.二叉樹T的寬度優(yōu)先遍歷序列為A數據結構基礎知識課件歷屆試題（NOIp2007）.已知7個節(jié)點的二叉樹的先根遍歷是1245637(數字為結點的編號，以下同)，后根遍歷是4652731，則該二叉樹的可能的中根遍歷是（

）A.4265173

B.4256137C.4231547

D.4256173（NOIp2008）.二叉樹T，已知其先根遍歷是1243576（數字為結點的編號，以下同），后根遍歷是4275631，則該二叉樹的可能的中根遍歷是（）。A.4217536B.2417536C.4217563D.2415736ABDABD歷屆試題（NOIp2007）.已知7個節(jié)點的二叉樹的先根遍數據結構基礎知識課件歷屆試題表達式a*(b+c)-d的后綴表達式是()A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd(NOIP2010)前綴表達式“+3*2+5

12”的值是（

）。

A.23

B.25

C.37

D.65BC歷屆試題表達式a*(b+c)-d的后綴表達式是(數據結構基礎知識課件圖圖由頂點V的集合和邊E的集合組成，如下圖是一無向圖（頂點的前后順序不限）。V={V1,V2,V3,V4,V5}E={(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)}圖圖由頂點V的集合和邊E的集合組成，如下圖是一無向圖（頂點的圖下圖是一有向圖（頂點分先后順序）。V={V1,V2,V3,V4}E={<V1,V2>,<V2,V4>,<V1,V3>,<V3,V4>,<V4,V1>}圖下圖是一有向圖（頂點分先后順序）。圖的性質頂點的度：與頂點關聯的邊的數目。有向圖中等于該頂點的入度與出度之和。

入度——以該頂點為終點的邊的數目和

出度——以該頂點為起點的邊的數目和

度數為奇數的頂點叫做奇點，度數為偶數的點叫做偶點。[定理1]圖中所有頂點的度數之和等于邊數的2倍。因為計算頂點的度數時。每條邊均用到2次。[定理2]任意一個圖一定有偶數個奇點。無向圖中，若任意兩個頂點之間都存在路徑，則稱該無向圖為連通圖。

圖的性質頂點的度：與頂點關聯的邊的數目。有向圖中等于該頂點的圖的遍歷深度優(yōu)先遍歷

1)從某一頂點出發(fā)開始訪問,被訪問的頂點作相應的標記,輸出訪問頂點號.

2)從被訪問的頂點出發(fā),搜索與該頂點有邊的關聯的某個未被訪問的鄰接點再從該鄰接點出發(fā)進一步搜索與該頂點有邊的關聯的某個未被訪問的鄰接點,直到全部接點訪問完畢。圖的遍歷深度優(yōu)先遍歷圖的遍歷廣度優(yōu)先遍歷1）從某個頂點出發(fā)開始訪問，被訪問的頂點作相應的標記，并輸出訪問頂點號；2）從被訪問的頂點出發(fā)，依次搜索與該頂點有邊的關聯的所有未被訪問的鄰接點，并作相應的標記。3）再依次根據2）中所有被訪問的鄰接點，訪問與這些鄰接點相關的所有未被訪問的鄰接點，直到所有頂點被訪問為止。圖的遍歷廣度優(yōu)先遍歷歷屆試題（NOIp2007）.歐拉圖G是指可以構成一個閉回路的圖，且圖G的每一條邊恰好在這個閉回路上出現一次（即一筆畫成）。在以下各個描述中,不一定是歐拉圖的是：（

）。A.圖G中沒有度為奇數的頂點B.包括歐拉環(huán)游的圖(歐拉環(huán)游是指通過圖中每邊恰好一次的閉路徑)C.包括歐拉閉跡的圖(歐拉跡是指通過途中每邊恰好一次的路徑)D.存在一條回路,通過每個頂點恰好一次E.本身為閉跡的圖（NOIp2008）.設T是一棵有n個頂點的樹，下列說法正確的是（）。A.T是連通的、無環(huán)的B.T是連通的，有n-1條邊C.T是無環(huán)的，有n-1條邊D.以上都不對DABC歷屆試題（NOIp2007）.歐拉圖G是指可以構成一個閉回數據結構基礎知識NOIP提高組初賽解析數據結構基礎知識NOIP提高組初賽解析什么是數據結構？數據元素相互之間的關系稱為數據結構。其中數據元素是個廣義概念，是所有能輸入到計算機中并被計算機程序處理的符號的總稱。什么是數據結構？數據元素相互之間的關系稱為數據結構。其中數據四大類基本數據結構集合（無相互關系）線性結構（一對一）樹（一對多）圖（多對多）四大類基本數據結構集合（無相互關系）集合運算(NOIp2005)字符串“ababacbab”和字符串“abcba”的最長公共子串是（）。

A.abcbaB.cbaC.abcD.abE.bcba（NOIp2008）.設字符串S=”O(jiān)lympic”，S的非空子串的數目是（）。選B非空分別是OlympicOlympilympic。。。即1+2+3+4+5+6+7=28先算長為一的有七個,這個你會吧.接著是大等二的,還記的小學奧數的數線段題吧,其實這題就是讓數有七個點的線段,那么公式是...點數乘段數除以二.即:7*6/2=21.再加上那個七A.29B.28C.16D.17E.7(NOIp2005)設全集I={a,b,c,d,e,f,g,h}，集合A∪B={a,b,c,d,e,f}，A∩C={c,d,e}，A∩～B={a,d}，那么集合A∩B∩C為（）。

A.{c,e}B.{d,e}C.{e}D.{c,d,e}E.{d,f}一般地，對于給定的兩個集合A和集合B的交集是指含有所有既屬于A又屬于B的元素，而沒有其他元素的集合。一組集合的并集是這些集合的所有元素構成的集合，而不包含其他元素。交集就是兩個集合都有的部分，并集就是兩個集合的加起來的全部。交集:表示方法∩。交集是集合的公共部分。并集:表示方法∪。并集是所有空集是不含任何元素

U=全班同學A=班上男同學B=班上女同學A的補集就是B（在U中）BAB集合運算(NOIp2005)字符串“ababacbab”和字線性結構線性表隊列棧線性結構線性表線性表n個數據元素的的有限序列。其特點是除了表頭和表尾外，表中的每一個元素有且僅有唯一的前驅和唯一的后繼，表頭有且只有一個后繼，表尾有且只有一個前驅。線性表n個數據元素的的有限序列。其特點是除了表頭和表尾外，表線性表的修改存入數據下一個元素的地址鏈表順序表線性表的修改存入數據下一個元素的地址鏈表順序表隊列隊列是一種特殊的線性表，對這種線性表，刪除操作只在表頭(稱為隊頭)進行，插入操作只在表尾(稱為隊尾)進行。隊列的修改是按先進先出的原則進行的。隊列隊列是一種特殊的線性表，對這種線性表，刪除操作只在表頭(隊列的修改隊列的修改棧棧是另一種特殊的線性表。這種表只在表頭進行插入和刪除操作。因此，表頭對于棧來說具有特殊的意義，稱為棧頂。相應地，表尾稱為棧底。不含任何元素的棧稱為空棧。棧的修改是按后進先出的原則進行的。棧棧是另一種特殊的線性表。這種表只在表頭進行插入和刪除操作。棧的修改棧的修改歷屆試題(NOIp2005).設棧S的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次入棧，以下出棧序列不可能出現的有（）。A.a,b,c,e,d,f,gB.b,c,a,f,e,g,dC.a,e,c,b,d,f,gD.d,c,f,e,b,a,gE.g,e,f,d,c,b,a(NOIp2006)．某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態(tài)為空，從這一時刻開始的出入記錄為：“進，出，進，進，進，出，出，進，進，進，出,出”。假設車輛入站的順序為1，2，3，……，則車輛出站的順序為（）。A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2E.1,4,3,7,5CEC歷屆試題(NOIp2005).設棧S的初始狀態(tài)為空，元素a,歷屆試題（NOIp2007).地面上有標號為A、B、C的3根細柱,在A柱上放有10個直徑相同中間有孔的圓盤,從上到下次依次編號為1,2,3,……，將A柱上的部分盤子經過B柱移入C柱,也可以在B柱上暫存。如果B柱上的操作記錄為：“進，進，出，進，進，出，出，進，進，出，進，出，出”。那么,在C柱上,從下到上的盤子的編號為（

）。A.243657

B.241257

C.243176D.243675

E.214375（NOIp2008)．設棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，c，f，e，a，則棧S的容量至少應該是（）。A.6B.5C.4D.3E.2DD歷屆試題（NOIp2007).地面上有標號為A、B、C的3歷屆試題（NOIp2006）.設棧S的初始狀態(tài)為空，元素a,b,c,d,e依次入棧，以下出棧序列不可能出現的有（）。A.a,b,c,e,dB.b,c,a,e,dC.a,e,c,b,dD.d,c,e,b,a(NOIP2010)元素R1、R2、R3、R4、R5入棧的順序為R1、R2、R3、R4、R5。如果第1個出棧的是R3，那么第5個出棧的可能是(

)。

A.R1

B.R2

C.R4

D.R5CACD歷屆試題（NOIp2006）.設棧S的初始狀態(tài)為空，元素a樹樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如下圖的樹，其度為3。樹的深度——組成該樹各結點的最大層次，如下圖的樹，其深度為4。樹樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該二叉樹二叉樹是樹的一種重要形態(tài)，只有左、右子樹且順序不能顛倒。邏輯上二叉樹有五種基本形態(tài)：(1)空二叉樹——(a)；(2)只有一個根結點的二叉樹——(b)；(3)右子樹為空的二叉樹——(c)；(4)左子樹為空的二叉樹——(d)；(5)完全二叉樹——(e)

二叉樹二叉樹是樹的一種重要形態(tài)，只有左、右子樹且順序不能顛倒關于二叉樹的兩個重要概念滿二叉樹，一棵深度為K的二叉樹有2K-1個結點，則稱為滿二叉樹。關于二叉樹的兩個重要概念滿二叉樹，一棵深度為K的二叉樹有2K關于二叉樹的兩個重要概念和滿二叉樹對照，只有最下面的兩層結點度小于2，并且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹，稱為完全二叉樹。結論：滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。關于二叉樹的兩個重要概念和滿二叉樹對照，只有最下面的兩層結點歷屆試題（NOIp2005）.完全二叉樹的結點個數為4*N+3，則它的葉結點個數為（）。A.2*NB.2*N-1C.2*N+1D.2*N-2E.2*N+2（NOIp2008）．完全二叉樹共有2*N-1個結點，則它的葉節(jié)點數是（）。A.N-1B.2*NC.ND.2N-1E.N/2（NOIp2006）．高度為n的均衡的二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是高度為n-1的滿二叉樹。在這里，樹高等于葉結點的最大深度，根結點的深度為0，如果某個均衡的二叉樹共有2381個結點，則該樹的樹高為（）。A.10B.11C.12D.13E.210–1ECB歷屆試題（NOIp2005）.完全二叉樹的結點個數為4*歷屆試題(NOIP2009)一個包含n個分支結點（非葉結點）的非空滿k叉樹，k>=1，它的葉結點數目為：()A)nk+1B)nk-1C)(k+1)n-1D.(k-1)n+1(NOIP2010)完全二叉樹的順序存儲方案，是指將完全二叉樹的結點從上到下、從左到右依次存放到一個順序結構的數組中。假定根結點存放在數組的1號位置上，則第k號結點的父結點如果存在的話，應當存放在數組中的（

）號位置。

A.2k

B.2k+1

C.k/2下取整

D.(k+1)/2DC歷屆試題(NOIP2009)一個包含n個分支結點（非葉結點）樹的遍歷（訪問）先序遍歷中序遍歷后序遍歷樹的遍歷（訪問）先序遍歷歷屆試題（NOIp2005）.二叉樹T的寬度優(yōu)先遍歷序列為ABCDEFGHI，已知A是C的父結點，D是G的父結點，F是I的父結點，樹中所有結點的最大深度為3（根結點深度設為0），可知E的父結點可能是（）。A.AB.BC.CD.DE.F（NOIp2006）.已知6個結點的二叉樹的先根遍歷是123456（數字為結點的編號，以下同），后根遍歷是325641，則該二叉樹的可能的中根遍歷是（）A.321465B.321546C.231546D.231465(NOIP2010)一顆二叉樹的前序遍歷序列是ABCDEFG，后序遍歷序列是CBFEGDA，則根結點的左子樹的結點個數可能是（

）。

A．0

B.2

C.4

D.6

BCBCB歷屆試題（NOIp2005）.二叉樹T的寬度優(yōu)先遍歷序列為A數據結構基礎知識課件歷屆試題（NOIp2007）.已知7個節(jié)點的二叉樹的先根遍歷是1245637(數字為結點的編號，以下同)，后根遍歷是4652731，則該二叉樹的可能的中根遍歷是（

）A.4265173

B.4256137C.4231547

D.4256173（NOIp2008）.二叉樹T，已知其先根遍歷是1243576（數字為結點的編號，以下同），后根遍歷是4275631，則該二叉樹的可能的中根遍歷是（）。A.4217536B.2417536C.4217563D.2415736ABDABD歷屆試題（NOIp2007）.已知7個節(jié)點的二叉樹的先根遍數據結構基礎知識課件歷屆試題表達式a*(b+c)-d的后綴表達式是()A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd(NOIP2010)前綴表達式“+3*2+5