2025年大学二年级计算机科学上学期算法试卷

2025年大学二年级计算机科学上学期算法试卷考试时间：______分钟总分：______分姓名：______一、选择题（每题2分，共20分。请将正确选项的字母填在题后的括号内）1.下列关于算法复杂度的说法中，正确的是（）。a)算法的实际执行时间取决于算法的输入规模和实现语言b)复杂度仅描述算法执行所需的时间c)O(f(n))表示算法的最快执行时间d)对于同一个问题，只有一种算法复杂度最低2.若一个算法的时间复杂度为O(n^2)，则当输入规模n增加一倍时，其执行时间大约增加（）。a)1倍b)2倍c)3倍d)4倍3.在下列排序算法中，平均情况下和最坏情况下的时间复杂度都是O(n^2)的是（）。a)归并排序b)快速排序c)插入排序d)堆排序4.下列数据结构中，最适合用来实现栈的是（）。a)链表b)数组c)哈希表d)树5.在一个长度为n的有序数组中查找一个不存在的元素，采用二分查找方法，其比较次数的最坏情况是（）。a)O(1)b)O(logn)c)O(n)d)O(nlogn)6.下列关于递归的说法中，错误的是（）。a)递归函数必须包含递归调用语句b)递归函数必须有一个明确的终止条件c)递归思考将问题分解为规模更小的相同问题d)递归通常比循环更高效7.在具有n个节点的单链表中，删除一个已知值的节点，其最坏情况下的时间复杂度是（）。a)O(1)b)O(logn)c)O(n)d)O(n^2)8.对于二叉搜索树，下列性质中错误的是（）。a)左子树上所有节点的值均小于根节点的值b)右子树上所有节点的值均大于根节点的值c)左右子树也都是二叉搜索树d)树中一定存在一个节点，其左子树和右子树的高度差大于19.广度优先搜索（BFS）算法通常使用（）来实现。a)栈b)队列c)堆d)哈希表10.已知数组A={5,1,8,3,2}，对其执行一次冒泡排序（从小到大），排序后的第一个元素是（）。a)1b)2c)3d)5二、判断题（每题1分，共10分。请在题后的括号内填“√”表示正确，“×”表示错误）1.算法的空间复杂度仅与算法执行过程中临时占用的存储空间有关。（）2.快速排序在最坏情况下的时间复杂度是O(n^2)，但平均情况下的时间复杂度是O(nlogn)。（）3.队列是一种先进先出（FIFO）的数据结构。（）4.插入排序是一种稳定的排序算法。（）5.在任何情况下，二分查找都比顺序查找更高效。（）6.递归算法通常需要比非递归算法更多的栈空间。（）7.哈希表的平均查找时间复杂度可以达到O(1)。（）8.树的节点可以有多个父节点。（）9.深度优先搜索（DFS）算法可以使用栈或队列来实现。（）10.冒泡排序是一种分治策略的排序算法。（）三、简答题（每题5分，共15分）1.简述大O表示法的基本思想及其主要用途。2.请分别说明栈和队列的基本操作（至少三种）及其逻辑含义。3.比较归并排序和快速排序的特点（至少两点），并说明它们各自适用于什么情况。四、算法设计题（每题10分，共20分）1.设计一个算法，计算一个非负整数n的所有因子（包括1和n本身）之和。请用伪代码或C/C++/Java等你熟悉的语言描述该算法的主要步骤。2.假设你有一个只包含正整数的数组A，请你设计一个算法，找出数组中第二大的元素。如果数组中所有元素都相同，则不存在第二大的元素，算法应返回一个特殊标记（如-1）。请用伪代码或C/C++/Java等你熟悉的语言描述该算法的主要步骤。五、编程题（每题15分，共30分）1.请编写一个函数，实现快速排序算法。该函数应接受一个整数数组作为输入，并原地（in-place）对该数组进行排序。要求在函数内部实现快速排序的逻辑。2.请编写一个函数，实现二分查找算法。该函数应接受一个按升序排列的整数数组和一个目标值作为输入，如果数组中存在目标值，则返回其索引；如果不存在，则返回-1。要求在函数内部实现二分查找的逻辑。试卷答案一、选择题1.a解析：算法复杂度描述的是算法效率随输入规模增长的趋势，实际执行时间受硬件、实现语言等多种因素影响。复杂度分析关注的是增长速度，而非绝对时间。O(f(n))描述的是增长上界，并非最快时间。算法可能有多种复杂度，取决于不同情况下的表现。2.d解析：O(n^2)表示执行时间与n的平方成正比。当n翻倍时，新的输入规模为2n，执行时间约为(2n)^2/n^2=4倍。3.c解析：插入排序和选择排序在最好（已排序）情况下均为O(n)，在最坏（逆序）和平均情况下均为O(n^2)。归并排序和堆排序在最好、最坏、平均情况下均为O(nlogn)。4.b解析：数组支持随机访问，实现栈的push和pop操作（通常在末尾）非常高效。链表虽然也能实现栈，但push/pop涉及指针操作，可能比数组略慢或需要更多空间。5.c解析：二分查找每次将搜索区间减半。最坏情况（查找失败且元素最接近）需要经过log2(n)次比较，当n次比较后区间大小变为1时，即为log2(n)+1次。由于通常计数从1开始，最坏情况比较次数为O(logn)。顺序查找最坏情况比较n次。6.d解析：递归不一定比循环更高效。递归可能带来额外的函数调用开销和栈空间消耗，对于某些问题，循环可能是更优或更节省资源的选择。7.c解析：在单链表中查找要删除的节点需要遍历链表，最坏情况是待删除节点是最后一个节点，需要遍历n个节点。找到节点后，删除操作本身是O(1)。8.d解析：二叉搜索树的性质包括：左子树所有节点值<根节点值<右子树所有节点值；左右子树也都是二叉搜索树。树的平衡性（高度差不超过1）是平衡二叉搜索树（如AVL树、红黑树）的特性，而非普通二叉搜索树的性质。9.b解析：BFS的核心思想是逐层遍历，符合队列先进先出的特性。使用栈可以实现DFS。10.b解析：冒泡排序从前往后比较相邻元素，将较大的元素向后移动。初始数组为{5,1,8,3,2}，第一次比较5和1，交换得到{1,5,8,3,2}，第一个元素变为1。二、判断题1.√解析：算法的空间复杂度是指算法运行时所需存储空间的大小，包括输入数据所占空间、辅助变量所占空间以及递归调用栈空间等。临时占用空间是空间复杂度的一部分。2.√解析：快速排序的时间复杂度与其分治过程的结果有关。平均情况下，每次划分能将问题规模大致减半，符合递归树模型的高度logn，每层处理n个节点，故为O(nlogn)。最坏情况发生在每次划分只能减少一个元素（如已排序数组且选择固定基准），递归深度为n，每层仍处理n个节点，复杂度为O(n^2)。3.√解析：队列遵循先进先出（First-In,First-Out,FIFO）原则，最早进入的元素最先被移除。4.√解析：插入排序在插入元素时，会将其与前面的已排序元素比较，如果待插入元素与前面某个元素相等，则保持它们原有的相对顺序不变，因此是稳定的。5.×解析：二分查找要求待查找的序列必须是有序的。对于无序序列，二分查找不适用，顺序查找可能是更合适的选择（尽管效率较低）。在序列无序时，顺序查找的时间复杂度为O(n)，可能比二分查找（O(logn)）更高效。6.√解析：递归函数的每一次调用都需要在调用栈上保存其局部变量和返回地址。递归调用的次数越多，栈的深度就越深，占用的栈空间就越大。7.√解析：理想情况下，哈希表通过计算键的哈希值直接定位到存储位置，实现常数时间O(1)的平均查找。即使考虑冲突解决（如链地址法、开放地址法），通过合适的哈希函数和冲突处理，平均查找时间仍可保持O(1)或接近O(1)。8.×解析：根据树的定义，树是一种非线性结构，其中每个节点（除根节点外）有且仅有一个父节点。如果节点有多个父节点，则该结构不再是树，而是有向图或更一般的数据结构。9.√解析：DFS的核心是探索一条路径直到无法继续，然后再回溯。这与栈的后进先出（LIFO）特性非常契合，可以用栈模拟DFS过程。虽然也可以用队列模拟（得到BFS），但用栈模拟DFS更直观。10.×解析：冒泡排序的基本思想是通过重复遍历待排序序列，比较相邻元素并交换位置，将较大的元素逐渐“冒泡”到序列的末尾。它是一种交换排序，不是分治排序。分治策略将问题分解为子问题，分别解决，再合并结果（如归并排序）。三、简答题1.大O表示法的基本思想是用一个函数的增长趋势来描述算法运行时间或所需空间随输入规模增长的变化规律，忽略常数因子和低阶项。其主要用途是方便地比较不同算法在输入规模很大时的效率差异，关注算法的“渐近”性能，从而选择适合特定问题的算法。2.栈的基本操作包括：*push(x)：将元素x压入栈顶。逻辑含义是使x成为新的栈顶元素。*pop()：移除栈顶元素并返回它。逻辑含义是访问并移除当前栈顶的元素。*top()或peek()：返回栈顶元素的值，但不移除它。逻辑含义是查看当前栈顶元素。队列的基本操作包括：*enqueue(x)：将元素x加入队尾。逻辑含义是使x成为新的队尾元素。*dequeue()：移除队首元素并返回它。逻辑含义是访问并移除当前队首的元素。*front()或peek()：返回队首元素的值，但不移除它。逻辑含义是查看当前队首元素。栈是LIFO（后进先出）结构，适用于需要“后处理”的场景。队列是FIFO（先进先出）结构，适用于需要“先处理”的场景。3.归并排序和快速排序的比较：*稳定性：归并排序是稳定的排序算法，相等元素的相对顺序不变。快速排序通常是不稳定的排序算法，相等元素的相对顺序可能改变。*时间复杂度：快速排序的平均和最好情况时间复杂度为O(nlogn)，但最坏情况为O(n^2)（如已排序数组且选择固定基准）。归并排序的最好、平均、最坏情况时间复杂度均为O(nlogn)。*空间复杂度：归并排序需要额外的存储空间来合并子数组，空间复杂度为O(n)。快速排序是原地排序（空间复杂度为O(logn)用于递归栈），不需要额外存储空间。归并排序适用于需要稳定排序且空间允许的情况。快速排序适用于对空间要求严格且平均性能要求高的情况，可以通过选择好的基准来避免最坏情况。四、算法设计题1.伪代码：FunctionSumOfFactors(n)Ifn<=0ThenReturn0//处理非正整数情况EndIfsum=0Fori=1TonStep1IfnModi==0Thensum=sum+iEndIfNextiReturnsumEndFunction//主要步骤：初始化和为0；遍历从1到n的所有整数i；检查i是否为n的因子（n能被i整除）；如果是，则累加到和中；返回最终的和。2.伪代码：FunctionFindSecondLargest(A)IfLength(A)<2ThenReturn-1//元素不足两个，不存在第二大的EndIffirstMax=A[0]secondMax=-1Fori=1ToLength(A)-1IfA[i]>firstMaxThensecondMax=firstMaxfirstMax=A[i]ElseIfA[i]>secondMaxAndA[i]!=firstMaxThensecondMax=A[i]EndIfNextiReturnsecondMaxEndFunction//主要步骤：初始化firstMax为第一个元素，secondMax为-1；遍历数组A的其余元素；对于当前元素A[i]：如果A[i]大于firstMax，则更新secondMax为旧的firstMax，然后更新firstMax为A[i]；如果A[i]小于firstMax且大于secondMax（且不等于firstMax），则更新secondMax为A[i]；返回secondMax。如果所有元素都相等，secondMax保持为-1。五、编程题1.C++示例：#include<vector>voidquickSort(std::vector<int>&A,intlow,inthigh){if(low<high){//Partitionthearrayaroundthepivotintpivot=A[high];inti=low-1;for(intj=low;j<high;j++){if(A[j]<=pivot){i++;std::swap(A[i],A[j]);}}std::swap(A[i+1],A[high]);intpartitionIndex=i+1;//RecursivelysortelementsbeforeandafterpartitionquickSort(A,low,partitionIndex-1);quickSort(A,partitionInde