初赛模拟试题（一）

NOIP20100初赛模拟试题（⼀）（普及 Pascal语⾔⼆⼩时完成）

●●全部试题答案均要求写在答卷纸上，写在试卷纸上⼀律⽆效●●

⼀．单项选择题（共10题，每题1.5分，共计15分。每题有且仅有⼀个正确答案。）1、建⽴了计算机最主要的结构原理的⼈是（）。A. 图灵B. ⽐尔·盖茨C. ·诺伊曼D. 克拉拉·丹E. 哥德尔

2、设a、b、c是三个布尔型(boolean)的变量，则表达式(a∨?b)∧(b∨?c)∧(c∨?a)∧(a∧?a)∧(b∧?b)的值（）。A. 始终为trueB. 始终为false

C. 当且仅当c为true时为falseD. 当且仅当a与b均为true时为trueE. 依赖于a、b、c三者的值

3、设a、b为两个浮点(float)型变量，下⾯的表达式中最有可能为真的是（）。A. a=b

B. a*a+2*a*b+b*b=(a+b)*(a+b)C. (a+b)*(a-b)+b*b-a*a<0.0001D. a/b=1/(b/a)

E. sqrt(a)*sqrt(b)=sqrt(a*b)

4、下⾯的数据中，在编程中⽤长整型(longint)表⽰最恰当的是（）。A. 宇宙中的原⼦数⽬

B. ⼀头⼤象的体重（⽤吨表⽰）C. 明的⾝⾼（⽤厘⽶表⽰）D. ⼀个⼭村的准确⼈⼝数

E. 从现在（2010年）到2012奥运会开幕的倒计时秒数

5、⼀个包含n个分⽀结点（⾮叶结点）的⾮空满k叉树，k>=1，它的叶结点数⽬为：A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+16. 表达式a*(b+c)-d的后缀表达式是：A) abcd*+-B) abc+*d-C) abc*+d-D) -+*abcd

7、最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使⽤的元素给与

较短的唯⼀编码，以提⾼通讯的效率。下⾯编码组合哪⼀组不是合法的前缀编码。A)（00，01，10，11）B)（0，1，00，11）C)（0，10，110，111）D)（1，01，000，001）

8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：A) 平均情况O(nlog2n)，最坏情况O(n2)B) 平均情况O(n)，最坏情况O(n2)C) 平均情况O(n)，最坏情况O(nlog2n)D) 平均情况O(log2n)，最坏情况O(n2)

9、佳佳在⽹上购买了⼀个空间，建设了⼀个。那么，他向上上传⽹页时最有可能采⽤的⽹络协议是（）。A. HTTPB. TCPC. POP3D. FTPE. BT

10、⼀个⾳乐爱好者收藏有100⾸MP3格式的⾳乐，这些⾳乐的编码率都是192Kbps，平均每⾸⾳乐的时长为3min，他要通过⽹络将这些⾳乐传送给另⼀个⼈，假设⽹络速度恒定为512KB/s，则他传送这些⾳乐⼤概需要（）。A. 72sB. 843sC. 112.5minD. 3h48min16sE. 超过24⼩时

⼆．不定项选择题（共10题，每题1.5分，共计15分。每题正确答案的个数不少于1。多选或少选均不得分）。1、(7f)16 + (10010101)2 的运算结果等于（）。A. (114)16B. (276)10C. (100010100)2D. (11d)16E. (731)8

2、设a、b、c是三个布尔（boolean）型变量，若表达式a∧?b∧c为true，则下列表达式⼀定为true的是（）。A. (a∧(b∨c))∨(?a)B. (b∧a)∨(a∧c)∨(c∧b)C. a∧b∧cD. (b∨a)∧(?(a∨b))E. 以上皆错

3、下⾯的前序遍历结果不可能是由⼀棵排序⼆叉树产⽣的有（）。A. 1、2、3、4、5、6、7、8B. 1、4、3、6、7、8、5、2C. 8、7、6、5、4、3、2、1D. 6、7、8、5、4、3、2、1E. 以上皆错

4、设想这样⼀种数据结构，它有PUSH和POP两个操作。其中PUSH操作就是将⼀个元素加⼊到这个数据结构中，⽽当第k次调⽤POP元素时（保证这个数据结构中有元素），选择其中的⼀个元素返回并删除，若k是奇数，选择的是元素中的最⼤值，若k是偶数，选择的是元素中的最⼩值。如果调⽤PUSH操作放⼊数据结构中的元素依次是1、2、3、4、5、6，则下列序列中可能通过适当的POP操作产⽣的有（）。A. 1、2、3、4、5、6B. 1、2、3、4、6、5C. 6、1、5、2、4、3D. 2、1、6、3、5、4E. 3、1、4、2、6、5

5、下⾯的软件必须在联⽹状态下才能正常使⽤的有（）。A. BitTorrentB. Mozilla FirefoxC. Red Hat LinuxD. MSN MessengerE. WinZip

6、若3个顶点的⽆权图G的邻接矩阵⽤数组存储为{{0，1，1}，{1，0，1}，{0，1，0}}，假定在具体存储中顶点依次为: v1，v2，v3关于该图，下⾯的说法哪些是正确的：A) 该图是有向图。B) 该图是强连通的。

C) 该图所有顶点的⼊度之和减所有顶点的出度之和等于1。

D) 从v1开始的深度优先遍历所经过的顶点序列与⼴度优先的顶点序列是相同的。

7、下⾯的硬件接⼝中既不可以连接声卡、⼜不可以连接⿏标的通讯设备或外设接⼝有（）。A. PCIB. USBC. BlueToothD. 红外E. 以上皆错

8、散列表的地址区间为0-10,散列函数为H(K)=K mod 11。采⽤开地址法的线性探查法处理

冲突，并将关键字序列26，25，72，38，8，18，59存储到散列表中，这些元素存⼊散列表的顺序并不确定。假定之前散列表为空，则元素59存放在散列表中的可能地址有：A) 5 B) 7 C) 9 D) 10

9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发⽣改变，下列哪些排序算法是稳定的：

A) 插⼊排序B) 基数排序C) 归并排序D) 冒泡排序

10、在参加NOI系列竞赛过程中，下⾯哪些⾏为是被严格禁⽌的：A)携带书写⼯具，⼿表和不具有通讯功能的电⼦词典进⼊赛场。

B)在联机测试过⼿⼯计算出可能的答案并在程序⾥直接输出答案来获取分数。C)通过互联⽹搜索取得解题思路。

D)在提交的程序中启动多个进程以提⾼程序的执⾏效率。三．问题求解（共2题，每空5分，共计10分）

2．某个国家的钱币⾯值有1, 7, 72, 73共计四种，如果要⽤现⾦付清10015元的货物，假设买卖双⽅各种钱币的数量⽆限且允许找零，那么交易过程中⾄少需要流通钱币。四．阅读程序写结果（共4题，每题8分，共计32分）1. program t1;vara:real;

i,j,t,n,ans:longint;beginreadln(n);for i:=1 to n dobeginreadln(a,t);

for j:=1 to t do ans:=ans xor trunc(a*j);end;writeln(ans);end.读⼊：31.6 32.6 11.0 2

输出：________________2. program t2;

var a:array[0..9] of longint;n,i,j,x:longint;begina[0]:=1;

for i:=1 to 9 doa[i]:=a[i-1]*i;read(x);while x>=0 dobegin

if x=0 then write('N',’’) elsebegin

for i:=9 downto 0 doif a[i]<=x then x:=x-a[i];

if x=0 then write('Y',’’) else write('N',’’);end;read(x);end;end.

读⼊：10 30 729 5048 -1输出：___________3. program t3;const n=200;var si,pr:set of 2..n;x,j,m:integer;beginreadln(m);si:=[2..m];pr:=[];x:=2;repeat

while not(x in si) do x:=succ(x);pr:=pr+[x];j:=x;

while j <= m do

begin si:=si-[j];j:=j+x; end;until si=[ ];j:=0;

for x:=m downto 2 doif x in pr thenbegin

write(x:5);inc(j);

if j mod 10=0 then writeln;end;writeln;end.

输⼊：50 输出：4.program t4;

var a:array[1..9,1..9] of string;st,x:string;i,j,n,m:integer;beginrepeat

writeln('please input a string(length<10):');readln(st);n:=length(st);

until (n < 10) and odd(n);m:=(n+1) div 2;for i:=1 to n dofor j:=1 to n do a[i,j]:=' ';for i:=1 to m dofor j:=i to n+1-i dobeginx:=copy(st,j,1);a[i,j]:=x;a[n+1-i,n+1-j]:=xend;

for j:=n downto 1 dobegin

for i:=1 to n do write(a[i,j]:2);writeln;end;end.

输⼊：ABCDEFG 输出：

五．完善程序 (前5空，每空2分，后6空，每空3分，共28分)1．循环⼩数

题⽬描述：给出⼀个分数的分⼦和分母，要将其转换为⼩数的形式。输⼊：只有两个整数，分别表⽰分数的分⼦和分母。

输出：只有⼀个⼗进制⼩数，表⽰这个分数转换成的⼩数。如果得到的⼩数不是循环⼩数，则输出其全部数字。否则在输出完毕第⼀个循环节后不再输出。var

s,t:array[0..99]of longint;a,b,g,i,j,d:longint;

function (a:longint;b:longint):longint;begin

if b=0 then :=a

else :=①————————;end;

procedure work(a:longint;b:longint);begini:=0;d:=1;while true dobegin

if a=0 then break;a:=a*10;t[i]:=a;s[i]:=a div b;a:=a mod b;for j:=0 to i-1 do

if (s[j]=s[i])and(t[j]=t[i]) thenbegindec(d);

②————————;end;

if d=0 then break;write(s[i]);

③————————;end;end;beginread(a,b);

if (a>b) then g:=(a,b)else ④————————;a:=a div g;b:=b div g;

⑤————————;a:=a mod b;work(a,b);end.

2. 题⽬描述：在⼀个果园⾥，多多已经将所有的果⼦打了下来，⽽且按果⼦的不同种类分成了不同的堆。多多决定把所有的果⼦合成⼀堆。

每⼀次合并，多多可以把两堆果⼦合并到⼀起，消耗的体⼒等于两堆果⼦的重量之和。可以看出，所有的果⼦经过n-1次合并之后，就只剩下⼀堆了。多多在合并果⼦时总共消耗的体⼒等于每次合并所耗体⼒之和。

因为还要花⼤⼒⽓把这些果⼦搬回家，所以多多在合并果⼦时要尽可能地节省体⼒。假定每个果⼦重量都为1，并且已知果⼦的种类数和每种果⼦的数⽬，你的任务是设计出合并的次序⽅案，使多多耗费的体⼒最少，并输出这个最⼩的体⼒耗费值。例如有3种果⼦，数⽬依次为1，2，9。可以先将1、2堆合并，新堆数⽬为3，耗费体⼒为3。接着，将新堆与原先的第三堆合并，⼜得到新的堆，数⽬为12，耗费体⼒为12。所以多多总共耗费体⼒=3+12=15。可以证明15为最⼩的体⼒耗费值。输⼊：输⼊包括两⾏，第⼀⾏是⼀个整数n(1<＝n<=10000)，表⽰果⼦的种类数。第⼆⾏包含n个整数，⽤空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果⼦的数⽬。

输出：输出包括⼀⾏，这⼀⾏只包含⼀个整数，也就是最⼩的体⼒耗费值。输⼊数据保证这个值⼩于2^31。program fill2;var

s1,s2:array[0..15000] of longint;s1low,s1hi,s2low,s2hi:integer;r,l,s,x,i,min1,min2:longint;function peeksmall:longint;begin

min1:=1000000000;min2:=1000000000;if s1low<>s1hi then min1:=s1[s1low];if s2low<>s2hi then min2:=s2[s2low];

if ①————————then begin peeksmall:=s1[s1low];inc(s1low); end else begin peeksmall:=s2[s2low];inc(s2low); end;end;

procedure swap(l:integer;r:integer);var tmp:longint;begin

tmp:=s1[r]; s1[r]:=s1[l]; s1[l]:=tmp;end;

procedure sort(low:integer; hi:integer);

var l:longint;begin

if low>=hi then ②————————elsex:=s1[(low+hi)div 2];swap(low,③——————);l:=low; r:=hi;while lbegin

while ((l=x)) do dec(r);s1[l]:=s1[r];while ((ls1[r]:=s1[l];end;

④————————;sort(low,l-1);sort(r+1,hi);end;beginread(s1hi);for i:=0 to s1hi-1 doread(s1[i]);sort(0,⑤————);s:=0;

for i:=s1hi-1 downto 1 dobegin

s2[s2hi]:=peeksmall+⑥;s:=s+s2[s2hi];inc(s2hi);end;write(s);end.