NOIP奥复习三.pptVIP

* 初赛复习三 问题求解与分析 一、问题求解题一般解决方法： 1、分析题意，了解条件与求解的问题 2、根据题意，由特殊、个别，推导出问题求解的一般规律或公式（个别到一般的归纳分析） 3、根据公式或规律求出问题解答结果 二、掌握基本数据结构知识和基本算法 （一）、线性表的知识 线性表的定义 线性表的存储结构 （1）顺序结构：数组，按照下标顺序存储 （2）链表结构：利用指针将结点链接起来 3. 线性表的特点 ：只有一个直接前驱和一个直接后继 4. 特殊线性表 ： （1）栈 ： 先进后出（FILO） （2）队列：先进先出（FIFO） 5. 递归程序执行过程 ：调用过程时将变量和返回地址存入栈变量区称为进栈，返回调用的程序时，根据栈顶地址返回，并将变量返回调用程序中。 队列的操作：一般用于图的遍历，广度优先遍历方法 访问一个结点（或输出），删除该结点（出队），并将其后继结点全部进队（入队），再访问下一个结点，将其后继结点进队 栈和队列在编程中最好用数组实现。 （二）、二叉树的基本知识 1. 二叉树的定义：空树或由一个根结点和两棵互不相交的分别称为左子树和右子树所组成的非空树 2. 二叉树的基本性质及证明、深度、宽度 3. 二叉树的存储结构 （1）顺序存储：用记录型一维数组，下标表示第几个结点，分为DATA、L、R 分别表示数据、左孩子、右孩子 （2）链接存储：用指针变量指向记录结点，结点的结构： 数据域、左地址域、右地址域 4. 二叉树的运算 （1）生成二叉树的算法：用广义表表示二叉树 A（B（D），C（E（F（，G））） 按照层的结构以及完全二叉树方法输入二叉树 （2）二叉树的输出 ：相当于前序遍历的二叉树 （3）二叉树的遍历：前序、中序、后序 前序：根结点——左孩子——右孩子 中序：左孩子——根结点——右孩子 后序：左孩子——右孩子——根结点 （4）插入结点 （5）删除结点 （三）、图的基本知识 1、图的定义：顶点和边组成的表示数据间的关系 2、顶点、边、度、入度、出度 3、图的存储结构 （1）邻接矩阵：二维数组，行表示顶点，列表示顶点之间联系 （2）邻接表：建立一维数组的单向链表，每个顶点为一维数组的头结点，其后连接与其有关联的边 （3）边集数组：用一维记录型数组表示 下标表示顶点，定义起点、终点、权三个域 4、图的数据关系的建立:邻接矩阵、边集数组、邻接表 5、图的遍历：深度优先、广度优先 6、图的最小生成树、最短路径的算法 （四）、问题分析与解答： 1、平面上有三条平行直线，每条直线上分别有8，5，7个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同的三角形？ 2、剪纸片：把一张纸剪成6块，从所得的纸片中取出若干块，每块各剪成6块；再从所得的纸片中取出若干块，每块各剪成6块……如此进行下去，到剪完某一次后停止。问所得纸片总数有可能是2000，2001，2002，2003这四个数中的哪一个数？为什么？ 1、问题分析： 本题是一个组合问题，因为三点构成的直线与点的顺序没有关系，且是一个加法原理。： = 1039 2、问题分析： 2001 次数 取出块数 剩余块数 总块数 1 X1 6-x1 6x1+（6-x1）=5x1+6 2 X2 5x1+6-x2 5x1+5x2+6 … … … … n Xn 5x1+5x2+…+5Xn-1+6-Xn 5x1+5x2+…+5Xn+6 根据计算表达式，总块数是5的倍数再加6，当总块数是5的偶数倍，则结果末位数应为6，当总块数是5的奇数倍，则结果的末位数应为1，所以选择2001。 采用归纳方法。 3、在书架上放有编号为1,2,....n的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能放在原来的位置上。例如:n=3时: 原来位置为:123 放回去时只能为:312或231这两种 问题:求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法)? 4、设有一棵k叉树,其中只有度为0和k两种结点,设n0,nk分别表示度为0和度为k的结点个数,试求出n0,nk之间的关系(n0=数学表达式,数学表达式仅含nk,k和数字) 5、 如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五