2023-09-16 CSP-J 第一轮初赛真题解析

分数：100

考试时间：120分钟

一、  单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）
1.在 C++中，下面哪个关键字用于声明一个变量，其值不能被修改？（B）(2分)
A. unsigned
B. const
C. static
D. mutable

2.八进制数12345670₈和07654321₈的和为（D）。(2分)
A. 22222221₈
B. 21111111₈
C. 22111111₈
D. 22222211₈

3.读下述代码，请问修改 data 的value 成员以存储3.14，正确的方式是(A)。(2分)

union Data{
    int num;
    float value;
    char symbol;
};
union Data data;

A. data.value = 3.14;
B. value.data = 3.14;
C. data->value = 3.14;
D. value->data = 3.14;

4.假设有一个链表的节点定义如下:

struct Node{
    int data;
    Node* next;
};

现在有一个指向链表头部的指针: Node* head，如果想要在表中插入一个新节点，其成员 data 的值为 42，并使新节点成为链表的第一个节点，下面哪个操作是正确的?(C)
A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head= newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next = head;

5.根节点的高度为 1，一棵拥有 2023 个节点的三叉树高度至少为（A）。(2分)
A.6
B.7
C.8
D.9

6.小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息，则小明一共有种选择时间段的方案。(B)(2分)
A.31
B.18
C.21
D.33

7.以下关于高精度运算的说法错误的是（C）。(2分)
A. 高精度计算主要是用来处理大整数或需要保留多位小数的运算
B. 大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。
C. 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
D. 高精度加法运算的关键在于逐位相加并处理进位。

8.后缀表达式“6 2 3 + - 3 8 2 / + * 2 ^ 3 +”对应的中表达式是(A)。(2分)
A. ((6 - (2 + 3))*(3 + 8 / 2)) ^ 2 
B.6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3
C.(6 - (2 + 3 )) * ((3 + 8 / 2) ^ 2) + 3
D.6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3

9.数101010₂和166₈的和为（D）。(2分)
A.10110000₂
B.236₈
C.158₁₀
D.A0₁₆

10.假设有一组字符{a, b, c, d, e, f}，对应的频率分别为5%， 9%， 12%， 13%，16%，45%。请问以下哪个选项是字符a, b, c, d, e, f分别对应的一组哈夫曼编码？（A）(2分)
A. 1111, 1110, 101, 100, 110, 0
B. 1011, 1001, 1000, 011, 010, 100
C. 000, 001, 010, 011, 10, 11
D. 1010, 1011, 110, 111, 00, 01

11.给定一颗二叉树，其前序遍历结果为：ABCDEFG，中序遍历结果为：DEBACFG。请问这棵树的正确遍历结果是什么？（A）(2分)
A. EDBFGCA
B. EDBGCFA
C. DEBGFCA
D. DBEGFCA

12.考虑一个有向无环图，该图包含4条有向边：（1, 2）,（1, 3）,（2, 4）和（3, 4）以下哪个选项是这个有向无环图的一个有效的拓扑排序？（B）(2分)

A. 4, 2, 3, 1
B. 1, 2, 3, 4
C. 1, 2, 4, 3
D. 2, 1, 3, 4

13.在计算机中，以下哪个选项描述的数据存储容量最小？（B）(2分)
A. 字节（byte）
B. 比特（bit）
C. 字（word）
D. 千字节（kilobyte）

14.一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能得组合？（A）(2分)
A. 1420
B. 1770
C. 1540
D. 2200

15.以下哪个不是操作系统？（D）(2分)
A. Linux
B. Windows
C. Android
D. HTML

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

#include
#include
using namespace std;
 
double f(double a,double b,double c){
    double s=(a+b+c)/2;
    return sqrt(s*(s-a)*(s-b)*(s-c));
}
 
int main(){
    cout.flags(ios::fixed);
    cout.precision(4);
    
    int a,b,c;
    cin>>a>>b>>c;
    cout<<f(a,b,c)<
    return 0;
}

假设输入的所有数都为不超过1000的正整数，完成下面的判断题和单选题：

·判断题

16. 当输入为“2 2 2”时，输出为“1.7321”（对 ）（2分）
17. 将第7行中的"（s-b）*（s-c）"改为"（s-c）*（s-b）"不会影响程序运行的结果（ 对）（2分）
18. 程序总是输出四位小数（对 ）（2分）
·单选题
19. 当输入为“3 4 5”时，输出为（ A）(3分)
A. "6.0000" 
B. "12.0000" 
C. "24.0000" 
D. "30.0000"

20. 当输入为“5 12 13”时，输出为（ B）(3分)
A. "24.0000"
B. "30.0000"
C. "60.0000"
D. "120.0000"

#include
#include
#include
using namespace std;
 
int f(string x,string y){
    int m=x.size();
    int n=y.size();
    vectorint>>v(m+1,vector<int>(n+1,0));
   for(int i=1;i<=m;i++){
       for(int j=1;j<=n;j++){
            if(x[i-1]==y[j-1]){
                v[i][j]=v[i-1][j-1]+1;
            }else{
                v[i][j]=max(v[i-1][j],v[i][j-1]);
            }
        }
    }
    return v[m][n];
}
 
bool g(string x,string y){
    if(x.size() != y.size()){
        return false;
    }
    return f(x+x,y)==y.size();
}
 
int main(){
    string x,y;
    cin>>x>>y;
    cout<<g(x,y)<
    return 0;
}

·判断题
21. f函数的返回值小于等于min（n,m）。（对 ）(1.5分)
22. f函数的返回值等于两个输入字符串的最长公共子串的长度。（ 错）(1.5分)
23. 当输入两个完全相同的字符串时，g函数的返回值总是true（ 对）(1.5分)
·单选题
24. 将第19行中的“v[m][n]”替换为“v[n][m]”，那么该程序（B ）(3分)
A. 行为不变
B. 只会改变输出
C. 一定非正常退出
D. 可能非正常退出
25. 当输入为“csppsc spsccp”时，输出为：（B ）(3分)
A. "0"
B. "1"
C. "T"
D. "F"
26. 当输入为 “csppsc spsccp”时，输出为（D）。(3分)
A. "T"
B. "F"
C. "0"
D. "1"

#include 
#include 
using namespace std;
 
int solve1(int n){
    return n*n;
}
 
int solve2(int n){
   int sum=0;
   for(int i=1;i<=sqrt(n);i++){
        if(n%i==0){
            if(n/i==i){
                sum+=i*i;
            }else{
                sum+=i*i+(n/i)*(n/i);
            }
        }
    }
    return sum;
}
 
int main(){
    int n;
    cin>>n;
    cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<
    return 0;
}

假设输入的n是绝对值不超过1000的整数，完成下面的判断题和单选题。

·判断题
27. 如果输入的n为正整数，solve2函数的作用是计算n所有的因子的平方和（对 ）(1.5分)
28. 第13~14行的作用是避免n的平方根因子i（或n/i）进入第16行而被计算两次（对 ）(1.5分)
29. 如果输入的n为质数，solve2（n）的返回值为n2+1（对 ）(1.5分)
·单选题
30. 如果输入的n为质数p的平方，那么solve2（n）的返回值为（ B）  （4分）
A. p2+p+1 
B. n2+n+1 
C. n2+1 
D. p4+2p2+1
31.  当输入为正整数时，第一项减去第二项的差值一定（ D）（3分）
A.  大于0 B. 大于等于0且不一定大于0 C. 小于0 D. 小于等于0且不一定小于0
32.  当输入为“5”时，输出为（C ）（3分）
A. "651.625" 
B. "650.729" 
C. "651.676" 
D. "652.625"

三、完善程序(单选题，每小题3分，共计 3 分)
(1)(寻找被移除的元素)问题:原有长度为 n+1公差为1等升数列，将数列输到程序的数组时移除了一个元素，导致长度为 n 的开序数组可能不再连续，除非被移除的是第一个或最后之个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

#include 
#include 
 
using namespace std;
 
int find missing(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right){
          int mid = left + (right  left) / 2;
         if (nums[mid] - mid+ ①) {
               ②;
           }else{
             ③
           }
      }
     return ④;
}
 
int main(){
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i= 0; i< n; i++) cin >> nums[i];
    int missing_number = find_missing(nums);
    if_(missing_number == ⑤) {
        cout << "Sequence is consecutive" << endl;
    }else{
           cout << "Missing number is " << ,missing numbeer << endl;
    }
    return 0;
}

 
33. ①处应填（ B）(3分)
A. 1 
B. nums[0] 
C. right 
D. left

34. ②处应填（A ）(3分)
A. left=mid+1 
B. right=mid-1 
C. right=mid 
D. left=mid

35. ③处应填（C ）(3分)
A.left=mid+1 
B.right=mid-1 
C.right=mid 
D.left=mid

36. ④处应填（A ）(3分)
A.left+nums[0] 
B.right+nums[0] 
C.mid+nums[0] 
D.right+1

37. ⑤处应填（ D）(3分)
A.nums[0]+n 
B.nums[0]+n-1 
C.nums[0]+n+1 
D.nums[n-1]

(2) (编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#include 
#include 
#include 
using namespace std;
 
int min(int x,int y,int z){
    return min(min(x,y),z);
}
 
int edit_dist_dp(string str1,string str2){
int m=str1.length();
int n=str2.length();
vectorint>> dp(m+1,vector<int>(n+1));
 
for(int i=0;i<=m;i++){
    for(int j=0;j<=n;j++){
        if(i==0)
            dp[i][j]=(1);
        else if(j==0)
            dp[i][j]=(2);
        else if((3))
            dp[i][j]=(4);
        else
            dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],(5)); 
    }
}
return dp[m][n];
 
int main(){
    string str1,str2;
    cin>>str1>>str2;
    cout<<"Mininum number of operation:"<<edit_dist_dp(str1,str2)<
    return 0; 
}

38. ①处应填（ A）(3分)
A. j 
B. i 
C. m 
D. n

39. ②处应填（B ）(3分)
A. j 
B. i 
C. m 
D. n
 
40. ③处应填（A ）(3分)
A. str1[i-1]==str2[j-1] 
B. str1[i]==str2[j] 
C. str1[i-1]!=str2[j-1] 
D. str1[i]!=str2[j]

41. ④处应填（B ）(3分)
A. dp[i-1][j-1]+1 
B. dp[i-1][j-1]
C. dp[i-1][j] 
D. dp[i][j-1]

42. ⑤处应填（ C）(3分)
A. dp[i][j] + 1 
B. dp[i-1][j-1]+1
C. dp[i-1][j-1] 
D. dp[i][j]