第二十三届全国青少年信息学奥林匹克C语言初赛试题

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

选手注意：

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

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

1.在8位二进制补码中，10101011表示的数是十进制下的（ ）

  A． 43      B.  -85    C.  -43    D。   -84

2.计算机存储数据的基本单位是（  ）

  A.  bit     B.  Byte     C.  GB    D.   KB

3.下列协议中与电子邮件无关的是（  ）

     A.  POP3     B.  SMTP    C  WTO    D   IMAP  

4.分辨率为800*600、16位色的位图，存储图像信息所需的空间为（  ）

A.  937.5KB     B.  4218.75KB      C. 4320KB   D. 2880KB

 5.计算机应用的最早领域是（  ）

 数值计算 人工智能 机器人 过程控制

 6.下列不属于面向对象程序设计语言的是（  ）

       A.  C     B.  C++    C.  Java     D.  C#

 的中文意思是（ ）

 中国信息赛 全国青少年信息学奥林匹克竞赛

 中国青少年信息学奥林匹克竞赛 中国计算机学会

8.  2017年10月1日是星期日，1999年10月1日是（  ）

  星期三 星期日 星期五 星期二

9.甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有（  ）

  A.  36      B.  48     C. 96    D.  192

10.设G是有n个结点、m条边（n≤m）的连接图，必须删去G的（  ）条边，才能使得G变成一棵树。

A. m-n+1       B.  m-n       C. m+n+1         D.  n-m+1 

11.对于给定的序列｛ak｝,我们把（i , j）称为逆序对当且仅当 i aj .那么序列1，7，2，3，5，4的逆序对数为（ ）个

         A.  4       B.   5       C.   6    D.  7

12.表达式a*(b+c)*d的后缀形式是（  ）

 ．  abcd*+*      B.  abc+*d*     C.  a*bc+*d     D.  b+c*a*d

13.向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行（  ）

  B.  s->next=hs; hs=s ;  

14.若串S=“copyright”，其子串的个数是（  ）

 A.  72    B.  45     C.  46    D.  36

15.十进制小数13.375对应的二进制数是（  ）

        A.  1101.011    B.  10111.011   C.  1101.101    D.  1010.01

16.  对于入栈顺序为a,b,c,d,e,f,g的序列，下列（  ）不可能是合法的出栈序列。

     A.  a,b,c,d,e,f,g      B. a,d,c,b,e,g,f    C. a,d,b,c,g,f,e   D.  g,f,e,d,c,b,a

17.设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做（  ）次比较。

 2     B.  n log n     C.  2n   D. 2n-1

18. 从（  ）年开始，NOIP竞赛将不再支持Pascal语言。

   A.   2020     B.  2021     C.  2022      D.   2023 

19. 一家四口人，至少两个人生日属于同一月份的概率是（  ） （假定每个人生日属于每个月份的概率相同且不同人之间相互）。

  A.  1/12     B.  1/144     C.  41/96   D.   3/4

20.以下和计算机领域密切相关的奖项是（  ）

  A．  奥斯卡奖 图灵奖 诺贝尔奖 普利策奖

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

1.一个人站在坐标（0，0）处，面朝x轴正方向。第一轮，他向前走1单位距离，然后右转；第二轮，他向前走2单位距离，然后右转；第三轮，他向前走3单位 距离，然后右转……他一直这么走下去。请问第2017轮后，他的坐标是：（___,____）。（请在答题纸上用逗号隔开两空答案）

2.如右图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由1变0，或由0变1）。现在要使得所有的格子中的数字都变为0，至少需要_____次操作。

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

char  s[10];

int  I;

scanf(“%s”,  s);

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

for ( i=0; i< strlen(s); i++)

for ( i=0 ; i< strlen (s) ; i++)

  if  (t[s[i]]==1  {

 “ %c\\n”,s[i]  ;

}

 Printf( “ no\\n”);

 Return  0;

 输入： xyzxyw

 输出：___________.

2. #include < stdio.h>

 “ %d%d”,  &m,&n);

 “ %d\\n”,g( m , n, 0 ));

输入：  7  3

输出：__________.

3.  #include  

 “ %s”, ch );

 -1]-‘0’;

 “%d\\n”, res );

       return    0;

  输入： 1001101011001101101011110001

   输出：____________________________.

4.  #include  

     int   main(  )  {

 “ %d%d”, &n,  &m) ;

 dx = - dx ;

 printf( “%d %d\\n” , x, y );

 输入1： 4  3

 输出2： _________________.（3分）

 输入2： 2017  1014 

 输出 2： ________________  ( 5分)。

四、完善程序 （共2题，每题14分，共计28分）

1. （快速幂）请完善下面的程序，该程序使用分治法求 xp  mod  m的值。（第一空2分，其余3分）

输入：三个不超过 10000的正整数 x, p, m .

输出：xp  mod  m的值。

提示：若p为偶数，xp=(x2)p/2  ; 若p为奇数，xp=x*(x2) ( p - 1)/2 .

#include

int  x, p, m, i , result ;

int  main(  )  {

 “%d%d%d”,  &x, &p, &m) ;

 (1)_____;

 (2)______)  {

 (3)_______;

x = __(4)_______;

 “ %d\\n”, __(5)_____) ;

  return  0 ;

2. (切割绳子) 有n条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。（第一、二空2.5分，其余3分）

  输入：第一行是一个不超过100的正整数n,第二行是n个不超过106的正整数，表示每条绳子的长度，第三行是一个不超过108的正整数m。

  输出 ：绳段的最大长度，若无法切割，输出Failed.

 绳子长度

 “ %d”, &n) ;

 for  ( i=0; i  “%d” , &len[i] );

 (1)________.

 “%d”,  &m );

 (2)_____)  {

 “ Failed\\n” ) ;

 (3)______ )  {

 (4)______;

 (5)_____ ;

 – 1 ;

 “%d\\n”,  lbound );