2025年C++数据结构机试题及答案

2025年C++数据结构机试题及答案【问题描述】任务调度系统需要处理动态添加的任务及其依赖关系，并支持查询从指定起始任务开始的最短完成总时间（即关键路径长度）。每个任务有唯一的ID和执行时间，任务执行前需完成所有前置任务。系统需支持以下两种操作：1.添加任务：格式为"ADD<任务ID><执行时间><前置任务数><前置任务ID列表>"（若前置任务数为0，则列表为空）2.查询任务：格式为"QUERY<起始任务ID>"，输出从该起始任务开始，完成所有可执行任务的最短总时间（即所有可能路径中的最长路径长度）输入保证：-所有任务ID为字符串，由字母和数字组成，长度不超过10-执行时间为正整数-添加任务时，所有前置任务已存在-任务依赖关系构成有向无环图（DAG）【输入样例】5ADDA30ADDB21AADDC41AADDD52BCQUERYA【输出样例】12【答案】```cppinclude<iostream>include<unordered_map>include<vector>include<queue>include<string>include<algorithm>include<climits>usingnamespacestd;structTask{inttime;vector<string>preds;vector<string>succs;};unordered_map<string,Task>tasks;vector<string>get_reachable(conststring&start){vector<string>reachable;if(tasks.find(start)==tasks.end())returnreachable;unordered_map<string,bool>visited;queue<string>q;q.push(start);visited[start]=true;reachable.push_back(start);while(!q.empty()){stringu=q.front();q.pop();for(conststring&v:tasks[u].succs){if(!visited[v]){visited[v]=true;reachable.push_back(v);q.push(v);}}}returnreachable;}vector<string>topological_sort(constvector<string>&nodes){unordered_map<string,int>in_degree;unordered_map<string,vector<string>>adj;for(conststring&u:nodes){adj[u]=tasks[u].succs;in_degree[u]=0;for(conststring&p:tasks[u].preds){if(find(nodes.begin(),nodes.end(),p)!=nodes.end()){in_degree[u]++;}}}queue<string>q;for(conststring&u:nodes){if(in_degree[u]==0){q.push(u);}}vector<string>topo;while(!q.empty()){stringu=q.front();q.pop();topo.push_back(u);for(conststring&v:adj[u]){if(find(nodes.begin(),nodes.end(),v)!=nodes.end()){in_degree[v]--;if(in_degree[v]==0){q.push(v);}}}}returntopo;}intquery(conststring&start){vector<string>reachable=get_reachable(start);if(reachable.empty())return0;vector<string>topo=topological_sort(reachable);if(topo.size()!=reachable.size())return0;unordered_map<string,int>dp;intmax_time=0;for(conststring&u:reachable){dp[u]=INT_MIN;}dp[start]=tasks[start].time;max_time=dp[start];for(conststring&u:topo){for(conststring&v:tasks[u].succs){if(find(reachable.begin(),reachable.end(),v)!=reachable.end()){if(dp[v]<dp[u]+tasks[v].time){dp[v]=dp[u]+tasks[v].time;if(dp[v]>max_time){max_time=dp[v];}}}}}returnmax_time;}intmain(){intn;cin>>n;stringop;while(n--){cin>>op;if(op=="ADD"){stringid;intt,k;cin>>id>>t>>k;Tasktask;task.time=t;for(inti=0;i<k;++i){stringpred;cin>>pred;task.preds.push_back(pred);tasks[pred].succs.push_back(id);}