当前位置:首页 >> 学科竞赛 >>

NOIP2016提高组Pascal试题


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


一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分;每题有且仅有一个正确 选项)
1. 以下哪一种编程语言是最早的面向对象程序设计语言( ) 。 B. Smalltalk C. Visual Basic D. Fortran

A. Java

2.

人工智能之父图灵在二战中所研发的计算机( )成功破译了德军的密码。 B.巨人计算机 C.ENIAC D.ABC 计算机

A.Enigma

3.

128KB 的存储器用十六进制表示,它的最大的地址码是( ) B. EFFF C. 1FFFF D. FFFFF

A. 10000

4.

下列说法不正确的是( ) 。 A. B. C. D. 在逻辑电路中,与门可以用或门和非门的组合来代替 在逻辑电路中,或门可以用与门和非门的组合来代替 在逻辑电路中,亦或门可以用与门和非门的组合来代替 以上选项有一个是错的

5.

以下十进制小数的二进制表述不是无限循环小数的是( ) 。
CCF NOIP2016 初赛提高组 Pascal 语言试题 第 1 页,共 12 页

A. 0.123 6.

B. 0.124

C. 0.125

D. 0.126

在半导体中经常会使用单向导电的 PN 结,其中 P 型半导体的载流子为( ) 。 B. 正电子 C. 负离子 D. 空穴

A. 电子

7.

计算机病毒传染的必要条件是(

)。 B. 删除文件 D. 复制文件 )。

A. 与万维网联通 C. 对磁盘进行读写操作 计算机网络可分为三类,它们是(

8.

A. Internet、Intranet、Extranet B. 广播式网络、移动网络、点-点式网络 C. X.25、MAN、WAN D. LAN、MAN、WAN 近期一款新游戏“精灵宝可梦”让玩家可以实现在生活中捕捉精灵,其实现主要运用 B.增强现实 D.影像现实 )的核心资

9.

了()技术。 A.虚拟现实 C.混合现实

10. 2016 年 7 月 25 日,美国电信巨头 Verizon(威瑞森)以 48 亿美元收购( 产。 A.Google B.yahoo! C.facebook D.IBM

11. 在保证树的节点数足够大且数据互不相同的条件下,若这棵树满足( 可能符合堆的定义。 A. 完全二叉树 B. 满二叉树 C.二叉排序树 D.红黑树

)的定义,就不

12. 在存在负权边的情况下,以下( A. Dijkstra C. Bellman-Ford

)最短路算法仍然能够正常执行? B. Floyd D.以上三个都不能

CCF NOIP2016 初赛提高组 Pascal 语言试题 第 2 页,共 12 页

13. 设某算法的计算时间表示为递推关系式 T(n) = T(n/2) + n(n 为正整数)及 T(0) = 1,则 该算法的时间复杂度为( ) 。 A.O(log n) B. O(n log n) C. O(n) D. O(n2)

14. 在图论的诸多算法中,Dijkstra 算法是一种采用了( )思想的算法。 A.贪心 B. 分治 C. 动态规划 D. 回溯

15. 在 NOI 系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中允许选手 自带的是( ) 。 A. 草稿纸 B. 笔 C. 计算机 D.键盘

二、不定项选择题(共 5 题,每题 1.5 分,共计 7.5 分;每题有一个或多个正确 选项,多选或少选均不得分)
1. 以下不属于多用户操作系统的有( ) 。 A. Windows XP B. DOS C. Linux D. Mac OS

2. 下列属于图片文件格式的有( ) 。 A. GIF B. PSD C. TIFF D. JPEG

3. 关于 windows 系统中的窗口和对话框的说法正确的是( A. 对话框能移动和改变大小 B. 窗口能移动和改变大小 C. 对话框只能移动和但不能改变大小 D. 对话框不能移动但能改变大小 下列关于十进制数 100 的正确说法是( ). B.反码为 9BH D.补码为 9BH

).

4.

A.反码为 64H C.补码为 64H

CCF NOIP2016 初赛提高组 Pascal 语言试题 第 3 页,共 12 页

5.

下面关于算法的正确的说法是( )

A. 算法必须有输出 B. 算法必须在计算机上用某种语言实现 C. 算法不一定有输入 D. 算法必须在有限步执行后能结束

三、问题求解(共 2 题,每题 5 分,共计 10 分;每题全部答对得 5 分,没有部 分分)
1. 盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。按售票处的规定, 每位购票者限购一张门票,每张票售价 50 元。在排成长龙的球迷中有 5 个人手持面额 50 元的钱币,另有 5 个人手持 100 元面额的钱币。现在售票处初始状态下没有零钱, 那么,这 10 个人一共有___________种排队方式,可使得售票处不出现找不出钱的尴尬 局面。

2.

对于一个 n 阶完全图,对每一条边染上红色或蓝色两种颜色之一。若对于任意一种染 色方法,都在这个双染色的 n 阶完全图中,存在一个子图,使得该子图为四阶完全图, 且满足其 6 条边颜色均一样,则最小的 n 为___________。

四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分)
1.
var a,b:longint; begin readln(a,b); writeln(a mod b); end.

输入:-62 -4 输出:_________

CCF NOIP2016 初赛提高组 Pascal 语言试题 第 4 页,共 12 页

2.

function gcd(a,b:longint; var x,y:longint):longint; var t:longint; begin if b=0 then begin x:=1; y:=0; exit(a); end; gcd:=gcd(b,a mod b,y,x); y:=y-(a div b)*x; end; var a,b,x,y:longint; begin readln(a,b); gcd(a,b,x,y); writeln(a*x+y*b); end.

输入:198 156 输出:_________ var n,i,x,sum:longint; begin readln(n);sum:=0; for i:=1 to n do begin x:=i; while x mod 2=0 do begin x:=x >> 1; inc(sum); end; end; writeln(sum); end. 输入:2147483647 输出:___________
CCF NOIP2016 初赛提高组 Pascal 语言试题 第 5 页,共 12 页

3.

4.

const maxn=20; type nettype=record c,f:integer; end; nodetype=record l,p:integer; end; var lt:array[0..maxn] of nodetype; g:array[0..maxn,0..maxn] of nettype; n,s,t:integer; procedure init; var i,j:integer; begin readln(n); fillchar(g,sizeof(g),0); fillchar(lt,sizeof(lt),0); for i:=1 to n do for j:=1 to n do read(g[i,j].c); end; function find:integer; var i:integer; begin i:=1; while (i<=n) and not((lt[i].l<>0)and(lt[i].p=0)) do inc(i); if i>n then find:=0 else find:=i; end; function ford(var a:integer):boolean; var i,j,m,x:integer; begin ford:=true; fillchar(lt,sizeof(lt),0); lt[s].l:=s;
CCF NOIP2016 初赛提高组 Pascal 语言试题 第 6 页,共 12 页

repeat i:=find; if i=0 then exit; for j:=1 to n do if (lt[j].l= 0)and((g[i,j].c<>0)or(g[j,i].c<>0)) then begin if (g[i,j].f<g[i,j].c) then lt[j].l:=i; if (g[j,i].f>0) then lt[j].l:=-i; end; lt[i].p:=1; until (lt[t].l<>0); m:=t; a:=maxint; repeat j:=m; m:=abs(lt[j].l); if lt[j].l<0 then x:=g[j,m].f; if lt[j].l>0 then x:=g[m,j].c-g[m,j].f; if x<a then a:=x; until m=s; ford:=false; end; procedure change(a:integer); var m,j:integer; begin m:=t; repeat j:=m; m:=abs(lt[j].l); if lt[j].l<0 then g[j,m].f:=g[j,m].f-a; if lt[j].l>0 then g[m,j].f:=g[m,j].f+a; until m=s; end; procedure print; var i:integer; max:integer; begin
CCF NOIP2016 初赛提高组 Pascal 语言试题 第 7 页,共 12 页

max:=0; for i:=1 to n do if g[i,t].f<>0 then max:=max+g[i,t].f; writeln(max); end; procedure process; var del:integer; success:boolean; begin s:=1; t:=n; repeat success:=ford(del); if success then print() else change(del); until success; end; begin init(); process(); end. 输入: 5 05070 00100 00004 00200 00000 输出:_________

CCF NOIP2016 初赛提高组 Pascal 语言试题 第 8 页,共 12 页

五、完善程序(共 2 题,每题 14 分,共计 28 分)
1. 高精度算法(第 1 空 4 分,第 2、3 空每空 2 分,第 3、4 空每空 3 分) 在本题中,a,b,c 三个数组分别代表两个操作数和结果,其下标为 0 的记录均表示该数 的十进制长度。

下面是常量定义与类型定义: const maxn=100; wei=10; type arr=array[0..maxn]of longint; 下面是高精度加法: procedure jia(a,b:arr; var c:arr); var i,p:longint; begin if a[0]<b[0] then begin c:=a; a:=b; b:=c; end; fillchar(c,sizeof(c),0); for p:=1 to a[0] do begin i:=p; c[i]:=c[i]+a[p]+b[q]; c[i+1]:=c[i+1]+c[i] div wei; c[i]:=c[i] mod wei; end; if c[i+1]>0 do inc(i); c[0]:=i; end;

CCF NOIP2016 初赛提高组 Pascal 语言试题 第 9 页,共 12 页

下面是高精度乘法: procedure cheng(a,b:arr; var c:arr); var i,p,q:longint; begin fillchar(c,sizeof(c),0); for p:=1 to a[0] do for q:=1 to b[0] do begin i:= c[i]:= (1) (2) ; ;

c[i+1]:=c[i+1]+c[i] div wei; c[i]:=c[i] mod wei; end; while begin inc(i); c[i+1]:= c[i]:= end; c[0]:=i; end; (4) (5) ; ; (3) do

2. (放棋子问题)有一个 n 行 m 列的棋盘,棋盘的每一个格子都有黑白两种颜色中的一种, 黑色(用 1 表示)代表可以放棋子,白色(用 0 表示)则不可以放棋子,并且有边相 邻的两个格子不能同时都放上棋子,试编程求一共能有几种放棋子的方法。输出方法 数对 100000000 取模的结果。 (第 1、2、3、4 空每空 3 分,第 5 空 2 分)

样例输入: 23 111 010 样例输出: 9

CCF NOIP2016 初赛提高组 Pascal 语言试题 第 10 页,共 12 页

const model=100000000; var n,m,x,i,j,p,k,ans:longint; var st,map:array [0..10000] of longint; //分别存每一行的状态和格子的颜色 f:array [0..13,0..100000] of longint; //表示在第 i 行状态为 j 时候可以放棋子的种数 function judge1(x:longint):boolean; begin exit((x and (x<<1))>0); end; //判断二进制有没有相邻的 1 function judge2(i,x:longint):boolean; begin exit((map[i] and st[x])>0); end; begin fillchar(st,sizeof(st),0); fillchar(map,sizeof(map),0); fillchar(f,sizeof(f),0); readln(n,m); for i:=1 to n do begin for j:=1 to m do begin read(x); if x=0 then map[i]:=map[i]+(1<<(j-1)); end; readln(); end; k:=0; for i:=0 to 1<<m-1 do
CCF NOIP2016 初赛提高组 Pascal 语言试题 第 11 页,共 12 页

if

(1)

then

begin st[k]:=i; inc(k); end; for i:=0 to k-1 do if not(judge2(1,i)) then f[1,i]:= (2) ;

for i:=2 to n do for j:=0 to k-1 do begin if judge2(i,j) then continue; for p:=0 to k-1 do begin if (3) then continue;

//剪枝,判断上一行放棋子的方案是否合法 if not((st[j] and st[p])>0) then f[i,j]:= end; end; ans:=0; for i:=0 to k-1 do ans:= (5) ; (4) ;

writeln(ans); end.

CCF NOIP2016 初赛提高组 Pascal 语言试题 第 12 页,共 12 页


相关文章:
NOIP2016提高组初赛解析
NOIP2016提高组初赛解析_学科竞赛_高中教育_教育专区。一、单项选择题 1.这题...C++版试题完善程序第一题这么输出: 然而 Pascal 版这么输出: C++的那个 endl ...
NOIP2016提高组复赛试题(Day1+Day2)
NOIP2016提高组复赛试题(Day1+Day2)_IT/计算机_专业资料。NOIP2016提高组复赛...Pascal 语言 编译选项 对于 C++ 语言 对于 C 语言 对于 Pascal 语言 注意事项...
NOIP2015提高组复赛试题Day1
NOIP2015提高组复赛试题Day1_学科竞赛_高中教育_教育专区。NOIP2015提高组复赛...对于pascal语言 fpcmagic.pas message.cpp message.c message.pas landlords.cpp...
NOIP2015提高组Pascal试题及参考答案
NOIP2015提高组Pascal试题及参考答案_其它考试_资格考试/认证_教育专区。第二十...文档贡献者 ghzs 贡献于2016-10-06 1/2 相关文档推荐 NOIP2015普及组初赛...
第22届全国青少年信息学奥林匹克联赛NOIP2016提高组试题day1
第22届全国青少年信息学奥林匹克联赛NOIP2016提高组试题day1_学科竞赛_高中教育_...Pascal 语言 编译选项 对于 C++语言 对于语言 对于 Pascal 语言 注意事项: 1....
noip2015提高组复赛试题答案
noip2015提高组复赛试题答案_IT认证_资格考试/认证_...pascal 语言 magic.pas 三.编译命令(不包含任何优化...文档贡献者 66hhyyh 贡献于2016-09-14 ...
noip2015提高组复赛试题答案
noip2015提高组复赛试题答案_IT认证_资格考试/认证_...对于pascal语言 fpc magic.pas message.cpp message....©2016 Baidu 使用百度前必读 | 文库协议 | 广告...
NOIP 2016 提高组 复赛 Day1
NOIP 2016 提高组 复赛 Day1_学科竞赛_高中教育_...对于Pascal 语言 编译选项 对于C++ 对于C 语言 语言...NOIP2011提高组复赛试题... 6页 1下载券 NOIP...
NOIP2015提高组初赛PASCAL语言试题
NOIP2015提高组初赛PASCAL语言试题_财会/金融考试_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档NOIP2015提高组初赛PASCAL语言试题_财会/金融考试_资格...
更多相关标签:
2016noip提高组试题 | noip2016初赛pascal | noip提高组初赛pascal | noip2016提高组复赛 | noip2016提高组初赛 | noip2016初赛试题 | noip2016提高组 | noip2016复赛试题 |