【真题】暑假备战CSP-J/S：CSP-J2022普及组初赛(第一轮)试题及参考答案电子版(PDF版、无水印可直接打印)

2023-08-31 18:34:26 浏览数 (2)

资料下载

公众号内回复：CSP-J2022，即可获取下载链接，直接打印电子版让孩子做即可，文件包含

  • 试题真题
  • 参考答案

注意：其他比赛年份得资料正在紧张整理中，大家耐心等，整理完毕后，会陆续在公众号内分享。

关注：小码匠和老码农，和小码匠一起携手备战2023年CSP-J/S，祝愿所有孩子们取得好成绩！！！

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

第 1 题

以下哪种功能没有涉及C 语言的面向对象特性支持：（ ）。

A. C 中调用printf函数

B. C 中调用用户定义的类成员函数

C. C 中构造一个class或struct

D. C 中构造来源于同一基类的多个派生类

第 2 题

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

A. 5 4 3 6 1 2

B. 4 5 3 1 2 6

C. 3 4 6 5 2 1

D. 2 3 4 1 5 6

第 3 题

运行以下代码片段的行为是 （ ）。

代码语言：javascript复制
int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;

A. 将x的值赋为201

B. 将y的值赋为101

C. 将q指向x的地址

D. 将p指向y的地址

第 4 题

链表和数组的区别包括（ ）。

A. 数组不能排序，链表可以

B. 链表比数组能存储更多的信息

C. 数组大小固定，链表大小可动态调整

D. 以上均正确

第 5 题

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

A. 2

B. 3

C. 4

D. 6

第 6 题

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

A. * a-bcd

B. a*-bcd

C. abc-d*

D. abc- d

第 7 题

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

A. 1

B. 2

C. 2或3

D. 3

第 8 题

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

A. 8、18

B. 10、18

C. 8、19

D. 10、19

第 9 题

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

A. N-1

B. N

C. N 1

D.

第 10 题

10.以下对数据结构的表述不恰当的一项为：（ ）。

A. 图的深度优先遍历算法常使用的数据结构为栈。

B. 栈的访问原则为后进先出，队列的访问原则是先进先出。

C. 队列常常被用于广度优先搜索算法。

D. 栈与队列存在本质不同，无法用栈实现队列。

第 11 题

以下哪组操作能完成在双向循环链表结点p之后插入结点s的效果（其中，next域为结点的直接后继，prev域为结点的直接前驱）：（ ）。

A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;

B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;

C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;

D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

第 12 题

以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

A. 冒泡排序算法是稳定的

B. 简单选择排序是稳定的

C. 简单插入排序是稳定的

D. 归并排序算法是稳定的

第 13 题

八进制数32.1对应的十进制数是（ ）。

A. 24.125

B. 24.250

C. 26.125

D. 26.250

第 14 题

一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串abcab有（ ）个内容互不相同的子串。

A. 12

B. 13

C. 14

D. 15

第 15 题

以下对递归方法的描述中，正确的是：（ ）

A. 递归是允许使用多组参数调用函数的编程技术

B. 递归是通过调用自身来求解问题的编程技术

C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型

D. 递归是将用某种高级语言转换为机器代码的编程技术

第 16 题

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

代码语言：javascript复制
#include <iostream>

using namespace std;

int main()
 {
   unsigned short x, y;
   cin >> x >> y;
   x = (x | x << 2) & 0x33;
   x = (x | x << 1) & 0x55;
   y = (y | y << 2) & 0x33;
   y = (y | y << 1) & 0x55;
   unsigned short z = x | y << 1;
   cout << z << endl;
   return 0;
 }

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

判断题

  1. 删去第7行与第13行的unsigned，程序行为不变。（ ）
    • A. 正确
    • B. 错误
  2. 将第7行与第13行的short均改为char，程序行为不变。（ ）
    • A. 正确
    • B. 错误
  3. 程序总是输出一个整数“0”。（ ）
    • A. 正确
    • B. 错误
  4. 当输入为“2 2”时，输出为“10”。（ ）
    • A. 正确
    • B. 错误
  5. 当输入为“2 2”时，输出为“59”。（ ）
    • A. 正确
    • B. 错误

单选题

  1. 当输入为“13 8”时，输出为（ ）。
    • A. “0”
    • B. “209”
    • C. “197”
    • D. “226”

第 17 题

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

代码语言：javascript复制
#include <algorithm>
#include <iostream>
#include <limits>

using namespace std;

const int MAXN = 105;
const int MAXK = 105;

int h[MAXN][MAXK];

int f(int n, int m)
{
   if (m == 1) return n;
   if (n == 0) return 0;

   int ret = numeric_limits<int>::max();
   for (int i = 1; i <= n; i  )
       ret = min(ret, max(f(n - i, m), f(i - 1, m - 1))   1);
   return ret;
 }

int g(int n, int m)
{
   for (int i = 1; i <= n; i  )
       h[i][1] = i;
   for (int j = 1; j <= m; j  )
       h[0][j] = 0;

   for (int i = 1; i <= n; i  ) {
     for (int j = 2; j <= m; j  ) {
         h[i][j] = numeric_limits<int>::max();
         for (int k = 1; k <= i; k  )
         h[i][j] = min( h[i][j],max(h[i - k][j], h[k - 1][j - 1])   1);
       }
    }
     return h[n][m];
 }

int main()
{
   int n, m;
   cin >> n >> m;
   cout << f(n, m) << endl << g(n, m) << endl;
   return 0;
 }

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

判断题

1.当输入为“7 3”时，第19行用来取最小值的min函数执行了449次。（ ）

  • A. 正确
  • B. 错误

2.输出的两行整数总是相同的。 （ ）

  • A. 正确
  • B. 错误

3.当m为1时，输出的第一行总为n。（ ）

  • A. 正确
  • B. 错误

4.算法g(n,m)最为准确的时间复杂度分析结果为（ ）。

  • A.
  • B. O(nm)
  • C. O(n^2m)
  • D.

5.当输入为“20 2”时，输出的第一行为（ ）。

  • A.“4”
  • B.“5”
  • C.“6”
  • D.“20”

6.（4分）当输入为“100 100”时，输出的第一行为（ ）。

  • A.“6”
  • B.“7”
  • C.“8”
  • D.“9”

第 18 题

代码语言：javascript复制
#include <iostream>

using namespace std;

int n, k;

int solve1()   
{
   int l = 0, r = n;
   while (l <= r) {
     int mid = (l   r) / 2;
     if (mid * mid <= n) l = mid   1;
     else r = mid - 1;
   }
   return l - 1;
 }  

double solve2(double x)
{
     if (x == 0) return x;
     for (int i = 0; i < k; i  )
         x = (x   n / x) / 2;
     return x;
 }   
  
int main()
{
     cin >> n >> k;
     double ans = solve2(solve1());
     cout << ans << ' ' << (ans * ans == n) << endl;
     return 0;
 }

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

判断题

1.该算法最准确的时间复杂度分析结果为

pdf 程序 队列 数据 数组

0 人点赞