#ACSP1004. cspj-模拟题4

cspj-模拟题4

普及组CSP-J 2024 初赛模拟卷4

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

  1. 正整数 2024 与 1840的最大公约数是 ({{ select(1) }})。
  • 46
  • 92
  • 44
  • 184
  1. 十进制数 28与二进制数 10000001110000求和的结果是({{ select(2) }})。
  • 十进制数 8332
  • 十六进制数 208A
  • 二进制数 100000000110
  • 八进制数20212
  1. C++程序中, (25|6)^5的值是 ({{ select(3) }})。
  • 25
  • 26
  • 27
  • 28
  1. 在数组 A[x]中, 若存在(i < j)且(A[i] > A[j]), 则称(A[i], A[j])为数组A[x]的一个逆序对。对于序列(7,4,1,9,3,6,8,5), 在不改变顺序的情况下, 去掉({{ select(4) }})会使逆序对的个数减少4。
  • 1
  • 3
  • 6
  • 5
  1. 如果字符串s在字符串A中出现了，则字符串s 被称作字符串A的子串。设字符串 A=”players”的非空子串的数目是({{ select(5) }})。
  • 27
  • 29
  • 28
  • 30
  1. 以下哪种算法的主要框架不是非比较排序?({{ select(6) }})。
  • 计数排序
  • 堆排序
  • 基数排序
  • 桶排序
  1. 采用了倍增法的程序运行的时间复杂度是({{ select(7) }})。
  • O(logn)
  • O(n)
  • O(n²)
  • O(nlogn)
  1. 将数组{9,33,5,18,71,3,52,85}中的元素按从大到小的顺序排列, 每次可以交换任意两个元素，最少需要交换({{ select(8) }})次。
  • 4
  • 5
  • 6
  • 7
  1. 关于计算机网络， 下面的说法中哪个是正确的? ({{ select(9) }})。
  • 计算机网络是一个管理信息系统
  • 计算机网络是一个管理数据系统
  • 计算机网络是一个在协议控制下的多机互联系统
  • 计算机网络是一个独立的操作系统
  1. 下列哪款软件不是操作系统软件的名字? ({{ select(10) }})。
  • 安卓
  • Windows 11
  • 华为鸿蒙
  • ChatGPT
  1. 下述选项中哪个不是算法描述的通用方法? ({{ select(11) }})。
  • 自然语言
  • 流程图
  • 人工智能
  • 伪代码
  1. 若A=True, B=False, C=True, D=False, 以下逻辑运算表达式的运算结果为真的是({{ select(12) }})。
  • (A∧B)∨(C∧D∨¬A)
  • ((A∧B)∧C)∧¬B
  • (B∨C∨D)∨D∧A
  • (A∧(D∨¬C)∧B
  1. 一棵二叉树的高度为h，所有结点的度数都为0或2，则此树最少有({{ select(13) }})个结点。
  • 2h-1
  • 2h-1
  • 2h+1
  • h+1
  1. 从12个人中选出5个人，其中甲、乙、丙必选的方法共有({{ select(14) }})种。
  • 60
  • 36
  • 72
  • 120
  1. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的({{ select(15) }})倍。
  • 1/2
  • 2
  • 1
  • 4

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

(1)

#include<bits/stdc++. h>
using namespace std;
char change(char str)
{
      if(str >= 'a' && str <= 'z')
        str -= 32;
      return str;
}
int main()
{
      string s1, s2;
      cin >> s1 >> s2;
      int cnt = 0;
      for (int i = 0; i < s1.size(); i++)
       {
        for (int j = 0; j < s2.size(); j++)
             if (change(s1[i]) == change(s2[j]))
               cnt++;
      }
      cout << cnt;
      return 0;
}

判断题

  1. 将第1行头文件改为#include, 程序的运行结果不会改变。 ({{ select(16) }})
  • 正确
  • 错误

17.将第5行中的'a'替换为97，程序的运行结果不会改变。 ({{ select(17) }})

  • 正确
  • 错误

18.将第6行中的32替换为' '，程序的运行结果不会改变。 ({{ select(18) }})

  • 正确
  • 错误

19.将第14行代码去掉，程序的运行结果不会改变。 ({{ select(19) }})

  • 正确
  • 错误

选择题

  1. 若输入数据为 ABCDE AbCdE, 则输出为({{ select(20) }})。
  • 3
  • 5
  • 2
  • 0

21.若输入数据为 WorldYiwuAsiaShanghai ChinaHangzhouZhejiangJinhua, 则输出为({{ select(21) }})。

  • 36
  • 40
  • 42
  • 44

(2)

#include<iostream>
using namespace std;
int solve(int n, int m)
{
      int i, sum;
      if(m==1)
          return 1;
      sum=0;
       for(i=1;i<n;i++)
          sum += solve(i,m-1);
      return sum;
}
int main()
{
       int n,m;
       cin>>n>>m;
       cout<<solve(n,m)<<endl;
       return 0;
}

判断题

22.如果n输入一个负整数，程序的运行会出错。 ({{ select(22) }})

  • 正确
  • 错误

23.如果n输入一个正整数，m输入一个负整数，那么程序会进入死循环，不会输出任何结果。 ({{ select(23) }})

  • 正确
  • 错误

24.若输入4 4，则程序的运行结果为1。 ({{ select(24) }})

  • 正确
  • 错误

25.若输入 4 -1,则程序的运行结果为0。 ({{ select(25) }})

  • 正确
  • 错误

选择题

  1. 若输入为 7 4, 则输出为({{ select(26) }})。
  • 20
  • 10
  • 15
  • 5

27.若输出为10,则输入可能为({{ select(27) }})。

  • 5 3
  • 5 4
  • 6 4
  • 6 5

(3)

#include <bits/stdc++. h>
using namespace std;
const int MAXN = 2e5 + 5;
int nums[MAXN];
int left_bound(int n, int target) {
     int left = 0, right = n - 1;
     while (left <= right) {
          int mid = (left + right) / 2;
          if(nums[mid] < target)
            left = mid + 1;
          else
            right = mid - 1;
     }
     if(left < n && nums[left] == target)
          return left;
     return -1;
}
int right_bound(int n, int target) {
     int left = 0, right = n - 1;
     while (left <= right) {
          int mid = (left + right) / 2;
          if(nums[mid] <= target)
             left = mid + 1;
          else
            right = mid - 1;
     }
     if(right >= 0 && nums[right] == target)
      return right;
      return -1;
}
int main()
{
     int n, c;
     cin>>n>>c;
     for(int i = 0; i < n; ++i)
          cin>>nums[i];
     sort(nums, nums + n);
     long long ans = 0;
     for(int i = 0; i < n; ++i) {
         int left = left_bound(n, nums[i] + c);
          int right = right_bound(n, nums[i] + c);
          if(left != -1)
             ans += right - left + 1;
    }
     cout<<ans<<endl;
       return 0;
}

判断题

28.本段程序的算法用到了二分算法的思想。 ({{ select(28) }})

  • 正确
  • 错误

29.将第3行中的const去掉，程序的运行结果不变。 ({{ select(29) }})

  • 正确
  • 错误

30.将第14行中的left < n去掉, 程序的运行结果不变。 ({{ select(30) }})

  • 正确
  • 错误

31.将第38行中的long long 替换为int, 程序的运行结果不变。 ({{ select(31) }})

  • 正确
  • 错误

选择题

32.第8行的写法在某些时候会导致程序运行有问题，最好换成写法({{ select(32) }})。

  • mid = (left + right) << 1
  • mid = left + (right - left)/2
  • mid = (left + right) >> 1
  • mid = (left + right) % 2

33.本程序的时间复杂度为({{ select(33) }})。

  • O(logn)
  • O(n)
  • O(n²)
  • O(nlogn)

34.(4分) 当输入

4 1

1 1 2 3

时，程序的输出结果为({{ select(34) }})。

  • 1
  • 2
  • 3
  • 4

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

(1)给定一棵树，输出树的根root、孩子结点最多的结点 max以及它的孩子结点。

输入格式：

第1行输入n(结点数≤100)和m(边数≤200)。以下m行输入每行两个结点x和y, 表示y是x的孩子结点(x,y≤1000)。

输出格式：

第1行是树根 root。第2行是孩子结点最多的结点max。第3行是 max的孩子结点。

输入样例：

8 7
4 2
1 3
1 5
2 6
5 7
7 8

输出样例：

1
5
6 7 8

#include<iostream>
using namespace std;
int n,m, tree[105]={0};
int main()
{
    int i,x,y, root, maxroot, sum=0,j, Max=0;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        ① ;
    }
    for(i=1;i<=n;i++) //找出树的根
        if( ② )
        {
            root=i;
            ③;
        }
    for(i=1;i<=n;i++) //找孩子结点最多的结点.
    {
        sum=0;
        for(j=1;j<=n;j++)
            if(tree[j]==i)
                 sum++;
        if( ④ )
        {
            Max=sum;
            maxroot=i;
        }
    }
    cout<<root<<endl<<maxroot<<endl;
    for(i=1;i<=n;i++)
        if( ⑤)
            cout<<i<<" ";
    return 0;
}

35.①处应填({{ select(35) }})。

  • tree[y] = x
  • tree[x] = y
  • tree[y] = i
  • tree[x] = i

36.②处应填 ({{ select(36) }})。

  • tree[i] == 1
  • tree[i] == 0
  • tree[i] == 2
  • tree[i]

37.③处应填 ({{ select(37) }})。

  • break
  • continue
  • return 0
  • exit

38.④处应填({{ select(38) }})。

  • sum == Max
  • sum <= Max
  • sum > Max
  • sum < Max

39.⑤处应填({{ select(39) }})。

  • tree[i] != maxroot
  • tree[i] <= maxroot
  • tree[i] >= maxroot
  • tree[i] == maxroot

(2)快速排序是一种高效的排序算法，我们常用的 STL 函数 sort 就是采用快速排序思想实现的。

如下代码是一个经典的快速排序过程，输入一个整数n，然后输入n 个整数，程序会按照从小到大的顺序将所有整数进行排序并输出。

请将程序补充完整。

#include<bits/stdc++. h>
using namespace std;
int a[1005];
void quickSort(int a[], int begin, int end)
{
    int i,j, tmp;
    if(begin >= end)
        return;
    ① ;
    i = begin;
    j = end;
    while(i < j)
    {
        while(a[j] > tmp)
              j--;
        while( ② )
            i++;
        if(i != j)
            swap(a[i], a[j]);
    }
    ③ ;
    ④ ;
    quickSort(a,i+1, end);
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
          cin>>a[i];
    ⑤ ;
    for(int i=1;i<=n;i++)
          cout<<a[i]<<" ";
    return 0;
}

40.①处应填({{ select(40) }})。

  • tmp = a[begin]
  • tmp = a[i]
  • tmp = a[j]
  • tmp = a[end]

41.②处应填({{ select(41) }})。

  • a[i] >= tmp && i < j
  • a[i] >= tmp && i > j
  • a[i] <= tmp && i > j
  • a[i] <= tmp && i < j

42.③处应填 ({{ select(42) }})。

  • swap(a[i],a[j])
  • swap(a[begin],a[i])
  • swap(a[begin],a[j-1])
  • swap(a[begin],a[end])

43.④处应填({{ select(43) }})。

  • quickSort(a, begin,i)
  • quickSort(a, begin,i-1)
  • quickSort(a,1,i)
  • quickSort(a,1,i-1)

44.⑤处应填({{ select(44) }})。

  • quickSort(a,1,n-1)
  • quickSort(a,0,n-1)
  • quickSort(a,1,n)
  • quickSort(a,0,n)
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 蜀ICP备2022008388号-1
  3. Worker 0, 168ms
  4. Powered by Hydro v4.19.1 Community