信息学奥赛五大算法

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

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

算法具有五个特征：

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

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

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

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

目 录

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

第1课 结构流程图

学习目标

1、进一步掌握流程图的概念与意义，会用流程图的方式表达算法的顺序及过程。 2、会用三种逻辑结构来进行流程图的设计 一、算法的三种重要结构是：

开始 （1）顺序结构：描述的是最简单的算法结构，语句

与语句之间，框与框之间是按从上到下的顺序进行的。

输入A、B、C、 （2）条件分支结构：它是依据指定条件选择执行不

x0、y0 同指令的控制结构。

（3）循环结构：根据指定条件决定是否重复执行一

z1=Ax0+By0+C 条或多条指令的控制结构。其中有两种类型的循环：

直到型（Until型）循环：如图（1），先执行A框，再判断给定的条件P是否为“假”。若P为“假”，则再z2=A2+B2 执行A框，如此反复，直到为“真”为止。

当型（While型）循环：如图（2）当给定的条件P

|z|d?1 成立时（“真”），反复执行A框操作，直到条件P为“假”

z2时才停止循环。

二、三种结构流程图练习

下列三个问题，应分别用哪种逻辑结构给出流程输出d 图？

1、已知点P(x0,y0)和直线l：Ax+By+C=0，写出求点P到直线l的距离d的流程图。

2、写出求一元二次方程ax2?bx?c?0的根的流程图。

3、已知n个正数排成一行如下：a

泰安市实验学校

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

信息学奥赛测试题

一、装球：设有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

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

煤

信息学奥赛初学练习题：

第一章：顺序结构练习题：重点掌握read,readln,write,writeln,场宽，小数位数和常用函数

1、输入三个字符，然后按输入字符次序输出这三个字符(一行)，再输出每个字符的序号（一行），最后按与输入字符相反的次序输出这三个字符（一行）。

2、输入一个三位整数，将它反向输出。例如输入127，输出应为721。

3、从键盘上读入小写的“pascal”，利用chr()和ord()，输出大写的“PASCAL”。 4、从键盘上读入一个实数，利用ROUND（）和TRUNC（）函数，输出该实数本身(场宽10，小数位数为3)、整数部分、小数部分、四舍五入后的值。要求：分三行输出 ；输出实数本身时，格式与读入时相同；整数部分、小数部分在同一行输出，中间以空格间隔开；其它各占一行。

5、从键盘上读入长方形的边长a,b(实型)，计算它的面积和周长，并分两行输出。

第二章：选择结构：掌握if和case语句，分支嵌套，以及begin end的用法。

1、对一批货物征收税金（长整型）。价格在1万元及以上的货物征税5%，在5000元及以上，1万元以下的货物征税3%，在1000元及以上，5000元以下的货物征税2%，1000元以下的货物免税。编写