信息学奥赛选拔试题

信息学奥赛试题

一、填空题（共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

目 录

青少年信息学奥林匹克竞赛情况简介 ................. 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

数据结构

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

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

基础题：

【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

泰安市实验学校

第五届全国青少年信息学计算机奥林匹克分区联赛初赛试题（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．计算机能直接执行的指令包括两部

第1~10题为基础题，第11~20题为提高题，第21~33为综合题

注：因为在本文档中需要用到一些特殊的数学符号（如：求和号、分数等），所以当您在百度文库中浏览时，一些数学符号可能会显示不出来，不过当您把本文档下载下来在本地浏览时，所有的符号即可全部都显示出来。^_^

基础题：

【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‥22

（PASCAL版 试卷）

2011年义乌市信息学奥林匹克竞赛

初 赛 试 题

（小学组 PASCAL语言 二小时完成）

●●全部试题答案都要求写在答卷纸上，写在试卷上一律无效●●

一．选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题2分，每题只有一个正确答案，多选无分。共30分）

1）我国一位“两院”院士、著名科学家开发汉字激光照排系统并形成产业，取代沿用了上百年的铅字印刷，推动了我国报业和出版业的跨越式发展，被誉为“当代毕昇”。这位科学家是（ ） A) 黄昆

B) 周以真

C) 李开复

D) 王选

2）2009年我国国防科技大学研制成功千万亿次超级计算机，在国际组织公布的名单中，该计算机位居超级计算机全球排名前五、亚洲排名第一。该计算机的名字是（ ） A) 曙光4000

B) 魔方

C) 天河一号

D) 曙光5000

3）下列计算机设备中，断电后其中的信息全部消失的是（ ） A) CPU

B) RAM

C) ROM

D) 优盘

4）在pascal中，“SHL x”命令的作用是将一个数对应的二进制数各位置上的数字左移x个位置，末尾新位置用零补充。如对二进制数（01100011）2执行“SHL 1”

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第1页

程序设计试题及答案

（备注：试题难度评价采取五★级评价体系，分基础、容易、一般、稍难、难五个等级，其中的一、二、三★级都属于程序设计的基础试题级别，同学们稍加思考均有能力求得正确解答，对于四★级试题属于程序设计试题基础级别的思考题，五★级难度试题在此没有涉及，在程序设计高级试题中另行讲解。对于基础和容易两个级别的程序设计试题，若能够给出语句分类（如If条件语句、条件语句嵌套、循环语句、多重循环语句等）的将尽量给出。若属于13大类别的将尽量标注。） 程序设计试题几大分类：

1、 素数类问题（求素数的几种算法）： 2、 数据排序问题（数据排序的几种方法）： 3、 最大公约数和最小公倍数问题（几种算法）：

4、 公式求解类问题（如求圆周率π、自然常数e、解方程等等）： 5、 编号相反处理问题：

6、 约瑟夫问题（或猴子选大王问题、密码问题）： 7、 回文数问题：

8、 高精度数值计算问题： 9、 数值计算问题： 10、 进制相互转换问题： 11、 字符串倒置问题： 12、 排列与组合类问题： 13、 因子、质因子（质因数）类相关问题：

答案部分：

（程序设计的源程序没有统一的标准

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第1页

程序设计试题及答案

（备注：试题难度评价采取五★级评价体系，分基础、容易、一般、稍难、难五个等级。

其中的一、二、三★级都属于程序设计的基础试题级别，同学们稍加思考均有能力求得正确解答。

对于四★级试题属于程序设计试题基础级别的思考题.

五★级难度试题在此没有涉及，在程序设计高级试题中另行讲解。对于基础和容易两个级别的程序设计试题，若能够给出语句分类（如If条件语句、条件语句嵌套、循环语句、多重循环语句等）的将尽量给出。若属于13大类别的将尽量标注。）

程序设计试题几大分类：

1、素数类问题（求素数的几种算法）： 2、数据排序问题（数据排序的几种方法）： 3、最大公约数和最小公倍数问题（几种算法）：

4、公式求解类问题（如求圆周率π、自然常数e、解方程等等）： 5、编号相反处理问题：

6、约瑟夫问题（或猴子选大王问题、密码问题）： 7、回文数问题：

8、高精度数值计算问题： 9、数值计算问题：

10、 进制相互转换问题： 11、 字符串倒置问题： 12、 排列与组合类问题：

13、 因子、质因子（质因数）类相关问题：

答案部分：

（程序设计的源程序没有统一的标准答案，实现程