首页 › 试卷 › 信息学奥赛 › 信息学奥赛-提高级 › 2019CCF非专业级别软件能力认证第一轮 (CSP-S)提高组(初赛)

2019CCF非专业级别软件能力认证第一轮 (CSP-S)提高组(初赛) VIP

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

一、单选题

1. 单选题

若有定义:int a=7; float x=2.5, y=4.7;则表达式x+a%3*(int)(x+y)%2的值是:( )

  • A 0.000000
  • B 2.750000
  • C 2.500000
  • D 3.500000
查看答案与解析
答案:D
这道题暂未补解析。
2. 单选题

下列属于图像文件格式的有( )

  • A WMV
  • B MPEG
  • C JPEG
  • D AVI
查看答案与解析
答案:C
这道题暂未补解析。
3. 单选题

二进制数11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑或运算的结果是( )

  • A 11 1111 1101
  • B 11 1111 1111 1101
  • C 10 1111 1111 1111
  • D 11 1111 1111 1111
查看答案与解析
答案:D
这道题暂未补解析。
4. 单选题

编译器的功能是( )

  • A 将源程序重新组合
  • B 将一种语言(通常是高级语言)翻译成另一种语言(通常是低级语言)
  • C 将低级语言翻译成高级语言
  • D 将一种编程语言翻译成自然语言
查看答案与解析
答案:B
这道题暂未补解析。
5. 单选题

设变量x为float型且已赋值,则以下语句中能将x中的数值保留到小数点后两位,并将第三位四舍五入的是( )

  • A X=(x*100+0.5)/100.0
  • B x=(int)(x*100+0.5)/100.0
  • C x=(x/100+0.5)*100.0
  • D x=x*100+0.5/100.0
查看答案与解析
答案:B
这道题暂未补解析。
6. 单选题

由数字1,1,2,4,8,8所组成的不同的4位数的个数是( )

  • A 104
  • B 102
  • C 98
  • D 100
查看答案与解析
答案:B
这道题暂未补解析。
7. 单选题

排序的算法很多,若按排序的稳定性和不稳定性分类,则( )是不稳定排序。

  • A 冒泡排序
  • B 直接插入排序
  • C 快速排序
  • D 归并排序
查看答案与解析
答案:C
这道题暂未补解析。
8. 单选题

G是一个非连通无向图(没有重边和自环),共有28条边,则该图至少有( )个顶点

  • A 10
  • B 9
  • C 11
  • D 8
查看答案与解析
答案:B
这道题暂未补解析。
9. 单选题

一些数字可以颠倒过来看,例如0、1、8颠倒过来看还是本身,6颠倒过来是9,9颠倒过来看还是6,其他数字颠倒过来都不构成数字。类似的,一些多位数也可以颠倒过来看,比如106颠倒过来是901。假设某个城市的车牌只有5位数字,每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌,并且车牌上的5位数能被3整除?( )

  • A 40
  • B 25
  • C 30
  • D 20
查看答案与解析
答案:B
这道题暂未补解析。
10. 单选题

一次期末考试,某班有15人数学得满分,有12人语文得满分,并且有4人语、数都是满分,那么这个班至少有一门得满分的同学有多少人?( )

  • A 23
  • B 21
  • C 20
  • D 22
查看答案与解析
答案:A
这道题暂未补解析。
11. 单选题

设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,请问任何以元素比较作为基本运算的归并算法,在最坏情况下至少要做多少次比较?( )

  • A n2
  • B n log n
  • C 2n
  • D 2n-1
查看答案与解析
答案:D
这道题暂未补解析。
12. 单选题

以下哪个结构可以用来存储图( )

  • A 栈
  • B 二叉树
  • C 队列
  • D 邻接矩阵
查看答案与解析
答案:D
这道题暂未补解析。
13. 单选题

以下哪些算法不属于贪心算法?( )

  • A Di jkstra算法
  • B Floyd算法
  • C Prim算法
  • D Kruskal算法
查看答案与解析
答案:B
这道题暂未补解析。
14. 单选题

有一个等比数列,共有奇数项,其中第一项和最后一项分别是2和118098,中间一项是486,请问以下哪个数是可能的公比?( )

  • A 5
  • B 3
  • C 4
  • D 2
查看答案与解析
答案:B
这道题暂未补解析。
15. 单选题

有正实数构成的数字三角形排列形式如图所示。第一行的数为a1,1;第二行的数从左到右依次为a2,1,a2,2,第n行的数为an,1,an,2,…,an,n。从a1,1开始,每一行的数ai,j只有两条边可以分别通向下一行的两个数ai+1,j和ai+1,j+1。用动态规划算法找出一条从a1,1向下通道an,1,an,2,…,an,n中某个数的路径,使得该路径上的数之和最大。

令C[i][j]是从a1,1到ai,j的路径上的数的最大和,并且C[i][0]= C[0][j]=0,则C[i][j]=( )

  • A max{C[i-1][j-1],C[i-1][j]}+ ai,j
  • B C[i-1][j-1]+C[i-1][j]
  • C max{C[i-1][j-1],c[i-1][j]}+1
  • D max{C[i][j-1],C[i-1][j]}+ ai,j
查看答案与解析
答案:A
这道题暂未补解析。
21. 单选题

(3分)若输入的a数组是一个严格单调递增的数列,此程序的时间复杂度是( )。

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

最坏情况下,此程序的时间复杂度是( )。

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

当n等于50时,若a、b的值都在[0,49]的范围内,且在第25行时x总是不等于y,那么输出为( )

  • A 1276
  • B 1176
  • C 1225
  • D 1250
查看答案与解析
答案:C
这道题暂未补解析。
29. 单选题

此程序的时间复杂度是( )

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

若tlen=10,输出为0,则slen最小为( )

  • A 10
  • B 12
  • C 0
  • D 1
查看答案与解析
答案:D
这道题暂未补解析。
36. 单选题

若tlen=10,输出为2,则slen最小为( )

  • A 0
  • B 10
  • C 12
  • D 1
查看答案与解析
答案:C
这道题暂未补解析。
38. 单选题

①处应填( )

  • A unlock[i]<=0
  • B unlock[i]>=0
  • C unlock[i]==0
  • D unlock[i]==-1
查看答案与解析
答案:C
这道题暂未补解析。
39. 单选题

②处应填( )

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

③处应填( )

  • A

     target = -1

  • B

     - -cnt[target]

  • C

     bbonus[target]=0

  • D points += bonus[target]
查看答案与解析
答案:D
这道题暂未补解析。
41. 单选题

④处应填( )

  • A cnt [child[target][i]] -=1
  • B cnt [child[target][i]] =0
  • C unlock[child[target][i]] -= 1
  • D unlock[child[target][i]] =0
查看答案与解析
答案:C
这道题暂未补解析。
42. 单选题

⑤处应填( )

  • A unlock[i] = cnt[i]
  • B unlock[i] =m
  • C unlock[i] = 0
  • D unlock[i] =-1
查看答案与解析
答案:B
这道题暂未补解析。
44. 单选题

①处应填()

  • A 0
  • B ~0u11
  • C ~0u11^1
  • D 1
查看答案与解析
答案:C
这道题暂未补解析。
45. 单选题

②处应填()

  • A a[j]<i
  • B a[j]==i
  • C a[j]!=i
  • D a[j]>i
查看答案与解析
答案:B
这道题暂未补解析。
46. 单选题

③处应填()

  • A
  • B
  • C
  • D
查看答案与解析
答案:A
这道题暂未补解析。
47. 单选题

④处应填()

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

⑤处应填()

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

二、简答题

16. 简答题

#include <cstdio>

using namespace std;

int n;

int a[100];


int main( ) {

scanf(“%d”,&n);

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

scanf(“%d”,&a[i])

int ans = 1

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

if ( i > 1 && a[i] < a[i-1])

ans = i ;

while (ans < n && a[i] >= a[ans+1])

++ans;

printf(“%d/n”, ans);

}

return 0;

}

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

#include <cstdio>

using namepace std ;


const int maxn =1000;

int n;

int fa[maxn],cnt [maxn];


int getroot(int v ) {

if (fa[v] == v) return v;

return getroot(fa[v]);

}


int main ( ) {

cin >> n;

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

fa[i]=i;

cnt[i]=1;

}

int ans = 0 ;

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

int a,b,x,y,;

cin >>a>>b

x=getRoot(a);

y=getRoot(b);

ans +=cnt[x]cnt[y];

fa[x]=y;

cnt[y] +=cnt[x];

}

cout<<ans<<endl;

return 0;

}

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

本题t是s的子序列的意思是:从s中删去若干个字符,可以得到t;特别的,如果s=t,那么t也是s的子序列;空串是任何串的子序列。例如“acd”是“abcde”的子序列,“acd”是“acd”的子序列,但“adc”不是“abcde”的子序列。

S[x…y]表示s[x]…s[y]共y-x+1个字符构成的字符串,若x>y则s[x…y]是空串。t[x…y]同理。

#include <cstdio>

#include <algorithm>

using namespace std;

const int max1 = 202;

string s, t ;

int pre[max1], suf[max1]


int main() {

cin>>s>>t;

int slen =s. length(), tlen= t. length();

for (int I = 0 ,j = 0 ; i< slen; ++i) {

if (j< tlen&&s[i]t[j] ) ++j;

pre[i] = j;// t[0…j-1]是s[0…i]的子序列

 }

for (int I = slen -1 ,j= tlen -1; I >=0;–i) {

if(j>=0&& s[i] == t [j]) –j;

suf [i]= j; //t[j+1…tlen-1]是s[i…slen-1]的子序列

}

suf[slen] = tlen -1;

int ans = 0;

for (int i=0, j=0, tmp=o; i<=slen; ++i){

while(j<=slen && tmp >=suf[j] + 1) ++j;

ans =max(ans, j – I – 1);

tmp = pre[i];

}

cout <<ans << end1;

return 0;

}

提示:

t[0…pre[i]-1]是s[0…i]的子序列;

t[suf[i]+1…tlen-1]是s[i…slen-1]的子序列。

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

(匠人的自我修养)一个匠人决定要学习n个新技术,要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。

输入第一行有两个数,分别为新技术个数n(1≤n≤103),以及已有经验值(≤107)。

接下来n行。第i行的两个正整数,分别表示学习第i个技术所需的最低经验值(≤107),以及学会第i个技术后可获得的经验值(≤104)。

接下来n行。第i行的第一个数mi(0≤mi<n),表示第i个技术的相关技术数量。紧跟着m个两两不同的数,表示第i个技术的相关技术编号,输出最多能学会的新技术个数。

下面的程序已O(n2)的时间复杂完成这个问题,试补全程序。

#inclde

using namesoace std;

const int maxn = 1001;


int n;

int cnt [maxn]

int child [maxn] [maxn];

int unlock[maxn];

int unlock[maxn];

int threshold [maxn],bonus[maxn];


bool find(){

int target=-1;

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

if(①&&②){

target = i;

break;

}

if(target-1)

return false;

unlock[target]=-1;

③;

for (int i=0;i<cut[target];++i)

④;

return true;

}


int main(){

scanf(“%d%d”,&n, &points);

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

cnt [i]=0;

scanf(“%d%d”,&threshold[i],&bonus[i];

}

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

int m;

scanf(“%d”,&m);

⑤;

for (int j=0; j<m ;++j={

int fa;

scanf(“%d”, &fa);

child [fa][cnt[fa]]=i;

++cnt[fa];

}

}

int ans = 0;

while(find())

++ans;

printf(“%d\n”, ans);

return 0;

}

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

(取石子)Alice和Bob两个人在玩取石子游戏。他们制定了n条取石子的规则,第i条规则为:如果剩余石子的个数大于等于a[i]且大于等于b[il, 那么他们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子, 而他无法按照任何规则取走石子,那么他就输了。一开始石子有m个。请问先取石子的人是否有必胜的方法?

输入第一行有两个正整数,分别为规则个数n(1≤n≤64),以及石子个数m(≤10^7)。

接下来n行。第i行有两个正整数a[i]和b[i](1≤a[i]≤10^7,1≤b[i]≤64)

如果先取石子的人必胜,那么输出“Win”,否则输出“Loss”

提示:

 可以使用动态规划解决这个问题。由于b[i]不超过64,所以可以使用64位无符号整数去压缩必要的状态。

 status是胜负状态的二进制压缩,trans是状态转移的二进制压缩。

试补全程序。

代码说明:

 “~”表示二进制补码运算符,它将每个二进制位的0变成1、1变为0; 

 而“^”表示二进制异或运算符,它将两个参与运算的数中的每个对应的二进制位一一进行比较,若两个二进制位相同,则运算结果的对应二进制位为0,反之为1。

ull标识符表示它前面的数字是unsigned long long 类型。

#include <cstdio>

#include<algorithm>

using namespace std ;


const int maxn =64;


int n,m;

int a[maxn],b[maxn];

unsigned long long status ,trans;

bool win;


int main() {

scanf("%d%d", &n, &m);

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

scanf("%d%d", &a[i], &b[i]);

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

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

if (a[i] > a[j]) {

swap(a[i],a[j]);

swap(b[i],b[j]);

}

status = ___(1)___;

trans = 0;

for(int i = 1, j = 0; i <= m; ++i) {

while (j < n && ___(2)___) {

___(3)___

++j;

}

win = ___(4)___;

___(5)___;

}

puts(win ? "Win" : "Loss");

return 0;

}

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

三、判断题

17. 判断题

(1分)第16行输出ans时,ans的值一定大于i。( )

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

(1分)程序输出的ans小于等于n。( )

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

若将第12行的“<”改为“!=”,程序输出的结果不会改变。( )

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

当程序执行到第16行时,若ans-i>2,则a[i+1]≦a[i]。( )

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

(1分)输入的a和b值应在[0,n-1]的范围内。( )

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

(1分)第16行改成“fa[i]=0;”, 不影响程序运行结果。( )

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

若输入的a和b值均在[0, n-1]的范围内,则对于任意0≤i<n,都有0≤fa[i]<n。( )

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

若输入的a和b值均在[0,n-1]的范围内,则对于任意0≤i<n,都有1≤cnt[i] ≤n。( )

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

(1分)程序输出时,suf数组满足:对任意0≤i<slen,suf[i] ≤suf[i+1]。( )

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

 (2分)当t是s的子序列时,输出一定不为0。( )

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

 (2分)程序运行到第23行时,“j-i-1”一定不小于0。( )

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

 (2分)当t是s的子序列时,pre数组和suf数组满足:对任意0≤i<slen,pre[i]>suf[i+1]+1。( )

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