2022年CSP-J初赛试卷

阅读量: 512 编辑
2022 CCF 非专业级别软件能力认证第一轮(CSP-J)入门级C++语言试题

考试认证时间:2022年9月18日09:30~11:30

共 39 题,包括选择题、程序阅读题、完善程序题

一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)

1、以下哪种功能没有涉及C++ 语言的面向对象特性支持: ( )。

2、有6个元素,按照6、5、4、3、2、1的顺序进入栈S, 请问下列哪个出栈序列是非法的( )

3、运行以下代码片段的行为是( )

int x = 101;
int y = 201;
int *p = &x;
int *q = &y
p = q;

4、链表和数组的区别包括( )

5、对假设栈S 和队列Q 的初始状态为空。存在e1~e6 六个互不相同的数据,每个数据按照 进栈S、 出栈S、 进队列Q、 出队列Q 的顺序操作,不同数据间的操作可能会交错。已知栈S 中依次有数据e1、e2、e3、e4、e5 和e6 进栈,队列Q 依次有数据e2、e4、e3、e6、e5 和 e1 出队列。则栈S 的容量至少是( )个数据。

6、对表达式 a+(b-c)*d 的前缀表达式为( ),其中+、 -、*是运算符。

7、假设字母表{a,b,c,d,e} 在字符串出现的频率分别为10%,15%,30%,16%, 29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码,字母 d 的编码长度为 ( )位。

8、一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第1个位 置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子结点的位置分别是( )。

9、考虑由N 个顶点构成的有向连通图,采用邻接矩阵的数据结构表示时,该矩阵中至少存在( )个非零元素。

10、以下对数据结构的表述不恰当的一项为: ( )。

11、以下哪组操作能完成在双向循环链表结点 p 之后插入结点s 的效果(其中, next 域为结点的直接后继, prev 域为结点的直接前驱): ( )

12、 以下排序算法的常见实现中,哪个选项的说法是错误的: ( )。

13、 八进制数32.1对应的十进制数是( )

14、一个字符串中任意个连续的字符组成的子序列称为该字符串的子串,则字符串 abcab 有( )个内容互不相同的子串。

15、以下对递归方法的描述中,正确的是 ( )

二 、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确、错误,除特殊说明外,判断题1.5分,选择题3分,共计40分)

程序(1)

01    #include <iostream>
02
03    using namespace std;
04
05    int main()
06    {
07       unsigned short x, y;
08       cin >> x  >> y;
09       x = (x | x <<  2) & 0x33;
10       x = (x | x <<  1) & 0x55;
11       y = (y | y <<  2) & 0x33;
12       y = (y | y <<  1) & 0x55;
13       unsigned short  z  =  x |  y  << 1;
14       cout << z << endl;
15       return  0;
16    }

假设输入的x、y 均是不超过15的自然数,完成下面的判断题和单选题:

16、删去第7行与第13行的unsigned, 程序行为不变。( )

17、将第7行与第13行的 short 均改为char, 程序行为不变。 ( )

18、程序总是输出一个整数“0”。 ( )

19、当输入为“22”时,输出为“10”。 ( )

20、当输入为“22”时,输出为“59”。 ( )

21、当输入为“138”时,输出为( )

程序(2)

01   #include <algorithm>
02   #include <iostream>
03   #include <limits>
04   
05   using namespace std; 
06   
07   const int MAXN = 105;
08   const int MAXK = 105;
09   
10   int h[MAXN][MAXK]; 
11    
12   int f(int n, int m) 
13   {
14   	if(m == 1)return n;
15   	if(n == 0)return 0; 
16   	
17   	int ret = numeric_limits<int>::max();
18   	for(int i = 1; i<= n; i++)
19   		ret = min(ret,max(f(n - i,m),f(i - 1,m - 1))+1);
20   	return ret;
21   }
22   
23   int g(int n, int m)
24   {
25   	for (int i = 1; i <= n; i++)
26   	    h[i][1] = i;
27   	for (int j = 1;j <= m; j++)
28   	    h[0][j] = 0;
29   	
30   	for(int i = 1; i<= n; i++){
31   	    for(int j = 2;j <= m; j++){
32   	        h[i][j] = numeric_limits<int>::max();
33   	        for(int k = 1; k <= i; k++) 
34   				h[i][j] = min(
35   	              	h[i][j],
36   	              	max(h[i - k][j],h[k - 1][j - 1]) + 1);
37   		}
38   	}
39   	
40   	return h[n][m];
41   }
42   
43   int main()
44   {
45   	int n, m;
46   	cin >> n >> m;
47    	cout << f(n,m) << endl << g(n,m) << endl;
48    	return 0; 
49   }

假设输入的n、m 均是不超过100的正整数,完成下面的判断题和单选题:

22、当输入为“73”时,第19行用来取最小值的min 函数执行了449次。 ( )

23、输出的两行整数总是相同的( )

24、当 m 为1时,输出的第 一 行总为n ( )

25、算法 g(n,m) 最为准确的时间复杂度分析结果为( )。

26、当输入为 “202” 时,输出的第一行为 ( )

27、当输入为“100100”时,输出的第一行为( )

程序(3)

01 	#include <iostream>
02 	
03 	using namespace std;
04 	
05 	int n, k; 
06 	
07 	int solve1()
08 	{
09 		int l = 0,r = n;
10 		while(l <= r){
11 	        int mid = (l + r)/ 2;
12 	        if (mid * mid <= n)l = mid + 1;
13 	        else r = mid - 1; 
14 		}
15 	   	return l - 1; 
16 	}
17 	
18 	double solve2(double x)
19 	{
20 		if(x == 0) return x;
21 	 	for(int i = 0; i < k; i++)
22 	        x = (x + n / x) / 2;
23 	     return x
24 	}
25 	
26 	int main()
27 	{
28 		cin >> n >>k;
29 	    double ans = solve2(solve1());
30 	    cout << ans << " " << (ans * ans == n) << endl;
31 	    return 0; 
32 	}

假设 int 为32位有符号整数类型,输入的 n 是不超过47000的自然数、 k 是不超过 int 表示范围的自然数,完成下面的判断题和单选题:

28、该算法最准确的时间复杂度分析结果为 (log n+k)。

29、当输入为“98011”时,输出的第一个数为“99”。 ( )

30、 对于任意输入的n, 随着所输入 k 的增大,输出的第二个数会变成“1”。( )

31、 该程序有存在缺陷。当输入的 n 过大时,第12 行的乘法有可能溢出,因此应当将 mid 强制转换为64位整数再计算。

32、当输入为“21”时,输出的第一个数最接近( )。

33、当输入为“310”时,输出的第一个数最接近( )

34、当输入为“25611”时,输出的第一个数 ( )

三、完善程序(单选题,每小题3分,共计30分)

(枚举因数)从小到大打印正整数n 的所有正因数。

01 	#include <bits/stdc++.h>
02 	using namespace std;
03 	
04 	int main(){
05 		int n;
06 	    cin >> n;
07 	
08 	   	vector<int> fac;
09 	   	fac.reserve((int)ceil(sqrt(n)));
10 	
11 	   	int i;
12 	   	for (i = 1; i * i < n; ++i){
13 			if( ① ){
14 				fac.push_back(i);
15 			}
16 	    }
17 	
18 	   	for (int k = 0; k < fac.size(); ++k){
19 	    	cout << ② << " ";
20 	   	}
21 	   	if ( ③ ){
22 	    	cout << ④ << " ";
23 	   	}
24 	    for (int k = fac.size() - 1; k >= 0; --k){
25 	    	cout << ⑤ << " ";
26 	   	}
27 	}

35、① 处应填( )

36、② 处应填( )

37、③ 处应填( )

38、④ 处应填( )

39、⑤ 处应填( )

爱码岛编程公众号
微信扫码关注
爱码岛编程小程序
微信扫码打开
苏ICP备13052010号
©2023 南京匠成信息科技有限公司