一、单项选择题(每题 2 分,共 30 分)

1. 正整数 $2024$ 与 $1840$ 的最大公约数是( )。

{{ select(1) }}

• $46$
• $92$
• $44$
• $184$

2. 十进制数 $28$ 与二进制数 $10000001110000$ 求和的结果是( )。

{{ select(2) }}

• 十进制数 $8332$
• 十六进制数 $208A$
• 二进制数 $1 0 0 0 0 0 0 0 0 1 1 0$
• 八进制数 $20212$

3. C++ 程序中, (25|6)\^5 的值是( )。

{{ select(3) }}

• $25$
• $26$
• $27$
• $28$

4. 在数组 A[x] 中,若存在(i < j)且(A[i] > A[j]),则称(A[i] ,A[j])为数组 A[x] 的一个逆序对。对于序列 ($7,4,1,9,3,6,8,5$),在不改变顺序的情况下,去掉 ( )会使逆序对的个数减少 $4$ 。

{{ select(4) }}

• $1$
• $3$
• $6$
• $5$

5. 如果字符串 $s$ 在字符串 A 中出现了,则字符串 $s$ 被称作字符串 A 的子串。设字符串 A = "players" , A 的非空子串的数目是( )。

{{ select(5) }}

• $27$
• $29$
• $28$
• $30$

6. 以下哪种算法的主要框架不是非比较排序?( )

{{ select(6) }}

• 计数排序
• 堆排序
• 基数排序
• 桶排序

7. 采用了倍增法的程序运行的时间复杂度是( )。

{{ select(7) }}

• $O(logn)$
• $O(n)$
• $O(n^2)$
• $O(n \log n)$

8. 将数组 {$9,33,5,18,71,3,52,85$ }中的元素按从大到小的顺序排列,每次可以交换任意两个元素,最少需要交换( )次。

{{ select(8) }}

• $4$
• $5$
• $6$
• $7$

9. 关于计算机网络,下面的说法中哪个是正确的?( )

{{ select(9) }}

• 计算机网络是一个管理信息系统
• 计算机网络是一个管理数据系统
• 计算机网络是一个在协议控制下的多机互联系统
• 计算机网络是一个独立的操作系统

10. 下列哪款软件不是操作系统软件的名字?( )

{{ select(10) }}

• 安卓
• Windows $11$
• 华为鸿蒙
• ChatGPT

11. 下述选项中哪个不是算法描述的通用方法?( )

{{ select(11) }}

• 自然语言
• 流程图
• 人工智能
• 伪代码

12. 若 A=True,B=False,C=True,D=False,以下逻辑运算表达式的运算结果为真的是 ( )。

{{ select(12) }}

• $(A \land B) \vee (C \land D \vee \neg A)$
• $((A \land B) \land C) \land \neg B$
• $(B \vee C \vee D) \vee D \land A$
• $(A \land (D \vee \neg C)) \land B$

13. 一棵二叉树的高度为 $h$ ,所有结点的度数都为 $0$ 或 $2$ ,则此树最少有( )个结点。

{{ select(13) }}

• $2^{h}-1$
• $2h-1$
• $2h+1$
• $h+1$

14. 从 $12$ 个人中选出 $5$ 个人,其中甲、乙、丙必选的方法共有( )种。

{{ select(14) }}

• $60$
• $36$
• $72$
• $120$

15. 在一个有向图中,所有顶点的人度之和等于所有顶点的出度之和的( )倍。

{{ select(15) }}

• $1/2$
• $2$
• $1$
• $4$

二、阅读程序

阅读程序(一)

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

#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<iostream> ,程序的运行结果不会改变。 ( )

{{ select(16) }}

• 正确
• 错误

(2) 将第 $5$ 行中的 'a' 替换为 $97$ ,程序的运行结果不会改变。 ( )

{{ select(17) }}

• 正确
• 错误

(3) 将第 $6$ 行中的 $32$ 替换为 ' ' ,程序的运行结果不会改变。 ( )

{{ select(18) }}

• 正确
• 错误

(4) 将第 $18$ 行代码去掉,程序的运行结果不会改变。 ( )

{{ select(19) }}

• 正确
• 错误

(5) 若输入数据为 ABCDE AbCdE,则输出为( )。

{{ select(20) }}

• $3$
• $5$
• $2$
• $0$

(6) 若输人数据为 WorldYiwuAsiaShanghai ChinaHangzhouZhejiangJinhua,则输出为( )。

{{ select(21) }}

• $36$
• $40$
• $42$
• $44$

阅读程序(二)

01 #include<iostream>
02 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;
}

(1) 如果 $n$ 输入一个负整数,程序的运行会出错。 ( )

{{ select(22) }}

• 正确
• 错误

(2) 如果 $n$ 输入一个正整数,$m$ 输入一个负整数,那么程序会进入死循环,不会输出任何结果。 ( )

{{ select(23) }}

• 正确
• 错误

(3) 若输入 $44$ ,则程序的运行结果为 $1$ 。 ( )

{{ select(24) }}

• 正确
• 错误

(4) 若输入 $4-1$ ,则程序的运行结果为 $0$ 。 ( )

{{ select(25) }}

• 正确
• 错误

(5) 若输入为 $74$ ,则输出为( )。

{{ select(26) }}

• $20$
• $10$
• $15$
• $5$

(6) 若输出为 $10$ ,则输入可能为( )。

{{ select(27) }}

• $53$
• $54$
• $64$
• $65$

阅读程序(三)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int MAXN = 2e5 + 5;
04 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;
}

(1) 本段程序的算法用到了二分算法的思想。 ( )

{{ select(28) }}

• 正确
• 错误

(2) 将第 $3$ 行中的 const 去掉,程序的运行结果不变。 ( )

{{ select(29) }}

• 正确
• 错误

(3) 将第 $14$ 行中的 left < n 去掉,程序的运行结果不变。 ( )

{{ select(30) }}

• 正确
• 错误

(4) 将第 $38$ 行中的 long long 替换为 int,程序的运行结果不变。 ( )

{{ select(31) }}

• 正确
• 错误

(5) 第 $8$ 行的写法在某些时候会导致程序运行有问题,最好换成写法( )。

{{ select(32) }}

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

(6) 本程序的时间复杂度为( )。

{{ select(33) }}

• $O(logn)$
• $O(n)$
• $O(n^2)$
• $O(n \log n)$

(7) 当输入

41
1123

时,程序的输出结果为( )。

{{ select(34) }}

• $1$
• $2$
• $3$
• $4$

三、完善程序

三、完善程序

单项选择题,每题 $3$ 分,共 $30$ 分。

完善程序(一)

给定一棵树,输出树的根 root、孩子结点最多的结点 $max$ 以及它的孩子结点。输入格式: 第 $1$ 行输入 n (结点数 $≤100$ ) 和 m(边数 $≤200$ ) 。以下 $m$ 行输入每行两个结点 $x$ 和 $y$ ,表示 $y$ 是 $x$ 的孩子结点( $x,y≤1000$ )。 输出格式: 第 $1$ 行是树根 $root$ 。第 $2$ 行是孩子结点最多的结点 $max$。第 $3$ 行是 $max$ 的孩子结点。

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

4
2
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;
}

(1) ① 处应填( )

{{ select(35) }}

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

(2) ② 处应填( )

{{ select(36) }}

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

(3) ③ 处应填( )

{{ select(37) }}

• break
• continue
• return 0
• exit

(4) ④ 处应填( )

{{ select(38) }}

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

(5) ⑤ 处应填( )

{{ select(39) }}

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

完善程序(二)

快速排序是一种高效的排序算法,我们常用的 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;
}

(1) ① 处应填( )

{{ select(40) }}

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

(2) ② 处应填( )

{{ select(41) }}

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

(3) ③ 处应填( )

{{ select(42) }}

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

(4) ④ 处应填( )

{{ select(43) }}

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

(5) ⑤ 处应填( )

{{ select(44) }}

• quickSort(a,1,n-1)
• quickSort(a,0,n-1)
• quickSort(a,1,n)
• quickSort(a,0,n)