NOIP初赛复习

.初赛复习 一 题型 单项选择题(共 10 题,每题 1.5 分,共计 15 分) 不定项选择题(共 10 题,每题 1.5 分,共计 15 分。多选或少选均不得分) 问题求解(共 2 题,每题 5 分,共计 10 分) 阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 完善程序 (前 5 空,每空 2 分,后 6 空,每空 3 分,共 28 分) 二 知识要点 1、计算机的基本常识 计算机产生与发展 、计算机的系统及工作原理、网络的基本知识 、网上搜索信息 的基本方法 、计算机中有关数、编码的基本常识 2、数据结构的基本知识 线性表的知识 :(1)栈 : 先进后出(FILO)(2)队列:先进先出(FIFO) 树的基本知识 图的基本知识 3、数学知识:如集合、排列组合等 4、算法的基本知识 (1)初等算法(计数、统计、数学运算等) (2)排序算法(冒泡法、插入排序、合并排序、快速排序) (3)查找(顺序查找、二分法) (4)回溯算法

数制及数制转换
1.数制 常用的进制:十进制(D) 二进制(B) 八进制(O) 十六进制(H) 基数: 10 2 8 16 位权: 10 的幂数 2 的幂数 8 的幂数 16 的幂数 数字符号: 0~9 0~2 0~7 0~9、A~F 2.数制转换 ? 2、8、16 或其他进制~10 进制的转换: ∑(该位上的数×该位上的位权值) 2 1 0 -1 -2 -3 如: (101.101)B=1×2 +0×2 +1×2 +1×2 +0×2 +1×2 =(5.625)D ? 10 进制~2、8、16 或其他进制的转换: 对于整数,采用除进制倒取余法;对于小数,采用乘进制正取整法 如: (13.6875)D=(1101.1011)B ▲注意: 一个二进制的小数能完全准确地转换成十进制小数, 但一个十进制的小数不一 定能完全准确地转换成二进制小数,如 0.1,可根据精度要求转换到某一位为止。 ? 2 进制与 8 进制之间的转换:每三个二进制位对应一个八进制位,以小数点分隔 如:(111010.110)2=(72.6)8 ? 2 进制与 16 进制之间的转换:每四个二进制位对应一个十六进制位 如:(111010.110)2=(3A.C)16 ? 8 进制与 16 进制之间的转换可借助二进制

1

初赛题 2005 年 3. 以下二进制数的值与十进制数23.456 的值最接近的是( )。 A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.1111 2005年 12. (3725)8 + (B)16的运算结果是( )。 A. (3736)8 B. (2016)10 C. (11111100000)2 D. (3006)10 E. (7E0)16 3.计算机中数的表示 ? 正负数的表示:用最高位表示符号位,规定用 0 表示正,用 1 表示负。其表示范围由硬 件决定,当使用 8 位寄存器时,字长为 8 位,则无符号数的范围是 0~255;有符号数 的范围是-128~127。当使用 16 位寄存器时 ,字长为 16 位,则无符号数的范围是 0~ 65535;有符号数的范围是-32768~32767 ? 定点数和浮点数: 根据小数点位置的不同约定两种表示方法, 一种是小数点位置固定不 变,称为定点数。一种是小数点位置可以浮动,称为浮点数。 定点数只能表示定点整数和定点纯小数,对于定点整数,约定小数点的位置在最低位; 对于定点纯小数,约定小数点的位置在符号位之后。 浮点数能表示既有整数又有小数的数,通常由阶码和尾数组成,类似指数形式 4.原码、反码、补码 ? 原码:普通二进制形式,比较自然的表示法,最高位表示符号,0 为正,1 为负。优点: 简单易懂;缺点:异号数加减法运算复杂。 如:+50 的原码为 00110010 -50 的原码为 10110010 ? 反码:为计算补码方便而引入。一个正数的反码是原码本身;一个负数的反码是除符号 位之外各位取反,即 0 变 1,1 变 0。一个数的反码的反码是原码本身。 如:-50 的反码为 00110010 -50 的反码为 11001101 ? 补码:加减法运算方便,减法可以转换为加法。一个正数的补码是原码本身,一个负数 的补码是其反码的低位加 1。一个数的补码的补码是原码本身。 如:+50 的补码为 00110010 -50 的补码为 11001110 ? 两个数的补码之和等于两个数和的补码,符号位参与运算。 5.BCD 码(二—十进制编码) 一个十进制数在计算机中以二进制形式存放, 需要一个转换过程。 但在将所有位的数字 输入完之前又不可能转换成完整的二进制数, 所以可将每一位数字用二进制进行编码, 称为 二进制编码的十进制数。 常用的二—十进制数的编码是 8421 码,用四位二进制数表示一位十进制数,自左至右 对应的位权是 8、4、2、1。应该指出的是,四位二进制数有 0000~1111 十六种状态,而十 进制数 0~9 只取 0000~1001 十种状态,其余六种不用。 如:(498.12)D 的 BCD 码是 0100,1001,1000.0001,0010

二 数据结构的基本知识 (1)栈 : 先进后出(FILO)

(2)队列:先进先出(FIFO)
如:某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。已知某时刻该车站状 态为空,从这一时刻开始的出入记录为: “进,出,进,进,出,进,进,进,出,出,进,

2

出” 。假设车辆入站的顺序为 1,2,3,??,则车辆出站的顺序为( ) 。 A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 1, 3, 6, 5, 7

E.

2003 19 已知元素(8,25,14,87,51,90,6,19,20),问这些元素以怎样的顺序进 入栈,才能使出栈的顺序满足:8 在 51 前面;90 在 87 的后面;20 在 14 的后面;25 在 6 的前面;19 在 90 的后面。( )。 A)20,6,8,51,90,25,14,19,87 B)51,6,19,20,14,8,87,90,25 C)19,20,90,8,6,25,51,14,87 D)6,25,51,8,20,19,90,87,14 E)25,6,8,51,87,90,19,14,20 设栈 S 和队列 Q 的初始状态为空,元素 e 1 ,e 2 ,e 3 ,e 4 ,e 5 ,e 6 依次通过栈 S,一个 元素出栈后即进入队列 Q,若出队的顺序为 e 2 ,e 4 ,e 3 ,e 6 ,e 5 ,e 1 ,则栈 S 的容量至少应该为( ) 。 A)2 B)3 C)4 D)5

(3)树 树的概念

图1 ? 树是一种重要的非线性数据结构, 如图 1 所示, 它比较形象地反映各结点之间一对多的 层次关系。如家族族谱、各种社会组织机构等。 树是由一个或多个结点组成的有限集合 T,其中: 1.必须有一个特定的结点,称为是整棵树的根,这个结点没有前驱。 2.其余结点分为 m 个互不相交的有限子集:T1,T2,T3,??,Tm,每一个子集是一 棵子树。 树的定义是一个递归定义,即用树来定义树。
3

?

?

树结构没有封闭的回路。

一、树的术语 1.结点的度——某个结点的子树的个数称为该结点的度。如图 1 中 A 结点的度为 3,C 结点的度为 1,G 结点的度为 0。 2.树的度——即树的宽度,是所有结点的度中的最大值,如图 1 的树,其度为 3; 3.树的深度——组成该树各结点的最大层次,如图 1 的树,其深度为 4; 4.森林——指若干棵互不相交的树的集合,如图 1,去掉根结点 A,其原来的三棵子树 T1、T2、T3 的集合{T1,T2,T3}就为森林; 5.有序树——指树中同层结点从左到右有次序排列,它们之间的次序不能互换,这样 的树称为有序树,否则称为无序树。 6.端结点——也叫叶子结点,如 K、L、F、G、M、I、J。 7.分枝结点——度不为 0 的结点,如 B、C、D、E、H。 8.某结点的子树的根称为该结点的儿子(或孩子),反之,该结点称为是儿子结点的 父亲 (或双亲) , 同一个父亲结点的儿子结点称为兄弟, 父亲结点与儿子结点之间用枝相连。 根结点到每一个分枝结点或叶子结点的路径是唯一的。 二、树的表示 1.自然界的树形表示法:如图 1,用结点和边表示树,一班用于分析问题。 2.括号表示法——也称广义表表示法:先将根结点放入一对圆括号中,然后把它的子 树由左至右的顺序放入括号中, 对子树也采用同样的方法处理, 同层子树放入它们根结点后 面的圆括号中,同层子树之间用逗号隔开。如图 1 可写成如下形式: (A(B(E(K,L),F),C(G),D(H(M),I,J))) 三、树的存储 树的存储一般有两种: 1.静态的二维数组或一维记录数组(将儿子的下标序列作为一个记录域) : 如图 1 的树中各结点关系可用下表表示,故可用数组存储 下标 1 2 3 4 5 6 7 8 9 10 11 12 13 结点 A B C D E F G H I J K L M 2 5 7 8 11 0 0 13 0 0 0 0 0 儿子的下标序列 3 6 0 9 12 0 0 0 0 0 0 0 0 4 0 0 10 0 0 0 0 0 0 0 0 0

4

二维数组存储结构: Const n=树的度; Max=结点数的上限; Type treetype=array[1..max,1..n+1] of integer; Var tree:treetype; 一维记录数组存储结构: Const n=树的度; Max=结点数的上限; Type node=record Data:datatype;{如字符型,存储结点数据} Children:array[1..n] of integer; End; treetype=array[1..max] of integer; Var tree:treetype; 2.动态的多重链表:由于树中可以有多个元素,所以用多重链表来描述比较方便。每 个结点由数据域和 n(n 为树的度)个指针域共 n+1 个域组成。其表示方法如下:

Const n=树的度; Type treetype=^node; node=record Data:datatype; next:array[1..n] of treetype; End; Var root:treetype; A B C G E K L F H N I J D

显然,取树的度作为每个结点的链域数(即指向儿子结点的指针数) ,虽使得各种算法 简化,但由于各结点的指针域个数不同,存在很多空链域,这就造成了空间的大量浪费。 能不能在减少浪费空链域的前提下, 寻找一种既使得每个结点的结构相同, 又方便运算 的树形式呢?设想,每个结点的度都为 2,则空指针域比重会变小,就能达到这个目的。下 面我们看另一种数据结构——二叉树。

5

第二节

二叉树

一、二叉树的概念 ? 二叉树(Binary Tree)是由 n 个结点组成的有限集合(n>=0)。此集合或是一个空集, 或是由一个根结点加上两根分别称为左子树和右子树的互不相交的二叉树组成。 ? 二叉树也是递归定义的,但二叉树与树是两个不同的概念。 1.二叉树可以是一个空集,而树至少要有一个结点; 2.树的子树无顺序之分,而二叉树的左子树、右子树顺序不能颠倒。 ? 所以,二叉树不是树的特殊情况,但前面的树的树语对二叉树仍然适用。 1.二叉树的基本形态: 二叉树是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:

(1)空二叉树——(a); (2)只有一个根结点的二叉树——(b); (3)右子树为空的二叉树——(c); (4)左子树为空的二叉树——(d); (5)完全二叉树——(e) 2.两个重要的概念: (1) 满二叉树——除最底一层的结点的度数为 0 外,其余结点的度数均为 2。 (2) 完全二叉树——如果一棵二叉树只有最下面的两层结点度小于 2,并且最下面一层 的结点都集中在该层最左边的若干位置, 则称为完全二叉树。 也就是说, 对于一棵满二叉树, 若从最底一层的最右边开始,连续向左缺少几个结点,就可得到一棵完全二叉树。满二叉树 一定是完全二叉树。 如图 2 为满二叉树,图 3 为完全二叉树

6

图2

图3 二、二叉树的性质 I-1 1.在二叉树中,第 I 层的结点总数不超过 2 ; 2.在深度为 K 的二叉树中,结点总数不超过 2 -1 3. 对于任意一棵二叉树, 如果其叶结点数为 N0, 而度数为 2 的结点总数为 N2, 则 N0=N2+1; 4.有 N 个结点的完全二叉树各结点如果用顺序方式表示,则结点之间有如下关系:
K

图4

图5

·如果 I<>1,则其父结点的编号为 I/2; ·如果 2*I<=N,则其左儿子(即左子树的根结点)的编号为 2*I;若 2*I>N,则无左儿子 ·如果 2*I+1<=N,则其右儿子的结点编号为 2*I+1;若 2*I+1>N,则无右儿子。 2003 5. 一个高度为 h 的二叉树最小元素数目是( A) 2h+1 B) h C) 2h-1 D) 2h )。 E) 2h-1

7

四、二叉树的存储结构: 1.顺序存储方式:将各结点按层次编号,顺序存储到一维数组中,通过下标的顺序确 定父子关系,或存储到一维记录数组中,这种存储方式适用于满二叉树和完全二叉树,因为 中间无空结点。 const n=树的结点数上限; type node=record data:datatype; {数据域类型} prt,lch,rch:0..n; {父结点、左儿子、右儿子结点编号} end; treetype=array[1..n] of node; {二叉树的顺序表类型} var tree:treetype;

图6 2.链表存储方式:对于图 6 所示的不完全二叉树,如用顺序存储方式就有些浪费空间, 这样我们可以采用链表存储方式。 静态的链表存储方式: 我们可以设立一个一维数组存放各结点的数据, 再设立两个一维 数组或一个二维数组来分别表示每一个结点对应的左指针和右指针。 数组下标: 数组 D: 左指针数组 L: 右指针数组 R: 1 A 2 3 2 B 4 5 3 C 6 0 4 D 0 0 5 E 7 0 6 F 0 8 7 G 0 0 8 H 0 0

动态的链表存储方式:因为二叉树中的每一个结点有一个数据元素和左右两个子结点, 所以我们采用双重链表(也叫二重链表、二叉链表)进行存储。 Type bitrtype=^bnode; {结点指针类型} Bnode=record Data:datatype; {结点值类型} Lch,Rch:bitrtype; {左指针域和右指针域} End; Var bt:bitrtype; {头指针,指向根结点}
8

A B D G E F H C

五、二叉树的遍历运算(递归定义) 所谓遍历是指按照一定的规律不重复地访问树中的每一个结点,在访问到每个结点时, 可以打印该结点的值,或是取出该结点的信息,或是修改结点的值,或作其他的处理等。三 种遍历规则和遍历过程如下: 1.先序遍历(根左右) :访问根;按先序遍历左子树;按先序遍历右子树 二叉链表: procedure pre(bt:bitrtype); begin if bt<>nil then 访问处理 bt^.data; pre(bt^.lch);{递归遍历左子树} pre(bt^.rch);{递归遍历右子树} end; end; 顺序一维记录存储结构: procedure pre(i:integer); begin if i<>0 then 访问处理 tree[i].data; pre(tree[i].lch);{递归遍历左子树} pre(tree[i].rch);{递归遍历右子树} end; end

2.中序遍历(左根右) :按中序遍历左子树;访问根;按中序遍历右子树 二叉链表: procedure infer(bt:bitrtype); begin if bt<>nil then infer(bt^.lch);{递归遍历左子树} 访问处理 bt^.data; infer(bt^.rch);{递归遍历右子树} end; end; 顺序一维记录存储结构: procedure infer(i:integer); begin if i<>0 then infer(tree[i].lch);{递归遍历左子树} 访问处理 tree[i].data; infer(tree[i].rch);{递归遍历右子树} end; end

3.后序遍历(左右根) :按后序遍历左子树;按后序遍历右子树;访问根 二叉链表: procedure post(bt:bitrtype); begin if bt<>nil then post(bt^.lch);{递归遍历左子树} post(bt^.rch);{递归遍历右子树} 访问处理 bt^.data; 顺序一维记录存储结构: procedure post(i:integer); begin if i<>0 then post(tree[i].lch);{递归遍历左子树} post(tree[i].rch);{递归遍历右子树} 访问处理 tree[i].data;
9

end; end;

end; end

六、由二叉树的两种遍历顺序确定树结构 从上述遍历规则可以看出, 前序遍历的第一个字符和后序遍历的最后一个字符为根, 中 序遍历中位于根左方的子串和右方的子串分别反映了左子树和右子树的结构, 因此, 二叉树 的形态可由中序与后序或者是中序与前序唯一确定,而前序与后序不能唯一确定一棵二叉 树,可对应多种形态的二叉树。 例:输入两种遍历顺序的字符串,输出另一种遍历顺序 2004 5. 二叉树 T,已知其前序遍历序列为 1 2 4 3 5 7 6,中序遍历序列为 4 2 1 5 7 3 6, 则其后序遍历序列为( ) 。 A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1 2003 9. 表达式(1+34)*5-56/7 的后缀表达式为( ) 。 A) 1+34*5-56/7 B) -*+1 34 5/56 7 C) 1 34 +5*56 7/D) 1 34 5* +56 7/E) 1 34+5 56 7-*/ 2005 13. 二叉树T的宽度优先遍历序列为A B C D E F G H I,已知A是C的父结点,D 是G 的 父结点,F 是I 的父结点,树中所有结点的最大深度为3(根结点深度设为0),可知E 的父结点可能是( )。 A. A B. B C. C D. D E. F 1.由中序 s1 与后序 s2 得出前序的过程 procedure solve1(s1,s2:string); var k:integer; begin if length(s2)=1 then 输出 s2 else begin k:=pos(s2[lengtth(s2)],s1); 输出子树根 s1[k]; if k>1 then solve1(copy(s1,1,k-1),copy(s2,1,k-1)); if k<length(s1) then solve1(copy(s1,k+1,length(s1)-k),copy(s2,k,length(s2)-k)); end; end; 2.由中序 s1 与前序 s2 得出后序的过程 procedure solve2(s1,s2:string); var k:integer; begin if length(s2)=1 then 输出 s2 else begin k:=pos(s2[1],s1); if k>1 then solve2(copy(s1,1,k-1),copy(s2,2,k)); if k<length(s1)
10

then solve2(copy(s1,k+1,length(s1)-k),copy(s2,k+1,length(s2)-k)); end; 输出子树根 s1[k]; end; 主程序:readln(s1,s2);solve1(s1,s2); readln(s1,s2);solve1(s1,s2); 七、二叉树的重要应用 1.二叉排序树 2 ? 排序的方法有很多种,常见的几种简单排序法算法复杂性为 O(n )级,是不是有效 率更高的算法呢?有的,利用树的性质构造的二叉排序树就是其中的一种。 ? 所谓二叉排序树是指具有下列性质的非空二叉树: (1)若根结点的左子树不空,则左子树的所有结点值均小于根结点值; (2)若根结点的右子树不空,则右子树的所有结点值均不小于根结点值; (3)根结点的左右子树也分别为二叉排序树。 显然,对二叉排序树进行中序遍历,可得出结点值为递增的排序序列。 ? 如何将无序序列 a1,a2,a3,?,an 构造成一棵二叉排序树呢? (1)令 a1 为二叉树的根; (2)若 a2<a1,令 a2 为 a1 左子树的根结点,否则令 a2 为 a1 右子树的根结点 (3)对 a3,?,an 递归重复步骤 2 2.最优二叉树——哈夫曼树 ? 路径: 从树中一个结点到另一个结点的分支构成两个结点之间的路径, 路径上的分 支数目称作路径长度。 ? 树的路径长度是从树根到每一个结点的路径长度之和。 ? 在处理实际问题时,出于某种目的,可以给叶子结点赋上某个实数值,这个值被称 为该叶结点的权,该二叉树被称为带权二叉树。则这个树的带权路径长度定义为: WPL= ? ?

?WiLi (n 为叶结点个数)
i ?1

n

由 n 个带权叶结点可以构成多种二叉树,WPL 最小的二叉树成为最优二叉树,也叫 哈夫曼树。 哈夫曼算法——即哈夫曼树的构造方法 ①将已知的 n 个结点看作一个森林 F,即每个结点都是一棵只有根结点的树; ②从中选取权值最小的两棵树作为左右子树合并成一颗新二叉树, 且令二叉树的根 结点的权值为左右子树权值之和; ③从 F 中删除已合并过的两棵树,同时将新树加入; ④重复②③,直到 F 中只含有一棵树为止,这棵树就是哈夫曼树。 注:合并时约定把权值小的作为左子树

11

{哈夫曼树的结构定义} Const n=叶结点数的上限; m=2*n-1; {m 为构造完的哈夫曼树的结点个数} Type node=record Data:integer; Prt,lch,rch,lth:0..m; {父、左、右指针和路径长度} Wtype=array[1..n] of integer; {存储 n 个叶结点权值} Treetype=array[1..m] of node; {哈夫曼树的结构类型} Var tree:treetype; {哈夫曼算法过程} Procedure hufm(w:wtype;var tree:treetype;var bt:integer;) {bt 为根序号} Function min(h:integer):integer; {在前 h 个结点中选择父指针为 0 且} Begin {权值最小的结点} m1:=32767; for p:=1 to h do if (tree[p].prt=0) and (tree[p].data<m1) then begin i:=p; m1:=tree[p].data; end; min:=I; end; begin fillchar(tree,sizeof(tree),0); {构造初始集合 F} for I:=1 to n do read(tree[i].data); for k:=n+1 to m do begin {计算以 k 为根的左、右儿子} i:=min(k-1);tree[i].prt:=k;tree[k].lch:=I; j:=min(k-1);tree[j].prt:=k;tree[k].rch:=j; tree[k],data:=tree[i].data+tree[j].data; end; bt:=m; end;

堆 普通树或森林的遍历 1.普通树转换成二叉树

例: 1.用顺序存储方式建立一棵有 31 个结点的满二叉树,并对其进行先序遍历。
12

2.用链表存储方式建立一棵如图三、4 所示的二叉树,并对其进行先序遍历。 3.给出一组数据:R={10.18,3,8,12,2,7,3},试编程序,先构造一棵二叉树,然后以中 序遍历访问所得到的二叉树,并输出遍历结果。 4.给出八枚金币 a,b,c,d,e,f,g,h,编程以称最少的次数,判定它们蹭是否有假币,如 果有,请找出这枚假币,并判定这枚假币是重了还是轻了。

图 图是比树的结构更为复杂的一种非线性数据结构。 线性结构是一对一的关系, 树结构是 一对多的关系,图结构是多对多的关系。 图是由一个点集及这个集合中的某些点对应的连线构成的。 第一节 图的基本概念 1 5 2 4 a ? ? 3 5 1 2 3 4 b

?

图被定义为顶点的集合 V 和边的集合 E 组成的二元组, 记作 G=(V,E)。 V 是顶点的集合, E 是边的集合。 无向图:如 a ,V={V1,V2,V3,V4,V5}, E={(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1),(v1,v4),(v3,v5)} 在无向图中, 与同一条边互相关联的两个顶点称为相邻顶点或邻接点, 与同一个顶 点相关联的两条边称为相邻边。 有向图:如 b ,V={ V1,V2,V3,V4,V5}, E={<1,4>,<3,4>,<5,2>,<5,3>,<2,1>,<5,5>} 在有向图中,有向边又称作弧,起始点称作弧尾,终止点称作弧头。顶点重合为一 点的边称作环。

13

?

? ? ? ?

?

? ? ? ?

简单图:若一个图既没有环也无两条边连接同一对顶点,则称为简单图 完全图:每一对不同的顶点都有一条边相连的简单图,则称为完全图 完全无向图的边数=n*(n-1)/2 完全有向图的边数=n*(n-1) 结点(顶点)的度:与该结点相关联的边的数目。一个环相当于两条边。 入度:以该结点为终点的边的数目;出度:以该结点为起点的边的数目 终端结点(叶结点) :有向图中出度为 0 的结点(如 b 中的 4) 路径:从顶点 V 到顶点 V’的路径是一个顶点序列,{如 b 中的(5,2,1,4)} 路径长度:路径上边的数目或弧的数目 顶点不重复出现的路径称为简单路径; 第一个顶点和最后一个顶点相同的路径称为回路或环 除第一个顶点和最后一个顶点之外,内部顶点不重复出现的路径称为简单回路或环 连通和强连通:如果两个顶点之间存在路径,则称这两个顶点之间是连通的。 若一个无向图中任意两个顶点都是连通的,则称该图是连通图; 若一个有向图中任意两个顶点之间都存在两条方向相反的路径, 则称该图是强连通图 欧拉图:若一个图含有经过该图每条边恰好一次而顶点可重复的环游(欧拉回路) ,则 称这个图为欧拉图 强定理:图中的每个定点的度为偶数必存在欧拉回路。 哈迷尔顿图:若一个图含有经过该图每个顶点的圈(哈米尔顿圈) ,则称这个图为 Hamilton 图 加权图:如果在各边上附加一个具有代表性的数据,则称该图为带权图,或加权图、赋 权图。这个数值可表示费用或付出的代价等。 网络:若一个带权图是一个连通图,这个图就称为网络。 第二节 图的存储结构

一.邻接矩阵(Adjacency Matrix) 表示顶点之间相互关系的矩阵。如图 a 的邻接矩阵如下 V1 V2 V3 V4 V5 V1 0 1 0 1 1 5 V2 1 0 1 0 0 2 A(G)= V3 0 1 0 1 1 V4 1 0 1 0 1 4 3 V5 1 0 1 1 0 在表示无向图时,邻接矩阵是对称的;在表示有向图时,邻接矩阵通常是不对称的。 邻接矩阵也可以表示 加权图,将 1 用边上的权值替代 二.关联矩阵 表示顶点与边之间的关联关系的矩阵,如下图的关联矩阵为: 1 X g f e a h U X U A(G)= V W a 1 1 0 0 b 0 1 1 0 c 0 1 1 0 d 0 0 1 1 e 0 0 0 2 f 0 0 0 2 g 1 0 0 1 h 1 0 1 0

b

c

d V W 当与某个顶点相关联的边是一个环时,关联次数为 2。

14

三.邻接表(Adjacency List) 用顶点及该顶点的全部相邻顶点来表示图 1 5 顶点 V1 V2 V3 V4 V5 相邻顶点 2 1 2 1 1 4 3 4 2 3 5 4 5 3 4 0 0 0 5 0 0 0 0 0 0 邻接顶点数 3 3 3 4 3

2

3 1

4

2

5

3

4

顶点 V1 V2 V3 V4 V5

相邻顶点 2 3 4 2 1 4 0 5 0 4 0 0 0 0 5 0 0 0 0 0

邻接顶点数 2 1 2 1 3

由于用邻接表表示图时,把图的每个顶点的相邻顶点都列举出来了,故采用这种表示 法对解决查找路径及计算路径的长度等问题是十分有用的。 以上存储结构都可以用数组实现

图的遍历
图的遍历是对给定一个图, 从其中的任一顶点出发顺序访问图中的所有顶点, 每个顶点 被访问一次。遍历的结果是将顶点排成一定的序列。图的遍历是求解图的连通、拓扑排序等 算法的基础。通常有深度优先遍历和广度优先遍历两种方法。 5.2.1 深度优先遍历(DFS) DFS 在访问图中某一起始顶点 v 后, 由 v 出发, 访问它的任一邻接顶点 w1; 再从 w1 出发,访问与 w1 邻接但还没有访问过的顶点 w2;然后再从 w2 出发,进行类似的访问,? 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着,退回一步,退到 前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点, 之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上 述过程,直到连通图中所有顶点都被访问过为止。
深度优先遍历的实现(用邻接矩阵) program graphdfs; const maxn=100; var v:array[1..maxn] of Boolean;{顶点访问标志} a:array[1..maxn,1..maxn] of integer;{ 邻接矩阵} I,j,n:integer; procedure dfs(i:integer) var j:integer; begin v[i]:=true;{将该顶点置已经被访问标志}

15

write(i:5); for j:=1 to n do if (not v[j]) and(a[I,j]=1) then dfs(j);{如果该顶点没被访问且邻接} end; begin read(n); fillchar(v,sizeof(v),false); for i:=1 to n do for j:=1 to n do read(a[I,j]); dfs(1); end.

5.2.2 广度优先遍历 BFS 使用广度优先搜索在访问了起始顶点 v 之后,由 v 出发,依次访问 v 的各 个未曾被访问过的邻接顶点 w1, w2, ?, wt,然后再顺序访问 w1, w2, ?, wt 的所 有还未被访问过的邻接顶点。 再从这些访问过的顶点出发, 再访问它们的所有还未被访 问过的邻接顶点,? 如此做下去,直到图中所有顶点都被访问到为止。 广度优先搜索是一种分层的搜索过程, 每向前走一步可能访问一批顶点, 不像深度 优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程,其算法也不 是递归的。
var a:array[1..100,1..100] of integer; v:array[1..100] of boolean; i,j,k,n:integer; front,tail:integer; procedure bfs(x:integer); var i,j:integer; begin front:=1; tail:=1; fillchar(v,sizeof(v),false); {将顶点访问标识置成 false} v[front]:=true; write(front:4); while front<=tail do begin for i:=1 to n do if (a[front,i]=1)and(v[i]=false) then { 将与 front 顶点邻接的顶点入队列} begin inc(tail); v[i]:=true; write(i:4); end; inc(front); end; end; {从图的第一个顶点开始访问} { 队列首尾指针} {邻接矩阵} { 顶点访问标识}

16

begin assign(input,'bfs.in'); reset(input); read(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); bfs(1); end.

图的最短路
5.4.1 单源最短路 给定带权有向图 G=(V,E) ,其中每条边的权是非负实数,另外,再给定 V 中的一个顶 点,我们称之为源点。要计算从源点到其他各顶点的最短路径长度。这个问题称为图论单源 最短路问题。 1.Dijkstra 算法的基本思想 Dijkstra 算法是解决单源最短路径问题的贪心算法。 其基本思想是设置顶点集合 S, 首 先将源点加入该集合, 然后依据源点到其他顶点的路径长度, 选择路径长度最小的顶点加入 集合,根据所加入顶点更新源点到其他顶点的路径长度,然后再选取最小边的顶点,依次来 做,直到求解出到达所有顶点的路径长度。 例 5-1:给定如图带权(无负权)有向图,求顶点①到其它各顶点的最短路。 ① 29 4 ③ ① ④
① ①

4

② ① 6 3 4 ⑤ ④


6

program dijs;

var a:array[1..20,1..20] of integer; {邻接矩阵} ① v:array[1..20] of boolean;{顶点访问标志} i,j,max,n,p:integer; flag:boolean; begin assign(input,'path.in'); reset(input); readln(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); fillchar(v,sizeof(v),false); v[1]:=true;

17

for j:=2 to n do begin max:=maxint; for i:=1 to n do if not v[i] and (a[1,i]<>0) and(a[1,i]<max) then begin p:=i; end; v[p]:=true; {置被访问标志} for i:=1 to n do if (a[1,p]<>0)and(a[p,i]<>0) then if (a[1,i]>a[1,p]+a[p,i])or (a[1,i]=0) then a[1,i]:=a[1,p]+a[p,i]; {更新权值} end; for i:=2 to n do writeln(a[1,i]); {输出源点到其它顶点最短路径} end. {寻找源点到其它顶点的最短权值} max:=a[1,i];

生成树
1、生成树 如果连通图 G 的一个子图是一棵包含 G 的所有顶点的树, 则该子图称为 G 的生成树(SpanningTree)。 生成树是连通图的包含图中的所有顶点的极小连通子图。 图的生成树不惟一。从不同的顶点出发进行遍历,可以得到不同的生成树。 2、深度优先生成树和广度优先生成树 (1)生成树的求解方法 设图 G=(V,E)是一个具有 n 个顶点的连通图。则从 G 的任一顶点(源点)出发,作一次深度优先搜 索 (广度优先搜索) , 搜索到的 n 个顶点和搜索过程中从一个已访问过的顶点 vi 搜索到一个未曾访问过的邻 接点 vj,所经过的边(vi,vj)(共 n-1 条)组成的极小连通子图就是生成树。 (源点是生成树的根) 通常,由深度优先搜索得到的生成树称为深度优先生成树,简称为 DFS 生成树;由广度优先搜索得 到的生成树称为广度优先生成树,简称为 BPS 生成树。 2 最小生成树 对于连通的带权图(连通网)G, 其生成树也是带权的。 生成树 T 各边的权值总和称为该树的权, 记作:

这里:

18

TE 表示 T 的边集 w(u,v)表示边(u,v)的权。 权最小的生成树称为 G 的最小生成树(Minimum SpannirngTree)。最小生成树可简记为 MST。

构造最小生成树:普里姆(Prim)算法和克鲁斯卡尔算法

拓扑排序(Topological Sort)

对一个有向无环图(Directed Acyclic Graph 简称 DAG)G 进行拓扑排序,是将 G 中所有顶点排成一 个线性序列,使得图中任意一对顶点 u 和 v,若<u,v> ∈E(G),则 u 在线性序列中出现在 v 之前。 通常,这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列,简称拓扑序列。 注意: ①若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的。 ②若图中存在有向环,则不可能使顶点满足拓扑次序。 ③一个 DAG 的拓扑序列通常表示某种方案切实可行。 【例】一本书的作者将书本中的各章节学习作为顶点,各章节的先学后修关系作为边,构成一个有向 图。按有向图的拓扑次序安排章节,才能保证读者在学习某章节时,其预备知识已在前面的章节里介绍过。 ④一个 DAG 可能有多个拓扑序列。

⑤当有向图中存在有向环时,拓扑序列不存在

无前趋的顶点优先的拓扑排序方法

该方法的每一步总是输出当前无前趋(即人度为零)的顶点,其抽象算法可描述为: NonPreFirstTopSort(G){//优先输出无前趋的顶点 while(G 中有人度为 0 的顶点)do{ 从 G 中选择一个人度为 0 的顶点 v 且输出之; 从 G 中删去 v 及其所有出边;

19

} if(输出的顶点数目<|V(G)|) //若此条件不成立,则表示所有顶点均已输出,排序成功。 Error("G 中存在有向环,排序失败!"); } 对 G9 执行上述算法的执行过程得到的拓扑序列是 C0,C1,C2,C4,C3,C5,C7,C9,C6。 注意: 无前趋的顶点优先的拓扑排序算法在具体存储结构下,为便于考察每个顶点的人度,可保存各顶点 当前的人度。为避免每次选入度为 0 的顶点时扫描整个存储空间,可设一个栈或队列暂存所有入度为零的 顶点: 在开始排序前,扫描对应的存储空间,将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点 时,只需做出栈(队)操作即可。

2004 20.计算机专业的必修课及其先修课程如下表所示: 课程代号 课程名称 先修课程 C0 高等数学 C1 程序设计语言 C2 离散数学 C0, C1 C3 数据结构 C1, C2 C4 编译技术 C3 C5 操作系统 C3, C7 C6 普通物理 C0 C7 计算机原理 C6

请你判断下列课程安排方案哪个(些)是合理的( ) 。 A. C0, C1, C2, C3, C4, C5, C6, C7 B. C0, C1, C2, C3, C4, C6, C7, C5 C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4 E. C0, C1, C2, C3, C6, C7, C5, C4 2002 18.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的( A)1/2 B)1 C)2 D)4

)倍。

2003 20. 假设我们用 d=(a1,a2,?,a5),表示无向图 G 的 5 个顶点的度数,下面给出的哪 (些)组 d 值合理( )。 A){5,4,4,3,1} B){4,2,2,1,1} C){3,3,3,2,2} D){5,4,3,2,1} E){2,2,2,2,2} 2005 5. 平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为 完全图G 的顶点, 每两点之间的直线距离是图G 中对应边的权值。图G 的最小生成树中的所有边的权值 综合为( )。 A. 8 B. 7+ 5 C. 9 D. 6+ 5 E. 4+2 2 + 5 数学知识

20

集合、组合数学、逻辑运算等 1.已知 A = 35H,A /\ 05H \/ A /\ 30H 的结果是: ( ) 。 A)30H B)05H C)35H D)53H 2. 设全集 E={1,2,3,4,5},集合 A={1,4},B={1,2,5},C={2,4},则集合(A ∩B) ∪~C 为( )。 A) 空集 B) {1} C) {3,5} D){1,5} E) {1,3,5} 3.设全集 I = {a, b, c, d, e, f, g},集合 A = {a, b, c},B = {b, d, e},C = {e, f, g},那么集合 ( A ? B) ? (~ C ? B) 为( ) 。 A. {a, b, c, d} g} B. {a, b, d, e} C. {b, d, e} D. {b, c, d, e} E. {d, f,

4. 某年级学生共选修 6 门课程,期末考试前,必须提前将这 6 门课程考完,每人每天只在 下午至多考一门课程,设 6 门课程为 C1,C2,C3,C4,C5,C6,S(Ci)为学习 Ci 的学生集 合。已知 S(Ci)∩S(C6)≠ф ,i=1,2,?,5,S(Ci)∩S(Ci+1)≠ф ,i=1,2,3,4, S(C5)∩S(C1)≠ф ,问至少安排_____天才能考完这 6 门课程。 5.由 3 个 a,5 个 b 和 2 个 c 构成的所有字符串中,包含子串“abc”的共有( )个。 A. 40320 B. 39600 C. 840 D. 780 E. 60 6.平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都不在同 一条直线上。问用这些点为顶点,能组成多少个不同四边形?

7.75 名儿童到游乐场去玩。他们可以骑旋转木马,坐滑行铁道,乘宇宙飞船。已知其中 20 人这三种东西都玩过,55 人至少玩过其中的两种。若每样乘坐一次的费用是 5 元,游乐场 总共收入 700,可知有 名儿童没有玩过其中任何一种。

21


相关文档

noip初赛复习(全)
NOIP初赛复习01
Noip初赛综合复习
NOIP初赛复习——基础
NOIP初赛复习分析
NOIP初赛期末复习
NOIP初赛复习要点
NOIP初赛复习03
NOIP初赛复习02
NOIP初赛复习01分析
电脑版