noip初中普及组模拟试卷

1、NOIP考前模拟测试一、选择题(每空1.5分，共30分)1、关于图灵机下面的说法哪个是正确的()图灵机是世界上最早的电子计算机。由于大量使用磁带操作，图灵机运行速度很慢。图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用图灵机只是一个理论上的计算模型。2、关于ASCII,下面哪个说法是正确的()ASCII码就是键盘上所有键的唯一编码。一个ASCII码使用一个字节的内存空间就能够存放。C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。D)ASCII码是英国人主持并推广使用的。3、表达式a*(b+c)-d的后缀表达式是()A)abcd*+B)abc+*d-C)abc*+

2、d-D)-+*abcd4、有一个由4000个整数构成的顺序表,假定表中的元素已经按升序排列,采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素()A)11次B)12次C)13次D)14次5、2E+03表示()A)2.03B)5C)8D)20006、以下逻辑表达式的值为真的是()A)PV(-PAQ)V(PAQ)B)QV(-PAQ)V(PAQ)C)PVQV(PAQ)V(-PAQ)D)PVQV(pAQ)V(pAQ)7、设X、Y、Z分别代表三进制下的一位数字，若等式XY+ZX=XYX在三进制下成立，那么同样在三进制下，等式XY*ZX=()也成立。A)YXZB)ZXYC)XYZD)

3、XZY8、主存储器的存取速度比中央处理器(CPU)的工作速度慢得多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了()。A)寄存器B)高速缓存C)内存D)外存9、一片容量为8GB的SD卡能存储大约()张大小为2MB的数码相片。A)1600B)2000C4000D)1600010、如果根节点的深度记为1,则一颗恰有2011个叶节点的二叉树的深度最少为()A)10B)11C)12D)1311、在含有n个元素的双向链表中查询是否存在关键字为k的元素，最坏情况下运行的时间复杂度为()A)O(1

4、)B)O(logn)C)O(n)D)O(nlogn)12、现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只有4个汉字“之”、“乎”、“者”、“也”组成,它们出现的次数分别为700、600、300、200.那么“也”字的编码长度是()A)1B)2C)3D)413、目前计算机芯片(集成电路)制造的主要原料是(),它是一种可以在沙子中提炼出的物质。A)硅B)铜C)锗D)铝14、如果一颗二叉树的中序遍历是BAC,那么它的先序遍历不可能是()A)ABCB)CBAC)ACBD)BAC15、使用冒泡排序对序列进行升序排列，没执行一次交换操作，系统将会减少1个逆序对，因此序列5，4，

5、3，2，1需要执行()次操作，才能完成冒泡排序。A)0B)5C)10D)1516、原字符串中任意一段连续的字符所组成的新字符串称为子串，则字符AAABBBCCC”共有()个不同的非空子串。A)3B)12C)36D)4517、无向图G=(V,E)，其中：V=a,b,c,d,e,f，E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是()A)a,b,e,c,d,fB)a,c,f,e,b,dC)a,e,b,c,f,dD)a,e,d,f,c,b18、HTML中，表示()A)正在点击文字的色彩是红色；B)可链接文字的色彩是

6、红色；C)非可链接文字的色彩是红色；D)已链接文字的色彩是红色19、以下取自中国计算机学会2011年4月14日制定的规则不正确的是()A)当参赛选手对一道试题提交多份使用不同后缀的源程序文件时，测试系统按照.c,.cpp,.pas的顺序选取第一份存在的文件进行编译和测评，并忽略其他文件。B)除另有规定外，每道题参赛程序源文件不得大于100KB。C)如果选手目录下没有程序，就会任意选择一个子目录里的源程序进行测评。D)对于Pascal程序禁止使用内嵌汇编，并禁止使用任何编译开关。20、把64位非零浮点数强制转换为32位浮点数后，不可能()A)大于原数B)小于原数C)等于原数D)与原数符号相反。二

7、、问题求解(每题5分，共10分)第一题：5男5女坐成一桌(10个座位)，同性别不能相邻的坐法共有种。第二题：小陈现有2个任务A,B要完成，每个任务分别有若干步骤如下：A=a1-a24a3,B=b1-b24b34b44b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后,切换至另一个任务,从上次任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如a24b24a34b3是合法的，而a-b3-a34b2是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。

8、试计算小陈饭前已做的可能的任务步骤序列共有种。三、阅读程序；.constSIZE=100;varn,i,sum,x:integer;a:array1.SIZEofinteger;beginreadln(n);fillchar(a,sizeof(a),0);fori:=1tondobeginread(x);inc(ax);end;i:=0;sum:=0;whilesum(ndiv2+1)dobegininc(i);sum:=sum+ai;end;writeln(i);end.输入：1145664332321输出：二、vara,b:integer;functionwork(a,b:integer)

9、:integer;beginifamodb0thenwork:=work(b,amodb)elsework:=b;end;beginread(a,b);writeln(work(a,b);end.输入：2012输出：三、varn,i,j:integer;a:array1.100,1.100ofinteger;functionsolve(x,y:integer):integer;varu,v:integer;beginifx=nthenbeginsolve:=ax,y;exit;end;u:=solve(x+1,y);v:=solve(x+1,y+1);ifuvthensolve:=ax,y+u

10、elsesolve:=ax,y+v;end;beginread(n);fori:=1tondoforj:=1toidoread(ai,j);writeln(solve(1,1);end.输入：52-142-1-2-164032-158输出：四、vari,a,b,c,x,y:integer;p:array0.4ofinteger;beginy:=20;fori:=0to4doread(p);readln;a:=(p0+p1)+(p2+p3+p4)div7;b:=p0+p1div(p2+p3)divp4);c:=p0*p1divp2;x:=a+b-p(p3+3)mod4;if(x10)theny:

11、=y+(b*100-a)div(pp4mod3*5)elsey:=y+20+(b*100-c)div(pp4mod3*5);writeln(x,x,y);end.注：本例中，给定的输入数据可以避免分母为0或数组元素下标越界输入：66553输出：四、完善程序（前5空，每空2分，共计28分）.（子矩阵）输入一个n1+m1d哦矩阵a,和n2+m2的矩阵b,问a中是否存在子矩阵和b相等。若存在，输出所有子矩阵左上角的坐标；若不存在输出“Thereisnoanswer”。constSIZE=50;varn1,m1,n2,m2,i,j,k1,k2:integer;a,b:array1.SIZE,1.SIZ

12、Eofinteger;good,haveAns:boolean;beginreadln(n1,m1);fori:=1ton1doforj:=1tom1doread(ai,j);readln(n2,m2);fori:=1ton2doforj:=1tom2dohaveAns:=false;fori:=1ton1-n2+1doforj:=1to_dobeginfork1:=1ton2dofork2:=1to_doifai+k1-1,j+k2-1bk1,k2thengood:=false;ifgoodthenbeginwriteln(i,j);end;end;ifnothaveAnsthenwrite

13、ln(Thereisnoanswer);end.(二叉查找树)二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。输入的第一行包含一个整数n,表示这颗树有n个顶点，编号为1,2,树n,其中编号为1的为根节点。之后的第i行有三个数value，left_child，right_child，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点,则用0代替。输出1表示这颗树是二叉查找树,输出0则表示不是。programBst;constSIZE=100;constINFINITE=1000000;typenode=recordleft_child,right_child,value:longint;end;vara:array1.SIZEofnode;i,n:longint;functionis_bst(root,lower_bound,upper_bound:longint):longint;varcur:longint;beginifroot=0thenbeginis_bst:=1;exit;end;cur:=aroot.value;if(curlow