初赛模拟试题(一)

（ 普及 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. 始终为true B. 始终为false C. 当且仅当c为true时为false D. 当且仅当a与b均为true时为true E. 依赖于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.0001 D. 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+1

6. 表达式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)

第1页 共8页

9、佳佳在网上购买了一个空间，建设了一个网站。那么，他向网站上上传网页时最有可能采用的网络协议是（ ）。

A. HTTP B. TCP C. POP3 D. FTP E. BT

10、一个音乐爱好者收藏有100首MP3格式的音乐，这些音乐的编码率都是192Kbps，平均每首音乐的时长为3min，他要通过网络将这些音乐传送给另一个人，假设网络速度恒定为512KB/s，则他传送这些音乐大概需要（ ）。

A. 72s B. 843s C. 112.5min D. 3h48min16s E. 超过24小时

二． 不定项选择题 （共10题，每题1.5分，共计15分。每题正确答案的个数不少于1。多选或少选均不得分）。

1、(7f)16 + (10010101)2 的运算结果等于（ ）。

A. (114)16 B. (276)10 C. (100010100)2 D. (11d)16 E. (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∧c D. (b∨a)∧(¬(a∨b)) E. 以上皆错

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

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

第2页 共8页

5、下面的软件必须在联网状态下才能正常使用的有（ ）。 A. BitTorrent B. Mozilla Firefox C. Red Hat Linux D. MSN Messenger E. WinZip

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

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

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

7、下面的硬件接口中既不可以连接声卡、又不可以连接鼠标的通讯设备或外设接口有（ ）。

A. PCI B. USB C. BlueTooth D. 红外 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分）

1．有五个工人A、B、C、D、E需要做工作一、二、三、四、五，下表显示了每个人做每项工作所要花费的最短时间。则完成所有5项工作所需要的最短时间是______________。（说明：不同的工作可以由不同的人同时做，但同一个工作只能由一个人来完成） A B 5 3 8 7 3 C 8 5 6 3 6 D 6 4 7 4 5 E 4 6 3 5 3 一 7 二 4 三 5 四 6 五 4

第3页 共8页

2．某个国家的钱币面值有1, 7, 72, 73共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通 张钱币。

四．阅读程序写结果（共4题，每题8分，共计32分） 1. program t1; var a:real;

i,j,t,n,ans:longint; begin readln(n); for i:=1 to n do begin readln(a,t);

for j:=1 to t do ans:=ans xor trunc(a*j); end; writeln(ans); end. 读入：3 1.6 3 2.6 1 1.0 2

输出：________________ 2. program t2;

var a:array[0..9] of longint; n,i,j,x:longint; begin a[0]:=1; for i:=1 to 9 do a[i]:=a[i-1]*i; read(x); while x>=0 do begin

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

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

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

第4页 共8页

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; begin

readln(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 do if x in pr then begin

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; begin repeat

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

until (n < 10) and odd(n); m:=(n+1) div 2;

第5页 共8页

for i:=1 to n do

for j:=1 to n do a[i,j]:=' '; for i:=1 to m do

for j:=i to n+1-i do begin

x:=copy(st,j,1); a[i,j]:=x;

a[n+1-i,n+1-j]:=x end;

for j:=n downto 1 do begin

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 gcd(a:longint;b:longint):longint; begin

if b=0 then gcd:=a

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

procedure work(a:longint;b:longint); begin i:=0; d:=1;

while true do begin

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

第6页 共8页

if (s[j]=s[i])and(t[j]=t[i]) then begin dec(d);

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

③————————; end; end; begin read(a,b);

if (a>b) then g:=gcd(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

第7页 共8页

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 ② ————————else x:=s1[(low+hi)div 2];

swap(low,③——————); l:=low; r:=hi; while lwhile ((l=x)) do dec(r); s1[l]:=s1[r];

while ((l④————————; sort(low,l-1); sort(r+1,hi); end; begin

read(s1hi);

for i:=0 to s1hi-1 do read(s1[i]);

sort(0,⑤————); s:=0;

for i:=s1hi-1 downto 1 do begin

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

第8页 共8页