NOIP奥复习三

1、初赛复习三初赛复习三 问题求解与分析问题求解与分析一、问题求解题一般解决方法：一、问题求解题一般解决方法： 1 1、分析题意，了解条件与求解的问题、分析题意，了解条件与求解的问题 2 2、根据题意，由特殊、个别，推导出问题求、根据题意，由特殊、个别，推导出问题求解的一般规律或公式（个别到一般的归纳分析）解的一般规律或公式（个别到一般的归纳分析） 3 3、根据公式或规律求出问题解答结果、根据公式或规律求出问题解答结果二、掌握基本数据结构知识和基本算法二、掌握基本数据结构知识和基本算法 （一）、线性表的知识（一）、线性表的知识1. 线性表的定义线性表的定义2. 线性表的存储结构线性表的存储结构（1

2、）顺序结构：数组，按照下标顺序存储）顺序结构：数组，按照下标顺序存储（2）链表结构：利用指针将结点链接起来）链表结构：利用指针将结点链接起来3. 线性表的特点线性表的特点 ：只有一个直接前驱和一个直接后继：只有一个直接前驱和一个直接后继4. 特殊线性表特殊线性表 ：（1）栈）栈 ： 先进后出（先进后出（FILO）（2）队列：先进先出（）队列：先进先出（FIFO）5. 递归程序执行过程递归程序执行过程 ：调用过程时将变量和返回地址存：调用过程时将变量和返回地址存入栈变量区称为进栈，返回调用的程序时，根据栈顶地址入栈变量区称为进栈，返回调用的程序时，根据栈顶地址返回，并将变量返回调用程序中。返回，

3、并将变量返回调用程序中。 队列的操作：一般用于图的遍历，广度优先遍历方法队列的操作：一般用于图的遍历，广度优先遍历方法 访问一个结点（或输出），删除该结点（出队），并访问一个结点（或输出），删除该结点（出队），并将其后继结点全部进队（入队），再访问下一个结点，将将其后继结点全部进队（入队），再访问下一个结点，将其后继结点进队其后继结点进队 栈和队列在编程中最好用数组实现。栈和队列在编程中最好用数组实现。（二）、二叉树的基本知识（二）、二叉树的基本知识 1. 二叉树的定义：空树或由一个根结点和两棵互不相二叉树的定义：空树或由一个根结点和两棵互不相交的分别称为左子树和右子树所组成的非空树交的分别称

4、为左子树和右子树所组成的非空树 2. 二叉树的基本性质及证明、深度、宽度二叉树的基本性质及证明、深度、宽度 3. 二叉树的存储结构二叉树的存储结构（1）顺序存储：用记录型一维数组，下标表示第几个结）顺序存储：用记录型一维数组，下标表示第几个结点，分为点，分为DATA、L、R 分别表示数据、左孩子、右孩子分别表示数据、左孩子、右孩子（2）链接存储：用指针变量指向记录结点，结点的结构：）链接存储：用指针变量指向记录结点，结点的结构： 数据域、左地址域、右地址域数据域、左地址域、右地址域 4. 二叉树的运算二叉树的运算 （1）生成二叉树的算法：用广义表表示二叉树）生成二叉树的算法：用广义表表示二叉树

5、 A（B（D），），C（E（F（，（，G） 按照层的结构以及完全二叉树方法输入二叉树按照层的结构以及完全二叉树方法输入二叉树 （2）二叉树的输出）二叉树的输出 ：相当于前序遍历的二叉树：相当于前序遍历的二叉树 （3）二叉树的遍历：前序、中序、后序）二叉树的遍历：前序、中序、后序 前序：根结点前序：根结点左孩子左孩子右孩子右孩子 中序：左孩子中序：左孩子根结点根结点右孩子右孩子 后序：左孩子后序：左孩子右孩子右孩子根结点根结点 （4）插入结点）插入结点 （5）删除结点）删除结点（三）、图的基本知识（三）、图的基本知识 1、图的定义：顶点和边组成的表示数据间的关系、图的定义：顶点和边组成的表示数据

6、间的关系 2、顶点、边、度、入度、出度、顶点、边、度、入度、出度 3、图的存储结构、图的存储结构 （1）邻接矩阵：二维数组，行表示顶点，列表示顶点）邻接矩阵：二维数组，行表示顶点，列表示顶点之间联系之间联系 （2）邻接表：建立一维数组的单向链表，每个顶点为）邻接表：建立一维数组的单向链表，每个顶点为一维数组的头结点，其后连接与其有关联的边一维数组的头结点，其后连接与其有关联的边 （3）边集数组：用一维记录型数组表示）边集数组：用一维记录型数组表示 下标表示顶点，定义起点、终点、权三个域下标表示顶点，定义起点、终点、权三个域 4、图的数据关系的建立、图的数据关系的建立:邻接矩阵、边集数组、邻接表

7、邻接矩阵、边集数组、邻接表 5、图的遍历：深度优先、广度优先、图的遍历：深度优先、广度优先 6、图的最小生成树、最短路径的算法、图的最小生成树、最短路径的算法（四）、问题分析与解答：（四）、问题分析与解答： 1 1、平面上有三条平行直线，每条直线上分别有平面上有三条平行直线，每条直线上分别有8 8，5 5，7 7个点，且不同直线上三个点都不在同一条直线上。问用这个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同的三角形？些点为顶点，能组成多少个不同的三角形？ 2 2、剪纸片：把一张纸剪成、剪纸片：把一张纸剪成6 6块，从所得的纸片中取出若块，从所得的纸片中取出若干块

8、，每块各剪成干块，每块各剪成6 6块；再从所得的纸片中取出若干块，块；再从所得的纸片中取出若干块，每块各剪成每块各剪成6 6块块如此进行下去，到剪完某一次后停止。如此进行下去，到剪完某一次后停止。问所得纸片总数有可能是问所得纸片总数有可能是20002000，20012001，20022002，20032003这四个这四个数中的哪一个数？为什么？数中的哪一个数？为什么？ 1、问题分析：、问题分析： 本题是一个组合问题，因为三点构成的直线与点的顺序本题是一个组合问题，因为三点构成的直线与点的顺序没有关系，且是一个加法原理。：没有关系，且是一个加法原理。： = 1039 2、问题分析：、问题分析：

9、2001 )(*)(*)(*171825151827151728151718cccccccccccc次数次数取出块数取出块数剩余块数剩余块数总块数总块数1X16-x16x1+（6-x1）=5x1+62X25x1+6-x25x1+5x2+6nXn5x1+5x2+5Xn-1+6-Xn5x1+5x2+5Xn+6 根据计算表达式，总块数是根据计算表达式，总块数是5的倍数再加的倍数再加6，当总块数，当总块数是是5的偶数倍，则结果末位数应为的偶数倍，则结果末位数应为6，当总块数是，当总块数是5的奇数的奇数倍，则结果的末位数应为倍，则结果的末位数应为1，所以选择，所以选择2001。 采用归纳方法。采用归纳方

10、法。 3、在书架上放有编号为在书架上放有编号为1,2,.n的的n本书。现将本书。现将n本书全本书全部取下然后再放回去部取下然后再放回去,当放回去时要求每本书都不能放在当放回去时要求每本书都不能放在原来的位置上。例如原来的位置上。例如:n=3时时:原来位置为原来位置为:123 放回去时只能为放回去时只能为:312或或231这两种这两种问题问题:求当求当n=5时满足以上条件的放法共有多少种时满足以上条件的放法共有多少种?(不用列不用列出每种放法出每种放法) 4、设有一棵、设有一棵k叉树叉树,其中只有度为其中只有度为0和和k两种结点两种结点,设设n0,nk分别表示度为分别表示度为0和度为和度为k的结

11、点个数的结点个数,试求出试求出n0,nk之间的关之间的关系系(n0=数学表达式数学表达式,数学表达式仅含数学表达式仅含nk,k和数字和数字) 5 5、 如下图如下图, ,有一个无穷大的的栈有一个无穷大的的栈S,S,在栈的右边排列着在栈的右边排列着1,2,3,4,51,2,3,4,5共五个车厢。其中每个车厢可以向左行走共五个车厢。其中每个车厢可以向左行走, ,也可也可以进入栈以进入栈S S让后面的车厢通过。现已知第一个到达出口的让后面的车厢通过。现已知第一个到达出口的是是3 3号车厢，请写出所有可能的到达出口的车厢排列总数号车厢，请写出所有可能的到达出口的车厢排列总数( (不必给出每种排列不必给

12、出每种排列) ) SS出口出口 1 2 3 4 51 2 3 4 5 6 6、将、将N N个红球和个红球和M M个黄球排成一行。例如个黄球排成一行。例如:N=2,M=3:N=2,M=3可可得到以下得到以下1010种排法种排法: : 红红黄黄黄红红黄黄黄 红黄红黄黄红黄红黄黄 红黄黄红黄红黄黄红黄 黄红红黄黄黄红红黄黄 黄红黄红黄黄红黄红黄 黄黄黄红红黄黄黄红红问题问题: :当当N=4,M=3N=4,M=3时有多少种不同排法时有多少种不同排法?(?(不用列出每种排法不用列出每种排法) )问题解答：问题解答： 3、 答：当答：当n=5时，满足以上条件的方法共有时，满足以上条件的方法共有44种。种。

13、 4、 答：答：n0和和nk 之间的关系为：之间的关系为：n0=(k-1) nk+ 1 。 5 5、答：所有可能到达出口的车厢排列总数为答：所有可能到达出口的车厢排列总数为 9 。 6、答：当答：当N=4，M=3时有时有 35 种不同排列。种不同排列。 7、已知一棵二叉树的结点名为大写英文字母，其中序已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：与后序遍历的顺序分别为：CBGEAFHDIJ 与与 CGEBHFJIDA则该二叉树的先序遍历的顺序为：则该二叉树的先序遍历的顺序为： 8、平面上有三条平行直线，每条直线上分别有平面上有三条平行直线，每条直线上分别有7，5，6个点，

14、且不同直线上三个点都不在同一条直线上。问用个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？这些点为顶点，能组成多少个不同四边形？ 7、答：该二叉树先序遍历的顺序为：、答：该二叉树先序遍历的顺序为：ABCEGDFHIJ 8、答：这些点为顶点，能组成、答：这些点为顶点，能组成2250个不同四边形个不同四边形 9、已知一棵度为、已知一棵度为m的树中有的树中有N1个度为个度为1的结点，的结点，N2个度个度为为2的结点，的结点，Nn个度为个度为m的结点，问该树有多少个的结点，问该树有多少个叶子结点？叶子结点？ 10、在在a,b,c,d,e,fa,b,c,d,e,f六

15、件物品中，按下面的条件能选出六件物品中，按下面的条件能选出的物品是：的物品是： (1)(1)a,ba,b两样至少有一样两样至少有一样(2)(2)a,da,d不能同时取不能同时取(3)(3)a,e,fa,e,f中必须有中必须有2 2样样(4)(4)b,cb,c要么都选，要么都不选要么都选，要么都不选(5)(5)c,dc,d两样中选一样两样中选一样(6)(6)若若d d不选，则不选，则e e也不选也不选1111、若已知一个栈的入栈顺序是、若已知一个栈的入栈顺序是1 1，2 2，3 3，n n，其输出，其输出序列为序列为P1P1，P2P2，P3P3，PnPn，若，若P1P1是是n n，则，则PiPi

16、是是( ) ( ) A)i A)i B)n-1 B)n-1 C)n-i+1 C)n-i+1 D)D)不确定不确定 1212、 无向图无向图G=(VG=(V，E)E)，其中，其中V=a,b,c,d,e,f V=a,b,c,d,e,f E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 对该图进行深度优先遍历对该图进行深度优先遍历, ,得到的顶点序列正确的是得到的顶点序列正确的是( )( ) A)a,b,e,c,d,fA)a,b,e,c,d,f B)a,c,f,e,b,dB)a

17、,c,f,e,b,d C)a,e,b,c,f,dC)a,e,b,c,f,d D)a,b,e,d,f,cD)a,b,e,d,f,c13、已知：、已知：A1，A2，A81 共有共有81个数，其中只有一个数，其中只有一个数比其它数大，要用最少的比较运算次数，把这个值大个数比其它数大，要用最少的比较运算次数，把这个值大的数找出来（假设两个数比较一次能决定出大于、小于或的数找出来（假设两个数比较一次能决定出大于、小于或等于这三种情况）请将以下算法补充完整：等于这三种情况）请将以下算法补充完整：第一步：第一步： S1 = A1 + A2 + + A27 S2 = A28 + A29 + A54 第一次比较

18、（第一次比较（S1，S2） ： S1 S2 取取 K=0 S1 S2 取取 K= _ S1 S2 取取 K=_ S1 S2 -_ 为最大数为最大数 S1 =1N=1）都满足）都满足U U n+2 n+2 =U=Un+1n+1+U+Un n 。试对数列。试对数列1 12 2，2 22 2，3 32 2，n n2 2, ,求求K K和和a a1 1,a,a2 2, , ,a,aK K使得（使得（A A）式成立。）式成立。问题分析：问题分析：根据题意，可以用解方程的方法求得解：根据题意，可以用解方程的方法求得解：（1 1）可以先设定）可以先设定K=2K=2，列出方程组：，列出方程组： a a* *1

19、 12 2 +b +b* *2 22 2 = 3 = 32 2 得不到得不到a,ba,b整数解，整数解， a a* *2 22 2 +b +b* *3 32 2 = 4 = 42 2 （2 2）再设）再设K=3K=3得到方程组得到方程组 a a* *0 02 2 +b +b* *1 12 2 +C +C* *2 22 2 =9 =9 解得解得a=1,b=-3,c=3 aa=1,b=-3,c=3 a* *1 12 2 +b +b* *2 22 2 +C +C* *3 32 2 =16 =16 a a* *2 22 2 +b +b* *3 32 2 +C +C* *4 42 2 =25 =25 所

20、以本题的正确答案是：所以本题的正确答案是：K=3K=3，a1=1, a2=-3, a3=3 a1=1, a2=-3, a3=3 ，满，满足足U U n+3 n+3 =U =Un+1n+1-3-3* *U Un n +3+3* *U U n+2 n+2 1515、将将LnLn定义为求在一个平面中用定义为求在一个平面中用n n条直线所能确定的最条直线所能确定的最大区域数目。例如：当大区域数目。例如：当n=1n=1时，时，L1=2,L1=2,进一步考虑，用进一步考虑，用n n条条折成角的直线（角度任意），放在平面上，能确定的最大折成角的直线（角度任意），放在平面上，能确定的最大区域数目区域数目ZnZ

21、n是多少？例如：当是多少？例如：当n=1n=1时，时，Z1=2Z1=2（如下图所示）（如下图所示） 当给出当给出n n后，请写出以下的表达式：后，请写出以下的表达式：LnLn = _ 1 _ = _ 1 _Zn = _ 2 _ Zn = _ 2 _ 问题分析：问题分析：本题实质是求直线或折线将一个平面分成最大区域数，我本题实质是求直线或折线将一个平面分成最大区域数，我们可以从两个方面考虑：们可以从两个方面考虑：（1 1） 求在一个平面中用求在一个平面中用n n条直线所能确定的最大区域数条直线所能确定的最大区域数目；目；（2 2） 求在一个平面中用求在一个平面中用n n条折线所能确定的最大区域数

22、条折线所能确定的最大区域数目；目；问题（问题（1 1），通过几何知识可以知道），通过几何知识可以知道n n条直线两两相交，所条直线两两相交，所构成的区域数目最大：构成的区域数目最大： n=1 n=1 ， L1= 2 L1= 2 ； F(1)=2 ;F(1)=2 ;n=2 , L2= 4 ; F(2)=F(1)+2 ;n=2 , L2= 4 ; F(2)=F(1)+2 ;n=3 , L3= 7 ; F(3)=F(2)+3 ;n=3 , L3= 7 ; F(3)=F(2)+3 ; n=4 , L4= 11 ; F(4)=F(3)+4 ; n=4 , L4= 11 ; F(4)=F(3)+4 ; n

23、=5 , L5= 16 ; F(5)=F(4)+5 ; n=5 , L5= 16 ; F(5)=F(4)+5 ; 得到公式：得到公式：F(n)=F(n-1)+n ,F(n)=F(n-1)+n ,两边相加后得：两边相加后得： n+(n-1)+(n-2)+ n+(n-1)+(n-2)+ +2+1+1=n +2+1+1=n* *(n+1)/2+1 (n+1)/2+1 所以当给出所以当给出n n后，最大区域数目是后，最大区域数目是LnLn= n= n* *(n+1)/2+1(n+1)/2+116、一元三次方程求解、一元三次方程求解(20分分) 有形如：有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给这样的一个一元三次方程。给出该方程中各项的系数出该方