初中信息竞赛数据结构

数据结构与简单算法江山二中祝小林老师用计算机解决问题一般步骤：具体问题数学模型算法编程、调试得到答案数据结构什么是数据结构线性表二维数组与线性表栈队列树图什么是数据结构?计算机处理的对象是什么?数据间的关系表示成数学模型有几种?三种经典的数学模型查字典——线性关系家庭成员关系问题——树城市道路问题——图数据结构（datastructure）简单的解释：分两层意思，一是要处理的数据有哪些，二是这些数据之间的关系是如何的。数据间的关系有逻辑关系、存储关系，对于初中学生通常的数据结构讨论的是逻辑关系。数据元素逻辑关系----“逻辑结构”三种基本类型(逻辑)线性结构树型结构图状结构线性树图数据元素存储关系----“存储结构”二种基本类型顺序结构链状结构线性表（一）逻辑关系：N个数据元素的有限序列存储关系：顺序存储结构、链式存储结构12131522343843201 2 3 4 5 6 7 8线性表（二）链式存储12131522

^20

^Lhead一个节点

三个信息存储地址数据域指针域1李437钱1313孙119王Null25伍3731赵737张1943周25头指针为31(赵地址)赵7钱13孙1李43周25伍37张19王null头二维数组与线性表二维数组的一个形象比喻——多个纵队形成的方块m*na11a12a13a14……a1na21a22a23a24……a2na31a32a33a34……a3n………………………………am1am2am3am4……amn数组地址计算问题题目描述：已知N*(N+1)/2个数据，按行的顺序存入数组b[1],b[2],…中。其中第一个下标表示行，第二个下标表示列。若aij(i>=j,j=1,2,…,,n)存于b[k]中，问：k,i,j之间的关系如何表示？给定k值，写出能决定相应i,j的算法。a11a21a22a31a32a33………………………………an1an2an3an4……ann答案①K=i*(i-1)/2+j②Read(k);Fori:=1tokdoforj:=1toidoifk=(trunc(I*(I-1)/2)+j)thenwriteln(k,’对应的i,j为：‘,i,’,’,j)栈(strack)特殊的线性表栈顶（top）——栈底(buttom)——操作特点：后进先出（LastInFirstOut）空栈an-1a1a3a2an栈底栈顶。。。。出栈入栈栈（考题分析）（1998）栈S初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是______(A){5,4,3,2,1}(B){2,1}(C){2,3}(D){3,4}3、1、3：栈的应用举例---汉诺塔最下面的先移动目标盘，最上面的最后移到目标盘。后进先出。

abcHanoi的递归实现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．地面上有标号为A、B、C的三根柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3……，将A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在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

52005noip-20.设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序列不可能出现的是（）。

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.

某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（）。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队列(queue)特殊线性表：允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。先进先出（进出的序列一致）循环队列a1a2a3a4……an出队列入队列循环队列15678RF一.判断是否是空:iffront=rearthenempty;二.判断队列为满:(rear+1)modm=front三、获取队头元素：若为空输出提示；若不空则x:=q[front];树(生活模型,几个结点,三个”一”)根、叶子、中间结点、子树（关系）结点的度：结点拥有的子树数（树的度）结点的层次、树的深度。森林,有序树、无序树树的表示：画树，括号树的存储：表二叉树ACFEBDG层次123二叉树特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。五种形态第i层至多有

个结点（i>=1）深度为K的二叉树最多有

个结点（K>=1）度为2的结点数与度为0的结点数间的关系？下列两种二叉树儿子和父亲序号的关系？ACFEBDGACFEBD满二叉树完全二叉树历年初赛题2003noip16．一个高度为h的二叉树最小元素数目是()。

A)2h+lB)hC)2h-1D)2hE)2h-lNoip-2006-14．高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。A.10B.11C.12D.132005noip-4.完全二叉树的结点个数为11，则它的叶结点个数为（）。

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

2004noip-16.

满二叉树的叶结点个数为N，则它的结点总数为（）。A.NB.2*NC.2*N–1D.2*N+1E.2N–1二叉树的存储ACEDBHFG节点节点值左孩子爸爸右孩子1A2032B0143C0154D6275E8306F0407G0408H05012345678二叉树的遍历先（根）序遍历（DLR）中（根）序遍历(LDR)后（根）序遍历(LRD)ACEDBHFG例题分析给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA，画出此二叉树。ACEDBHFGI历年试题Noip2006-20.已知6个结点的二叉树的先根遍历是123456（数字为结点的编号，以下同），后根遍历是325641，则该二叉树的可能的中根遍历是（）A.321465B.321546C.213546D.2314652007noip-20．已知7个节点的二叉树的先根遍历是1

2

4

5

6

3

7（数字为节点的编号，以下同），中根遍历是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的宽度优先遍历序列为ABCDEFGHI，已知A是C的父结点，D是G的父结点，F是I的父结点，数中所有结点的最大深度为3，（根结点深度设为0），可知F的父结点是（）。

A.无法确定B.BC.CD.DE.E普通树转换成二叉树1、普通有序树转换成二叉树方法：：凡是兄弟就用线连起来，然后只留下父母到其第一个子女的连线，去掉该结点与其它孩子的连线。ABCDEFGHIABCDEFGHI森林转换成二叉树2、一个森林转换为二叉树：方法：先将森林中每一棵树变为二叉树，后将各二叉树的根结点视为兄弟从左到右连在一起，就形成了一棵二叉树。ABCDEFGHIJABCDEFGHIJ图的结构:顶点，边

图的概念:分有向无向图，顶点度，路径(简单路,回路,环)，连通,强连通图）ACEDB无向图ACEDB有向图顶点的分类:奇点,偶点及个数关系呢?边数与图的总度数的关系如何?连通图与强连通图的关系?图的存储结构邻接矩阵顶点:一个字符型的数组边如下:1452312345101100210001301001410100500000表示什么情况?图的存储结构邻接表(指针加数组)a:array[1..n,0..e]ofinteger;A[i,0]表示顶点i有几条边,a[I,j]的值呢?如何求点的度?145231323422133412454213513图的遍历深度优先搜索

越深越好)

先访问结点I,

再深度优先搜索结点I的邻接结点.

不能访问所有结点,则换一个结点再深度优先搜索图.14523从第结点2出发试试??图的遍历宽度优先搜索(广度,按层搜索):

先访问结点I,

再宽度优先搜索结点I的邻接结点.

不能访问所有结点,则换一个结点再宽度优先搜索图.14523从第结点2出发试试??一笔画问题：无奇度的点或有两个

2004noip-19.

在下图中，从顶点（）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次。

A.A点B.B点C.C点D.D点E.E点生成树问题生活中模型:交通网干线.无向图的最小生成树（贪心思想）Prim算法，适用于点少的图Kruskal算法，适用于边少的图Prim算法(通过找边加入点)将1号节点置入集合S中。找到所有连接S中的节点和非S中的节点的边中的权值最小的那一条，并标记这条边，同时将连接的非S中的节点加入S集合,修正非S节点到S的最小距离。重复2步骤，直到所有节点都在S中了。1243561231231212Kruskal算法找到连接两个不同连通分量（由已标记的边构成的）的边中，权值最小的那一条，标记这条边。重复1步骤，直到所有节点都在同一连通分量中。1243561231231212图的最小生成树

2005noip-5.平面上有五个点，坐标如下A（5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以这五点作为完全图G的顶点，每两点之间的直线距离是图G中对应边的权值。以下哪条边不是图G的最小生成树中的边（）。

A.ADB.BDC.CDD.DEE.EA最短路问题

生活中模型:最优乘车单源最短路——

Dijkstra算法多源最短路——Floyd-Warshall算法Dijkstra算法Dijkstra算法中心——++124331632+∞+∞+∞0Dist值4321节点号32654选择标记扩展任意顶点对之间的最短路假设求从vi到vj的最短路径,如果vi到vj有弧,则它们的路径为cost[i,j],否则需要进行n次试探,首先考虑(viv1

vj

),比较它与(vivj

)的大小,取较短者为中间节点序号不大于1的最短路径,ji假如(vi,…,v2)和(v2,…,

vj

)都是中间节点序号不大于1的最短路径,那么(vi,…,v2,…,

vj

)可能是中间节点序号不大于2的最短路径.将它和中间节点序号不大于1的最短路相比较,从中选出中间节点的序号不大于2的最短路径之后,再增加一个顶点v3,继续进行试探.这样进行n次试探后,最后得到必然是vi到vj的最短路径。Floyd-Warshall算法过程dist数组的初始值为所有边的情况Fork:=1TovtxnumDo{枚举中间点}Fori:=1TovtxnumDo{枚举起点}Forj:=1TovtxnumDo{枚举终点}Ifdist[i,k]+dist[k,j]<dist[i,j]Then

dist[i,j]:=dist[i,k]+dist[k,j]最后的结果仍旧保存在dist数组中图的拓扑结构拓扑排序顶点表示活动的网——AOV-网例如课程选择中课程之间的关系关键路径边表示活动的网——AOE-网求图中总长最长的路径例如计算工程所需时间拓扑排序算法寻找入度为0的节点将找到的节点放入队列中，删除所有这个节点引出的边重复1，直至没有度为0的节点如果有节点不在队列中，则说明原图中有环，否则无环。1253647拓扑排序拓扑排序的方法：（可判断有向图是否是有环）①从图中选择一个入度为0的顶点且输出之；②从图中删掉该顶点及其所有以该顶点为弧尾的弧（与之相邻的所有顶点的入度减1）；③反复执行这两个步骤，直到所有的顶点都被输出。输出的序列就是这个无环有向图的拓扑序列（在每一时刻，