信息奥赛

目 录

青少年信息学奥林匹克竞赛情况简介 ................. 5 第一章 计算机基础知识 ........................... 7

1.1 计算机的基本常识 .................................................................................................................. 7

1.1.1 计算机的产生与发展 ..................................................................................................... 7 1.1.2 计算机系统及工作原理 ................................................................................................. 7 1.1.3 计算机中有关数及编码的知识 ......................................................

信息学奥赛辅导资料

湖南省桂阳三中信息组

目 录

1、数据结构基础知识……………………2 2、动态规划………………………………17 3、分支限界………………………………19 4、分治策略………………………………21 5、排序算法………………………………28 6、贪心算法………………………………45 7、计算机基础知识练习题………………51 8、附录——基础知识练习题参考答案…78

1

数据结构

数据结构是计算机专业基础课程之一，是十分重要的核心课程。计算机的所有系统软件和应用软件都要用到各种类型的数据结构。要想更好地运用计算机来解决实际问题，仅仅学习计算机语言而缺乏数据结构知识是远远不够的，而打好“数据结构”这门课程的扎实基础，对于学习计算机机专业的其他课程都是十分重要的。

随着计算机应用领域不断扩大，非数值计算问题占据了当今计算机应用的绝大多数，简单的数据类型已经远远不能满足需要，各数据元素之间的复杂联系已经不是普通数学方程所能表达的。因此，掌握好数据结构方面的知识，对于提高我们解决实际问题的能力将会有莫大的帮助。实际上一个好的程序无非是选择一个合适的数据结构和好的算法，而好的算法的选择很大程度上取决于描述实际问题

信息学奥赛试题

一、填空题（共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。

1.微型计算机的性能主要取决于（ ）。

A） 内存 B） 主板 C） 中央处理器 D） 硬盘 E） 显示器 2.能将高级语言程序转换为目标程序的是( ).

A）调试程序 B）解释程序C）编辑程序 D）编译程序E）连接程序 3．A=11001010B,B=00001111B,C=01011100B,则A∨B∧C=( )

A）01011110 B） 00001111 C）01011100 D） 11001110 E) 11001010 4.计算机设备，既是输入设备，又是输出设备的是( )。 A)键盘 B)触摸屏 C)扫描仪 D)投影仪 E)数字化仪 5.计算机病毒传染的必要条件是( ) 。

A) 在内存中运行病毒程序 B) 对磁盘进行读写操作

C) 在内存中运行含有病毒的可执行程序 D) 复制文件 E)删除文件

6．已知队列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入队列的元素是13

信息学奥赛测试题

一、装球：设有N个盒子（N足够大，可装入任何数量的球），分别编号1，2，…，同时有K个小 （K＞0），今将K个小球装入到盒子中去，装入规则如下：

1、第一个盒子不能为空。

2、装入必须严格按递增的顺序进行。 例如，当K=8，N=6装入方法有：

1，2，5或1，3，4

3、在满足上面的两个条件下，要求有球的盒子尽可能多。 4、装完之后，相邻盒子中球个数差的绝对值之和为最小（未装的盒子不计）。

如上例中：

装入法1，2，5则差的绝对值之和为：2－1＋5－2=4 装入法1，3，4则差的绝对值之和为：3－1＋4－3=3

二、读入N个不相同且不为0的数（1≤N≤100），不用排序，求出其中第R个大的数（1≤R≤N），即有R－1个数比它大，其余的数都比它小。

例如：输入3，14，22，15，17，6其中第3个大的数为15。 三、输入2个整数K，N，将K分成N个全不相同的整数，并使此

N个整数的乘积为最大。

四、输入N和一组整数（以0结束），N表示编号1，3…，N的箱子，一组整数表示零件的重量（单位为G）。现要求将一批零件，分别装入编号为1，2，…，N的N只箱子中去，装入的方法是：

0G＜零件重量＜100G 装入1号箱 100G

泰安市实验学校

第五届全国青少年信息学计算机奥林匹克分区联赛初赛试题（1999年）

一．选择一个正确答案代码(A/B/C/D)填入每题的括号内 （每题1．5分，多选无分，共30分） 1．微机内的存储器的地址是按（ ）编址的。 A.二进制位 B.字长C.字节 D.微处理器的型号 2.下列诸因素中，对微机工作影响最小的是（）． A.尘土 B.噪声 C.温度 D.湿度

3.在24*24点阵字库中，汉字’一’与’编’的字模占用的字节数分别是（）． A.32,32 B.3Z,72 C.72,72 D.72,32

4.将 DOS系统盘插人 A驱动器启动机器随后使用一批应用软件．在此过程中， DOS系统盘（ ）． A. 必须始终插人在A驱动器中B.不必再用

C.可能有时要插人A驱动器中D.可能有时要插入B驱动器中 5. 以下dos命令有可能在磁盘上建立子目录的是（ ） A type B．dir C．xcopy D．cd

6．在CONFIG．SYS文件中，装入特定可安装设备驱动程序的命令是（）． A. buffer B flies C. driver D． device

7．计算机能直接执行的指令包括两部

我们首先说华杯赛。华杯赛的全称是华罗庚金杯少年数学邀请赛，主办方包括一些权威学术机构和政府部门，组委会包括众多全国闻名的数学权威，王世坤教授、朱华伟教授、余其煌教授、周春荔教授、陶晓永教授等知名专家均在其中，所以华杯赛的试题水平在各大杯赛中一直稳居前列。

华杯赛分为初赛、决赛、总决赛，小升初的时候大家所说的“双一”的一个“一”指的就是华杯赛成都赛区决赛一等奖。所以得到了很多家长的青睐。每年华杯赛约12月开始报名，三月初赛，四月决赛，四月底的时候就会出成绩。华杯赛获奖人数与参赛人数有关，不超过参赛人数的30%进入决赛，决赛人数的36%获奖，其中前6%获得一等奖，其余的前12%获二等奖，其余的18%获三等奖。成都每年大约300名优秀同学获得华杯赛一等奖，600名同学拿下二等奖。

在成都所说的“双一”中另一个一就是指的国奥赛，国奥赛全称为全国小学数学奥林匹克竞赛，与世界上规模和影响最大的中学生数学学科竞赛：国际奥林匹克数学竞赛（简称IMO)不是同一个比赛，很多家长朋友容易把这个搞混淆，哈哈。国奥赛分为初赛和

决赛，一般年底开始报名，三月初赛，四月决赛，比赛时间和华杯赛接近，但是近年来国奥赛的报名和比赛均比华杯赛早一个星期，请各位家长朋友放

2011暑季四年级初赛

（本试卷满分100分，考试时间90分钟）

一、填空题（5分×12＝60分）

1、2011×64＋2011＋35×2011＝ 。

2、在下面的方格中填上同一个数，使等式成立。 □＋□－□×□÷□＝20

3、喜羊羊去羊村超市买了一杯益生菌纯酸奶，喝一半后用水加满；又喝了一半，用水加满；再喝一半，再用水加满；第四次再喝一半，再用水加满，最后他全部喝完。喜羊羊一共喝了 杯益生菌酸奶， 杯水。

4、护士为病人每1小时量一次体温，做第五次测量时，时钟时针指向数字11，那么量第一次时，时针指向数字 。

5、要在一个水池周围种树，已知这个水池周长为255米，计划要栽51棵树，相邻两树之间距离相等。那么相邻两树之间相距是 米。

6、 北京火车站，上站台有载货电梯2部，自动电梯2部，观光电梯3部。那么上站台有 种不同的走法。

7、大正方形和小正方形拼成的图形如下图。小正方形的边长是4厘米，阴影部分的面积是28平方厘米。空白部分的面积是 。

8、张莉参加世界奥林匹克数学竞赛夏季联赛，共有10道题，每做对一题得8分，每做错一题倒扣5分，张莉最

算法在信息学奥赛中的应用 (基础篇)

学习过程序设计的人对算法这个词并不陌生，从广义上讲，算法是指为解决一个问题而采用的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计语言的各种语句，为解决特定的问题而构成的各种逻辑组合。我们在编写程序的过程就是在实施某种算法，因此程序设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂，一个好的程序必须有一个好的算法，一个没有有效算法的程序就像一个没有灵魂的躯体。

算法具有五个特征：

1、有穷性： 一个算法应包括有限的运算步骤，执行了有穷的操作后将终止运算，不能是个死循环；

2、确切性： 算法的每一步骤必须有确切的定义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。如在算法中不允许有“计算8/0”或“将7或8与x相加”之类的运算，因为前者的计算结果是什么不清楚，而后者对于两种可能的运算应做哪一种也不知道。

3、输入：一个算法有0个或多个输入，以描述运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。如在5个数中找出最小的数，则有5个输入。

4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法设

1．已知，按中序遍历二叉树的结果为：abc

问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。

2．有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。 此时用一个1×2的骨牌铺满方格，共有3种铺法：

试对给出的任意一个n（n>0），求出铺法总数的递推公式。

3．设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1,1+2,2+1,3。

4.在a,b,c,d,e,f六件物品中，按下面的条件能选出的物品是： (1)a,b两样至少有一样 (2)a,d不能同时取 (3)a,e,f中必须有2样

(4)b,c要么都选，要么都不选 (5)c,d两样中选一样

(6)若d不选，则e也不选

5.平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？

6.已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA

基础题：

【1 Prime Frequency】

【问题描述】

给出一个仅包含字母和数字（0-9, A-Z 以及 a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。 输入：

输入的第一行给出一个整数T ( 0

对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。这些字符按字母升序排列。所谓“字母升序”意谓按ASCII 值升序排列。如果没有字符的频率是素数，输出“empty”（没有引号）。 样例输入 3 ABCC AABBBBDDDDD ABCDFFFF 注：

试题来源：Bangladesh National Computer Programming Contest 在线测试：UVA 10789

样例输出 Case 1: C Case 2: AD Case 3: empty 提示

先离线计算出[2‥2200]的素数筛u[]。然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u[p[i]]=1且ASCLL码值为i的字符）。若没有频率为素数的字符，则输出失败信息。

【2 Twin Pr