信息学奥赛NOIP初赛复习知识点+基本函数

11信息学奥赛NOIP初赛复习知识点+基本函数1被西方人誉为“计算机之父”的美籍匈牙利科学家、数学家冯·诺依曼于1945年发表了一个全新的存储程序通用电子计算机方案—EDVAC。EDVAC方案提出了著名的“冯·诺依曼体系结构”理论：（1）采用二进制形式表示数据和指令（2）采用存储程序方式（3）由运算器、存储器、控制器、输入设备和输出设备五大部件组成计算机系统2“图灵机”与“冯·诺伊曼机”齐名，被永远载入计算机的发展史中。1950年10月，图灵又发表了另一篇题为“机器能思考吗”的论文，成为划时代之作。也正是这篇文章，为图灵赢得了“人工智能之父”的桂冠。与计算机有关的最高奖项“图灵奖”。3常见的操作系统有：DOS、WIN32、WIN95、WIN98、WIN2000、WINXP、WIN2003、LINUX、4断电后能保存信息的有：ROM（只读存储器）、硬盘、软盘、光盘、U盘、MP3、MP4等；不能保存的主要是RAM（读写存储器）。5CPU又名中央处理器，它可以分成运算器、控制器和寄存器6Smalltalk被认为是第一个真正面向对象的语言7第一代语言：机器语言（0101001）；第二代语言：20世纪50年代，汇编语言，第三代语言：高级语言、算法语言，如BASIC，FORTRAN，COBOL，PASCAL，C；高级语言的特点是可读性强，编程方便；第四代语言：非过程化语言；SQL；第五代语言：智能性语言，PROLOG（代表）；还有：LISP，APL，SNOBOL，SIMULA。8编程时读入一个很大的二维数组，按行读和按列读相比，输入效率上（取决于数组的存储方式）。9希尔排序是一种不稳定的排序快速排序是冒泡排序的改进，是速度最快的排序方法排序方法时间复杂度最好时间复杂度最坏时间复杂度是否稳定空间复杂度简单排序（采用比较为主要操作的算法）插入排序O(n^2)O(n)O(n^2)稳定O(1)选择排序O(n^2)O(n^2)O(n^2)不稳定O(1)冒泡排序O(n^2)O(n)O(n^2)稳定O(1)快速排序O(nlogn)O(nlogn)O(n^2)不稳定O(logn)①n比较小的时候，适合插入排序和选择排序；②基本有序的时候，适合直接插入排序和冒泡排序；④n很大的时候，适合快速排序、堆排序、归并排序；⑤无序的时候，适合快速排序；⑥稳定的排序：冒泡排序、插入排序、归并排序、基数排序；⑦复杂度是O(nlogn)：快速排序、堆排序、归并排序；⑧辅助空间（大次大）：归并排序、快速排序；⑨好坏情况一样：简单选择排序（n^2），堆排序（nlogn），归并排序（nlogn）；⑩最好是O(n)的：插入排序、冒泡排序。10PASCAL语言中，表达式（21XOR2）的值是（23）11PASCAL语言，判断a不等于0且b不等于0的正确的条件表达式是（a0）and(b0)12高度为N的均衡的二叉树是：如果去掉叶结点及相应的树枝，它应该是高度为N-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（11）。13结点的度：一个结点的子树数目称为该结点的度树的度：所有结点中最大的度称为该树的度(宽度）。（3）树的深度（高度）：树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。树中最大的层次称为树的深度，亦称高度。14满二叉树：若深度为K的二叉树，共有2K-1个结点，即第I层有2I-1的结点，称为满二叉树。15完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树16二叉树的三个主要性质：性质1：在二叉树的第i（≥1）层上，最多有2i-1个结点性质2：在深度为k(k≥1)的二叉树中最多有2k-1个结点。性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。n0=n2+117数的表示：为了表达方便起见，常在数字后加一缩写字母后缀作为不同进制数的标识。各种进制数的后缀字母分别为：B：二进制数。Q：八进制数。D：十进制数。H：十六进制数。对于十进制数通常不加后缀，也即十进制数后的字母D可省略18广度优先需要用到的是队列，深度优先需要的是栈19回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。动态规划把多阶段过程转化为一系列单阶段问题，利用22各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。一、数学函数：Inc(i)使I:=I+1;Inc(I,b)使I:=I+b;Abs(x)求x的绝对值例：abs(-3)=3Chr(x)求编号x对应的字符。例：Chr(65)=’A’chr(97)=’a’chr(48)=’0’Ord(x)求字符x对应的编号。例:ord(‘A’)=65ord(‘a’)=97另外：ord(false)=0ord(true)=1Sqr(x)求x的平方。例：sqr(4)=16Sqrt(x)求x的开方.例：sqrt(16)=4round(x)求x的四舍五入例：round(4.5)=5trunc(x)求x的整数部分例：trunc(5.6)=5结果是integer型int(x)求x的整数部分例int(5.6)=5.0frac(x)求x的小数部分例frac(5.6)=0.6pred(x)求x的前导pred(‘b’)=’a’pred(5)=4pred(true)=falsesucc(x)求x的后继succ(‘b’)=’c’succ(5)=6succ(false)=trueodd(x)判断x是否为奇数。如果是值为true，反之值为false.Odd(2)=falseodd(5)=truepower(a,n)求a的n次方power(2,3)=8exp(b*ln(a))a的b次方random取0~1之间的随机数（不能取到1）randomize随机数的种子函数,在每次设置随机数时都要把这个函数放在最前面.Fillchar(a,size(a),0)数组初始化，即把数组a的值全部置为0二、字符串函数1.连接运算concat(s1,s2,s3…sn)相当于s1+s2+s3+…+sn.例：concat(‘11’,’aa’)=’11aa’;2.求子串。Copy(s,i,L)从字符串s中截取第i个字符开始后的长度为L的子串。例:copy(‘abdag’,2,3)=’bda’3.删除子串。过程Delete(s,i,L)从字符串s中删除第i个字符开始后的长度为L的子串。例：s:=’abcde’;delete(s,2,3);结果s:=’ae’4.插入子串。过程Insert(s1,s2,I)把s1插入到s2的第I个位置例：s:=abc;insert(‘12’,s,2);结果s:=’a12bc’5.求字符串长度length(s)例：length(‘12abc’)=56.搜索子串的位置pos(s1,s2)如果s1是s2的子串，则返回s1的第一个字符在s2中的位置，若不是子串，则返回0.例：pos(‘ab’,’12abcd’)=37.字符的大写转换。Upcase(ch)求字符ch的大写体。例：upcase(‘a’)=’A’8.数值转换为数串。过程Str(x,s)把数值x化为数串s.例：str(12345,s);结果s=’12345’9.数串转换为数值。过程val(s,x,i)把数串s转化为数值x,如果成功则i=0,不成功则i为无效字符的序数例：val(‘1234’,x,I);结果x:=1234xor:异或运算shr：位运算相当于/2shl：位运算相当于*2，但是比*运算快的多的多int:求一个实型数的整数部分arctan：反正切函数xor：异或运算，就是把两个数转换成二进制数，然后每位对应，如果相同（都是0或1）就得1，如果不同就得0shl：左位移（左位移一位=*2，左位移两位=*2^2……ashlb=a*2^b）shr：右位移（右位移一位=/2，右位移两位=/2^2……ashlb=a/2^b）取整函数int(x)注意：X是实型数，返回值也是实型的；返回的是X的整数部分，也就是说，X被截尾了（而不是四舍五入）