《noip复习资料汇总》由会员分享，可在线阅读，更多相关《noip复习资料汇总（80页珍藏版）》请在金锄头文库上搜索。
1、NOIP初赛复习,第一部分：复习,函数不能做为语句单独使用，多出现在条件和：的右边位置 过程无返回值，必须做为语句单独使用 辨别下面使用对错 ABS(-5); A:=ABS(-5); FILLCHAR(W,SIXZEOF(W),0); W:=FILLCHAR(W,SIXZEOF(W),0);,标准过程与函数,算术函数,求绝对值ABS：是英文单词absolute（绝对）的缩写，ABS(x)表示求x的绝对值 指数函数EXP、自然对数函数 LN：EXP是英文单词exponent（指数）的缩写，EXP(x)表示求以e为底x为指数的函数值 ，即EX；LN是英文单词logarithrm（自然对数）的缩写，
2、LN(x)表示求x的自然对数，即LOGeX Pascal中无幂运算，要求XY可以用后面的公式：XY=eYLNX (X0) e2.71828 平方函数SQR、正平方根函数SQRT：SQR是英文单词square（平方）的缩写；SQRT是英文单词square root（平方根）的缩写,类型转换函数,取整数函数TRUNC：如TRUNC(7.8)的值为7，TRUNC(-6.1)的值为-6 四舍五入函数ROUND：如ROUND(7.8)的值为8，ROUND(-6.1)的值为-6 序号函数ORD：返回参数的对应的序号；若参数为字符，则返回其ASCII码（0的ASCII码为48，A的ASCII码为65，a的A
3、SCII码为97）值，如ORD(B)的值为66；若参数为BOOLEAN，则ORD(TRUE)的值为，ORD(FALSE)的值为 字符函数CHR：返回序号所对应的字符，与ORD互为反函数；如CHR(66)的值为B,顺序函数与判断函数,前趋函数PRED：返回参数的前一个数据，若参数为第一项，则函数无意义 后继函数SUCC：返回参数的后一个数据，若参数为最后一项，则函数无意义 奇偶判断函数ODD：判断参数的奇偶性，当参数为偶数时，函数值为FALSE；当参数为奇数时，函数值为TRUE,字符串函数,字符串过程,FILLCHAR,FILLCHAR(S,N,CH)，给S填充N个相同的CH，用于初始化数组或字
4、符串，N常用SIZEOF(S)代替 var a:array 110 of arrtype; 执行fillchar(a,sizeof(a),0); 当arrtype为 1.real(其他实数类型差不多) 使得a中的元素全部成为0.0 2.integer(byte,word,longint,shortint都相同) 全部为0 3.boolean 全部为false 4.char 全部为#0 这里使用了函数sizeof(a)，其功能是返回变量a所占的总字节数,FILLCHAR,执行的是fillchar(a,size(a),255),结果又是怎样的？(a为integer或longint) 由于(255)
5、10=(11111111)2,故填充后,补码为11111111111111111111111111111111,原码为10000000000000000000000000000001,其值为-1,逻辑运算,设A=B=D=true，C=E=false，以下逻辑运算表达式值为真的有（ ）。 (多选) A. (AB)(CD)E B. (AB)C)DE) C. A(BCDE) D. (A(BC) DE 已知A = 35H，A05HA30H 的结果是：（ ）。A）30H B）05H C）35H D）53H (/表示，即交集，二进制运算中相当于and。 /表示，即并集，二进制运算中相当于or。),ABC,
6、C,集合运算,设全集 I = a, b, c, d, e, f, g, h，集合 A = a, b, c, d, e, f，B = c, d, e，C = a, d，那 么集合 A B C 为（ ）。(NOIP2005普及) A. c, e B. d, e C. e D. c, d, e E. d, f 为补集符号，即在此题中，将C中的a、d删掉,A,NOIP2004普及组,75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。,10,位
7、运算,在 Pascal 语言中，表达式 (21 xor 2)的值是（ ）A. 441 B. 42 C.23 D.24 E.25 将十进制数化为二进制 or:两者为0结果为0 and:两者为1结果为1 not：取反 xor:两者相异结果为1 负数符号位为1，其补码=反码+1，反码符号位不变 正数原码=反码 13 and -17=,C,13,位运算,shl:左移位运算:在没有超出范围时相当于a * 2n 。注意左移后符号位的变化 shr:右移位运算:相当于a div 2n,模运算,表达式(4 mod (-3)与(-4 mod 3)的值为( ) A.-1,-1 B.1,-1 C.-1,1 D.1,1
8、 (-14) mod (-3) 模运算的规律：结果与被除数的符号相同。即被除数为正，模为正，否则为负。结果与除数的符号没有关系 Div运算与mod运算取商的规律相同,B,二叉树的性质,二叉树具有以下重要性质： 性质1 二叉树第i层上的结点数目最多为2i-1(i1)。 证明：用数学归纳法证明： 归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。 归纳假设：假设对所有的j(1j2k-1-1。 另一方面，由性质2可得： n2k-1， 即：2k-1-ln2k-1 由此可推出：2k-1n2k，取对数后有： k-1log2nn，则结点i无左孩子(i为叶子结点)；否则其左孩
9、子是结点2i (3)如果2i+1n，则结点i无右孩子；否则其右孩子是结点2i+1,最小生成树,对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权(这棵树的代价)，权最小的生成树称为G的最小生成树(Minimum Spannirng Tree)。最小生成树可简记为MST。,普里姆(Prim)算法,算法思想 T=(U，TE)是存放MST的集合。 T的初值是(r，) 即最小生成树初始时只有一个红点r，没有红边。 T经过n-1次如下步骤操作，最后得到一棵含n个顶点，n-1条边的最小生成树 选择紫边集中一条轻边并扩充进T 将轻边连接的蓝点改红点 将轻边改红边 修改紫边集
10、,克鲁斯卡尔(Kruskal)算法,算法思想 T的初始状态 只有n个顶点而无边的森林T=(V， ) 按边长递增的顺序选择E中的n-1安全边(u，v)并加入T，生成MST 注意： 安全边指两个端点分别是森林T里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树 因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树。,编译原理,在下列关于计算机语言的说法中，不正确的是（ ）。 A. Pascal和C都是编译执行的高级语言 B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C. C+是历史上的第一个支持面向对象的计算机语
11、言 D. 与汇编语言相比，高级语言程序更容易阅读 20世纪60年代出现最早的面向对象程序设计语言Simula63 1972年PARC发布了Smalltalk的第一个版本。大约在此时，“面向对象”这一术语正式确定。Smalltalk被认为是第一个真正面向对象的语言,编译原理,18. 在下列关于计算机语言的说法中，正确的有（ ）。(多选) A. Pascal和C都是编译执行的高级语言 B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C. C+是历史上的第一个支持面向对象的计算机语言 D. 高级语言比汇编语言更高级，是因为它的程序的运行效率更高,AB,编译原理,20. 下列关
12、于高级语言的说法正确的有（ ）。(NOIP2005) A. Ada 是历史上的第一个高级语言 B. Pascal和C都是编译执行的高级语言 C. C+是历史上的第一个支持面向对象的语言 D. 编译器将高级语言程序转变为目标代码 E. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 FORTRAN第一个电脑高级语言，它是1954年美国的IBM的IT成果,BDE,编译原理,19.下列哪个（些）程序设计语言支持面向对象程序设计方法（ ）。(NOIP2004)A. C+ B. Object Pascal C. C D. Smalltalk E. Java 12. 下列关于高级语言的说法错误的是（ ）。(NOIP2005普及，单选)A. Fortran 是历史上的第一个面向科学计算的高级语言B. Pascal 和 C 都是编译执行的高级语言C. C+是历史上的第一个支持面向对象的语言D. 编译器将高级语言程序转变为目标代码E. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上,
