2025年编程计算考试题及答案

2025年编程计算考试题及答案一、选择题（每题3分，共30分）1.以下关于动态规划（DP）的描述中，错误的是：A.动态规划适用于具有重叠子问题和最优子结构性质的问题B.状态转移方程的构建是动态规划的核心步骤C.所有使用递归解决的问题都可以用动态规划优化D.动态规划通过存储子问题的解来避免重复计算2.对于长度为n的有序数组，使用二分查找定位目标值时，最坏情况下的时间复杂度是：A.O(n)B.O(nlogn)C.O(logn)D.O(1)3.若哈希表采用链地址法处理冲突，当插入n个元素时，平均查找长度主要取决于：A.哈希函数的选择B.负载因子（元素数/桶数）C.哈希表的初始大小D.元素的插入顺序4.Python中，以下关于提供器（Generator）的说法正确的是：A.提供器函数使用return返回值B.提供器通过__next__()方法逐个产生值C.提供器表达式使用[]定义D.提供器在内存中存储所有中间结果5.以下C++代码执行后，输出结果是：```cppinclude<iostream>usingnamespacestd;intmain(){inta[]={1,2,3,4};intp=a;cout<<(p+2)p++<<endl;return0;}```A.2B.3C.4D.56.若用邻接表存储一个有向图，其中包含V个顶点和E条边，进行深度优先搜索（DFS）的时间复杂度为：A.O(V)B.O(E)C.O(V+E)D.O(VE)7.以下SQL语句中，用于查询"学生表"中数学成绩在80到90之间（包含边界）的学生姓名的是：A.SELECT姓名FROM学生表WHERE数学成绩BETWEEN80AND90B.SELECT姓名FROM学生表WHERE数学成绩IN(80,90)C.SELECT姓名FROM学生表WHERE数学成绩>80AND<90D.SELECT姓名FROM学生表WHERE数学成绩>=80OR<=908.对于二叉树的后序遍历序列为DEBFCA（根节点为A），中序遍历序列为DBEAFC，则前序遍历序列是：A.ABDECFB.ADBECFC.ABDEFCD.ABEDCF9.以下关于KMP算法的描述中，正确的是：A.KMP算法通过预处理模式串提供部分匹配表（失败函数）B.KMP算法的时间复杂度为O(nm)（n为主串长度，m为模式串长度）C.KMP算法在匹配失败时，主串指针需要回退D.部分匹配表存储的是模式串中最长前缀与后缀的长度差10.用Python实现一个装饰器，用于记录函数的执行时间，以下代码中横线处应填入的是：```pythonimporttimedeftimer(func):defwrapper(args,kwargs):start=time.time()result=func(args,kwargs)end=time.time()print(f"函数{func.__name__}执行时间：{endstart:.4f}秒")return______returnwrapper```A.startB.endC.resultD.func二、填空题（每题4分，共20分）1.已知一个栈的入栈序列是1,2,3,4,5，若出栈序列的第一个元素是3，则最后一个出栈的元素可能是________（写出所有可能值）。2.用快速排序对数组[5,3,9,1,6,2,7]进行升序排序，选择第一个元素5作为基准，一次划分（分区）后的数组状态为________。3.对于递推关系式T(n)=2T(n/2)+n（n>1），T(1)=1，其时间复杂度为________（用大O表示）。4.给定关系模式R(A,B,C,D)，函数依赖集F={A→B,B→C,C→D}，则R的最高范式是________（填1NF/2NF/3NF/BCNF）。5.用Python提供一个包含100个0到99之间随机整数的列表，要求每个数唯一，应使用的代码是________。三、编程题（共50分）1.（15分）某物联网设备每分钟提供一条日志，格式为"时间戳,设备ID,温度,湿度"（如"2025-03-1508:05:00,dev001,25.3,45.6"）。要求编写Python程序：读取当前目录下的"log.txt"文件（假设文件存在且格式正确）；统计每个设备在一天中各小时的平均温度（例如dev001在8点的平均温度）；将结果按设备ID升序、小时升序排序后，输出到"result.csv"文件，格式为"设备ID,小时,平均温度"。2.（20分）给定一个无向图（可能存在环），用邻接表表示（顶点编号从0开始），编写C++程序实现：输入：第一行是顶点数V和边数E；接下来E行，每行两个整数u和v表示顶点u和v之间有一条边；输出：①所有顶点的度（即与该顶点相连的边数）；②从顶点0出发的广度优先搜索（BFS）遍历序列（要求使用队列实现，访问顺序按顶点编号升序）；③判断图中是否存在环，若存在则输出"存在环"，否则输出"不存在环"。3.（15分）设计一个Python类"LRUCache"，实现最近最少使用（LRU）缓存机制：构造方法接收容量参数capacity；实现get(key)方法：若key存在则返回对应值，否则返回-1；访问后需更新key的最近使用状态；实现put(key,value)方法：若key存在则更新值并更新使用状态；若不存在且缓存未满则插入；若已满则删除最久未使用的key，再插入新key-value；要求get和put操作的时间复杂度均为O(1)。答案一、选择题1.C（递归问题若没有重叠子问题，无法用动态规划优化）2.C（二分查找最坏时间复杂度为O(logn)）3.B（链地址法的平均查找长度主要与负载因子相关）4.B（提供器使用yield，通过__next__()产生值）5.A（表达式运算顺序：(p+2)=3，p++=1，3-1=2）6.C（DFS遍历每个顶点和边各一次，时间复杂度O(V+E)）7.A（BETWEEN操作符包含边界值）8.A（通过后序和中序推导前序：根A，中序左子树DBE，右子树FC；后序左子树DEB，右子树FC→左子树根B，右子树根C→前序ABDECF）9.A（KMP预处理模式串提供部分匹配表，主串指针不回退，时间复杂度O(n+m)）10.C（装饰器需要返回原函数的执行结果）二、填空题1.1或2或4或5（出栈序列第一个是3，说明1、2已入栈未出栈，此时栈中有[1,2,3]，出栈顺序可能为3,2,1,4,5→最后5；或3,2,4,1,5→最后5；或3,4,5,2,1→最后1；或3,4,2,5,1→最后1；或3,5,4,2,1→最后1；可能的最后元素为1、2、4、5）2.[2,3,1,5,6,9,7]（快速排序分区过程：基准5，左指针找比5大的元素（9），右指针找比5小的元素（1），交换→[5,3,1,9,6,2,7]；左指针移到9，右指针移到2，交换→[5,3,1,2,6,9,7]；左指针移到6（>5），右指针移到2（<5），此时左指针>右指针，交换基准与右指针位置→[2,3,1,5,6,9,7]）3.O(nlogn)（主定理：T(n)=2T(n/2)+n，a=2,b=2,f(n)=n，满足f(n)=Θ(nlog^0n)，故T(n)=Θ(nlogn)）4.1NF（存在传递依赖A→B→C→D，不满足2NF的完全依赖要求）5.importrandom;lst=random.sample(range(100),100)（sample函数提供不重复的随机数）三、编程题1.Python实现：```pythonfromcollectionsimportdefaultdictimportcsvdefprocess_log():初始化字典：设备→小时→[温度列表,计数]device_hour=defaultdict(lambda:defaultdict(lambda:[0.0,0]))withopen("log.txt","r")asf:forlineinf:line=line.strip()ifnotline:continueparts=line.split(",")timestamp,dev_id,temp,_=parts提取小时（格式"YYYY-MM-DDHH:MM:SS"）hour=int(timestamp.split()[1].split(":")[0])转换温度为浮点数temp_val=float(temp)更新统计device_hour[dev_id][hour][0]+=temp_valdevice_hour[dev_id][hour][1]+=1整理结果并排序result=[]fordevinsorted(device_hour.keys()):设备ID升序forhourinsorted(device_hour[dev].keys()):小时升序total,count=device_hour[dev][hour]avg_temp=total/countresult.append([dev,hour,f"{avg_temp:.2f}"])写入CSVwithopen("result.csv","w",newline="")asf:writer=csv.writer(f)writer.writerow(["设备ID","小时","平均温度"])writer.writerows(result)process_log()```2.C++实现：```cppinclude<iostream>include<vector>include<queue>include<algorithm>usingnamespacestd;classGraph{private:intV;vector<vector<int>>adj;vector<int>degree;boolhasCycleUtil(intv,vector<bool>&visited,vector<bool>&recStack){if(!visited[v]){visited[v]=true;recStack[v]=true;for(intneighbor:adj[v]){if(!visited[neighbor]&&hasCycleUtil(neighbor,visited,recStack))returntrue;elseif(recStack[neighbor])returntrue;}}recStack[v]=false;returnfalse;}public:Graph(intv):V(v),adj(v),degree(v,0){}voidaddEdge(intu,intv){adj[u].push_back(v);adj[v].push_back(u);degree[u]++;degree[v]++;}voidprintDegree(){for(inti=0;i<V;i++)cout<<"顶点"<<i<<"的度："<<degree[i]<<endl;}voidBFS(intstart){vector<bool>visited(V,false);queue<int>q;q.push(start);visited[start]=true;cout<<"BFS遍历序列：";while(!q.empty()){intu=q.front();q.pop();cout<<u<<"";//按顶点编号升序访问邻居sort(adj[u].begin(),adj[u].end());for(intv:adj[u]){if(!visited[v]){visited[v]=true;q.push(v);}}}cout<<endl;}boolhasCycle(){vector<bool>visited(V,false);vector<bool>recStack(V,false);for(inti=0;i<V;i++)if(hasCycleUtil(i,visited,recStack))returntrue;returnfalse;}};intmain(){intV,E;cin>>V>>E;Graphg(V);for(inti=0;i<E;i++){intu,v;cin>>u>>v;g.addEdge(u,v);}//输出度g.printDegree();//BFS遍历g.BFS(0);//判断环cout<<(g.hasCycle()?"存在环":"不存在环")<<endl;return0;}```3.PythonLRUCache实现（使用双向链表+哈希表）：```pythonclassNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.size=0self.cache={}key→Node虚拟头尾节点self.head=Node()self.tail=Node()self.head.next=self.tailself.tail.prev=self.headdef_move_to_head(self,node):断开原位置node.prev.next=node.nextnode.next.prev=node.prev插入头部node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_add_to_head(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=no