## 数据结构测试题

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的倍数。

``````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.志愿者选拔

``````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.单词接龙

``````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()
}``````
##### 4.对称二叉树

``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.英雄南昌欢迎您

``````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.时间转换

``0``

``0:0:0``

``5436``

``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.矩阵乘法

例如：

A =

1 2

3 4

A的2次幂

7 10

15 22

``````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。

``````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;
}``````

### 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…

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

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

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

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

### 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…

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

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