搜索
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（自然对数）的缩写，LN(x)表示求x的自然对数，即LOGeX•Pascal中无幂运算，要求XY可以用后面的公式：XY=eYLNX(X0)e≈2.71828•平方函数－SQR、正平方根函数－SQRT：SQR是英文单词square（平方）的缩写；SQRT是英文单词squareroot（平方根）的缩写类型转换函数•取整数函数－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’的ASCII码为97）值，如ORD(‘B’)的值为66；若参数为BOOLEAN，则ORD(TRUE)的值为１，ORD(FALSE)的值为０•字符函数－CHR：返回序号所对应的字符，与ORD互为反函数；如CHR(66)的值为'B'顺序函数与判断函数•前趋函数－PRED：返回参数的前一个数据，若参数为第一项，则函数无意义•后继函数－SUCC：返回参数的后一个数据，若参数为最后一项，则函数无意义•奇偶判断函数－ODD：判断参数的奇偶性，当参数为偶数时，函数值为FALSE；当参数为奇数时，函数值为TRUE字符串函数函数名功能说明CONCAL(ST1,...,STn)将N个字符串连接起来等效于ST1+...+ST2COPY(S,M,N)取S中第M个字符开始的N个字符若M大于S的长度，则返回空串；否则，若M+N大于s的长度，则截断LENGTH(S)求s的动态的长度返回值为整数POS(SUB,S)在S中找子串SUB返回值为SUB在S中的位置，为byte型UPCASE(CH)将字母CH转换成大写字母若CH不为小写字母，则不转换字符串过程过程名功能说明INSERT(SOUR,S,M)在S的第M个字符位置处插入子串SOUR若返回串超过255，则截断DELETE(S,M,N)删除S中第M个字符开始的N个字符串若M大于S的长度，则不删除；否则，若M+N大于S的长度，则删除到结尾STR(X[:W[:D]],S)将整数或实数X转换成字符串SW和D是整型表达式，意义同带字宽的write语句VAL(S,X,CODE)将字符串S转换成整数或实数X若S中有非法字符，则CODE存放非法字符在S中的下标；否则，CODE为零,CODE为整型FILLCHAR•FILLCHAR(S,N,CH)，给S填充N个相同的CH，用于初始化数组或字符串，N常用SIZEOF(S)代替•vara:array[1..10]ofarrtype;执行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)10=(11111111)2,故填充后,补码为11111111111111111111111111111111,原码为10000000000000000000000000000001,其值为-1逻辑运算设A=B=D=true，C=E=false，以下逻辑运算表达式值为真的有（）。(多选)A.(A∧B)∨(C∧D)∨EB.(((A∧B)∨C)∧D∧E)C.A∧(B∨C∨D∨E)D.(A∧(B∨C))∧D∧E•已知A=35H，A/\05H\/A/\30H的结果是：（）。A）30HB）05HC）35HD）53H•(/\表示∩，即交集，二进制运算中相当于and。\/表示∪，即并集，二进制运算中相当于or。)ABCC集合运算•设全集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}•~为补集符号ANOIP2004普及组•75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有名儿童没有玩过其中任何一种。10位运算•在Pascal语言中，表达式(21xor2)的值是（）A.441B.42C.23D.24E.25将十进制数化为二进制or:两者为0结果为0and:两者为1结果为1not：取反xor:两者相异结果为1负数符号位为1，其补码=反码+1，反码符号位不变正数原码=反码13and-17=C13位运算•shl:左移位运算:在没有超出范围时相当于a*2n。注意左移后符号位的变化•shr:右移位运算:相当于adiv2n模运算•表达式(4mod(-3))与(-4mod3)的值为()A.-1,-1B.1,-1C.-1,1D.1,1•(-14)mod(-3)•模运算的规律：结果与被除数的符号相同。即被除数为正，模为正，否则为负。结果与除数的符号没有关系•Div运算与mod运算取商的规律相同B二叉树的性质•二叉树具有以下重要性质：性质1二叉树第i层上的结点数目最多为2i-1(i≥1)。•证明：用数学归纳法证明：归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。归纳假设：假设对所有的j(1≤ji)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。二叉树的性质•性质2深度为k的二叉树至多有2k-1个结点(k≥1)。•证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：20+21+…+2k-1=2k-1故命题正确。二叉树的性质•性质3在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。•证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：n=n0+n1+n2(式子1)另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：n=n1+2n2+1(式子2)由式子1和式子2得到：n0=n2+1完全二叉树的性质4•性质4具有n个结点的完全二叉树的深度为:或(表示不大于的最大整数)•证明：设所求完全二叉树的深度为k。由完全二叉树定义可得：深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：n2k-1-1。另一方面，由性质2可得：n≤2k-1，即：2k-1-ln≤2k-1由此可推出：2k-1≤n2k，取对数后有：k-1≤log2nk又因k-1和k是相邻的两个整数，故有由此即得：完全二叉树的性质5•性质5如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到层，每层从左到右)，则对任一结点i(1=i=n)，有：•(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是结点•(2)如果2in，则结点i无左孩子(i为叶子结点)；否则其左孩子是结点2i•(3)如果2i+1n，则结点i无右孩子；否则其右孩子是结点2i+1最小生成树•对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权(这棵树的代价)，权最小的生成树称为G的最小生成树(MinimumSpannirngTree)。最小生成树可简记为MST。普里姆(Prim)算法•算法思想T=(U，TE)是存放MST的集合。①T的初值是({r}，￠)即最小生成树初始时只有一个红点r，没有红边。②T经过n-1次如下步骤操作，最后得到一棵含n个顶点，n-1条边的最小生成树⒈选择紫边集中一条轻边并扩充进T⒉将轻边连接的蓝点改红点⒊将轻边改红边⒋修改紫边集克鲁斯卡尔(Kruskal)算法•算法思想①T的初始状态只有n个顶点而无边的森林T=(V，￠)②按边长递增的顺序选择E中的n-1安全边(u，v)并加入T，生成MST注意：安全边指两个端点分别是森林T里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树。编译原理•在下列关于计算机语言的说法中，不正确的是（）。A.Pascal和C都是编译执行的高级语言B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C.C++是历史上的第一个支持面向对象的计算机语言D.与汇编语言相比，高级语言程序更容易阅读•20世纪60年代出现最早的面向对象程序设计语言Simula63•1972年PARC发布了Smalltalk的第一个版本。大约在此时，“面向对象”这一术语正式确定。Smalltalk被认为是第一个真正面向对象的语言编译原理•18.在下列关于计算机语言的说法中，正确的有（）。(多选)•A.Pascal和C都是编译执行的高级语言•B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上•C.C++是历史上的第一个支持面向对象的计算机语言•D.高级语言比汇编语言更高级，是因为它的程序的运行效率更高AB编译原理•20.下列关于高级语言的说法正确的有（）。(NOIP2005)A.Ada是历史上的第一个高级语言B.Pascal和C都是编译执行的高级语言C.C++是历史上的第一个支持面向对象的语言D.编译器将高级语言程序转变为目标代码E.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上•FORTRAN第一个电脑高级语言，它是1954年美国的IBM的IT成果BDE编译原理•19.下列哪个（些）程序设计语言支持面向对象程序设计方法（）。(NOIP2004)A.C++B.ObjectPascalC.CD.SmalltalkE.Java•12.下列关于高级语言的说法错误的是（）。(NOIP2005普及，单选)A.Fortran是历史上的第一个面向科学计算的高级语言B.Pascal和C都是编译执行的高级语言C.C++是历史上的第一个支持面向对象的语言D.编译器将高级语言程序转变为目标代码E.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上ABDEC编译原理•14．下列关于程序语言的叙述，不正确的是()。(NOIP2003普及)A)编写机器代码不比编写汇编代码容易。B)高级语言需要编译成目标代码或通过解释器解释后才能被CPU执行。C)同样一段高级语言程序通过不同的编译器可能