信息学知识

《信息学知识》由会员分享，可在线阅读，更多相关《信息学知识（9页珍藏版）》请在金锄头文库上搜索。

1、赛前知识点梳理_数据结构一）基本概念线性表：数据间关系是线性的，每个元素只有一个前趋，一个后续；树：有着明显的层次关系，每个元素只有一个前趋，但有多个后续；图：数据之间的关系是任意，每个元素的前趋和后续个数是不定的；引入：柯尼斯堡七桥问题，能否从A地发出，各座桥恰好通过一次，最后回到出发地A?画问题”。答案是否定的，因为，对于每一个顶点，不论如何经过，必须有一条进路和一条岀路，与每一 个顶点相邻的线（关联边）必须是偶数条（除起点和终点外），而此图中所有点都只有奇数条关联边。在 后面的应用中，我们将专门讨论这个问题。定义：简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据

2、结构，定 义为：graph= （V，E）。V是一个非空有限集合，代表顶点（结点），E代表边的集合，一般用（Vx, Vy） 表示，其中，Vx, Vy属于V。分类：如果边是没有方向的，称为“无向图”。表示时用一队圆括号表示，如：（Vx, Vy），（Vy， Vx），当然这两者是等价的。并且说边（Vx，Vy）依附于（相关联）顶点Vx和Vy。如果边是带箭头的， 则称为“有向图”，表示时用一队尖括号表示，此时Vx, Vy与VY, VX是不同的，如VX, VY的起点为 VX,终点为VY。有向图中的边又称为弧。起点称为弧头、终点称为弧尾。PVy, Vx是不同的，如Vx, Vy的起点为Vx,终点为Vy。有向图中

3、的边又称为弧。起点称为弧头、终点称为弧尾。相邻：若两个结点 U、 V 之间有一条边连接，则称这两个结点 U、 V 是关联的。带权图：两点间不仅有连接关系，还标明了数量关系（距离、费用、时间等）。 图的阶：图中结点的个数。结点的度：图中与结点A关联的边的数目，称为结点A的度。入度：在有向图中，把以结点V为终点 的边的数目称为V的入度；出度：在有向图中，把以结点U为起点的边的数目称为U的出度；奇点：度数为奇数的结点； 偶点：度数为偶数的结点； 终端结点：在有向图中，出度为0的结点；定理1：图中所有结点的度数之和等于边数的2倍:定理2：任意一个图一定有偶数个奇点:连通：如果图中结点U, V之间存在一

4、条从U通过若干条边、点到达V的通路，则称U、V是连通的。路（径）：从一个结点出发，沿着某些边连续地移动而到达另一个指定的结点，这种依次由结点和边 组成的序列，叫“路”或者“路径”。路径长度：路径上边的数目。简单路径：在一个路径上，各个结点 都不相同，则称为简单路径。回路：起点和终点相同的路径，称为回路，或“环”。连通图：对于图G中的任一对不同顶点U、V,都有一条（U, V）通路，则称图G是连通的。强连通图：在有向图G中，每一对结点之间都有路径的图。网络：带权的连通图。二）表示方法巾 UR1、邻接矩阵表示法（顺序存储）72CO 5C O匸:口 |匚:口1 15 g 1. g 2 请大家自己画出图

5、（C）如上图（B）和10的邻接袒阵分别如下:A =的邻接表分别如下,0 1 12、接表表示法（链式存储法）A）、图（B）nilnil3ml无向图：AI, J = 1当I与J两个结点相邻时= 0 当 I 与 J 两个结点不相邻时，或 I=J（1=I, J=图中结点数）且有：AI，J=AJ, I，即邻接矩阵是对称的。 如上图（A）的邻接矩阵如下：当I与J两个结点相邻，磁值为PI，J时当I与J两个结点不相邻时，或I=J（三）图的遍历1、概念：从图中某一结点出发系统地访问图中所有结点,使每个结点恰好被访问一次,这种运算称 图的遍历。为了避免重复访问某个结点，可以设一个标志数组visitedI，未访问时

6、值为FALSE，访问一 次后就改为 TRUE。2、分类：深度优先遍历和广度优先遍历。3、深度优先遍历：类似于树的先序遍历，从图中某个结点V0出发，访问此结点，然后依次访问从V0 的未被访问的邻接点出发进行深度优先遍历，直到图中所有和V0有路径相通的结点均被访问到。若此时 图中尚有结点未被访问，则另选图中一个未被访问的结点V1作为起点，重复上述过程，直至图中所有结 点都被访问到为止。 如下面两个图的深度优先遍历结果分别为：a， b， c， d， e， g， fV1， V2， V4， V8， V5， V3， V6， V7的所有结点，然后再分别从这些结点出发进行广度优先遍历，直到图中所有被访问过的结

7、点的相邻结点都被访问到。若此时图中还有结点尚未被访问，则另选图中一个未被访问过的结点作为起点，重复上述过程直到图中所有结点都被访问到为止。如上面两个图的广度优先遍历结果分别为：a，b，d，e，f，c，gV1，V2，V3，V4，V5，V6，V7，V8 （四）最小生成树问题如果图G=（V, E）是一个连通的无向图，则从G的任一个顶点出发进行一次深度优先遍历或广度优先 遍历便可遍历全部图。设遍历过程中走过的边的集合为TE（G），显然T=（V，TE）是G的一个连通子图，且T本身也是一 棵树（无根树），则称T是G的生成树。1210上图（B）和（C）是对（A）分别进行深度和广度优先遍历得到的一种生成树。注

8、意，图的生成树是10从顶点了出发姑舍不唯一的。对于一棵带权树，生成树中各边的权值之和称为这棵生成树的代价，代价最小的生成树称为“最 小代价生成树”。如何求最小代价生成树呢？ R.C.Prim提出的求最小代价生成算法是常用的一种，设图的顶点集合V共 有 n 个顶点，则算法如下：1、设置一个顶点的集合S1和一个边的集合TE，S1和TE的初始状态均为空集;2、选定图中的一个顶点K,从K开始生成最小代价生成树，将K加入到集合S1；3、重复下列操作，直到选取了 n-1条边：选取一条权值最小的边（X, Y），其中XUS1, not（YuSl）。将顶点Y加入集合S1，边（X, Y）加入集合TE。下图给出了上

9、图（A）的最小代价生成树的生成过程:（五）一笔画问题 请你设计一个程序，对给定的一个图，由计算机判断能否一笔画出，若能请打印出一笔画的先后顺序若不能则打印“NO SOLUTION!”。1. 欧拉路：在无孤立结点的图G中，若存在一条路，经过图中每条边一次且仅一次，则称此路为 欧拉路。如下图（左）可以构成一个欧拉路2. 欧拉回路：若存在一条路，经过图中每条边一次且仅一次，且回到原来位置，则称此路为欧拉 回路。因此，七桥问题转换成了欧拉回路问题。如下图（右）可以构成一个欧拉路3. 欧拉图：存在欧拉回路的图，称为欧拉图。4. 定理1：存在欧拉路的条件：图是连通的，且存在0 个或2个奇点。5. 定理2：

10、存在欧拉回路的条件：图是连通的，且存在0个奇点。6. 哈密尔顿图：无孤立结点的连通图，若存在一条路，经过图中每一个结点一次且仅一次，则称 为哈密尔顿图。7. 哈密尔顿环：是一条沿着图的n边环行的路径，它访问每一个结点一次且仅一次，并且返回到 它的开始位置。（七）拓扑排序问题 一项大的工程可以看作是由若干个称为“活动”的子工程组成的集合，这些子工程之间必定存在一种 先后关系，即某些子工程必须在其它一些工程完成之后才能开始，我们可以用有向图表示工程间关系，子 工程（活动）为顶点，活动之间的先后关系为有向边，这种有向图称为顶点表示活动的网络，又称为AOV 网。在AOV网中，如果有一条从顶点Vi到Vj

11、的路径，则说Vi是Vj的前趋，Vj是Vi的后续。如果有弧 Vi, Vj，则称Vi是Vj的直接前趋，Vj是Vi的直接后续。VI, VJ，则称VI是VJ的直接前趋，VJ是 VI的直接后续。拓扑排序是把AOV网中所有顶点排成一个线性序列（拓扑序列），如果有弧Vi，Vj，则 序列中顶点 Vi 在 Vj 之前。一个存在回路的有向图顶点是不能排成拓扑序列的，因为有回路的有向图的边 体现的先后关系不是非自反的。任何没有回路的有向图，其顶点都可以排成一个拓扑序列。而且得到的拓 扑序列是不唯一的。如对下图进行拓扑排序可以得到多个拓扑序列，如： 02143567、01243657、02143657、 012435

12、67。 在这个AOV网络之中，工程1和过程2显然可以同时进行，先后无所谓。但工程4显然要等工程1和 工程 2 都完成以后才可进行，工程3要等到工程 4 完成以后才可进行（当然工程1 也要完成后，显然）， 工程 5、又要等到工程3完成以后（工程4 也必须先完成，显然），工程6则要等到工程 4 完成后进行， 工程 7要等到工程 3、5、6 都完成后才能进行。（八）关键路径问题利用AOV网络，对其进行拓扑排序能对工程中活动的先后顺序作出安排。但一个活动的完成总需要一 定的时间，为了能估算出某个活动的开始时间，找出那些影响工程完成时间的最主要的活动，我们可以利 用带权的有向网，图中的顶点表示一个活动结

13、束（开始）的事件，图中的边表示活动，边上的权表示完成 该活动所需要的时间。这种用边表示活动的网络，称为AOE网络。下图表示一个具有12个活动的AOE网络。图中有8个顶点，分别表示事件（状态）0到7,其中，0 表示开始状态， 7表示结束状态；边上的权表示完成该活动所需要的时间。在实际中， AOE 网络没有回路，存在唯一的入度为 0 的开始顶点，存在唯一的出度为 0 的结束顶点。 在 AOE 网络上，要研究的问题是完成整个工程至少需要多少时间，哪些活动是影响工程进度的关键。在 AOE 网络中，有些活动可以并行地进行，所以，完成工程的最少时间是从开始顶点到结束顶点的最 长路径的长度。关键路径就是指从

14、开始结点到完成结点的具有最大长度的路径。关键路径上的活动称为关键活动。关 键路径的长度就是完成整个工程所需要的最短时间。（十）图的综合应用举例11999 年初赛试题高中组第二大题题目将ln定义为求在一个平面中用n条直线所能确定的最大区域数目。例如，当n=1时，11=2。进 一步考虑，用n条折成角的直线（角度任意），放在平面上，能确定的最大区域数目zn是多少？例如， 当 n=1 时，z1=2。 分析1、第n条直线与前n-1条直线最多有n-1个交点，它们将第n条直线分割成n段，每一段都不在同 一个区域内，且将其所在区域一分为二，即多出n个区域。也就是说L=Ln-1+n,nL =L +nn n-1L

15、 =L +n-1n-1n-2L = +22 L1L =L +110L =10将等式左边和右边分别相加得：L =（n+1）*n/2+1n2、将第n条折线当作两条射线来考虑，每条射线与前2*（n-1）条射线最多有2*（n-1）个交点，它们将 每条射线分割成2n-1段，从而多出2*（2n-1）个区域，由于是折线，连接折线交点的两段线段是处于同一 区域内的，因而要少算一个区域，即只多出4*n-3个区域。也就是说：Z =Z +4n-3，同样地n n-1Z =Z +4（n-1）-3n-1n-2Z =Z +4*2-3Z =Z +4*1-310Z =10将等式左边和右边分别相加得：Z =4*（n+l）*n/2+l-3*n=2n2-n+ln2求关键路径（2001 年初赛）问题描述设有一个工程网络如下图表示（无环路的有向图）：其中，顶点表示活动，表示工程开始，表示工 程结束（可变，用N表示），边上的数字表示活动延续的时间。编程求关键路径。32001 年初赛问题描述设在A、B两个城市之间有N个路站（如下图中的S1,且N10