下载文档原格式
noip2022提高组初赛试题及答案第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组C语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一.单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确选项。
）1.与16进制数A1.2等值的10进制数是（）A.101.2B.111.4C.161.125D.177.252.一个字节（byte）由（）个二进制位组成。
A.8B.16C.32D.以上都有可能3.一下逻辑表达式的值恒为真的是（）A.P∨（┐P∧Q)∨（┐P∧┐Q)B.Q∨（┐P∧Q)∨(P∨┐Q)C.P∨Q∨(P∧┐Q)∨(┐P∧Q)D.P∨┐Q∨(P∧┐Q)∨(┐P∧┐Q)4.Linu某下可执行文件的默认扩展名为（）5.如果在某个进制下等式7某7=41成立，那么在该进制下等式12某12=（）也成立。
A.100B.144C.164D.1966.提出“存储程序”的计算机工作原理的是（）。
A.克劳德·香农B.戈登·摩尔C.查尔斯·巴比奇D.冯·诺依曼7.前缀表达式“+3某2+512”的值是（）A.23B.25C.37D.658.主存储器的存取速度比中央处理器（CPU）的工作速度慢很多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了（）A.寄存器B.高速缓存C.闪存D.外存9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右一次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置，则第K号结点的父结点如果存在的话，应当存放在数组的（）号位置。
A.2kB.2k+1C.k/2下取整D.(k+1)/2下取整10.一下竞赛活动中历史最悠久的是（）A.全国青少年信息学奥林匹克联赛（NOIP）B.全国青少年信息学奥林匹克竞赛（NOI）C.国际信息学奥林匹克竞赛（IOI）D.亚太地区信息学奥林匹克竞赛（APIO）二.不定项选择题（共10题，每题1.5分，共计15分。
2004年第16届国际信息学奥赛试题解析（希腊）第一题阿耳特弥斯Day 1. Source file Artemis.*Available memory:16M. Maximum running time:1SZeus gave Artemis, the goddess of the wilderness, a rectangular area for growing a forest. With the left side of the area as a segment of the positive y-axis and the bottom side as a segment of the positive x-axis, and(0,0) the left bottom corner of the area, Zeus told Artemis to plant trees only on integer coordinate points in the area. Artemis liked the forest to look natural, and therefore planted trees in such a way that a line connecting two trees was never parallel to x-axis or y-axis.At times, Zeus wants Artemis to cut trees for him. The trees are to be cut as follows: 1．Zeus wants at least a given number T of trees to be cut for him.2．To get a rectangular football pitch for future football success, Artemis is to cut all trees within a rectangular area, and no trees outside of it.3．The sides of this rectangular area are to be parallel to x-axis and y-axis.4．Two opposite corners of the area must be located on trees and therefore those corner trees are also cut.As Artemis likes the trees, she wants to fulfill these conditions whilst cutting as few trees as possible. You are to write a program that, given information on the forest and the minimum number T of trees to be cut, selects an area for cutting trees for Artemis.INPUTThe input file name is artemis. in. The first line contains one integer N: the number of trees in the forest. The second line contains one integer T: the minimum number of trees to be cut. The following N lines describe the positions of the N trees. Each of these lines contains two integers X and Y: the x-coordinate followed by the y-coordinate of a tree.OUTPUTSseparated by one space: Artemis should use the Jth tree (with position given on line 1+2 of the input file) and Jth tree(with position given on line J+2 of the input file)as the corners of the area for cutting trees. The order of these two number is irrelevant. There may be several ways to choose these trees and you need to find and output one of them. For all test cases at least one solution exists.EXAMPLE INPUTS AND OUTPUTSartemis. in artemis. outIn all inputs, 1≤N≤20000, 0≤X, Y≤64000 and, 1<T≤N.Additionally, in 50% of the inputs, 1<N<5000参考译文：阿耳特弥斯（Day1文件名artemis. *内存限制：16MB，时间限制1s）问题描述：宙斯赠予女神阿耳特弥斯一片矩形的土地让其植树。
第十届：1、一个家具公司生产桌子和椅子。
现有113个单位的木材。
每张桌子要使用20个单位的木材，售价是30元；每张椅子要用16个单位的木材，售价是20元。
使用已有的木材生产桌椅（不一定要用光木材）做多可以买__ __元钱。
2、75名儿童去游乐场玩。
他们可以骑旋转木马，坐滑行轨道，乘宇宙飞船。
已知其中20人这三种东西都玩过，55人至少．．玩过其中两种。
若每玩一样的费用为5元，游乐场总共收入700元，可知有___ __名儿童没有玩过其中任何一种。
第十一届：1. 将数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换_____次。
2. 有3 个课外小组：物理组，化学组和生物组。
今有张、王、李、赵、陈5 名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。
如果要在3 个小组中分别选出3 位组长，一位同学最多只能担任一个小组的组长，共有种_____选择方案。
第十二届：1．（寻找假币）现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。
请写出你的结果：_________________________________________________。
2．（取石子游戏）现有5堆石子,石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）, 取最后一颗石子的一方获胜。
甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：_____________________________________。
第十三届：1．（子集划分）将n 个数{1，2，…，n}划分成r 个子集。
每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。
noip2022提高组初赛试题第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组C语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一.单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确选项。
）1.与16进制数A1.2等值的10进制数是（）A.101.2B.111.4C.161.125D.177.252.一个字节（byte）由（）个二进制位组成。
A.8B.16C.32D.以上都有可能3.一下逻辑表达式的值恒为真的是（）A.P∨（┐P∧Q)∨（┐P∧┐Q)B.Q∨（┐P∧Q)∨(P∨┐Q)C.P∨Q∨(P∧┐Q)∨(┐P∧Q)D.P∨┐Q∨(P∧┐Q)∨(┐P∧┐Q)4.Linu某下可执行文件的默认扩展名为（）5.如果在某个进制下等式7某7=41成立，那么在该进制下等式12某12=（）也成立。
A.100B.144C.164D.1966.提出“存储程序”的计算机工作原理的是（）。
A.克劳德·香农B.戈登·摩尔C.查尔斯·巴比奇D.冯·诺依曼7.前缀表达式“+3某2+512”的值是（）A.23B.25C.37D.658.主存储器的存取速度比中央处理器（CPU）的工作速度慢很多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了（）A.寄存器B.高速缓存C.闪存D.外存9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右一次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置，则第K号结点的父结点如果存在的话，应当存放在数组的（）号位置。
A.2kB.2k+1C.k/2下取整D.(k+1)/2下取整10.一下竞赛活动中历史最悠久的是（）A.全国青少年信息学奥林匹克联赛（NOIP）B.全国青少年信息学奥林匹克竞赛（NOI）C.国际信息学奥林匹克竞赛（IOI）D.亚太地区信息学奥林匹克竞赛（APIO）二.不定项选择题（共10题，每题1.5分，共计15分。
第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组 C++语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确选项。
）1．与十六进制数 A1.2等值的十进制数是（）A．101.2 B．111.4 C．161.125 D．177.252．一个字节（byte）由（）个二进制组成。
A．8 B．16 C．32 D．以上都有可能3．以下逻辑表达式的值恒为真的是（）。
A．P∨（┓P∧Q）∨(┓P∧┓Q) B．Q∨（┓P∧Q）∨（P∧┓Q）C．P∨Q∨（P∧┓Q）∨（┓P∧Q） D．P∨┓Q∨（P∧┓Q）∨(┓P∧┓Q)4．Linux下可执行文件的默认扩展名是( )。
A. exeB. comC. dllD. 以上都不是5．如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。
A. 100B. 144C. 164D. 1966．提出“存储程序”的计算机工作原理的是（）。
A. 克劳德•香农B. 戈登•摩尔C. 查尔斯•巴比奇D. 冯•诺依曼7．前缀表达式“+ 3 * 2 + 5 12 ”的值是（）。
A. 23B. 25C. 37D. 6 58．主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了( )。
A．寄存器 B．高速缓存 C．闪存 D．外存9．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（）号位置。
A．2k B．2k+1 C．k/2下取整 D．(k+1)/210．以下竞赛活动中历史最悠久的是（）。
NOIP2010第十六届初赛试题及答案(普及组Pascal)NOIP2010第十六届初赛试题及答案(普及组Pascal) PDF格式第十六届全国青少年信息学奥林匹克联赛初赛试题（普及组 Pascal 语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一. 单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确答案。
）1.2E＋03表示（）。
A.2.03B.5C.8D.20002.一个字节（byte）由（）个二进制位组成。
A.8B.16C.32D.以上都有可能3.以下逻辑表达式的值恒为真的是（）。
A.P∨(﹁P∧Q) ∨(﹁P∧﹁Q)B.Q∨(﹁P∧Q) ∨(P∧﹁Q)C. P∨Q∨(P∧﹁Q) ∨(﹁P∧Q)D.P∨﹁Q∨(P∧﹁Q) ∨(﹁P∧﹁Q)4.Linux下可执行文件的默认扩展名为（）。
A.exeC.dllD.以是都不是5.如果树根算是第1层，那么一棵n层的二叉树最多有（）结点。
A.2n-1B.2nC.2n+1D.2n+16.提出“存储程序”的计算机工作原理的是（）。
A.克劳德·香农B.戈登·摩尔C.查尔斯·巴比奇D.冯·诺依曼7.设X、Y、Z分别代表三进制下的一位数字，若等式XY＋ZX＝XYX在三进制下成立，那么同样在三进制下，等式XY×ZX＝（）也成立。
A.YXZB.ZXYC.XYZD.XZY9.前缀表达式“＋3×2＋5 12”的值是（）。
A.23B.25C.37D.6510.主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了（）。
A.寄存器B.高速缓存C.闪存D.外存11.一个字长为8位的整数的补码是11111001,则它的原码是（）。
第十六届全国青少年信息学奥林匹克联赛初赛试题试题及答案NOIP2010（Pascal提高组）一、单项选择题1.与16进制数 A1.2等值的10进制数是（）A.101.2B.111.4C.161.125D.177.252.一个字节（byte）由（）个二进制组成。
A.8B.16C.32D.以上都有可能3.以下逻辑表达式的值恒为真的是（）。
A.P∨（┓P∧Q）∨(┓P∧┓Q)B.Q∨（┓P∧Q）∨（P∧┓Q）C.P∨Q∨（P∧┓Q）∨（┓P∧Q）D.P∨┓Q∨（P∧┓Q）∨(┓P∧┓Q)4.Linux下可执行文件的默认扩展名是( )。
A. exeB. comC. dllD. 以上都不是5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。
A. 100B. 144C. 164D. 1966.提出“存储程序”的计算机工作原理的是（）。
A. 克劳德•香农B. 戈登•摩尔C. 查尔斯•巴比奇D. 冯•诺依曼7.前缀表达式“+ 3 * 2 + 512 ” 的值是（）。
A. 23B. 25C. 37D. 658.主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了( )。
A. 寄存器B. 高速缓存C. 闪存D. 外存9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（）号位置。
A. 2kB. 2k+1C. k/2下取整D. (k+1)/210. 以下竞赛活动中历史最悠久的是（）。
A. NOIPB. NOIC. IOID. APIO二、不定项选择题1.元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。
2004年第16届国际信息学奥赛试题解析（希腊）第一题阿耳特弥斯Day 1. Source file Artemis.*Available memory:16M. Maximum running time:1SZeus gave Artemis, the goddess of the wilderness, a rectangular area for growing a forest. With the left side of the area as a segment of the positive y-axis and the bottom side as a segment of the positive x-axis, and(0,0) the left bottom corner of the area, Zeus told Artemis to plant trees only on integer coordinate points in the area. Artemis liked the forest to look natural, and therefore planted trees in such a way that a line connecting two trees was never parallel to x-axis or y-axis.At times, Zeus wants Artemis to cut trees for him. The trees are to be cut as follows: 1．Zeus wants at least a given number T of trees to be cut for him.2．To get a rectangular football pitch for future football success, Artemis is to cut all trees within a rectangular area, and no trees outside of it.3．The sides of this rectangular area are to be parallel to x-axis and y-axis.4．Two opposite corners of the area must be located on trees and therefore those corner trees are also cut.As Artemis likes the trees, she wants to fulfill these conditions whilst cutting as few trees as possible. You are to write a program that, given information on the forest and the minimum number T of trees to be cut, selects an area for cutting trees for Artemis.INPUTThe input file name is artemis. in. The first line contains one integer N: the number of trees in the forest. The second line contains one integer T: the minimum number of trees to be cut. The following N lines describe the positions of the N trees. Each of these lines contains two integers X and Y: the x-coordinate followed by the y-coordinate of a tree.OUTPUTSseparated by one space: Artemis should use the Jth tree (with position given on line 1+2 of the input file) and Jth tree(with position given on line J+2 of the input file)as the corners of the area for cutting trees. The order of these two number is irrelevant. There may be several ways to choose these trees and you need to find and output one of them. For all test cases at least one solution exists.EXAMPLE INPUTS AND OUTPUTSartemis. in artemis. outIn all inputs, 1≤N≤20000, 0≤X, Y≤64000 and, 1<T≤N.Additionally, in 50% of the inputs, 1<N<5000参考译文：阿耳特弥斯（Day1文件名artemis. *内存限制：16MB，时间限制1s）问题描述：宙斯赠予女神阿耳特弥斯一片矩形的土地让其植树。
noip2022提高组初赛试题及答案第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组C语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一.单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确选项。
）1.与16进制数A1.2等值的10进制数是（）A.101.2B.111.4C.161.125D.177.252.一个字节（byte）由（）个二进制位组成。
A.8B.16C.32D.以上都有可能3.一下逻辑表达式的值恒为真的是（）A.P∨（┐P∧Q)∨（┐P∧┐Q)B.Q∨（┐P∧Q)∨(P∨┐Q)C.P∨Q∨(P∧┐Q)∨(┐P∧Q)D.P∨┐Q∨(P∧┐Q)∨(┐P∧┐Q)4.Linu某下可执行文件的默认扩展名为（）5.如果在某个进制下等式7某7=41成立，那么在该进制下等式12某12=（）也成立。
A.100B.144C.164D.1966.提出“存储程序”的计算机工作原理的是（）。
A.克劳德·香农B.戈登·摩尔C.查尔斯·巴比奇D.冯·诺依曼7.前缀表达式“+3某2+512”的值是（）A.23B.25C.37D.658.主存储器的存取速度比中央处理器（CPU）的工作速度慢很多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了（）A.寄存器B.高速缓存C.闪存D.外存9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右一次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置，则第K号结点的父结点如果存在的话，应当存放在数组的（）号位置。
A.2kB.2k+1C.k/2下取整D.(k+1)/2下取整10.一下竞赛活动中历史最悠久的是（）A.全国青少年信息学奥林匹克联赛（NOIP）B.全国青少年信息学奥林匹克竞赛（NOI）C.国际信息学奥林匹克竞赛（IOI）D.亚太地区信息学奥林匹克竞赛（APIO）二.不定项选择题（共10题，每题1.5分，共计15分。
第十六届全国青少年信息学奥林匹克联赛初赛试题（普及组 C++语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确选项。
）1．2E+03表示（）。
A. 2.03B. 5C. 8D. 20002．一个字节（byte）由（）个二进制位组成。
A. 8B. 16C. 32D. 以上都有可能3．以下逻辑表达式的值恒为真的是（）。
A. P∨(¬P∧Q)∨(¬P∧¬Q)B. Q∨(¬P∧Q)∨(P∧¬Q)C. P∨Q∨(P∧¬Q)∨(¬P∧Q)D. P∨¬Q∨(P∧¬Q)∨(¬P∧¬Q)4．Linux下可执行文件的默认扩展名为（）。
A. exeB. comC. dllD. 以上都不是5．如果树根算第1层，那么一棵n层的二叉树最多有（）个结点。
A. 2n-1B. 2nC. 2n+1D. 2n+16．提出“存储程序”的计算机工作原理的是（）。
A. 克劳德·香农B. 戈登·摩尔C. 查尔斯·巴比奇D. 冯·诺依曼7．设X、Y、Z分别代表三进制下的一位数字，若等式XY + ZX = XYX在三进制下成立，那么同样在三进制下，等式XY * ZX = （）也成立。
A. YXZB. ZXYC. XYZD. XZY8．Pascal语言、C语言和C++语言都属于（）。
A. 面向对象语言B. 脚本语言C. 解释性语言D. 编译性语言9．前缀表达式“+ 3 * 2 + 5 12”的值是（）。
A. 23B. 25C. 37D. 6510．主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
第十六届全国青少年信息学奥林匹克联赛初赛试题（普及组Pascal语言两小时完成）●●全部试题答案均要求卸载答卷纸上，写在试卷上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确选项。
）1.2E+03表示（）。
A.2.03B.5C.8D.20002.一个字节（byte）由（）个二进制组成。
A.8B.16C.32D.以上都有可能3.以下逻辑表达式的值恒为真的是（）。
A.P∨（┓P∧Q）∨(┓P∧┓Q)B.Q∨（┓P∧Q）∨（P∧┓Q）C.P∨Q∨（P∧┓Q）∨（┓P∧Q）D.P∨┓Q∨（P∧┓Q）∨(┓P∧┓Q)4.Linux下可执行文件的默认扩展名是()。
A.exeC.dll D.以上都不是5.如果树根算第1层，那么一颗n层的二叉树最多有（）个结点。
A.2n-1B.2nC.2n+1D. 2n+16.提出“存储程序”的计算机工作原理的是（）。
A.克劳德•香农B.戈登•摩尔C.查尔斯•巴比奇 D.冯•诺依曼7.设X、Y、Z分别代表三进制下的一个数字，若等式XY+ZX=XYX在三进制下成立，那么同样在三进制下，等式XY*ZX=()也成立。
A.YXZB.ZXYC.XYZ D.XZY8.Pascal语言、C语言和C++语言都属于（）。
A.面向对象语言B.脚本语言C.解释性语言D.编译性语言9.前缀表达式“+3*2+512”的值是（）。
A.23B.25C.37 D.6510.主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了()。
A.寄存器B.高速缓存C.闪存 D.外存11.一个字长为8位的整数的补码是11111001，则它的原码是（）。
A.00000111B.01111001C.11111001D.1000011112.基于比较的排序时间复杂度的下限是（），其中n表示待排序的元素个数。
第十六届全国青少年信息学奥林匹克联赛初赛试题（普及组 Pascal 语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷上一律无效●●CCF NOIP2010普及组（Pascal语言）参考答案与评分标准一、单项选择题（共20题，每题1.5分，共计30分）1 2 3 4 5 6 7 8 9 10D A A D A D B D C B11 12 13 14 15 16 17 18 19 20D B B B B A A D C D二、问题求解（共2题，每题5分，共计10分）1、2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6（或22123113431213536）2、49三、阅读程序写结果（共4题，每题8分，其中第4题（1）、（2）各4分，共计32分）1、2 20 77 912、99 101 1113、120 1124、（1）1（2）4四、完善程序（前4空，每空2.5分，后6空，每空3分，共计28分）（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）1、① tmp := true② p[j]③ p[r] := i④ p[j] + p[k]（或p[k] + p[j]）⑤10042、① num <= 2（或num < 3 或num = 2）②go(LEFT_TO_RIGHT)③pos[i] = LEFT（或LEFT = pos[i]）④ time[i] + go(RIGHT_TO_LEFT)（或go(RIGHT_TO_LEFT) + time[i]）⑤ pos[i] := LEFT本小题中，LEFT可用true代替，LEFT_TO_RIGHT可用true代替，RIGHT_TO_LEFT 可用false代替。
第十六届全国青少年信息学奥林匹克联赛初赛试题(普及组C++语言两小时完成)•• 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效••一、单项选择题(共20 题，每题1.5 分，共计30 分。
每题有且仅有一个正确选项。
) 1 ．2E+03 表示()。
A. 2.03B.5C.8D.20002．一个字节( byte )由()个二进制位组成。
A.8B.16C.32D. 以上都有可能3．以下逻辑表达式的值恒为真的是()。
A.P V (?P A Q) V (?P A ?Q)B.Q V (?P A Q) V (P A ?Q)C.P V QV (P A ?Q) V (?P A Q)D.P V ?Q V (P A ?Q) V (?P A ?Q)4．Linux 下可执行文件的默认扩展名为()。
A.exeC.dllD. 以上都不是5．如果树根算第1 层，那么一棵n 层的二叉树最多有()个结点。
A.2 n-1B.2 nC.2 n+1D.2 n+16．提出“存储程序”的计算机工作原理的是()。
A.克劳德•香农B.戈登•摩尔C.查尔斯•巴比奇D.冯•诺依曼7.设X、Y、Z分别代表三进制下的一位数字，若等式XY+ZX=XYX在三进制下成立，那么同样在三进制下，等式XY*ZX= ()也成立。
A.YXZB.ZXYC.XYZD.XZY8.Pascal 语言、C 语言和C+ +语言都属于()。
A. 面向对象语言B. 脚本语言C. 解释性语言D. 编译性语言9.前缀表达式“ +3*2+512 ”的值是()。
A.23B.25C.37D.6510•主存储器的存取速度比中央处理器( CPU)的工作速度慢得多，从而使得后者的效率受到影响。
而根据局部性原理，CPU 所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了()。
A. 寄存器B. 高速缓存C. 闪存D. 外存11.一个字长为8 位的整数的补码是，则它的原码是()。
全国青少年信息学奥林匹克联赛初赛试题普及组C++题目及答案(2)第十六届全国青少年信息学奥林匹克联赛初赛试题（普及组C++语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确选项。
）1．2E+03表示（）。
A. 2.03B. 5C. 8D. 20002．一个字节（byte）由（）个二进制位组成。
A. 8B. 16C. 32D. 以上都有可能3．以下逻辑表达式的值恒为真的是（）。
A. P∨(?P∨Q)∨(?P∨?Q)B. Q∨(?P∨Q)∨(P∨?Q)C. P∨Q∨(P∨?Q)∨(?P∨Q)D. P∨?Q∨(P∨?Q)∨(?P∨?Q)4．Linux下可执行文件的默认扩展名为（）。
A. exeB. comC. dllD. 以上都不是5．如果树根算第1层，那么一棵n层的二叉树最多有（）个结点。
A. 2n-1B. 2nC. 2n+1D. 2n+16．提出“存储程序”的计算机工作原理的是（）。
A. 克劳德·香农B. 戈登·摩尔C. 查尔斯·巴比奇D. 冯·诺依曼7．设X、Y、Z分别代表三进制下的一位数字，若等式XY + ZX = XYX在三进制下成立，那么同样在三进制下，等式XY * ZX = （）也成立。
A. YXZB. ZXYC. XYZD. XZY8．Pascal语言、C语言和C++语言都属于（）。
A. 面向对象语言B. 脚本语言C. 解释性语言D. 编译性语言9．前缀表达式“+ 3 * 2 + 5 12”的值是（）。
A. 23B. 25C. 37D. 6510．主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了（）。
第十六届全国青少年信息学奥林匹克联赛初赛试题(提高组Pascal 语言二小时完成 )••全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效••一．单项选择题 (共10 题，每题1.5 分，共计15 分。
每题有且仅有一个正确答案。
)1. 与16 进制数A1.2 等值的10 进制数是 ()A. 101.2B.111.4C.161.125D.177.252. 一个字节( byte )由( )个二进制组成。
A. 8B.16C.32D.以上都有可能3 .以下逻辑表达式的值恒为真的是( )。
A.P V(n P A Q)V (n P A n QB .Q V(n P A Q)V( P心Q)C.P V Q V( P A n Q)V(n P AD.Q) V n Q V( P A n Q)V (n P A n Q)4. Linux 下可执行文件的默认扩展名是( )。
A. exeB. comC. dllD.以上都不是5. 如果在某个进制下等式7*7=41 成立，那么在该进制下等式12*12= ( )也成立。
A. 100B. 144C. 164D. 1966. 提出“存储程序”的计算机工作原理的是( )。
A.克劳德？香农B.戈登？摩尔C.查尔斯？巴比奇D.冯？诺依曼7. 前缀表达式“+ 3 * 2 + 5 12 ” 的值是( )。
A. 23 B. 25 C. 37D. 658. 主存储器的存取速度比中央处理器（CPU）的工作速度慢的多，从而使得后者的效率受到影响。
而根据局部性原理，CPU 所访问的存储单元通常都趋于一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了（）。
A.寄存器 B.高速缓存 C.闪存 D.外存9. 完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。
假定根结点存放在数组的 1 号位置上，则第k 号结点的父结点如果存在的话，应当存放在数组中的（）号位置。
第六届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题(提高组参考答案)一、选择一个正确答案代码(A/B/C/D),填入每题的括号内(每题1.5分，多选无分，共30分)二、问题解答(第1题的第1问2分，第2问5分，第2题7分，两题共14分)1.答：有5种不同形态的二叉树可以得到这一遍历结果；可画出的这些二叉树为：2. 用递推公式给出的某人从底层开始走完全部楼梯的走法为(用F(N))记录不同案数：F(1)=1 F(2)=2 F(3)=4 F(N)=F(N-3)+F(N-2)+F(N-1) (N≥4)三、阅读程序，并写出程序的正确运行结果：(10分，共20分)(1)程序的运行结果是：4 3 0 2(2)程序的运行结果是：BBAC四、根据题意，将程序补充完整(每个点3分，共30分)第七届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题(提高组参考答案)一、选择一个正确答案代码(A/B/C/D)，填入每题的括号内(每题1.5分，多选无分，共30分)二、问题解答(5+7分，两题共12分)1.答：该二叉树先序遍历的顺序为：ABCEGDFHIJ2.答：用这些点为顶点，能组成2250个不同四边形三、阅读程序，并写出程序的正确运行结果：(4+7+8+9分，共28分)(1)程序的运行结果是：125(2)程序的运行结果是：181 110 87 76 66 62 61 60(3)程序的运行结果是：1348(4)程序的运行结果是：153四、根据题意，将程序补充完整(每个点3分，共30分)题一① SP：=SP+1② I：=I -1③ DK[I，2]+L+DK[I+1，2]④ D⑤ DK[I+1，1]题二① READLN(X，Y，W)② R[J，I]+EET[J]>MAX③ ET[N]：=EET[N]；④ ET[J]-R[I，J]<MIN⑤ EET[I]=ET[I]第八届全国青少年信息学奥林匹克联赛初赛试题提高组一、选择题二、问题解答1、442、N0 = (K－1) Nk +1三、读程序写结果1、RRRRWWBBBB2、300313、15.00(PASCAL) 15(BASIC)四、补充程序题一：1、c[n+1]2、(yu+d[j1]<c[j1+1])3、yu:=yu+d[j1];4、e[j0]:=s;5、write(e[I]:4);题二：1、P AND (B[0]=0)2、B[J]：=1；3、P：=FALSE；4、（A[I，J]=－1） AND （B[J]=1）5、P第九届全国青少年信息学奥林匹克联赛初赛试题提高组参考答案一、单项选择题（共10题，每题1.5分，共计15分。
第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一．单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确答案。
）1.与16进制数 A1.2等值的10进制数是（）A.101.2B.111.4C.161.125D.177.252.一个字节（byte）由（）个二进制组成。
A.8B.16C.32D.以上都有可能3.以下逻辑表达式的值恒为真的是（）。
A.P∨（┓P∧Q）∨(┓P∧┓Q)B.Q∨（┓P∧Q）∨（P∧┓Q）C.P∨Q∨（P∧┓Q）∨（┓P∧Q）D.P∨┓Q∨（P∧┓Q）∨(┓P∧┓Q)4.Linux下可执行文件的默认扩展名是( )。
A. exeB. comC. dllD.以上都不是5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。
A. 100B. 144C. 164D. 1966.提出“存储程序”的计算机工作原理的是（）。
A. 克劳德•香农B.戈登•摩尔C.查尔斯•巴比奇D.冯•诺依曼7.前缀表达式“+ 3 * 2 + 512 ” 的值是（）。
A. 23 B. 25 C. 37 D. 658.主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了( )。
A.寄存器 B.高速缓存 C.闪存 D.外存9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（）号位置。
A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/210.以下竞赛活动中历史最悠久的是（）。
A. NOIP B.NOI C. IOI D. APIO二．不定项选择题（共10题，每题1.5分，共计15分。
每题正确答案的个数不少于1。
多选或少选均不得分）。
1.元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。
如果第1个出栈的是R3，那么第5个出栈的可能是( )。
A.R1 B.R2 C.R4 D.R52. Pascal语言，C语言和C++语言都属于( )。
A.高级语言 B.自然语言 C.解释性语言 D.编译性语言3. 原地排序是指在排序过程中(除了存储待排序元素以外的)辅助空间的大小与数据规模无关的排序算法。
以下属于原地排序的有( )。
A.冒泡排序 B.插入排序 C.基数排序 D.选择排序4. 在整数的补码表示法中，以下说法正确的是（）。
A．只有负整数的编码最高位为1 B．在编码的位数确定后，所能表示的最小整数和最大整数的绝对值相同C．整数0只有一个唯一的编码D．两个用补码表示的数相加时，若在最高位产生进位，则表示运算溢出5. 一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（）。
A．0 B. 2 C. 4 D. 66. 在下列HTML语句中，可以正确产生一个指向NOI官方网站的超链接的是（）。
A．<a url=”h t t p : / / w w w . n o i . c n”>欢迎访问NOI网站</a>B．<a href=”h t t p : / / w w w . n o i . c n”>欢迎访问NOI网站</a>C．<a>h t t p : / / w w w . n o i . c n</a>D．<a name”h t t p : / / w w w . n o i . c n”>欢迎访问NOI网站</a>7. 关于拓扑排序，下列说法正确的是( )。
A．所有连通的有向图都可以实现拓扑排序B．对同一个图而言，拓扑排序的结构是唯一的C．拓扑排序中入度为0的结点总会排在入度大于0的结点的前面D．拓扑排序结果序列中的第一个结点一定是入度大于0的点8. 一个平面的法线是指与该平面垂直的直线。
过点(1,1,1)、（0,3,0）、(2,0,0)的平面的法线是（）。
A．过点（1，1，1）、（2，3，3）的直线B．过点（1，1，1）、（3，2，1）的直线C．过点（0，3，0）、（-3，1，1）的直线D．过点（2，0，0）、（5，2，1）的直线9.双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。
设p指向链表中的一个结点，他的左右结点均为非空。
现要求删除结点p，则下列语句序列中正确的是( )。
A．p->rlink->llink=p->rlink;p->llink->rlink=p->llink; delete p;B．p->llink->rlink=p->rlink;p->rlink->llink = p->llink; delete p;C．p->rlink->llink = p->llink;p->rlink->llink ->rlink = p->rlink; delete p;D．p->llink->rlink = p->rlink;p->llink->rlink->link = p->llink; delete p;10. 今年(2010年)发生的事件有（）。
A．惠普实验室研究员Vinay Deolalikar 自称证明了P≠NPB．英特尔公司收购计算机安全软件公司迈克菲(McAfee)C．苹果公司发布iPhone 4手机D．微软公司发布Windows 7 操作系统三、问题求解1．LZW编码是一种自适应词典编码。
在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。
举例说明，考虑一个待编码的信息串：“xyx yy yy xyx”。
初始词典只有3个条目，第一个为x,编码为1；第二个为y，编码为2；第三个为空格，编码为3；于是串“xyx”的编码为1-2-1（其中-为编码分隔符），加上后面的一个空格就是1-2-1-3。
但由于有了一个空格，我们就知道前面的“xyx”是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里，编码为4，然后按照新的词典对后继信息进行编码，以此类推。
于是，最后得到编码：1-2-1-3-2-2-3-5-3-4。
我们可以看到，信息被压缩了。
压缩好的信息传递到接受方，接收方也只要根据基础词典就可以完成对该序列的完全恢复。
解码过程是编码过程的逆操作。
现在已知初始词典的3个条目如上述，接收端收到的编码信息为2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，则解码后的信息串是”____________”。
2.无向图G有7个顶点，若不存在由奇数条边构成的简单回路，则它至多有__________条边。
3.记T为一队列，初始时为空，现有n个总和不超过32的正整数依次入列。
如果无论这些数具体为何值，都能找到一种出队的方式，使得存在某个时刻队列T中的数之和恰好为9，那么n的最小值是___________。
四、阅读程序写结果1.constsize = 10;vari, j, cnt, n, m : integer;data : array[1..size] of integer; beginreadln(n, m);for i := 1 to n doread(data[i]);for i := 1 to n dobegincnt := 0;for j := 1 to n doif (data[i] < data[j]) or ((data[j] = data[i]) and (j < i))then inc(cnt);if cnt = mthen writeln(data[i]);end;end.输入5 296 -8 0 16 87输出：__________2.constsize = 100;varna, nb, i, j, k : integer;a, b : array[1..size] of integer; beginreadln(na);for i := 1 to na doread(a[i]);readln(nb);for i := 1 to nb doread(b[i]);i := 1;j := 1;while (i <= na) and (j <= nb) dobeginif a[i] <= b[j] thenbeginwrite(a[i],' ');inc(i);endelse beginwrite(b[j], ' ');inc(j);end;end;if i <= na thenfor k := i to na dowrite(a[k], ' ');if j <= nb thenfor k := j to nb dowrite(b[k], ' '); end.输入51 3 5 7 942 6 10 14输出：__________3.constnum = 5;varn: integer;function r(n : integer) : integer;vari : integer;beginif n <= num thenbeginr := n;exit;end;for i :=1 to num doif r(n-i) < 0 thenbeginr:=i;exit;end;r:=-1;end;beginreadln(n);writeln(r(n));end.输入 16输出：__________4.constsize=100;varn,m,x,y,i :integer;r: array[1.. size] of integer;map : array[1..size, 1..size] of boolean;found : boolean;function successful : boolean;vari : integer;beginfor i :=1 to n doif not map[r[i]][r[i mod n + 1]]then beginsuccessful := false;exit;end;successful :=true;end;procedure swap(var a, b : integer);vart : integer;begint := a;a := b;b := t;end;procedure perm(left, right : integer);vari : integer;beginif foundthen exit;if left > rightthen beginif successfulthen beginfor i := 1 to n dowriteln(r[i], ' ');found := true;end;exit;end;for i:= left to right dobeginswap(r[left], r[i]);perm(left + 1, right);swap(r[left], r[i]);end;end;beginreadln(n, m);fillchar(map, sizeof(map), false);for i := 1 to m dobeginreadln(x, y);map[x][y] := true;map[y][x] := true;end;for i := 1 to n dor[i] := i;found := false;perm(1, n);if not foundthen writeln('Nosoloution');end.输入:9 121 22 33 44 55 66 11 72 73 84 85 96 9输出：__________五、完善程序1.(过河问题) 在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N(2<=N<1000)和这N 个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸.例如,有3个人甲、乙、丙,他们单独过桥的时间分别为1 2 4,则总共最少需要的时间为7.具体方法是:甲乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲,丙在一起过桥到河的左岸,总时间为2+1+4=7. constSIZE = 100;INFINITY = 10000;LEFT = true;RIGHT = false;LEFT_TO_RIGHT = true;RIGHT_TO_LEFT = false;varn, i : integer;time : array[1..Size] of integer;pos :array[1..Size] of Boolean; function max(a, b :integer) : integer; beginif a > b thenmax := aelsemax := b;end;function go(stage : boolean) : integer;vari, j, num, tmp, ans : integer; beginif (stage = RIGHT_TO_LEFT)then beginnum := 0;ans :=0;for i := 1 to n doif pos[i] = Rignt thenbegininc(num);if time[i] > ans thenans :=time[i];end;if __________ thenbegingo := ans;exit;end;ans := INFINITY;for i := 1 to n – 1 doif pos[i] = RIGHT thenfor j := i+1 to n doif pos[j] = RIGHT thenbeginpos[i] := LEFT;pos[j] := LEFT;tmp := max(time[i], time[j]) + _______;if tmp < ans thenans := tmp;pos[i] := RIGHT;pos[j] := RIGHT;end;go := ans;endelse if (stage = LEFT_TO_RIGHT)then beginans := INFINITY;for i := 1 to n doif _______ thenbeginpos[i] := RIGHT;tmp := ________;if tmp < ans thenans := tmp;_________;end;go := ans;endelse go := 0;end;beginreadln(n);for i := 1 to n dobeginread(time[i]);pos[i] := RIGHT;end;writeln(go(RIGHT_TO_LEFT));end.2．（烽火传递）烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。
