宁波市第32届小学生计算机程序设计初赛试题 [2017年]

1. Facebook是美国的一个社交网络服务网站，它的创始人是( )

2. 以下列扩展名结尾的文件，是图片文件的是( )。

3. 进制数11011011的十进制值是( )

4. 机存储容量的基本单位是( )

5. 缀表达式(A+B)*(C*(D+E)+F)的后缀表达式是( )

6. 以下不能用程序设计解决的问题是( )

7. 下列排序算法中，哪个排序是稳定的( )

8. 家里刚安装了50M宽带，极限下载速度大概有6M每秒，现在考虑全程满速度下载，一个1.5G的文件大概要花费( )时间

9. ∧表示与，∨表示或，ac为 true，bd为false，下列( )选项逻辑运算结果是false

10. 如果一棵二叉树的中序遍历是 ACDB，先序遍历是ABCD，那么它的后序遍历是( )

11. 1963年( )发明了首款头戴式图形显示器，如今的 OculusRift虚拟现实眼罩就采用了这种模式，他也被后人誉为人工智能之父

12. 一体机和普通台式机相比，试分析以下结论不确切的是( )

13. 192.168.1.3这种 ip地址的写法是以下明哪种形式( )

14. 试计算如下二进制表示的和101+10101= ( )

15. 如下图描述，符合以下哪种数据结构( )

16. 根据入栈序列54321，判断以下哪种不可能是出栈序列

17. 如果约定二叉树根结点是第一层，那么以下哪项不能成为完全二叉树

18. 某火车运输公司有一个中央仓库和 n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点 i和 j之间运输货物存在费用cij。为求解旅行费用总和最小的运输路径，设计如下算法:首先选择离中央仓库最近的运输目的地1，然后选择离运输目的地1最近的运输目的地2，…，每次在来访问过的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库 。请问该算法的类型( )

19. 羽毛球比赛采取21分制，决胜盘要胜出两分才算赢，否则即使到21分也不能胜出，当然先拿到30分者获胜，给你一个比分，试判断是否是正常结束的比分，解决这个问题，从原理上分析，最少需要用到程序设计中的( )

20. 你觉得如下做法较合理的是( )

1. 按照如下表格中的数字规律，X标记的单元格应该填( )
答案：47

2. 一个学校开设了如下的课程：语文、数学、信息、体育，一天4节课，上午2节，下午2节，有几个限制条件:一天不允许上重复的课，语文、数学这两门课不能连续上，请问排足一天的课有( )种方案。
答案：12

1.

#include <iostream>
using namespace std;
int a,b,c,i,j;
int main()
{
	i=1;j=32;
	a=i+j;
	b=a+j;
	c=b+i*j;
	a=a+i+c*2;
	cout<<a<<" "<<b<<" "<<c<<endl;
	return 0;
}
输出：228 65 97

2.

#include <iostream>
using namespace std;
int i,j,k,p;
int main()
{
	i=1;
	j=0;
	p=1;
	do{
		i++;
		j=p+1;
		p=j*2;
	}while(i !=5);
	cout<<p<<endl;
	return 0;
}
输出：46

3.

#include <iostream>
#include <cstring>
using namespace std;
int n;
int a[101];
int f(int n)
{
	int tmp;
	if(a[n-1]>0) tmp=a[n-1];
	else tmp=f(n-1);
	if (a[n-2]>0) tmp += a[n-2];
	else tmp += f(n-2);
	a[n]=tmp;
	return tmp; 
}
int main()
{
	memset(a,0,sizeof(a));
	a[1]=2;
	a[2]=3;
	cout<<f(9)<<endl;
	return 0;
}
输出：89

4.

#include <iostream>
#include <cstring>
using namespace std;
int n,i,max1,j,h,t;
int a[10001],b[10001];
int main()
{
	cin>>n;
	b[0]=0;
	for (i=1; i<=n; i++)
	{
		cin>>a[i];
		b[i]=b[i-1]+a[i];		
	}
	a[0]=0;
	max1=-100;
	for (i=1; i<=n; i++){
			for (j=i; j<=n; j++){
			b[j] -= a[i-1];
			if (b[j]>max1){
				h=i;
				t=j;
				max1=b[j];
			}
		}
	}
	if (max1<=0) cout<<0<<endl;
	else cout<<max1<<endl;
	return 0;
}
输入：
11
-2 11 -4 13 -50 -2 13 -1 3 6 -9
输出：21

1. 第1题：如下是冒泡排序算法的程序，其中有个优化：使用布尔型变量判断是否已经有序，如果是不用执行接下来的排序过程。

#include <iostream>
using namespace std;
const int maxn=20;
int n;
int a[maxn];
int main()
{
	cin>>n;
	for (int i=0; i<n; i++) cin>>a[i];
	bool done;
	do {
		  done=false ;
		for ( int i=1; i<n; i++)
			if (a[i-1]>a[i]){
				int t=a[i-1];
				a[i-1]=a[i];
				a[i]=t;
				 done=true ; 			
			}
		
	}while ( done ) ;
	for (int i=0; i<n; i++) cout<< a[i] <<" ";
	cout<<endl;
	return 0;
}

2. 第2题：希尔排序( Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序。因DL.Shell于1959年提出而得名。希尔排序思想：希尔排序是按照不同步长对原始元素12 11 10 9 8 7 6 5 4 3 2 1进行插入排序，步长为6，也就是间隔为6的元素插入排序结果为6 5 4 3 2 1 12 11 10 9 8 7，接着步长为3进行插入排序结果为3 2 1 6 5 4 9 8 7 12 11 10，再接着步长为1进行插入排序结果为1 2 3 4 5 6 7 8 9 10 11 12

根据如上描述，完善如下希尔排序程序

#include<ctime>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std; 
const int SIZE = 12; 
typedef int arr[SIZE +1]; 
arr a;
int i, j, k, t; 
void ki(){
	srand(time(NULL) );
	for(i= 1; i<=SIZE; i++)
		cin>>a[i];
	}
void ki2(){
	for (i=1; i<SIZE; i++) cout<<a[i]<< " ";
	cout << a[SIZE]; 
}
void insertionsort(arr a){
	for (i=2; i<=SIZE; i++){
		t=a[i];
		j=i-1;
		while (j>0 && a[j]>t ) {
		}
			a[j+1]=a[j];
			 j-- ; 
		}
		a[j+1]=t;
	}
}

int main(){
	ki();
	k=SIZE;
	while (k>1) {
		k /=2;
		for (j=k+1; j<=SIZE; j++){
			t=a[j];
			i=j-k;
			while (i>0 && a[i] >t){
				a[i+k]=a[i];
				 i-=k ;
		}
			a[i+k]=t;
		}		
	}
	ki2();
	return 0;
}