NOIP2012初赛模拟试题（二）
（ 普及 Pascal语言 二小时完成 ）
● ● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●
一． 单项选择题 （共10题，每题1.5分，共计15分。每题有且仅有一个正确答案。）
1、下列说法正确的是( )。
A. CPU的主频越高，其运算速度越快
B．存储器具有记忆能力，其中信息任何时候都不会丢失 C．两个显示器屏幕尺寸相同，则它们的分辨率必定相同 D．计算机系统可以分为硬件系统和系统软件两大部分
2、有一个数值2341，它与十六进制数4E1相等，那么该数值是( )。 A．五进制数 B．六进制数 C．七进制数 D．八进制数
3、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于( )数据结构。 A．栈 B．树 C．双向队列 D．广义表
4、表达式a*(c-b)／(d+e)的前缀表达式是()。
A．acbde*-／+ B．*-／+achde C．-cb*a／+de D．／*a-cb+de
5、在一个具有N个顶点的无向图中，要连通全部的顶点至多需要边的数目是( )。 A．N B．N-l C．N*(N-1)／2 D．N*(N-1)
6. 二进制数00100100和00010100的和是( )。
A．00101000 B．001010100 C．01000100 D．00111000
7、一个队列开始为空，数列1，2，3??按顺序进队，经过操作序列“进、进、出、进、进、出、进、进、进、出、进、出”后，队列中的倒数第2个元素是（ ） A．5 B．6 C．7 D．8
8、表达式28 div 4 mod (-3)+trunc(3.675)的值是( )。 A．5 B．4 C．3 D．2
9、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为( )。
A．4 B．5 C．6 D．7
10、存储400个24*24点阵汉字的字模所需的存储容量为( )。 A．255KB B．75KB C．37.5KB D．28.125KB
11、存储一幅分辨率为1024*768像素的256色图片需要的存储容量为( )。
第1页 共7页
A．768KB B．0.7MB C．375KB D．28.125KB
12、操作系统、数据库管理系统和程序设计语言处理软件属于( )。
A．管理软件 B．系统软件 C编辑软件 D．应用软件
13、设有字符序列(Q,H,C,Y,P,A,M,S,R,D,F,X)，问新序列(F,H,C,D,P,A,M,Q,R,S,Y,X)是下列
哪个排序算法一趟扫描的结果( )
A．起泡排序 B．初始步长为4的希尔排序
C．二路归并排序 D.以第一元素为分界元素的快速排序
14、对于线性表(18,25,63,50,42,32,90,66)进行散列存储时，若选用H(K)=K mod x作为散列
函数，对于x值的选取，下列最合适的是 （ ） A．8 B 9 C．10 D．11
15、链表不具有的特点是（ ）。
A．可随机访问任一个元素 B．插入删除不需要移动元素
C．不必事先估计存储空间 D．所需空间与线性表的长度成正比
16、设E={a，b，c，d，e}，A={a,b}，B={a,b,e}，C={b,d}，则(A∩B)∪～C=( )。
A．{a,b,d} B．{b} C．{a,b,c,e} D．{a,c,e}
17、下面( )语言不是常用的网页制作语言。
A．PHP B．C++ C．Java D．Html
18、在具有n个结点点的完全图中需删去( )条边才能得n个结点到树。
A．(n-1)(n-2)／2 B．n-1 C．(n-1)(n-2) D．n
19、对于下图，至少要加( )条边，使之存在一条路径，经过图中每条边一次且仅一次。
A．1 B．2 C3 D．4
20、一棵含有101个结点的完全二叉树存储在数组A[1..101]中,对1≤k≤101,若 A[k]是叶子结
点,则k的最小值是：（ ） A．51 B．50 C．49 D．48
三．问题求解（共2题，每空5分，共计10分）
1．马路上有编号为1，2，3，?，10的十盏路灯，为了既能节约用电，又能看清路面(不影响走路照明)，可以把其中的i盏灯关掉，但不能同时关掉相邻的两盏或两盏以上的灯。在两端的灯也不能关掉的情况下，求满足条件的关灯办法有_________种?
第2页 共7页
2．若一个数(首位不为零)从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个十进制数56，将56加65(即把56从右向左读)，得到121是一个回文数。又如，对于十进制数87，
STEPl：87+78=165 STEP2：165+56l=726 STEP3：726+627=l353 SFEP4：1353+3531=4884
在这里的一步是指进行了一次N进制的加法，上例最少用4步得到回文数4884。 那么，对于九进制数87，最少用_________步得到回文数。 四．阅读程序写结果（共4题，每题8分，共计32分） 1. program t1;
const n=7; var i,k,m,j:integer;
a:array[0..10] of integer; begin m:=10; repeat read(k); j:=k mod n; a[j]:=1; m:=m-1; until m=0; k:=0;
for i:=1 to 10 do if a[i]=0 then k:=k+1; write(k); end.
输入:2005 2006 2007 2008 2009 2010 2011 2012 2013 2014
输出:_________________
2. program t2;
Const Max=2000;
Var a:Array[1..Max+2]of Byte; i,top,w1,w2,t:Integer; Procedure Do_with(x,y:Integer); Var s:integer; Begin s:=x*y ; If s<10 Then
Begin Inc(t); a[t]:=s; Exit;End; t:=t+1; a[t]:=s Div 10; t:=t+1; a[t]:=s Mod 10; End; begin
a[1]:=2; a[2]:=3; top:=0; t:=2; Repeat
Top:=top+1;
第3页 共7页
Do_with(a[top],a[top+1]); Until t>=Max; read (w1,w2);
For i:=W1 To w2 Do Write(a[i]:2); End. 输入:15 25 输出:_______________
3. program t3;
var a,x,y,z:Integer;
procedure p(x,y:integer;var z:integer);
begin z:=y-x-z;
writeln(x,' ' ,y,' ',z); end;
function q(m:integer):integer; begin z:=z+m; q:=succ(m);
end; begin
x:=2; y:=5; z:=9; p(5,x+y+z,x); writeln(x,' ',Y,' ',z); a:=q(2);
a:=a*q(z); writeln(a,' ',z); end.输出:___________
4.program t4;
const n=4;
type se=array[1..n*2]of char; var i,j,i1,j1,k,s,t,s1,L,swap:integer; temp:char; a:se; Begin
for i:=1 to n*2 do read(a[i]); readln; s:=0; t:=0; for i:=1 to n*2 do
if a[i]='1' then s:=s+1 else if a[i]='0' then t:=t+1; if(s<>n) or (t<>n) then writeln('error') else begin s1:=0;
for i:=1 to 2*n-1 do if a[i]<>a[i+1] then s1:=s1+1;
第4页 共7页
writeln('jamp=',s1); swap:=0;
for i:=1 to 2*n-1 do for j:=i+1 to 2*n do if a[i]<>a[j] then begin
temp:=a[i];a[i]:=a[j];a[j]:=temp; s:=0;
for L:=1 to 2*n-1 do
if a[L]<>a[L+1] then s:=s+1;
if s>swap then begin swap:=s; i1:=i; j1:=j; end; temp:=a[i]; a[i]:=a[j]; a[j]:=temp; end; if swap>0 then
writeln('maxswap=', swap-s1, 'i=', i1, 'j=', j1) end; End.
输入:00100111 输出:_________
五．完善程序 (前5空，每空2分，后6空，每空3分，共28分)
1．Fibonacci数列的规律是:前2个数均为1,从第3个数开始每个数等于它前面两个数之和,
即:1,1,2,3,5,8,13,21,34,55,89,144,233,377,?已知任意一个大于0的整数可以表示为若干个互不相同的Fibonacci之数和. 例如:121=89+21+8+3
下面的程序是由键盘输入一个正整数n,输出组成n的互不相同的fihonacci数. 输入样例:121
输H{样例:121=89+21+8+3 [算法设计](n=121为例)
(1)寻找小于或等于n的最大的fibonacci数a(例如89),并以a作为组成n的一个数输出. (2)若n≠a,则以n-a作为新的任意正整数(例如32),重复步骤1;
若n=a,则结束.程序中的函数find返回小于或等于n的最大的fibonacci数.
var n,t:integer;
data:array[1．．10000] of integer;
procedure print(t); var I:integer; begin
write(data[1]);
for i:=2 to t do write(‘+’,data[i]); end;
第5页 共7页