#3295. CSP-J 2024 第一轮（初赛）模拟 Ⅱ

CSP-J 2024 第一轮（初赛）模拟 Ⅱ

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

1、在C++中，以下哪种方式不能用于向函数传递参数（ ）： {{ select(1) }}

  • 值传递
  • 模版传递
  • 引用传递
  • 指针传递

2、以下关于算法描述正确的是（ ） {{ select(2) }}

  • 算法是为解决问题而编制的计算机程序
  • 算法是为解决问题而采用的计算机程序设计语言
  • 算法是为解决问题而采用的计算方法
  • 算法是为解决问题而采取的方法与步骤

3、在关系数据库中，存放在数据库中的数据的逻辑结构以（ ）为主 {{ select(3) }}

  • 二维表
  • 二叉树
  • 哈希表
  • 邻接表

4、设某算法的时间复杂度函数的递推方程是T(n) = T(n - 1) + n（n为正整数）及T(0) = 1，则该算法的时间复杂度为（ ）。 {{ select(4) }}

  • O(logn)O(logn)
  • O(n)O(n)
  • O(n2)O(n^2)
  • O(nlogn)O(nlogn)

5、在使用C++语言中一般提到的“空间复杂度”中的“空间”是指（ ） {{ select(5) }}

  • 程序运行时所占的内存大小
  • 程序运行时所占的数组大小
  • 程序运行时所占的硬盘大小
  • 程序源文件所占的硬盘大小

6、2017 年 9 月 30 日是星期六，1999 年 9 月 30 日是（ ） {{ select(6) }}

  • 星期三
  • 星期六
  • 星期五
  • 星期四

7、设栈 S 的初始状态为空，元素 1, 2, 3, 4, 5 依次入栈，以下出栈序列不可能出现的有（ ） {{ select(7) }}

  • 1, 2, 3, 5, 4
  • 2, 3, 1, 5, 4
  • 1, 5, 3, 2, 4
  • 4, 3, 5, 2, 1

8、关于分治算法，下列说法错误的是（ ） {{ select(8) }}

  • 分治算法核心思想是分而治之，把问题转化为多个规模更小的子问题求解。
  • 分治算法可以不使用递归实现。
  • 分治算法的时间复杂度是O(logn)，其中n表示问题的规模。
  • 二分法、快速排序等算法都是典型的使用分治思想的算法。

9、如下代码主要是表示什么数据结构?（ ）

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;	
} LTNode;

{{ select(9) }}

  • 单向链表
  • 双向链表
  • 循环链表
  • 优先队列

10、使用如下代码片段定义四个字符串（假设头文件已正确定义），以下说法错误的是（ ）

string str1 = "csp"
string str2 = str1;
char str3[] = "csp";
char * str4 = str3;

{{ select(10) }}

  • 对于四个字符串，都可以使用 std::cout 输出其中的内容（例如,cout<<str3; str3;）
  • str3 只占用 4 字节内存，但 str1 却要占用更多内存
  • 由于 str2 由 str1 直接赋值得到，因此二者指向同一块内存，即修改str1 的内容后 str2 的内容也会随之改变
  • 由于 str4 由 str3 直接赋值得到，因此二者指向同一块内存，即修改str3 的内容后 str4 的内容也会随之改变

11、冯诺依曼体系结构中组成计算机的五大部件是（ ） {{ select(11) }}

  • 总线，处理器，存储器，输入设备，输出设备
  • 处理器，运算器，存储器，输入设备，输出设备
  • 总线，控制器，存储器，输入设备，输出设备
  • 控制器，运算器，存储器，输入设备，输出设备

12、如下代码对树的操作是（ ）

void postorder(tree bt) 
{
  	if(bt)
	{
 	    postorder(bt->lchild);
  	    postorder(bt->rchild);
 	    cout << bt->data;
 	}
}

{{ select(12) }}

  • 后序遍历
  • 中序遍历
  • 前序遍历
  • 层次遍历

13、有规格尺寸相同5种颜色不同的手套各15只混装在箱子里（不分左右），从里面至少取出多少只一定能配出三副相同颜色的手套？（ ） {{ select(13) }}

  • 8
  • 9
  • 10
  • 11

14、由3个a，5个b和2个c构成的字符串中，包含子串“abc”的共有（ ） {{ select(14) }}

  • 39600
  • 780
  • 840
  • 260

15、1 GB代表的字节数量是（ ） {{ select(15) }}

  • 2102^{10}
  • 2202^{20}
  • 2302^{30}
  • 2402^{40 }

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

01 #include<bits/stdc++.h>
02 using namespace std;
03 const int SIZE = 25;
04 int n,k,a[SIZE];
05 int cnt=0;
06 long long ans;
07 bool isPrime(int n)
08 {
09	   cnt++;
10	   cout<<cnt<<endl;
11	   if(n<=1)
12	       return false;
13	   for(int i=2;i*i<=n;++i)
14	      if(0==n%i)
15		    return false;
16	   return true;
17 }
18 void dfs(int m, int sum, int x)
19 {
20	   if(m==k)
21	   {
22	      if(isPrime(sum))
23	      {
24		     ans++;
25	      }
26	      return;
27	   }
28	   for(int i=x;i<n;++i)
29	       dfs(m+1,sum+a[i],i+1);
30	   return;
31 }
32 int main()
33 {
34	   cin >> n >> k;
35	   for (int i = 0; i < n;++i)
36	       cin >> a[i];
37	   dfs(0,0,0);
38	   cout << ans <<endl;
39	   return 0;
40 }

判断题

16、将第 13 行i*i ≤\le n改为i ≤\le qrt(n)程序运行结果不会改变。 ( )

{{ select(16) }}

  • 正确
  • 错误

17、将第 29 行sum+a[i]改为sum+=a[i]程序运行结果不会改变。 {{ select(17) }}

  • 正确
  • 错误

18、若输入 k 值比 n 大，则程序会死循环无输出。 {{ select(18) }}

  • 正确
  • 错误

19、将第 14 行文件if(0==n%i)替换成if(n%i==0)，程序运行结果不会改变。 {{ select(19) }}

  • 正确
  • 错误

选择题

20、若输入k的值为6，且输入n≥\geq k，a数组的元素均为相等的正整数，则输出为（ ） {{ select(20) }}

  • 0
  • 2
  • 4
  • 8

21、若输入12 8, 则isPrime被调用次数为（ ）。 {{ select(21) }}

  • 4
  • 66
  • 132
  • 495
01 #include <bits/stdc++.h>
02 using namespace std;
03 int CNT, p; 
04 int check(int tmp, int n)
05 {
06	 int res = 0;
07	 for(int i=tmp; i>0; i--)
08	 {
09		res += n;
10		int a=0, ans=res;
11		while(ans%n == 0)
12			a++, ans/=n;
13		i -= a-1;
14	 }
15	 return res;
16 }
17 int main()
18 {
19	 cin >> CNT;
20	 while(CNT--)
21	 {
22	    int ans=1;
23	    cin >> p;
24	    for(int i=2; i<=sqrt(p); i++)
25	    {
26		  int tmp=0;
27		  while(p%i == 0)
28		      tmp++, p/=i;
29		  if(tmp)
30		      ans = max(ans,check(tmp,i));
31	    }
32	    ans = max(ans,p);
33	    cout<<ans<<endl;
34	 }
35	 return 0; 
36 }

判断题

22、若输入 1 2, 程序的输出会报错。 {{ select(22) }}

  • 正确
  • 错误

23、若第 27 行 while 改为 if，程序输出结果不变。 {{ select(23) }}

  • 正确
  • 错误

24、若输入 p 是一个质数，程序第 30 行不会被执行。 {{ select(24) }}

  • 正确
  • 错误

25、若输入 p 是一个质数，则输出 ans 的值为 p。 {{ select(25) }}

  • 正确
  • 错误

选择题

26、若输入1 36，则输出为（ ）。

{{ select(26) }}

  • 36
  • 6
  • 4
  • 9

27、若tmp < n，则返回的 res 结果为（ ）。

{{ select(27) }}

  • n
  • tmp
  • tmp*n
  • tmp+n
01 #include<iostream>
02 #include<string>
03 #include<set>
04 using namespace std;
05 string a, s[105];
06 int cnt=0;
07 set<string>dict;
08 void trim(string &s)
09 {
10	   if(!s.empty())
11	   {
12    	  s.erase(0,s.find_first_not_of(" "));
13	       s.erase(s.find_last_not_of(" ")+1);
14	   }
15 }
16 int main()
17 {
18     cin>>a;
19     while(a!="#")
20     {
21    	   int length = a.length();
22    	   for(int i=0;i<length;i++)
23    	       if(isalpha(a[i]))
24    		      a[i] = tolower(a[i]);
25    	       else
26    		      a[i] = ' ';
27    	   trim(a);
28    	   s[cnt]=a;
29    	   dict.insert(a);
30    	   cnt++;
31    	   cin>>a;
32	    }
33	    for(set<string>::iterator it=dict.begin();it!=dict.end();++it)
34    	    cout << *it << " ";
35      return 0;
36 }

判断题

28、STL模板库中的set属于关联式容器。 ( ) {{ select(28) }}

  • 正确
  • 错误

29、若将第 6 行int cnt=0替换为int cnt，程序运行结果不会改变。 ( ) {{ select(29) }}

  • 正确
  • 错误

30、若将第 21 行a.length()替换为a.size()，程序运行结果不会改变。 ( )

{{ select(30) }}

  • 正确
  • 错误

31、若输入34 12 56 #，则程序输出 12 34 56。 ( ) {{ select(31) }}

  • 正确
  • 错误

选择题（最后一题4分）

32、若输入数据为A Dream Is To Build A Big Big World #，则输出是（ ）。

{{ select(32) }}

  • A Dream Is To Build A Big Big World
  • a dream is to build a big big world
  • a big build dream is to world
  • A Big Build Dream Is To World

33、若输入数据为WorldYiwu AsiaShanghai ChinaHangzhou ZhejiangJinhua #，则输出是（ ）。

{{ select(33) }}

  • WorldYiwu AsiaShanghai ChinaHangzhou ZhejiangJinhua
  • worldyiwu asiashanghai chinahangzhou zhejiangjinhua
  • AsiaShanghai ChinaHangzhou WorldYiwu ZhejiangJinhua
  • asiashanghai chinahangzhou worldyiwu zhejiangjinhua

34、若输入数据为I am 12 years old. #，则输出是（ ）。

{{ select(34) }}

  • am i old years
  • am I old years
  • I am years old.
  • I am 12 years old.

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

  1. 假设有一个无向图，将这个无向图的某一条欧拉路或者欧拉回路用算法实现打印出来。

样例输入:第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。

5 5
1 2
2 3
3 4
4 5
5 1

样例输出:欧拉路或欧拉回路

1 5 4 3 2 1

01 #include<bits/stdc++.h>
02 using namespace std;
03 #define MAXN 105
04 int g[MAXN][MAXN];      
05 int du[MAXN];           
06 int circuit[MAXN];      
07 int n,e,circuitpos,x,y,start;
08 void find_circuit(int i)        
09 {
10	    for (int j = 1; j <= n; j++)
11	        if ( ① )          
12	        {
13		       g[j][i] = 0;
14		       g[i][j] = 0; 
15		       find_circuit(j);
16	        }
17	    ②;   
18 }
19 int main()
20 {
21     memset(g,0,sizeof(g));
22     cin >> n >> e;
23     for (int i = 1; i <= e; i++)
24     {
25	       cin >> x >> y;
26	       g[y][x] = 1;
27	       ③; 
28	       du[x]++;      
29	       du[y]++;
30     }
31     start = 1;          
32     for (int i = 1; i <= n; i++) 
33	       if ( ④ )    
34             start = i;
35	   circuitpos = 0;
36	    ⑤;
37	   for (int i = 1; i <= circuitpos; i++)
38	       cout << circuit[i] << ' ';
39	   cout << endl;
40	   return 0;
41 }

35、①处应填( )

{{ select(35) }}

  • g[i][j] == 0
  • g[i][j] == 1
  • du[i] == 1
  • du[j] == 1

36、②处应填( )

{{ select(36) }}

  • circuit[++circuitpos] = i
  • circuit[circuitpos] = i
  • circuit[j] = i
  • circuit[i] = j

37、③处应填( )

{{ select(37) }}

  • start=1
  • start=0
  • g[x][y]=1
  • g[x][y]=0

38、④处应填( )

{{ select(38) }}

  • g[i][j] % 2 == 0
  • g[i][j] % 2 == 1
  • du[i] % 2 == 0
  • du[i] % 2 == 1

39、⑤处应填( )

{{ select(39) }}

  • find_circuit(0)
  • find_circuit(start)
  • find_circuit(1)
  • find_circuit(n)
  1. 设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为did_i，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
  • subtree的左子树的加分×subtree的右子树的加分＋subtree的根的分数。
  • 若某个子树为空，规定其加分为1。
  • 叶子的加分就是叶节点本身的分数，不考虑它的空子树。

试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。

要求输出：

  • 1、tree的最高加分
  • 2、tree的前序遍历

输入格式

第1行：一个整数n，为节点个数。

第2行：n个用空格隔开的整数，为每个节点的分数（0<分数<100）。

输出格式

第1行：一个整数，为最高加分（结果不会超过int范围）。

第2行：n个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。

数据范围

n<30n<30

5
5 7 1 2 10

145
3 1 2 4 5

01 #include<bits/stdc++.h>
02 using namespace std;
03 const int N=30;
04 int n, w[N], f[N][N], rt[N][N];
05 void print(int l, int r)
06 {
07	    if(l > r)
08		  return;
09	    ①; 
10	    printf("%d ",root);
11	    ②;    
12	    print(root+1, r);
13 }
14 int main() 
15 {
16	    memset(f,0,sizeof(f));
17      scanf("%d", &n);
18      for (int i=1; i<=n; ++i) 
19	    {
20          scanf("%d", &w[i]);
21          ③;			
22          rt[i][i] = i;
23      }
24      for (int l=n; l>=1; l--) //枚举左端点
25          for(int r=l+1; r<=n; r++)//枚举右端点
26		       for(int root=l; root<=r; root++)//枚举这段结点的根 
27		       {
28                  int lw=f[l][root-1];
29  		     ④;				
30   		     if(lw == 0)
31			         lw = 1; 
32    		     if(rw == 0)
33			         rw = 1; 
34		           if( ⑤ )
35		           {
36			         f[l][r] = lw*rw+w[root]; 
37			         rt[l][r] = root; 
38		           }					
39	             }
40      printf("%d\n", f[1][n]);//整棵树的最优答案 
41      print(1, n);		      //前序遍历整棵树 
42      printf("\n");
43      return 0;
44 }

40、①处应填( )

{{ select(40) }}

  • int root = 0
  • int root = 1
  • int root = rt[l][r]
  • int root = rt[1][n]

41、②处应填( )

{{ select(41) }}

  • print(1, root-1)
  • print(l, root-1)
  • print(1, root)
  • print(l, root)

42、③处应填( )

{{ select(42) }}

  • f[i][i] = 0
  • f[i][i] = 1
  • f[i][i] = i
  • f[i][i] = w[i]

43、④处应填( )

{{ select(43) }}

  • int rw=f[root][r]
  • int rw=f[root+1][r]
  • int rw=f[root][n]
  • int rw=f[root+1][n]

44、⑤处应填( )

{{ select(44) }}

  • lw*rw+w[root] > f[l][r]
  • lw*rw+w[root] < f[l][r]
  • lw*rw+w[root] > f[1][n]
  • lw*rw+w[root] < f[1][n]
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  6. Worker 0, 45ms
  7. Powered by Hydro v4.18.0 Community