ACM基础程序设计竞赛试题（含详细答案解析）

ACM基础程序设计竞赛试题（含详细答案解析）适用范围：高校ACM校赛、新生选拔赛考试时长：120分钟满分：100分语言限制：C/C++、Java、Python一、单项选择题（共10题，每题3分，共30分）说明：每题只有一个正确答案，多选、错选、不选均不得分1.下列关于时间复杂度的描述中，效率最高的是（）A.O(n²)  B.O(logn)  C.O(n)  D.O(nlogn)2.栈结构的核心操作特性是（）A.先进先出  B.先进后出  C.随机存取  D.有序存储3.已知一个二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为（）A.CBEFDA  B.FEDCBA  C.CBEDFA  D.无法确定4.在C++中，下列变量定义合法的是（）A.int1a=10;  B.inta_1=10;  C.inta-b=10;  D.intfloat=10;5.冒泡排序算法的最坏时间复杂度为（）A.O(1)  B.O(n)  C.O(n²)  D.O(logn)6.队列不适合用于以下哪种场景（）A.任务排队调度  B.函数递归调用  C.消息缓冲处理  D.广度优先搜索7.十进制数25对应的二进制数是（）A.11001  B.10111  C.11010  D.100118.下列排序算法中，属于稳定排序的是（）A.快速排序  B.冒泡排序  C.选择排序  D.堆排序9.图的广度优先搜索（BFS）主要借助的数据结构是（）A.栈  B.队列  C.数组  D.链表10.若inta=5,b=2;则a%b的结果是（）A.0  B.1  C.2  D.2.5二、程序填空题（共2空，每空5分，共10分）说明：根据题目功能，补全代码空缺部分，实现完整功能题目功能：输入一个正整数n，计算1~n的所有整数累加和，输出结果。c++

#include<iostream>

usingnamespacestd;

intmain(){

intn,sum=0;

cin>>n;

for(inti=1;______;i++){

sum+=i;

}

cout<<sum<<endl;

return0;

}补充第二空：若改用while循环实现相同功能，补全下方代码：c++

#include<iostream>

usingnamespacestd;

intmain(){

intn,sum=0,i=1;

cin>>n;

while(______){

sum+=i;

i++;

}

cout<<sum<<endl;

return0;

}三、编程大题（共3题，每题20分，共60分）说明：编写完整可运行代码，完成题目要求，输入输出格式严格匹配样例题目1：奇偶判断题目描述：输入一个整数，判断该数是奇数还是偶数。若为偶数输出Yes，奇数输出No。输入格式：一行一个整数x（-1000≤x≤1000）输出格式：单行输出结果，无多余字符样例输入1：4样例输出1：Yes样例输入2：7样例输出2：No题目2：最大公约数题目描述：输入两个正整数a、b，求解并输出两个数的最大公约数。输入格式：一行两个正整数a,b（1≤a,b≤1000）输出格式：单行输出最大公约数样例输入：1218样例输出：6题目3：字符串统计题目描述：输入一串仅包含大小写字母的字符串，统计其中大写字母的个数并输出。输入格式：单行字符串（长度不超过100）输出格式：单行输出大写字母数量样例输入：AcMPro样例输出：2四、详细答案与解析（一）单项选择题答案及解析1.答案：B解析：时间复杂度优先级：O(logn)<O(n)<O(nlogn)<O(n²)，对数级复杂度运行效率最高。2.答案：B解析：栈是后进先出（先进后出）结构，队列是先进先出结构。3.答案：A解析：由前序A为根节点，中序CBA为左子树、EDF为右子树，递归推导后序序列为CBEFDA。4.答案：B解析：变量名不能以数字开头、不能含特殊符号、不能使用关键字，仅a_1符合规则。5.答案：C解析：冒泡排序最坏情况为逆序数组，需要n(n-1)/2次比较，时间复杂度O(n²)。6.答案：B解析：函数递归调用依靠栈结构实现，队列适用于排队、BFS、消息缓冲等场景。7.答案：A解析：25=16+8+1，对应二进制11001。8.答案：B解析：冒泡排序、插入排序为稳定排序；快排、选择排序、堆排序为不稳定排序。9.答案：B解析：BFS广度优先搜索基于队列实现，DFS深度优先搜索基于栈实现。10.答案：B解析：%为取余运算符，5除以2商2余1，结果为1。（二）程序填空题答案第一空：i<=n解析：循环需要遍历1到n的所有整数，循环条件为i小于等于n。第二空：i<=n解析：while循环延续遍历逻辑，满足i不大于n时持续累加，实现1~n求和。（三）编程大题标准答案（C++版本）题目1：奇偶判断完整代码c++

#include<iostream>

usingnamespacestd;

intmain(){

intx;

cin>>x;

if(x%2==0){

cout<<"Yes"<<endl;

}else{

cout<<"No"<<endl;

}

return0;

}解题思路：利用取余运算，整数对2取余结果为0即为偶数，否则为奇数，注意兼容负数输入。题目2：最大公约数完整代码c++

#include<iostream>

usingnamespacestd;

//欧几里得算法求解最大公约数

intgcd(inta,intb){

while(b!=0){

inttemp=a%b;

a=b;

b=temp;

}

returna;

}

intmain(){

inta,b;

cin>>a>>b;

cout<<gcd(a,b)<<endl;

return0;

}解题思路：采用辗转相除法（欧几里得算法），反复取余迭代，直到余数为0，此时的被除数即为最大公约数，效率高于暴力枚举。题目3：字符串统计完整代码c++

#include<iostream>

#include<string>

usingnamespacestd;

intmain(){

strings;

cin>>s;

intcnt=0;

for(inti=0;i<s.size();i++){

//判断是否为大写字母

if(s[i]>='A'&&s[i]<='Z'){

cnt++;

}

}

cout<<cn