2023CCF非专业级别软件能力认证第一轮CSP-J初赛试题

2023 CCF⾮专业级别软件能⼒认证第⼀轮 （CSP - J1）⼊⻔级C++语⾔试题 认证时间：2023年9⽉16⽇09:30～11:30 ⼀、 单项选择题（共15题，每题2分，共计30分：每题有且仅有⼀个正确选项） 1. 在C++中，下⾯哪个关键字⽤于声明⼀个变量，其值不能被修改？（ ）。 A. unsigned B. const C. static D. mutable 2. ⼋进制数123456708 和076543218的和为（ ）。 A. 222222218 B. 211111118 C. 221111118 D. 222222118 3. 阅读下述代码，请问修改data的value成员以存储3.14，正确的⽅式是（ ）。 A. data.value = 3.14; B. value.data = 3.14; C. data->value = 3.14; D. value->data = 3.14; 4. 假设有⼀个链表的节点定义如下： union Data{  int num;      float value;      char symbol; }; union Data data; 1 2 3 4 5 6 struct Node {  int data;  Node* next; }; 1 2 3 4 现在有⼀个指向链表头部的指针：Node* head。如果想要在链表中插⼊⼀个新节点，其成员data的值为42，并使 新节点成为链表的第⼀个节点，下⾯哪个操作是正确的？（ ） 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. 6 B. 7 C. 8 D. 9 6. ⼩明在某⼀天中依次有七个空闲时间段，他想要选出⾄少⼀个空闲时间段来练习唱歌，但他希望任意两个练习 的时间段之间都有⾄少两个空闲的时间段让他休息，则⼩明⼀共有（ ）种选择时间段的⽅案。 A. 31 B. 18 C. 21 D. 33 7. 以下关于⾼精度运算的说法错误的是（ ）。 A. ⾼精度计算主要是⽤来处理⼤整数或需要保留多位⼩数的运算。 B. ⼤整数除以⼩整数的处理的步骤可以是，将被除数和除数对⻬，从左到右逐位尝试将除数乘以某个数，通过减 法得到新的被除数，并累加商。 C. ⾼精度乘法的运算时间只与参与运算的两个整数中⻓度较⻓者的位数有关。 D. ⾼精度加法运算的关键在于逐位相加并处理进位。 8. 后缀表达式“6 2 3 + - 3 8 2 / + * 2 ^ 3 +”对应的中缀表达式是（ ） A. ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3 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. 数1010102和1668的和为（ ）。 A. 101100002 B. 2368 C. 15810 D. A016 10. 假设有⼀组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字 符a,b,c,d,e,f分别对应的⼀组哈夫曼编码？（ ） A. 1111，1110，101，100，110，0 B. 1010，1001，1000，011，010，00 C. 000，001，010，011，10，11 D. 1010，1011，110，111，00，01 11. 给定⼀棵⼆叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历 结果是什么？（ ） A. EDBFGCA B. EDBGCFA C. DEBGFCA D. DBEGFCA 12. 考虑⼀个有向⽆环图，该图包括4条有向边：(1,2)，(1,3)，(2,4)，和(3,4)。以下哪个选项是这个有向⽆环图的 ⼀个有效的拓扑排序？（ ） A. 4，2，3，1 B. 1，2，3，4 C. 1，2，4，3 D. 2，1，3，4 13. 在计算机中，以下哪个选项描述的数据存储容量 ⼩？（ ） A. 字节（byte） B. ⽐特（bit） C. 字（word） D. 千字节（kilobyte） 14. ⼀个班级有10个男⽣和12个⼥⽣。如果要选出⼀个3⼈的⼩组，并且⼩组中必须⾄少包含1个⼥⽣，那么有多 少种可能的组合？（ ） A. 1420 B. 1770 C. 1540 D. 2200 15. 以下哪个不是操作系统？（ ） A. Linux B. Windows C. Android D. HTML   ⼆、 阅读程序（程序输⼊不超过数组成字符串定义的范围：判断题正确填√，错误填×；除特殊说明外，判断题1.5 分，选择题3分，共计40分） (1）   假设输⼊的所有数都为不超过1000的正整数，完成下⾯的判断题和单选题： 判断题: 16. （2分）当输⼊为“2 2 2”时，输出为“1.7321”（ ）   17. （2分）将第7⾏中的"（s-b）（s-c）"改为"（s-c）（s-b）"不会影响程序运⾏的结果（ ）   18. （2分）程序总是输出四位⼩数（ ） 单选题 19. 当输⼊为“3 4 5”时，输出为（ ） A. "6.0000" B. "12.0000" C. "24.0000" D. "30.0000" 20. 当输⼊为“5 12 13”时，输出为（ ） （2） #include <iostream> #include <cmath> 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) << endl;    return 0; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 判断题 21. f函数的返回值⼩于等于min（n,m）。（ ） 22. f函数的返回值等于两个输⼊字符串的 ⻓公共⼦串的⻓度。（ ） 23. 当输⼊两个完全相同的字符串时，g函数的返回值总是true（ ） 单选题 24. 将第19⾏中的“v[m][n]”替换为“v[n][m]”，那么该程序（ ） 25. 当输⼊为“csppsc spsccp”时，输出为：（ ） （3） #include <iostream> #include <vector> #include <algorithm> using namespace std; int f(string x, string y) {    int m = x.size();    int n = y.size();    vector<vector<int>> 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) << endl;    return 0; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include <iostream>1   假设输⼊的n是绝对值不超过1000的整数，完成下⾯的判断题和单选题。 判断题 27. 如果输⼊的n为正整数，solve2函数的作⽤是计算n所有的因⼦的平⽅和（ ） 28. 第13~14⾏的作⽤是避免n的平⽅根因⼦i（或n/i）进⼊第16⾏⽽被计算两次（ ） 29. 如果输⼊的n为质数，solve2（n）的返回值为n2+1（ ） 单选题 30. （4分）如果输⼊的n为质数p的平⽅，那么solve2（n）的返回值为（ ） A. p2+p+1 B. n2+n+1 C. n2+1 D. p4+2p2+1 31. 当输⼊为正整数时，第⼀项减去第⼆项的差值⼀定（ ） A. ⼤于0 B. ⼤于等于0且不⼀定⼤于0 C. ⼩于0 D. ⼩于等于0且不⼀定⼩于0 32. 当输⼊为“5”时，输出为（ ） A. "651.625" B. "650.729" C. "651.676" D. "652.625"   #include <cmath> 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))) << endl;    return 0; } 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 三、完善程序(单选题，每⼩题3分，共计 3 分) (1)(寻找被移除的元素)问题:原有⻓度为 n+1公差为1等升数列，将数列输到程序的数组时移除了⼀个元素，导致⻓ 度为 n 的开序数组可能不再连续，除⾮被移除的是第⼀个或 后之个元素。需要在数组不连续时，找出被移除的元 素。试补全程序。 33. ①处应填（ ） A. 1 B.nums[0] C.right D.left 34. ②处应填（ ） A. left=mid+1 B.right=mid-1 C.right=mid D.left=mid 35. ③处应填（ ） A.left=mid+1 B.right=mid-1 C.right=mid D.left=mid 36. ④处应填（ ） #include<iostream> #include <vector> 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_number << endl;   }    return 0; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 A.left+nums[0] B.right+nums[0] C.mid+nums[0] D.right+1 37. ⑤处应填（ ） A.nums[0]+n B.nums[0]+n-1 C.nums[0]+n+1 D.nums[n-1] (2) （编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插⼊（Insert）、替换（Replace），⼀个 字符，求将第⼀个字符串转换为第⼆个字符串所需要的 少操作次数。 38. ①处应填（ ） A.j B.i C.m D.n 39. ②处应填（ ） A.j B.i C.m D.n #include <iostream> #include <string> #include <vector> 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();    vector<vector<int>> 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) << endl;    return 0; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 40. ③处应填（ ） 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. ④处应填（ ） A. dp[i-1][j-1]+1 B. dp[i-1][j-1] C. dp[i-1][j] D. dp[i][j-1] 42. ⑤处应填（ ） A. dp[i][j] + 1 B. dp[i-1][j-1]+1 C. dp[i-1][j-1] D. dp[i][j]