2014年宁波市第29届中小学生计算机程序设计竞赛 初中组初赛c语言试题

2014年宁波市第29届中小学生计算机程序设计竞赛

初中组初赛c语言试题

（说明：答案请写在答题卷上。考试时间120分钟，满分100分）

 

一、选择题（每题有且仅有一个正确答案，选对得1.5分，选错. 不选或多选均不得分）

1. 计算机主机最主要是由CPU 与（ ）构成的：

（A）控制器       （B）运算器     （C）输入、输出设备  （D）内存储器

 

2. 操作系统是重要的系统软件,下面几个软件中不属于操作系统的是：

（A）MS-DOS     （B）linux      （C）PASCAL        （D）Win8

 

3. 在计算机网络中，IP地址127.0.0.1表示：

（A）局域网         （B）本地主机    （C）空白页         （D）CCF NOI官网

 

4. 无线局域网络的英文缩写是：

（A）Lan          （B）Wlan      （C）Wan           （D）wifi

 

5. 以下哪个不是常见智能手机的操作系统：

（A）Symbian     （B）Android    （C）iOS           （D）wifi

 

6. 第四代移动通信技术即4G是集3G与WLAN于一体，它最高能以多少bps的速度下载：

（A）100M        （B）10M        （C）20M          （D）50M

 

7. 如果只运行一个普通的串行程序，采用四核CPU的电脑与双核电脑相比（假设其他配置均相同）：

（A）运行速度几乎差不多             （B）运行速度是原来2倍

（C）运行速度是原来4倍             （D）运行速度是原来8倍

 

8. 在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是：

（A）沃尔夫奖      （B）诺贝尔奖    （C）菲尔兹奖       （D）图灵奖

 

9. 以下哪个是指可以显示网页服务器或者文件系统的HTML文件内容，并让用户与这些文件交互的一种软件：

（A）计算器        （B）浏览器      （C）电子邮件       （D）编译器

 

10. 十进制数100.625等值于二进制数：

（A）1001100.101   （B）1100100.101  （C）1100100.011     （D）1001100.11

 

 

11. 体育课的铃声响了，同学们都陆陆续续地奔向操场，按老师的要求从高到矮站成一排。每个同学来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于以下哪个算法：

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

 

12. 对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找，等概率情况下，查找成功的平均查找长度（平均比较次数）是：

（A）35/11         （B）34/11        （C）33/11          （D）32/11

 

13. 由3个a，1个b和2个c构成的所有字符串中，包含子串“abc”的共有几个：

（A）20           （B）8            （C）12           （D）16

 

14. 递归过程和函数调用时，处理参数和返回地址，通常使用哪种数据结构：

（A）队列         （B）线性表        （C）链表          （D）栈

 

15. 设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a那么栈容量至少应该是：

（A）6            （B）5             （C）4            （D）3

 

16. 满二叉树的叶结点个数为N，则它的结点总数为：

（A）N            （B）2 * N        （C）2 * N – 1     （D）2 * N + 1

 

17. 在含有n个元素的双向链表中查询是否存在关键字为k的元素，最坏情况下运行的时间是：

（A） Θ(1)        （B） Θ(log n)   （C） Θ(n)        （D） Θ(n log n)

 

18. 假设A=true,B=false,C=ture,D=ture,逻辑运算表达式A∧B∨C∧D的值是（ ）。
    （A）ture         （B）false         （C））0            （D）1

 

19. 一个有n个顶点的无向图（无重边）最多有几条边：

（A）n            （B）n（n -1）     （C）n (n -1)/2       （D）2n

 

20. 现有4个砝码，重量分别为1克、2克、4克和8克。那么可以称出几种不同重量的物体（物体重量必须大于0）：

（A）12           （B）13           （C）14            （D）15

 

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

1. 现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同。如果使用不带砝码的天平称重，最坏情况下最少需要称____次，就一定可以找出假币？

 

2. 5男5女围着一张圆桌坐下，要求男女隔位就座，问有____种不同的方案？两个方案相同，当且仅当经过一定的旋转（不允许翻转），每个座位上的人都相同。

 

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

#include<stdio.h>

 

int main()

{

int a[10];

int s,t,i,j;

a[1]=1;

t=0;

for(i=2;i<=6;i++)

{

s=0;

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

s+=a[j];

a[i]=s+1;

}

t=0;

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

t+=a[i];

printf("t=%d\n",t);

}

输出：

 

2.

#include<stdio.h>

 

int gd(int m,int n)

{

if(n==0) return m;

return gd(n,m%n);

}

int main()

{

int a,b,f;

scanf("%d%d",&a,&b);

printf("(%d,%d)=",a,b);

f=gd(a,b);

printf("%d\n",f);

}

输入: 172  16

 

输出：

3.

#include<stdio.h>

#include<string.h>

int visited[200],e[200][200];

int n,m,ans,i,j,a,b,c;

 

void dfs(int x,int len)

{

int i;

visited[x]=1;

if(len>ans) ans=len;

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

if(!visited[i] && e[x][i]!=-1) dfs(i,len+e[x][i]);

visited[x]=0;

}

int main()

{

scanf("%d%d",&n,&m);

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

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

e[i][j]=-1;

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

输入： 4  6 1  2  10 2  3  20 3  4  30 4  1  40 1  3  50 2  4  60

输出:

{

scanf("%d%d%d",&a,&b,&c);

e[a][b]=c;

e[b][a]=c;

}

memset(visited,0,sizeof(visited));

ans=0;

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

dfs(i,0);

printf("%d\n",ans);

}

 

#include<stdio.h>

#include<string.h>

int p[200],e[200];

int n,i,m,ans;

int pow(int x,int w)

{

int i,ret;

ret=1;

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

ret*=x;

return ret;

}

int main()

{

scanf("%d",&n);

m=0;

i=2;

while(n!=1)

{

if(n%i==0){

m++;

p[m]=i;

e[m]=0;

while(n%i==0)

{

e[m]++;

n/=i;

}

}

i++;

}

ans=1;

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

ans=ans*(p[i]-1)*pow(p[i],e[i]-1);

printf("%d\n",ans);

}

	输入： 19800
			输出：

 

 

 

 

 

四．程序填空（前2空，每空2分，后8空，每空3分，共28分）

 

1. 输入一个正整数n（2 <= n <= 10⁶），以及n个不同的正整数（范围在1 <= a[i]<= n）。这n个数可以理解为n的一种排列，假设（1，2，3，4，……，n）是第1个排列，（n,n-1,n-2,……,1）是最后一个排列，根据这n个数组成的排列，输出下一个排列，每个数后输出一个空格;若这n个数已经是最后一个排列，输出“No Next Permutation”。

#include<stdio.h>

#include<string.h>

输出： 1 3 2 4 5

输入： 5 1 2 5 4 3

int n,num,i,mid,t;

int a[1000009],b[1000009];

int main()

{

scanf("%d",&n);

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

scanf("%d",&a[i]);

num=0;

i=n;

while(i>1)

{

if(  （1）  ){

num++;

b[num]=a[i];

}

else{

num++;

b[num]=a[i];

num++;

  （2）  ;

mid=i-2;

break;

}

i--;

}

if(i==1)   （3）  ;

else

{

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

if(  （4）  ){

t=b[i];

b[i]=b[num];

b[num]=t;

break;

}

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

printf("%d ",a[i]);

printf("%d ",b[num]);

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

  （5）  ;

puts("");

}

}

2. 某地共派出M名选手参加宁波市程序设计竞赛，现在他们正赶往火车站参加比赛。火车站共有N(1<=N<=100000)个检票口。由于检票员的操作速度不同，每个检票口的通行速度也就不同，平均测量，第k个检票口的速度为每人T_k秒（范围在[1, 10⁹]）。

在候车时，精于计算的选手们就开始思考，假设一开始所有检票口都处于准备状态，每个检票口一次只能通过一人。那么M（2 <= M <= 10⁹）名选手至少需要多少时间全部通过检票口。输入N，M，以及N个检票口的检票时间。求最少全部通过时间。

输出： 8

输入： 7 10 3 8 3 6 9 2 4

#include<stdio.h>

#define ll long long

int a[100009];

int n,m;

int check(ll mid)

{

ll sum;

int i;

sum=0;

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

{

sum=  （1）  ;

if(sum>=m)   （2）  ;

}

return 0;

}

int main()

{

int i;

ll left,right,mid;

scanf("%d%d",&n,&m);

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

scanf("%d",&a[i]);

left=0;

right=a[1];

right*=m;

while(left<right){

mid=(left+right)/2;

if(  （3）  ) right=mid;

else   （4）  ;

}

  （5）  ;

}