PDF文档公众号回复关键字:20240701
2021 CSP-J 选择题
单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）
4.以比较作为基本运算，在N个数中找出最大数，最坏情况下所需要的最少比较次数为
A. N^2
B. N
C. N-1
D. N+1
6.对于有n个顶点、m条边的无向连通图(m>n),需要删掉( )条边才能使其成为一棵树
A. n-1
B. m-n
C. m-n-1
D. m-n+1
12.由 1，1，2，2，3这五个数字组成不同的三位数有( )种
A. 18
B. 15
C. 12
D. 24
13.考虑如下递归算法
solve(n)
if n<=1 return 1
else if n>=5 return n*solve(n-2)
else return n*solve(n-1)
则调用solve(7)得到的返回结果为( )
A. 105
B. 840
C. 210
D. 420
14.以a为起点，对右边的无向图进行深度优先遍历，则b、c、d、e四个点中有可能作为最后一个遍历的点的个数为( )
A. 1
B. 2
C. 3
D. 4
2 相关知识点
1) n个数取最大
3个数取最大，需比较2次
#include<bits/stdc++.h>
using namespace std;
/*
3个数取最大 比较2次
*/
int main(){
int a,b,c ;
scanf("%d%d%d",&a,&b,&c) ;
if(b > a)a = b ;
if(c > a)a = c ;
printf("%d",a) ;
return 0;
}
/*
输入 1 2 3
输出 3
输入 9 5 10
输出 10
*/
n个数取最大，需比较n-1次
#include<bits/stdc++.h>
using namespace std;
/*
n数进行比较，循环1~n-1，进行n-1次循环
*/
int n,a[10000];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<n;i++){
if(a[0]<a[i]){
a[0]=a[i];
}
}
printf("%d",a[0]);
return 0;
}
/*
输入 4 5 9 10 8
输出 10
输入 3 9 5 10
输出 10
*/
2) 树的边数
树的边数是指树中所有边的数量。在非空树中，边的数量等于结点数量减1
3) 枚举算法
枚举算法是一种通过列举所有可能情况来求解问题的策略。它通常适用于问题规模较小且解空间明确、有限的情况。枚举算法的关键在于如何有效地遍历解空间，并在遍历过程中判断每个候选解是否满足问题的要求
枚举算法一般需要按一定规则进行分类，避免重复枚举或遗漏的情况
4) 递归、递推
递归
递归是一种解决问题的方法，它通过将问题分解为更小的子问题来解决。
一个递归函数会在其定义中直接或间接地调用自身
递归通常包括两个部分：基本情况（Base case）和递归步骤（Recursive step）。
基本情况是指当问题规模变得足够小时，可以直接得到解决方案的情况。
递推
递推是一种描述序列中项与项之间关系的方法。递推关系通常用于定义具有某种规律性的数列，如斐波那契数列
递推关系可以用一个公式或方程来表示，该公式或方程描述了序列中的每一项如何由前一项（或前几项）计算得出
递归和递推区别
递归是一种解决问题的方法，通过将问题分解为更小的子问题来解决，自上而下分解，通常会出现多次重复计算问题
递推是一种描述序列中项与项之间关系的方法，自底而上计算，避免重复计算
通过斐波那契数列演示区别
递归f(3)重复计算3次，如果数更大重复更多
递推计算是从最底层计算，计算上一层时使用前面的计算结果，所以f(3)只计算1次
5) 深度优先搜索
从某个特定顶点开始，尽可能深地搜索树的分支，直到达到叶子节点，然后回溯到前一个节点，继续搜索下一个分支，实现DFS时，通常使用堆栈数据结构来实现
3 思路分析
4.以比较作为基本运算，在N个数中找出最大数，最坏情况下所需要的最少比较次数为( C )
A. N^2
B. N
C. N-1
D. N+1
分析
比较作为基本运算，用第1个数做基准数，和第2个比较，然后保留最大的，逐一和后面的数进行比较
1和2，2和3，3和4，… n-1和n
最多为n-1次
6.对于有n个顶点、m条边的无向连通图(m>n),需要删掉( D )条边才能使其成为一棵树
A. n-1
B. m-n
C. m-n-1
D. m-n+1
分析
n个节点的树，有n-1条边
无向图有m条边，需要变成n-1条边
应删掉m-(n-1)=m-n+1
所以选D
12.由 1，1，2，2，3这五个数字组成不同的三位数有( A )种
A. 18
B. 15
C. 12
D. 24
分析
分类枚举
1有1 2 3这3个不同数字组成的3位数个数有A(3,3)=3 * 2 *1=6种
2有1 1 2 这3个数字组成的3位数 112 121 211 这3种
3有1 2 2 这3个数字组成的3位数 122 212 221 这3种
4有1 1 3 这3个数字组成的3位数 112 131 311 这3种
5有2 2 3 这3个数字组成的3位数 223 232 322 这3种
上述分5类枚举，根据加法原理
6+3+3+3+3=18
13.考虑如下递归算法
solve(n)
if n<=1 return 1
else if n>=5 return n*solve(n-2)
else return n*solve(n-1)
则调用solve(7)得到的返回结果为( C )
A. 105
B. 840
C. 210
D. 420
分析
递归从大到小计算会出现一些重复计算，可以从小到大递推得到solve(7)的值
solve(1)=1
solve(2)=n * solve(n-1)=2* solve(1)=2*1=2
solve(3)=n * solve(n-1)=3* solve(2)=3*2=6
solve(4)=n * solve(n-1)=4* solve(3)=4*6=24
solve(5)=n * solve(n-2)=5* solve(3)=5*6=30
solve(6)=n * solve(n-2)=6* solve(4)=6*24=144
solve(7)=n * solve(n-2)=7* solve(5)=7*30=210
14.以a为起点，对右边的无向图进行深度优先遍历，则b、c、d、e四个点中有可能作为最后一个遍历的点的个数为( B )
A. 1
B. 2
C. 3
D. 4
分析
从a点出发沿着一个分支节点尽可能深的搜索树的分支，直到达到叶子节点，然后回溯到前一个节点，继续搜索下一个分支
1 从a出发沿bdce一个分支搜索完所有节点，最后节点为e
2 从a出发沿ce搜索到叶子节点，回溯到c沿db搜结束，最后节点为b
深度优先搜索只有上述2种情况，可能作为最后节点的为e和b这2个节点
具体如下图
