初中信息競(jìng)賽數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)與簡(jiǎn)單算法江山二中祝小林老師用計(jì)算機(jī)解決問題一般步驟：具體問題數(shù)學(xué)模型算法編程、調(diào)試得到答案數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)線性表二維數(shù)組與線性表?xiàng)ｊ?duì)列樹圖什么是數(shù)據(jù)結(jié)構(gòu)?計(jì)算機(jī)處理的對(duì)象是什么?數(shù)據(jù)間的關(guān)系表示成數(shù)學(xué)模型有幾種?三種經(jīng)典的數(shù)學(xué)模型查字典——線性關(guān)系家庭成員關(guān)系問題——樹城市道路問題——圖數(shù)據(jù)結(jié)構(gòu)（datastructure）簡(jiǎn)單的解釋：分兩層意思，一是要處理的數(shù)據(jù)有哪些，二是這些數(shù)據(jù)之間的關(guān)系是如何的。數(shù)據(jù)間的關(guān)系有邏輯關(guān)系、存儲(chǔ)關(guān)系，對(duì)于初中學(xué)生通常的數(shù)據(jù)結(jié)構(gòu)討論的是邏輯關(guān)系。數(shù)據(jù)元素邏輯關(guān)系----“邏輯結(jié)構(gòu)”三種基本類型(邏輯)線性結(jié)構(gòu)樹型結(jié)構(gòu)圖狀結(jié)構(gòu)線性樹圖數(shù)據(jù)元素存儲(chǔ)關(guān)系----“存儲(chǔ)結(jié)構(gòu)”二種基本類型順序結(jié)構(gòu)鏈狀結(jié)構(gòu)線性表（一）邏輯關(guān)系：N個(gè)數(shù)據(jù)元素的有限序列存儲(chǔ)關(guān)系：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)12131522343843201 2 3 4 5 6 7 8線性表（二）鏈?zhǔn)酱鎯?chǔ)12131522

^20

^Lhead一個(gè)節(jié)點(diǎn)

三個(gè)信息存儲(chǔ)地址數(shù)據(jù)域指針域1李437錢1313孫119王Null25伍3731趙737張1943周25頭指針為31(趙地址)趙7錢13孫1李43周25伍37張19王null頭二維數(shù)組與線性表二維數(shù)組的一個(gè)形象比喻——多個(gè)縱隊(duì)形成的方塊m*na11a12a13a14……a1na21a22a23a24……a2na31a32a33a34……a3n………………………………am1am2am3am4……amn數(shù)組地址計(jì)算問題題目描述：已知N*(N+1)/2個(gè)數(shù)據(jù)，按行的順序存入數(shù)組b[1],b[2],…中。其中第一個(gè)下標(biāo)表示行，第二個(gè)下標(biāo)表示列。若aij(i>=j,j=1,2,…,,n)存于b[k]中，問：k,i,j之間的關(guān)系如何表示？給定k值，寫出能決定相應(yīng)i,j的算法。a11a21a22a31a32a33………………………………an1an2an3an4……ann答案①K=i*(i-1)/2+j②Read(k);Fori:=1tokdoforj:=1toidoifk=(trunc(I*(I-1)/2)+j)thenwriteln(k,’對(duì)應(yīng)的i,j為：‘,i,’,’,j)棧(strack)特殊的線性表?xiàng)ｍ敚╰op）——棧底(buttom)——操作特點(diǎn)：后進(jìn)先出（LastInFirstOut）空棧an-1a1a3a2an棧底棧頂。。。。出棧入棧棧（考題分析）（1998）棧S初始狀態(tài)為空，現(xiàn)有5個(gè)元素組成的序列{1，2，3，4，5}，對(duì)該序列在棧S上一次進(jìn)行如下操作（從序列中的1開始，出棧后不再進(jìn)棧）：進(jìn)棧、進(jìn)棧、進(jìn)棧、出棧、進(jìn)棧、出棧、進(jìn)棧。問出棧的元素序列是______(A){5,4,3,2,1}(B){2,1}(C){2,3}(D){3,4}3、1、3：棧的應(yīng)用舉例---漢諾塔最下面的先移動(dòng)目標(biāo)盤，最上面的最后移到目標(biāo)盤。后進(jìn)先出。

abcHanoi的遞歸實(shí)現(xiàn)Procedurehanoi(n:integer;a,b,c:char);beginhanoi(n-1,a,c,b);

writeln(a,’--’,c);/tot:=tot+1;hanoi(n-1,b,a,c);end;歷年初賽試題2007noip-16．地面上有標(biāo)號(hào)為A、B、C的三根柱，在A柱上放有10個(gè)直徑相同中間有孔的圓盤，從上到下依次編號(hào)為1，2，3……，將A柱上的部分盤子經(jīng)過B柱移入C柱，也可以在B柱上暫存。如果B柱上的操作記錄為“進(jìn)、進(jìn)、出、進(jìn)、進(jìn)、出、出、進(jìn)、進(jìn)、出、進(jìn)、出、出”。那么，在c柱上，從下到上的編號(hào)為（

）。

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

52005noip-20.設(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,d,c,b,f,g

D.d,c,f,e,b,a,g

E.g,e,f,d,c,b,a

2004noip-14.

某個(gè)車站呈狹長形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從這一時(shí)刻開始的出入記錄為：“進(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,3,5,4,6D.1,3,5,6,7E.1,3,6,5,7隊(duì)列(queue)特殊線性表：允許插入的一端稱為隊(duì)尾(rear)，允許刪除的一端稱為隊(duì)頭(front)。先進(jìn)先出（進(jìn)出的序列一致）循環(huán)隊(duì)列a1a2a3a4……an出隊(duì)列入隊(duì)列循環(huán)隊(duì)列15678RF一.判斷是否是空:iffront=rearthenempty;二.判斷隊(duì)列為滿:(rear+1)modm=front三、獲取隊(duì)頭元素：若為空輸出提示；若不空則x:=q[front];樹(生活模型,幾個(gè)結(jié)點(diǎn),三個(gè)”一”)根、葉子、中間結(jié)點(diǎn)、子樹（關(guān)系）結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)（樹的度）結(jié)點(diǎn)的層次、樹的深度。森林,有序樹、無序樹樹的表示：畫樹，括號(hào)樹的存儲(chǔ)：表二叉樹ACFEBDG層次123二叉樹特點(diǎn)：每個(gè)結(jié)點(diǎn)至多只有二棵子樹，并且二叉樹的子樹有左右之分。五種形態(tài)第i層至多有

個(gè)結(jié)點(diǎn)（i>=1）深度為K的二叉樹最多有

個(gè)結(jié)點(diǎn)（K>=1）度為2的結(jié)點(diǎn)數(shù)與度為0的結(jié)點(diǎn)數(shù)間的關(guān)系？下列兩種二叉樹兒子和父親序號(hào)的關(guān)系？ACFEBDGACFEBD滿二叉樹完全二叉樹歷年初賽題2003noip16．一個(gè)高度為h的二叉樹最小元素?cái)?shù)目是()。

A)2h+lB)hC)2h-1D)2hE)2h-lNoip-2006-14．高度為n的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0，如果某個(gè)均衡的二叉樹共有2381個(gè)結(jié)點(diǎn)，則該樹的樹高為（）。A.10B.11C.12D.132005noip-4.完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為11，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（）。

A.4B.3C.5D.2E.6

2004noip-16.

滿二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)為N，則它的結(jié)點(diǎn)總數(shù)為（）。A.NB.2*NC.2*N–1D.2*N+1E.2N–1二叉樹的存儲(chǔ)ACEDBHFG節(jié)點(diǎn)節(jié)點(diǎn)值左孩子爸爸右孩子1A2032B0143C0154D6275E8306F0407G0408H05012345678二叉樹的遍歷先（根）序遍歷（DLR）中（根）序遍歷(LDR)后（根）序遍歷(LRD)ACEDBHFG例題分析給出一棵二叉樹的中序遍歷：DBGEACHFI與后序遍歷：DGEBHIFCA，畫出此二叉樹。ACEDBHFGI歷年試題Noip2006-20.已知6個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是123456（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），后根遍歷是325641，則該二叉樹的可能的中根遍歷是（）A.321465B.321546C.213546D.2314652007noip-20．已知7個(gè)節(jié)點(diǎn)的二叉樹的先根遍歷是1

2

4

5

6

3

7（數(shù)字為節(jié)點(diǎn)的編號(hào)，以下同），中根遍歷是4

2

6

5

1

7

3，則該二叉樹的后根遍歷是（

）。

A．4

6

5

2

7

3

1

B．4

6

5

2

1

3

7

c．4

2

3

1

5

4

7

D．4

6

5

3

1

7

2

二叉樹的寬度遍歷按層的遍歷，第一層，第二層。。。。2005noip-19.二叉樹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），可知F的父結(jié)點(diǎn)是（）。

A.無法確定B.BC.CD.DE.E普通樹轉(zhuǎn)換成二叉樹1、普通有序樹轉(zhuǎn)換成二叉樹方法：：凡是兄弟就用線連起來，然后只留下父母到其第一個(gè)子女的連線，去掉該結(jié)點(diǎn)與其它孩子的連線。ABCDEFGHIABCDEFGHI森林轉(zhuǎn)換成二叉樹2、一個(gè)森林轉(zhuǎn)換為二叉樹：方法：先將森林中每一棵樹變?yōu)槎鏄?，后將各二叉樹的根結(jié)點(diǎn)視為兄弟從左到右連在一起，就形成了一棵二叉樹。ABCDEFGHIJABCDEFGHIJ圖的結(jié)構(gòu):頂點(diǎn)，邊

圖的概念:分有向無向圖，頂點(diǎn)度，路徑(簡(jiǎn)單路,回路,環(huán))，連通,強(qiáng)連通圖）ACEDB無向圖ACEDB有向圖頂點(diǎn)的分類:奇點(diǎn),偶點(diǎn)及個(gè)數(shù)關(guān)系呢?邊數(shù)與圖的總度數(shù)的關(guān)系如何?連通圖與強(qiáng)連通圖的關(guān)系?圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣頂點(diǎn):一個(gè)字符型的數(shù)組邊如下:1452312345101100210001301001410100500000表示什么情況?圖的存儲(chǔ)結(jié)構(gòu)鄰接表(指針加數(shù)組)a:array[1..n,0..e]ofinteger;A[i,0]表示頂點(diǎn)i有幾條邊,a[I,j]的值呢?如何求點(diǎn)的度?145231323422133412454213513圖的遍歷深度優(yōu)先搜索

越深越好)

先訪問結(jié)點(diǎn)I,

再深度優(yōu)先搜索結(jié)點(diǎn)I的鄰接結(jié)點(diǎn).

不能訪問所有結(jié)點(diǎn),則換一個(gè)結(jié)點(diǎn)再深度優(yōu)先搜索圖.14523從第結(jié)點(diǎn)2出發(fā)試試??圖的遍歷寬度優(yōu)先搜索(廣度,按層搜索):

先訪問結(jié)點(diǎn)I,

再寬度優(yōu)先搜索結(jié)點(diǎn)I的鄰接結(jié)點(diǎn).

不能訪問所有結(jié)點(diǎn),則換一個(gè)結(jié)點(diǎn)再寬度優(yōu)先搜索圖.14523從第結(jié)點(diǎn)2出發(fā)試試??一筆畫問題：無奇度的點(diǎn)或有兩個(gè)

2004noip-19.

在下圖中，從頂點(diǎn)（）出發(fā)存在一條路徑可以遍歷圖中的每條邊一次，而且僅遍歷一次。

A.A點(diǎn)B.B點(diǎn)C.C點(diǎn)D.D點(diǎn)E.E點(diǎn)生成樹問題生活中模型:交通網(wǎng)干線.無向圖的最小生成樹（貪心思想）Prim算法，適用于點(diǎn)少的圖Kruskal算法，適用于邊少的圖Prim算法(通過找邊加入點(diǎn))將1號(hào)節(jié)點(diǎn)置入集合S中。找到所有連接S中的節(jié)點(diǎn)和非S中的節(jié)點(diǎn)的邊中的權(quán)值最小的那一條，并標(biāo)記這條邊，同時(shí)將連接的非S中的節(jié)點(diǎn)加入S集合,修正非S節(jié)點(diǎn)到S的最小距離。重復(fù)2步驟，直到所有節(jié)點(diǎn)都在S中了。1243561231231212Kruskal算法找到連接兩個(gè)不同連通分量（由已標(biāo)記的邊構(gòu)成的）的邊中，權(quán)值最小的那一條，標(biāo)記這條邊。重復(fù)1步驟，直到所有節(jié)點(diǎn)都在同一連通分量中。1243561231231212圖的最小生成樹

2005noip-5.平面上有五個(gè)點(diǎn)，坐標(biāo)如下A（5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以這五點(diǎn)作為完全圖G的頂點(diǎn)，每?jī)牲c(diǎn)之間的直線距離是圖G中對(duì)應(yīng)邊的權(quán)值。以下哪條邊不是圖G的最小生成樹中的邊（）。

A.ADB.BDC.CDD.DEE.EA最短路問題

生活中模型:最優(yōu)乘車單源最短路——

Dijkstra算法多源最短路——Floyd-Warshall算法Dijkstra算法Dijkstra算法中心——++124331632+∞+∞+∞0Dist值4321節(jié)點(diǎn)號(hào)32654選擇標(biāo)記擴(kuò)展任意頂點(diǎn)對(duì)之間的最短路假設(shè)求從vi到vj的最短路徑,如果vi到vj有弧,則它們的路徑為cost[i,j],否則需要進(jìn)行n次試探,首先考慮(viv1

vj

),比較它與(vivj

)的大小,取較短者為中間節(jié)點(diǎn)序號(hào)不大于1的最短路徑,ji假如(vi,…,v2)和(v2,…,

vj

)都是中間節(jié)點(diǎn)序號(hào)不大于1的最短路徑,那么(vi,…,v2,…,

vj

)可能是中間節(jié)點(diǎn)序號(hào)不大于2的最短路徑.將它和中間節(jié)點(diǎn)序號(hào)不大于1的最短路相比較,從中選出中間節(jié)點(diǎn)的序號(hào)不大于2的最短路徑之后,再增加一個(gè)頂點(diǎn)v3,繼續(xù)進(jìn)行試探.這樣進(jìn)行n次試探后,最后得到必然是vi到vj的最短路徑。Floyd-Warshall算法過程dist數(shù)組的初始值為所有邊的情況Fork:=1TovtxnumDo{枚舉中間點(diǎn)}Fori:=1TovtxnumDo{枚舉起點(diǎn)}Forj:=1TovtxnumDo{枚舉終點(diǎn)}Ifdist[i,k]+dist[k,j]<dist[i,j]Then

dist[i,j]:=dist[i,k]+dist[k,j]最后的結(jié)果仍舊保存在dist數(shù)組中圖的拓?fù)浣Y(jié)構(gòu)拓?fù)渑判蝽旤c(diǎn)表示活動(dòng)的網(wǎng)——AOV-網(wǎng)例如課程選擇中課程之間的關(guān)系關(guān)鍵路徑邊表示活動(dòng)的網(wǎng)——AOE-網(wǎng)求圖中總長最長的路徑例如計(jì)算工程所需時(shí)間拓?fù)渑判蛩惴▽ふ胰攵葹?的節(jié)點(diǎn)將找到的節(jié)點(diǎn)放入隊(duì)列中，刪除所有這個(gè)節(jié)點(diǎn)引出的邊重復(fù)1，直至沒有度為0的節(jié)點(diǎn)如果有節(jié)點(diǎn)不在隊(duì)列中，則說明原圖中有環(huán)，否則無環(huán)。1253647拓?fù)渑判蛲負(fù)渑判虻姆椒ǎ海膳袛嘤邢驁D是否是有環(huán)）①從圖中選擇一個(gè)入度為0的頂點(diǎn)且輸出之；②從圖中刪掉該頂點(diǎn)及其所有以該頂點(diǎn)為弧尾的?。ㄅc之相鄰的所有頂點(diǎn)的入度減1）；③反復(fù)執(zhí)行這兩個(gè)步驟，直到所有的頂點(diǎn)都被輸出。輸出的序列就是這個(gè)無環(huán)有向圖的拓?fù)湫蛄校ㄔ诿恳粫r(shí)刻，