NOIP2009 - 2016普及组初赛试题 答案C++

第十五届全国青少年信息学奥林匹克联赛初赛试题

（ 普及组 C++语言 二小时完成 ）

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

一． 单项选择题 （共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。）

1、 关于图灵机下面的说法哪个是正确的：

A) 图灵机是世界上最早的电子计算机。

B) 由于大量使用磁带操作，图灵机运行速度很慢。

C) 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。 D) 图灵机只是一个理论上的计算模型。

2、关于计算机内存下面的说法哪个是正确的：

A) 随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随

机而不确定的。

B) 1MB内存通常是指1024*1024字节大小的内存。

C) 计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）

三个部分。

D) 一般内存中的数据即使在断电的情况下也能保留2个小时以上。

3、关于BIOS下面说法哪个是正确的：

A) BIOS是计算机基本输入输出系统软件的简称。

B) BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。 C) BIOS一般由操作系统厂商来开发完成。

D) BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

4、关于CPU下面哪个说法是正确的：

A) CPU全称为中央处理器（或中央处理单元）。 B) CPU可以直接运行汇编语言。

C) 同样主频下，32位的CPU比16位的CPU运行速度快一倍。 D) CPU最早是由Intel公司发明的。

5、关于ASCII，下面哪个说法是正确的：

A) ASCII码就是键盘上所有键的唯一编码。

B) 一个ASCII码使用一个字节的内存空间就能够存放。

C) 最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。 D) ASCII码是英国人主持制定并推广使用的。

6、下列软件中不是计算机操作系统的是：

A) Windows B) Linux C) OS/2 D) WPS

7、关于互联网，下面的说法哪一个是正确的：

A) 新一代互联网使用的IPv6标准是IPv5标准的升级与补充。 B) 互联网的入网8主机如果有了域名就不再需要IP地址。 C) 互联网的基础协议为TCP/IP协议。

D) 互联网上所有可下载的软件及数据资源都是可以合法免费使用的。

8、关于HTML下面哪种说法是正确的：

A） HTML实现了文本、图形、声音乃至视频信息的统一编码。 B） HTML全称为超文本标记语言。

C） 网上广泛使用的 Flash动画都是由HTML编写的。 D） HTML也是一种高级程序设计语言。

9、关于程序设计语言，下面哪个说法是正确的：

A) 加了注释的程序一般会比同样的没有加注释的程序运行速度慢。

B) 高级语言开发的程序不能使用在低层次的硬件系统如：自控机床或低端手机上。 C) 高级语言相对于低级语言更容易实现跨平台的移植。 D) 以上说法都不对。

10、已知大写字母A的ASCII编码为65（10进制），则大写字母J的10进制ASCII编码为：

A) 71 B) 72 C) 73 D) 以上都不是

11、十进制小数125.125对应的8进制数是

A) 100.1 B) 175.175 C) 175.1 D) 100.175

12、有六个元素FEDCBA 从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下

列哪一个不可能是合法的出栈序列？

A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF

13、 表达式a*(b+c)-d的后缀表达式是：

A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd

14、一个包含n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为：

A) 2n + 1 B) 2n-1 C) n-1 D) n+1

15、快速排序最坏情况下的算法时间复杂度为：

A) O(log2n) B) O(n) C) O(nlog2n) D) O(n2)

16. 有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找

定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素： A) 11次 B) 12次 C) 13次 D) 14次

17、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排

序算法是不稳定的：

A) 冒泡排序 B) 插入排序 C) 归并排序 D) 快速排序

18、已知n个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），

则该图中最少有多少条有向边？

A) n B) n+1 C) n-1 D) n*(n-1)

19、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资

源，请问全国信息学奥林匹克官方网站的网址是： A) http://www.noi.com/ B) http://www.noi.org/ C) http://www.noi.cn/ D) http://www.xinxixue.com/

20、在参加NOI系列竞赛过程中，下面哪一种行为是 不 被严格禁止的：

A) 携带书写工具，手表和不具有通讯功能的电子词典进入赛场。

B) 在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。 C) 通过互联网搜索取得解题思路。

D) 在提交的程序中启动多个进程以提高程序的执行效率。

二．问题求解（共2题，每空5分，共计10分）

1．小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如??a2->b2->a3->b3??是合法的，而??a2->b3->a3->b2??是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有 种。

2．有如下的一段程序：

1. 2. 3. 4. 5. 6. 7.

a=1; b=a; d=-a; e=a+d; c=2*d; f=b+e-d; g=a*f+c;

现在要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在 单

位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。

三．阅读程序写结果（共4题，每题8分，共计32分） 1．

#include using namespace std;

int a,b;

int work(int a,int b){ if (a%b)

return work(b,a%b);

return b; }

int main(){ cin >> a >> b;

cout << work(a,b) << endl; return 0; }

输入：20 12 输出：_______ 2．

#include using namespace std; int main() {

int a[3],b[3]; int i,j,tmp;

for (i=0;i<3;i++)

cin >> b[i];

for (i=0;i<3;i++) { } tmp=1;

for (i=0;i<3;i++) { }

cout << tmp << endl; return 0; }

a[i]%=10; b[i]%=10; tmp*=a[i]+b[i]; a[i]=0;

for (j=0;j<=i;j++) { }

a[i]+=b[j]; b[a[i]%3]+=a[j];

输入：2 3 5 输出：_______ 3．

#include using namespace std;

const int c=2009;

int main() {

int n,p,s,i,j,t; cin >> n >> p; s=0;t=1;

for(i=1;i<=n;i++) { }

cout << s << endl; return 0; }

t=t*p%c;

for(j=1;j<=i;j++)

s=(s+t)%c;

输入：11 2 输出： 4．

#include using namespace std;

const int maxn=50; void getnext(char str[]) {

int l=strlen(str),i,j,k,temp; k=l-2;

while(k>=0&&str[k]>str[k+1]) k--; i=k+1;

while(istr[k]) i++; temp=str[k]; str[k]=str[i-1]; str[i-1]=temp; for(i=l-1;i>k;i--)

}

for(j=k+1;j

if(str[j]>str[j+1]) { }

temp=str[j]; str[j]=str[j+1]; str[j+1]=temp;

return ;

int main() {

char a[maxn]; int n;

cin >> a >> n; while(n>0) { }

cout << a << endl; return 0; }

getnext(a); n--;

输入：NOIP 3 输出：

四．完善程序 (前8空，每空3分，后2空，每空2分，共28分) 1．（最大连续子段和）给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为4，-5，3，2，4时，输出9和3；数列为1 2 3 -5 0 7 8时，输出16和7。

#include using namespace std;

int a[101];

int n,i,ans,len,tmp,beg;

int main(){ cin >> n;

for (i=1;i<=n;i++)

cin >> a[i];

tmp=0; ans=0; len=0;

beg= ① ; for (i=1;i<=n;i++){ }

cout << ans << \ return 0; }

if (tmp+a[i]>ans){ }

else if ( ② &&i-beg>len) } else

⑤ ; len=i-beg; beg= ④ ; tmp=0;

if (tmp+a[i] ③ ){

ans=tmp+a[i]; len=i-beg;

2. (国王放置) 在n*m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x,y)格，国王的攻击的区域是:(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。读入三个数n,m,k，输出答案。题目利用回溯法求解。棋盘行标号为0~n-1，列标号为0~m-1。

#include using namespace std;

int n,m,k,ans; int hash[5][5];

void work(int x,int y,int tot){ int i,j; if (tot==k){ } do{

while (hash[x][y]){

y++; if (y==m){ ans++; return;

}

}

x++;

y= ① ; }

if (x==n)

return;

for (i=x-1;i<=x+1;i++)

if (i>=0&&i

for (j=y-1;j<=y+1;j++)

if (j>=0&&j

② ;

③ ;

for (i=x-1;i<=x+1;i++)

if (i>=0&&i

for (j=y-1;j<=y+1;j++)

if (j>=0&&j

④ ;

y++; }

if (y==m){

x++; y=0;

if (x==n)

return;

while (1); }

int main(){

cin >> n >> m >> k; ans=0;

memset(hash,0,sizeof(hash)); ⑤ ;

cout << ans << endl; return 0; }

答案部分

NOIP2009年普及组（C++语言）参考答案与评分标准

一、单项选择题：（每题1.5分）

1. D 2. B 3. A 4. A 5. B 6. D 7. C 8. B 9. C 10. D 11. C 12. C

13. B 14. D 15. D

16. B 17. D 18. A 19. C 20. B 二、问题求解：（共2题，每空5分，共计10分） 1．70 2．5

三、阅读程序写结果（共4题，每题8分，共计32分） 1. 4 2. 416 3. 782 4. NPOI

四．完善程序 (前8空，每空3分，后2空，每空2分，共28分)

（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查） 1. ① 0

② tmp+a[i]==ans 或者 a[i]+tmp==ans 或者ans==a[i]+tmp等 ③ <0 ④ i

⑤ tmp+=a[i] 或者 tmp=tmp+a[i] 2. ① 0

② hash[i][j]++ 或者 hash[i][j]= hash[i][j]+1 或者 ++hash[i][j]

③ work(x,y,tot+1)

④ hash[i][j]-- 或者 hash[i][j]= hash[i][j]-1 或者--hash[i][j] ⑤ work(0,0,0)

注意：② ④ 两空，不一定要++ 或者 - -。也可以是④ - - , ② ++. 也可以是 += k , 也可以 -= k, 甚至任何加标记的操作(如位运算)都可以，只要相互撤销。（所以答案非常多）。

第十六届全国青少年信息学奥林匹克联赛初赛试题

（ 普及组 C++语言 两小时完成 ）

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

一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。）

1．2E+03表示（ ）。

A. 2.03 B. 5 C. 8 D. 2000

2．一个字节（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. exe B. com C. dll D. 以上都不是

5．如果树根算第1层，那么一棵n层的二叉树最多有（ ）个结点。 A. 2n-1 B. 2n C. 2n+1 D. 2n+1

6．提出“存储程序”的计算机工作原理的是（ ）。

A. 克劳德·香农 B. 戈登·摩尔 C. 查尔斯·巴比奇 D. 冯·诺依曼

7．设X、Y、Z分别代表三进制下的一位数字，若等式XY + ZX = XYX在三进制下成立，那么同样在三进制下，等式XY * ZX = （ ）也成立。

A. YXZ B. ZXY C. XYZ D. XZY

8．Pascal语言、C语言和C++语言都属于（ ）。

A. 面向对象语言 B. 脚本语言 C. 解释性语言 D. 编译性语言

9．前缀表达式“+ 3 * 2 + 5 12”的值是（ ）。

A. 23 B. 25 C. 37 D. 65

10．主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了（ ）。 A. 寄存器 B. 高速缓存 C. 闪存 D. 外存

11．一个字长为8位的整数的补码是11111001，则它的原码是（ ）。

A. 00000111 B. 01111001 C. 11111001 D. 10000111

12．基于比较的排序时间复杂度的下限是（ ），其中n表示待排序的元素个数。 A. Θ(n) B. Θ(n log n) C. Θ(log n) D. Θ(n2)

13．一个自然数在十进制下有n位，则它在二进制下的位数与（ ）最接近。 A. 5n B. n*log210 C. 10*log2n D. 10nlog2n

14．在下列HTML语句中，可以正确产生一个指向NOI官方网站的超链接的是（ ）。 A. B. C. http://www.noi.cn

D.

15．元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的不可能是（ ）。

A. R1 B. R2 C. R4 D. R5

16．双向链表中有两个指针域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->llink = p->llink; delete p;

17．一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（ ）。

A. 2 B. 3 C. 4 D. 5

18．关于拓扑排序，下面说法正确的是（ ）。 A. 所有连通的有向图都可以实现拓扑排序 B. 对同一个图而言，拓扑排序的结果是唯一的

C. 拓扑排序中入度为0的结点总会排在入度大于0的结点的前面 D. 拓扑排序结果序列中的第一个结点一定是入度为0的点

19．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的（ ）号位置。

A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2下取整

20．全国青少年信息学奥林匹克系列活动的主办单位是（ ）。

A. 教育部 B. 科技部 C. 共青团中央 D. 中国计算机学会

二、问题求解（共2题，每题5分，共计10分）

1．LZW编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。

举例说明，考虑一个待编码的信息串：\。初始词典只有3个条目，第一个为x，编码为1；第二个为y，编码为2；第三个为空格，编码为3；于是串\的编码为1-2-1（其中-为编码分隔符），加上后面的一个空格就是1-2-1-3。但由于有了一个空格，我们就知道前面的\是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里，编码为4，然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码：1-2-1-3-2-2-3-5-3-4。

现在已知初始词典的3个条目如上述，则信息串\的编码是_________。

2．队列快照是指在某一时刻队列中的元素组成的有序序列。例如，当元素1、2、3入队，元素1出队后，此刻的队列快照是\3\。当元素2、3也出队后，队列快照是\，即为空。现有3个正整数元素依次入队、出队。已知它们的和为8，则共有_________种可能的不同的队列快照（不同队列的相同快照只计一次）。例如，\、\、\都是可能的队列快照；而\不是可能的队列快照，因为剩下的2个正整数的和不可能是1。

三、阅读程序写结果（共4题，每题8分，其中第4题（1）、（2）各4分，共计32分）

1．

#include using namespace std;

void swap(int & a, int & b) {

int t; t = a; a = b; b = t; }

int main() {

int a1, a2, a3, x;

cin>>a1>>a2>>a3; if (a1 > a2) swap(a1, a2); if (a2 > a3) swap(a2, a3); if (a1 > a2) swap(a1, a2);

cin>>x; if (x < a2) if (x < a1)

cout< cout<

if (x < a3)

cout<

cout<

}

if ( ① ) return ans; ans = INFINITY;

for (i = 1; i <= n - 1; i++) if (pos[i] == RIGHT)

for (j = i + 1; j <= n; j++) if (pos[j] == RIGHT) { pos[i] = LEFT; pos[j] = LEFT;

tmp = max(hour[i], hour[j]) + ② ; if (tmp < ans) ans = tmp; pos[i] = RIGHT; pos[j] = RIGHT; } return ans; }

if (stage == LEFT_TO_RIGHT) { ans = INFINITY;

for (i = 1; i <= n; i++) if ( ③ ) { pos[i] = RIGHT; tmp = ④ ; if (tmp < ans) ans = tmp; ⑤ ; } return ans; }

return 0; }

int main() {

int i; cin>>n;

for (i = 1; i <=n; i++) { cin>>hour[i]; pos[i] = RIGHT; }

cout<

NOIP2010 年普及组（C++语言）参考答案与评分标准

一、单项选择题：（每题1.5 分） 1 2 3 4 5 6 7 8 9 10 D A A D A D B D C B 11 12 13 14 15 16 17 18 19 20 D 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 分，共计32 分） 1．2 20 77 91 2．99 101 111 3．120 112 4．（1）1 （2）4

四、完善程序（前4 空，每空2.5 分，后6 空，每空3 分，共计28 分） （说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，

不一定上报科学委员会审查） 1．

① tmp=true

② p[j] ③ p[r]=i ④ p[j]+p[k] ⑤ 1004

本小题中，LEFT 可用true 代替，LEFT_TO_RIGHT 可用true 代替，RIGHT_TO_LEFT 可用false 代替。 2．

① num <= 2（或num < 3 或num = 2） ② go(LEFT_TO_RIGHT)

③ pos[i] = =LEFT（或LEFT = pos[i]）

④ hour[i] + go(RIGHT_TO_LEFT)（或go(RIGHT_TO_LEFT) +hour[i]） ⑤ pos[i] = LEFT

本小题中，LEFT 可用true 代替，LEFT_TO_RIGHT 可用true 代替，RIGHT_TO_LEFT 可用false 代替。

第十八届全国青少年信息学奥林匹克联赛初赛

（普及组C++语言试题）

竞赛时间：2012年10月13日14:30~16:30

选手注意： ? ?

试题纸共有10页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上一律无效。

不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料

一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项） 1．计算机如果缺少（A ），将无法正常启动。 1 A 11 B

A．内存

B．鼠标

C． U盘

D． 摄像头

2 B 12 D 3 A 13 B 4 B 14 C 5 C 15 C 6 C 16 D 7 B 17 C 8 C 18 A 9 A 19 C 10 A 20 B 2．（ B ）是一种先进先出的线性表。 A．栈

B．队列 C．哈希表（散列表） D．二叉树

3．目前计算机芯片（集成电路）制造的主要原料是（ A），它是一种可以在沙子中提炼出的物质。

A．硅

B．铜 C．锗

D．铝

4．十六进制数9A在（ B ）进制下是232。 A．四

5．（ C）不属于操作系统。 A．Windows

B．DOS

C．Photoshop

D．NOI Linux

B．八

C．十

D．十二

6．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（ C）。 A．ABC

B．CBA

C．ACB

D．BAC

7． 目前个人电脑的（ B ）市场占有率最靠前的厂商包括Intel、AMD等公司。 A．显示器

B．CPU

C．内存

D．鼠标

8． 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列 5，4，3，2，1需要执行（ C）次操作，才能完成冒泡排序。 A．0

B．5

C．10

D．15

9． 1946年诞生于美国宾夕法尼亚大学的ENIAC属于（ A ）计算机。 A．电子管

B．晶体管

C．集成电路

D．超大规模集成电路

10． 无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（ A ）。 A． 中国公司的经理与波兰公司的经理交互商业文件

B． 军队发布命令

C． 国际会议中，每个人都与他国地位对等的人直接进行会谈

D． 体育比赛中，每一级比赛的优胜者晋级上一级比赛

11．矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（ B ）。

A．记录了大量像素块的色彩值来表示图像

B．用点、直线或者多边形等基于数学方程的几何图元来表示图像 C．每个像素点的颜色信息均用矢量表示

D．把文件保存在互联网，采用在线浏览的方式查看图像

12． 如果一个栈初始时为空，且当前栈中的元素从栈顶到栈底依次为a，b，c，另有元素d已经出栈，则可能的入栈顺序是（ D ）。 A．a, d, c, b

B．b, a, c, d

C．a, c, b, d

D．d, a, b, c

13．（ B ）是主要用于显示网页服务器或者文件系统的HTML文件的内容，并让用户与这些文件交互的一种软件。 A．资源管理器

B．浏览器

C．电子邮件

D．编译器

14．（ C ）是目前互联网上常用的E-mail服务协议。 A．HTTP

B．FTP

C．POP3

D．Telnet

15．（ C ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。 A．动态规划

B．贪心

C．分治

D．搜索

16．地址总线的位数决定了CPU可直接寻址的内存空间大小，例如地址总线为16位，其最大的可寻址空间为64KB。如果地址总线是32位，则理论上最大可寻址的内存空间为（ D ）。 A．128KB

B．1MB

C．1GB

D．4GB

17．蓝牙和Wi-Fi都是（ C ）设备。 A．无线广域网

B．无线城域网

C．无线局域网

D．无线路由器

18． 在程序运行过程中，如果递归调用的层数过多，会因为（ A）引发错误。 A．系统分配的栈空间溢出 C．系统分配的队列空间溢出

B．系统分配的堆空间溢出 D．系统分配的链表空间溢出

19． 原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符“AAABBBCCC”共有（ C ）个不同的非空子串。 A．3

B．12

C．36

D．45

20． 仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术中。以下关于仿生学的叙述，错误的是（ B ） A．由研究蝙蝠，发明雷达 C．由研究海豚，发明声纳

B．由研究蜘蛛网，发明因特网 D．由研究电鱼，发明伏特电池

二、问题求解（共2题，每题5分，共计10分）

1． 如果平面上任取n个整点（横纵坐标都是整数），其中一定存在两个点，它们连线的中点也是整点，那么n至少是__________。

2． 在NOI期间，主办单位为了欢迎来自各国的选手，举行了盛大的晚宴。在第十八桌，有5名大陆选手和5名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右旁都是港澳选手，每个港澳选手左右旁都是大陆选手。那么，这一桌一共有_______种不同的就坐方案。

注：如果在两个方案中，每个选手左右相邻的选手相同，则视为同一种方案。 三、阅读程序写结果。（共4题，每题8分，共计32分） 1．

#include using namespace std; int a,b,c,d,e,ans; int main() { 3 7

cin>>a>>b>>c; d=a+b; e=b+c;

10 ans=d+e; }

输入：1 2 5

输出：____10__________ 2．

#include using namespace std; int n,i,ans; int main() { }

输入：18

输出：__24___________ 3．

#include using namespace std;

cin>>n; ans=0;

for(i=1;i<=n;i++)1 1 1 1 1 1

if(n%i==0) ans++; cout<

cout<

int n,i,j,a[100][100]; int solve(int x,int y) { }

int main() { } 输入： 5 2 -1 4 2 -1 -2 -1 6 4 0 3 2 -1 5 8

输出：______________ 4．

#include #include using namespace std; int n,i,j,ans; string s; char get(int i) { }

if(i>n;

for(i=1;i<=n;i++)

for(j=1;j<=i;j++) cin>>a[i][j]; int u,v;

if(x==n) return a[x][y]; u=solve(x+1,y); v=solve(x+1,y+1);

if(u>v) return a[x][y]+u; else return a[x][y]+v;

cout<

int main() { }

输入：CBBADADA 输出：____________

四、完善程序（前2空每空2分，后8空每空3分，共计28分）

1．（坐标统计）输入n个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即x、y坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。

#include using namespace std; const int SIZE =100;

int x[SIZE],y[SIZE],f[SIZE]; int n,i,j,max_f,ans; int main() {

cin>>n;

for(i=1;i<=n;i++) cin>>x[i]>>y[i]; max_f=0;

for(i=1;i<=n;i++) cin>>s; n=s.size(); ans=0;

for(i=1;i<=n-1;i++) { }

for(j=0;j<=n-1;j++) cout<

for(j=0;j<=n-1;j++)

if(get(i+j)

else if(get(i+j)>get(ans+j)) break;

ans=i; break;

}

{ }

for(i=1;i<=n;i++) cout<

f[i]= ① ; for(j=1;j<=n;j++) { }

if( ④ ) { }

max_f=f[i]; ⑤ ;

if(x[j]

2． （排列数）输入两个正整数n，m（1

#include #include using namespace std; const int SIZE =25; bool used[SIZE]; int data[SIZE]; int n,m,i,j,k; bool flag; int main() {

cin>>n>>m;

memset(used,false,sizeof(used)); for(i=1;i<=m;i++)

}

{ }

flag=true; while(flag) { }

return 0;

for(i=1;i<=m-1;i++) cout<=1;i--) { }

② ;

for(j=data[i]+1;j<=n;j++) { }

for(k=i+1;k<=m;k++)

for(j=1;j<= ④ ;j++) if(!used[j]) { }

data[k]=j; used[j]=true; break;

if(!used[j]) { }

used[j]=true; data[i]= ③ ; flag=true; break;

data[i]=i; used[i]=true;

if(flag)

⑤ ;

参考答案

一、单项选择题（共20题，每题1．5分，共计30分；每题且仅有一个正确选项）

1 A 11 B 2 B 12 D 3 A 13 B 4 B 14 C 5 C 15 C 6 C 16 D 7 B 17 C 8 C 18 A 9 A 19 C 10 A 20 B 二、问题求解（共2题，每题5分，共计10分） 1． 5 2． 2880

三、阅读程序写结果。（共4题，每题8分，共计32分） 10 6 14 ACBBADAD

四、完善程序（前2空每空2分，后8空每空3分，共计28分） 1、 ① 0 ② y[j]

④（i>1）&& (f[i]>f[i-1]) ⑤ ans=max_f 2、 ① false

② used[data[i]]=flase ③ j ④ n ⑤ break

第十九届全国青少年信息学奥林匹克联赛初赛普及组

C++语言试题

竞赛时间： 2013 年 10 月 13 日 14:30~16:30

选手注意： 试题纸共有

9 页，答题纸共有2 页，满分 100 分。请在答题纸上作答，写在试题纸上的一

律无效。不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。 一、单项选择题（共20 题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项） 1. 2. 3.

一个 32 位整型变量占用（ ）个字节。

B. 8

C. 32 D. 128

）。

C. 6.25 D. 11.125 ）算法有着异曲同工之妙。

二进制数 11.01 在十进制下是（ 下面的故事与（

A. 4

A. 3.25 B. 4.125

从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....’ A. 枚举 B. 递归 C. 贪心 D. 分治 4.

逻辑表达式（）的值与变量A 的真假无关。

A. (A ∨ B) ∧﹃A 5.

B. (A ∨ B) ∧﹃B D. (A ∨ B) ∧﹃A ∧ B

C. (A ∧ B) ∨ (﹃ A ∧ B)

将（ 2, 6, 10, 17）分别存储到某个地址区间为0~10 的哈希表中，如果哈希函数h(x) =（ ），将不会产生冲突，其中a mod b 表示 a 除以 b 的余数。

B. x2 mod 11

D. |√2| mod 11 ，其中√X表示√X下取整

A. x mod 11 C. 2x mod 11 6. 7. A. 9

在十六进制表示法中，字母 A 相当于十进制中的（ ）。

B. 10 C. 15 D. 16

）。

下图中所使用的数据结构是（

A. 哈希表 B. 栈 C. 队列 D. 二叉树 8.

在 Windows 资源管理器中，用鼠标右键单击一个文件时，会出现一个名为“复制”的操作

）。

选项，它的意思是（

A. 用剪切板中的文件替换该文件

B. 在该文件所在文件夹中，将该文件克隆一份 C. 将该文件复制到剪切板，并保留原文件 D. 将该文件复制到剪切板，并删除原文件 9.

已知一棵二叉树有10 个节点，则其中至多有（ ）个节点有

B. 5

C. 6

D. 7

）条边。

2 个子节点。

A. 4

10. 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4 个顶点、 6 条边的连通图。若要使它不再是连通图，至少要删去其中的（

A. 1 B. 2 C. 3

D. 4

）。

11. 二叉树的（ ）第一个访问的节点是根节点。

A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 以上都是

12. 以 A0 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（

A. A0, A1 , A2, A3

B. A0, A1, A3, A2

C. A0, A2, A1, A3

D. A0, A3, A1, A2

13. IPv4 协议使用32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用（ ）位地址的 IPv6 协议所取代。 A. 40 B. 48 C. 64 D. 128

14. （ ）的 平均时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。 A. 快速排序 B. 插入排序 int euclid(int a, int b) {

if (b == 0)

return a; else

return euclid(b, a % b);

}

A. 最大公共质因子 C. 最大公约数

B. 最小公共质因子 D. 最小公倍数

C. 冒泡排序

D. 基数排序

15. 下面是根据欧几里得算法编写的函数，它所计算的是 a 和 b 的（ ）。

16. 通常在搜索引擎中，对某个关键词加上双引号表示（ ）。 A. 排除关键词，不显示任何包含该关键词的结果 B. 将关键词分解，在搜索结果中必须包含其中的一部分 C. 精确搜索，只显示包含整个关键词的结果 D. 站内搜索，只显示关键词所指向网站的内容 17. 中国的国家顶级域名是（ A. .cn

B. .ch

）。

D. .china

不可能 （）。

C. .chn

18. 把 64 位非零浮点数强制转换成32 位浮点数后， A. 大于原数 B. 小于原数 C. 等于原数 D. 与原数符号相反

19. 下列程序中，正确计算1, 2, ?, 100 这 100 个自然数之和 sum（初始值为0）的是（ ）。

20. CCF NOIP 复赛全国统一评测时使用的系统软件是（ ）。 A. NOI Windows B. NOI Linux 1.

7 个同学围坐一圈，要选

C. NOI Mac OS D. NOI DOS

5 分，没有部分分）

二、问题求解（共2 题，每题 5 分，共计 10 分；每题全部答对得

2 个不相邻的作为代表，有_________种不同的选法。

2. 某系统自称使用了一种防窃听的方式验证用户密码。密码是n 个数 s1, s2, ? , sn，均为 0或 1。该系统每次随机生成 n 个数 a1, a2, ? , an，均为 0或1，请用户回答 (s1a1 + s2a2 + ?+ snan) 除以 2 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。 然而，事与愿违。例如，当n = 4 时，有人窃听了以下5 次问答：

就破解出了密码 1.

s1 = _________

，s2 = _________ ，s3 = _________ ，s4 =

_________ 。三、阅读程序写结果（共4 题，每题 8 分，共计 32 分）

#include using namespace std; int main() {

int a, b; }

输入： 3 5

cin>>a>>b;

cout<

}

程序运行后输出结果错误，导致错误结果的程序行是( )。 A.s = 1.0; B.for(n = 10; n > 1; n--) C.s = s + 1 / n; D.cout << s << endl;

⒕设变量x为float型且已赋值，则以下语句中能将x中的数值保留到小数点后两位，并将第三位四舍五入的是( )。

A.x = (x * 100) + 0.5 / 100.0; B.x = (x * 100 + 0.5) / 100.0; C.x = (int)(x * 100 + 0.5)/100.0; D.x = (x / 100 + 0.5) * 100.0; ⒖有以下程序 #include using namespace std; int main() {

int s, a, n; s = 0; a = 1; cin >> n; do {

s += 1; a -= 2; }

while(a != n); cout << s << endl; return 0; }

若要使程序的输出值为2，则应该从键盘给n输入的值是( )。 A.-1 B.-3 C.-5 D.0 ⒗一棵具有5层的满二叉树中结点数为( )。 A.31 B.32 C.33 D.16

⒘有向图中每个顶点的度等于该顶点的( )。 A.入度 B.出度 C.入度和出度之和 D.入度和出度之差

⒙设有100个数据元素，采用折半搜索时，最大比较次数为( )。 A.6 B.7 C.8 D.10

⒚若有如下程序段，其中s、a、b、c均已定义为整型变量，且a、c均已赋值，c>0。 s = a; for(b = 1; b <= c; b++) s += 1;

则与上述程序段功能等价的赋值语句是( )。 A.s = a + b B.s = a + c C.s = s + c D.s = b + c ⒛计算机界的最高奖是( )。

A.菲尔兹奖 B.诺贝尔奖 C.图灵奖 D.普利策奖

二、问题求解(共2题，每题5分，共计10分；每题全部答对得5分，没有部分分)

1.把M个同样的球放到N个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的放置方法？(用K表示)。

例如，M＝7，N＝3时，K＝8；在这里认为和是同一种放置方法。 问：M＝8，N＝5时，K＝ 18 。

2.如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是 11 。

三、阅读程序写结果(共4题，每题8分，共计32分) 1.

#include using namespace std; int main() {

int a, b, c, d, ans; cin >> a >> b >> c; d = a- b; a = d + c; ans = a * b;

cout << \} 输入：2 3 4 输出：Ans = 9 2 #include using namespace std; int fun(int n) {

if(n == 1) return 1; if(n == 2) return 2;

return fun(n -2) - fun(n - 1); } int main() { int n; cin >> n;

cout << fun(n) << endl; return 0; } 输入：7 输出：-11 3 #include #include using namespace std; int main() {

string st; int i, len; getline(cin, st); len = st.size(); for(i = 0; i < len; i++)

if(st[i] >= 'a' && st[i] <= 'z') st[i] = st[i] - 'a' + 'A'; cout << st << endl; return 0; }

输入：Hello, my name is Lostmonkey. 输出：HELLO, MY NAME IS LOSTMONKEY 4.

#include using namespace std; const int SIZE = 100; int main() {

int p[SIZE]; int n, tot, i, cn; tot = 0; cin >> n;

for(i = 1; i <= n; i++) p[i] = 1;

for(i = 2; i <= n; i++) {

if(p[i] == 1) tot++; cn = i * 2; while(cn <= n) {

p[cn] = 0; cn += i; } }

cout << tot << endl;

return 0; } 输入：30 输出： 10

四、完善程序(共2题，共计28分)

1.(数字删除)下面程序的功能是将字符串中的数字字符删除后输出。请填空。(每空3分，共12分) #include using namespace std; int delnum(char *s) { int i, j; j = 0;

for(i = 0; s[i] != '\\0'; i++) if(s[i] < '0' || s[i] > '9') {

s[j] = s[i]; j++ ; }

return j ; }

const int SIZE = 30; int main() {

char s[SIZE]; int len, i;

cin.getline(s, sizeof(s)); len = delnum(s); for(i = 0; i < len; i++) cout << s[i] ; cout << endl; return 0; }

2.(最大子矩阵和)给出m行n列的整数矩阵，求最大的子矩阵和(子矩阵不能为空)。 输入第一行包含两个整数m和n，即矩阵的行数和列数。之后m行，每行n个整数，描述整个矩阵。程序最终输出最大的子矩阵和。(最后一空4分，其余3分，共16分) 比如在如下这个矩阵中： 4 4

0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 拥有最大和的子矩阵为： 9 2 -4 1 -1 8 其和为15 3 3 -2 10 20 -1 100 -2 0 -2 -3 最大子矩阵和为128 4 4

0 -2 -9 -9 -9 11 5 7 -4 -3 -7 -6 -1 7 7 5 最大子矩阵和为26 #include using namespace std;

const int SIZE = 100;

int matrix[SIZE + 1][SIZE + 1];

int rowsum[SIZE + 1][SIZE + 1]; //rowsum[i][j]记录第i行前j个数的和 int m, n, i, j, first, last, area, ans; int main() {

cin >> m >> n;

for(i = 1; i <= m; i++) for(j = 1; j <= n; j++) cin >> matrix[i][j]; ans = matrix[1][1]; for(i = 1; i <= m; i ++) rowsum[i][0] = 0; for(i = 1; i <= m; i++) for(j = 1; j <= n; j++)

rowsum[i][j] = rowsum[i][j - 1] + matrix[i][j]; for(first = 1; first <= n; first++) for(last = first; last <= n; last++) {

area = 0;

for(i = 1; i <= m; i++) {

area += rowsum[i][last] - rowsum[i][first - 1]; if(area > ans) ans = area; if(area < 0) area = 0; } }

cout << ans << endl; return 0; }

本文来源：https://www.bwwdw.com/article/w9cv.html