2025年大学计算机程序设计试卷及答案

2025年大学计算机程序设计试卷及答案一、单项选择题（每题2分，共20分）1.以下关于C++指针的描述中，正确的是（）。A.指针变量存储的是对象的值B.空指针（nullptr）可以解引用C.指向数组的指针进行+1操作时，移动的字节数等于数组元素类型的大小D.指针数组与数组指针的定义完全相同2.Python中，执行以下代码后，输出结果是（）。```pythondeff(x):return[lambday:yiforiinx]res=f([1,2,3])print([func(2)forfuncinres])```A.[2,4,6]B.[6,6,6]C.[2,2,2]D.[3,3,3]3.对长度为n的有序数组进行二分查找，最坏情况下的时间复杂度为（）。A.O(n)B.O(nlogn)C.O(logn)D.O(n²)4.已知某二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则该二叉树的前序遍历序列为（）。A.CEDBAB.ACBEDC.DECABD.ECDAB5.以下哈希冲突解决方法中，属于开放定址法的是（）。A.链地址法B.再哈希法C.公共溢出区法D.双哈希法6.递归函数计算斐波那契数列F(n)=F(n-1)+F(n-2)（F(0)=0,F(1)=1）时，计算F(5)需要调用函数的次数为（）。A.9次B.15次C.19次D.25次7.动态规划解决最长公共子序列（LCS）问题时，若两个序列长度分别为m和n，则状态表的大小为（）。A.m×nB.(m+1)×(n+1)C.2^(m+n)D.max(m,n)8.无向图的邻接矩阵中，若存在i到j的边，则矩阵中元素G[i][j]和G[j][i]的值（）。A.一定相等B.一定不相等C.可能相等D.无法确定9.C++中，关于虚函数的描述错误的是（）。A.虚函数可以在子类中被重写B.含有纯虚函数的类是抽象类C.虚函数的调用在编译时确定（静态绑定）D.基类指针指向子类对象时，通过指针调用虚函数会执行子类的实现10.Python提供器（generator）的主要优点是（）。A.提高代码运行速度B.减少内存占用C.支持多线程D.强制类型检查二、填空题（每题3分，共15分）1.补全C++代码，实现单链表逆置。假设链表节点定义为：```cppstructListNode{intval;ListNodenext;ListNode(intx):val(x),next(nullptr){}};```逆置函数部分代码如下：```cppListNodereverseList(ListNodehead){ListNodeprev=nullptr,curr=head;while(curr!=nullptr){ListNodenextTemp=curr->next;curr->next=prev;prev=curr;curr=nextTemp;}return______;}```2.归并排序对长度为8的数组进行排序时，递归调用的总次数为______（包括最顶层调用）。3.若二叉树的前序遍历序列为ABCDE，后序遍历序列为CDEBA，则该二叉树的形态______（填“能”或“不能”）唯一确定。4.补全Python代码，实现大根堆的调整函数（siftdown）。假设堆存储为列表heap，当前需要调整的节点索引为i，堆的大小为n：```pythondefsift_down(heap,i,n):largest=ileft=2i+1right=2i+2ifleft<nandheap[left]>heap[largest]:largest=leftifright<nandheap[right]>heap[largest]:largest=rightiflargest!=i:heap[i],heap[largest]=heap[largest],heap[i]______```5.字符串"abacab"的KMP算法部分匹配表（部分匹配值数组）为______（按顺序写出每个字符对应的部分匹配值）。三、编程题（共65分）1.（20分）给定一个由括号和其他字符组成的字符串s，找出其中最长的有效括号子串的长度。有效括号子串需满足：①括号正确匹配（每个左括号有对应的右括号，且顺序正确）；②子串连续，其他字符不影响匹配。例如，输入s="a(bc)d)ef(gh)"，最长有效子串为"(bc)"，长度为3；输入s=")()())"，最长有效子串为"()()"，长度为4。要求用C++实现，时间复杂度O(n)。2.（25分）设计一个算法，计算无向图中两个节点之间的所有简单路径（路径中无重复节点）。输入为邻接表表示的图（节点用整数标识）、起始节点start和终止节点end，输出所有简单路径的列表（路径按节点顺序存储为列表，顺序不限）。例如，输入邻接表{0:[1,2],1:[0,3],2:[0,3],3:[1,2]}，start=0，end=3，输出应为[[0,1,3],[0,2,3]]。要求用Python实现，递归或回溯法。3.（20分）给定一个整数数组nums和目标值target，找出两个不重叠的子数组（子数组指连续元素），使得它们的和均为target，且两个子数组的长度之和最小。若不存在这样的两个子数组，返回-1。例如，输入nums=[1,2,3,4,5]，target=7，可能的子数组组合有[1,2,4]（和为7，长度3）与[3,4]（和为7，长度2），但需不重叠，故最小长度和为3+2=5；输入nums=[-1,3,1,-3,2]，target=3，可能的组合有[3]（长度1）与[1,-3,2]（长度3），或[3,1,-3,2]（和为3，长度4）与无，故最小长度和为1+3=4。要求用动态规划或滑动窗口方法，C++或Python实现。答案一、单项选择题1.C2.B3.C4.A5.B6.B7.B8.A9.C10.B二、填空题1.prev2.15（归并排序递归次数为2n-1，n=8时为15）3.不能（前序和后序无法唯一确定二叉树结构，可能存在不同形态）4.sift_down(heap,largest,n)5.[0,0,1,0,1,2]（部分匹配值为最长相等前缀后缀的长度，"a"→0；"ab"→0；"aba"→1（前缀"a"和后缀"a"）；"abac"→0；"abaca"→1（前缀"a"和后缀"a"）；"abacab"→2（前缀"ab"和后缀"ab"））三、编程题1.C++实现：```cppinclude<string>include<stack>usingnamespacestd;intlongestValidParentheses(strings){stack<int>stk;stk.push(-1);//初始栈底为-1，处理边界intmaxLen=0;for(inti=0;i<s.size();++i){if(s[i]=='('){stk.push(i);}else{stk.pop();if(stk.empty()){stk.push(i);//无效右括号，更新栈底}else{maxLen=max(maxLen,istk.top());}}}returnmaxLen;}```解析：使用栈记录未匹配的左括号索引，初始栈底为-1处理边界。遍历字符串，遇到左括号压栈，遇到右括号弹栈后，若栈非空则计算当前索引与栈顶的差（有效长度），更新最大值。时间复杂度O(n)。2.Python实现：```pythondeffind_all_paths(graph,start,end):paths=[]defbacktrack(current_path,visited):ifcurrent_path[-1]==end:paths.append(current_path.copy())returnforneighboringraph[current_path[-1]]:ifneighbornotinvisited:visited.add(neighbor)current_path.append(neighbor)backtrack(current_path,visited)current_path.pop()visited.remove(neighbor)visited=set([start])backtrack([start],visited)returnpaths```解析：回溯法遍历所有可能路径。使用visited集合记录已访问节点避免重复，current_path记录当前路径。当路径末尾为end时，将路径加入结果列表。时间复杂度取决于路径数量，最坏为O(n!)（n为节点数），但实际中通过剪枝优化。3.Python实现（滑动窗口）：```pythondefminSumOfLengths(nums,target):n=len(nums)left=0current_sum=0min_len=float('inf')dp=[float('inf')]ndp[i]表示前i个元素中长度最小的和为target的子数组result=float('inf')forrightinrange(n):current_sum+=nums[right]左指针右移，缩小窗口whilecurrent_sum>targetandleft<=right:current_sum-=nums[left]left+=1找到和为target的子数组ifcurrent_sum==target:current_length=rightleft+1若左边存在有效子数组，更新结果ifleft>0:result=min(result,dp[left1]+current_leng