下载文档原格式
第二十四届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2018年10月13日14:30~16:30选手注意：●试题纸共有7页，答题纸共有2页，满分100分。
请在答题纸上作答，写在试题纸上的一律无效。
●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）1.以下哪一种设备属于输出设备：（）A.扫描仪B.键盘C.鼠标D.打印机解析：这是一道送分题，会就会，不会就不会。
所以选D。
2.下列四个不同进制的数中，与其它三项数值上不相等的是（）。
A.(269)16B.(617)10C.(1151)8D．(1001101011)2解析：这题考核的是进制转换。
（269）16=2*16^2+6*16^1+9*16^0=617，(1151)8=1*8^3+1* 8^2+5*8^1+1*8^0=617，而(1001101011)2=619。
所以选D。
3.1MB等于（）。
A.1000字节B.1024字节C.1000X1000字节D.1024X1024字节1KB=1024B1MB=1024KB解析：这题考核的是字节之间的转换。
1MB=1024KB=1024*1024B。
所以选D。
4.广域网的英文缩写是（）。
NB．WANC．MAND．LNA解析：这题是送命题，，会就会，不会就不会。
WAN全称为Wide Area Network。
所以选B。
5.中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。
A.1983B.1984C.1985D.1986解析：这题是送命题，会就会，不会就不会。
NOI是全国青少年信息学奥林匹克竞赛(National Olympiad in Informatics)的简称。
NOI是国内包括港澳在内的省级代表队最高水平的大赛，自1984年至今，在国内包括香港、澳门组织竞赛活动。
所以选B。
6.如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第81个字符是字母（）。
NOIP提高组初赛历年试题及答案选择题篇单项选择题（共10-15题，每题1.5分，共计15-22.5分。
每题有且仅有一个正确选项。
）注：答案在末尾NOIP2011-1.在二进制下，1011001+（）=1100110。
同普及组NOIP2011-1 A.1011 B.1101 C.1010 D.1111NOIP2011-2.字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。
A.66B.5AC.50D.视具体的计算机而定NOIP2011-3.下图是一棵二叉树，它的先序遍历是（）。
A.ABDEFCB.DBEFACC.DFEBCAD.ABCDEFNOIP2011-4.寄存器是（）的重要组成部分。
同普及组NOIP2011-6A.硬盘B.高速缓存C.内存D.中央处理器（CPU）NOIP2011-5.广度优先搜索时，需要用到的数据结构是（）。
同普及组NOIP2011-11A.链表B.队列C.栈D.散列表NOIP2011-6.在使用高级语言编写程序时，一般提到的“空间复杂度”中的空间是指（）。
同普及组NOIP2011-12A.程序运行时理论上所占的内存空间B.程序运行时理论上所占的数组空间C.程序运行时理论上所占的硬盘空间D.程序源文件理论上所占的硬盘空间NOIP2011-7.应用快速排序的分治思想，可以实现一个求第K大数的程序。
假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。
A.O(n2) B.O(n log n) C.O(n) D.O(1)NOIP2011-8.为解决web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。
A.微软B.美国计算机协会（ACM）C.联合国教科文组织D.万维网联盟（W3C）NOIP2011-9.体育课的铃声响了，同学们都陆续的奔向操场，按老师的要求从高到低站成一排。
贪心算法贪心算法是一种用来求最优解的算法，主要思想是将问题分为数个步骤，用一个贪心标准逐步求出每一步骤的最优解，最终产生全局最优解。
贪心算法的优点是效率高，缺点是最终产生的解不一定是最优解。
1.均分纸牌（NOIP2002提高组第1题）问题描述：有 N 堆纸牌，编号分别为 1，2，…, N。
每堆上有若干张，但纸牌总数必为 N 的倍数。
可以在任一堆上取若干张纸牌，然后移动。
移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求用最少的移动次数S使每堆上纸牌数都一样多。
输入格式：Na[1], a[2], …, a[N]输出格式：S算法分析：从第1堆到第N堆纸牌，按从左到右的顺序，若第i堆纸牌数a[i]大于平均数k，则将多出的纸牌移到第i+1堆上；若a[i]小于k，则将缺少的纸牌数移到第i+1堆上（缺少的纸牌数可由右侧传递给左侧，次数相同）。
例：n=4 a[1..4] = 4 6 10 84 ——〉 6 ——〉 10 ——〉 8-3 -4 -1（等于右给左2）（右给左4）（右给左1）源程序：Vara: Array[1..100]Of Integer;i, n, t, s: Integer;BeginReadLn(n);For i := 1 To n Do Read(a[i]);For i := 1 To n Do t := t + a[i];t := t Div n; {求平均数}For i := 1 To n-1 DoIf a[i] <> t ThenBeginInc(s); {计数}a[i+1] := a[i+1] + (a[i] - t);End;WriteLn(s);End.在用贪心算法解题时，需要注意两方面，一是问题是否适用于贪心算法，二是应选用怎样的贪心标准。
题目：贪心算法、分治算法、动态规划算法间的比较贪心算法：贪心算法采用的是逐步构造最优解的方法。
在每个阶段，都在一定的标准下做出一个看上去最优的决策。
决策一旦做出，就不可能再更改。
做出这个局部最优决策所依照的标准称为贪心准则。
分治算法：分治法的思想是将一个难以直接解决大的问题分解成容易求解的子问题，以便各个击破、分而治之。
动态规划：将待求解的问题分解为若干个子问题，按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。
在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。
依次解决各子问题，最后一个子问题就是初始问题的解。
二、算法间的关联与不同1、分治算法与动态规划分治法所能解决的问题一般具有以下几个特征：①该问题的规模缩小到一定程度就可以容易地解决。
②该问题可以分为若干个较小规模的相似的问题，即该问题具有最优子结构性质。
③利用该问题分解出的子问题的解可以合并为该问题的解。
④该问题所分解出的各个子问题是相互独立的且子问题即之间不包含公共的子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是分治法应用的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划算法；第四条特征涉及到分治法的效率，如果各个子问题不是独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。
这类问题虽然可以用分治法解决，但用动态规划算法解决效率更高。
当问题满足第一、二、三条，而不满足第四条时，一般可以用动态规划法解决，可以说，动态规划法的实质是：分治算法思想+解决子问题冗余情况2、贪心算法与动态规划算法多阶段逐步解决问题的策略就是按一定顺序或一定的策略逐步解决问题的方法。
