数据结构测试题

news/2024/4/24 17:33:02/文章来源:https://blog.csdn.net/2302_79372568/article/details/136414241

目录

1.闰年判断

2.志愿者选拔 

3.单词接龙

4.对称二叉树 

5.英雄南昌欢迎您

6.时间转换

7.矩阵乘法

8. Huffuman树


1.闰年判断

题目描述:

给定一个年份,判断这一年是不是闰年。

当以下情况之一满足时,这一年是闰年:

1. 年份是4的倍数而不是100的倍数;

2. 年份是400的倍数。

其他的年份都不是闰年。

数据规模与约定1990 <= y <= 2050。

输入格式:

输入包含一个整数y,表示当前的年份。请在这里写输入格式。例如:输入在一行中给出2个绝对值不超过1000的整数A和B。

输出格式

输出一行,如果给定的年份是闰年,则输出yes,否则输出no。

输入样例:

2013
2016

输出样例:

no
yes

参考答案:

#include<iostream>
using namespace std;
void check(int year)
{if(year>=1990&&year<=2050){if(year%4==0&&year%400!=0||year%400==0)cout<<"yes"<<endl;else cout<<"no"<<endl;}
}
int main()
{int a,b;cin>>a>>b;check(a),check(b);
}
2.志愿者选拔 

题目描述:

光明学院ACM赛事志愿者的选拔工作正在学院如火如荼地进行。为了选拔最合适的人才,学院对所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定,即如果计划录取m名志愿者,则面试分数线为排名第m*150%(向下取整)名的选手的分数,而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线,并输出所有进入面试的选手的报名号和笔试成绩。

输入格式:

第1行,两个整数n,m(5≤n≤5000,3≤m≤n),中间用一个空格隔开,其中n表示报名参加笔试的选手总数,m表示计划录取的志愿者人数。输入数据保证m*150%向下取整后小于等于n。

第2行到第n+1行,每行包括两个整数,中间用一个空格隔开,分别是选手的报名号k(1000≤k≤9999)和该选手的笔试成绩s(1≤s≤100)。数据保证选手的报名号各不相同。

输出格式:

第1行,有两个整数,用一个空格隔开,第1个整数表示面试分数线;第2个整数为进入面试的选手的实际人数。

从第2行开始,每行包括两个整数,中间用一个空格隔开,分别表示进入面试的选手的报名号和笔试成绩,按照笔试成绩从高到低输出,如果成绩相同,则按报名号由小到大的顺序输出。

输入样例:

6    3    
1000    90
3239    88
2390    95
7231    84
1005    95
1001    88

输出样例:

88    5
1005    95
2390    95
1000    90
1001    88
3239    88

参考答案: 

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
struct node{int hao;int score;bool operator<(const node& L)const{return score>L.score||(score==L.score&&hao<L.hao);}
};
struct node ren[5005];
int main()
{cin>>n>>m;for(int i=0;i<n;i++){int hao,g;cin>>hao>>g;ren[i]={hao,g};}sort(ren,ren+n);int x=(int)(m*1.5);int xian=ren[x-1].score;int sum=0;cout<<xian;for(int i=0;i<n;i++){if(ren[i].score>=xian) sum++;}cout<<' '<<sum<<endl;for(int i=0;i<n;i++)if(ren[i].score>=xian)cout<<ren[i].hao<<' '<<ren[i].score<<endl;
}
3.单词接龙

题目描述:

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at和atide间不能相连。

输入格式:

输入的第一行为一个单独的整数n(n<=20)表示单词数,以下n行每行有一个单词(只含有大写或小写字母,长度不超过20),输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式:

只需输出以此字母开头的最长的“龙”的长度。

输入样例:

5
at
touch
cheat
choose
tact
a

输出样例:

23

参考答案 :

#include<iostream>
#include<cstring>
using namespace std;
const int N=10005;
string all[N];
int n,book[N],sub[N][N],ans;
void dfs(string s,int u)
{int len=s.size();ans=max(ans,len);book[u]++;for(int i=1;i<=n;i++){if(book[i]<2&&sub[u][i]){dfs(s+all[i].substr(sub[u][i]),i);}}book[u]--;return ;
}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>all[i];}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){string a=all[i],b=all[j];int lena=a.size(),lenb=b.size();int len=min(lena,lenb);for(int k=1;k<len;k++){if(a.substr(a.size()-k,k)==b.substr(0,k)){sub[i][j]=k;break;}}} char head;cin>>head;// cout<<head<<endl;for(int i=1;i<=n;i++)if(all[i][0]==head)dfs(all[i],i);cout<<ans;return 0;
}
4.对称二叉树 

题目描述:

如果二叉树的左右子树的结构是对称的,即两棵子树皆为空,或者皆不空,则称该二叉树是对称的。编程判断给定的二叉树是否对称。

例:如下图中的二叉树T1是对称的,T2是不对称的。

二叉树用顺序结构给出,若读到#则为空,二叉树T1=ABCDE,T2=ABCD#E,如果二叉树是对称的,输出“Yes”,反之输出“No”。

输入格式:

二叉树用顺序结构给出,若读到#则为空。

输出格式:

如果二叉树是对称的,输出“Yes”,反之输出“No”。

输入样例:

ABCDE

输出样例:

Yes

参考答案:

#include<iostream>
using namespace std;
int main()
{string s;cin>>s;int len=s.size();s[len]='#';int f=0;for(int i=1;i<len;i+=2){if((s[i]=='#'&&s[i+1]!='#')||(s[i+1]=='#'&&s[i]!='#')){f=1;break;}}if(f==1) cout<<"No";else cout<<"Yes";
}
5.英雄南昌欢迎您

题目描述:

南昌城是一个英雄城,也是一个旅游胜地,每年都有成千上万的人前来观光。为方便游客,公交公司在各个旅游景点及宾馆,饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发,依次途经若干个巴士站,最终到达终点巴士站。

一名旅客最近到南昌来旅游,他很想去滕王阁游玩,但如果从他所在的饭店没有一路巴士可以直接到达滕王阁,则他可能要先乘某一路巴士坐几站,再下来换乘同一站台的另一路巴士, 这样换乘几次后到达滕王阁。

现在用整数1,2,…N 给南昌城的所有的巴士站编号,约定这名旅客所在饭店的巴士站编号为1,滕王阁巴士站的编号为N。

写一个程序,帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到滕王阁的过程中换车的次数最少。

输入格式:

第一行有两个数字M和N(1≤M≤100 1<N≤500),表示开通了M条单程巴士线路,总共有N个车站。从第二行到第M行依次给出了第1条到第M条巴士线路的信息。其中第i+1行给出的是第i条巴士线路的信息,从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。

输出格式:

只有一行。如果无法乘巴士从饭店到达滕王阁,则输出"N0",否则输出你的程序所找到的最少换车次数,换车次数为0表示不需换车即可到达。

输入样例:

3 7
6 7
4 7 3 6
2 1 3 5

输出样例:

2

参考答案: 

#include<iostream>
#include<cstring>
using namespace std;
const int N=1005;
int e[N][N],dist[N],book[N],shuzi[N];
char s[N];
const int inf=0x3f3f3f3f;
int n,m;
void Dijkstra()
{book[1]=1;for(int i=1;i<=n;i++){int min_=inf,u;for(int j=1;j<=n;j++){if(book[j]==0&&dist[j]<min_){min_=dist[j];u=j;}}book[u]=1;for(int j=1;j<=n;j++){if(e[u][j]<inf&&dist[j]>dist[u]+e[u][j])dist[j]=dist[u]+e[u][j];}}
}
int main()
{cin>>m>>n;getchar();memset(e,0x3f,sizeof e);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i==j) e[i][j]=0;int k=1;while(m--){k=1;memset(shuzi,0,sizeof shuzi);memset(s,'\0',sizeof s);cin.getline(s,sizeof s);for(int i=0;i<strlen(s);i++){if(isdigit(s[i])){shuzi[k]=shuzi[k]*10+s[i]-'0';}else k++;}for(int i=1;i<k;i++)for(int j=i+1;j<=k;j++)e[shuzi[i]][shuzi[j]]=1;}for(int i=1;i<=n;i++){dist[i]=e[1][i];book[i]=0;} Dijkstra();if(dist[n]!=inf) cout<<dist[n]-1;else cout<<"NO";
}
6.时间转换

题目描述:

给定一个以秒为单位的时间t,要求用“<H>:<M>:<S> ”的格式来表示这个时间。<H>表示时间,<M>表示分钟,而<S>表示秒,它们都是整数且没有前导的“0”。例如,若t=0,则应输出是“0:0:0”;若t=3661,则输出“1:1:1”。

输入格式:

输入只有一行,是一个整数t(0<=t<=86399)。

输出格式:

输出只有一行,是以“<H>:<M>:<S> ”的格式所表示的时间,不包括引号。

输入样例1:

0

输出样例1:

0:0:0

输入样例2:

5436

输出样例2:

5436

参考答案:

#include<iostream>
using namespace std;
int main()
{int n;cin>>n;if(n==0)printf("0:0:0");else{int h=n/3600;int f=n/60-h*60;int m=n-h*3600-f*60;printf("%d:%d:%d",h,f,m);}
}
7.矩阵乘法

题目描述:

给定一个N阶矩阵A,输出A的M次幂(M是非负整数)

  例如:

  A =

  1 2

  3 4

  A的2次幂

  7 10

15 22

输入格式:

第一行是一个正整数N、M(1<=N<=30, 0<=M<=5),表示矩阵A的阶数和要求的幂数

接下来N行,每行N个绝对值不超过10的非负整数,描述矩阵A的值

输出格式:

输出共N行,每行N个整数,表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开

输入样例:

2 2
1 2
3 4

输出样例:

7 10
15 22

参考答案:

#include<iostream>
#include<cstring>
using namespace std;
const int N=105;
int a[N][N],b[N][N],c[N][N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];for(int i=1;i<=n;i++)c[i][i]=1;for(int i=1;i<=m;i++){memset(b,0,sizeof b);for(int j=1;j<=n;j++)for(int j1=1;j1<=n;j1++)for(int j2=1;j2<=n;j2++)b[j][j1]+=c[j][j2]*a[j2][j1];memcpy(c,b,sizeof b);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<c[i][j]<<' ';} if(i<n)cout<<endl;}
}
8. Huffuman树

题目描述:

Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。

  给出一列数{pi}={p0, p1, …, pn-1},用这列数构造Huffman树的过程如下:

  1. 找到{pi}中最小的两个数,设为pa和pb,将pa和pb从{pi}中删除掉,然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。

  2. 重复步骤1,直到{pi}中只剩下一个数。

  在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。

  本题任务:对于给定的一个数列,现在请你求出用该数列构造Huffman树的总费用。

  例如,对于数列{pi}={5, 3, 8, 2, 9},Huffman树的构造过程如下:

  1. 找到{5, 3, 8, 2, 9}中最小的两个数,分别是2和3,从{pi}中删除它们并将和5加入,得到{5, 8, 9, 5},费用为5。

  2. 找到{5, 8, 9, 5}中最小的两个数,分别是5和5,从{pi}中删除它们并将和10加入,得到{8, 9, 10},费用为10。

  3. 找到{8, 9, 10}中最小的两个数,分别是8和9,从{pi}中删除它们并将和17加入,得到{10, 17},费用为17。

  4. 找到{10, 17}中最小的两个数,分别是10和17,从{pi}中删除它们并将和27加入,得到{27},费用为27。

  5. 现在,数列中只剩下一个数27,构造过程结束,总费用为5+10+17+27=59。

输入格式:

输入的第一行包含一个正整数n(n<=100)。

接下来是n个正整数,表示p0, p1, …, pn-1,每个数不超过1000。

输出格式:

输出用这些数构造Huffman树的总费用。

输入样例:

5
5 3 8 2 9

输出样例:

59

参考答案: 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main()
{int n;cin>>n;int x;priority_queue<int,vector<int>,greater<int>> heap;for(int i=0;i<n;i++) {cin>>x;heap.push(x);}int sum=0;while(heap.size()>1){int a=heap.top();heap.pop();int b=heap.top();heap.pop();sum+=a+b;heap.push(a+b);}cout<<sum;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_998439.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Libevent的使用及reactor模型

Libevent 是一个用C语言编写的、轻量级的开源高性能事件通知库&#xff0c;主要有以下几个亮点&#xff1a;事件驱动&#xff08; event-driven&#xff09;&#xff0c;高性能;轻量级&#xff0c;专注于网络&#xff0c;不如 ACE 那么臃肿庞大&#xff1b;源代码相当精炼、易读…

Linux/Knife

Knife Enumeration nmap 第一次扫描发现系统对外开放了22和80端口&#xff0c;端口详细信息如下 系统对外开放了2个端口&#xff0c;22的ssh和80的http&#xff0c;先访问web看看 单看该服务&#xff0c;并没有发现有趣的东西&#xff0c;wappalyzer显示php版本为8.1.0 PHP…

React报错 之 Objects are not valid as a React child

原文链接&#xff1a; 1、React报错之Objects are not valid as a React child 2、Objects are not valid as a React child error [Solved] 作者&#xff1a;Borislav Hadzhiev 以下文中涉及到的链接均来自于该作者&#xff0c;他写了很多相关的文章&#xff0c;可以多看看他的…

Type-C接口小家电使用PD诱骗芯片获取充电器的5V9V12V20V供电

随着Type-C接口的逐渐普及&#xff0c;小家电设备慢慢开始采用Type-C&#xff0c;淘汰了以往的DC接口&#xff0c;Type-C接口在小家电设备中的应用也越来越广泛。Type-C接口支持大电流宽电压范围&#xff0c;如何确保设备能够正确识别并使用各种电压&#xff08;例如5V、9V、12…

走向审计4.0:内部审计数字化转型的路径与方法【文末送书-34】

文章目录 走向审计4.0&#xff1a;内部审计数字化转型的路径与方法一、内部审计的发展阶段二、内部审计的逻辑架构三、内部审计数字化转型面临的问题四、内部审计数字化转型的框架方法五、内部审计的数字化转型能力体系六、内部审计的数字化转型路径七、内部审计的数字化系统平…

lqb省赛日志[2/37]

一只小蒟蒻备考蓝桥杯的日志 文章目录 笔记&#xff01;lqb不能用to_string和atoi历史遗留问题1 刷题心得小结 笔记 &#xff01;lqb不能用to_string和atoi 有替代方法 参考 不使用C 11的整数转字符串 C语言提供了一种方法。 #include sstream &#xff08;我没学&#xff0…

社区服务类创业项目推荐:抓住社区商业新机遇

大家好&#xff0c;我是一名90后鲜奶吧创业者&#xff0c;目前在社区经营5年时间&#xff0c;今天我想和大家分享一些关于社区服务类创业项目的推荐&#xff0c;都是这么多年我见证过生意最好的店面。 1、社区便利店&#xff1a; 随着人们生活节奏的加快&#xff0c;对便利购…

【论文阅读】TensoRF: Tensorial Radiance Fields 张量辐射场

发表于ECCV2022. 论文地址&#xff1a;https://arxiv.org/abs/2203.09517 源码地址&#xff1a;https://github.com/apchenstu/TensoRF 项目地址&#xff1a;https://apchenstu.github.io/TensoRF/ 摘要 本文提出了TensoRF&#xff0c;一种建模和重建辐射场的新方法。不同于Ne…

鸿蒙Harmony应用开发—ArkTS声明式开发(通用属性:菜单控制)

为组件绑定弹出式菜单&#xff0c;弹出式菜单以垂直列表形式显示菜单项&#xff0c;可通过长按、点击或鼠标右键触发。 说明&#xff1a; 从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 CustomBuilder里不支持再使用bind…

【前端】-初始前端以及html的学习

&#x1f496;作者&#xff1a;小树苗渴望变成参天大树&#x1f388; &#x1f389;作者宣言&#xff1a;认真写好每一篇博客&#x1f4a4; &#x1f38a;作者gitee:gitee✨ &#x1f49e;作者专栏&#xff1a;C语言,数据结构初阶,Linux,C 动态规划算法&#x1f384; 如 果 你 …

华为---MSTP(一)---MSTP生成树协议

目录 1. MSTP技术产生背景 2. STP/RSTP的缺陷 ​编辑 2.1 无法均衡流量负载 2.2 数据使用次优路径 3. MSTP生成树协议 3.1 MSTP相关概念 3.2 MSTP树生成的形成过程 4. MSTP报文 1. MSTP技术产生背景 RSTP在STP基础上进行了改进&#xff0c;实现了网络拓扑快速收敛。但…

【UE5】游戏框架GamePlay

游戏框架 游戏 由 游戏模式(GameMode) 和 游戏状态(GameState) 所组成 加入游戏的 人类玩家 与 玩家控制器(PlayerController) 相关联 玩家控制器允许玩家在游戏中拥有 HUD&#xff0c;这样他们就能在关卡中拥有物理代表 玩家控制器还向玩家提供 输入控制&#xff08;Input…

unity-urp:视野雾

问题背景 恐怖游戏在黑夜或者某些场景下&#xff0c;需要用雾或者黑暗遮盖视野&#xff0c;搭建游戏氛围 效果 场景中&#xff0c;雾会遮挡场景和怪物&#xff0c;但是在玩家视野内雾会消散&#xff0c;距离玩家越近雾越薄。 当前是第三人称视角&#xff0c;但是可以轻松的…

AWS ECR(AWS云里面的docker镜像私库)

问题 上一篇文章&#xff0c;在AWS云上面部署了k8s集群&#xff0c;这次接下来&#xff0c;需要在一个docker镜像私库。 步骤 创建docker镜像私库 打开AWS ECR主页&#xff0c;创建一个docker镜像私库&#xff0c;如下图&#xff1a; 设置私有镜像库名称&#xff0c;直接创…

【译】WordPress Bricks主题安全漏洞曝光,25,000个安装受影响

WordPress的Bricks主题存在一个严重的安全漏洞&#xff0c;恶意威胁行为者正在积极利用该漏洞在易受攻击的安装上运行任意PHP代码。 该漏洞被跟踪为CVE-2024-25600&#xff08;CVSS评分&#xff1a;9.8&#xff09;&#xff0c;使未经身份验证的攻击者能够实现远程代码执行。它…

鸿蒙 Stage模型-AbilityStage、Context、Want

前提&#xff1a;基于官网3.1/4.0文档。参考官网文档 基于Android开发体系来进行比较和思考。&#xff08;或有偏颇&#xff0c;自行斟酌&#xff09; 一、 AbilityStage 1.概念 AbilityStage是一个Module级别的组件容器&#xff0c;应用的HAP在首次加载时会创建一个AbilitySt…

Vue3 配置 vite.config.js 解决跨域问题

Vue3 配置 vite.config.js 解决跨域问题 问题再现 Access to XMLHttpRequest at ‘http://localhost:8080/user/register’ from origin ‘http://localhost:5173’ has been blocked by CORS policy: No ‘Access-Control-Allow-Origin’ header is present on the requested…

人工智能在日常生活中的应用

在我们的日常生活中&#xff0c;人工智能已经成为一种无处不在的力量&#xff0c;从智能家居到在线助手&#xff0c;再到高度个性化的服务和推荐&#xff0c;它无声地改变着我们的生活方式和习惯。随着技术的不断进步和普及&#xff0c;人工智能正以前所未有的速度和规模渗透到…

多线程系列(十二) -生产者和消费者模型

一、简介 在 Java 多线程编程中&#xff0c;还有一个非常重要的设计模式&#xff0c;它就是&#xff1a;生产者和消费者模型。 这种模型可以充分发挥 cpu 的多线程特性&#xff0c;通过一些平衡手段能有效的提升系统整体处理数据的速度&#xff0c;减轻系统负载&#xff0c;提…

http【详解】状态码,方法,接口设计 —— RestfuI API,头部 —— headers,缓存

http 状态码 1xx 服务器收到请求 2xx 请求成功 200 成功 3xx 重定向&#xff08;目标服务器返回另一个服务器的地址&#xff0c;浏览器会自动去访问另一个服务器&#xff09; 常见应用场景&#xff1a;搜索引擎&#xff0c;短网址 301 永久重定向 &#xff08;常用于已停服的…