初赛模拟试题(一)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. 始终为falseC. 当且仅当c为true时为falseD. 当且仅当a与b均为true时为trueE. 依赖于a、b、c三者的值3、设a、b为两个浮点(float)型变量，下面的表达式中最有可能为真的是（）。

A. a=bB. 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) -+*abcd7、最优前缀编码，也称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. BT10、一个音乐爱好者收藏有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)82、设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、55、下面的软件必须在联网状态下才能正常使用的有（）。

A. BitTorrentB. Mozilla FirefoxC. Red Hat LinuxD. MSN MessengerE. WinZip6、若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) 109、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：A) 插入排序 B) 基数排序 C) 归并排序 D) 冒泡排序10、在参加NOI系列竞赛过程中，下面哪些行为是被严格禁止的：A)携带书写工具，手表和不具有通讯功能的电子词典进入赛场。

B)在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。

C)通过互联网搜索取得解题思路。

D)在提交的程序中启动多个进程以提高程序的执行效率。

三．问题求解（共2题，每空5分，共计10分）1．有五个工人A、B、C、D、E需要做工作一、二、三、四、五，下表显示了每个人做每项工作所要花费的最短时间。

则完成所有5项工作所需要的最短时间是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 dobeginif x=0 then write('N',’’) elsebeginfor 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;repeatwhile not(x in si) do x:=succ(x);pr:=pr+[x];j:=x;while j <= m dobegin si:=si-[j];j:=j+x; end;until si=[ ];j:=0;for x:=m downto 2 doif x in pr thenbeginwrite(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;beginrepeatwriteln('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 dobeginfor i:=1 to n do write(a[i,j]:2);writeln;end;end.输入：ABCDEFG 输出：五．完善程序 (前5空，每空2分，后6空，每空3分，共28分)1．循环小数题目描述：给出一个分数的分子和分母，要将其转换为小数的形式。

输入：只有两个整数，分别表示分数的分子和分母。

输出：只有一个十进制小数，表示这个分数转换成的小数。

如果得到的小数不是循环小数，则输出其全部数字。

否则在输出完毕第一个循环节后不再输出。

vars,t:array[0..99]of longint;a,b,g,i,j,d:longint;function gcd(a:longint;b:longint):longint;beginif b=0 then gcd:=aelse gcd:=①————————;end;procedure work(a:longint;b:longint);begini:=0;d:=1;while true dobeginif 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 doif (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:=gcd(a,b)else ④————————;a:=a div g;b:=b div g;⑤————————;a:=a mod b;work(a,b);end.2. 题目描述：在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。