当前位置:首页 >> 学科竞赛 >> NOIP2012提高组初赛及答案(Pascal)

NOIP2012提高组初赛及答案(Pascal)


第十八届全国青少年信息学奥林匹克联赛初赛
(提高组 Pascal 语言试题) 竞赛时间:2012 年 10 月 13 日 14:30~16:30 选手注意: ? 试题纸共有 10 页,答题纸共有 2 页,满分 100 分。请在答题纸上作答,写在试题纸上一律无效。 ? 不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料 一、单项选择题(共 10 题,每题

1.5 分,共计 15 分;每题有且仅有一个正确选项) 1.目前计算机芯片(集成电路)制造的主要原料是( ) ,它是一种可以在沙子中提炼出的物质。 A.硅 B.铜 C.锗 D.铝 2. ( )是主要用于显示网页服务器或者文件系统的 HTML 文件的内容,并让用户与这些文件交互 的一种软件。 A.资源管理器 B.浏览器 C.电子邮件 D.编译器 3.目前个人电脑的( )市场占有率最靠前的厂商包括 Intel、AMD 等公司。 A.显示器 B.CPU C.内存 D.鼠标 4. 无论是 TCP/IP 模型还是 OSI 模型, 都可以视为网络的分层模型, 每个网络协议都会被归入某一层中。 如果用现实生活中的例子来比喻这些“层” ,以下最恰当的是( ) 。 A. 中国公司的经理与波兰公司的经理交互商业文件

B. 军队发布命令

C. 国际会议中,每个人都与他国地位对等的人直接进行会谈

D. 体育比赛中,每一级比赛的优胜者晋级上一级比赛

5.如里不在快速排序中引入随机化,有可能导致的后果是( ) 。 A.数组访问越界 B.陷入死循环 C.排序结果错误 D.排序时间退化为平方级 6.1946 年诞生于美国宾夕法尼亚大学的 ENIAC 属于( A.电子管 B.晶体管 C.集成电路 )计算机。 D.超大规模集成电路

7.在程序运行过程中,如果递归调用的层数过多,会因为( )引发错误。 A.系统分配的栈空间溢出 B.系统分配的堆空间溢出 C.系统分配的队列空间溢出 D.系统分配的链表空间溢出

8.地址总线的位数决定了 CPU 可直接寻址的内存空间大小,例如地址总线为 16 位,其最大的可寻址 空间为 64KB。如果地址总线是 32 位,则理论上最大可寻址的内存空间为( ) 。 A.128KB B.1MB C.1GB D.4GB 9.以下不属于 3G(第三代移动通信技术)标准的是( ) 。 A.GSM B.TD-SCDMA C.CDMA2000

D.WCDMA

10.仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理,并将这 些原理移植于新兴的工程技术中。以下关于仿生学的叙述,错误的是( ) A.由研究蝙蝠,发明雷达 B.由研究蜘蛛网,发明因特网 C.由研究海豚,发明声纳 D.由研究电鱼,发明伏特电池 二、不定项选择题(共 10 题,每题 1.5 分,共计 15 分;每题有一个或多个正确选项,多选或少选均不 得分) 1.如果对于所有规模为 n 的输入,一个算法均恰好进行( )次运算,我们可以说该算法的时间复

杂度为 O (2 ) 。 A. 2 n ?1 B. 3 n C. n * 2 n D. 2 2 n

n

2. 从顶点 A0 出发,对有向图(
A0 , A1 , A2 , A3 , A4 。

)进行广度优先搜索(BFS)时,一种可能的遍历顺序是

3.如果一个栈初始时为空,且当前栈中的元素从栈顶到栈底依次为 a,b,c(如右图所示) ,另有元素 d 已经出栈,则可能的入栈顺序是( ) 。 A.a, b, c, d C.a, c, b, d B.b, a, c, d D.d, a, b, c

4.在计算机显示器所使用的 RGB 颜色模型中, ( )属于三原色之一。 A.黄色 B.蓝色 C.10 D.15 5.一棵二叉树一共有 19 个节点,其叶子节点可能有( A.1 B.9 C.紫色 )个。 D.绿色

6.已知带权有向图 G 上的所有权值均为正整数,记顶点 u 到顶点 v 的最短路径的权值为 d ( u , v ) 。若
v1 , v 2 , v 3 , v 4 , v 5 是图 G 上的顶点,且它们之间两两都存路径可达,则以下说法正确的有(

) 。

A. v 1 到 v 2 的最短路径可能包含一个环 B. d ( v1 , v 2 ) ? d ( v 2 , v1 ) C. d ( v1 , v 3 ) ? d ( v1 , v 2 ) ? d ( v 2 , v 3 ) D.如果 v1 ? v 2 ? v 3 ? v 4 ? v 5 是 v 1 到 v 5 的一条最短路径,那么 v 2 ? v 3 ? v 4 是 v 2 到 v 4 的一 条最短路径

7.逻辑异或( ? )是一种二元运算,其真值表如下所示。 a False False True True b False True False True ) 。
a?b

False True True Flase

以下关于逻辑异或的性质,正确的有( A.交换律: a ? b ? b ? a B.结合律: ( a ? b ) ? c ? a ? ( b ? c )

C.关于逻辑与的分配律: a ? ( b ? c ) ? ( a ? b ) ? ( a ? c ) D.关于逻辑或的分配律: a ? ( b ? c ) ? ( a ? b ) ? ( a ? c ) 8.十进制下的无限循环小数(不包括循环节内的数字均为 0 成均为 9 的平凡情况) ,在二进制下有可能 是( ) 。 A.无限循环小数(不包括循环节内的数字均为 0 或均为 9 的平凡情) B.无限不循环小数 C.有限小数 D.整数 9. ( )是目前互联网上常用的 E-mail 服务协议。 A.HTTP B.FTP C.POP3

D.SMTP

10.以下关于计算复杂度的说法中,正确的有( ) 。 A.如果一个问题不存在多项式时间的算法,那它一定是 NP 类问题 B.如果一个问题不存在多项式时间的算法,那它一定不是 P 类问题 C.如果一个问题不存在多项式空间的算法,那它一定是 NP 类问题 D.如果一个问题不存在多项式空间的算法,那它一定不是 P 类问题 三、问题求解(共 2 题,每题 5 分,共计 10 分) 1. 本题中,我们约定布尔表达式只能包含 p,q,r 三个布尔变量,以及“与” (∧)“或” 、 (∨)“非” 、 (¬)三种布尔运算。如果无论 p,q,r 如何取值,两个布尔表达式的值总是相同,则称它们等价。例 如(p∨q)∨r 和 p∨(q∨r)等价,p∨¬p 和 q∨¬q 也等价;而 p∨q 和 p∧q 不等价。那么两两不等价的布 尔表达式最多有 个。

2. 对于一棵二叉树,独立集是指两两互不相邻的节点构成的集合。例如,图 1 有 5 个不同的独立集(1 个双点集合,3 个单点集合、1 个空集) ,图 2 有 14 个不同的独立集。那么图 3 有 个不同的独 立集。

三、阅读程序写结果。(共 4 题,每题 8 分,共计 32 分) 1. var n,i,temp,sum:integer; a :array[1..100] of integer; begin readln(n); for i:=1 to n do read(a[i]); for i:=1 to n-1 do if a[i]>a[i+1] then begin temp := a[i]; a[i] := a[i+1]; a[i+1] := temp; end; for i:=n downto 2 do if a[i]<a[i-1] then begin temp := a[i]; a[i] := a[i-1]; a[i-1] := temp; end; sum := 0; for i:=2 to n-1 do inc(sum,a[i]); writeln(sum div (n-2)); end. 输入: 8 40 70 50 70 20 40 10 30

输出:______________ 2. var n,i,ans:integer; function gcd(a,b :integer) : integer; begin if a mod b=0 then gcd :=0; else gcd := gcd(b,a mod b); end; begin readln(n); ans := 0; for i:=1 to n do if gcd(n,i)=i then ans := ans + 1; writeln(ans); end. 输入:120 输出:_____________ 3. var data : array[1..20] of integer; n,i,h,ans : integer;

procedure merge; begin data[h-1] := data[h-1] + data[h]; dec(h); inc(ans); end; begin readln(n); h := 1; data[h] := 1;

ans := 0; for i:=2 to n do begin inc(h); data[h] := 1; while (h>1) and (data[h]=data[h-1]) do merge; end; writeln(ans); end. (1) 输入:8 输出:______________ (4 分) (2) 输入:2012 输出:______________ (4 分) 4. var left, right, father sl, s2, s3 :string; n,ana begin if left[x]>0 then check(left[x)); s3 := s3 + sl[x]; if right[x]>0 then check(right[x]); end; procedure calc(x,dep begin ans:= ans + dep*(ord(sl[x])-ord('A')+1); if left[x] > 0 then calc(left[x],dep+l); if right[x]> 0 then calc(right[x),dep+l); end; procedure dfs(x,th :integer); begin if th = n+1 then :integer); :integer; :integer); procedure check(x :array[1..20] of integer;

begin s3 :=''; check(1); if s2=s3 then begin ans := 0; calc(1,1); writeln(ans); end; exit; end; if (left[x]=0) and (right[x]=0) then begin left[x) := th; father[th] := x; dfs(th, th+1); father[th] := 0; left[x] := 0; end; if right[x] = 0 then begin right[x] := th; father[th] := X; dfs(th, th+1); father[th] := 0; right[x] := 0; end; if (father[x] > 0) then dfs(father[x],th); end; begin readln(s1); readln(s2); n := length(s1); fillchar(left,sizeof(left),0); fillchar(right,sizeof(right),0); fillcahr(father,sizeof(father),0); dfs(1,2); end.

输入: ABCDEF BCAEDF 输出:____________ 五、完善程序(第 1 题第 2 空 3 分,其余每空 2.5 分,共计 28 分) 1.(排列数)输入两个正整数 n , m (1 ? n ? 20,1 ? m ? n ) ,在 1 ? n 中任取 m 个数,按字典序从小到 大输出所有这样的排列。例如 输入:3 2 输出:1 2 1 3 2 1 2 3 3 1 3 2

const SIZE=20; var used data flag begin readln(n,m); fillchar(used,sizeof(used),false); for i:=1 to m do begin data[i] := i; used[i] := true; end; flag := true; while flag do begin for i:=1 to m-1 do write(data[i],' '); :array [1..SIZE] of boolean; :array [1..SIZE] of integer; :integer; :boolean;

n,m,i,j,k

writeln(data[m]); flag := begin ② begin used[j] := true; data[i] := ③ flag := true; break; end; if flag then begin for k:= i+l to m do for j:= 1 to begin data[k] := j; used[j] := true; break; end; ⑤ end; end; end; end. 2.(新壳栈)小 Z 设计了一种新的数据结构“新壳栈”。首先,它和传统的栈一样支持压入、弹出操作。 此外,其栈顶的前 c 个元素是它的壳,支持翻转操作。其中,c>2 是一个固定的正整数,表示壳的厚度。 小 Z 还希望,每次操作,无论是压入、弹出还是翻转,都仅用与 c 无关的常数时间完成。聪明的你能帮 助她编程实现“新壳栈”吗? 程序期望的实现效果如以下两表所示。其中,输入的第一行是正整数 c,之后每行输入都是一条指 令。另外,如遇弹出操作时栈为空,或翻转操作时栈中元素不足 c 个,应当输出相应的错误信息。 指令 1[空格]e 2 3 0 涵义 在栈顶压入元素 e 弹出(并输出)栈顶元素 翻转栈顶的前 c 个元素 退出 表 1:指令的涵义 ; ④ do if used[j]=false then ; ; for j := data[i]+1 to n do if used[j] = false then ① ; for i := m downto 1 do

输入 3 1 1 1 2 1 3 1 4 3 1 5 3 2 2 2 3 2 2 2 0

输出

栈中的元素 (左为栈底,右为栈顶) 1 1 2 1 2 3 1 2 3 4 1 4 3 2 1 4 3 2 5 1 4 5 2 3

说明 输入正整数 c 压入元素 1 压入元素 2 压入元素 3 压入元素 4 翻转栈顶的前 c 个元素 压入元素 5 翻转栈顶的前 c 个元素 弹出栈顶元素 3 弹出栈顶元素 2 弹出栈顶元素 5 由于栈中元素不足 c 个,无法翻转,故操 作失败,输出错误信息 弹出栈顶元素 4 弹出栈顶元素 1 由于栈中元素不足 c 个,无法翻转,故操 作失败,输出错误信息 退出

3 2 5 错误信息 4 1 错误信息

1 4 5 2 1 4 5 1 4 1 4 1 空 空 空

表 2:输入输出样例 const NSIZE = 100000; CSIZE = 1000; var n,c,r,tail,head :longint; s : array[1..NSIZE] of longint; //数组 s 模拟一个栈,n 为栈的元素个数 q :array[1..CSIZE] of longint; //数组 q 模拟一个循环队列,tail 为队尾的下标,head 为队头的下标 direction,empty :boolean; function previous(k :longint) :longint; begin if direction then previous := ((k+c-2) mod c) + 1; else previous := (k mod c) + 1; end; function next(k :longint) :longint;

begin if direction then ① else next := ((k+c-2) mod c)+1; end; procedure push; var element :longint; begin read(element); if next(head) = tail then begin inc(n); ② ; tail := next(tail); end; if empty then empty := false else head := next(head); ③ := element; end; procedure pop; begin if empty then begin writeln('Error: the stack is empty!'); exit; end: writeln( ④ ); if tail = head then empty := true else begin head := previous(head); if n > 0 then begin tail := previous(tail); ⑤ := s[n]; dec(n); end; end; end;

procedure reverse; var temp :longint; begin if ⑥ = tail then begin direction := not direction; temp := head; head := tail; tail := temp; end else writeln('Error:less than',c,' elements in the stack!'); end; begin readln(c); n := 0; tail := 1; head := 1; empty := true; direction := true; repeat read(r); case r of 1 : push; 2 : pop; 3 : reverse; end; until r = 0; end.


更多相关文档:

NOIP2012提高组初赛及答案(Pascal)

NOIP2012提高组初赛及答案(Pascal)_学科竞赛_高中教育_教育专区。用了两天的时间,终于将提高组初赛的WORD文档处理好,希望对大家有帮助!...

NOIP2012 提高组初赛答案

NOIP2012 提高组初赛答案_学科竞赛_高中教育_教育专区。NOIP2012 提高组初赛答案 文档贡献者 谁推我向前 贡献于2012-10-14 1/2 相关文档推荐 ...

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

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

NOIP2013初赛提高组Pascal试题及答案

NOIP2013初赛提高组Pascal试题及答案_其它课程_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛提高组 Pascal 语言试题 竞赛时间:2013 年 10 月 13 ...

NOIP2012普及组初赛及答案(Pascal)

NOIP2012普及组初赛及答案(Pascal)_学科竞赛_初中教育_教育专区。更新第10题答案...NOIP2012提高组初赛及答... 14页 2下载券 08年普及组Pascal答案 1页 免费喜欢...

NOIP2012信息学奥林区克竞赛初赛提高组试题及参考答案(PASCAL)

NOIP2012信息学奥林区克竞赛初赛提高组试题及参考答案(PASCAL)_学科竞赛_高中教育_教育专区。+申请认证 文档贡献者 陈嘉庆 教师 15 8992 4.2 文档数 浏览总量 总...

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

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

noip2013普及组初赛试题及答案(pascal)

noip2013普及组初赛试题及答案(pascal)_财会/金融考试_资格考试/认证_教育专区。...NOIP2013初赛提高组Pasc... 暂无评价 12页 免费喜欢此文档的还喜欢 ...

2012十八届noip提高组题目及答案

2012十八届noip提高组题目及答案_学科竞赛_高中教育_教育专区。为了打印各种调的~~~第十八届全国青少年信息学奥林匹克联赛初赛(提高组 Pascal 语言试题) 一、单项选...
更多相关标签:
noip提高组初赛pascal | noip2012提高组初赛 | 2012年noip提高组初赛 | 2012noip提高组初赛c | noip2016初赛pascal | noip普及组初赛pascal | noip2015提高组初赛 | noip2016提高组初赛 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com