灵神常见算法

In Process

一、  单项选择题

1、在C++中，下面哪个关键字用于声明一个变量，其值不能被修改？（ ）。

A. unsigned

B. const

C. static

D. mutable

答案: B。在C++中，关键字`const`用于声明一个变量，表示其值是常量，不能被修改。一旦用`const`声明一个变量后，它的值在声明之后就不能再被修改，任何试图修改该变量的操作都会被编译器报错。

其中 A 选项为无符号性 B 为定义常亮 (不可修改)C 为静态变量 D 为可修改变量和 const

2.  八进制数12345670(8) 和07654321(8)的和为（ ）。

A.  22222221(8)

B.  21111111(8)

C.  22111111(8)

D.  22222211(8)

答案: D

直接算。笨方法是首先将八进制数转换为十进制数，然后将两个十进制数相加，最后将结果转换回八进制数。

3.  阅读下述代码，请问修改data的value成员以存储3.14，正确的方式是（ ）。

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;

答案: A。Union 为联合体，和 struct 类似，赋值应用.运算符，指针才能用->运算符

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

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

现在有一个指向链表头部的指针：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;

答案: A

B 选项对 head 的 data 进行修改。

C、D 选项没有更新 head 的值，导致没法插入新的数据。

5.  根节点的高度为1，一根拥有2023个节点的三叉树高度至少为（ ）。

A.  6

B.  7

C.  8

D.  9

答案: C

满三叉树的节点数为$s=(3^n-1) \div 2$，2023 个节点介于 7 层到 8 层之间，所以最少需要 8 层二叉树，所以至少八层。

6.  小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息，则小明一共有（ ）种选择时间段的方案。

A.  31

B.  18

C.  21

D.  33

答案: B。7个空闲时间1、2、3、4、5、6、7。

只选一个练习时间段：随便一个都行，有 7 种。

选 2 个练习时间段：

1. 选1，能选4、5、6、7，有4种

2. 选2，能选5、6、7，有3种（往前选1，会重复）

3. 选3，能选6、7，有2种

4. 选4，能选7，有1种

• 共有 10 种。

  选 3 个联系时间段：只能选1、4、7，有 1 种。

  。故总数为 18 种

7.  以下关于高精度运算的说法错误的是（ ）。

A.  高精度计算主要是用来处理大整数或需要保留多位小数的运算。

B.  大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。

C.  高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。

D.  高精度加法运算的关键在于逐位相加并处理进位。 

答案: C。高精度乘法的运算时间与两个整数的位数的乘积有关，而不仅仅是较长者的位数。位数的增加会导致乘法的复杂度呈指数级增长，需要更多的计算步骤和时间。

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

答案: A。根据后缀表达式到中缀表达式的转换规则，我们可以逆序遍历后缀表达式并使用栈来构建中缀表达式。遇到数字时，直接将其入栈；遇到运算符时，从栈中弹出相应数量的操作数，并按照运算在·符和操作数之间的优先级进行括号添加，然后将结果再次入栈。

对于给定的后缀表达式6 2 3 + - 3 8 2 / + * 2 ^ 3 +，我们可以通过上述方法得到中缀表达式为：((6-(2+3))*(3+(8/2)))^2+3

因此，选项 A. ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3 是正确的答案。

9.  数101010(2)和166(8)的和为（ ）。

A.  10110000(2)

B.  236(8)

C.  158(10)

D.  A0(16)

答案: D

将二进制数101010(2)转换为十进制得到42，将八进制数166(8)转换为十进制得到118。

将十进制数42和118相加得到160。

现在我们将160转换为十六进制，得到A0(16)。

因此，正确答案是选项 D. A0(16)。

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

答案: A

根据哈夫曼编码的生成过程，我们可以按照如下步骤得到字符a,b,c,d,e,f分别对应的哈夫曼编码：

1. 将所有字符按照出现频率从小到大排序，得到字符序列{a,b,c,d,e,f}。
2. 取出频率最小的两个字符a和b，构建一棵二叉树，并将其根节点的频率设置为a和b的频率之和（即5%+9%=14%）。
3. 将原序列中的a和b删除，并将新生成的节点插入到序列中，得到新的字符序列{c,d,e,f,ab}。
4. 重复步骤2和3，直到得到一棵包含所有字符的二叉树。
5. 对于每条从根节点到叶子节点的路径，用0表示向左走，用1表示向右走，得到对应字符的哈夫曼编码。

按照上述算法，我们可以得到如下结果：

字符	频率	哈夫曼编码
a	5%	1111
b	9%	1110
c	12%	101
d	13%	100
e	16%	110
f	45%	0

因此，正确答案是选项 A. 1111，1110，101，100，110，0。

11.  给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么？（ ）

A.  EDBFGCA

B.  EDBGCFA

C.  DEBGFCA

D.  DBEGFCA

答案: A

根据前序遍历结果和中序遍历结果重构二叉树的步骤如下：

1. 前序遍历结果的第一个字符为根节点，即A。
2. 在中序遍历结果中找到根节点A，将其左边的字符为左子树的中序遍历结果，右边的字符为右子树的中序遍历结果。根据此规则，我们可以得到左子树的中序遍历结果为DEB，右子树的中序遍历结果为CFG。

1. 根据左子树的中序遍历结果DEB和左子树的前序遍历结果ABD，递归重构左子树。结果如下：

    A  
   / \  
  B   F  
 / \  
D   E  

2. 根据右子树的中序遍历结果CFG和右子树的前序遍历结果CFG，递归重构右子树。结果如下：

  G  
 / \  
C   G

3. 将左子树和右子树连接到根节点上，得到整棵树的结构：

  A  
 / \  
B   F  
   / \  
  D   E  
     / \  
    C   G

根据后序遍历的性质，在后序遍历中，左子树先于右子树被访问，根节点最后被访问。因此，这棵树的正确后序遍历结果是EDBFGCA。

因此，正确答案是选项 A. EDBFGCA。

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

答案: B。拓扑排序是有向无环图中对顶点进行排序的一种方法，使得所有的有向边从排在前面的顶点指向排在后面的顶点。根据提供的有向边 (1,2)，(1,3)，(2,4)，和(3,4)，我们可以确定拓扑排序的正确选项。

根据题目给出的有向边，可以得出以下关系：

• 1 -> 2
• 1 -> 3
• 2 -> 4
• 3 -> 4

根据拓扑排序的定义，我们需要先排列没有前置依赖的顶点。根据上述关系，只有顶点 1 没有前置依赖，所以它必须是拓扑排序的第一个顶点。

接下来，根据关系 (1,2) 和 (1,3)，顶点 2 和 3 是直接依赖于顶点 1 的，它们应该在 1 后面。

最后，根据关系 (2,4) 和 (3,4)，顶点 4 是直接依赖于顶点 2 和 3 的，所以它们也应该在 2 和 3 后面。

综上所述，有效的拓扑排序应该是 B. 1，2，3，4。

13.  在计算机中，以下哪个选项描述的数据存储容量最小？（ ）

A.  字节（byte）

B.  比特（bit）

C.  字（word）

D.  千字节（kilobyte）

答案: B在计算机中，以下选项描述的数据存储容量最小是B. 比特（bit）。

比特（bit）是计算机中最基本的单位，用来表示二进制数据的单个位，可以取0或1两个值。比特是计算机中最小的存储单位。

字节（byte）是计算机中常用的数据存储单位，它由8个比特组成，可以用来表示一个字符或8个二进制位。字节是相对于比特来说更常用的单位。

字（word）通常指计算机中一个机器字的大小，表示计算机一次能够处理的二进制位数，其大小由机器的架构决定。

千字节（kilobyte）是计算机中常用的数据存储容量单位，等于1024字节，用来表示较小的数据量。

因此，在计算机中，比特是描述数据存储容量最小的单位。

14.  一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？（ ）

A.  1420

B.  1770

C.  1540

D.  2200

答案: A。要选出一个3人的小组，并且小组中必须至少包含1个女生。

情况一：选取1个女生和2个男生。

选择女生的方式有 12 种，选择男生的方式有 $C_{10}^2 = 45$ 种。总共的组合方式为 12 * 45 = 540 种。

情况二：选取2个女生和1个男生。 选择女生的方式有 $C_{12}^2 = 66$ 种，选择男生的方式有 10 种。总共的组合方式为 66 * 10 = 660 种。

情况三：选取3个女生。 选择女生的方式有 $C_{12}^3 = 220$ 种。总共的组合方式为 220 种。

综上所述，总共的可能的组合方式为 540 + 660 + 220 = 1420 种。

15.  以下哪个不是操作系统？（ ）

A.  Linux

B.  Windows

C.  Android

D.  HTML

答案: D

HTML（超文本标记语言）是一种用于创建网页的标记语言，它并不是操作系统。HTML主要用于描述网页的结构和内容，而不是提供操作系统所需的核心功能，如管理资源、调度任务和控制硬件等。

Linux、Windows和Android都是常见的操作系统。Linux是一种开源的操作系统，被广泛应用于服务器和嵌入式设备等领域。Windows是由微软公司开发的操作系统，用于个人电脑和服务器等。Android是由谷歌开发的移动设备操作系统，用于智能手机、平板电脑等移动设备。

---

二、阅读程序

2.1

#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;
}

题目解析：本题是求三角形面积的海伦公式，即给出三角形的三边长a，b，c，利用第7行给出的公式，即可方便地求出三角形的面积。

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

判断题

1、（2分）当输入为 2 2 2 时，输出为1.7321（ 对 ）

$\sqrt3 = 1.732050807568877$，四舍五入就是1.7321。

2、（2分）将第7行中的 (s-b)*(s-c) 改为 (s-c)*(s-b) 不会影响程序运行的结果（ 对 ）

3、（2分）程序总是输出四位小数（ 错 ）

如果a、b、c不能构成三角形，根号下可能为负数，不能正常运行。

单选题

4、当输入为 3 4 5 时，输出为（ ）

A.6.0000

B. 12.0000

C. 24.0000

D. 30.0000

选A。$6 \times 3 \times 2 \times 1 = 36，\sqrt{36} = 6$。

5、当输入为 5 12 13 时，输出为（ ）

A. 24.0000

B. 30.0000

C. 60.0000

D.120.0000

选B。

2.2

#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;
}

本题的f函数为【最长公共子序列】问题的模板程序。即可以求出两个字符串共同含有的子串里，最长的子串的长度。注意子串不一定取连续的字母，但是顺序必须和原始顺序保持一致。

判断题

1、f 函数的返回值小于等于 min{n,m}。（ 对 ）

2、f 函数的返回值等于两个输入字符串的最长公共子串的长度。（ 错 ）

3、当输入两个完全相同的字符串时，g 函数的返回值总是 true。（ 对 ）

单选题

4、将第19行中的 v[m][n] 替换为 v[n][m]，那么该程序（）。

A. 行为不变

B. 只会改变输出

C. 一定非正常退出

D. 可能非正常退出

5、当输入为 csp-j p-jcs 时，输出为（）。

A. 0

B. 1

C. T

D. F

6、当输入为 csppsc spsccp 时，输出为（）。
A. T

B. F

C. 0

D. 1

---

参考

• (CSP-J1) 入门级 C++语言试题 (qq.com)

• 1041 - CSP 2023 入门级第一轮 - 洛谷有题 (luogu.com.cn)

• 【零一原创】2023 CSP-J组第一轮初赛真题答案及全面解析 - 知乎 (zhihu.com)

• 求三叉树高度 - 23lalala - 博客园 (cnblogs.com)