tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

1999年至2013年历年信息学奥赛提高组初赛答案


福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

NOIP2013 第十九届全国青少年信息学奥林匹克联赛初 赛(提高组)试题解析
一、单选题(15*1.5) 1、A,一个字节有 8 个 bit,32 位整型变量占用 4 个字节,故选 A。 2、A,二进制 11.01 转为十进制,(11.01)2 = 1*2+1+0*0.5

+1*0.25 = (3.25) 10 。 3、B,老和尚给小和尚讲的故事里边有故事本身,递归是函数内部调用函数本身, 故选 B,递归。 4、D,香农信息论鼻祖。 5、A,一定是满二叉树时拥有 2 个字节点的节点数最多,最下一层会有 2013-1023=990 个节点,于是倒数第二层会有 990/2=495 个节点有 2 个字节点, 从第 1 层到倒数第三层共有 1023-2^9=511 个节点, 且这些节点都是用 2 个子节点 的节点,所以共有 495+511=1006 个,选 A。 6、B,要使图不联通,只要其中某一个节点不连通即可,所有顶点度最少是 3, 所以最少需要删除 3 条边,选 B。 7、D,此题最开始一眼扫到的时候脑子进水,跟学生将选 B,O(n),实际上不 是,计算 F1 需要 1 次,计算 F2 需要一次,计算 Fn 需要计算 F(n-1)的次数加上 F (n-2)的次数,所以其实就是计算 Fn 次,于是答案选择 D,至于这个 Fn 到底是 多大,数学上可以计算,它等于 O(((1+sqrt(5))/2)^n). 8、B,这个必须是 B,没有什么好说的,中序遍历保证左边都是小于根的,右边 都是大于根的,所以可以保证是一个有序序列。 9、D,A 项 6 和 17 对 11 取余都是 6 发生冲突,B 项 10 的平方和 17 的平方对 11 取余都是 1 发生冲突,C 项 6 的两倍和 17 的两倍对 11 取余都是 1 发生冲突,D 项 分别为 1,2,3,4,不冲突。 10、D,IPV6 地址是 128 位的。谢谢网友指正! 11、C,二分为 6 个和 6 个的顶点,此时边最多,有 36 条边。 12、B,我的学生几乎全选 A 去了,因为之前讲题只介绍过 ASCII 码,但是看到统 一二字也应该想到 Uni...前缀啊。 13、D,64 位非零浮点数强制转换成 32 位浮点数,两个数会有大小上的细微差别, 但不会发生符号变化,因为有专门的符号位。 14、B,Dijkstra 算法计算单源最短路时间复杂度如果不借助堆或优先队列优化, 是 O(n^2). 15、B,此题和学生讲的时候又是脑子进水了,我一眼扫以为选 A,后来令 n=2,4, 8,16 等值带如递推式,发现计算出来的 T(n)和 n 不成线性关系,也不成 n^2 关系,仔细研究了一下,发现其实是 nlgn,具体可以画图证明。 二、不定项选择题(5*1.5) 1、AC,求 1,2,...100 的和,这个平时练习过很多次。
1

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

2、AD,只有快速排序和归并排序是 nlgn 的,冒泡和插入都是 n^2 的时间复杂度。 3、CD,此题最开始以为选 BD,因为我题目错看成宽度优先搜索了。 4、AB,如果一个问题复杂度是该问题的一个实例规模 n 的多项式函数,则这种可 以在多项式时间内解决的问题属于 P 类问题;可以在多项式时间内验证一个解是 否正确的问题称为 NP 类问题; 可以在多项式时间内解决的问题一定可以在多项式 时间内验证,所以 P 类问题一定属于 NP 类问题,故此题应选择 AB,D 我看错了, NP 类问题显然不是说在指数时间内能够解决的问题,谢谢网友提示!。 5、ABCD, 此题完全不会, 因为是第一次带学生参赛,对复赛什么情况完全不了解, 个人觉得程序名、输出文件名这类问题不应该是什么大问题应该允许申诉,但对 BD 这些没按规定要求做的肯定不会受理的,网友回复说选 ABCD,那就暂时改为 ABCD,如有其他声音,欢迎批评指正。 三、问题求解(2*5) 1、0 1 1 1;此题应该算是简单题,密码都是 0 或 1,所以根据第 5 项可以很轻 松得到 S1=0,再根据第 1 项可以得到 S2=1,再根据第 3 项可以 S3=1,最后根据 第 2 项得到 S4=1,然后利用第 4 项进行验证发现可行。 2、37/12,此题最开始看到做不出来,只知道这是一道求数学期望的题目。计算 n=2 为什么平均一共跳 2 次的时候,我最开始是这么想的,1 次跳到 1 处的概率是 1/2,2 次的概率是 1/4,3 次是 1/8.。。。于是数学期望 Ex=1*1/2+2*1/4+3*1/8+......=2,但是这样的计算对于后边 n=3,得情况却怎么 都算不了,于是想到递归,设从 2 跳到 1 的期望是 f2,那么有 1/2 的概率是一次 跳到 1,还有 1/2 的概率是(1+f2)次跳到 1,即第一次没有跳到 1,跳到 2 的情 况,于是可以列出等式:f2=1*1/2+(1+f2)*1/2,解出 f2=2;对于 n=3,则有 1/3 的概率一次跳到 1,有 1/3 的概率(1+f2)次跳到 1,即第一次跳到 2,再从 2 跳 到 1 的过程,最后还有 1/3 的概率(1+f3)次跳到 1,于是 f3=1/3+(1+f2)*1/3+ (1+f3)*1/3,解出 f3=2.5;同理 f4=1/4+(1+f2)*1/4+(1+f3)*1/4+(1+f4) *1/4,解出 f4=17/6;f5=1/5+(1+f2)*1/5+(1+f3)*1/5+(1+f4)*1/5+(1+f5)*1/5, 解出 f5=37/12. 四、阅读程序写结果(4*8) 1、Yes,此程序判断给定字符串是否是回文串。显然输入串"abceecba"是回文串。 2、133,此题计数 1-1000 范围内能够整除 10 或 15 的数有多少个,使用容斥原理 或者集合求并很容易可以得到 1000/10+1000/15-1000/30=133. 3、4,此题实际上是一种简单的动态规划的方法找最长递增串的长度,从输入数 据 3 2 5 11 12 7 4 10 来看,显然最长的递增串可以是 3 5 11 12,长度为 4; 4、7,似乎二分图染色问题,手动模拟出结果为 7. 五、完善程序(15+13) 1、n-p+i i-p+1 a[i-p] i>end1 i j-1; 序列重排还是比较简单的一道题目,第一种方法是通过开一个 b 数组,然后先将 a 数组中 1 到 p 的数复制到 b 数组中 n-p+1 到 n, 将 p+1 到 n 区间的数复制到 b 数 组 1,n-p,最后再将 b 数组元素复制回 a 数组中;显然第一空是 n-p+i。

2

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

第二种方法是以时间换空间的方法,每一次先将要移到前面的数保存在 temp 中, 然后将前面那 p 个数依次往后移,再将空出来的那个位置存 temp;所以第二个空 和第三个空分别是 i-p+1 和 a[i-p]。 第三种方法的实际上是一种递归的思想,第四、五、六空分别是 i〉end1 i,i, j-1 2、j-i cur1 count1--; count2--; cur1=a[j],此题没什么好说的,题目中的注 释已经讲得很明白了。

3

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

NOIP2012 初赛提高组参考答案(PASCAL)
一、单项选择题 1 A 2 B 3 B 4 A 5 D 6 A 7 A 8 D 9 A 10 B

二、不定项选择题 1 A 2 AD 3 AD 4 BD 5 ABC 6 CD 7 AB 8 A 9 CD 10 BD

三、问题求解 1、 256 2、 5536 四、阅读程序题 1.41 2.16 3.(1)7 (2)2004 4.55 五、完成程序题 1、(1)false (2) used[data[i]]:=false; (3)j 2 、 (1) next:=k mod c+1 或 s[n]:=q[tail]; (3) q[head] (4) q[head] 注:false 可以用 0 来代替; (4)n (5)break (2)

next:= ( k mod c ) +1 (6) next(head)

(5) q[tail]

4

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

第十七届(2011 年)信息学奥赛提高组初赛试题答案
一、单项选择题(共 10 题,每题 1.5 分,共计 15 分) 1 B 2 B 3 A 4 D 5 B 6 A 7 C 8 D 9 B 10 A

二、不定项选择题(共 10 题,每题 1.5 分,共计 15 分,多选或少选均不得分) 1 CD 2 ABCD 3 AB 4 BC 5 BC 6 ABD 7 CD 8 A 9 BCD 10 ABC

三、问题求解(共 2 题,每题 5 分,共计 10 分) 1.9 2.4 四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1.3 2.1 2 5 13 34 3.150 4.57344 五、完善程序(第 1 题,每空 2 分,第 2 题,每空 3 分,共计 28 分) (说明:以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上机验证,不 一定上报科学委员会审查) 1.① ans.num[i + j - 1] ② ans.num[i] := ans.num[i] mod 10; ③ ans.num[i] + a.num[i] + b.num[i]; ④ ans.num[i] mod 2 (或 ans.num[i] and 1) ⑤ inc(ans.len) (或 ans.len := ans.len + 1) ⑥ a.len < b.len ⑦ ord('0')(或 48) ⑧ times(middle, middle), target
5

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

2.① inc(num) (或 num := num + 1) ② j := i ③ solve(left, j - 1, deep + 1) ④ solve(j + 1, right, deep + 1)

第十六届(2010 年)信息学奥赛初赛试题答案

一、单项选择题(共 10 题,每题 1.5 分,共计 15 分) 1 2 3 4 5 6 7 8 9 10 C A A D B D C B C B 二、不定项选择题(共 10 题,每题 1.5 分,共计 15 分,多选或少选均不得分) 1 2 3 4 5 6 7 8 9 10 ACD AD ABD AC B B D D BCD ABC 三、问题求解(共 3 题,每题 5 分,共计 15 分) 1.yyxy xx yyxy xyx xx xyx 2.12 3.18 四、阅读程序写结果(共 4 题,每题 7 分,共计 28 分) 1.16 2.1 2 3 5 6 7 9 10 14 3.4 4.1 6 9 5 4 8 3 2 7 五、完善程序(第 1 空 2 分,其余 10 空,每空 2.5 分,共计 27 分) (说明:以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上机验证, 不一定上报科学委员会审查) 1.① num <= 2(或 num < 3 或 num = 2) ② go(LEFT_TO_RIGHT) ③ pos[i] = LEFT(或 LEFT = pos[i]) ④ time[i] + go(RIGHT_TO_LEFT)(或 go(RIGHT_TO_LEFT) + time[i]) ⑤ pos[i] := LEFT 本小题中, LEFT 可用 true 代替, LEFT_TO_RIGHT 可用 true 代替, RIGHT_TO_LEFT 可用 false 代替。 2.① opt[k] ② home[r] := k ③ j := i + i(或 j := 2 * i 或 j := i * 2) ④ swap(i, j)(或 swap(j, i)) ⑤ value[i] + heap[1](或 heap[1] + value[i]) ⑥ i-m

6

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

第十五届(2009 年)信息学奥赛提高组初赛试题答案

一. 单项选择题 (共 10 题,每题 1.5 分,共计 15 分,每题有且仅有一个正确答案。) 1 、关于图灵机下面的说法哪个是正确的:答案(C) A)图灵机是世界上最早的电子计算机。 B)由于大量使用磁带操作,图灵机运行速度很慢。 C)图灵机只是一个理论上的计算模型。 D)图灵机是英国人图灵发明的,在二战中为破译德军的密码发挥了重要作用。 最早的计算机是 ENIAC 图灵机是计算机模型,没有运行速度,更谈不上磁带操作 图灵机是英国人阿兰图灵提出的理论, 阿兰图灵本人在二战中破译德军密码系统发挥重要作用,而不是图灵机发挥作用。

图灵是英国著名的数学家和逻辑学家,被称为计算机科学之父、人工智能之父,是计算 机逻辑的奠基者,提出了“图灵机”和“图灵测试”等重要概念。人们为纪念其在计算机领 域的卓越贡献而设立“图灵奖” 。 1936 年,阿兰 .图灵提出了一种抽象的计算模型 ── 图灵机 (Turing Machine) 。 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,他把这样的过程看 作下列两种简单的动作: 在纸上写上或擦除某个符号; 把注意力从纸的一个位置移动到另一个位置; “图灵机”不是一种具体的机器,而是一种思想模型,可制造一种十分简单但运算能 力极强的计算机装置,用来计算所有能想像得到的可计算函数。装置由一个控制器和 一根假设两端无界的工作带(起存储器的作用)组成。工作带被划分为大小相同的方 格,每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动,它带有 一个读写出一个你期待的结果。外行人看了会坠入云里雾里,而内行人则称它是“阐 明现代电脑原理的开山之作” ,并冠以“理想计算机”的名称。 “图灵机”更在电脑史 上与“冯 · 诺依曼机”齐名,被永远载入计算机的发展史中。 回顾 20 世纪科学技术的辉煌发展时,不能不提及 20 世纪最杰出的数学家之一的 冯· 诺依曼(美籍匈牙利人) 。 20 世纪 40 年代,冯 · 诺依曼在参与世界上第一台计算机 ENIAC 的研制小组工作时,发现 ENIAC 有两个致命的缺陷:一是采用十进制运算,逻 辑元件多,结构复杂,可靠性低;二是没有内部存贮器,操纵运算的指令分散存贮在 许多电路部件内,这些运算部件如同一副积木,解题时必须像搭积木一样用人工把大 量运算部件搭配成各种解题的布局,每算一题都要搭配一次,非常麻烦且费时。
7

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

针对这两个问题,诺依曼和其他合作者一起呕心沥血地进行了半年多时间的改革 性研究,结果取得了令人满意的成果。但是,由于 ENIAC 的制造已接近尾声,因此它 未能采用诺依曼的改进意见。 诺依曼的研究成果得到了 ENIAC 研制小组专家的青睐,他们在 ENIAC 尚未竣工 之前,就着手计划一个结构全新的电子计算机 — EDVAC 方案。 1945 年 6 月底,由诺 依曼执笔写出了 EDVAC 计划草案。在这个方案中,诺依曼提出了在计算机中采用二进 制算法和设置内存贮器的理论,并明确规定了电子计算机必须由运算器、控制器、存 贮器、输入设备和输出设备等五大部分构成的基本结构形式。他认为,计算机采用二 进制算法和内存贮器后,指令和数据便可以一起存放在存贮器中,并可作同样处理, 这样,不仅可以使计算机的结构大大简化,而且为实现运算控制自动化和提高运算速 度提供了良好的条件。EDVAC 于 1952 年建成,它的运算速度与 ENIAC 相似,而使用 的电子管却只有 5900 多个,比 ENIAC 少得多。EDVAC 的诞生,使计算机技术出现了 一个新的飞跃。它奠定了现代电子计算机的基本结构,标志着电子计算机时代的真正 开始。 根据冯 · 诺依曼提出的原理制造的计算机被称为冯 · 诺依曼结构计算机,现代计算机 虽然结构更加复杂,计算能力更加强大,但仍然是基于这一原理设计的,也是冯诺依 曼机。 最简单的来说,他的精髓贡献是 2 点: 2 进制思想与程序内存思想。 2、关于 BIOS 下面的说法哪个是正确的:答案(A) A)BIOS 是计算机基本输入输出系统软件的简称。 B)BIOS 里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。 C)BIOS 一般由操作系统厂商来开发完成。 D)BIOS 能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。 其实 bios=Basic Input Output System。但是对于是否是软件这一说法还存在争议呢! BIOS 只存一些系统启动的基本信息,这些设备的驱动程序是不存的。 BIOS 一般是由单独的芯片厂家生产的,最著名的都是台湾的三家。 固件 BIOS 根本这些功能。 BIOS 是"基本输入输出系统"。其实,它是一组固化到计算机内主板上一个 ROM 芯片上 的程序,它保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和 系统自启动程序。 其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。 3、 已知大写字母 A 的 ASCII 编码为 65 (十进制) , 则大写字母 J 的十六进制 ASCII 编码 为: 答案(D)

8

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

A)48

B)49

C)50

D)以上都不是

“0”的 ASCII 编码为 48 “A”的 ASCII 编码为 65 “a”的 ASCII 编码为 97 4 、 在 字 长 为 16 位 的 系 统 环 境 下 , 一 个 16 位 带 符 号 整 数 的 二 进 制 补 码 为 1111111111101101。其对应的十进制整数应该是:答案(B) A)19 B)-19 C)18 D)-18 最高位为符号位 补码 –1 再取反 原码:1000000000010011 十进制整数:-19 5 、一个包含 n 个分支结点(非叶结点)的非空满 k 叉树,k>=1,它的叶结点数目为:答案 (D) A)nk+1 B)nk-1 C)(k+1)n-1 D)(k-1)n+1 多叉树的性质,N0=(K-1)N+1,考试的时带入 K=2 时候,验证二叉树能得到结果。 二叉树的性质:N0=N2+1 即叶子节点比二叉节点数多一个。 (1)完全二叉树的定义:深度为 k,有 n 个结点的二叉树当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时,称为完全二叉树。 特点:叶子结点只可能在层次最大的两层上出现;对任一结点,若其右分支下子孙的最 大层次为 l,则其左分支下子孙的最大层次必为 l 或 l+1 (2)满二叉树:一棵深度为 k,且有 2 的(k)次方-1 个节点的二叉树 特点:每一层上的结点数都是最大结点数 满二叉树肯定是完全二叉树 完全二叉树不一定是满二叉树 一棵深度为 K 且有 2 的 K 次方减 1 个结点的二叉树称为满二叉树。 深度为 K 的,有 N 个结点的二叉树,当且仅当其每一个结点都与深度为 K 的满二叉树中 编号从 1 至 N 的结点一一对应,称之为完全二叉树。 0 / 0 / \ 0 \ 0 / \ 0 0 0 (1) 0 / 0 (2)
9

0 / \ 0 0

0 / \ 0 / \ 0 0 (3)

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

1、是满二叉树,也是完全二叉树。 2、是完全二叉树。 3、非完全二叉树。 简单的讲,将节点按层次从 1-n 编号: 1 / \ 2 3 / \ / \ 4 5 6 7 ... ... ... .. 缺少的节点只能是大号的,即: 如果 n 号节点存在, 则 1 到 n-1 号节点必定存在, 同样, 若 n 号节点不存在,则 n+1 号及更大号的节点也必定不存在 可以根据公式进行推导,假设 n0 是度为 0 的结点总数(即叶子结点数) ,n1 是度为 1 的 结点总数,n2 是度为 2 的结点总数,由二叉树的性质可知:n0=n2+1,则 n= n0+n1+n2 (其中 n 为完全二叉树的结点总数) ,由上述公式把 n2 消去得:n= 2n0+n1-1,由于完全二 叉树中度为 1 的结点数只有两种可能 0 或 1,由此得到 n0=(n+1)/2 或 n0=n/2,合并成 一个公式:n0=(n+1)/2,就可根据完全二叉树的结点总数计算出叶子结点数。

6 、表达式 a*(b+c)-d 的后缀表达式是:答案(B) A)abcd*+B)abc+*dC)abc*+d-

D)-+*abcd

主要是考树的遍历,要明白前缀、中缀和后缀表达式。 构造二叉树,操作数做叶子节点,运算符做非叶节点。按中序遍历就可以得到中缀表达 式。 根据所给表达式(其实正常的都是中缀表达式)可以构造二叉树 — / \ * d / \ a + / \ b c 中缀表达式就是中序遍历 a*(b+c)-d 后缀表达式就是后续遍历 abc+*d前缀表达式就是前序遍历-*a+bcd

10

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

7 、最优前缀编码,也称 Huffman 编码。这种编码组合的特点是对于较频繁使用的元素给与 较短的唯一编码,以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码:答案(B) A)(00,01,10,11) B)(0,1,00,11) C)(0,10,110,111) D)(1,01,000,001) 0 是 00 的前缀码,这部分是数据结构中哈夫曼编码处的知识。 哈夫曼编码 从哈夫曼树根结点开始,对左子树分配代码“0”,右子树分配代码“1”,一直到达 叶子结点为止,然后将从树根沿每条路径到达叶子结点的代码排列起来,便得到了哈夫曼 编码。 例,对电文 EMCAD 编码。若等长编码,则

EMCAD => 000001010011100 共 15 位 设各字母的使用频度为 {E,M,C,A,D}={1,2,3,3,4}。 用频度为权值生成哈夫曼树, 并在 叶子上标注对应的字母,树枝分配代码“0” 或“1”:

11

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

各字母的编码即为哈夫曼编码: EMCAD => 000001011011 共 12 位
8 、快速排序平均情况和最坏情况下的算法时间复杂度分别为:答案(A) A)平均情况 O(nlog(2,n)),最坏情况 O(n^2) B)平均情况 O(n),最坏情况 O(n^2) C)平均情况 O(n),最坏情况 O(nlog(2,n)) D)平均情况 O(log(2,n)),最坏情况 O(n^2) 最好的时候是 n× log(2,n) ,最坏情况的是退化成冒泡排序,复杂度为 O(n^2) 。 选择排序:O(n^2) 冒泡排序:O(n^2) 计数排序:O(n^2) 比较排序:O(log(2,n)-1.44n) 堆排序: O(log(2,n)) 9 、左图给出了一个加权无向图,从顶点 V0 开始用 prim 算法求最小生成树。则依次加 入最 小生成树的顶点集合的顶点序列为:答案(A) A)V0,V1,V2,V3,V5,V4 B)V0,V1,V5,V4,V3,V3 C)V1,V2,V3,V0,V5,V4 D)V1,V2,V3,V0,V4,V5 加入的边依次为 v0v1、v1v2、v1v3(或 v2v3) 、v1v5、v3v4。

12

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

Prim 算法用于求无向图的最小生成树。 假设 V 是图中顶点的集合,E 是图中边的集合,设图 G =(V,E),其生成树的顶点集合为 U。 ①、把 v0 放入 U。 ②、在所有 u∈U,v∈V-U 的边(u,v)∈E 中找一条最小权值的边,加入生成树。 ③、把②找到的边的 v 加入 U 集合。如果 U 集合已有 n 个元素,则结束,否则继续执行②。 其算法的时间复杂度为 O(n^2) 做法:任取一个顶点加入生成树,然后对那些一个端点在生成树中,而另一个端点不在生 成树中的边进行排序,取权值最小的边,将它和另一个端点加进生成树中。重复步骤直到所 有顶点都加进了生成树。 加入的边依次为 v0v1、v1v2、v1v3(或 v2v3)、 Prim 算法实现: ( 1) 集合: 设置一个数组 set(i=0,1,..,n-1), 初始值为 0, 代表对应顶点不在集合中 (注 意:顶点号与下标号差 1 )

( 2 ) 图用邻接矩阵或邻接表表示,路径不通用无穷大表示,在计算机中可用一个
大整数(如 1 << 30 )代替。 10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息 和资 源,请问全国信息学奥林匹克官方网站的网址是:答案(C) A)http://www.noi.com/ B)http://www.noi.org/ C)http://www.noi.cn/ D)http://www.xinxixue.com/

二、.不定项选择题(共 10 题,每题 1.5 分,共计 15 分,每题正确答案的个数不少于 1。多 选或少选均不得分)。答案(AB) 1、关于 CPU 下面哪些说法是正确的: A)CPU 全称为中央处理器(或中央处理单元)。 B)CPU 能直接运行机器语言。 C)CPU 最早是由 Intel 公司发明的。 D)同样主频下,32 位的 CPU 比 16 位的 CPU 运行速度快一倍。 Intel 最早发明的是微处理器,而 CPU 之前就由电子管、晶体管实现 位数只能说明处理的字长,所在的系统硬件指令不同,速度很难说谁快。 1、 64bit CPU 拥有更大的寻址能力, 最大支持到 16GB 内存, 32bit 支持 4G 内存, 而 16bit 只支持 64K 内存(1M) 。

13

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

2、64 位 CPU 一次可提取 64 位数据,比 32 位提高了一倍,理论上性能会提升 1 倍。但 这是建立在 64bit 操作系统,64bit 软件的基础上的(30%) 。 WindowsXP 64 位

2、关于计算机内存下面的说法哪些是正确的:答案(BD) A)随机存储器(RAM)的意思是当程序运行时,每次具体分配给程序的内存位置是随机而 不确定的。 B)一般的个人计算机在同一时刻只能存/取一个特定的内存单元。 C)计算机内存严格来说包括主存(memory)、高速缓存(cache)和寄存器(register)三 个部分。 D)1MB 内存通常是指 1024*1024 字节大小的内存。 一般是对字节的一个单元串行操作。1MB=1024KB=1024*1024B RAM 不是位置随机,而是随时访问,所谓“随机存取”,指的是当存储器中的消息被读取或 写入时,所需要的时间与这段信息所在的位置无关。 高速缓存和寄存器的物理实现是集成在 CPU 中, 这两部分不属于冯诺依曼体系中的五大部 分的任意一个部分。

3、关于操作系统下面说法哪些是正确的:答案(BC) A.多任务操作系统专用于多核心或多个 CPU 架构的计算机系统的管理。 B.在操作系统的管理下,一个完整的程序在运行过程中可以被部分存放在内存中。 C.分时系统让多个用户可以共享一台主机的运算能力,为保证每个用户都得到及时的响应通 常会采用时间片轮转调度的策略。 D.为了方便上层应用程序的开发,操作系统都是免费开源的。 多任务系统可以是单个 CPU 构架的,普通的 PC 都是多任务的。 操作系统不是都免费开源 4、关于计算机网络,下面的说法哪些是正确的:答案(C) A)网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。 B)新一代互联网使用的 IPv6 标准是 IPv5 标准的升级与补充。 C)TCP/IP 是互联网的基础协议簇,包含有 TCP 和 IP 等网络与传输层的通讯协议。 D)互联网上每一台入网主机通常都需要使用一个唯一的 IP 地址,否则就必须注册一个固定 的域名来标明其地址。 网络协议分层不是为了兼容,而是根据网络分层模型来的。 新的 IPv6 是 IPv4 的升级。
14

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

即使注册了域名也要有 IP 地址的。 5、关于 HTML 下面哪些说法是正确的:答案(BD) A)HTML 全称超文本标记语言,实现了文本、图形、声音、乃至视频信息的统一编码。 B)HTML 不单包含有网页内容信息的描述,同时也包含对网页格式信息的定义。 C)网页上的超链接只能指向外部的网络资源,本网站网页间的联系通过设置标签来实现。 D)点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符(URL)请求网络 资源或者网络服务。 没有都统一编码 本网站页面也可以用超链接,就是绝对路径。也可以用相对路径。 6、若 3 个顶点的无权图 G 的邻接矩阵用数组存储为{{0,1,1}{1,0,1}{0,1,0}},假定在 具体存储中顶点依次为:v1,v2,v3 关于该图,下面的说法哪些是正确的:答案(ABD) A)该图是有向图。 B)该图是强联通的。 C)该图所有顶点的入度之和减所有顶点的出度之和等于 1。 D)从 v1 开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。 可以画出这个有向图,矩阵存储的时候,矩阵为非对称,故为有向图。 入度之和等于出度之和。 7、在带尾指针(链表指针 clist 指向尾结点)的非空循环单链表中每个结点都以 next 字段的 指针指向下一个节点 。 假定其中已经有了 2 个以上的结点 。 下面哪些说法是正确的 : 答案 (AC) A)如果 p 指向一个待插入的新结点,在头部插入一个元素的语句序列为: p^.next:=clist^.next;clist^.next:=p; B)如果 p 指向一个待插入的新结点,在尾部插入一个元素的语句序列为: p^.next:=clist;clist^.next:=p; C)在头部删除一个结点的语句序列为: p:=clist^.next;clist^.next:=clist^.next^.next;dispose(p); D)在尾部删除一个结点的语句序列为: p:=clist;clist:=clist^.next;dispose(p); B 应为 p^.next:=clist^.next;clist^.next:=p; D 中要循环找到尾指针的上一个元素才能进行删除 8、散列表的地址区间为 0-10,散列函数为 H(K)=K mod 11。采用开地址法的线性探查法处 理冲突,并将关键字序列 26,25,72,38,8,18,59 存储到散列表中,这些元素存入散 列表的顺序并不确定。假 定之前散列表为空,则元素 59 存放在散列表中的可能地址有:答 案(ABC)
15

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

A)5

B)7

C)9

D)10

选择 ABCD 哈希函数的冲突避免 计算各个的散列值 26 25 72 38 8 18 59 5 4 6 5 8 7 4 这样就可能 5 的顺序:25、59…… 7 的顺序:25、26、38、59…… 9 的顺序:25、26、38、18、59…… 10 的顺序:……59 上面的顺序不是唯一的。 9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变,下列哪些排序 算法是稳定的:答案(ABCD) A)插入排序 B)基数排序 C)归并排序 D)冒泡排序 在编程实现的时候,只要控制好边界都是可以达到稳定排序的。 10、在参加 NOI 系列竞赛过程中,下面哪些行为是被严格禁止的:答案(BCD) A)携带书写工具,手表和不具有通讯功能的电子词典进入赛场。 B)在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。 C)通过互联网搜索取得解题思路。 D)在提交的程序中启动多个进程以提高程序的执行效率。 A 有时候是可以的。这里考的是 NOI,不是 NOIP。 三.、问题求解(共 2 题,每空 5 分,共计 10 分) 1.拓扑排序是指将有向无环图 G 中的所有顶点排成一个线性序列,使得图中任意一对顶点 u 和 v,若<u,v>∈E(G),则 u 在线性序列 中出现在 v 之前,这样的线性序列成为拓扑序列。 如下的有向无环图,对其顶点做拓扑排序,则所有可能的拓扑序列的个数为__432____。

用排列组合,先确定 12346 的顺序,然后将 7 插入内部有两个位置可选(可将 7 放在 4 钱前或 4 后) ,然后将 5 插入时候(如在 123476 中插入 5,五应在 1 的后面就可以,则有 6
16

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

种情况,当然在 123746 中也一样) ,可以有 6 个位置选择。最后,放 89 的时候,考虑两种情 况,89 在一起,有 8 个位置选(可放在 1 前或者 1 的后面都可以) ;89 不在一起,8 个位置 选 2 个。 C(2,1)×C(6,1)×[C(8,1)+C(8,2)]=2×6×(8+28)=432

2、某个国家的钱币面值有 1,7,7^2,7^3 共计四种,如果要用现金付清 10015 元的货物, 假设买卖双方各种钱币的数量无限且允许找零,那么交易过程中至少需要流通____35__张钱 币。 可以判断用 29 张 7^3 的钱,用一张 7^2 的钱,此时还剩余 19 元,可用 2 张 7 元的和五 张一元的解决, 但这时一元用的太多我们可以给对方一张七元的让对方找两张一元的就可以, 这样只用到 29+1+2(七元)+1(七元)+2(一元)共 35 张,而第一种方法需要更多一些 10015 化成 7 进制数是 41125,正常是 4× 7+1=29 张 7^3 面额的,1 张 7^2 面额,2 张 7 面 额的,5 张 1 面额的。 因为可以无限且找零,并要求最少流通数量。这样就把 7 进制上大于等于 4 的数 a,用找 零 7-a 的方法代替,这样就能达到最少。 这里 29、1、2、5 中只有 5 是大于 4 的,所以用一张大额的,并 7-5 找零的方法计算。 这样,总数 29+1+2+(1+7-5)=35 张。

四、.阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. 输出:__3___ 2. 输出:__5850____ 3. 输出:___487___ 4. var n,m,i,j,k,p:integer; a,b:array[0..100]of integer; begin read(n,m); a[0] := n; i := 0; p := 0; k := 0; repeat for j := 0 to i - 1 do if a[i] = a[j] then begin
17

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

p := i; k := j; break; end; if p <> 0 then break; b[i] := a[i] div m; a[i+1] := (a[i] mod m) * 10; inc(i); until a[i] = 0

NOIP2008 年提高组(Pascal 语言)参考答案与评分标准
一、单项选择题: (每题 1.5 分) 1. C 6. D 2. A 7. D 3. B 8. E 4. C 9. B 5. B 10. C

二、 不定项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题正确答案的个 数大于或等于 1。多选或少选均不得分) 。 11. ABD 16. ABD 1.7 1. 23 (信心题) 2. 1,3,2 (简单递归) 3. 132/213/231/312/321/ (全排列) 4. defghijxyzabc/hfizxjaybcccc (字符串替换) 五.完善程序 (前 6 空,每空 3 分,后 5 空,每空 2 分,共 28 分) 12. AC 17. BCD 13. BC 18. ABC 2.3060 14. B 19. ACD 15. ABC 20. ABCD

三、问题求解: (共 2 题,每题 5 分,共计 10 分) 四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分)

(说明:以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上 机验证,不一定上报科学委员会审查)

18

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

1. ① a[left] ② a[j] < value (或 a[j] <= value) ③ a[i] > value (或 a[i] >= value) ④ a[i] := value; ⑤ i,right,n ⑥ FindKth(left, i, n) 2. ① inc(j); (或者 j := j+1;) ② a[i,j] > k ③ a[i,j] < k ④ answerx := i; ⑤ answery := j;
NOIP2007 年(第十三届)提高组(Pascal 语言)参考答案 一、单项选择题 1. D 2. E 3. D 4. B 5. A 6. B 7. D 8. B 9. D 10. A 二、 不定项选择题 11. ABC 12. AD 13. ABD 14. ABD 15. BC 16. ABD 17. AB 18. CD 19. BC 20. AC 三、问题求解 1.350 2.289 四、阅读程序写结果 1 129,43 2 No.1:3,6 No.2:3,6 3 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 4 No.1: XTORSEAAMPLE No.2: AAEELMOPRSTX 五、完善程序 (前 5 空,每空 2 分,后 6 空,每空 3 分,共 28 分) (说明:以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上机验证,不 一定上报科学委员会审查) 1 ① bound*2 ② exit ③ j:=0 ④ (j mod b-(b div 2))=0 ⑤ downto 1 2 ① x[i-2]*(m-1) ② j+x[i-1]*k ③ j+x[i-1]*k (同 2) ④ r-1 ⑤ x[i-1]+1 ⑥ backtrace(i+1,r)

19

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

NOIP2006 年(第十二届)提高组(Pascal 语言)参考答案 一、单项选择题 1. E 2. C 3. D 4. E 5. C 6. E(满分) 7. C 8. B 9. A 10. B 二、 不定项选择题 11. ABC 12. AB 13. C 14. BC 15. ABCD 16. AD 17. CD 18.AB 19. BD 20. (满分,空白 0 分) 三、问题求解 1. 401 2. 9! (或 362880) 四、阅读程序写结果 1、 -13,57 (对 1 个数给 4 分,无逗号扣 1 分) 2、 6 28 496 8128 33550336 (前 2 个对 1 个数给 1 分,后 3 个对 1 个数给 2 分) 3、 11 4、6 2 5 4 3 7 9 9 7 3 4 5 2 6(数字之间无空格扣 2 分) 五、完善程序(前 5 空,每空 2 分,后 6 空,每空 3 分) 1.① j=k (或 k=j) ② p:=1 to k ③ perm2(j+1) ④ a[j]:=a[i];a[i]:=t ⑤ perm2(1) 2.① a1[i]:=a2[i];a2[i]:=t ② kz1[i]:=1;kz2[i]:=1; ③ kz1[i]:=0;kz2[j]:=0; ④ (a1[j]=a1[i])and(kz1[j]=-1) ⑤ (a2[j]=a2[kj])and(kz2[j]=-1) ⑥ cross(a1,a2,t1,t2,n) NOIP2005 年(第十一届)提高组(Pascal 语言)参考答案 一、单项选择题 1. B 2. A 3. D 4. E 5. D 6. E 7. E 8. B 9. A 10.C 二、 不定项选择题 11. CDE 12. BCE 13. BC 14. CE 15. BCE 16. B 17. ACD 18. BCDE 19. ABCDE 20. BDE 三、问题求解 1. 5 2. 11011 四、 阅读程序 1.-7452 2.3223 3.Zzzaaabbbcccy 4.31 五、 完善程序 (前 5 空,每空 2 分,后 6 空,每空 3 分,共 28 分) 1.(1)num + len[i] div t (2)num >= k (3)eft := 0 (4)left + 1 (5)not isok(mid) (或者 isok(mid) = false) 2.(1)getcom := 1 (2)getcom(x - 1, y - 1) (3)s + t - p + 1 (4) inc(t) (或者 t := t + 1) (5)sum (6)1, len, NOIP2004 年(第十届)提高组(Pascal 语言)参考答案 一、单项选择题 1. A 2. D 3. E 4. C 5. B 6. B 7. C 8. D 9. C 10.A 二、 不定项选择题 11. BC 12. ACDE 13. BCD 14. D 15. AC 16. BE 17. ADE 18. ACD 19. ABDE 20. BCE 三、问题求解 1. 10 2.a b d f g e c 四、 阅读程序
20

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

1. 263 2.328 3. 1 4 2 1 3 3 4.-400 五、 完善程序 (前 5 空,每空 2 分,后 6 空,每空 3 分,共 28 分) 1.(1)start+m-1 (2)result>=k (或者 k<=result) (3)not find (或者 find=false) (4)2*k-i (5)m-1 2. (1) 0,-1 (2)a[x-1,y-1] (3)a[x-1,y-1] (4)d[2*i+1] (5)a[x1,y1]=orig (或者 orig=a[x1,y1]) (6)orig:=a[i,j] NOIP2003 年(第九届)提高组(Pascal 语言)参考答案 一、单项选择题 1. B 2. B 3. D 4. A 5. B 6. B 7. C 8. E 9. C 10.B 二、 不定项选择题 11. D 12. BDE 13. AD 14. AB 15. AC 16. E 17. B 18. BCD 19. D 20. BE 三、问题求解 1.11 2.4 四、 阅读程序 1. 8910 2.126 3. 1872 4. 1 1 2 4 5 1 1 3 9 (空格分隔) 五、完善程序 1.(1)2 (2)i*m (3)t=2*m (4)(t*2) mod d (5)m>0 (6)solve(m) 2. (1) m[0,k,s-1]+m[1,k,s-1] (2)h:=y (3)k-1,s+1,nth (4)i:=i+1 (5)2*i,0,nth NOIP2002 年(第八届)提高组(Pascal 语言)参考答案 一、单项选择题 1. C 2. A 3. D 4. A 5. C 6. B 7. B 8. D 9. A 10.D 11. C 12. B 13. C 14. B 15. C 16. B 17. C 18. B 19. C 20. B 二、问题求解 1. 44 2. (k-1)*nk+1 三、看程序写结果 1. RRRRWWBBBB 2. 30031 3.[五个空格] 15.00 四、完善程序 1.(1)c[n+1] (2)c[j1+1]>yu+d[j1] (3)yu:=yu+d[j1]; (4)e[j0]:=s (5)Write(e[i]:4) (场宽不同亦可) 2. (1) p and b[0]=0 (2)b[j]:=1; (3)p:=false; (4)(a[[i,j]=-1] and (b[j]=1) (5)p (要写 p=true 也可以啦) NOIP2001 年(第七届)提高组(Pascal 语言)参考答案 一、单项选择题 1. A 2. D 3. B 4. D 5. C 或 D 6. D 7. A 8. A 9. A 10.A 11. A 12. C 13. C 14. B 15. B 16. B 17. B 18. C 19. B 20. D
21

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

二、问题求解(5+7 分,两题共 12 分) 1.二叉树先序遍历的顺序为:ABCEGDFHIJ 2.能组成 2250 个不同四边形 三、阅读程序,写出程序的正确运行结果(4+7+8+9=28 分) 1.125 2.181 110 87 86 66 62 61 60 3.1348 4.153 四、根据题意,将程序补充完整 1.(1)SP:=SP+1 (2)I:=I-1 (3)DK[I,2]+L+DK[I+1,2] (4)D (5)DK[I+1,1] 2. (1) REDLN(X,Y,W) (2)R[I,J]+EET[J]>MAX (3)ET[N]:=EET[N]; (4)ET[J]-R[I,J]<MIN (5)EET[I]=ET[I] NOIP2000 年(第六届)提高组(Pascal 语言)参考答案 一、单项选择题 1. C 2. B 3. D 4. C 5. D 6. B 7. D 8. B 9. A 10.C 11. B 12. B 13. D 14. C 15. A 16. D 17. B 18. D 19. C 20. A 二、问题求解 1、5 棵。如下: a b a c c \ /\ \ / / b a c c a b \ / \ / c b b a 2、F(N)=F(N-1)+F(N-2)+F(N-3) (N>=4 ,F(1)=1 F(2)=2 F(3)=4) 三、输出结果 1.4 3 0 2 2.BBAC 四、程序填空 1.(1)A[J]:=1; (2)A[I]:=0; (3)S:=0; (4)B[S]:=1; (5)S=32 2. (1) SP1<=SP2 (2)Q[SP1,0]+1 (3)Q[SP1,J]<>0 (4)(Q[SP2,0]); (5)D[Q[I,0]]+1; NOIP1999 年(第五届)提高组(Pascal 语言)参考答案 一、单项选择题 1. C 2. B 3. C 4. C 5. C 6. D 7. B 8. C 9. C 10.A 11. D 12. B 13. A 14. C 15. B 16. A 17. D 18. D 19. B 20. B 二、问题求解 Ln=n(n+1)/2+1(n≥0) Zn=L2n-2n=2n2-n+1 三、阅读程序,并写出正确的程序运行结果 1.程序运行的结果:970 2. (1)调用该过程的语句为 SORT1(N) ;比较运算的次数为:n(n-1) (2)调用该过程的语句为 SORT2(N) ;比较运算的次数为:n(n-1)/2
22

福建省莆田第一中学 信息学奥赛兴趣小组

整理:林梓雨

(3)调用该过程的语句为 SORT3(N) ;比较运算的次数为:nlog2n+c 四、根据题意,将以下程序填写完善 (1)共 15 分(2+2+3+2+2+2+2=15 分) ① sp1<=sp2 ② p:=p+1 ③ g[sp1,j]<>0 ④ sp2:=sp2+1; ⑤ sp1:=sp1+1 ⑥ k=g[i,2] ⑦ j:=1; (2)共 15 分(每个点 3 分) ① a[i]:=i; ② 1 to s ③ a[j-1]>a[j] ④ (a[i1]>a[j-1]) and (a[i1]<a[k]) ⑤ a[i1]>a[k]

23


推荐相关:

NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考答案

NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考答案_学科竞赛_高中教育_教育专区。NOIP2013第十九届信息学奥赛提高组答案NOIP2013第十九届全国青少年信息学奥林...


第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:2...


2013第十九届全国青少年信息学奥林匹克联赛初赛提高组(C++)

2013 第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:2013 年 10 月 13 日 14:30~16:30 选手注意:试题纸共有 12 页,答题纸共有 ...


2011年第十七届信息奥林匹克初赛提高组pascal 附答案

信息奥林匹克初赛提高组pascal 附答案_其它课程_...举例说明, 对于字符串"BCA", 可以将A移B之前,...1999年—2011年信息学奥... 116页 2下载券 第七...


2015年第二十一届全国青少年信息学奥林匹克联赛提高组初赛试题(C++)

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


第十四届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组PASCAL)

第十四届全国青少年信息学奥林匹克联赛初赛试题答案(提高组PASCAL)_初三英语_英语_初中教育_教育专区。第十四届全国青少年信息学奥林匹克联赛初赛试题答案(提高组PA...


NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组试题及答案PASCAL)

第二十届全国青少年信息学奥林匹克联赛初赛提高组 Pascal 语言试题 竞赛时间:2014 年 10 月 12 日 14:30~16:30 选手注意: ● 试题纸共有 10 页,答题纸共...


NOIP2014信息学奥赛全国联赛提高组参考答案

104页 1下载券 noip2014提高组初赛答案 1页 免费 第十四届信息学奥赛联赛... 15页 1下载券 1999年至2013年历年信息... 124页 2下载券©...


第十七届全国青少年信息学奥林匹克联赛提高组初赛试题_

第十七届全国青少年信息学奥林匹克联赛初赛试题( 提高组●● C 语言 两小时完成 )●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 一、单项选择题 ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com