noip2016备战初赛

LOGO备战初赛(2016NOIP)1初赛内容及分值分布初赛：初赛全部为笔试，满分100分。试题由四部分组成：1、选择题：共20题，每题1.5分，共计30分。(普及组全为单选题;提高组10个单选，10个不定项选择)2、问题求解题：共2题，每题5分,共计10分3、程序阅读理解题:共4题，每题8分,共计32分。4、程序完善题：共2题，每题14分，共计28分。2选择题知识范围计算机基本常识：IT文化、微机原理信息安全、基本应用与奥赛活动有关的知识程序语言及算法基础数据结构(串、栈、队、树、图)离散数学：排列组合、数理逻辑5、离散数学什么是逻辑运算－－逻辑运算用来判断一件事情是“对”的还是“错”的，或者说是“成立”还是“不成立”，判断的结果是二值的。逻辑运算基本逻辑运算1.“与”运算(AND)“与”运算又称逻辑乘，用符号“∧”、“·”或者“and”来表示。运算规则如下：0∧0=00∧1=01∧0=01∧1=1即当两个参与运算的数中有一个数为0，则运算结果为0；若都为1，则结果为1。练习11001与11011的逻辑与运算结果是?2.“或”运算(OR)“或”运算又称逻辑加，用符号“+”、“∨”或者“or”表示。运算规则如下:0∨0=00∨1=11∨0=11∨1=1即当两个参与运算的数中有一个数为1，则运算结果为1；若都为0，则结果为0。练习11001与11011的逻辑或运算结果是?3.“非”运算(NOT)如果变量为A，则它的非运算结果用A表示。其运算符号为“-”，有时也用“¬”或“not”表示运算规则如下:0=11=0练习11001逻辑非运算结果是?4.“异或”运算(XOR)“异或”运算用符号“-∨”或者“xor”来表示。其运算规则如下:-0∨0=0-0∨1=1-1∨0=1-1∨1=0即当两个参与运算的数取值相异时，运算结果为1，否则为0.练习11001与11011的逻辑异或运算结果是?逻辑运算练习1011∨1001=100010∧101001=-11101∨11010=10101=小结:逻辑常量运算与运算或运算非运算异或运算0·0=00·1=01·0=01·1=10+0=00+1=11+0=01+1=1_1=0_0=1-0∨0=0-0∨1=1-1∨0=1-1∨1=0基本概念把分散的人或事物聚集到一起叫做集合。其中各事物叫做集合的元素。例如：26个英文字母的集合。空集是不含任何元素的集合。集合集合的基本运算有并、交、补、减等。集合的运算假设有集合A={a,b,c}，B={c,d}，C={b}并运算：A∪B={a,b,c,d}，B∪C={b,c,d}A∪C={a,b,c}并集：以属于A或属于B的元素为元素的集合称为A与B的并（集），记作A∪B（或B∪A），读作“A并B”（或“B并A”）即A∪B={x|x∈A,或x∈B}。练习有两个集合A={2,3}、B={2,3,5,7}，请问A∪B=？有三个集合A={1,3}、B={2,3,5,7}，B={3,5}，请问A∪B=？，A∪C=？，C∪B=？假设有集合A={a,b,c}，B={c,d}，C={b}交运算：A∩B={c}，A∩C={b}A∩C={b}交集：以属于A且属于B的元素为元素的集合称为A与B的交（集），记作A∩B（或B∩A），读作“A交B”（或“B交A”），即A∩B={x|x∈A,且x∈B}练习有两个集合A={2,3}、B={2,3,5,7}，请问A∩B=？有三个集合A={1,3}、B={2,3,5,7}，B={3,5}，请问A∩B=？，A∩C=？，C∩B=？7、数据结构数据结构是计算机存储、组织数据的方式。数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。需要掌握的数据结构形式：一维数组、堆栈、二叉树栈是一种数据结构，它按照先进后出的原则存储数据。栈栈的示意图计算原则：先进入的数据被压入栈底，最后的数据在栈顶。需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈的示意图栈顶栈底进栈有集合A={a1，a2，a3，a4，a5}，按照a1至a5的顺序进栈。栈顶栈底栈a1a2a3a4a5进栈(Push)出栈顺序：栈顶栈底栈a1a2a3a4a5①②③出栈(Pop)规则：先进后出，后进先出！！！有XYZ三个元素依次入栈,不可能的出栈顺序是?()A:ZYXB:ZXYC:YXZD:XYZ为什么?设栈S和队列Q的初始状态为空，元素a1、a2、a3、a4、a5、a6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是a2、a4、a3、a6、a5、a1，则栈S的容量至少有（）。A.2B.3C.4D.5E.6一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是A3，5，4，2，1B3，2，4，5，1C1，2，3，4，5D5，4，3，1，2若让元素1,2,3依次进栈，若元素可随时出栈，则下列出栈次序不可能出现的是（）。A.3,2,1B.2,1,3C.3,1,2D.1,3,2栈底至栈顶依次存放元素ABCD,第五个元素入栈前,栈中元素可以出栈,则出栈的序列可能是_________A.ABCEDB.DBCEAC.CDABED.DCBEA树：是一种重要的非线性数据结构，它是由n（n=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。二叉树⒈必有一个特定的称为根(ROOT)的结点；⒉剩下的结点被分成ｎ=0个互不相交的集合T1、T2、......Tn，而且，这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。根T1T2T3（某一个结点）的（儿子结点）的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。例如在图中，结点A，B和E的度分别为3，2，0，树的度为3。在一棵树中，度为零的结点称为叶结点或终端结点。图中，E，I，J，C，G，H均为叶结点。从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点的深度或层数。例如，在图中，结点A的深度为0；结点B，C和D的深度为1；结点E，F，G，H的深度为2；结点I和J的深度为3。二叉树(binarytree)是另一种树型结构特点：每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。逻辑上二叉树有五种基本形态：(1)空二叉树——(a)；(2)只有一个根结点的二叉树——(b)；(3)右子树为空的二叉树——(c)；(4)左子树为空的二叉树——(d)；(5)完全二叉树——(e)(a)(b)(c)(d)(e)二叉树的性质（1）在二叉树中，第i层的结点最多有2i-1个；例：二叉树中，第3层最多有23-1=22=4个123456i=1i=2i=357（2）深度为h的二叉树最多有2h-1个结点(h=1)，最少有h个结点；12345657h=3，最多有（23-1）个结点，最少有3个结点（3）在任意二叉树中，如果叶子数为n0，度为2的结点数为n2，则n0=n2+1;证明:设n1为二叉树T中度为1的结点数。∵二叉树中所有结点的度均小于或等于2∴n=n0+n1+n2(1)设B为分支总数，则n=B+1∵这些分支是由度为1或2的结点射出的∴B=n1+2n2∴n=n1+2n2+1(2)由式(1)和(2)得n0=n2+1二叉树的特殊形态满二叉树1234567一棵深度为k，而且有2k-1个结点的二叉树，称为满二叉树12345满二叉树非满二叉树完全二叉树二叉树的特殊形态123456当每一个结点都与深度为k的满二叉树中编号的结点一一对应时，称为完全二叉树一个深度为k的二叉树，如果k-1层为满二叉数且第k层结点按从左至右的顺序满插入的话，这棵树称为完全二叉树。二叉树的遍历所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。设L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情况：DLR（根左右，称为先序遍历）LDR（左根右，称为中序遍历）LRD（左右根，称为后序遍历）(1)先序遍历（以根结点为参照）⑴访问根结点；⑵先序遍历左子树；⑶先序遍历右子树(2)中序遍历（以根结点为参照）⑴中序遍历左子树；⑵访问根结点；⑶中序遍历右子树(3)后序遍历（以根结点为参照）⑴后序遍历左子树；⑵后序遍历右子树；⑶访问根结点遍历二叉树先序遍历上图所示的二叉树时，得到的先序序列为：ABDCEF中序遍历上图所示的二叉树时，得到的中序序列为：DBAECF后序遍历上图所示的二叉树时，得到的后序序列为：DBEFCA由二叉树的前序序列和中序序列建立该二叉树1.用前序序列的第一个结点作为根结点;2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);3.根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列;4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。假设前序序列为ABDGHCEFI，中序序列为GDHBAECIF，则得到的二叉树如下所示1。A为根结点ABDGHCEFIGDHBAECIF2.B为左子树的根结点BDGHGDHB3.D为左子树的左子树的根结点4.C为右子树的根结点CEFIECIF5.F为右子树的右子树的根结点表达式二叉树-+/a*eb-cdf请写出该二叉树对应的表达式!前缀表达式(波兰式):-+a*b-cd/ef中缀表达式:a+b*c-d-e/f后缀表达式(逆波兰式):abcd-*+ef/-基本算法什么是算法?算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法排序算法查找算法回溯算法排序排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。以比较为基础的排序算法的基本操作大多数排序算法都有两个基本的操作：(1)比较两个关键字的大小；(2)改变指向记录的游标或移动记录本身。需要学习的排序算法：冒泡排序、直接插入排序、归并排序、快速排序冒泡排序（借助“交换”进行排序）基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。排序方法：依次比较相邻的两个数，将大数放在前面，小数放在后面。即首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。示例对序列2,38,65,13,27排序382651327①②386521327386513227③④第一趟排序，结果：选出最小的数386513272第二趟排序，结果：选出第二小的数653813272①②③653813272653827132第三趟排序，结果：选出第三小的数653827132①②653827132第四趟排序，结果：选出第四小的数653827132①【效率分析】空间效率：仅用了一个辅助交换单元。时间效率：总共要进行n-1趟冒泡，对n个记录的表进行一趟冒泡需要n-1次数值大小比较。移动次数：最好情况下，待排序列已有序，不需移动。冒泡排序最好的时间复杂度为O(n)。冒泡排序的最坏时间复杂度为O(n2)。冒泡排序的平均时间复杂度为O(n2)。冒泡排序是就地排