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

1、NOIP提高組初賽解析數(shù)據(jù)元素相互之間的關(guān)系稱為數(shù)據(jù)結(jié)構(gòu)。其中數(shù)據(jù)元素是個(gè)廣義概念，是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱。 集合（無相互關(guān)系）線性結(jié)構(gòu)（一對一）樹（一對多）圖（多對多）(NOIp2005)字符串“ababacbab”和字符串“abcba”的最長公共子串是（ ）。 A. abcba B. cba C. abc D. ab E. bcba（NOIp2008）. 設(shè)字符串S=”O(jiān)lympic”，S的非空子串的數(shù)目是（ ）。選B 非空分別是Olympic Olympi lympic 。即1+2+3+4+5+6+7=28 先算長為一的有七個(gè),這個(gè)你會(huì)吧.接著是大等二的,還

2、記的小學(xué)奧數(shù)的數(shù)線段題吧,其實(shí)這題就是讓數(shù)有七個(gè)點(diǎn)的線段,那么公式是.點(diǎn)數(shù)乘段數(shù)除以二.即:7*6/2=21.再加上那個(gè)七 A. 29 B. 28 C. 16 D. 17 E. 7(NOIp2005)設(shè)全集I = a, b, c, d, e, f, g, h，集合AB = a, b, c, d, e, f， AC= c, d, e， AB= a, d，那么集合ABC 為（ ）。 A. c, e B. d, e C. e D. c, d, e E. d, f一般地，對于給定的兩個(gè)集合A 和 集合B 的交集是指含有所有既屬于 A 又屬于 B 的元素，而沒有其他元素的集合。一組集合的并集是這些集合的

3、所有元素構(gòu)成的集合，而不包含其他元素。交集就是兩個(gè)集合都有的部分，并集就是兩個(gè)集合的加起來的全部。 交集: 表示方法 。交集是集合的公共部分。 并集 : 表示方法 。并集是所有 空集是不含任何元素 U=全班同學(xué) A=班上男同學(xué) B=班上女同學(xué)A的補(bǔ)集就是B（在U中）BAB線性表隊(duì)列棧n個(gè)數(shù)據(jù)元素的的有限序列。其特點(diǎn)是除了表頭和表尾外，表中的每一個(gè)元素有且僅有唯一的前驅(qū)和唯一的后繼，表頭有且只有一個(gè)后繼，表尾有且只有一個(gè)前驅(qū)。存入數(shù)據(jù)下一個(gè)元素的地址鏈表順序表隊(duì)列是一種特殊的線性表，對這種線性表，刪除操作只在表頭(稱為隊(duì)頭)進(jìn)行，插入操作只在表尾(稱為隊(duì)尾)進(jìn)行。隊(duì)列的修改是按先進(jìn)先出的原則進(jìn)行

4、的。 棧是另一種特殊的線性表。這種表只在表頭進(jìn)行插入和刪除操作。因此，表頭對于棧來說具有特殊的意義，稱為棧頂。相應(yīng)地，表尾稱為棧底。不含任何元素的棧稱為空棧。棧的修改是按后進(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, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, g D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a(NOIp2006)某個(gè)車站呈狹長形，寬度只能

5、容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從 這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出”。假設(shè)車輛入站的 順序?yàn)?1，2，3，則車輛出站的順序?yàn)椋?）。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5CEC（NOIp2007). 地面上有標(biāo)號為A、B、C的3根細(xì)柱, 在A柱上放有10個(gè)直徑相同中間有孔的圓盤, 從上到下次依次編號為1, 2, 3, ，將A柱上的部分盤子經(jīng)過B柱移入C柱, 也可以在B柱上暫存。如果B柱上的操作記錄為

6、：“進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，出，進(jìn)，出，出”。那么, 在C柱上, 從下到上的盤子的編號為（ ）。 A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 C. 2 4 3 1 7 6 D. 2 4 3 6 7 5 E. 2 1 4 3 7 5（NOIp2008)設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，c，f，e，a，則棧S的容量至少應(yīng)該是（ ）。A. 6 B. 5 C. 4 D. 3 E. 2DD（NOIp2006）. 設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e 依次入棧，以下出棧序列不可能出現(xiàn)的有（ ）。A. a, b, c,

7、 e, d B. b, c, a, e, dC. a, e, c, b, d D. 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樹的度也即是寬度，簡單地說，就是結(jié)點(diǎn)的分支數(shù)。以組成該樹各結(jié)點(diǎn)中最大的度作為該樹的度，如下圖的樹，其度為3。樹的深度組成該樹各結(jié)點(diǎn)的最大層次，如下圖的樹，其深度為4。二叉樹是樹的一種重要形態(tài)，只有左、右子樹且順序不能顛倒。邏輯上二叉樹有五種基本形態(tài)：(1)空二叉樹(a)；(2)只有一個(gè)根結(jié)點(diǎn)的二

8、叉樹(b)；(3)右子樹為空的二叉樹(c)；(4)左子樹為空的二叉樹(d)；(5)完全二叉樹(e)滿二叉樹，一棵深度為K的二叉樹有2K-1個(gè)結(jié)點(diǎn)，則稱為滿二叉樹。 A B C D E F G H I J K L M N O 和滿二叉樹對照，只有最下面的兩層結(jié)點(diǎn)度小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置的二叉樹，稱為完全二叉樹。結(jié)論：滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。 A B C D E F G H I J K L 6） （NOIp2005）.完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為4 * N + 3，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（ ）。 A. 2 * N B. 2 * N - 1 C.

9、 2 * N + 1 D. 2 * N - 2 E. 2 * N + 2（NOIp2008）完全二叉樹共有2*N-1個(gè)結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是（ ）。A. N-1 B. 2*N C. N D. 2N-1 E. N/2（NOIp2006）高度為 n 的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為 n-1 的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為 0，如果某個(gè)均衡的二叉樹共有 2381 個(gè)結(jié)點(diǎn)， 則該樹的樹高為（ ）。A. 10 B. 11 C. 12 D. 13 E. 210 1 ECB(NOIP2009)一個(gè)包含n個(gè)分支結(jié)點(diǎn)（非葉結(jié)點(diǎn)）的非空滿k叉樹，k=1，

10、它的葉結(jié)點(diǎn)數(shù)目為：( )A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1(NOIP2010)完全二叉樹的順序存儲(chǔ)方案，是指將完全二叉樹的結(jié)點(diǎn)從上到下、從左到右依次存放到一個(gè)順序結(jié)構(gòu)的數(shù)組中。假定根結(jié)點(diǎn)存放在數(shù)組的1號位置上，則第k號結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在的話，應(yīng)當(dāng)存放在數(shù)組中的（ ）號位置。A.2k B.2k+1 C.k/2下取整 D.(k+1)/2DC先序遍歷中序遍歷后序遍歷（NOIp2005）.二叉樹T的寬度優(yōu)先遍歷序列為A B C D E F G H I，已知A是C的父結(jié)點(diǎn)，D是G的父結(jié)點(diǎn)，F(xiàn)是I的父結(jié)點(diǎn)，樹中所有結(jié)點(diǎn)的最大深度為3（根結(jié)點(diǎn)深度設(shè)為0），可

11、知E的父結(jié)點(diǎn)可能是（ ）。 A. A B. B C. C D. D E. F（NOIp2006）. 已知 6 個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是 1 2 3 4 5 6（數(shù)字為結(jié)點(diǎn)的編號，以下同），后根遍歷是3 2 5 6 4 1，則該二叉樹的可能的中根遍歷是（ ）A. 3 2 1 4 6 5 B. 3 2 1 5 4 6C. 2 3 1 5 4 6 D. 2 3 1 4 6 5(NOIP2010)一顆二叉樹的前序遍歷序列是ABCDEFG，后序遍歷序列是CBFEGDA，則根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)個(gè)數(shù)可能是（ ）。A0 B.2 C.4 D.6 BCBCB（NOIp2007）. 已知7個(gè)節(jié)點(diǎn)的二叉樹的先根遍歷

12、是1 2 4 5 6 3 7(數(shù)字為結(jié)點(diǎn)的編號，以下同)， 后根遍歷是4 6 5 2 7 3 1， 則該二叉樹的可能的中根遍歷是（ ）A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3（NOIp2008）. 二叉樹T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為結(jié)點(diǎn)的編號，以下同），后根遍歷是4 2 7 5 6 3 1，則該二叉樹的可能的中根遍歷是（ ）。A. 4 2 1 7 5 3 6 B. 2 4 1 7 5 3 6 C. 4 2 1 7 5 6 3 D. 2 4 1 5 7 3 6 ABDABD表達(dá)

13、式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圖由頂點(diǎn)V的集合和邊E的集合組成，如下圖是一無向圖（頂點(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=V1,V2,V3,V4 E=, 頂點(diǎn)的度頂點(diǎn)的度：與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目。有向圖中等于該頂點(diǎn)

14、的入度與出度之和。入度以該頂點(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)。無向圖中，若任意兩個(gè)頂點(diǎn)之間都存在路徑，則稱該無向圖為連通圖。深度優(yōu)先遍歷 1)從某一頂點(diǎn)出發(fā)開始訪問,被訪問的頂點(diǎn)作相應(yīng)的標(biāo)記,輸出訪問頂點(diǎn)號. 2)從被訪問的頂點(diǎn)出發(fā),搜索與該頂點(diǎn)有邊的關(guān)聯(lián)的某個(gè)未被訪問的鄰接點(diǎn) 再從該鄰接點(diǎn)出發(fā)進(jìn)一步搜索與該頂點(diǎn)有邊的關(guān)聯(lián)的某個(gè)未被訪問的鄰接點(diǎn),直到全部接點(diǎn)訪問完畢。 廣度優(yōu)先遍歷 1）從某個(gè)頂點(diǎn)出發(fā)開始訪問，被訪問的頂點(diǎn)作相應(yīng)的標(biāo)記，并輸出訪問頂點(diǎn)號； 2）從被訪問的頂點(diǎn)出發(fā)，依次搜索與該頂點(diǎn)有邊的關(guān)聯(lián)的所有未被訪問的鄰接點(diǎn)，并作相應(yīng)的標(biāo)記。 3）再依次根據(jù)2）中所有被訪問的鄰接點(diǎn)，訪問與這些鄰接點(diǎn)相關(guān)的所有未被訪問的鄰接點(diǎn)，直到所有頂點(diǎn)被訪問為止。（NOIp2007）. 歐拉圖G是指可以構(gòu)成一個(gè)閉回路的圖，且圖G的每一條邊恰好在這個(gè)閉回路上出現(xiàn)一次（即一筆畫成）。