下载文档原格式
全国青少年信息学奥林匹克联赛培训习题与解答（中学高级本）光盘模拟试题集普及组 (2)第一套 (2)打保龄球 (2)安全逃离 (2)表达式的转换 (3)到天宫做客 (4)第二套 (5)奶牛卧室 (5)进制转换 (5)硬币翻转 (5)拱猪计分 (6)第三套 (7)车厢重组 (7)阶乘问题 (8)子数整数 (8)垃圾陷阱 (9)提高组 (10)第一套 (10)低价购买 (10)棋盘游戏 (10)求正整数 (11)奇怪的电梯ok (11)第二套 (12)轰炸 (12)连续自然数和ok (12)约瑟夫 (13)点和线 (13)第三套 (14)杂务 (14)排行榜 (14)银行贷款 (15)机器人搬重物 (16)第四套 (17)数字组合 (17)相似基因 (17)波浪数 (18)文件压缩 (19)省队训练 (20)第一套 (20)海战ok (20)POLYGON (20)POWER (21)婚礼 (21)第二套 (22)多边形的面积 (22)玛丽卡 (23)PASTE (24)SEARCH (24)第三套 (25)文件排版 (25)纵横填字游戏 (26)普通递归关系 (27)完美的对称 (28)普及组第一套打保龄球源程序名bowling.??? (pas,c,cpp)可执行文件名 bowling.exe输入文件名 bowling.in输出文件名 bowling.out打保龄球是用一个滚球去打击十个站立的柱，将柱击倒。
一局分十轮，每轮可滚球一次或多次，以击倒的柱数为依据计分。
一局得分为十轮得分之和，而每轮的得分不仅与本轮滚球情况有关，还可能与后续一两轮的滚球情况有关。
即某轮某次滚球击倒的柱数不仅要计入本轮得分，还可能会计入前一两轮得分。
具体的滚球击柱规则和计分方法如下：（1）若某一轮的第一次滚球就击倒全部十个柱，则本轮不再滚球（若是第十轮则还需另加两次滚球，不妨称其为第十一轮和第十二轮，并不是所有的情况都需要滚第十一轮和第十二轮球）。
一、选择题：1. 下面哪个是关系型数据库管理系统（RDBMS）？A. MongoDBB. OracleC. HadoopD. Redis答案：B2. 在面向对象编程中，封装的主要目的是：A. 提高程序的执行效率B. 减少代码的复用性C. 控制类与类之间的依赖关系D. 隐藏实现细节，保护数据的安全性答案：D3. 以下哪种算法不属于常见的排序算法？A. 冒泡排序B. 插入排序C. 快速排序D. 广度优先搜索答案：D4. 下面哪个网络协议主要用于将网页从Web服务器传送到Web浏览器？A. FTPB. HTTPC. SMTPD. SNMP答案：B5. 常用的编程语言C++是基于以下哪种编程语言发展而来的？A. C语言B. JavaC. PythonD. Ruby答案：A二、填空题：1. 在计算机领域中，HTTP是指______________。
答案：超文本传输协议2. 在关系型数据库中，使用的是______________查询语言。
答案：结构化查询语言3. 在计算机网络中，TCP/IP协议簇中的IP是指______________协议。
答案：Internet协议4. 在面向对象编程中，继承可以实现代码的______________。
答案：重用和扩展5. 在计算机科学中，OS是指______________。
答案：操作系统三、简答题：1. 请解释一下什么是数据库索引？答案：数据库索引是一种用于提高数据库查询性能的数据结构。
它通过创建特定的数据结构，来加速对数据库表中数据的查询。
索引会根据指定的列或字段的值来对数据进行排序和组织，使得查询操作可以更快地定位到所需的数据。
索引的创建和维护可能会占用额外的存储空间和计算资源，但可以大大提高查询操作的效率。
2. 请简述面向对象编程的特点和优势。
答案：面向对象编程（OOP）是一种程序设计的范式，其特点包括封装、继承和多态。
面向对象编程的优势包括代码的重用性、可维护性和扩展性。
第1~10题为基础题，第11~20题为提高题，第21~33为综合题注：因为在本文档中需要用到一些特殊的数学符号（如：求和号、分数等），所以当您在百度文库中浏览时，一些数学符号可能会显示不出来，不过当您把本文档下载下来在本地浏览时，所有的符号即可全部都显示出来。
^_^基础题：【1 Prime Frequency】【问题描述】给出一个仅包含字母和数字（0-9, A-Z 以及a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。
输入：输入的第一行给出一个整数T( 0<T<201)，表示测试用例个数。
后面的T行每行给出一个测试用例：一个字母-数字组成的字符串。
字符串的长度是小于2001的一个正整数。
输出：对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。
这些字符按字母升序排列。
所谓“字母升序”意谓按ASCII 值升序排列。
如果没有字符的频率是素数，输出“empty”（没有引号）。
注：试题来源：Bangladesh National Computer Programming Contest在线测试：UV A 10789提示先离线计算出[2‥2200]的素数筛u[]。
然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u [p[i]]=1且ASCLL码值为i的字符）。
若没有频率为素数的字符，则输出失败信息。
【2 Twin Primes】【问题描述】双素数（Twin Primes）是形式为(p, p+2)，术语“双素数”由Paul Stäckel (1892-1919)给出，前几个双素数是(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。
在本题中请你给出第S对双素数，其中S是输入中给出的整数。
奥林匹克信息学竞赛试题一、选择题（每题2分，共10分）1. 在C++语言中，以下哪个是正确的整数类型定义？A. int a = 10;B. float a = 10;C. double a = 10;D. char a = 10;2. 以下哪个算法的时间复杂度为O(n^2)？A. 归并排序B. 快速排序C. 线性搜索D. 二分查找3. 在数据结构中，以下哪个是线性结构？A. 树B. 图C. 栈D. 队列4. 以下哪个是递归算法的典型应用？A. 快速排序B. 归并排序C. 深度优先搜索D. 广度优先搜索5. 在数据库中，以下哪个操作用于删除表中的记录？A. SELECTB. INSERTC. UPDATED. DELETE二、简答题（每题5分，共20分）1. 解释什么是贪心算法，并给出一个实际应用的例子。
2. 描述什么是动态规划，并解释它与贪心算法的区别。
3. 什么是哈希表？请简述其工作原理。
4. 什么是图的深度优先搜索（DFS）？请描述其基本步骤。
三、编程题（每题15分，共30分）1. 编写一个函数，实现对一个整数数组的快速排序算法。
2. 编写一个程序，实现对一个字符串进行反转。
四、综合题（每题20分，共40分）1. 给定一个无向图，编写一个程序来找到图中的最短路径。
请使用Dijkstra算法实现。
2. 设计并实现一个算法，用于解决背包问题，其中背包的容量为W，有n个物品，每个物品有其价值和重量。
五、附加题（10分）1. 假设你正在开发一个在线购物平台，需要实现一个推荐系统。
描述你将如何使用机器学习算法来实现这一功能。
结束语：奥林匹克信息学竞赛不仅考验参赛者的编程技巧，更考验他们的逻辑思维和创新能力。
希望本试题能够激发你的学习兴趣，帮助你在竞赛中取得优异的成绩。
信息奥林匹克竞赛试题一、选择题（每题2分，共20分）1. 在计算机科学中，以下哪个不是基本数据结构？A. 数组B. 链表C. 栈D. 文件系统2. 以下哪个算法是用于解决最短路径问题的？A. 快速排序B. 深度优先搜索C. 迪杰斯特拉算法D. 欧几里得算法3. 在C++语言中，以下哪个关键字用于声明引用类型？A. intB. floatC. &D. *4. 以下哪个排序算法是稳定的？A. 快速排序B. 归并排序C. 堆排序D. 冒泡排序5. 在数据库中，以下哪个操作用于删除表中的记录？A. SELECTB. INSERTC. DELETED. UPDATE二、简答题（每题10分，共20分）1. 描述什么是递归，并给出一个简单的递归算法的例子。
2. 解释什么是时间复杂度，并给出一个算法的时间复杂度分析示例。
三、编程题（每题30分，共60分）1. 编写一个函数，实现对一个整数数组的快速排序算法。
要求：- 输入：一个整数数组及其长度。
- 输出：排序后的数组。
2. 编写一个程序，实现对一个字符串进行模式匹配的KMP算法。
要求：- 输入：主字符串和模式字符串。
- 输出：模式字符串在主字符串中的所有出现位置。
四、算法设计题（每题30分，共30分）设计一个算法，用于在无序数组中找到第k大的元素。
假设数组中没有重复元素。
要求：- 输入：一个无序整数数组及其长度，以及一个整数k。
- 输出：第k大的元素。
结束语：本试题旨在考察参赛者对计算机科学基础知识的掌握程度，以及编程和算法设计的能力。
希望参赛者能够通过练习，提高自己的编程技巧和解决问题的能力。
祝所有参赛者取得优异的成绩！。
NOI’95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛初赛试题（高中组）竞赛用时：2小时一、基础题：<1> 执行①C>DIR 命令后，屏幕上显示如下画面：FORMAT COM 12145SYS COM 4878PUC BAT 126XCOPY EXE 112164 FILE（S）123456 bytes free接着又顺序执行了如下几条DOS 命令：②C>DIR> DF.TXT //表示将列表显示的目录作为文件写盘//③C>TYPE DF.TXT④C>DIR试问：执行命令③和④在屏幕上显示的结果是否与①相同?<2> 列举一个问题，使问题的解能对应相应的算法。
例如对算法：X：=10；Y：=5；READ（M，N）；S：=X*M-Y*N；可列举出如下的问题：学生答题，答对一题可得10分，答错一题则要扣去5分，输入答对的题数（M）与答错的题数（N），求最后得分（S）是多少？现有以下算法：K：=0 ；FOR I：=0 TO 10 DOK：=K+（50-I*5）DIV 2+1请列出一个相应的问题。
<3> 有标号为A、B、C、D和1、2、3、4的8个球，每两个球装一盒，分装4盒。
标号为字母的球与标号为数字的球有着某种一一对应的关系（称为匹配），并已知如下条件：①匹配的两个球不能在一个盒子内。
②2号匹配的球与1号球在一个盒子里。
③A号和2号球在一个盒子里。
④B匹配的球和C号球在一个盒子里。
⑤3号匹配的球与A号匹配的球在一个盒子里。
⑥4号是A或B号球的匹配球。
⑦D号与1号或2号球匹配。
请写出这四对球匹配的情况。
<4> 从入口（1）到出口（17）的可行路线图中，数字标号表示关卡：现将上面的路线图，按记录结构存储如下：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。
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那么该二叉树的先序遍历的顺序为：7.平面上有三条平行直线，每条直线上别离有7，5，6个点，且不同直线上三个点都不在同一条直线上。
问用这些点为极点，能组成多少个不同四边形？8.如以下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车箱。
其中每一个车箱能够向左行走,也能够进入栈S让后面的车箱通过。
现已知第一个抵达出口的是3号车箱，请写出所有可能的抵达出口的车箱排列总数(没必要给出每种排列)。
出口←← 1 2 3 4 5S↓9..将N个红球和M个黄球排成一行。
例如:N=2,M=3可取得以下6种排法:红红黄黄黄红黄红黄黄红黄黄红黄黄红红黄黄黄红黄红黄黄黄黄红红问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法)10．在书架上放有编号为1 ，2 ，．．．，n的n本书。
例13-4迷宫寻宝【问题描述】一个n行m列的迷宫（1<=n,m<=5），入口在左上角，规定只能向下或向右走。
迷宫的某些地方藏有不同价值（>0）的宝藏，同时又存在一些障碍无法通过。
求到达右下角出口时收集宝藏的最大值。
【输入】第一行n和m一下n行m列描述迷宫矩阵a[I,j]（-1：障碍）；最大值【样例输入】342-150513-16-18910【样例输出】33【分析】A[I,j]保存第i行第j列的宝藏价值。
令f[I,j]为从（1，1）走到第i行第j列时所能收集的宝藏的最大价值。
状态转移方程：F[I,j]=max{f[I-1,j],f[I,j-1]}+a[I,j](i<=n,1<=m)条件：n[I,j]<>-1初始：f[1,1]=a[1,1]目标：f[n,m]【参考程序】Const maxn=50;maxm=50;Fin=’b1.in’;Fout=’b1.out’;VarF,a:array[0..maxn+1,0..maxm+1]of integer;I,j,k,n,m,t:integer;Procedure init;BeginAssign(input,fin);Reset(input);Readln(n,m);For i:=0to n+1doFor j:=0to m+1do a[I,j]:=-1;A[0,1]:=0;For i:=1to n doFor j:=1to m doBeginRead(a[I,j]);If(a[I,j-1]=-1)and(a[i-1,j]=-1)then a[I,j]:=-1;//很关键的预处理End;Close(input);End;Function max(a,b:integer):integer;Begin max:=a;if b>a then max:=b;end;Procedure work;BeginFillchar(f,sizeof(f),0);For i:=1to n doFor j:=1to m doIf a[I,j]<>-1Then f[I,j]:=max(f[i-1,j],f[I,j-1])+a[I,j];End;Procedure print;BeginAssign(output,fout);Rewrite(output);Writeln(f[n,m]);Close(output);End;BeginInit;Work;Print;End.13-5花店橱窗布置（IOI1999）【问题描述】假设你想以最美观的方式布置花店的橱窗。
信息学奥赛试题及答案信息学奥赛试题一、填空题（共20题，每题1.5分，共计30分。
每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。
1.微型计算机的性能主要取决于（）。
A）内存B）主板C）中央处理器D）硬盘E）显示器2.能将高级语言程序转换为目标程序的是( ).A）调试程序B）解释程序C）编辑程序D）编译程序E）连接程序3．A=B,B=B,C=B,则A∨B∧C=( )A） B） C） D） E)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，则第五个出行列的元素是( )。
A)5 B)41 C)77 D)13 E)187.在利用E-mail前，需求对Outlook举行设置，个中ISP 发送电子邮件的效劳器称为( )效劳器。
A)POP3 B)SMTPC)DNS D)FTP E)HTTP8.对给定的整数序列(54,73,21,35,67,78,63,24,89)举行从小到大的排序时,接纳快速排序的第一趟扫描的成效是( ).A)(24,21,35,54,67, 78,63,73,89) B)(24,35,21,54,67, 78,63,73,89)C)(24,21,35,54,67, 63,73,78,89) D)(21,24,35,54,63, 67,73,78,89)E)(24,21,35,54,67, 63,73,78,89)9.编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1，2，3，……,一圈又一圈,问当数到数字n ,所在的纸牌编号为多少?A) n mod 13 B)1+(n-1) mod 13 C)(n+1) mod 13-1 D)(n+1) mod 13 E) (n-1) mod 1310.对下图进行广度优先拓朴排序得到的顶点序列正确的是( ).A) 1,2,3,4,5,6 B) 1,3,2,4,5,6 C) 1,3,2,4,6,5D) 1,2,3,4,6,5, E) 1,3,2,4,5,611.下列属于冯.诺依曼计算机模型的核心思想是( ).A)采用二进制表示数据和指令; B)采用”存储程序”工作方式C)计算机硬件有五大部件(运算器、控制器、存储器、输入和输出设备)D)结构化程序设计方法E)计算机软件只有系统软件12．CPU访问内存的速度比访问下列哪个(些)存储设备要慢( )。
信息学基础知识题库硬件1．微型计算机的问世是由于（C）的出现。
A. 中小规模集成电路B. 晶体管电路C. (超)大规模集成电路D. 电子管电路2．中央处理器（CPU）能访问的最大存储器容量取决于（A）。
A. 地址总线B. 数据总线C. 控制总线D. 实际内存容量3．微型计算机中，（C）的存储速度最快。
A. 高速缓存B. 外存储器C. 寄存器D. 内存储器4．在计算机硬件系统中，cache是（D）存储器。
A. 只读B. 可编程只读C. 可擦除可编程只读D. 高速缓冲5．若我们说一个微机的CPU是用的PII300，此处的300确切指的是（A）。
A. CPU的住时钟频率B. CPU产品的系列号C. 每秒执行300百万条指令D. 此种CPU允许的最大内存容量6．计算机主机是由CPU与（D）构成。
A. 控制器B. 输入输出设备C. 运算器D. 内存储器7．计算机系统总线上传送的信号有（B）。
A. 地址信号与控制信号B. 数据信号、控制信号与地址信号C. 控制信号与数据信号D. 数据信号与地址信号8．不同类型的存储器组成了多层次结构的存储器体系，按存储器速度又快到慢的排列是（C）。
A. 快存>辅存>主存B. 外存>主存>辅存C. 快存>主存>辅存D. 主存>辅存>外存9．微机内存储器的地址是按（C）编址的。
A. 二进制位B. 字长C. 字节D. 微处理器的型号10．在微机中，通用寄存器的位数是（D）。
A. 8位B. 16位C. 32位D. 计算机字长11．不同的计算机，其指令系统也不同，这主要取决于（C）。
A. 所用的操作系统B. 系统的总体结构C. 所用的CPUD. 所用的程序设计语言12．下列说法中，错误的是（BDE）A. 程序是指令的序列，它有三种结构：顺序、分支和循环B. 数据总线决定了中央处理器CPU所能访问的最大内存空间的大小C. 中央处理器CPU内部有寄存器组，用来存储数据D. 不同厂家生产的CPU所能处理的指令集是相同的E. 数据传输过程中可能会出错，奇偶校验法可以检测出数据中哪一位在传输中出了错误13．美籍匈牙利数学家冯·诺依曼对计算机科学发展所作出的贡献是（C）。
卜人入州八九几市潮王学校信息学根底知识题库硬件1．微型计算机的问世是由于〔C〕的出现。
A.中小规模集成电路B.晶体管电路C.(超)大规模集成电路D.电子管电路2．HY处理器〔CPU〕能访问的最大存储器容量取决于〔A〕。
A.地址总线B.数据总线C.控制总线D.实际内存容量3．微型计算机中，〔C〕的存储速度最快。
A.高速缓存B.外存储器C.存放器D.内存储器4．在计算机硬件系统中，cache是〔D〕存储器。
A.只读B.可编程只读C.可擦除可编程只读D.高速缓冲5．假设我们说一个微机的CPU是用的PII300，此处的300确切指的是〔A〕。
A.CPU的住时钟频率B.CPU产品的系列号C.每秒执行300百万条指令D.此种CPU允许的最大内存容量6．计算机主机是由CPU与〔D〕构成。
A.控制器B.输入输出设备C.运算器D.内存储器7．计算机系统总线上传送的信号有〔B〕。
A.地址信号与控制信号B.数据信号、控制信号与地址信号C.控制信号与数据信号D.数据信号与地址信号8．不同类型的存储器组成了多层次构造的存储器体系，按存储器速度又快到慢的排列是〔C〕。
A.快存>辅存>主存B.外存>主存>辅存C.快存>主存>辅存D.主存>辅存>外存9．微机内存储器的地址是按〔C〕编址的。
A.二进制位B.字长C.字节D.微处理器的型号10．在微机中，通用存放器的位数是〔D〕。
A.8位B.16位C.32位D.计算机字长11．不同的计算机，其指令系统也不同，这主要取决于〔C〕。
A.所用的操作系统B.系统的总体构造C.所用的CPUD.所用的程序设计语言12．以下说法中，错误的选项是〔BDE〕A.程序是指令的序列，它有三种构造：顺序、分支和循环B.数据总线决定了HY处理器CPU所能访问的最大内存空间的大小C.HY处理器CPU内部有存放器组，用来存储数据D.不同厂家消费的CPU所能处理的指令集是一样的E.数据传输过程中可能会出错，奇偶校验法可以检测出数据中哪一位在传输中出了错误13．美籍匈牙利数学家冯·诺依曼对计算机科学开展所作出的奉献是〔C〕。
信息学基础知识题库硬件1．微型计算机的问世是由于（C）的出现。
A. 中小规模集成电路B. 晶体管电路C. (超)大规模集成电路D. 电子管电路2．中央处理器（CPU）能访问的最大存储器容量取决于（A）。
A. 地址总线B. 数据总线C. 控制总线D. 实际内存容量3．微型计算机中，（C）的存储速度最快。
A. 高速缓存B. 外存储器C. 寄存器D. 内存储器4．在计算机硬件系统中，cache是（D）存储器。
A. 只读B. 可编程只读C. 可擦除可编程只读D. 高速缓冲5．若我们说一个微机的CPU是用的PII300，此处的300确切指的是（A）。
A. CPU的住时钟频率B. CPU产品的系列号C. 每秒执行300百万条指令D. 此种CPU允许的最大内存容量6．计算机主机是由CPU与（D）构成。
A. 控制器B. 输入输出设备C. 运算器D. 内存储器7．计算机系统总线上传送的信号有（B）。
A. 地址信号与控制信号B. 数据信号、控制信号与地址信号C. 控制信号与数据信号D. 数据信号与地址信号8．不同类型的存储器组成了多层次结构的存储器体系，按存储器速度又快到慢的排列是（C）。
A. 快存>辅存>主存B. 外存>主存>辅存C. 快存>主存>辅存D. 主存>辅存>外存9．微机内存储器的地址是按（C）编址的。
A. 二进制位B. 字长C. 字节D. 微处理器的型号10．在微机中，通用寄存器的位数是（D）。
A. 8位B. 16位C. 32位D. 计算机字长11．不同的计算机，其指令系统也不同，这主要取决于（C）。
A. 所用的操作系统B. 系统的总体结构C. 所用的CPUD. 所用的程序设计语言12．下列说法中，错误的是（BDE）A. 程序是指令的序列，它有三种结构：顺序、分支和循环B. 数据总线决定了中央处理器CPU所能访问的最大内存空间的大小C. 中央处理器CPU内部有寄存器组，用来存储数据D. 不同厂家生产的CPU所能处理的指令集是相同的E. 数据传输过程中可能会出错，奇偶校验法可以检测出数据中哪一位在传输中出了错误13．美籍匈牙利数学家冯·诺依曼对计算机科学发展所作出的贡献是（C）。
信息学基础知识题库硬件1．微型计算机的问世是由于（C）的出现。
A. 中小规模集成电路B. 晶体管电路C. (超)大规模集成电路D. 电子管电路2．中央处理器（CPU）能访问的最大存储器容量取决于（A）。
A. 地址总线B. 数据总线C. 控制总线D. 实际内存容量3．微型计算机中，（C）的存储速度最快。
A. 高速缓存B. 外存储器C. 寄存器D. 内存储器4．在计算机硬件系统中，cache是（D）存储器。
A. 只读B. 可编程只读C. 可擦除可编程只读D. 高速缓冲5．若我们说一个微机的CPU是用的PII300，此处的300确切指的是（A）。
A. CPU的住时钟频率B. CPU产品的系列号C. 每秒执行300百万条指令D. 此种CPU允许的最大内存容量6．计算机主机是由CPU与（D）构成。
A. 控制器B. 输入输出设备C. 运算器D. 内存储器7．计算机系统总线上传送的信号有（B）。
A. 地址信号与控制信号B. 数据信号、控制信号与地址信号C. 控制信号与数据信号D. 数据信号与地址信号8．不同类型的存储器组成了多层次结构的存储器体系，按存储器速度又快到慢的排列是（C）。
A. 快存>辅存>主存B. 外存>主存>辅存C. 快存>主存>辅存D. 主存>辅存>外存9．微机内存储器的地址是按（C）编址的。
A. 二进制位B. 字长C. 字节D. 微处理器的型号10．在微机中，通用寄存器的位数是（D）。
A. 8位B. 16位C. 32位D. 计算机字长11．不同的计算机，其指令系统也不同，这主要取决于（C）。
A. 所用的操作系统B. 系统的总体结构C. 所用的CPUD. 所用的程序设计语言12．下列说法中，错误的是（BDE）A. 程序是指令的序列，它有三种结构：顺序、分支和循环B. 数据总线决定了中央处理器CPU所能访问的最大内存空间的大小C. 中央处理器CPU内部有寄存器组，用来存储数据D. 不同厂家生产的CPU所能处理的指令集是相同的E. 数据传输过程中可能会出错，奇偶校验法可以检测出数据中哪一位在传输中出了错误13．美籍匈牙利数学家冯·诺依曼对计算机科学发展所作出的贡献是（C）。
信息学竞赛中问题求解常见题分析（四）（排列组合问题）一、知识点：1． 分类计数原理：做一件事情，完成它可以有n 类办法，在第一类办法中有m 1种不同的方法，在第二类办法中有m 2种不同的方法，……，在第n 类办法中有m n 。
种不同的方法，那么完成这件事共有N=m 1+m 2+…+m n 。
种不同的方法。
2． 分步计数原理：做一件事情，完成它需要分成n 个步骤，做第一步有m 1种不同的方法，做第二步有m 2种不同的方法，……，做第n 步有m n 种不同的方法，那么完成这件事有N=m 1*m 2*…m n 。
种不同的方法。
3． 排列的概念：从n 个不同元素中，任取m(m ≤n)个元素(这里的被取元素各不相同)，按照一定的顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列。
4． 排列数的定义：从n 个不同元素中，任取m(m ≤n)个元素的所有排列的个数叫做从n 个元素中取出m 个元素的排列数，用符号m n A 表示。
5． 排列数公式：m n A =n(n-1)(n-2)…(n-m+1)(m ，n ∈N ，m ≤n)6． 阶乘：n!表示正整数l 到n 的连乘积，叫做n 的阶乘规定0!=l 。
7． 排列数的另一个计算公式：)!(!m n n A m n -= 8． 组合的概念：一般地，从n 个不同元素中取出m(m ≤n)个元素并成一组，叫做从n 个不同元素中取出m 个元素的一个组合．9． 组合数的概念：从n 个不同元素中取出m(m ≤n)个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数．用符号m n C 表示．10．组合数公式：!)1)...(2)(1(m m n n n n A A C m m m n m n+---==，或)!(!!m n m n C m n -= (n ，m ∈N ，且m ≤n) 11．组合数的性质1：m n n m n C C -=，规定：0n C ：=1； 2：11-++=m nm n m n C C C 。
信息学奥林匹克竞赛一、问题求解（每题5分，共10分）1. （寻找假币问题）现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？请指出第一次的分组称重方法。
[4次，27 27 26]2. 父子年龄之和50岁,再过5年父亲年龄是儿子的4倍,父亲和儿子现在各多少岁?[43 7]3.有红、黄、黑、白四色球各一个，放置在一个内存编号为1、2、3、4四个格子的盒中，每个格子放置一只球，它们的顺序不知。
甲、乙、丙三人猜测放置顺序如下：甲：黑编号1，黄编号2；乙：黑编号2，白编号3；丙：红编号2，白编号4。
结果证明甲乙丙三人各猜中了一半，写出四色球在盒子中放置情况及推理过程。
4.有一个两位数,加6后再把个位数与十位数互换,得到一个新的两位数,这样加6再互换共三次后,又得到了原来的两位数,求原来的两位数. [ 19, 52, 85 ]5.如果一个自然数的数字之积加上这些数字之和正好等于这个自然数,我们称这样的自然数为"巧数",求100以内的所有巧数. [19,29,39,49,59,69,79,89,99 ]6.有一个数字各不相同的三位数,如果将此数码重新排列,必可得到一个最大数和一个最小数,此两数之差正好就是原来的三位数,求这个三位数. [ 495 ]7.把一个两位素数写在另一个两位素数后面,得到一个四位数.它能被这两个素数之和的一半整除,求出所有这样的素数对. [ 53,13; 47,19; 43,23; 37,29 ]8.从小到大找出五个素数,使后面的数比前面的数都大12. [ 5,17,29,41,53 ]9.求1--200之间,有多少个连续的自然数之和等于555,把这样的数组分别打印出来.[ 共6组: 4-33, 30-44, 51-60, 90-95, 109-113, 184-186 ]10.某路公共汽车包括起始站和终点站共有15个车站,有一辆车除终点外,每一站上车的乘客中都恰好有一位乘客到以后的每一站下车,为了使每一位乘客都有座位,问这辆公共汽车最少要有多少个座位?这趟车共售出多少张票? [ 56 , 105 ]11.A,B,C三人分24个苹果,每人所得个数等于三年前他们的年龄数.如果C把所得苹果的一半平分给A和B,然后B再把现有苹果的一半平分给A和C;最后A再把现有苹果的一半平分给B和C,这时每人的苹果数恰好相等.求现在三人的年龄个是多少岁?[ 16, 10, 7]12.蜘蛛有8条腿,蜻蜓有6条腿和2对翅,蝉有6条腿和1对翅. 三种虫子共18只,共有118条腿和20对翅.问每种虫子各几只? [ 5, 7, 6 ]13. 甲,乙两数的和为168,甲数的八分之一与乙数的四分之三的和为76,求甲,乙两数各是多少?[ 80, 88 ]14. 我国古代数学问题:1兔换2鸡,2兔换3鸭,5兔换7鹅.某人用20只兔换得鸡.鸭.鹅共30只,问其中鸡.鸭.鹅各几只? [ 2,21,7 ; 4,12,14 ; 6,3,21 ]15.将下图中8个字母换成1-8这8个不相同的数,使其四个算式成立.[ 8 7 1 5 6 3 2 4 6 5 1 7 8 4 2 3]A -B =C C +D =E G *F = E A /G = H15. 有一本小册子,中间撕去一页后,剩下的各页码之和为90, 求:(1)这本小册子共有多少页? (2)撕下的那页的两个页码是几? [ 7 ; 7, 8 ]16.甲,乙两港口距离不超过5000公里,有三只轮船于某天零时同时从甲港开往乙港,设三只船都以匀速24小时不停地航行,若干天后零时第一只船到达乙港,几天后18时,第二只船也到达,再过几天后8时,第三只船也到达,假定三只船每天的航速分别为300公里/天,240公里/天,180公里/天, 问甲乙两港实际的距离多少公里? 三只船各走了多少时间?[ 3300公里; 11天, 13天18小时, 18天8小时]17.环绕大厅有七盏电灯A,B,C,D,E,F,G,各自装有一个拉线开关,开始时只有A,C,E,G四盏灯亮着,一个小孩从A灯开始顺次拉一下开关,问当他拉了1000次开关后,最后都有哪几盏灯是亮着的?18.一木板高110厘米,有个小虫由地面向上爬,每分钟爬上50厘米,每爬1分钟就要休息1分钟,在这休息时间内下滑30厘米,当小虫爬到顶部还要休息2分钟,再按原路爬回地面,问共用多少分钟? [ 10 ] 19. 一个椭园形跑道周长为400米,甲,乙两人同时从一个起跑点向相反的方向绕跑道慢跑,已知甲每秒跑5米,乙每秒跑3米,问他们两人在跑道上分别5次相遇时,每次各距起跑点多远?(取距起跑点近的距离)20、某老者和他的孙子同生于20世纪,他们年龄相差60岁,若把他们出生年份被3,4,5,6除,余数分别是1,2,3,4. 编程求出老者和他的孙子各自出生的年份.[ 1918, 1978 ]21、自然数被3,4,5除都余1,被7除余2,此数最小是几? [ 121 ]22、学生排队：设有6名学生，按身高上升次序排列，他们是A，B，C，D，E，F。
第1~10题为基础题，第11~20题为提高题，第21~33为综合题注：因为在本文档中需要用到一些特殊的数学符号（如：求和号、分数等），所以当您在百度文库中浏览时，一些数学符号可能会显示不出来，不过当您把本文档下载下来在本地浏览时，所有的符号即可全部都显示出来。
^_^基础题：【1 Prime Frequency】【问题描述】给出一个仅包含字母和数字（0-9, A-Z 以及a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。
输入：输入的第一行给出一个整数T( 0<T<201)，表示测试用例个数。
后面的T行每行给出一个测试用例：一个字母-数字组成的字符串。
字符串的长度是小于2001的一个正整数。
输出：对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。
这些字符按字母升序排列。
所谓“字母升序”意谓按ASCII 值升序排列。
如果没有字符的频率是素数，输出“empty”（没有引号）。
注：试题来源：Bangladesh National Computer Programming Contest在线测试：UV A 10789提示先离线计算出[2‥2200]的素数筛u[]。
然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u [p[i]]=1且ASCLL码值为i的字符）。
若没有频率为素数的字符，则输出失败信息。
【2 Twin Primes】【问题描述】双素数（Twin Primes）是形式为(p, p+2)，术语“双素数”由Paul Stäckel (1892-1919)给出，前几个双素数是(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。
在本题中请你给出第S对双素数，其中S是输入中给出的整数。
历届“问题求解”解析（2013竞赛辅导）问题求解是信息学竞赛初赛中常见题型，它共两题，每题5分，共10分，十六届增加了比重，有三题，占15分。
诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合、逻辑推理、递推关系等问题出现在问题求解中。
（相关问题的具体讲解根据需要考虑发讲义） 第一届（逻辑推理问题）1. 有标号为A 、B 、C 、D 和1、2、3、4的8个球，每两个球装一盒，分装4盒。
标号为字母的球与标号为数字的球有着某种一一对应的关系（称为匹配），并已知如下条件： ① 匹配的两个球不能在一个盒子内。
② 2号匹配的球与1号球在一个盒子里。
③ A 号和2号球在一个盒子里。
④ B 匹配的球和C 号球在一个盒子里。
⑤ 3号匹配的球与A 号匹配的球在一个盒子里。
⑥ 4号是A 或B 号球的匹配球。
⑦ D 号与1号或2号球匹配。
请写出这四对球匹配的情况。
第四届（递推、树、图）1. 已知一个数列U 1，U 2，U 3，…，U N ，… 往往可以找到一个最小的K 值和K 个数a 1，a 2，…,a n 使得数列从某项开始都满足： U N+K =a 1U N+K-1+a 2U N+K-2+……+a k U N (A)例如对斐波拉契数列1，1，2，3，5，…可以发现：当K=2，a 1 =1，a 2 =1时，从第3项起（即N>=1）都满足U n+2 =U n+1+U n 。
试对数列13，23，33，…，n 3,…求K 和a 1,a 2, …,a K 使得（A ）式成立。
当K= 4，a 1,a 2,…,a k 为a 1=4, a 2=6, a 3=4，a 4=-1对数列132333,…,n 3,…（A ）成立。
2．给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA 画出此二叉树。
3．用邻接矩阵表示下面的无向图：表示该无向图的邻接矩阵为 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0第五届（递推）将Ln 定义为求在一个平面中用n 条直线所能确定的最大区域数目。
高中信息学竞赛各种问题求解试题及答案第1题(5分)，将n个不同颜色的球放人k个无标号的盒子中( n>=k，且盒子不允许为空)的方案数为S(n，k)，例如：n=4，k=3时，S(n，k)=6。
当n=6，k=3时，S(n，k)=________。
答案：0 k < nS(n,k)= 1 k = 1S(n-1,k-1)+k*S(n-1,k) n >= k >= 2第2题(5分)，有5本不同的数学书分给5个男同学，有4本不同的英语书分给4个女同学，将全部书收回来后再从新发给他们，与原方案都不相同的方案有________种。
答案：5!*4!+D(5)*D(4)=1140480其中：D(n)=(n-1)*(D(n-1)+D(n-2)) (n > 2)D(1)=0 D(2)=1第3题(6分)，把三角形各边分成n等分，过每一分点分别做各边的平行线，得到一些由三角形的边和这些平行线所组成的平行四边形。
n为已知整数，能组成_______个平行四边形。
答案：3*C(n+2,4)第4题(6分)，由a，b，c3个不同的数字组成一个N 位数，要求不出现两个a相邻，也不出现两个b相邻，这样的N位数的个数为AN，用AN-1和AN-2表示AN的关系式为：AN＝_______________。
答案：AN= 2*AN-1+AN-2第5题(6分)，在m*n的棋盘上，每个方格(单位正方形，即边长为1的正方形)的顶点称为格点。
以格点为顶点的多边形称为格点多边形。
若设格点凸N边形面积的最小值为gn，格点凸N边形内部(非顶点的)格点的个数的最小值为fn，则gn和fn的关系式为：gn=___________。
答案：Gn= fn+N/2-1 ( N >= 3 )第6题(4分)，编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1、2、3、…、20、21、…，一圈又一圈。
问：当数到数字N时，所在纸牌的编号为多少?答案：1+(N-1) mod 13第7题(8分)，有位小同学喜欢在方阵中填数字，规则是按下图示例从右上角开始，按斜线填数字，碰到边界就重新。
显然，数字1在坐标(1，5)位置，数字25在坐标(5，1)位置。
后来这位小朋友想知道，对于N阶的方阵，随机取一个位置(x，y)，并规定x≤y，问这个位置上应该填的数字是多少?5阶方阵的示例图如下：11 7 4 2 116 12 8 5 320 17 13 9 623 21 18 14 1025 24 22 19 15答案：(N-y+x)*(N-y+x-1)/2+x第8题(5分)，设有质量为1、3、9、27、81、…3n g...的砝码各一枚，如果砝码允许放在天平的两边，则用它们来称物体的质量，最多可称出1g到3n+3n/2g之间的所有质量，如n=4时，可称出18到121g之间的所有质量；当物体质量为M=14时，有14+9+3+1=27，即天平一端放M=14g的物体和9g、3g、1g的砝码，另一端放27g的砝码，即可称出M的质量。
当M=518g时，请你写出称出该物体的质量的方法，并用上述所示的等式来表示。
答案：518+243+3+1= 729+27+9第9题(7分)，在圆周上有N个点(N>=6)，在任意两个点之间连一条弦，假设任何3条弦在圆的内部都没有公共点，问这些弦彼此相交能在圆内构成多少个三角形(只要求写出三角形总数的表示式而无需化简)?提示：下图是N=6的情况，图中所示的4个三角形从某种意义上说具有一定的代表性。
答案：C(N,3)+4*C(N,4)+5*C(N,5)+6*C(N,6)第10题(6分)，用1个或多个互不相同的正整数之和表示1～511之间的所有整数①至少要多少个不同的正整数_________________;②这些正整数是_______________答案：①9②1,2,4,6,16,32,64,128,256第11题(7分)，在有m行n列格子的棋盘内，一枚棋子从棋盘的左上角格子沿上、下、左、右方向行走，最后走到棋盘的右下角格子。
该棋子走过的格子数为奇数的充分必要条件是________________答案：m+n为偶数完善程序试题及其答案第1题(14分)以下程序是将一组整数按从小到大的顺序排列。
排序的方法是将长度为n的数a分为两个长度分别为(n div 2)与(n-n div 2)的子数组a1，a2。
然后递归调用排序过程，将a1，a2分别排序，最后将a1，a2归并成数组a。
例如a=(3，1，2，4)，那么a1=(3，1)，a2=(2，4)。
调用排序过程将a1，a2排序，得到a1=(1，3)，a2=(2，4)，然后进行合并排序。
从键盘输入数的长度n以及n个整数，存在数组a中，调用子过程sort进行排序，最后输出排序结果。
program wsh；const maxn=100；．type arr：array[1..maxn] of integer；vara：array[1..maxn] of integer；n，i：integer；procedure sort(n:integer; var a:arr);vari, p1, p2, n1, n2: integer;a1,a2 :arr;beginif n = 1 then exit;fillchar(a1,sizeof(a1) ,0);fillchar(a2,sizeof(a2) ,0);n1:=0; n2:=0;n1:=n div 2; n2:=(____(1)____);for i:= 1 to n1 do a1[i]:=a[i];for i:= 1 to n2 do a2[i]:=____(2)____;____(3)____;sort(n2, a2);p1:=1; p2:=1;n:=0;while (p1 <= n1) and (____(4)____) dobeginn:=n+1;if ____(5)____then begin a[n]:=a1[p1] ;inc(p1); endelse begin ____(6)____; inc(p2) ;end;end;if p1 <= n1then for i:= ____(7)____ to n1 do begin n:=n+1;a[n]:=a1[i] endelse for i:=p2 to n2 do begin n:=n+1; a[n]:=a2[i]; end; end;beginwrite('n = ');readln (n);for i:= 1 to n do read(a[i]);readln;sort(n,a);for i:=1 to n do write(a[i],'');writeln;end. 答案：n-n1a[n1+i]sort(n1,a1)(p2 < =n2)a1[p1] < a2[p2]a[n]:=a2[p2]p1第2题(8分)有n(1≤n≤100)个同学种m(1≤n≤m≤100)种小树苗，例如：4个同学（1、2、3、4）每小时种4种树苗（A、B、C、D）的数量估算如下表所示，编程输出每人种1种苗所用的总时间最少的安排方案和所花费的时间。
学生 A B C D1 52 4 52 43 5 33 5 24 24 3 2 3 3program wsh;constmaxn=100; maxm = 100;vara: array[1..maxn, 1..maxm] of integer;m, n: integer;i, j, t: integer;procedure work(k,t1: integer);var i: integer;beginif ____(1)____ thenbeginif t1 < t then t1:=t;exit;end;for i:= ___(2)___ to ___(3)___ dowork(k+1,___(4)___);end;beginreadln(n,m);for i:=1 to n dobeginfor j:=1 to m do read (a[i,j]);readlnend;t:= maxint;work(1,0);writeln(t)end.答案：k>n1mt1+t[k,i]第3题(10分)程序的任务是用0…9中的数字填入如下乘法运算的*处，数字可重复使用，且所用的数字至少有一个是素数，要求输出满足下列算式的方案数。
* * *x * *-------------------------* * ** * *-------------------------* * *program wsh;const p:set of 0...9 = [2,3,5,7];vars:set of 0..9;n: integer;ans: longint;f: text;procedure init;vari: integer;t:byte;beginreadln(n);s:=[];for i:=1 to n dobeginread(t);s:=s+[t];end;close(f);end;function ok(x,l:integer):boolean; {此函数判断x是否符合条件}var t: byte;beginok:=false;if ___(1)___< > l then exit;while x< >0 dobegint:=x mod 10;if not ( t in s) then exit;x:=x div 10;end;ok:=true;end;function inset(x:integer):boolean; {此函数判断x中是否包含素数字}var t: byte;begininset:= false;while ___(2)___ dobegint:=x mod 10;if t in p thenbegininset:= true;exit;end;___(3)___;end;end;procedure work;var i,i1,i2,i3,j1,j2:integer;beginans:=0;for i1:=1 to 9 doif i1 in s thenfor i2:=1 to 9 doif i2 in s thenfor i3:=1 to 9 doif i3 in s thenbegin___(4)___;for j1:=1 to 9 doif (j1 in s) and ok(j1*i,3) thenfor j2:=1 to 9 doif (j2 in s) and ok(j2*i,3) and ___(5)___thenbeginif (i1 in p) or (i2 in p) or (i3 in p)or (j1 in p) or (j2 in p) or inset(j1*i) orinset(j2*i)then inc(ans);end;end;writeln(ans);end;begininit;work;end.答案：trunc(ln(x)/ln(10))+1x>0x:=x div 10i:=i1*100+i2*10+i3ok(j1*i*10+j2*i,4)第4题(15分)下列程序是对冒泡排序的一种改进，数组elem中有n个元素elem[1]、elem[2]…、elem[n]。
