首页 › 试卷 › 信息学奥赛 › 信息学奥赛-提高级 › 2020年CCF非专业级别软件能力认证第一轮 (CSP-S)提高级C++语言试题

2020年CCF非专业级别软件能力认证第一轮 (CSP-S)提高级C++语言试题 VIP

信息学奥赛-提高级 共 46 题 2020 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

请选出以下最大的数( )

  • A (550)10
  • B (777)8
  • C 210
  • D (22F)16
查看答案与解析
答案:C
这道题暂未补解析。
2. 单选题

操作系统的功能是()。

  • A 负责外设与主机之间的信息交换
  • B 控制和管理计算机系统的各种硬件和软件资源的使用
  • C 负责诊断机器的故障
  • D 将源程序编译成目标程序
查看答案与解析
答案:B
这道题暂未补解析。
3. 单选题

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

  • A 30G
  • B 90G
  • C 150G
  • D 450G
查看答案与解析
答案:B
这道题暂未补解析。
4. 单选题

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

  • A b
  • B a
  • C d
  • D c
查看答案与解析
答案:B
这道题暂未补解析。
5. 单选题

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

  • A x^2 mod 11
  • B 2x mod 11
  • C x mod 11
  • D
查看答案与解析
答案:D
这道题暂未补解析。
6. 单选题

下列哪些问题不能用贪心法精确求解?( )

  • A 霍夫曼编码问题
  • B 0-1背包问题
  • C 最小生成树问题
  • D 单源最短路径问题
查看答案与解析
答案:B
这道题暂未补解析。
7. 单选题

具有n个顶点,e条边的图釆用邻接表存储结构,进行深度优先遍历运算的 时间复杂度为()

  • A 0(n+e)
  • B 0(n^2)
  • C 0(e^2)
  • D 0(n)
查看答案与解析
答案:A
这道题暂未补解析。
8. 单选题

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

  • A 144
  • B 100
  • C 48
  • D 122
查看答案与解析
答案:A
这道题暂未补解析。
9. 单选题

广度优先搜索时,一定需要用到的数据结构是()

  • A 栈
  • B 二叉树
  • C 队列
  • D 哈希表
查看答案与解析
答案:C
这道题暂未补解析。
10. 单选题

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

  • A 30<n<40
  • B 40<n<50
  • C 50<n<60
  • D 20<n<30
查看答案与解析
答案:C
这道题暂未补解析。
11. 单选题

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

  • A 14
  • B 16
  • C 15
  • D 13
查看答案与解析
答案:C
这道题暂未补解析。
12. 单选题

表达式a*(b+c)-d的后缀表达形式为( )

  • A abc*+d-
  • B -+*abcd
  • C abcd*+-
  • D abc+*d-
查看答案与解析
答案:D
这道题暂未补解析。
13. 单选题

从一个4X4的棋盘中选取不在同一行也不在同一列上的两个方格,共有 ()种方法。

  • A 60
  • B 72
  • C 86
  • D 64
查看答案与解析
答案:B
这道题暂未补解析。
14. 单选题

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

  • A 0((m + n^2) log n)
  • B 0(mn + n^3)
  • C 0((m + n) log n)
  • D 0(n^2)
查看答案与解析
答案:D
这道题暂未补解析。
15. 单选题

1948年,()将热力学中的熵引入信息通信领域,标志着信息论研究的 开端。

  • A 欧拉(Leonhard Euler)
  • B 冯•诺伊曼(John von Neumann)
  • C 克劳徳•香农(Claude Shannon)
  • D 图灵(Alan Turing)
查看答案与解析
答案:C
这道题暂未补解析。
21. 单选题

若输入n 100.且输出为127.则输入的d[i]中不可能有()。

  • A 127
  • B 126
  • C 128
  • D 125
查看答案与解析
答案:C
这道题暂未补解析。
22. 单选题

若输出的数大于0,则下面说法正确的是()。

  • A 若输出为偶数,则输入的d[i],中最多有两个偶数
  • B 若输出为奇数,则输入的d[i]中至少有两个奇数
  • C 若输出为偶数,则输入的d [ i ]中至少有两个偶数
  • D 若输出为奇数,则输入的d[i]中最多有两个奇数
查看答案与解析
答案:C
这道题暂未补解析。
27. 单选题

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

  • A 0(n^2)
  • B 0(n)
  • C 0(n log n)
  • D 0(log n)
查看答案与解析
答案:B
这道题暂未补解析。
28. 单选题

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

  • A 0(n), 0(n^2)
  • B 0(n), 0(n log n)
  • C 0(n log n), 0(n^2)
  • D 0(n log n), 0(n log n)
查看答案与解析
答案:A
这道题暂未补解析。
29. 单选题

(2.5分)若输入的d[i]都为同一个数,此程序平均的时间复杂度是()

  • A 0(n)
  • B 0(log n)
  • C 0(n log n)
  • D 0(n^2)
查看答案与解析
答案:D
这道题暂未补解析。
34. 单选题

(2.5分)若输入的第一个字符串长度由100个不同的字符构成,第二 个字符串是第一个字符串的倒序,输入的m为0,则输岀为()。

  • A 49
  • B 50
  • C 100
  • D -1
查看答案与解析
答案:D
这道题暂未补解析。
35. 单选题

(4分)已知当输入为“0123\n3210\n1”时输出为4,当输入为 “012345\n543210\n1”时输出为14,当输入为 “01234567\n76543210\n1”时输出为28,则当输入为 “0123456789ab\nba9876543210\n1” 输出为()。其中“\n”为换行符。

  • A 56
  • B 84
  • C 102
  • D 68
查看答案与解析
答案:D
这道题暂未补解析。
36. 单选题

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

  • A 若n、m均为奇数,则输出可能小于0
  • B 若n、m均为偶数,则输出可能小于 0
  • C 若n为奇数、m为偶数,则输出可能小于0
  • D 若n为偶数、m为奇敎.则输出可能小于0
查看答案与解析
答案:C
这道题暂未补解析。
38. 单选题

①处应填()

  • A W[j] / v[j] < w[j+1]/v[j+1]
  • B W[j] / v[j]> w[j+1]/v[j+1]
  • C v[j] * w[j+1]< v[j+1]*w[j]
  • D w[j] * v[j+1]< w[j+1]*v[j]
查看答案与解析
答案:D
这道题暂未补解析。
39. 单选题

②处应填()

  • A w[1] <= B
  • B v[1] <= B
  • C w[1] >= B
  • D v[1] >= B
查看答案与解析
答案:B
这道题暂未补解析。
40. 单选题

③处应填()

  • A print(v[1]w[1]); return 0;
  • B curV = 0; curW = 0;
  • C print(w[1] v[1]); return 0;
  • D curV = v[1]; curW = w[1];
查看答案与解析
答案:D
这道题暂未补解析。
41. 单选题

④处应填()

  • A curW * v[i] + curV * w[i], v[i]
  • B (curW - w[i]) * v[i] + (B - curV) * w[i], v[i]
  • C curW + v[i], w[i]
  • D curW * v[i] * (B - curV) * w[i], v[i]
查看答案与解析
答案:D
这道题暂未补解析。
42. 单选题

⑤处应填()

  • A curW, curV
  • B curW,1
  • C curV, curW
  • D curV,1
查看答案与解析
答案:B
这道题暂未补解析。
44. 单选题

①处应填()

  • A X >>= 1
  • B X ^=X & (x ^ (x + 1))
  • C X -= X | -X
  • D X ^= X & (X ^ (x - 1))
查看答案与解析
答案:D
这道题暂未补解析。
45. 单选题

③处应填()

  • A -INF
  • B Max[y] [x]
  • C 0
  • D Max[x][yJ
查看答案与解析
答案:C
这道题暂未补解析。
46. 单选题

⑤处应填()

  • A to_max(Max[y][z],v + w(a ^(z << B)))
  • B to_max(Max[z][y],v + w((x ^ z) << B))
  • C to_max(Max[zJ[y],v + w(a ^ (z << B)))
  • D to_max(Max[x][z],v + w(y ^ z))
查看答案与解析
答案:B
这道题暂未补解析。

二、简答题

16. 简答题

假设输入的n和d[i]都是不超过10000的正整数,完成下面的判断题和单 选题:

查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
23. 简答题

假设输入的n, k和d[i]都是不超过10000的正整数,且k不超过n,并 假设rand()函数产生的是均匀的随机数,完成下面的判断题和单选题:

查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
26. 简答题

(2.5分)当输入的d[i]是严格单调递增序列时,第17行的 “swap”平均执行次数是()。

查看答案与解析
答案:A,B,C,D
这道题暂未补解析。
30. 简答题

01 #include <iostream>

02 #include <queue>

03 using namespace std;

04

05 const int max1 = 2000000000;

06

07 class Map (

08 struct item {

09 string key; int value;

10} d[max1];

11int cnt;

12public:

13int find(string x) {

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

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

16return d[i].value;

17return -1;

18}

19static int end() { return -1; } 

20void insert(string k, int v) {

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

22}

23} s[2];

24

25class Queue {

26string q[max1];

27int head, tail;

28public:

29void pop() { ++head; }

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

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

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

33} q[2];

34

35string st0,stl;

36int m;

37

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

39string t = s;

40char tmp = t[L];

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

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

43t[R] = tmp;

44return t;

45}

46

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

48string t = s;

49char tmp = t[R];

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

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

52t[L] = tmp;

53return t;

54}

55

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

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

58return false;

59++step;

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

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

62q[p].push(st);

63return false;

64}

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

66return true;

67}

68

69int main() {

70cin >> st0 >> stl;

71int len = st0.length();

72if (len != stl.length()) { 

73cout << -1 << end1; 

74return 0;

75}

76if (st0 == st1) { 

77cout << 0 << end1; 

78return 0;

79}

80cin >> m;

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

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

83for (int p = 0;

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

85p ^=1) {

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

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

88if ((p == 0 &&

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

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

91|| 

92(p == 1 &&

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

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

95return 0;

96}

97cout << -1 << end1; 

98return 0;

99}

查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
37. 简答题

(分数背包)小S有n块蛋糕,编号从1到n第i块蛋糕的价值是wi, 体积是vi。他有一个大小为B的盒子来装这些蛋糕,也就是说装入盒子的 蛋糕的体积总和不能超过B。

他打算选择一些蛋糕装入盒子,他希望盒子里装的蛋糕的价值之和尽量 大。

为了使盒子里的蛋糕价值之和更大,他可以任意切割蛋糕。具体来说,他 可以选择一个a (0<a<l),并将一块价值是w,体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是(l-a)・w.体 积是(l-a)v。他可以重复无限次切割操作。

现要求编程输出最大可能的价值,以分数的形式输出。

比如n=3, B=8,三块蛋糕的价值分别是4、4、2,体枳分别是5、3、2。 那么最优的方案就是将休积为5的蛋糕切成两份,一份体积是3,价值是 2.4,另一份体积是2,价值是1.6,然后把休积是3的那部分和后两块蛋 糕打包进盒子。最优的价值之和是8.4,故程序输出42/5。

输入的数据范围为:1≤n≤1000,1≤B≤10^5;1≤wi,vi≤100。

提示:将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。 

试补全程序。

#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 d = 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[i]);

}

 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(int i = 2; i <= n; i ++) 

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

curV += v[i]; 

curW += w[i];

} else {

print(④); 

return 0;

}

print (⑤);

return 0;

}


查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
43. 简答题

(最优子序列)取m=6,给出长度为n的整数序列a1,a2,……an(0 ≤ ai<2m)。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1,b2,…,bk,定 义其子序列分值S为w(b1㊉b2)+w(b2㊉b3)+w(b3㊉b4)+……+w(bk-1㊉bk)。其中㊉表示按位异或。对于空子序列,规定其子序列分值为0。求一个子序列使得其子序列分值最大,输出这个最大值。

输入第一行包含一个整数n(1 ≤ n ≤  40000).接下来一行包含n个整数 a1,a2,……,an。

提示:考虑优化朴素的动态规划算法,将前位和后位分开计算。

Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。

试补全程序。

查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。

三、判断题

17. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
18. 判断题

输出一定大于等于0。()

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
19. 判断题

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

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
20. 判断题

将第14行的“d[i] < d[j]"改为wd[i] != d[j]”,程序输出不会改 变。()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
24. 判断题

第9行的“x”的数值范围是L+1到R.即[L+l, R]。()

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
25. 判断题

将第19行的“d[a]”改为“d[b]“,程序不会发生运行错误。()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
31. 判断题

输出可能为0 ()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
32. 判断题

若输入的两个字符串长度均为101时,则m=0时的输出, m=10O时的 输出是一样的。()

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
33. 判断题

若两个字符串的长度均为n,则最坏情况下,此程序的时间复杂度为 0(n!)。 ()

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。