noip初中普及组模拟试卷
- 格式：docx
- 大小：20.56 KB
- 文档页数：6
NOIP考前模拟测试一、选择题（每空1.5分，共30分）1、关于图灵机下面的说法哪个是正确的（）A) 图灵机是世界上最早的电子计算机。
B) 由于大量使用磁带操作，图灵机运行速度很慢。
C) 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用D) 图灵机只是一个理论上的计算模型。
2、关于ASCII，下面哪个说法是正确的（）A) ASCII码就是键盘上所有键的唯一编码。
B) 一个ASCII码使用一个字节的内存空间就能够存放。
C) 最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。
D) ASCII码是英国人主持并推广使用的。
3、表达式a*(b+c)-d的后缀表达式是（）A) abcd*+ B) abc+*d- C) abc*+d- D) -+*abcd4、有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。
则最多需要几次比较就能确定是否存在所查找的元素（）A) 11次B) 12次C) 13次D) 14次5、2E+03表示（）A) 2.03 B) 5 C)8 D)20006、以下逻辑表达式的值为真的是（）A) P∨(—P∧Q)∨(—P∧—Q) B)Q∨(—P∧Q)∨(P∧—Q)C)P∨Q∨(P∧—Q)∨(—P∧Q) D)P∨—Q∨(P∧—Q)∨(—P∧—Q)7、设X、Y、Z分别代表三进制下的一位数字，若等式XY+ZX=XYX在三进制下成立，那么同样在三进制下，等式XY*ZX=( )也成立。
A) YXZ B) ZXY C) XYZ D)XZY8、主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了（）。
A) 寄存器B)高速缓存C)内存D)外存9、一片容量为8GB的SD卡能存储大约（）张大小为2MB的数码相片。
A) 1600 B)2000 C4000 D)1600010、如果根节点的深度记为1，则一颗恰有2011个叶节点的二叉树的深度最少为（）A) 10 B)11 C) 12 D)1311、在含有n个元素的双向链表中查询是否存在关键字为k的元素，最坏情况下运行的时间复杂度为（）A) O(1) B) O(logn) C) O(n) D) O(nlogn)12、现有一段文言文，要通过二进制哈夫曼编码进行压缩。
简单起见，假设这段文言文只有4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、200.那么“也”字的编码长度是（）A) 1 B) 2 C) 3 D) 413、目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。
A) 硅B) 铜C) 锗D) 铝14、如果一颗二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）A) ABC B) CBA C) ACB D)BAC15、使用冒泡排序对序列进行升序排列，没执行一次交换操作，系统将会减少1个逆序对，因此序列5，4，3，2，1需要执行（）次操作，才能完成冒泡排序。
A) 0 B)5 C)10 D) 1516、原字符串中任意一段连续的字符所组成的新字符串称为子串，则字符“AAABBBCCC”共有（）个不同的非空子串。
A) 3 B) 12 C) 36 D) 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,f B) a,c,f,e,b,d C) a,e,b,c,f,d D) a,e,d,f,c,b18、HTML中<body text=red>，表示（）A) 正在点击文字的色彩是红色；B) 可链接文字的色彩是红色；C) 非可链接文字的色彩是红色；D) 已链接文字的色彩是红色19、以下取自中国计算机学会2011年4月14日制定的规则不正确的是（）A) 当参赛选手对一道试题提交多份使用不同后缀的源程序文件时，测试系统按照.c,.cpp,.pas 的顺序选取第一份存在的文件进行编译和测评，并忽略其他文件。
B)除另有规定外，每道题参赛程序源文件不得大于100KB。
C) 如果选手目录下没有程序，就会任意选择一个子目录里的源程序进行测评。
D) 对于Pascal程序禁止使用内嵌汇编，并禁止使用任何编译开关。
20、把64位非零浮点数强制转换为32位浮点数后，不可能（）A) 大于原数B) 小于原数C) 等于原数D) 与原数符号相反。
二、问题求解（每题5分，共10分）第一题：5男5女坐成一桌（10个座位），同性别不能相邻的坐法共有________种。
第二题：小陈现有2个任务A,B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。
在任何时候，小陈只能专心做某个任务的一个步骤。
但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次任务第一个未做的步骤继续。
每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而……a->b3->a3->b2……是不合法的。
小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。
当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。
试计算小陈饭前已做的可能的任务步骤序列共有__________种。
三、阅读程序；一、constSIZE = 100;varn, i, sum, x:integer;a:array[1..SIZE] of integer;beginreadln(n);fillchar(a,sizeof(a),0);for i:=1 to n dobeginread(x);inc(a[x]);end;i:=0;sum:=0;while sum<(n div 2 +1) dobegininc(i);sum:=sum+a[i];end;writeln(i);end.输入：114 5 6 6 4 3 3 2 3 2 1 输出：二、vara,b:integer;function work(a,b:integer):integer; beginif a mod b <> 0 thenwork := work(b, a mod b) elsework := b;end;beginread(a,b);writeln(work(a,b));end.输入：20 12输出：三、varn, i , j : integer;a: array[1..100,1..100] of integer; function solve(x,y:integer):integer; varu,v:integer;beginif x=n thenbeginsolve:=a[x,y];exit;end;u:=solve(x+1,y);v:=solve(x+1,y+1);if u>v then solve:=a[x,y]+uelse solve:=a[x,y]+v;end;beginread(n);for i:=1 to n dofor j:=1 to i doread(a[i,j]);writeln(solve(1,1);end.输入：52-1 42 -1 -2-1 6 4 03 2 -1 5 8输出：四、vari,a,b,c,x,y:integer;p:array[0..4] of integer;beginy:=20;for i:=0 to 4 do read(p);readln;a:=(p[0]+p[1])+(p[2]+p[3]+p[4]) div 7;b:=p[0]+p[1] div ((p[2]+p[3]) div p[4]);c:=p[0]*p[1] div p[2];x:=a+b-p[(p[3]+3) mod 4];if (x>10)then y:=y+(b*100-a) div (p[p[4] mod 3] * 5)else y:=y+20+(b*100-c) div (p[p[4] mod 3] * 5);writeln(x,’x’,y);end.{注：本例中，给定的输入数据可以避免分母为0或数组元素下标越界}输入：6 6 5 5 3输出：四、完善程序（前5空，每空2分，共计28分）1. （子矩阵）输入一个n1+m1d哦矩阵a，和n2+m2的矩阵b，问a中是否存在子矩阵和b 相等。
若存在，输出所有子矩阵左上角的坐标；若不存在输出“There is no answer”。
constSIZE = 50;varn1,m1,n2,m2,i,j,k1,k2:integer;a,b:array[1..SIZE,1..SIZE] of integer;good, haveAns : boolean;beginreadln(n1,m1);for i:=1 to n1 dofor j:=1 to m1 doread(a[i,j]);readln(n2,m2);for i:=1 to n2 dofor j:=1 to m2 do____ _______haveAns := false;for i:=1 to n1-n2+1 dofor j:=1 to __ ____ dobegin___●_______;for k1:=1 to n2 dofor k2:=1 to _❍____ doif a[i+k1-1,j+k2-1] <> b[k1,k2] thengood:=false;if good thenbeginwriteln(i, ‘‘,j);_____⏹_________end;end;if not haveAns thenwriteln(‘There is no answer’);end.2. （二叉查找树）二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。
试判断一棵树是否为二叉查找树。
输入的第一行包含一个整数n，表示这颗树有n个顶点，编号为1，2，…，n，其中编号为1的为根节点。
之后的第i行有三个数value，left_child，right_child，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用0代替。
输出1表示这颗树是二叉查找树，输出0则表示不是。
