數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)課件

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)NOIP提高組初賽解析數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)NOIP提高組初賽解析什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)元素相互之間的關(guān)系稱為數(shù)據(jù)結(jié)構(gòu)。其中數(shù)據(jù)元素是個(gè)廣義概念，是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)元素相互之間的關(guān)系稱為數(shù)據(jù)結(jié)構(gòu)。其中數(shù)據(jù)四大類基本數(shù)據(jù)結(jié)構(gòu)集合（無(wú)相互關(guān)系）線性結(jié)構(gòu)（一對(duì)一）樹(shù)（一對(duì)多）圖（多對(duì)多）四大類基本數(shù)據(jù)結(jié)構(gòu)集合（無(wú)相互關(guān)系）集合運(yùn)算(NOIp2005)字符串“ababacbab”和字符串“abcba”的最長(zhǎng)公共子串是（）。

A.abcbaB.cbaC.abcD.abE.bcba（NOIp2008）.設(shè)字符串S=”O(jiān)lympic”，S的非空子串的數(shù)目是（）。選B非空分別是OlympicOlympilympic。。。即1+2+3+4+5+6+7=28先算長(zhǎng)為一的有七個(gè),這個(gè)你會(huì)吧.接著是大等二的,還記的小學(xué)奧數(shù)的數(shù)線段題吧,其實(shí)這題就是讓數(shù)有七個(gè)點(diǎn)的線段,那么公式是...點(diǎn)數(shù)乘段數(shù)除以二.即:7*6/2=21.再加上那個(gè)七A.29B.28C.16D.17E.7(NOIp2005)設(shè)全集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}一般地，對(duì)于給定的兩個(gè)集合A和集合B的交集是指含有所有既屬于A又屬于B的元素，而沒(méi)有其他元素的集合。一組集合的并集是這些集合的所有元素構(gòu)成的集合，而不包含其他元素。交集就是兩個(gè)集合都有的部分，并集就是兩個(gè)集合的加起來(lái)的全部。交集:表示方法∩。交集是集合的公共部分。并集:表示方法∪。并集是所有空集是不含任何元素

U=全班同學(xué)A=班上男同學(xué)B=班上女同學(xué)A的補(bǔ)集就是B（在U中）BAB集合運(yùn)算(NOIp2005)字符串“ababacbab”和字線性結(jié)構(gòu)線性表隊(duì)列棧線性結(jié)構(gòu)線性表線性表n個(gè)數(shù)據(jù)元素的的有限序列。其特點(diǎn)是除了表頭和表尾外，表中的每一個(gè)元素有且僅有唯一的前驅(qū)和唯一的后繼，表頭有且只有一個(gè)后繼，表尾有且只有一個(gè)前驅(qū)。線性表n個(gè)數(shù)據(jù)元素的的有限序列。其特點(diǎn)是除了表頭和表尾外，表線性表的修改存入數(shù)據(jù)下一個(gè)元素的地址鏈表順序表線性表的修改存入數(shù)據(jù)下一個(gè)元素的地址鏈表順序表隊(duì)列隊(duì)列是一種特殊的線性表，對(duì)這種線性表，刪除操作只在表頭(稱為隊(duì)頭)進(jìn)行，插入操作只在表尾(稱為隊(duì)尾)進(jìn)行。隊(duì)列的修改是按先進(jìn)先出的原則進(jìn)行的。隊(duì)列隊(duì)列是一種特殊的線性表，對(duì)這種線性表，刪除操作只在表頭(隊(duì)列的修改隊(duì)列的修改棧棧是另一種特殊的線性表。這種表只在表頭進(jìn)行插入和刪除操作。因此，表頭對(duì)于棧來(lái)說(shuō)具有特殊的意義，稱為棧頂。相應(yīng)地，表尾稱為棧底。不含任何元素的棧稱為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的。棧棧是另一種特殊的線性表。這種表只在表頭進(jìn)行插入和刪除操作。棧的修改棧的修改歷屆試題(NOIp2005).設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次入棧，以下出棧序列不可能出現(xiàn)的有（）。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)．某個(gè)車站呈狹長(zhǎng)形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從這一時(shí)刻開(kāi)始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出”。假設(shè)車輛入站的順序?yàn)?，2，3，……，則車輛出站的順序?yàn)椋ǎ?。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).設(shè)棧S的初始狀態(tài)為空，元素a,歷屆試題（NOIp2007).地面上有標(biāo)號(hào)為A、B、C的3根細(xì)柱,在A柱上放有10個(gè)直徑相同中間有孔的圓盤,從上到下次依次編號(hào)為1,2,3,……，將A柱上的部分盤子經(jīng)過(guò)B柱移入C柱,也可以在B柱上暫存。如果B柱上的操作記錄為：“進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，出，進(jìn)，出，出”。那么,在C柱上,從下到上的盤子的編號(hào)為（

）。A.243657

B.241257

C.243176D.243675

E.214375（NOIp2008)．設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，c，f，e，a，則棧S的容量至少應(yīng)該是（）。A.6B.5C.4D.3E.2DD歷屆試題（NOIp2007).地面上有標(biāo)號(hào)為A、B、C的3歷屆試題（NOIp2006）.設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e依次入棧，以下出棧序列不可能出現(xiàn)的有（）。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入棧的順序?yàn)镽1、R2、R3、R4、R5。如果第1個(gè)出棧的是R3，那么第5個(gè)出棧的可能是(

)。

A.R1

B.R2

C.R4

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

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

）號(hào)位置。

A.2k

B.2k+1

C.k/2下取整

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

）。

A．0

B.2

C.4

D.6

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

）A.4265173

B.4256137C.4231547

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

12”的值是（

）。

A.23

B.25

C.37

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

入度——以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目和

出度——以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目和

度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫做偶點(diǎn)。[定理1]圖中所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。因?yàn)橛?jì)算頂點(diǎn)的度數(shù)時(shí)。每條邊均用到2次。[定理2]任意一個(gè)圖一定有偶數(shù)個(gè)奇點(diǎn)。無(wú)向圖中，若任意兩個(gè)頂點(diǎn)之間都存在路徑，則稱該無(wú)向圖為連通圖。

圖的性質(zhì)頂點(diǎn)的度：與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目。有向圖中等于該頂點(diǎn)的圖的遍歷深度優(yōu)先遍歷

1)從某一頂點(diǎn)出發(fā)開(kāi)始訪問(wèn),被訪問(wèn)的頂點(diǎn)作相應(yīng)的標(biāo)記,輸出訪問(wèn)頂點(diǎn)號(hào).

2)從被訪問(wèn)的頂點(diǎn)出發(fā),搜索與該頂點(diǎn)有邊的關(guān)聯(lián)的某個(gè)未被訪問(wèn)的鄰接點(diǎn)再?gòu)脑撪徑狱c(diǎn)出發(fā)進(jìn)一步搜索與該頂點(diǎn)有邊的關(guān)聯(lián)的某個(gè)未被訪問(wèn)的鄰接點(diǎn),直到全部接點(diǎn)訪問(wèn)完畢。圖的遍歷深度優(yōu)先遍歷圖的遍歷廣度優(yōu)先遍歷1）從某個(gè)頂點(diǎn)出發(fā)開(kāi)始訪問(wèn)，被訪問(wèn)的頂點(diǎn)作相應(yīng)的標(biāo)記，并輸出訪問(wèn)頂點(diǎn)號(hào)；2）從被訪問(wèn)的頂點(diǎn)出發(fā)，依次搜索與該頂點(diǎn)有邊的關(guān)聯(lián)的所有未被訪問(wèn)的鄰接點(diǎn)，并作相應(yīng)的標(biāo)記。3）再依次根據(jù)2）中所有被訪問(wèn)的鄰接點(diǎn)，訪問(wèn)與這些鄰接點(diǎn)相關(guān)的所有未被訪問(wèn)的鄰接點(diǎn)，直到所有頂點(diǎn)被訪問(wèn)為止。圖的遍歷廣度優(yōu)先遍歷歷屆試題（NOIp2007）.歐拉圖G是指可以構(gòu)成一個(gè)閉回路的圖，且圖G的每一條邊恰好在這個(gè)閉回路上出現(xiàn)一次（即一筆畫(huà)成）。在以下各個(gè)描述中,不一定是歐拉圖的是：（

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

A.abcbaB.cbaC.abcD.abE.bcba（NOIp2008）.設(shè)字符串S=”O(jiān)lympic”，S的非空子串的數(shù)目是（）。選B非空分別是OlympicOlympilympic。。。即1+2+3+4+5+6+7=28先算長(zhǎng)為一的有七個(gè),這個(gè)你會(huì)吧.接著是大等二的,還記的小學(xué)奧數(shù)的數(shù)線段題吧,其實(shí)這題就是讓數(shù)有七個(gè)點(diǎn)的線段,那么公式是...點(diǎn)數(shù)乘段數(shù)除以二.即:7*6/2=21.再加上那個(gè)七A.29B.28C.16D.17E.7(NOIp2005)設(shè)全集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}一般地，對(duì)于給定的兩個(gè)集合A和集合B的交集是指含有所有既屬于A又屬于B的元素，而沒(méi)有其他元素的集合。一組集合的并集是這些集合的所有元素構(gòu)成的集合，而不包含其他元素。交集就是兩個(gè)集合都有的部分，并集就是兩個(gè)集合的加起來(lái)的全部。交集:表示方法∩。交集是集合的公共部分。并集:表示方法∪。并集是所有空集是不含任何元素

U=全班同學(xué)A=班上男同學(xué)B=班上女同學(xué)A的補(bǔ)集就是B（在U中）BAB集合運(yùn)算(NOIp2005)字符串“ababacbab”和字線性結(jié)構(gòu)線性表隊(duì)列棧線性結(jié)構(gòu)線性表線性表n個(gè)數(shù)據(jù)元素的的有限序列。其特點(diǎn)是除了表頭和表尾外，表中的每一個(gè)元素有且僅有唯一的前驅(qū)和唯一的后繼，表頭有且只有一個(gè)后繼，表尾有且只有一個(gè)前驅(qū)。線性表n個(gè)數(shù)據(jù)元素的的有限序列。其特點(diǎn)是除了表頭和表尾外，表線性表的修改存入數(shù)據(jù)下一個(gè)元素的地址鏈表順序表線性表的修改存入數(shù)據(jù)下一個(gè)元素的地址鏈表順序表隊(duì)列隊(duì)列是一種特殊的線性表，對(duì)這種線性表，刪除操作只在表頭(稱為隊(duì)頭)進(jìn)行，插入操作只在表尾(稱為隊(duì)尾)進(jìn)行。隊(duì)列的修改是按先進(jìn)先出的原則進(jìn)行的。隊(duì)列隊(duì)列是一種特殊的線性表，對(duì)這種線性表，刪除操作只在表頭(隊(duì)列的修改隊(duì)列的修改棧棧是另一種特殊的線性表。這種表只在表頭進(jìn)行插入和刪除操作。因此，表頭對(duì)于棧來(lái)說(shuō)具有特殊的意義，稱為棧頂。相應(yīng)地，表尾稱為棧底。不含任何元素的棧稱為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的。棧棧是另一種特殊的線性表。這種表只在表頭進(jìn)行插入和刪除操作。棧的修改棧的修改歷屆試題(NOIp2005).設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次入棧，以下出棧序列不可能出現(xiàn)的有（）。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)．某個(gè)車站呈狹長(zhǎng)形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從這一時(shí)刻開(kāi)始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出”。假設(shè)車輛入站的順序?yàn)?，2，3，……，則車輛出站的順序?yàn)椋ǎ?。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).設(shè)棧S的初始狀態(tài)為空，元素a,歷屆試題（NOIp2007).地面上有標(biāo)號(hào)為A、B、C的3根細(xì)柱,在A柱上放有10個(gè)直徑相同中間有孔的圓盤,從上到下次依次編號(hào)為1,2,3,……，將A柱上的部分盤子經(jīng)過(guò)B柱移入C柱,也可以在B柱上暫存。如果B柱上的操作記錄為：“進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，出，進(jìn)，出，出”。那么,在C柱上,從下到上的盤子的編號(hào)為（

）。A.243657

B.241257

C.243176D.243675

E.214375（NOIp2008)．設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，c，f，e，a，則棧S的容量至少應(yīng)該是（）。A.6B.5C.4D.3E.2DD歷屆試題（NOIp2007).地面上有標(biāo)號(hào)為A、B、C的3歷屆試題（NOIp2006）.設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e依次入棧，以下出棧序列不可能出現(xiàn)的有（）。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入棧的順序?yàn)镽1、R2、R3、R4、R5。如果第1個(gè)出棧的是R3，那么第5個(gè)出棧的可能是(

)。

A.R1

B.R2

C.R4

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

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

）號(hào)位置。

A.2k

B.2k+1

C.k/2下取整

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

）。

A．0

B.2

C.4

D.6

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

）A.4265173

B.4256137C.4231547

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