ACM大学生程序设计综合实践期末考试试题及答案

ACM大学生程序设计综合实践期末考试试题及答案考试说明：满分100分，考试时间120分钟，包含选择题、填空题、编程实操题，语言不限（推荐C/C++、Java、Python），侧重基础算法、逻辑思维与代码实操能力。一、单项选择题（共10题，每题3分，共30分）每题只有一个正确答案，选择最贴合题意的选项1.下列时间复杂度中，效率最高的是（）A.O(n²)  B.O(logn)  C.O(n)  D.O(1)2.冒泡排序算法的最坏时间复杂度为（）A.O(n)  B.O(n²)  C.O(logn)  D.O(nlogn)3.栈结构的操作特性是（）A.先进先出  B.先进后出  C.随机存取  D.有序排序4.队列结构不适合用于以下哪种场景（）A.任务排队调度  B.浏览器后退功能  C.消息队列处理  D.多人排队系统5.二分查找算法适用的前提条件是（）A.数组无序  B.数组有序  C.数组元素唯一  D.数组长度为偶数6.下列不属于递归算法必备要素的是（）A.递归终止条件  B.递归递推公式  C.循环遍历结构  D.问题规模缩小逻辑7.哈希表的核心优势是（）A.有序存储  B.查找效率极高  C.占用内存极小  D.无冲突风险8.求最短路径的Dijkstra算法适用于（）A.带权无负权图  B.任意有向图  C.带负权图  D.无权图9.C++语言中，vector容器对应的底层数据结构是（）A.链表  B.动态数组  C.栈  D.队列10.贪心算法的核心思想是（）A.全局最优推导  B.每一步局部最优  C.暴力枚举所有解  D.递归回溯求解二、填空题（共5题，每题4分，共20分）1.链表相比于数组，最大的优势是__________，无需预先分配固定内存空间。2.深度优先搜索的英文缩写是DFS，广度优先搜索的英文缩写是__________。3.斐波那契数列的前两项均为1，数列前5项依次是__________。4.快速排序的平均时间复杂度是__________，是实践中效率极高的排序算法。5.二叉树中，度为0的节点称为__________节点。三、编程实操题（共3题，共50分）题目1：数值求和计算（15分）【题目描述】输入一个正整数n，计算1~n之间所有偶数的平方和。【输入格式】单个正整数n（1≤n≤1000）【输出格式】输出一个整数，为对应偶数平方和【样例输入】10【样例输出】220【样例解释】2²+4²+6²+8²+10²=4+16+36+64+100=220题目2：字符串字符统计（15分）【题目描述】输入一串仅包含小写字母的字符串，统计字符串中元音字母（a、e、i、o、u）的个数并输出。【输入格式】单行字符串（长度不超过100）【输出格式】输出一个整数，为元音字母总个数【样例输入】acmprogram【样例输出】3【样例解释】字符串中a、o、a共3个元音字母题目3：最大公约数与最小公倍数（20分）【题目描述】输入两个正整数a、b，求解并输出两个数的最大公约数（GCD）和最小公倍数（LCM）。【输入格式】两个空格分隔的正整数（1≤a,b≤10000）【输出格式】两个整数，依次为最大公约数、最小公倍数，空格分隔【样例输入】1218【样例输出】636【公式提示】最小公倍数=两数乘积/最大公约数参考答案及详细解析一、单项选择题答案及解析1.答案：D解析：O(1)为常数时间，不随数据量变化，是最优时间复杂度；其余复杂度随数据量增大运行时间明显增加。2.答案：B解析：冒泡排序最坏情况为数组完全逆序，需要进行n(n-1)/2次比较，时间复杂度为O(n²)。3.答案：B解析：栈是典型的后进先出结构，最后入栈的元素最先弹出，常用于递归、回溯、浏览器后退等场景。4.答案：B解析：浏览器后退功能基于栈结构实现，队列先进先出的特性无法满足后退撤销的逻辑。5.答案：B解析：二分查找通过对半缩小检索范围实现高效查找，必须建立在数据有序的基础上，无序数组无法使用。6.答案：C解析：递归核心要素为终止条件和递推逻辑，无需循环结构，循环和递归是两种独立的代码实现方式。7.答案：B解析：哈希表通过哈希映射实现O(1)级别的查找效率，是其最核心优势，存在哈希冲突、无序存储的特点。8.答案：A解析：Dijkstra算法仅适用于无负权边的图，负权图需使用Bellman-Ford等算法。9.答案：B解析：C++vector是动态扩容的数组容器，底层依托连续内存的数组实现，区别于list链表容器。10.答案：B解析：贪心算法不追求全局推演，每一步都选择当前最优解，部分场景可得到全局最优结果。二、填空题答案及解析1.动态扩容、插入删除高效（核心：插入删除无需移动大量元素）解析：数组插入删除需移动后续元素，链表通过指针连接节点，可动态增减节点，操作效率更高。2.BFS解析：BreadthFirstSearch，广度优先搜索，逐层遍历节点，常用于最短路径、层序遍历场景。3.1、1、2、3、5解析：斐波那契数列规则：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)，依次推导前5项即可。4.O(nlogn)解析：快速排序平均时间复杂度为O(nlogn)，最坏为O(n²)，整体排序效率优于冒泡、选择排序。5.叶子解析：二叉树中没有子节点（度为0）的节点为叶子节点，有子节点的为非叶子节点。三、编程实操题答案（C++代码，附带详细注释）题目1参考代码cpp

#include<iostream>

usingnamespacestd;

intmain(){

intn;

cin>>n;

intsum=0;

//遍历1到n的所有数，筛选偶数计算平方和

for(inti=2;i<=n;i+=2){

sum+=i*i;

}

cout<<sum<<endl;

return0;

}解题思路：直接遍历所有偶数，累加平方值，循环步长设为2可减少循环次数，提升效率。题目2参考代码cpp

#include<iostream>

#include<string>

usingnamespacestd;

intmain(){

strings;

cin>>s;

intcnt=0;

//遍历字符串每个字符

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

charc=s[i];

//判断是否为元音字母

if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'){

cnt++;

}

}

cout<<cnt<<endl;

return0;

}解题思路：逐字符遍历字符串，匹配元音字母，统计计数，逻辑简单直观，适配题目数据范围。题目3参考代码cpp

#include<iostream>

usingnamespacestd;

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

intgcd(inta,intb){

while(b!=0){

inttemp=a%b;

a=b;

b=temp;

}

returna;

}

intmain(){

inta,b;

cin>>a>>b;

intmax_gcd=gcd(a,b);

//防止整数溢出，先除后乘

intmin_lcm=a/max_gcd*b;

cout<<max_gcd<<""<<min_lcm<<endl;

retur