NOIP初赛复习要点.pdf

《NOIP初赛复习要点.pdf》由会员分享，可在线阅读，更多相关《NOIP初赛复习要点.pdf（21页珍藏版）》请在三一文库上搜索。

1、1 . 初赛复习 一 题型 单项选择题 （共 10 题，每题1.5 分，共计15 分） 不定项选择题（共10 题，每题1.5 分，共计15 分。多选或少选均不得分） 问题求解（共2 题，每题5 分，共计10 分） 阅读程序写结果（共4 题，每题8 分，共计32 分） 完善程序 ( 前 5 空，每空2 分，后 6 空，每空3 分，共 28 分) 二 知识要点 1、计算机的基本常识 计算机产生与发展、计算机的系统及工作原理、网络的基本知识、网上搜索信息 的基本方法、计算机中有关数、编码的基本常识 2、数据结构的基本知识 线性表的知识：（ 1）栈： 先进后出（ FILO）（ 2）队列：先进先出（FI

2、FO） 树的基本知识 图的基本知识 3、数学知识：如集合、排列组合等 4、算法的基本知识 （1）初等算法（计数、统计、数学运算等） （2）排序算法（冒泡法、插入排序、合并排序、快速排序） （3）查找（顺序查找、二分法） （4）回溯算法 数制及数制转换 1数制 常用的进制：十进制（D）二进制 (B) 八进制 (O) 十六进制 (H) 基数： 10 2 8 16 位权 ： 10的幂数 2的幂数 8的幂数 16的幂数 数字符号： 09 02 07 09、AF 2数制转换 2、8、16 或其他进制10 进制的转换：（该位上的数该位上的位权值） 如： （101. 101）B=1 2 2+021+120+

3、12-1 +02 -2 +12 -3=（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

4、. 110)2=(3A. C)16 8 进制与 16 进制之间的转换可借助二进制 2 初赛题 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

5、表示负。 其表示范围由硬 件决定，当使用8 位寄存器时，字长为8 位，则无符号数的范围是0255；有符号数 的范围是 -128 127。当使用 16 位寄存器时，字长为 16 位，则无符号数的范围是0 65535；有符号数的范围是-32768 32767 定点数和浮点数：根据小数点位置的不同约定两种表示方法，一种是小数点位置固定不 变，称为定点数。一种是小数点位置可以浮动，称为浮点数。 定点数只能表示定点整数和定点纯小数，对于定点整数，约定小数点的位置在最低位； 对于定点纯小数，约定小数点的位置在符号位之后。 浮点数能表示既有整数又有小数的数，通常由阶码和尾数组成，类似指数形式 4原码、反码、

6、补码 原码：普通二进制形式，比较自然的表示法，最高位表示符号，0 为正， 1为负。优点： 简单易懂；缺点：异号数加减法运算复杂。 如： +50 的原码为00110010 -50的原码为10110010 反码： 为计算补码方便而引入。一个正数的反码是原码本身；一个负数的反码是除符号 位之外各位取反，即0 变 1，1 变 0 。 一个数的反码的反码是原码本身。 如： -50 的反码为00110010 -50的反码为11001101 补码： 加减法运算方便，减法可以转换为加法。一个正数的补码是原码本身，一个负数 的补码是其反码的低位加1。一个数的补码的补码是原码本身。 如： +50 的补码为0011

7、0010 -50的补码为11001110 两个数的补码之和等于两个数和的补码，符号位参与运算。 5BCD码（二十进制编码） 一个十进制数在计算机中以二进制形式存放，需要一个转换过程。但在将所有位的数字 输入完之前又不可能转换成完整的二进制数，所以可将每一位数字用二进制进行编码，称为 二进制编码的十进制数。 常用的二十进制数的编码是8421 码，用四位二进制数表示一位十进制数，自左至右 对应的位权是8、4、2、 1。应该指出的是，四位二进制数有00001111 十六种状态，而十 进制数 09 只取 0000 1001 十种状态，其余六种不用。 如： (498.12)D的 BCD码是 0100 ，

8、1001，1000.0001,0010 二 数据结构的基本知识 （1）栈 ：先进后出（ FILO） （2）队列：先进先出（ FIFO） 如：某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状 态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进， 3 出” 。假设车辆入站的顺序为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 E. 1, 3, 6, 5, 7 2003 19 已知元素（ 8，25，14， 87，5

9、1，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 ，

10、一个 元素出栈后即进入队列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 ，每一个子集是一 棵子树。 树的定义是一个递归定义，即用树来定义树。 4 树结构没有封闭的回

11、路。 一、树的术语 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

12、 、D、E、H。 8某结点的子树的根称为该结点的儿子（或孩子），反之，该结点称为是儿子结点的 父亲（或双亲） ，同一个父亲结点的儿子结点称为兄弟，父亲结点与儿子结点之间用枝相连。 根结点到每一个分枝结点或叶子结点的路径是唯一的。 二、树的表示 1自然界的树形表示法：如图1，用结点和边表示树，一班用于分析问题。 2括号表示法也称广义表表示法：先将根结点放入一对圆括号中，然后把它的子 树由左至右的顺序放入括号中，对子树也采用同样的方法处理，同层子树放入它们根结点后 面的圆括号中，同层子树之间用逗号隔开。如图1 可写成如下形式： (A(B(E(K,L),F),C(G),D(H(M),I,J) 三、树

13、的存储 树的存储一般有两种： 1静态的二维数组或一维记录数组（将儿子的下标序列作为一个记录域）： 如图 1 的树中各结点关系可用下表表示，故可用数组存储 下标结点儿子的下标序列 1 A 2 3 4 2 B 5 6 0 3 C 7 0 0 4 D 8 9 10 5 E 11 12 0 6 F 0 0 0 7 G 0 0 0 8 H 13 0 0 9 I 0 0 0 10 J 0 0 0 11 K 0 0 0 12 L 0 0 0 13 M 0 0 0 5 二维数组存储结构： Const n=树的度 ; Max=结点数的上限; Type treetype=array1max,1n+1 of int

14、eger; Var tree:treetype; 一维记录数组存储结构： Const n=树的度 ; Max=结点数的上限; Type node=record Data:datatype;如字符型，存储结点数据 Children:array1n of integer; End; treetype=array1max of integer; Var tree:treetype; 2动态的多重链表：由于树中可以有多个元素，所以用多重链表来描述比较方便。每 个结点由数据域和n（n 为树的度）个指针域共n+1 个域组成。其表示方法如下： Const n=树的度 ; Type treetype=node

15、; node=record Data:datatype; next:array1n of treetype; End; Var root:treetype; 显然，取树的度作为每个结点的链域数（即指向儿子结点的指针数），虽使得各种算法 简化，但由于各结点的指针域个数不同，存在很多空链域，这就造成了空间的大量浪费。 能不能在减少浪费空链域的前提下，寻找一种既使得每个结点的结构相同，又方便运算 的树形式呢？设想，每个结点的度都为2，则空指针域比重会变小，就能达到这个目的。下 面我们看另一种数据结构二叉树。 A D G F E B J I H K C L N 6 第二节二叉树 一、二叉树的概念 二叉

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

17、(4) 左子树为空的二叉树(d) ； (5) 完全二叉树(e) 2. 两个重要的概念： (1) 满二叉树除最底一层的结点的度数为0 外，其余结点的度数均为2。 (2) 完全二叉树如果一棵二叉树只有最下面的两层结点度小于2，并且最下面一层 的结点都集中在该层最左边的若干位置，则称为完全二叉树。也就是说， 对于一棵满二叉树， 若从最底一层的最右边开始，连续向左缺少几个结点，就可得到一棵完全二叉树。满二叉树 一定是完全二叉树。 如图 2 为满二叉树，图3 为完全二叉树 7 图 2 图 3 二、二叉树的性质 1在二叉树中，第I 层的结点总数不超过2 I-1 ； 2在深度为K的二叉树中，结点总数不超过2

18、 K -1 3 对于任意一棵二叉树， 如果其叶结点数为N0， 而度数为2 的结点总数为N2， 则 N0=N2+1； 4有 N个结点的完全二叉树各结点如果用顺序方式表示，则结点之间有如下关系： 如果 Inil then 访问处理bt.data; pre(bt.lch);递归遍历左子树 pre(bt.rch);递归遍历右子树 end; end; 顺序一维记录存储结构： procedure pre(i:integer); begin if inil then infer(bt.lch);递归遍历左子树 访问处理bt.data; infer(bt.rch);递归遍历右子树 end; end; 顺序一维

19、记录存储结构： procedure infer(i:integer); begin if inil then post(bt.lch);递归遍历左子树 post(bt.rch);递归遍历右子树 顺序一维记录存储结构： procedure post(i:integer); begin if i1 then solve1(copy(s1,1,k-1),copy(s2,1,k-1); if k1 then solve2(copy(s1,1,k-1),copy(s2,2,k); if k, 在有向图中，有向边又称作弧，起始点称作弧尾，终止点称作弧头。顶点重合为一 点的边称作环。 1 2 4 5 3 2

20、 1 5 4 3 a b 14 简单图：若一个图既没有环也无两条边连接同一对顶点，则称为简单图 完全图：每一对不同的顶点都有一条边相连的简单图，则称为完全图 完全无向图的边数=n*(n-1)/2 完全有向图的边数=n*(n-1) 结点（顶点）的度：与该结点相关联的边的数目。一个环相当于两条边。 入度：以该结点为终点的边的数目；出度：以该结点为起点的边的数目 终端结点（叶结点） ：有向图中出度为0 的结点（如b 中的 4） 路径：从顶点V到顶点 V的路径是一个顶点序列，如 b 中的 (5,2,1,4) 路径长度：路径上边的数目或弧的数目 顶点不重复出现的路径称为简单路径； 第一个顶点和最后一个顶

21、点相同的路径称为回路或环 除第一个顶点和最后一个顶点之外，内部顶点不重复出现的路径称为简单回路或环 连通和强连通：如果两个顶点之间存在路径，则称这两个顶点之间是连通的。 若一个无向图中任意两个顶点都是连通的，则称该图是连通图； 若一个有向图中任意两个顶点之间都存在两条方向相反的路径，则称该图是强连通图 欧拉图：若一个图含有经过该图每条边恰好一次而顶点可重复的环游（欧拉回路），则 称这个图为欧拉图强定理：图中的每个定点的度为偶数必存在欧拉回路。 哈迷尔顿图：若一个图含有经过该图每个顶点的圈（哈米尔顿圈），则称这个图为 Hamilton 图 加权图：如果在各边上附加一个具有代表性的数据，则称该图为

22、带权图，或加权图、赋 权图。这个数值可表示费用或付出的代价等。 网络：若一个带权图是一个连通图，这个图就称为网络。 第二节图的存储结构 一邻接矩阵（Adjacency Matrix） 表示顶点之间相互关系的矩阵。如图a 的邻接矩阵如下 在表示无向图时，邻接矩阵是对称的；在表示有向图时，邻接矩阵通常是不对称的。 邻接矩阵也可以表示 加权图，将1 用边上的权值替代 二关联矩阵 表示顶点与边之间的关联关系的矩阵，如下图的关联矩阵为： 当与某个顶点相关联的边是一个环时，关联次数为2。 A（G）= V1 V2 V3 V4 V5 V1 0 1 0 1 1 V2 1 0 1 0 0 V3 0 1 0 1 1

23、 V4 1 0 1 0 1 V5 1 0 1 1 0 A（ G）= a b c d e f g h X U V W 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 2 2 1 0 X W U V a b c d e f g h 1 2 4 5 3 15 三邻接表（ Adjacency List） 用顶点及该顶点的全部相邻顶点来表示图 由于用邻接表表示图时，把图的每个顶点的相邻顶点都列举出来了，故采用这种表示 法对解决查找路径及计算路径的长度等问题是十分有用的。 以上存储结构都可以用数组实现 图的遍历 图的遍历是对给定一个图，从其中

24、的任一顶点出发顺序访问图中的所有顶点，每个顶点 被访问一次。 遍历的结果是将顶点排成一定的序列。图的遍历是求解图的连通、拓扑排序等 算法的基础。通常有深度优先遍历和广度优先遍历两种方法。 5.2.1深度优先遍历（DFS ） DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1； 再从 w1 出发， 访问与 w1 邻接但还没有访问过的顶点 w2；然后再从 w2 出发， 进行类似的访问， 如此进行下去， 直至到达所有的邻接顶点都被访问过的顶点u 为止。接着， 退回一步， 退到 前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点， 之后再从此顶

25、点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上 述过程，直到连通图中所有顶点都被访问过为止。 深度优先遍历的实现（用邻接矩阵） program graphdfs; const maxn=100; var v:array1maxn of Boolean;顶点访问标志 a:array1maxn,1maxn of integer;邻接矩阵 I,j,n:integer; procedure dfs(i:integer) var j:integer; begin vi:=true;将该顶点置已经被访问标志 1 2 4 5 3 1 2 4 5 3 顶点 V1 V2 V3 V4 V5

26、相邻顶点 2 4 5 0 0 1 3 4 0 0 2 4 5 0 0 1 2 3 5 0 1 3 4 0 0 邻接顶点数 3 3 3 4 3 顶点 V1 V2 V3 V4 V5 相邻顶点 2 4 0 0 3 0 0 0 4 5 0 0 2 0 0 0 1 4 5 0 邻接顶点数 2 1 2 1 3 16 write(i:5); for j:=1 to n do if (not vj) and(aI,j=1) then dfs(j);如果该顶点没被访问且邻接 end; begin read(n); fillchar(v,sizeof(v),false); for i:=1 to n do for

27、 j:=1 to n do read(aI,j); dfs(1); end. 5.2.2广度优先遍历 BFS使用广度优先搜索在访问了起始顶点 v 之后，由 v 出发，依次访问 v 的各 个未曾被访问过的邻接顶点w1, w2, , wt ，然后再顺序访问w1, w2, , wt 的所 有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访 问过的邻接顶点， 如此做下去，直到图中所有顶点都被访问到为止。 广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度 优先搜索那样有往回退的情况。因此， 广度优先搜索不是一个递归的过程，其算法也不 是递归的。 var

28、a:array1100,1100 of integer; 邻接矩阵 v:array1100 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 vfront:=true; 从图的第一个顶点开始访问 write(front:4); while front0) and(a1,i0)and(ap,ia1,p

29、+ap,i)or (a1,i=0) then a1,i:=a1,p+ap,i; 更新权值 end; for i:=2 to n do writeln(a1,i); 输出源点到其它顶点最短路径 end. 生成树 1、生成树 如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树 (SpanningTree)。 生成树是连通图的包含图中的所有顶点的极小连通子图。 图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。 2、深度优先生成树和广度优先生成树 （1）生成树的求解方法 设图 G=(V，E)是一个具有n 个顶点的连通图。则从G的任一顶点（源点）出发，作一次深度优

30、 先搜索（广度优先搜索） ，搜索到的 n 个顶点和搜索过程中从一个已访问过的顶点vi搜索到一个未曾访问过 的邻接点 vj，所经过的边 (vi，vj) （共 n-1 条）组成的极小连通子图就是生成树。（源点是生成树的根） 通常， 由深度优先搜索得到的生成树称为深度优先生成树，简称为 DFS生成树； 由广度优先搜索 得到的生成树称为广度优先生成树，简称为BPS生成树。 2 最小生成树 对于连通的带权图( 连通网 )G，其生成树也是带权的。生成树T 各边的权值总和称为该树的权， 记作： 19 这里 : TE表示 T 的边集 w(u，v) 表示边 (u ，v) 的权。 权最小的生成树称为G的最小生成树

31、 (Minimum SpannirngTree)。最小生成树可简记为MST 。 构造最小生成树：普里姆(Prim) 算法和克鲁斯卡尔算法 拓扑排序 (Topological Sort) 对一个 有向无环图 (Directed Acyclic Graph简称 DAG )G 进行拓扑排序，是将G中所有顶点排成 一个线性序列，使得图中任意一对顶点u 和 v，若 E(G)，则u 在线性序列中出现在v 之前。 通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称 拓扑序列 。 注意： 若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。 若图中存在有向环，

32、则不可能使顶点满足拓扑次序。 一个 DAG的拓扑序列通常表示某种方案切实可行。 【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有 向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍 过。 一个 DAG可能有多个拓扑序列。 当有向图中存在有向环时，拓扑序列不存在 无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输出当前无前趋( 即人度为零 ) 的顶点，其抽象算法可描述为： NonPreFirstTopSort(G)/优先输出无前趋的顶点 20 while(G中有人度为0 的顶点 )do 从 G中选择一个人度为0 的

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

34、做出栈( 队) 操作即可。 2004 20. 计算机专业的必修课及其先修课程如下表所示： 课程代号C0C1C2C3C4C5C6C7 课程名称高等数学 程序设计语言 离散数学 数据结构编译技术 操作系统 普通物理 计算机原理 先修课程C0, C1C1, C2C3C3, C7C0C6 请你判断下列课程安排方案哪个（些）是合理的（） 。 A. C0, C1, C2, C3, C4, C5, C6, C7 B. C 0, C1, C2, C3, C4, C6, C7, C5 C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3,

35、 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)。以这五点作为

36、完全图 G 的顶点， 21 每两点之间的直线距离是图G 中对应边的权值。图G 的最小生成树中的所有边的权值 综合为（）。 A. 8 B. 7+ 5 C. 9 D. 6+ 5 E. 4+2 2 + 5 数学知识 集合、组合数学、逻辑运算等 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,

37、 d, e, f, g，集合 A = a, b, c， B = b, d, e，C = e, f, g，那么集合)()(BCBA为（） 。 A. a, b, c, d B. a, b, d, e C. b, d, e D. b, c, d, e E. d, f, g 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，可知有名儿童没有玩过其中任何一种。