第 1 题 提出计算机的体系结构主要包括运算器、( )、 存储器、输入和输出设备。

第 2 题 A、B、C、D、E五个人并排站成一列，若A、B必相邻，则有( )种不同排法。

第 3 题 设A=true,B=false,C=true,D=false,以下逻四运算衰达式值为假的是( )。

第 4 题 二进制数1011.01转换成十进制数是( )。

第 5 题 以下数据中，C++编程时用整型(int)表示最恰当的是( )。

第 6 题 设有一顺序栈S，元素a1,a2,a3,a4日依次进栈，如果4个元素出栈的顺序是a2,a3,a4,a1,则栈的容量至少应该是( )。

第 7 题 下列设备中，既是输入设备又是输出设备的是( ) 。

第 8 题 假设用双核CPU运行我们平常编写的信息学竞赛程序，相对于同等规格的单核CPU而言，运行时间( )。

第 9 题 以下程序段的时间复杂度为()。

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

第 10 题 有6个顶点的无向图至少应该有( )条边才能确保是一个连通图。

第 11 题 对一组(82,47,25,12,21)排序，数据的排到次序在排序的过程中的变化为: (1)82 47 25 12 21 (2)12 47 25 82 21 (3)12 21 25 82 47 (4)12 21 25 47 82 则采用的排序是( )排序。

第 12 题 折半查找对元素的排列要求及适用的表的存储方式为( )。

第 13 题 一个具有1025个结点的二叉树的高度h为( )。

第 14 题 计算机病毒的传染需要计算机运行和( )这两个条件，否则病毒是不会传染的。

第 15 题 从5个人中选择2个人参加文艺活动，其中1人唱歌，1人朗诵，则有( )种 不同排法。

二、判断题（每题 2 分，共 20 分）

第 16 题

#include<iostream>
using namespace std;
long long fun_one(int n) {
	if(n==1) {
		return 1;
	} else if(n==2) {
		return 2;
	} else {
		return fun_one(n-1) +fun_one(n-2);
	}
}
long long fun_two(int n) {
	long long a[2005];
	a[1]=1;
	a[2]=2;
	for (int i=3; i<=n; i++) {
		a[i]=a[i-1]+a[i-2];
	}
	return a[n];
}
int main() {
	int k;
	cin>>k;
	cout<<fun_two(k)<<endl;
	cout<<fun_one(k)<<endl;
	return 0;
}

假设输入的k是不超过2000的数，试完成下面的判断题和选择题。

第 16 题 输入的k必须大于0。( )

第 17 题 输入的k值只要小于2000, 则24和25行会得到大于0的数。

第 18 题 输入的k值不能太大，否则会发生运行错误。( )

第 19 题 函数fun_one(k)调用靠栈来实现，当次数足够大时，会导致函数栈溢出而死机。( )

第 20 题 若输入k值为10,则输出的值是( )。

第 21 题 (4分)以下说法正确的是( )。

第 23 题

#include<cstdio>
using namespace std;
int k,n,ans;
int a[50010],r[50010];
void merge_sort(int s,int t) {
	if(s==t)
		return;
	int m=(s+t)>>1;
	merge_sort(s,m);
	merge_sort(m+1,t);
	int i=s,j=m+1,k=s;
	while(i<=m&&j<=t) {
		if(a[i]<=a[j])
			r[k++]=a[i++];
		else {
			r[k++]=a[j++];
			ans+=m-i+1;
		}
	}	
	while(i<=m)
		r[k++]=a[i++];
	while(j<=t)
		r[k++]=a[j++];
	for (int p=s; p<=t; ++p)
		a[p]=r[p];
}
int main() {
	scanf ("%d", &n) ;
	for(int i=1; i<=n; ++i)
		scanf ("%d",&a[i]);
	merge_sort(1, n) ;
	printf ("%d\n",ans);
	for(int i=1; i<=n; i++)
		printf("%d ",a[i]);
	return 0;
}

假设输入的n是不超过5000的正整数,试完成下面的判断题和选择题。

第 23 题 若将第31行的merge_sort(1,n)改成merge_sort(0,n)，输出结果不变。()

第 24 题 若将第31行的merge_sort(1,n)改成merge_sort(1,n+1) ，输出结果不变。()

第 25 题 输出结果中ans的值一定大于0。( )

第 26 题 该程序最坏情况下的时间复杂度是O(nlogn)，平均时间复杂度是0(nlogn) ()

第 27 题 若输入的n值是5,数组●的值是4,5,3,2,1,则输出结果是( )。

第 28 题 (4分)若输入的n值是5,数组a的值是4,5,3,2,1,但将第31行改成merge_sort(3,n),则输出结果是()。

第 30 题

#include<iostream>
#include<cstdio>
#include <cmath>
#include<cstring>
using namespace std;
char a[10001];
int b[10001];
int n,m;
char w[6]={'A','B','C','D','E','F'};
int main() {
	cin>>n;
	scanf("%s",&a) ;
	cin>>m;
	int len=strlen(a) ;
	if(a[0]=='0'&&len==1) {
		cout<<"0";
		return 0;
	}
	for (int i=0; i<len; i++) {
		if(a[i]>=97&&a[i]<=122) {
			a[i]=a[i]-32;
		}
		if (a[i]>=49&&a[i]<=57) {
			b[i]=a[i]-48;
		} else if(a[i]>=65&&a[i]<=90) {
			b[i]=a[i]-55;
		}
	}
	int ans=0,cnt=0;
	for(int i=len-1; i>=0; i--) {
		ans =ans+b[i]*(pow(n, cnt));
		cnt++;
	}
	int cnt1=1;
	while (ans!=0) {
		int r=ans%m;
		b[cnt1++] =r;
		ans = ans/m;
	}
	for(int i=cnt1-1; i>=1; i--) {
		if(b[i]<10)
			cout<<b[i];
		else {
			int k=b[i]-10;
			cout<<w[k];
		}
	}
	return 0;
}

假设输入的n、m在[2,16]范围内,数组a中存放非负整数的字符形式,试完成下面 的判断题和选择题。

第 30 题 第21行的作用是将小写字母转换成大写字母。( )

第 31 题 第24行的作用是将数字字符转换成数字并保存。( )

第 32 题 第26行的作用是将大写字母转换成数字10到35。()

第 33 题 如果将第34行中cntl的值改成0,则程序输出结果不变。()

第 34 题 (4分)若输入8 735 10,则输出结果是()。

第 35 题 (4分)若输入10 735 8,则输出结果是( )。

三、编程题（每题 25 分，共 50 分）

第 37 题 1.函数求和 问题描述:学习数学时,有这样一个公式:f(n)= 1^2+2^2+3^2+... +n^2 ,即求1到n的平方和，现在的问题是想要计算f(n)对1007取余的值。 提示:对上述函数化简后可以得到一个通项公式再进行计算即可。

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
	long long n,a,b, mod=1007;
	while (cin>>n) {
		if (n%3==1) {
			__(1)__;
			b=((2*n+1)/3) %mod;
		} else {
			a= (n*(n+1)/6)%mod;
			__(2)__;
		}
		long long ans=0;
		while(b) {
			if (b&1)
				__(3)__;
			__(4)__;
			__(5)__;
		}
		printf ("%lld\n", ans);
	}
	return 0;
}

第 37 题 ⑴处应填( )。

第 38 题 ⑵处应填( )。

第 39 题 ⑶处应填( )。

第 40 题 ⑷处应填( )。

第 41 题 ⑸处应填( )。

第 43 题 最短路径 问题描述:有V个点,给出从a点到b点的距离，当然a和b是互相可以抵达的，向从第V 个点到第1个点的最短距离。 输入:边数E和顶点数V，以及有边连接的两端顶点的编号u、v和边上的距离值cost。 输出:最短距离值

#include<cstdio>
using namespace std;
const int MAXN=1005;
const int INF=0x3fffffff;
int mp[MAXN][MAXN];
int V, E,vis[MAXN], d[MAXN];
int dijkstra(int s) {
	for(int i=1; i<=V; i++) {
		vis[i]=0;
		d[i]=mp[s][i];
	}
	vis[s]=1;
	for (int i=1; i<=V; i++) {
		int mincost,k;
		__(1)__;
		for(int j=1; j<=V; j++) {
			if(__(2)__) {
				k=j;
				mincost=d[j];
			}
		}
		__(3)__;
		for (int j=1; j<=V; j++) {
			if(vis[j]&&a[j]>a[k]+mp[k][j]) {
				__(4)__;
			}
		}
	}
	return __(5)__;
}
int main() {
	while (scanf ("%d%d",&E, &V)!=EOF) {
		for(int i=1; i<=V; i++)
			for(int j=1; j<=V; j++)
				if(i==j)
					mp[i][j]=0;
				else
					mp[i][j]=INF;
		for(int i=0; i<E; i++) {
			int u,v,cost;
			scanf ("%d%d%d", &u,&v, &cost) ;
			if (cost<mp[u][v])
				mp[u][v]=mp[v][u]=cost;
		}
		int ans =dijkstra(V);
		printf ("%d\n",ans);
	}
	return 0;
}

第 43 题 ⑴处应填( )。

第 44 题 ⑵处应填( )。

第 45 题 ⑶处应填( )。

第 46 题 ⑷处应填( )。

第 47 题 ⑸处应填( )。