nbhkdz.com冰点文库

NOIP2016年第二十二届全国青少年信息学奥林匹克联赛提高组初赛(pascal)

时间:2017-09-04


第二十二届全国青少年信息学奥林匹克联赛初赛
提高组 Pascal 语言试题 竞赛时间:2016 年 10 月 22 日 14:30~16:30 选手注意: ? 试题纸共有 13 页,答题纸共有 2 页,满分 100 分。请在答题纸上作答,写在试题纸 上的一律无效。 ? 不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。 一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分;每题有且仅有一个正确选项) 1. 以下不是微软公司出品的软件是( ) 。 A. Powerpoint C. Excel B. Word D. Acrobat Reader 2. 如果开始时计算机处于小写输入状态, 现在有一只小老鼠反复按照 CapsLock、 字母键 A、 字母键 S 和字母键 D 的顺序来回按键,即 CapsLock、A、S、D、S、A、CapsLock、A、S、 D、S、A、CapsLock、A、S、D、S、A、??,屏幕上输出的第 81 个字符是字母( ) 。 A. A B. S C. D D. a 3. 二进制数 00101100 和 01010101 异或的结果是( ) 。 A. 00101000 B. 01111001 C. 01000100 D. 00111000 4. 与二进制小数 0.1 相等的八进进制数是( ) 。 A. 0.8 B. 0.4 C. 0.2 D. 0.1 5. 以比较作为基本运算,在 N 个数中找最小数的最少运算次数为( ) 。 2 A. N B. N-1 C. N D. log N 6. 表达式 a*(b+c)-d 的后缀表达形式为( ) 。 A. abcd*+B. abc+*dC. abc*+dD. -+*abcd

7. 一棵二叉树如右图所示,若采用二叉树链表存储该二叉树(各个结 点包括结点的数据、左孩子指针、右孩子指针) 。如果没有左孩子或者 右孩子,则对应的为空指针。那么该链表中空指针的数目为( ) 。 A. 6 B. 7 C. 12 D. 14 8. G 是一个非连通简单无向图,共有 28 条边,则该图至少有( )个顶点。 A. 10 B. 9 C. 8 D. 7 9. 某计算机的 CPU 和内存之间的地址总线宽度是 32 位(bit) ,这台计算机最多可以使用 ( )的内存。 A. 2GB B. 4GB C. 8GB D. 16GB 10. 有以下程序: var k, n: longint; begin k := 4; n := 0; while n < k do begin inc(n); if n mod 3 <> 0 then continue; dec(k);

end; writeln(k, ',', n); end. 程序运行后的输出结果是( ) 。 A. 2,2 B. 2,3 C. 3,2 D. 3,3 )种放法。

11. 有 7 个一模一样的苹果,放到 3 个一样的盘子中,一共有( A. 7 B. 8 C. 21 D. 37

12. Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关 系图,两个人之间有边相连代表这两个 人是朋友,没有边相连代表不是朋友。 这个社交网站的规则是:如果某人 A 向 他(她)的朋友 B 分享了某张照片,那 么 B 就可以对该照片进行评论;如果 B 评论了该照片,那么他(她)的所有朋 友都可以看见这个评论以及被评论的照 片, 但是不能对该照片进行评论 (除非 A 也向他 (她) 分享了该照片) 。 现在 Lucia 已经上传了一张 照片,但是她不想让 Jacob 看见这张照片,那么她可以向以下朋友()分享该照片。 A. Dana, Michael, Eve B. Dana, Eve, Monica C. Michael, Eve, Jacob D. Micheal, Peter, Monica 13. 周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈 负责炒菜。 假设做每道菜的顺序都是: 先洗菜 10 分钟, 然后切菜 10 分钟, 最后炒菜 10 分 钟。那么做一道菜需要 30 分钟。注意:两道不同的菜的相同步骤不可以同时进行。例如第 一道菜和第二道的菜不能同时洗,也不能同时切。那么做完三道菜的最短时间需要( )分 钟。 A. 90 B. 60 C. 50 D. 40 14. 假设某算法的计算时间表示为递推关系式

则算法的时间复杂度为() 。 A. O() B. O( ) C. O( log ) D. O(2)

15. 给定含有 n 个不同的数的数组 L=<x1, x2, ..., xn>。如果 L 中存在 x( i 1 < i < n)使得 x1 < x2 < ... < xi-1 < xi > xi+1 > ... > xn, 则称 L 是单峰的, 并称 xi 是 L 的 “峰顶” 。 现在已知 L 是单峰的, 请把 a-c 三行代码补全到算法中使得算法正确找到 L 的峰顶。 a. Search(k+1, n) b. Search(1, k-1) c. return L[k] Search(1, n) 1. k←?n/2?

2. if L[k] > L[k-1] and L[k] > L[k+1] 3. then __________ 4. else if L[k] > L[k-1] and L[k] < L[k+1] 5. then __________ 6. else __________ 正确的填空顺序是() 。 A. c, a, b B. c, b, a C. a, b, c D. b, a, c

二、不定项选择题(共 5 题,每题 1.5 分,共计 7.5 分;每题有一个或多个正确选项,多 选或少选均不得分) 1. 以下属于无线通信技术的有( ) 。 A. 蓝牙 B. WiFi C. GPRS D. 以太网 2. 可以将单个计算机接入到计算机网络中的网络接入通讯设备有( ) 。 A. 网卡 B. 光驱 C. 鼠标 D. 显卡 3. 下列算法中运用分治思想的有( ) 。 A. 快速排序 B. 归并排序 C. 冒泡排序 D. 计数排序 4. 下图表示一个果园灌溉系统,有 A、B、C、 D 四个阀门,每个阀门可以打开或关上,所有 管道粗细相同,以下设置阀门的方法中,可以 让果树浇上水的有( ) 。 A. B 打开,其他都关上 C. A 打开,其他都关上 B. AB 都打开,CD 都关上 D. D 打开,其他都关上 5. 参加 NOI 比赛, 以下能带入考场的有 ( ) 。 A. 钢笔 B. 适量的衣服 C. U 盘 D. 铅笔 三、问题求解(共 2 题,每题 5 分,共计 10 分;每题全部答对得 5 分,没有部分分) 1. 一个 1×8 的方格图形(不可旋转)用黑、白两种颜色填涂每个方格。如果每个方格只 能填涂一种颜色,且不允许两个黑格相邻,共有_________种填涂方案。 2. 某中学在安排期末考试时发现,有 7 个学生要参加 7 门课程的考试,下表列出了哪些学 生参加哪些考试(用√表示要参加相应的考试) 。 最少要安排_________个不同的考试时间段才能避免冲突?

考试 通用技术 物理 化学 生物 历史 地理 政治

学生 1 √ √ √

学生 2 √ √

学生 3

学生 4

学生 5 √

学生 6

学生 7 √ √

√ √ √ √ √ √ √ √ √ √



四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. var

a: array[1..6] of longint = (1, 2, 3, 4, 5, 6); pi, pj, t, i: longint; begin pi := 1; pj := 6; while pi < pj do begin t := a[pi]; a[pi] := a[pj]; a[pj] := t; inc(pi); dec(pj); end; for i := 1 to 6 do write(a[i], ','); writeln; end. 输出:_________ 2. var n, i, j, k: longint; total_len: array[1..100] of longint; len: array[1..100, 1..3] of longint; a, b: array[1..100, 1..100] of char; c: array[1..100] of string[100]; begin i := 0; j := 0; k := 1; readln(n); for i := 1 to n do begin readln(c[i]); total_len[i]:=length(c[i]); end; for i := 1 to n do begin j := 1; while (c[i, j] <> ':') do begin a[i, k] := c[i, j]; k := k + 1; inc(j); end; len[i, 1] := k - 1; a[i, k] := chr(0);

k := 1; for j := j + 1 to total_len[i] do begin b[i, k] := c[i, j]; k := k + 1; end; len[i, 2]:=k-1; b[i, k]:=chr(0); k := 1; end; for i := 1 to n do begin if (len[i, 1] >= len[i, 2]) then write('NO,') else begin k := 1; for j := 1 to len[i, 2] do begin if a[i, k] = b[i, j] then k := k + 1; if k > len[i, 1] then break; end; if j = len[i, 2] then write('NO,') else write('YES,'); end; end; writeln; end. 输入:3 AB:ACDEbFBkBD AR:ACDBrT SARS:Severe Atypical Respiratory Syndrome 输出:_________ (注:输入各行前后均无空格) 3. function lps(seq: string; i, j: longint): longint; var len1, len2: longint; begin if i = j then

exit(1); if i > j then exit(0); if (seq[i] = seq[j]) then exit(lps(seq, i + 1, j - 1) + 2); len1 := lps(seq, i, j - 1); len2 := lps(seq, i + 1, j); if len1 > len2 then exit(len1) else exit(len2); end; var n: longint; seq: string; begin seq := 'acmerandacm'; n := length(seq); writeln(lps(seq, 1, n)); end. 输出:_________ 4. var map: array[1..100, 1..100] of longint; sum, weight, visit: array[1..100] of longint; n, i, x, y, ans, ansn: longint; procedure dfs(node: longint); var v, maxw: longint; begin visit[node] := 1; sum[node] := 1; maxw := 0; for v := 1 to n do begin if (map[node][v] = 0) or (visit[v] <> 0) then continue; dfs(v); inc(sum[node], sum[v]); if sum[v] > maxw then maxw := sum[v]; end;

if n - sum[node] > maxw then maxw := n - sum[node]; weight[node] := maxw; end; begin fillchar(map, sizeof(map), 0); fillchar(sum, sizeof(sum), 0); fillchar(weight, sizeof(weight), 0); fillchar(visit, sizeof(visit), 0); readln(n); for i := 1 to n - 1 do begin read(x,y); map[x,y]:=1; map[y,x]:=1; end; dfs(1); ans := n; ansn := 0; for i := 1 to n do if weight[i] < ans then begin ans := weight[i]; ansn := i; end; writeln(ansn, ' ', ans); end. 输入:11 12 13 24 25 26 37 78 7 11 69 9 10 输出:_________ 五、完善程序(共 2 题,每题 14 分,共计 28 分) 1. (交朋友)根据社会学研究表明,人们都喜欢找和自己身高相近的人做朋友。现在有 n 名身高两两不相同的同学依次走入教室, 调查人员想预测每个人在走入教室的瞬间最想和已

经进入教室的哪个人做朋友。 当有两名同学和这名同学的身高差一样时, 这名同学会更想和 高的那个人做朋友。比如一名身高为 1.80 米的同学进入教室时,有一名身高为 1.79 米的同 学和一名身高为 1.81 米的同学在教室里, 那么这名身高为 1.80 米的同学会更想和身高为 1.81 米的同学做朋友。对于第一个走入教室的同学我们不做预测。 由于我们知道所有人的身高和走进教室的次序, 所以我们可以采用离线的做法来解决这 样的问题, 我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最 相近的人。 (第一空 2 分,其余 3 分) const maxn = 200000; infinity = 2147483647; var answer, height, previous, next: array[0..maxn] of longint; rank: array[0..maxn] of longint; n, higher, shorter, i: longint; procedure sort(l, r: longint); var x, i, j, temp: longint; begin x := height[rank[(l + r) div 2]]; i := l; j := r; while i <= j do begin while height[rank[i]] < x do inc(i); while height[rank[j]] > x do dec(j); if (1) then begin temp := rank[i]; rank[i] := rank[j]; rank[j] := temp; inc(i); dec(j); end; end; if i < r then sort(i, r); if l < j then sort(l, j); end; begin readln(n); for i := 1 to n do begin read(height[i]); rank[i] := i; end; sort(1, n); for i := 1 to n do

begin previous[rank[i]] := rank[i - 1]; (2) ; end; for i := n downto 2 do begin higher := infinity; shorter := infinity; if previous[i] <> 0 then shorter := height[i] - height[previous[i]]; if next[i] <> 0 then (3) ; If (4) then answer[i] := previous[i] else answer[i] := next[i]; next[previous[i]] := next[i]; (5) ; end; for i := 2 to n do writeln(i, ':', answer[i]); end. 2. (交通中断)有一个小国家,国家内有 n 座城市和 m 条双向的道路,每条道路连接着 两座不同的城市。其中 1 号城市为国家的首都。由于地震频繁可能导致某一个城市与外界 交通全部中断。这个国家的首脑想知道,如果只有第 i(i>1)个城市因地震而导致交通中断时, 首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 i 个城市而导致从首 都出发无法到达某个城市,也认为到达该城市的最短路径长度改变。 对于每一个城市 i, 假定只有第 i 个城市与外界交通中断, 输出有多少个城市会因此导 致到首都的最短路径长度改变。 我们采用邻接表的方式存储图的信息,其中 head[x]表示顶点 x 的第一条边的编号, next[i]表示第 i 条边的下一条边的编号,point[i]表示第 i 条边的终点,weight[i]表示第 i 条 边的长度。 (第一空 2 分,其余 3 分) const maxn = 6000; maxm = 100000; inf = 2147483647; var next, point, weight: array[1..maxm] of longint; head, dist, visit: array[1..maxn] of longint; queue: array[0..maxn - 1] of longint; n, m, i, j, s, t, total, x, y, z, answer: longint; procedure link(x, y, z: longint);

begin inc(total); next[total] := head[x]; head[x] := total; point[total] := y; weight[total] := z; inc(total); next[total] := head[y]; head[y] := total; point[total] := x; weight[total] := z; end; begin total := 0; readln(n, m); for i := 1 to m do begin readln(x, y, z); link(x, y, z); end; for i := 1 to n do dist[i] := inf; (1) ; queue[1] := 1; visit[1] := 1; s := 1; t := 1; // 使用 SPFA 求出第一个点到其余各点的最短路长度 while s <= t do begin x := queue[s mod maxn]; j := head[x]; while j <> 0 do begin if (2) then begin dist[point[j]] := dist[x] + weight[j]; if (visit[point[j]] = 0) then begin inc(t); queue[t mod maxn] := point[j]; visit[point[j]] := 1; end; end; j := next[j];

end; (3) inc(s); end; for i := 2 to n do begin queue[1] := 1; fillchar(visit, sizeof(visit), 0); visit[1] := 1; s := 1; t := 1; while s <= t do // 判断最短路长度是否不变 begin x := queue[s]; j := head[x]; while j <> 0 do if (point[j] <> i) and ( (4) ) and (visit[point[j]] = 0) then begin (5) ; inc(t); queue[t] := point[j]; end; j := next[j]; inc(s); end; answer := 0; for j := 1 to n do inc(answer, 1 - visit[j]); writeln(i, ':', answer - 1); end; end. ;

第二十二届全国青少年信息学奥林匹克联赛初赛 提高组参考答案
一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分)
1 D 9 B 2 A 10 D 3 B 11 B 4 B 12 A 5 B 13 C 6 B 14 C 7 B 15 A 8 B

二、不定项选择题(共 5 题,每题 1.5 分,共计 7.5 分;每题有一个或多个正确选项,没有部 分分) 2 1 ABC A 3 AB 4 A 5 ABD

三、问题求解(共 2 题,每题 5 分,共计 10 分;每题全部答对得 5 分,没有部分分) 1. 55 2. 3 四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. 6,5,4,3,2,1, 2. YES,NO,YES, 3. 5 4. 2 5 五、完善程序(共计 28 分,以下各程序填空可能还有一些等价的写法,由各省赛区组织本 省专家审定及上机验证,可以不上报 CCF NOI 科学委员会复核) Pascal 语言 1 1 2 3 4 5 2 1 2 3 4 5 visit[x]:=0 dist[x]+weight[j]=dist[point[j]] visit[point[j]:=1 dist[1]:=0 dist[x]+weight[j]<dist[point[j]] visit[x]=0 dist[x]+weight[j]==dist[point[j]] visit[point[j]=1 next[rank[i]]:=rank[i+1] higher:=height[next[i]]-height[i] previous[next[i]]:=previous[i] shorter<higher previous[next[i]]=previous[i] dist[1]=0 i<=j next[rank[i]]=rank[i+1] higher=height[next[i]]-height[i] C++语言 C 语言 分值 2 3 3 3 3 2 3 3 3 3


NOIP2016年第二十二届全国青少年信息学奥林匹克联赛提....doc

NOIP2016年第二十二届全国青少年信息学奥林匹克联赛提高组初赛(pascal)_学科竞赛_高中教育_教育专区。NOIP2016年第二十二届全国青少年信息学奥林匹克联赛提高组初赛(...

NOIP2017提高组Pascal试题.pdf

NOIP2017提高组Pascal试题 - 第二十届全国青少年信息学奥林匹克联赛初赛 提高组 Pascal 语言试题 选手注意: ? 试题纸共有 10 页,答题纸共有 2 页,满分 100...

...二十三届全国青少年信息学奥林匹克联赛提高组初赛答....doc

NOIP2017第二十届全国青少年信息学奥林匹克联赛提高组初赛答案_其它课程_高中...本省专 家审定及上机验证,可以不上报 CCF NOI 科学委员会复核) Pascal 语言 ...

NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛....pdf

NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组试题及答案PASCAL)_电子/电路_工程科技_专业资料。第二十届全国青少年信息学奥林匹克联赛初赛...

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题....doc

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案_学科竞赛_高中

第22届全国青少年信息学奥林匹克联赛NOIP2016提高组试....doc

第22 届全国青少年信息学奥林匹克联赛 CCF-NOIP-2016 提高组(复赛)第一试 ...Pascal 语言 编译选项 对于 C++语言 对于语言 对于 Pascal 语言 注意事项: 1....

NOIP初赛试题及答案(提高组Pascal).doc

NOIP初赛试题及答案(提高组Pascal) - 第十届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 Pascal 语言 二小时完成 )●● 全部试题答案均要求写在答卷纸上,写...

第五届全国青少年信息学奥林匹克联赛初赛试题及答案(提....pdf

第五届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组PASCAL)_学科竞赛_小学...NOIP1999 年(第届)提高组(Pascal 语言)参考答案 一、单项选择题 1. C 2...

NOIP2013信息学奥林匹克联赛初赛试题(提高组PASCAL).pdf

NOIP2013信息学奥林匹克联赛初赛试题(提高组PASCAL)_电子/电路_工程科技_专业资料。第十九届全国青少年信息学奥林匹克联赛初赛提高组 Pascal 语言试题 竞赛时间:2013 ...

NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛....doc

NOIP2015第二十届全国青少年信息学奥林匹克联赛初赛提高组C语言试题_学科竞赛_高中教育_教育专区。NOIP2015第二十届全国青少年信息学奥林匹克联赛初赛提高组C语言...

第十五届全国青少年信息学奥林匹克联赛初赛试题(pascal....doc

第十五届全国青少年信息学奥林匹克联赛初赛试题提高组 ( 提高组 Pascal 语言 二...(nlog2n) NOIP2009 初赛 提高组 Pascal 1 D) 平均情况 O(log2n), 最坏...

第十六届_NOIP2010全国青少年信息学奥林匹克联赛初赛试....doc

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

第十四届全国青少年信息学奥林匹克联赛pascal初赛试题....doc

第十四届全国青少年信息学奥林匹克联赛pascal初赛试题...将数据和程序封装在对象中,以提高软件的重用性、...NOIP2008年普及组(Pascal 语言)参考答案与评分标准 ...

...(pascal)第九届全国青少年信息学奥林匹克联赛初赛试....pdf

NOIP2003(pascal)第九届全国青少年信息学奥林匹克联赛初赛试题_院校资料_高等教育_教育专区。第九届全国青少年信息学奥林匹克联赛初赛试题 (普及组 PASCAL 语言 二...

(NOIP2005)第11届全国青少年信息学奥林匹克联赛初赛试....doc

(NOIP2005)第11届全国青少年信息学奥林匹克联赛初赛试题普及组pascal_IT/计算机_专业资料。第十一届全国青少年信息学奥林匹克联赛初赛试题 (普及组 pascal 语言 二...

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

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

NOIP2013信息学奥林匹克联赛初赛试题(提高组PASCAL).doc

NOIP2013信息学奥林匹克联赛初赛试题(提高组PASCAL)_学科竞赛_高中教育_教育专区。NOIP2013信息学奥赛全国联赛提高组Pascal 第十九届全国青少年信息学奥林匹克联赛初赛...

NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛提高....pdf

NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛提高组Pascal试题_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛提高组 Pascal 语言试题 ...

Noip第16届2010提高组初赛试题PASCAL(完整版).doc

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

第十五届全国青少年信息学奥林匹克联赛初赛试题普及组 ....doc

第十五届全国青少年信息学奥林匹克联赛初赛试题普及组 Pascal语言(附答案)_电脑基础...输入:NOIP 3 输出:___ 完善程序( 四. 完善程序(前 8 空,每空 3 分,后...