全国CCF提高级非专业级别软件能力认证第一轮
一、单项选择题 （共15题，每题2分，共计30分；每题有且仅有一个正确选项）
1) 请选出以下最大的数( )




查看答案
2) 操作系统的功能是( )。




查看答案
3) 现有一段8分钟的视频文件，它的播放速度是每秒24帧图像，每帧图像是一幅分辨率为2048x1024像素的32位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间? ( )。




查看答案
4) 今有一空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进行:进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为()。




查看答案
5) 将(2, 7, 10, 18)分别存储到某个地址区间为0~10的哈希表中，如果哈希函数h(x) = ( ), 将不会产生冲突，其中a mod b表示a除以b的余数。




查看答案
6) 下列哪些问题不能用贪心法精确求解?()




查看答案
7) 具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为( )。




查看答案
8) 二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，24个顶点的二分图至多有( ) 条边。




查看答案
9) 广度优先搜索时，一定需要用到的数据结构是( )。




查看答案
10) 一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人,问这个班的学生人数n在以下哪个区间?已知n<60。( )。




查看答案
11) 小明想通过走楼梯来锻炼身体，假设从第1层走到第2层消耗10卡热量，接着从第2层走到第3层消耗20卡热量，再从第3层走到第4层消耗30卡热量，依此类推，从第k层走到第k+1层消耗10k卡热量(k>1)。如果小明想从1层开始，通过连续向上爬楼梯消耗1000卡热量，至少要爬到第几层楼? ( )。




查看答案
12) 表达式a*(b+c)-d的后缀表达形式为( )。




查看答案
13) 从一个4 x 4的棋盘中选取不在同一行也不在同一列上的两个方格，共有( )种方法。




查看答案
14) 对一个n个顶点、m条边的带权有向简单图用Dijkstra算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为( )。




查看答案
15) 1948年，( )将热力学中的熵引入信息通信领域，标志着信息论研究的开端。




查看答案
二、阅读程序 （程序输入不超过数组或字符串定义的范围;判断题正确填V,错误填X;除特殊说明外，判断题1.5分，选择题3分，共计40分）
#include <iostream>

using namespace std;



int n;

int d[1000];



int main() {

	cin >> n;

	for(int i=0; i<n; ++i)

		cin>> d[i];

	int ans = -1;

	for(int i=0; i<n; ++i)

		for(int j=0; j<n; ++j)

			if (d[i] < d[j])

				ans = max(ans, d[i] + d[j] - (d[i] & d[j]));

	cout << ans;

	return 0;

}
16) n必须小于1000，否则程序可能会发生运行错误。()

查看答案
17) 输出一定大于等于0。( )

查看答案
18) 若将第13行的“j =0”改为“j = i + 1”， 程序输出可能会改变。()

查看答案
19) 将第14行的“d[i] < d[j]"改为“d[i] != d[j]”，程序输出不会改变。()

查看答案
20) 若输入n为100， 且输出为127， 则输入的d[i]中不可能有( )。




查看答案
21) 若输出的数大于0，则下面说法正确的是( )。




查看答案 
#include <iostream>

#include <cstdlib>

using namespace std;



int n;

int d[10000];



int find(int L, int R, int k) {

	int x = rand() % (R-L+1) + L;

	swap(d[L], d[x]);

	int a=L+1,b=R;

	while(a<b) {

		while (a < b && d[a] < d[L])

			++a ;

		while (a < b && d[b] >= d[L])

			--b;

		cout<<"*"<<endl;	

		swap(d[a], d[b]);

	}

	if (d[a] < d[L])

		++a;

	if(a-L==k)

		return d[L];

	if (a-L <k)

		return find(a, R, k - (a - L));

	return find(L + 1, a - 1, k);

}

int main() {

	int k;

	cin >> n;

	cin >> k;

	for(int i=0; i<n; ++i)

		cin >> d[i];

	cout << find(0, n - 1, k);

	return 0;

}
22) 第9行的“x" 的数值范围是L+1到R，即[L+1, R]。( )

查看答案
23) 将第19行的“d[a]"改为“d[b]”， 程序不会发生运行错误。 ( )

查看答案
24) (2.5 分)当输入的d[i]是严格单调递增序列时，第17行的“swap"平均执行次数是( ) 。




查看答案
25) (2.5 分)当输入的d[i]是严格单调递减序列时，第17行的“swap”平均执行次数是( ) 。




查看答案
26) (2.5分) 若输入的d[i]为i,此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( ) 。




查看答案
27) (2.5分)若输入的d[i]都为同一个数，此程序平均的时间复杂度是()。




查看答案 
#include <iostream>

#include <queue>

using namespace std;



const int maxl = 2000000000;



class Map {

		struct item {

			string key; int value;

		} d[maxl];

		int cnt;

	public:

		int find(string x) {

			for(int i=0; i<cnt; ++i)

				if (d[i].key == x)

					return d[i].value;

			return -1;

		}

		static int end() {return -1;}

		void insert(string k, int v) {

			d[cnt].key = k;	d[cnt++].value = v;

		}

} s[2];



class Queue {

		string q[maxl];

		int head, tail;

	public:

		void pop() {++head;}

		string front() {return q[head + 1];}

		bool empty() {return head == tail;}

		void push(string x) {q[++tail] = x;}

} q[2];



string st0, st1;

int m;



string LtoR(string s, int L, int R) {

	string t = s;

	char tmp = t[L];

	for(int i=L; i<R; ++i)

		t[i] = t[i + 1];

	t[R] = tmp;

	return t;

}



string RtoL(string s, int L, int R) {

	string t = s;

	char tmp = t[R];

	for(int i=R; i>L; --i)

		t[i] = t[i - 1];

	t[L] = tmp;

	return t;

}



bool check(string st, int p, int step) {

	if (s[p].find(st) != s[p].end())

		return false;

	++step;

	if (s[p ^ 1].find(st) == s[p].end()) {

		s[p].insert(st, step);

		q[p].push(st);

		return false;

	}

	cout << s[p ^ 1].find(st) + step << endl;

	return true ;

}



int main() {

	cin>> st0>> st1;

	int len = st0.length();

	if (len != st1.length()) {

		cout << -1 << endl;

		return 0;

	}

	if (st0 == st1) {

		cout << 0 << endl;

		return 0;

	}

	cin>> m;

	s[0].insert(st0, 0);s[1].insert(st1, 0);

	q[0].push(st0);	q[1].push(st1);

	for(int p=0;

	        !(q[0]. empty() && q[1]. empty());

	        p^=1) {

		string st = q[p]. front();q[p].pop();

		int step = s[p].find(st);

		if((p==0&&

		        (check(LtoR(st, m, len - 1), p, step) ||

		         check(RtoL(st, 0, m), p, step)))

		         ||

		        (p==1&&

		         (check(LtoR(st, 0, m), p, step)||

		          check(RtoL(st, m, len - 1), p, step))))

			return 0;

	}

	cout << -1 << endl;

	return 0;

}
28) 输出可能为0。( )

查看答案
29) 若输入的两个字符串长度均为101时，则m=0时的输出与m=100时的输出是一样的。( )

查看答案
30) 若两个字符串的长度均为n，则最坏情况下，此程序的时间复杂度为θ(n!)。( )

查看答案
31) (2.5 分)若输入的第一个字符串长度由100个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的m为0，则输出为( ) 。




查看答案
32) (4 分)已知当输入为“0123)n3210\n1”时输出为4，当输入为“0123451543210\n1”时输出为14，当输入为“012345671n76543210\n1”时输出为28，则当输入为“0123456789ab\nba9876543210\n1"输出为( ) 。其中“\n”为换行符。




查看答案
33) (4分) 若两个字符串的长度均为n,且0<m<n-1，且两个字符串的构成相同(即任何一个字符在两个字符串中出现的次数均相同)，则下列说法正确的是( ) 。提示:考虑输入与输出有多少对字符前后顺序不一样。




查看答案
三、完善程序 （单选题，每题3分，共计30分）
1. 
#include <cstdio>

using namespace std;



const int maxn = 1005;



int n, B, w[maxn], v[maxn];



int gcd(int u, int v) {

	if(v == 0)

		return u;

	return gcd(v, u % v);

}



void print(int w，int v) {

	int gcd(W, v);

	w= w/ d;

	v= v/ d;

	if(v == 1)

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

	else

		printf("%d/%d\n", W，v);

}



void swap(int &x，int &y) {

	int t=x; x=y; y=t;

}



int main() {

	scanf("%d %d", &n，&B);

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

		scanf("%d%d"，&w[i], &v[1]);

	}

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

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

			if(①) {

				swap(w[j], w[j + 1]);

				swap(v[j], v[j + 1]);

			}

	int curV, curW;

	if(②) {

		③

	} else {

		print(B * w[1], v[1]);

		return 0;

	}

	

	for(inti=2; i<=n; i++)

		if(curV + v[i] <= B) {

			curV += v[i];

			curW += w[i] ;

		} else {

			print(④);

			return 0;

		}

	print(⑤);

	return 0;

}
34) ①处应填()




查看答案
35) ②处应填()




查看答案
36) ③处应填()




查看答案
37) ④处应填()




查看答案
38) ⑤处应填()




查看答案
(最优子序列) 取m= 16，给出长度为n的整数序列$(0 \leq a_i < 2^m)$。对于一个二进制数x，定义其分值w(x)为x + popcnt(x)，其中popcnt(x)表示x二进制表示中1的个数。对于一个子序列$b_1,b_2,\ldots,b_k$，定义其子序列分值S为$w(b_1 \oplus b2) + w(b2 \oplus b3) + w(b3 \oplus b4) +...+ w(b_{k-1} \oplus b_k)$。其中$\oplus$表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数 $n(1 ≤n≤40000)$。接下来一行包含n个整数$a_1,a_2,\ldots,a_n$。
提示:考虑优化朴素的动态规划算法，将前$\frac{m}{2}$位和后$\frac{m}{2}$位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是x、最后一个位置的低8位是y时的最大价值。

试补全程序。 
#include <iostream>



using namespace std;



typedef long long LL;



const int MAXN=40000, M=16,B=M>>1,MS=(1<< B)- 1;

const LL INF = 100000000000000LL ;

LL Max[MS + 4][MS + 4];



int w(int x)

{

	int s=x;

	while (x)

	{

		①;

		s++;

	}

	return s;

}



void to_max(LL &x, LL y)

{

	if(x<y)

		x =y;

}



int main()

{

	int n;

	LL ans=0;

	cin >> n;

	for(int x=0; x<=MS; x++)

		for(int y=0; y<=MS; y++)

			Max[x][y] = -INF;

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

	{

		LL a;

		cin >> a;

		int x=②,y=a&MS;

		LL v=③;

		for(int z=0; z<=MS; z++)

			to_max(v,④);

		for(int z=0; z<=MS; z++)

			⑤;

		to_max(ans, v);

	}

	cout << ans << endl ;

	return 0;

}
39) ①处应填()




查看答案
40) ②处应填()




查看答案
41) ③处应填()




查看答案
42) ④处应填()




查看答案
43) ⑤处应填()




查看答案
增值服务权益

1. 试题参考答案和解析查看；
2. 试卷模拟测试；
3. 随机组题测试；
4. 试卷PDF文件下载；
5. 赠送等值学豆；

  订阅  
学员服务
  在线编程  
教研服务

小鹏STEM教研服务系统是面向教师的一站式教研、教学和知识管理系统。
订阅服务后，所有题目均可无限制查看和服务。

  详情  
最新试卷