2014年宁波市第29届中小学生计算机程序设计竞赛
初中组初赛c语言试题
(说明:答案请写在答题卷上。考试时间120分钟,满分100分)
一、选择题(每题有且仅有一个正确答案,选对得1.5分,选错. 不选或多选均不得分)
- 计算机主机最主要是由CPU 与( )构成的:
(A)控制器 (B)运算器 (C)输入、输出设备 (D)内存储器
- 操作系统是重要的系统软件,下面几个软件中不属于操作系统的是:
(A)MS-DOS (B)linux (C)PASCAL (D)Win8
- 在计算机网络中,IP地址127.0.0.1表示:
(A)局域网 (B)本地主机 (C)空白页 (D)CCF NOI官网
- 无线局域网络的英文缩写是:
(A)Lan (B)Wlan (C)Wan (D)wifi
- 以下哪个不是常见智能手机的操作系统:
(A)Symbian (B)Android (C)iOS (D)wifi
- 第四代移动通信技术即4G是集3G与WLAN于一体,它最高能以多少bps的速度下载:
(A)100M (B)10M (C)20M (D)50M
- 如果只运行一个普通的串行程序,采用四核CPU的电脑与双核电脑相比(假设其他配置均相同):
(A)运行速度几乎差不多 (B)运行速度是原来2倍
(C)运行速度是原来4倍 (D)运行速度是原来8倍
- 在下面各世界顶级的奖项中,为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是:
(A)沃尔夫奖 (B)诺贝尔奖 (C)菲尔兹奖 (D)图灵奖
- 以下哪个是指可以显示网页服务器或者文件系统的HTML文件内容,并让用户与这些文件交互的一种软件:
(A)计算器 (B)浏览器 (C)电子邮件 (D)编译器
- 十进制数100.625等值于二进制数:
(A)1001100.101 (B)1100100.101 (C)1100100.011 (D)1001100.11
- 体育课的铃声响了,同学们都陆陆续续地奔向操场,按老师的要求从高到矮站成一排。每个同学来到操场时,都从排尾走向排头,找到第一个比自己高的同学,并站在他的后面。这种站队的方法类似于以下哪个算法:
(A)快速排序 (B)插入排序 (C)冒泡排序 (D)归并排序
- 对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找,等概率情况下,查找成功的平均查找长度(平均比较次数)是:
(A)35/11 (B)34/11 (C)33/11 (D)32/11
- 由3个a,1个b和2个c构成的所有字符串中,包含子串“abc”的共有几个:
(A)20 (B)8 (C)12 (D)16
- 递归过程和函数调用时,处理参数和返回地址,通常使用哪种数据结构:
(A)队列 (B)线性表 (C)链表 (D)栈
- 设栈S的初始状态为空,元素a,b,c,d,e,f依次入栈,出栈顺序为b,d,c,f,e,a那么栈容量至少应该是:
(A)6 (B)5 (C)4 (D)3
- 满二叉树的叶结点个数为N,则它的结点总数为:
(A)N (B)2 * N (C)2 * N – 1 (D)2 * N + 1
- 在含有n个元素的双向链表中查询是否存在关键字为k的元素,最坏情况下运行的时间是:
(A) Θ(1) (B) Θ(log n) (C) Θ(n) (D) Θ(n log n)
- 假设A=true,B=false,C=ture,D=ture,逻辑运算表达式A∧B∨C∧D的值是( )。
(A)ture (B)false (C))0 (D)1
- 一个有n个顶点的无向图(无重边)最多有几条边:
(A)n (B)n(n -1) (C)n (n -1)/2 (D)2n
- 现有4个砝码,重量分别为1克、2克、4克和8克。那么可以称出几种不同重量的物体(物体重量必须大于0):
(A)12 (B)13 (C)14 (D)15
二、问题求解(每小题5分,共10分)
- 现有80枚硬币,其中有一枚是假币,其重量稍轻,所有真币的重量都相同。如果使用不带砝码的天平称重,最坏情况下最少需要称____次,就一定可以找出假币?
- 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++)
|
|
{
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);
}
|
|||
|
|||
四.程序填空(前2空,每空2分,后8空,每空3分,共28分)
- 输入一个正整数n(2 <= n <= 106),以及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>
|
|
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("");
}
}
- 某地共派出M名选手参加宁波市程序设计竞赛,现在他们正赶往火车站参加比赛。火车站共有N(1<=N<=100000)个检票口。由于检票员的操作速度不同,每个检票口的通行速度也就不同,平均测量,第k个检票口的速度为每人Tk秒(范围在[1, 109])。
在候车时,精于计算的选手们就开始思考,假设一开始所有检票口都处于准备状态,每个检票口一次只能通过一人。那么M(2 <= M <= 109)名选手至少需要多少时间全部通过检票口。输入N,M,以及N个检票口的检票时间。求最少全部通过时间。
|
|
#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) ;
}