当前位置:首页 >> 其它考试 >>

NOIP2015提高组Pascal试题及参考答案


第二十一届全国青少年信息学奥林匹克联赛初赛 提高组 Pascal 语言试题
竞赛时间:2015 年 10 月 11 日 14:30~16:30
选手注意: 试题纸共有 9 页,答题纸共有 2 页,满分 100 分。请在答题纸上作答,写在试题纸上的一律无效。 不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。 一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分;每题有且仅有一个正确选项) 1. 在计算机内部用来传送、存贮、加工处理的数据或指令都是以( )形式进行的。 A. 二进制码 B. 八进制码 C. 十进制码 D. 智能拼音码 2. 下列说法正确的是( ) 。 A. CPU 的主要任务是执行数据运算和程序控制 B. 存储器具有记忆能力,其中信息任何时候都不会丢失 C. 两个显示器屏幕尺寸相同,则它们的分辨率必定相同 D. 个人用户只能使用 Wifi 的方式连接到 Internet 3. 与二进制小数 0.1 相等的十六进制数是( ) 。 A. 0.8 B. 0.4 C. 0.2 D. 0.1 4. 下面有四个数据组,每个组各有三个数据,其中第一个数据为八进制数,第二个数据为十进制数,第 三个数据为十六进制数。这四个数据组中三个数据相同的是( ) 。 A. 120 82 50 A. 必须连续 C. 一定不连续 B. 144 100 68 C. 300 200 C8 D. 1762 1010 3F2 5. 线性表若采用链表存储结构,要求内存中可用存储单元地址( ) 。 B. 部分地址必须连续 D. 连续不连续均可

6. 今有一空栈 S,对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行进栈,进栈,出栈,进栈,进栈, 出栈的操作,则此操作完成后,栈 S 的栈顶元素为( ) 。 A. f B. c C. a D. b B. 只有根结点的二叉树 7. 前序遍历序列与后序遍历序列相同的二叉树为( ) 。 A. 非叶子结点只有左子树的二叉树 C. 根结点无右子树的二叉树 A. 5 A. 6 B. 6 B. 5 C. 7 C. 7 D. 8 D. 4 D. 非叶子结点只有右子树的二叉树

8. 如果根的高度为 1,具有 61 个结点的完全二叉树的高度为( ) 。 9. 6 个顶点的连通图的最小生成树,其边数为( ) 。 10. 设某算法的计算时间表示为递推关系式 T(n) = T(n - 1) + n(n 为正整数)及 T(0) = 1,则该算法的 时间复杂度为( ) 。 A. O(log n) 度均为( ) 。 A. Θ (n2) B. Θ (e2) C. Θ (ne) D. Θ (n+e) 12. 在数据压缩编码的应用中,哈夫曼(Huffman)算法是一种采用了( )思想的算法。 B. O(nlogn) C. O(n) D. O(n2) 11. 具有 n 个顶点,e 条边的图采用邻接表存储结构,进行深度优先遍历和广度优先遍历运算的时间复杂

A. 贪心

B. 分冶

C. 递推

D. 回溯

13. 双向链表中有两个指针域,llink 和 rlink,分别指回前驱及后继,设 p 指向链表中的 一个结点,q 指向一待插入结点,现要求在 p 前插入 q,则正确的插入为( ) 。 A. p^.llink := q; q^.rlink := p; p^.llink^.rlink := q; q^.llink := p^.llink; B. q^.llink := p^.llink; p^.llink^.rlink := q; q^.rlink := p; p^.llink := q^.rlink; C. q^.rlink := p; p^.rlink := q; p^.llink^.rlink := q; q^.rlink := p; D. p^.llink^.rlink := q; q^.rlink := p; q^.llink := p^.llink; p^.llink := q; 14. 对图 G 中各个结点分别指定一种颜色,使相邻结点颜色不同,则称为图 G 的一个正常 着色。正常着色图 G 所必需的最少颜色数,称为 G 的色数。那么下图的色数是( ) 。

A. 3 ( ) 。 A. 鼠标 得分) B. 笔

B. 4

C. 5

D. 6

15. 在 NOI 系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选手自带的是 C. 身份证 D. 准考证

二、不定项选择题(共 5 题,每题 1.5 分,共计 7.5 分;每题有一个或多个正确选项,多选或少选均不 1. 以下属于操作系统的有( ) 。 A. Windows XP A. AVI B. MPEG B. UNIX C. WMV C. Linux D. JPEG C. 100:128:35:91 D. 111-127-35-21 D. Mac OS 2. 下列属于视频文件格式的有( ) 。 3. 下列选项不是正确的 IP 地址的有( ) 。 A. 202.300.12.4 B. 192.168.0.3 4. 下列有关树的叙述中,叙述正确的有( ) 。 A. 在含有 n 个结点的树中,边数只能是(n-1)条 B. 在哈夫曼树中,叶结点的个数比非叶结点个数多 1 C. 完全二叉树一定是满二叉树 D. 在二叉树的前序序列中,若结点 u 在结点 v 之前,则 u 一定是 v 的祖先 5. 以下图中一定可以进行黑白染色的有( ) 。 (黑白染色:为各个结点分别指定黑白 两种颜色之一,使相邻结点颜色不同。 ) A. 二分图 B. 完全图 C. 树 D. 连通图 三、问题求解(共 2 题,每题 5 分,共计 10 分;每题全部答对得 5 分,没有部分分) 1. 在 1 和 2015 之间(包括 1 和 2015 在内)不能被 4、5、6 三个数任意一个数整除的数

有_________个。 2. 结点数为 5 的不同形态的二叉树一共有_________种。 (结点数为 2 的二叉树一共有 2 种:一种是根结点和左儿子,另一种是根结点和右儿子。 ) 四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. type point = record x: longint; y: longint; end; EX = record a: longint; b: longint; c: point; end; var e: EX; begin e.a := 1; e.b := 2; e.c.x := e.a + e.b; e.c.y := e.a * e.b; writeln(e.c.x, ',', e.c.y); end. 输出:_________ 2. type p_char = ^char; var c1, c2: char; p1, p2: p_char; procedure fun(a, b: p_char); begin a := b; inc(a^); end; begin c1 := 'A'; c2 := 'a'; p1 := @c1; p2 := @c2; fun(p1,p2);

writeln(c1, c2); end. 输出:_________ 3. var len, maxlen: longint; s, ss: string; begin maxlen := 0; while true do begin readln(ss); len := length(ss); if ss[1] = '#' then break; if len > maxlen then begin s := ss; maxlen := len; end; end; writeln(s); end. 输入: I am a citizen of China # 输出:_________ 4. var n: longint; function fun(n, fromPos, toPos: longint): longint; var t, tot: longint; begin if n = 0 then exit(0); for t := 1 to 3 do if (t <> fromPos) and (t <> toPos) then break; tot := 0;

inc(tot, fun(n - 1, fromPos, t)); inc(tot); inc(tot, fun(n - 1, t, toPos)); exit(tot); end; begin read(n); writeln(fun(n, 1, 3)); end. 输入:5 输出:_________ 五、完善程序(共 2 题,每题 14 分,共计 28 分) 1. (双子序列最大和)给定一个长度为 n(3 ≤ n ≤ 1000)的整数序列,要求从中选出两个 连续子序列,使得这两个连续子序列的序列和之和最大,最终只需输出这个最大和。一个连续子序列的 序列和为该连续子序列中所有数之和。要求:每个连续子序列长度至少为 1,且两个连续子序列之间至少 间隔 1 个数。 (第五空 4 分,其余 2.5 分) Const MAXN = 1000; var n, i, ans, sum: longint; x: array [1..MAXN] of longint; lmax: array [1..MAXN] of longint; // lmax[i]为仅含 x[i]及 x[i]左侧整数的连续子序列的序列和中,最大的序列和 of longint; // rmax[i]为仅含 x[i]及 x[i]右侧整数的连续子序列的序列和中,最大的序列和 begin read(n); for i := 1 to n do read(x[i]); lmax[1] := x[1]; for i := 2 to n do if lmax[i - 1] <= 0 then lmax[i] := x[i] else lmax[i] := lmax[i - 1] + x[i]; for i := 2 to n do if lmax[i] < lmax[i - 1] then lmax[i] := lmax[i - 1]; (1) ; (2) for i := n - 1 downto 1 do if rmax[i + 1] <= 0 then else (3) ; (4) ; for i := n - 1 downto 1 do if rmax[i] < rmax[i + 1] then ans := x[1] + x[3]; rmax: array [1..MAXN]

for i := 2 to n - 1 do begin sum:= end; writeln(ans); end. 2. (最短路径问题)无向连通图 G 有 n 个结点,依次编号为 1,2,3,...,n。用邻接矩阵的形 式给出每条边的边长,要求输出以结点 1 为起点出发,到各结点的最短路径长度。 使用 Dijkstra 算法解 决该问题:利用 dist 数组记录当前各结点与起点的已找到的最短路径长度;每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展,更新与 v 相邻的结点的 dist 值;不断进行上述操作直至所有结点均被扩 展,此时 dist 数据中记录的值即为各结点与起点的最短路径长度。 (第五空 2 分,其余 3 分) Const MAXV = 100; var n, i, j, v: longint; w: array [1..MAXV, 1..MAXV] of longint; // 邻接矩阵,记录边长 // 其中 w[i, j]为连接结点 i 和结点 j 的无向边长度,若无边则为-1 dist: array [1..MAXV] of longint; used: array [1..MAXV] of longint; // 记录结点是否已扩展(0:未扩展;1:已扩展) begin read(n); for i := 1 to n do for j := 1 to n do read(w[i, j]); dist[1] := 0; for i := 2 to n do dist[i] := -1; for i := 1 to n do used[i] := 0; while true do begin (1) ; (2) )) then (3) ; for i := 1 to n do if (used[i] <> 1) and (dist[i] <> -1) and ((v=-1) or ( if v = -1 then break; (4) ; (5) )) then dist[i] := dist[v] + w[v, i]; for i := 1 to n do if (w[v, i] <> -1) and ((dist[i] = -1) or ( end; for i := 1 to n do writeln(dist[i]); end. (5) ; if sum > ans then ans := sum;

第二十一届全国青少年信息学奥林匹克联赛初赛 提高组参考答案
一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分) 1 A 9 B 1 ABCD 1、1075 2、42 四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1、3,2 2、Ab 3、citizen 4、31 五、完善程序(共计 28 分,以下程序填空可能还有一些等价的写法,由各省赛区组织本省专家审定及上 机验证,可以不上报 CCF NOI 科学委员会复核) Pascal 语言 (1) (2) 1 (3) (4) (5) (1) (2) (3) 2 (4) V:=-1 V:=i Used[v]:=1 Dist[v]+w[v,i]<dist[i] 或 (5) Dist[i]>dist[v]+w[v,i] 或 Dist[v]+w[v,i]<=dist[i] 或 dist[i]>=dist[v]+w[v,i] Rmax[n]:=x[n] Rmax[i]:=x[i] Rmax[i]:=rmax[i+1]+x[i] Ramx[i]:=rmax[i+1] C++语言 Rmax[n-1]=x[n-1] Rmax[i]=x[i] Rmax[i]=rmax[i+1]+x[i] Rmax[i]=rmax[i+1] Lmax[i-1]+rmax[i+1] V=-1 V=i Used[v]=1 Dist[v]+w[v][i]<dist[i] 或 Dist[i]>dist[v]+w[v][i] 或 Dist[v]+w[v][i]<=dist[i] 或 Dist[i]>=dist[v]+w[v][i] 2 Dist[i]<dist[v] 或 dist[v]>dist[i] 或 dist[i]<=dist[v] 或 dist[v]>=dist[i] C 语言 分值 2.5 2.5 2.5 2.5 4 3 3 3 3 2 A 10 D 3 A 11 D 2 ABC 4 D 12 A 3 ACD 5 D 13 D 6 B 14 A 4 AB 7 B 15 A 5 AC 8 B

二、不定项选择题(共 5 题,每题 1.5 分,共计 7.5 分;每题有一个或多个正确选项,没有部分分)

三、问题求解(共 2 题,每题 5 分,共计 10 分;每题全部答对得 5 分,没有部分分)


相关文章:
NOIP2015提高组Pascal试题及参考答案.doc
NOIP2015提高组Pascal试题及参考答案_其它考试_资格考试/认证_教育
NOIP2015提高组参考答案.pdf
NOIP2015提高组参考答案_学科竞赛_高中教育_教育专区。第二十一届全国青少年信息...本省专家审定及 上机验证,可以不上报 CCF NOI 科学委员会复核) Pascal 语言 ...
NOIP2015普及组初赛试题及答案(Pascal).doc
NOIP2015普及组初赛试题及答案(Pascal)_学科竞赛_初中教育_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 竞赛时间:2015 年 10 月...
NOIP2016提高组Pascal试题.pdf
以下属于无线通信技术的有( CCF NOIP2016 初赛提高组 Pascal 语言试题 第 3 页,共 13 页 西 D. O(2 ) D. b, a, c A. 蓝牙 B. WiFi C. GPRS D...
noip2015提高组复赛试题答案.doc
noip2015提高组复赛试题答案_IT认证_资格考试/认证_教育专区。全国信息学奥林...编译命令(不包含任何优化开关) 对于 C++语言 对于 C 语言 对于 pascal 语言 ...
noip2015提高组复赛试题答案.doc
noip2015提高组复赛试题答案_IT认证_资格考试/认证_教育专区。noip2015 提高组...对于pascal语言 fpc magic.pas message.cpp message.c message.pas landlords....
NOIP2017提高组Pascal试题.pdf
NOIP2017提高组Pascal试题 - 第二十三届全国青少年信息学奥林匹克联
NOIP2016提高组Pascal试题.pdf
NOIP2016提高组Pascal试题_学科竞赛_高中教育_教育...(n 为正整数)及 T(0) = 1,则 该算法的时间...NOIP2015提高组Pascal试... 9页 1下载券 NOIP2013...
NOIP初赛试题及答案(提高组Pascal).doc
NOIP初赛试题及答案(提高组Pascal) - 第十届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 Pascal 语言 二小时完成 )●● 全部试题答案均要求写在答卷纸上,写...
NOIP2000提高组pascal初赛试题和答案.pdf
NOIP2000提高组pascal初赛试题答案 - 第六届全国青少年信息学(计算机)奥林匹克分区联赛试题 ( 提高组 PASCAL 语言 二小时完成 )●● 全部试题答案均要求写在答卷...
NOIP2015提高组复赛试题Day1.doc
NOIP2015提高组复赛试题Day1_学科竞赛_高中教育_教育...(过滤行末空格及文末回车) 传统 传统 传统 128M ...对于pascal语言 magic.pas 三.编译命令(不包含任何...
NOIP2015普及组初赛试题及答案(PASCAL).pdf
NOIP2015普及组初赛试题及答案(PASCAL)_电子/电路_工程科技_专业资料。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 竞赛时间:2015 年 10 ...
NOIP2015普及组初赛试题及答案(Pascal).doc
NOIP2015普及组初赛试题及答案(Pascal)_学科竞赛_初中教育_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 竞赛时间:2015 年 10 月...
NOIP2015普及组Pascal试题.pdf
NOIP2015普及组Pascal试题_IT认证_资格考试/认证_教育专区。第二
NOIP2013初赛提高组Pascal试题及答案.doc
NOIP2013初赛提高组Pascal试题及答案 - 第十九届全国青少年信息学奥
NOIP2017提高组Pascal试题(NOIP2017提高组C试题(无水印....pdf
NOIP2017提高组Pascal试题(NOIP2017提高组C试题(无水印,去水印版)_学科竞赛_高中教育_教育专区。NOIP,NOIP2017,提高组,Pascal,无水印,去水印,信息学,NOIP2017提高...
noip2011提高组pascal试题及答案_图文.pdf
noip2011提高组pascal试题及答案_演讲/主持_工作范文_实用文档。noip2011提高组pascal试题及答案 文档贡献者 akng1208 贡献于2011-10-19 ...
NOIP2014提高组Pascal初赛试题.pdf
NOIP2014提高组Pascal初赛试题 - 第二十届全国青少年信息学奥林匹克联赛初赛 提高组 Pascal 语言试题 竞赛时间:2014 年 10 月 12 日 14:30~16:30 选手...
noip2007 提高组复赛试题及参考程序(pascal)_图文.doc
noip2007 提高组复赛试题及参考程序(pascal) - 全国信息学奥林匹克联赛(NOIP2007)复赛 题目名称 代号 输入文件 输出文件 时限 统计数字 count count.in ...
noip2002 提高组 复赛试题及参考程序(pascal).doc
noip2002 提高组 复赛试题及参考程序(pascal) - NOIP 2002 年全国青少年信息学奥林匹克(计算机) 题一 均分纸牌(noip1.pas/c/cpp noipg1.in n...
更多相关标签: