nbhkdz.com冰点文库

NOIP2010信息学奥赛初赛提高组模拟试题(一)


NOIP2010 初赛提高组模拟试题(一)
( 提高
●●

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+*dC) 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 一 二 三 四 五 7 4 5 6 4 B 5 3 8 7 3 C 8 5 6 3 6 D 6 4 7 4 5 E 4 6 3 5 3

第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 l<r do begin while ((l<r)and(s1[r]>=x)) do dec(r); s1[l]:=s1[r]; while ((l<r)and(s1[l]<=x)) do inc(l); s1[r]:=s1[l]; end; ④; 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页


NOIP2010信息学奥赛初赛提高组模拟试题(一)

NOIP2010信息学奥赛初赛提高组模拟试题(一)NOIP2010信息学奥赛初赛提高组模拟试题(一)隐藏>> NOIP2010 初赛提高组模拟试题(一)( 提高●● Pascal 语言 二小时完成...

2010信息学奥赛初赛试题及答案

2010信息学奥赛初赛试题及答案_学科竞赛_小学教育_教育专区。NOIP2010(Pascal 提高组) 一、单项选择题 1.与 16 进制数 A1.2 等值的 10 进制数是 ()A.101....

CCF NOIP2010全国青少年信息学奥林匹克联赛初赛试题

CCF NOIP2010全国青少年信息学奥林匹克联赛初赛试题_...NOIP2010(Pascal 提高组) 一、单项选择题 1.与 ...10.以下竞赛活动中历史最悠久的是( A. NOIP IOI ...

NOIP2010提高组初赛试题_C++含答案

A.全国青少年信息学奥林匹克联赛(NOIP) B.全国青少年信息学奥林匹克竞赛(NOI) C.国际信息学奥林匹克竞赛(IOI) NOIP2010 初赛 提高组 C++ 1 D.亚太地区信息学...

noip2010提高组PASCAL初赛试题和答案

第十六届全国青少年信息学奥林匹克联赛初赛试题 试题及答案 NOIP2010(Pascal 提高组) ( 提高组) 一、单项选择题 1.与 16 进制数 A1.2 等值的 10 进制数是 ...

信息学奥赛普及组初赛模拟试题

信息学奥赛普及组初赛模拟试题(一) 发布: 郭琪 时间: 2011/7/6 13:56:18 ...NOIP2010信息学奥赛初赛... 8页 1下载券 NOIP2010信息学奥赛初赛... 8页 ...

Noip2010提高组初赛试题及答案(C语言)

Noip2010提高组初赛试题及答案(C语言)_初一数学_数学_初中教育_教育专区。第十六届信息技术奥赛试题及答案 第十六届全国青少年信息学奥林匹克联赛初赛试题( 提高组 ...

Noip2010提高组初赛试题及详细解析(C语言)

Noip2010提高组初赛试题及详细解析(C语言)_建筑/土木_工程科技_专业资料。第十六...一下竞赛活动中历史最悠久的是( ) A.全国青少年信息学奥林匹克联赛(NOIP) B....

2012年信息学奥赛提高组初赛试题PASCAL(附答案_完整)

2012年信息学奥赛提高组初赛试题PASCAL(附答案_完整)_学科竞赛_高中教育_教育专区。第十八届全国青少年信息学奥林匹克联赛初赛(提高组 Pascal 语言试题) 竞赛时间:...

1999年—2011年信息学奥赛提高组初赛试题PASCAL(附答案_完整)1

1999年—2011年信息学奥赛提高组初赛试题PASCAL(附...107 CCF NOIP 提高组(Pascal)参考答案与评分标准 ....今年(2010 年)发生的事件有( )。 A.惠普实验室...