第四套中小学信息学奥赛CSP-J考前冲刺题
二、阅读程序题
(程序输入不超过数组或字符串定义的范围，判断题正确填√错误填X;除特殊说明外，判断题 1.5分，选择题3分，共计40分)
第一题 归并排序
1 #include <iostream>
2 using namespace std;
3 const int Maxn=10005;
4 int n,b[Maxn];
5 inline void mergesort(int*a,int l,int r){
6 if(l==r)return;
7 int mid=l+r>>1;
8 mergesort(a,l,mid),mergesort(a,mid+1,r);
9 int i=l,j=mid+1,cnt=0;
10 while(i<=mid && j<=r){
11 if (a[i]<=a[j])b[++cnt]=a[i++];
12 else b[++cnt]=a[j++];
13 }
14 while(i<=mid)b[++cnt]=a[i++];
15 while(j<=r)b[++cnt]=a[j++];
16 for(i=l;i<=r;i++)a[i]=b[i-l+1];
17 }
18 int a[Maxn];
19 int main(void){
20 cin>>n;
21 for (int i=1;i<=n;i++)cin>>a[i];
22 mergesort(a,1,n);
23 for (int i=1;i<=n;i++)cout<<a[i]<<(i==n ?'\n':' ');
24 return 0;
25 }程序分析
主要考查小朋友们读写程序能力和逻辑思维能力，此程序实现了归并排序算法，用于对输入的n个数进行排序。具体实现过程如下：
- 定义了一个全局常量Maxn，表示数组的最大长度。同时定义了一个辅助数组b，用于在归并过程中临时存储元素。
- 定义了一个mergesort函数，用于实现归并排序。该函数接受一个数组a，以及数组的左右边界l和r。若左右边界相等，则表示只有一个元素，无需排序，直接返回。否则，将数组a一分为二，分别对左半部分和右半部分进行归并排序。
- 在归并排序的过程中，先求出左半部分的中点mid，然后递归调用mergesort函数，对左半部分进行排序。再递归调用mergesort函数，对右半部分进行排序。
- 接下来，定义变量i和j，分别指向左半部分和右半部分的起始位置。定义一个变量cnt，用于计数。在while循环中，比较左半部分和右半部分当前位置的元素，将较小的元素放入辅助数组b，并将相应位置向后移动一位。
- 最后，将剩余的元素按顺序放入辅助数组b。再将辅助数组b中的元素复制回原数组a。
- 主函数中，首先读入整数n，并定义一个数组a，用于存储n个数字。 循环读入n个数字，将它们存入数组a。 调用mergesort函数，对数组a进行归并排序。 最后循环输出数组a的元素，实现排序后的结果。
判断题
1)、该算法中“int *a”没有传值
2)、该算法会换行
3)、该算法中mergesort 函数时间复杂度为 0(nlogn)
4)、如果输人为“5 4 3 9 7 8"则输出为3 4 7 8 9 \n
答案：1 × 2 √ 3 √ 4 √
答案分析：
1、从程序分析可以得出主函数种的a就是给int * a传值，只是传递进来的是数组首地址
2、在输出最后一个数字的时候就会换行
3、归并排序的时间复杂度就是O(n log n)
4、从程序分析中可以看出归并排序是按从小到大排序的
单选题
5)、下面哪句与“i==n?'\n':' '”相同
A、.i!=1 ? '\n' : ’ ‘
B、" \n"[i==n]
C、" \n"[i !=n]
D、’ ‘
答案：B
答案分析：从程序分析中可以看出当最后一个数字输出的时候才换行，等价于答案B
6)、该算法的最劣复杂度与哪个排序算法相同
A、快速排序
B、选择排序
C、计数排序
D、堆排序
答案：D
答案分析：快速排序和选择排序的时间复杂度都是O（n*n），计数排序的时间复杂度是O（n+k），堆排序的时间复杂度是O（n log n），答案D
第二题 并查集
1 #include<iostream>
2 using namespace std;
3 int i,j,k,n,m,f[10010],p1,p2,p3;
4 int find(int k){
5 if(f[k]==k)return k;
6 return f[k]=find(f[k]);
7 }
8 int main()
9 {
10 cin>>n>>m;
11 for(i=1;i<=n;i++)f[i]=i;
12 for(i=1;i<=m;i++){
13 cin>>p1>>p2>>p3;
14 if(p1==1)
15 f[find(p2)]=find(p3);
16 if(p1==2)
17 if(find(p2)==find(p3))
18 printf("y\n");
19 else
20 printf("N\n");
21 }
22 return 0;
23 }程序分析
主要考查小朋友们读写程序能力和逻辑思维能力，此程序是一个并查集的实现，用来解决集合的合并和查询问题。
- 程序中定义了一个数组f[10010]，表示每个元素所属的集合，初始时每个元素都是自己所属的集合。
- 函数find(k)用来查找元素k所属的集合，如果f[k]等于k，则返回k。否则，通过递归调用find(f[k])的方式，找到k所属的集合，并返回。
- 在主函数中，首先读入n和m，分别表示元素个数和操作次数。
- 接下来通过一个循环，遍历m次，读入每个操作的信息。
- 如果操作为1，则将元素p2和p3所属的集合合并在一起，即将p2所属的集合的根节点设置为p3所属的集合的根节点。
- 如果操作为2，则判断元素p2和p3是否属于同一个集合，即判断它们的根节点是否相同。如果根节点相同，则输出"y"，否则输出"N"。
- 最后，程序返回0，表示正常结束。
判断题
1)、该算法中p1的作用是确定操作类型
2)、去掉 for(i=1;i<=n;i++)f[i]=i;对该算法没有影响
3)、输人2 2 1 1 2 2 1 2 输出为Y
4)、输人2 1 2 1 2输出为N
答案：1 √ 2 × 3 √ 4 √
答案分析：
1、从程序分析可以得出p1的作用就是判断操作类型
2、如果去掉for循环，就意味着并查集没有初始化，肯定有影响
3、从程序分析可以得出开始p1=1的时候1和连一起，所以后一次输入的时候1和2就是在一个集合里面
4、从程序分析可以得出只有一步p1=2，并没有p1=1进行先合并集合，而是之间判断1和2是否同一个集合
单选题
5)、该算法时间复杂度为
A、O(m log n)
B、O(nm)
C、O(n+m)
D、O(nmm)
答案：A
答案分析：从程序分析以及程序中可以得出，如果没有按次进行合并的时间复杂度为O(log n)，按次之后就应该是O(m log n)，答案A
6)、把 return f[k]=find(f[k]);改成return find(f[k]);最差时间复杂度为
A、O(m log n)
B、O(nm)
C、O(n+m)
D、O(nmm)
答案：B
答案分析：从程序分析以及程序中可以得出，如果没有路径压缩的时间复杂度为O(n)，再进行m次之后的时间复杂度就是O(nm)，答案B
第三题 因式分解组合
#include<iostream>
using namespace std;
int t,x[100],a[100];
void work(int d,int i,int n){int k;if(n==1){for(k=0;k<d;k++)printf("%3d",a[k]);printf("\n");}elsefor(k=i;k<t;k++)if(n % x[k]==0){a[d]=x[k];work(d+1,k,n/x[k]);}
}
int main(){int i,k,n;cin>>n;for(i=n;i>1;i--)if(n%i==0) x[t++]=i;work(0,0,n);
}程序分析
主要考查小朋友们读写程序能力和逻辑思维能力，这段代码使用了递归来求解给定数n的所有因子的组合。
- 首先，在主函数中，通过cin读取一个整数n，然后从n开始递减，判断n的因子，并将这些因子存储在数组x中。同时，使用变量t来记录数组x中的元素个数。
- 接下来，调用work函数进行递归求解。work函数有三个参数，分别是当前因子的组合长度d，当前起始位置i以及剩余待分解的数n。
- 如果n等于1，说明当前已经找到了一组因子的组合，通过循环遍历数组a，将当前组合中的因子输出，并换行。
- 否则，使用循环遍历数组x，并判断当前数n是否可以被数组中的元素整除。如果可以，则将该元素作为当前组合的一个因子，并递归调用work函数，传入更新后的参数。
- 整个递归过程中，d增加表示找到了一个新的因子，i保持不变以确保每个因子只使用一次，n更新为n除以当前因子。
- 最终，所有的组合都会被找到并输出。
判斯题
1) for(i=n;i>1;i--)if(n%i==0)x[t++]=i;的作用是求出n的所有因数
2) 该程序的作用是对n进行质因数分解
3) prin("%3d",a[k]);中去掉3对程序没有影响
4) 去掉if(n%x[k]==0)对程序有影响
答案：1 × 2 × 3 × 4 √
答案分析：
1、从程序分析可以看出，并不是求因数，如果是求因数应该要包括数字1
2、从程序分析可以看出，该程序是求出n的所有因数组合
3、这里的3表示的是输出占位符，也就是每个输出数字占3个位，如果去掉了因素就合并在一起变成几十上百，就变了
4、这里的if表示找到了能被n分解的因子，如果去掉就不是所有的都能被整除，也就是并不是所欲的都是n的因子
单选题
5)如果输人为2,那么输出为
A、2
B、2 1
C、1 2
D、2 2
答案：A
答案分析：从程序分析中可以得出，如果输入的是2，也就只会执行一次，只有2这个因素，因为程序中排除了1这个因素，答案A
6)如果输人为72,那么输出的非回车字符有多少行
A、14
B、15
C、16
D、17
答案：C
答案分析：从程序分析中可以得出求得是因式分解的组合数，72可以分解为：
72
36 2
24 3
18 4
18 2 2
12 6
12 3 29 89 4 29 2 2 28 3 36 6 26 4 36 3 2 24 3 3 23 3 2 2 2
