2013年山东省信息学奥赛夏令营提高一树及其应用练习题目

第一篇：2013年山东省信息学奥赛夏令营提高一树及其应用练习题目

树及其应用上机练习题目

1.FBI树(fbi)

【问题描述】

我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：

（1）T的根结点为R，其类型与串S的类型相同；

（2）若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。

现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。

【输入文件】

输入文件fbi.in的第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2N的“01”串。

【输出文件】

输出文件fbi.out包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。

【样例输入】

10001011

【样例输出】

IBFBBBFIBFIIIFF

【数据规模】

对于40%的数据，N <= 2；

对于全部的数据，N<= 10。

2.树的遍历(tree)

【问题描述】

我们都知道二叉树的后序遍历，即对于节点i，先访问它的左儿子，再访问它的右儿子，最后输出它本身。我们对其稍加改动：对于节点i，先访问它的右儿子，再访问它的左儿子，最后输出它本身。给你一棵有序的二叉树（亦即，每个节点的值严格大于它左子树的节点的值，严格小于它右子树的节点的值）的后序遍历，请你输出它的“右-左-中”遍历。

【输入】

第一行是一个整数n，表示节点个数。

第二行有n个数，表示一个n个节点的有序的二叉树的后序遍历的数值。

【输出】

输出文件仅包含一行，有n个整数，表示这个二叉树的“右-左-中”遍历。

【样例输入】

5 21 22 27 25 20 10

【样例输出】21 22 25 20 7 1 5 10

【样例说明】

【数据规模和约定】

对于30%的数据，n<=100

对于100%的数据，n<=200000，所有节点数值不超过maxlongint且互异。

3.合并果子(fruit.pas)

【问题描述】

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

【输入文件】

输入文件fruit.in包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。

【输出文件】

输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。

【样例输入】2 9

【样例输出】

【数据规模】

对于30％的数据，保证有n<=1000：

对于50％的数据，保证有n<=5000；

对于全部的数据，保证有n<=10000。

第二篇：信息学奥赛练习8

信息学奥赛练习8

I8-1 用素数表求孪生素数

如果自然数N是素数，N+2也是素数，则称它们为孪生素数。如:3—55—711—13 编程求10000以内的孪生素数

I8-2 求费尔马“二平方”素数

除了2这个特别的素数外，所有的素数都可以分为2类：第一类被4除余1，如5，41；第二类被4除余3，如3、43。第一类素数都能表示成两个整数的平方和的形式，第二类则不能，这就是著名的费尔马“二平方”定理。

我们起名叫做费尔马“二平方”素数，即一个素数能够表示成两个素数的平方和的形式。如: 13=2*2+3*329=2*2+5*5

编程求10000以内的费尔马“二平方”素数

I8-3 回文式素数

有些回文数同时还是素数，如11，101，757，10301，98689，就叫做回文式素数。编程求1000以内的回文式素数。

I8-4 反序猜想：

任意的一个正整数，将其反序（高低位交换），与原来的整数相加，得到新的整数后重复以上步骤，最终可以得到一个回文数，这就叫做回文数反序猜想。

例如：291：291+192=483483+384=867867+768=16351635+5361=6996 6996是回文数，经过了4步

编程验证回文数反序猜想。

第三篇：第十九届信息学奥赛复赛题目

一、基础知识（每小题5分，共20分）

1、结构化程序设计所规定的三种基本控制结构是（C）

A．输入、处理、输出B．树型、网型、环型

C．顺序、选择、循环D．主程序、子程序、函数

2、Windows中所指的剪贴板就是（D）中的一块区域。

A．高速缓存B.光盘C.硬盘D.内存

3、电脑工作时，断电后，保存在（C）中的信息不会丢失。

A．ROM和RAMB.CPUC.ROMD.RAM4、算式1*2*3*4*5*„„*39*40的结果（A）被37037整除。

A．能B.不能

二、编程题（共80分）

1、有一个等差数列，它的前四项之和为26，之积为880，输出它的前20项。

答案：

CLS

FOR i1 = 1 TO 6

FOR n = 1 TO 5

i2 = i1 + n: i3 = i2 + n: i4 = i3 + n

IF i1 + i2 + i3 + i4 = 26 AND i1 * i2 * i3 * i4 = 880 THEN GOTO 10

NEXT n

NEXT i1FOR i = 1 TO 20

PRINT i1,i1 = i1 + n

NEXT i

END2、数学上有一个称为“角谷猜想”的经典题目：对于一个任意的正整数n，如果n为偶数，则把它除以2，如果n为奇数，则把它乘3再加上1。依此类推，当经过有限次的这种运算后，总可以得到正整数1。

输入n>=2和n<=2013的正整数，键盘输入n，还要输出运算过程。例如：

N=5

5*3+1=16

16/2=8

8/2=4

4/2=2

2/2=1

答案：

CLSINPUT “n=”;n

IF n < 2 OR n > 2013 THEN PRINT “Data error!”: GOTO 10 20 IF n MOD 2 = 0 THEN

PRINT n;“/2=”;

n = n / 2

PRINT n

DO: LOOP WHILE INKEY$ = “"

ELSE

PRINT n;”*3+1=“;

n = n * 3 + 1

PRINT n

DO: LOOP WHILE INKEY$ = ”“

END IF

IF n > 1 THEN 20

END3、用0—9这十个自然数分别组成一个一位数、两位数、三位数和四位数。并且要求这些数都是一个整数的平方，输出所有符合条件的数。每两个数之间用“，”隔开。

答案：

CLS

DIM a(10)

FOR i = 1 TO 3

FOR j = 4 TO 9

FOR k = 10 TO 31

FOR l = 32 TO 99

s1 = i * i: s2 = j * j: s3 = k * k: s4 = l * la(1)= s1

a(2)= s2 10: a(3)= s2 MOD 10

a(4)= s3 100: a(5)=(s3 10)MOD 10: a(6)= s3 MOD 10

a(7)= s4 1000: a(8)=(s4 100)MOD 10: a(9)=(s4 10)MOD 10: a(10)= s4 MOD 10

FOR q = 1 TO 9

FOR w = q + 1 TO 10

IF a(q)= a(w)THEN 10

NEXT w

NEXT q

f = f + 1

PRINT f;”:“;s1;”,“;s2;”,“;s3;”,";s4 10 NEXT l, k, j, i

END

第四篇：山东省信息学奥赛活动的开展情况介绍

山东省信息学奥赛活动的开展情况介绍

立足普及迈向提高

全国信息学奥林匹克竞赛（National Olympiad in Informatics,NOI））是一项面向全国青少年的信息学竞赛和普及活动，旨在激发中学生在计算机科学和信息技术方面的兴趣，向中学生普及计算机科学知识，培养他们的逻辑思维能力，给那些有才华的学生提供相互交流和学习的机会，通过竞赛和相关的活动培养和选拔优秀的计算机后备专业人才，给中学的信息技术教育课程提供新的思路和可借鉴的经验，推动中学的信息技术教育。

近年来，我省的联赛成绩斐然，参赛人数连年稳居全国首位，获奖人数也逐年增多（2004年第四，2005年第五），竞赛的成绩也有较大的提高（十年来第一次进入国家集训队）。作为奥赛的组织者兼辅导教师，我的心得和感受如下：

1、做好奥赛活动的宣传工作。

信息学奥林匹克活动通过竞赛形式对有才华的青少年起到激励作用，促其能力得以发展；让青少年彼此建立联系，推动经验交流，给学校的这一类课程增加活力，是智力和能力的竞赛，注重考查全面素质和创造能力，是素质教育的大课堂，符合国家素质教育的要求，对于提高青少年的计算机科学素养、逻辑思维能力、以计算机为工具（算法和程序设计语言）提高解决实际问题的能力非常重要。

从2000年开始，我们先选取生源质量较好、有参与热情的地区和学校开展辅导和培训工作，如胜利油田一中、山东师大附中、山东省实验中学、山东寿光一中、山东淄博张店区实验学校等都是最早积极参加的学校。取得初步的成果后，再进一步加大宣传力度，吸引更多的地区和学校参与这项活动，逐步地以点带线、以线带面开展工作。现在已在全省的每个地市都有几所积极参加活动的学校，象青岛二中也是近三、四年刚开始积极参加的学校之一，2005年就有10人获联赛一等奖。现在有200多所学校参加了这项活动，全省17地市中有16个地市参加了这项奥赛活动。

由于宣传工作的到位，山东各重点中学对信息学奥赛有了更清楚的了解，对信息学奥赛的重要性也有了进一步的了解，所以普及面进一步扩大，近几年山东参加信息学奥赛的人数一直在7000多人，在全国各赛区中名列前矛。

2、抓奥赛辅导老师的培训

2001年第一次举办了山东省信息学奥赛辅导老师的培训班，参加人数60多人，并邀请了全国信息学奥赛著名教练王建德老师主讲，学员（本省奥赛辅导老师）作了辅导经验交流，取得了良好的效果。从2001年开始，在每年举办山东省信息学奥赛夏令营的同时，把奥赛辅导老师集合起来，做培训和交流活动，部分老师还兼学生的辅导老师，每次都有40多位老师参加，这项活动已深得学生和家长的欢迎。

在辅导和培训学生的同时，发现和培养具有一定的基础并有志于奥赛工作的一线中学教师，逐步形成一个培训团队（山东省信息学奥赛教练组，成员已达到10人），通过这样一个团队进一步开展辅导和培训工作。

2005年上半年承办了全国青少年信息学奥赛指导老师培训班，有近70多人参加了这次培训，其中山东就有近40人参加了这次培训，收到了良好的效果，提高了山东信息学奥赛指导老师的积极性和奥赛指导水平。

3、举办山东省信息学奥赛夏令营及其他培训与选拔活动

利用每年的暑假期，每年组织一次山东省信息学奥赛夏令营（培训班），全省规模的统一培训，两周左右的时间，分普及、提高、集训三个层次进行，讲授与上机练习相结合，同学之间的交流与师生之间的交流相结合，本省老师讲课与邀请全国各地老师讲课相结合，穿插模拟测试及题目讨论。这类活动对激发学生的兴趣、培养学生的能力、提高学生的素质非常有好处。

家长和学生对这项活动越来越感兴趣，2001年只有50多位同学参加，2002年就有80多位同学参加，2003年就有100多位同学参加，2004年就有200多位同学参加，2005年就有300多位同学参加，这项深得人心。

每年的五月份前后，组织山东省队选拔赛，同时进行一次短期培训，一周左右的时间，主要面向水平较高的学生。这项活动每次大约有50—80人参加，也邀请全国各地奥赛辅导老师讲课，对学生水平的提高非常有好处。

另外，还协助各地市开展定期或不定期的辅导和培训活动。

4、在培训内容和训练方式上，逐渐规范

在程序设计语言培训阶段：打好基础，培养学生良好的编程习惯，并逐步渗透相关的数学知识，注重启发和锻炼学生的逻辑思维能力和抽象思维能力。

在数据结构培训阶段：明确各种数据模型的特点和使用，加强选取合适数据模型的训练，同时逐步养成估算时间和空间复杂度的习惯。

在算法培训阶段：分析具体算法的精髓，配以相应的题目加以演练，使学生尽快把握算法的整体思路，再结合具体的题目对算法加以分析和总结，使学生加深对算法特点、适用范围等的理解。同时，提倡和鼓励学生之间的交流，取长补短，共同提高。

5、与其他省市的交流与合作

积极利用NOI、全国的冬令营等机会与兄弟省市同行包括辅导老师和学生交流切磋，学习借鉴他们的经验和做法。另外，连续多年邀请全国知名的奥赛教练王建德老师协助辅导教师的培训，并直接面向学生授课，特别是省队选拔及后期的集训，收到了显著的效果。

6、山东的组织管理模式

由山东省科协牵头，2000年成立了有山东省科协、山东省教育厅、山东省五个学科的学会（数学、物理学、化学、生物学、计算机等五个省级学会）参加的“山东省学科竞赛委员会”，监督五个学科奥赛的竞赛活动。信息学奥赛由山东省科协科普部具体组织，山东省计算机学会承担具体的业务与技术活动。计算机学会成立了奥赛专家组，有山东师范大学、山东经济学院、山东计算中心的部分教授组成，负责山东的信息学奥赛业务活动。

为了和其他四个学科奥赛的协调，加强山东省学科竞赛委员会的监督力度，2006年开始，山东省信息学奥赛的所有组织与业务活动

全部有山东计算机学会承担。山东计算机学会也成立了“山东省青少年信息学奥林匹克竞赛委员会”，专门负责山东省青少年信息学奥林匹克竞赛工作，由山东计算机学会理事长、山东大学曾广周教授担任主任。全国青少年信息学奥林匹克联赛的试题（和其他学科一样）仍由山东省科协统一保管，一直送到考试现场（考场）。山东省学科竞赛委员会可以监督五个学科奥赛的全过程。

奥赛辅导是一项工作，同时更是一项事业。目前我省已是一个NOI大省，我们将继续努力，争取早日成为一个NOI强省。

刘培玉liupy@sdnu.edu.cn***

山东师范大学计算机科学系主任、教授、博士生导师

NOI山东特派员、NOI山东队总教练兼领队

第五篇：千淘万漉虽辛苦,吹尽黄沙始到金—2018年江苏省信息学奥赛夏令营小组讨论交流活动

千淘万漉虽辛苦，吹尽黄沙始到金

——2018年江苏省信息学奥赛夏令营小组讨论交流活动

作者：金陵中学河西分校

朱学兴

2018年江苏省信息学奥赛夏令营于7月3日-10日在镇江扬中高级中学举行，全省各地共有900多名学生参加了本次夏令营活动。

信息学奥寒夏令营安排的时间正处于暑期开始，天气炎热，往年为减轻学生负担，往往白天安排听讲座、上机测试练习，晚间则在教室或宿舍自由复习。这样带来的结果是，学生轻松了，但大把的时间却浪费了，培训效率低下，不利于下半年参加全国联赛发挥最佳水平。

今年，为提高培训效率，推行精细化管理，大家经过充分讨论，对夏令营活动的组织架构、时间分配、目标设定、活动形式、成果反馈，特别是晚间时间管理进行了精细化设计。

我们从所有带队老师中挑选出责任心强的老师担任班主任，专门负责晚间学生的讨论学习。具体做法是：

1、带队老师自我申请，由营委会根据学生报名情况选定确认；

2、学生按地区、学校分成20个临时班，并安排好指定教室；

3、让班主任在班级里组织若干个2-6人的研讨小组；

4、每天讲座后，讲座老师预留3-5个讨论话题给学生；

5、每天晚上6：00-8：00在相应教室，由班主任组织学生分小组讨论交流当天的学习内容和话题；

6、要求班主任在小组讨论基础上进行小组分享，每天评选最佳小组，分享较好的小组最终推荐参加最后一天大组交流活动；

7、最后一天晚上由营委会组织全体学生进行大组交流活动，分享各班研讨学习成果。

今年，在营委会的指导下，在带队老师和教练员的大力支持下，大组交流活动取得圆满成功，学生参与热情高，分享内容丰富，远远超出我们当初的设想。原来预计一个半小时，因为大家交流讨论热烈，最后两个半小时才结束。我们深感，学生的创造力与想象力是无穷的，只要我们的组织者给他们找建好舞台，孩子们就能够给我们创造想象不到的奇迹。

通过这个活动，同学们学会了学习，学会了交流，学会了分享，同时在语言表述、心理调节、文字表达、分工协作、集体意识的培养等方面也得到了全面发展。

通过小组讨论，孩子们对知识点的理解更加深刻，对于同伴良好学习方法的体认更加到位，对于当天设置问题的解决更加高效，对于指导老师关键时刻画龙点睛的指导意义的领会更加准确。

小组沟通交流，让孩子们学会了与人真诚相处，学会了互帮互学，学会了分享经验、方法、成功与快乐。

通过小组讨论，分享交流发言，同学们学会了如何准备有条理的汇报，学会了用什么样的语言表达，学会了如何制作精美的PPT展示学习成果，学会了如何通过分工协作完成复杂的学习任务。

今年的夏令营活动，老师们付出了很多，学生们的收获更多。

每一棵大树的成长，都要经历风雨的洗礼；每一颗金子的闪光，都要经历千淘万漉的艰辛。为了把今天的懵懂顽童造就成明天的栋梁之材，我们愿意付出辛勤的汗水，因为我们所有老师的心里都有一个不变的信念：千淘万漉虽辛苦，吹尽黄沙始到金。