swust oj计算机大类专业数据结构上半期实验练习题
有些实验考试数据会有问题
941: 有序顺序表的合并操作的实现
题目描述
已知两非递减的顺序线性表，要求合并成一个新的非递减顺序线性表。(测试数据为整型)
输入
输入包含四行，第一行为自然数n，表示第一个非递减顺序线性表的长度; 第二行为n个自然数构成的非递减顺序线性表; 第三行为自然数m，表示第二个非递减顺序线性表的长度; 第四行为m个自然数构成的非递减顺序线性表。
输出
输出：用一行输出合并后的非递减顺序线性表，各数之间用一个空格隔开。
样例输入
2 1 3 3 2 3 6
样例输出
1 2 3 3 6
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++)cin>>a[i];
cin>>m;
vector<int>b(m);
vector<int>c(n+m);
for(int i=0;i<m;i++)cin>>b[i];
for(int i=0;i<n;i++)c[i]=a[i];
for(int i=0;i<m;i++)c[i+n]=b[i];
sort(c.begin(),c.end());
for(int i=0;i<n+m;i++)cout<<c[i]<<" ";
}943: 顺序表插入操作的实现
题目描述
建立长度为n的顺序表，在指定的数据元素item之前插入数据元素data。如果指定的数据元素item不存在，则将data插入到顺序表的尾端。（数据类型为整型）
输入
第一行为顺序表的长度n； 第二行为顺序表中的数据元素； 第三行为指定的数据元素item； 第四行为要插入的数据元素data；
输出
输出结果为顺序表中的数据元素。
样例输入
10 10 20 30 40 50 60 70 80 90 100 50 55
样例输出
10 20 30 40 55 50 60 70 80 90 100
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
int b;
cin>>b;
int c;
cin>>c;
auto it=find(a.begin(),a.end(),b);
if(it!=a.end())a.insert(it,c);
else a.insert(a.end(),c);
for(int i=0;i<n+1;i++){
cout<<a[i]<<" ";
}
}952: 单链表的插入操作的实现
题目描述
建立长度为n的单链表，在第i个结点之前插入数据元素data。
输入
第一行为自然数n，表示链式线性表的长度； 第二行为n个自然数表示链式线性表各元素值； 第三行为指定插入的位置i；第四行为待插入数据元素data。
输出
指定插入位置合法时候，输出插入元素后的链式线性表的所有元素，元素之间用一个空格隔开。输入不合法，输出"error!"。
样例输入
5 1 2 3 4 5 3 6
样例输出
1 2 6 3 4 5
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
int index,m;
cin>>index;
cin>>m;
if(index<1||index>=n+1){
cout<<"error!";
return 0;
}
a.insert(a.begin()+index-1,m);
for(int i=0;i<a.size();i++)cout<<a[i]<<" ";
}953: 单链表的删除操作的实现
题目描述
建立长度为n的单链表，删除第i个结点之前的结点。
输入
第一行为自然数n，表示链式线性表的长度； 第二行为n个自然数表示链式线性表各元素值； 第三行为指定的删除参数i。
输出
指定删除位置合法时候，输出删除元素后的链式线性表的所有元素，元素之间用一个空格隔开。 输入不合法，输出"error!"。
样例输入
5 1 2 3 4 5 3
样例输出
1 3 4 5
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
int index;
cin>>index;
if(index<2||index>n+1){
cout<<"error!";
return 0;
}
a.erase(a.begin()+index-2);
for(int i=0;i<a.size();i++)cout<<a[i]<<" ";
}954: 单链表的链接
题目描述
建立长度为n的单链表A和长度为m的单链表B。编程实现将B表链接在A表的尾端，形成一个单链表A。数据类型指定为字符型。
输入
第一行为A表的长度n； 第二行为A表中的数据元素; 第三行为B表的长度m； 第四行为B表中的数据元素。
输出
输出为链接好后的A表中的所有数据元素。
样例输入
4 A B C D 6 1 2 3 4 5 6
样例输出
A B C D 1 2 3 4 5 6
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<char>a(n);
for(int i=0;i<n;i++)cin>>a[i];
int m;
cin>>m;
vector<char>b(m);
for(int i=0;i<m;i++)cin>>b[i];
vector<char> c(a.begin(), a.end());
c.insert(c.end(), b.begin(), b.end());
for(int i=0;i<m+n;i++)cout<<c[i]<<" ";
}956: 约瑟夫问题的实现
题目描述
n个人围成一个圈，每个人分别标注为1、2、...、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即为胜利者。例如当n=10,k=4时，依次出列的人分别为4、8、2、7、3、10，9、1、6、5，则5号位置的人为胜利者。给定n个人，请你编程计算出最后胜利者标号数。（要求用单循环链表完成。）
输入
第一行为人数n; 第二行为报数k。
输出
输出最后胜利者的标号数。
样例输入
10 4
样例输出
5
#include <bits/stdc++.h>
using namespace std;
int findWinner(int n, int k) {
vector<int> people(n);
for (int i = 0; i < n; ++i) {
people[i] = i + 1;
}
int currentIndex = 0;
while (n > 1) {
currentIndex = (currentIndex + k - 1) % n;
people.erase(people.begin() + currentIndex);
n--;
}
return people[0];
}
int main() {
int n, k;
cin >> n >> k;
cout << findWinner(n, k);
return 0;
}957: 逆置单链表
题目描述
建立长度为n的单链表，然后将其数据元素逆置，即第1个元素变为最后一个元素，第2个元素变为倒数第2个元素，以此类推，最后一个元素变为第1个元素。（处理的数据类型为字符型。必须使用链表完成。）
输入
第一行为链表长度n； 第二行为链表中的n个数据元素的值。
输出
逆置后的原始的值。
样例输入
10 ABCDEFGHIJ
样例输出
J I H G F E D C B A
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<char>a(n);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=n-1;i>=0;i--)cout<<a[i]<<" ";
}960: 双向链表的操作问题
题目描述
建立一个长度为n的带头结点的双向链表，使得该链表中的数据元素递增有序排列。（必须使用双向链表完成，数据类型为整型。）
输入
第一行：双向表的长度； 第二行：链表中的数据元素。
输出
输出双向链表中的数据元素的值。
样例输入
10 2 4 6 3 5 8 10 21 12 9
样例输出
2 3 4 5 6 8 9 10 12 21
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++)cin>>a[i];
sort(a.begin(),a.end());
for(int i=0;i<n;i++)cout<<a[i]<<" ";
}961: 进制转换问题
题目描述
建立顺序栈或链栈，编写程序实现十进制数到二进制数的转换。
输入
输入只有一行，就是十进制整数。
输出
转换后的二进制数。
样例输入
10
样例输出
1010
#include<stdio.h>
void fact(int n){
int arry[32]={0};
int i=0;
if(n==0){
printf("0");
return;
}
while(n>0){
arry[i]=n%2;
n=n/2;
i++;
}
for(int j=i-1;j>=0;j--)printf("%d",arry[j]);
}
int main(){
int n;
scanf("%d",&n);
fact(n);
}962: 括号匹配问题
题目描述
假设表达式中允许包含两种括号:圆括号和方括号。编写一个算法判断表达式中的括号是否正确配对。
输入
由括号构成的字符串，包含”（“、”）“、”[“和”]“。
输出
如果匹配输出YES，否则输出NO。
样例输入
[([][]())]
样例输出
YES
#include<bits/stdc++.h>
using namespace std;
int main(){
stack<char>a;
char ch;
while(cin>>ch){
if(ch=='('||ch=='['||a.empty())a.push(ch);
else if(ch==')'&&a.top()=='(')a.pop();
else if(ch==']'&&a.top()=='[')a.pop();
}
if(a.empty())cout<<"YES";
else cout<<"NO";
} 964: 数细胞
#include<bits/stdc++.h>
using namespace std;
int n,m,g[10000][10000];
void dfs(int x,int y){
g[x][y]=0;
if(g[x+1][y]!=0)dfs(x+1,y);
if(g[x-1][y]!=0)dfs(x-1,y);
if(g[x][y+1]!=0)dfs(x,y+1);
if(g[x][y-1]!=0)dfs(x,y-1);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)cin>>g[i][j];
}
int sum=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]!=0){
dfs(i,j);
sum++;
}
}
}
cout<<sum;
}965: 循环队列
题目描述
根据给定的空间构造顺序循环队列，规定队满处理方法为少用一个元素空间。例如，给定5个元素空间构造循环队列，则只能存放4个元素。试根据入队及出队操作判断队列最后的元素存放情况，并输出最后队列中的元素值，即完成给定入队及出列操作后一次性全部出队的元素值。要求采用顺序队列完成，少用一个存储空间的方法区分队列的空和满。
输入
输入的第一行为一个自然数n，表示要求构造的顺序循环队列空间数。 第二行为操作次k，接下来k行为出队入队操作，每行各代表一次操作。入队用in表示，出队用out表示，如果是入队，则in隔一空格后为一整数，表示入队元素值。
输出
输出完成所有入队出队操作后，一次性出队元素。用一个空格隔开。可以假定队在完成所有操作后不为空。
样例输入
4 7 in 1 in 2 in 5 in 6 out out in 8
样例输出
5 8
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
queue<int>a;
int num;
cin>>num;
while(num--){
string ch;
cin>>ch;
if(ch=="in"){
int b;
cin>>b;
if(a.size()!=n-1)a.push(b);
}
if(!a.empty()&&ch=="out")a.pop();
}
while(!a.empty()){
cout<<a.front()<<" ";
a.pop();
}
} 971: 统计利用先序遍历创建的二叉树的深度
题目描述
利用先序递归遍历算法创建二叉树并计算该二叉树的深度。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树的深度（使用二叉树的后序遍历算法）。需要注意输入数据序列中的"#"字符和非"#"字符的序列及个数关系，这会最终决定创建的二叉树的形态。
输入
输入为先序遍历二叉树结点序列。
输出
对应的二叉树的深度。
样例输入
A## ABC#### AB##C## ABCD###E#F##G## A##B##
样例输出
1 3 2 4 1
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
char data;
struct node*lchild,*rchild;
}*bitree,binode;
void createbitree(bitree &t){
char ch;
cin>>ch;
if(ch=='#')t=NULL;
else{
t=new binode;
t->data=ch;
createbitree(t->lchild);
createbitree(t->rchild);
}
}
int depth(bitree t){
if(t==NULL)return 0;
else {
int i=depth(t->lchild);
int j=depth(t->rchild);
return i>j?i+1:j+1;
}
}
int main(){
bitree t;
createbitree(t);
cout << depth(t);
}972: 统计利用先序遍历创建的二叉树的宽度
输出
输出该用例对应的二叉树的宽度。
样例输入
A## ABC#### AB##C## ABCD###EF##G### A##B##
样例输出
1 1 2 3 1
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
char data;
struct node*lchild,*rchild;
}*bitree,binode;
void createbitree(bitree &t){
char ch;
cin>>ch;
if(ch=='#')t=NULL;
else{
t=new binode;
t->data=ch;
createbitree(t->lchild);
createbitree(t->rchild);
}
}
int getWidth(bitree t){
if(t==NULL)return 0;
queue<bitree>q;
q.push(t);
int max_width=0;
while(!q.empty()){
int size=q.size();
max_width=max(max_width,size);
for(int i=0;i<size;i++){
bitree node=q.front();
q.pop();
if(node->lchild)q.push(node->lchild);
if(node->rchild)q.push(node->rchild);
}
}
return max_width;
}
int main(){
bitree t;
createbitree(t);
cout<<getWidth(t);
return 0;
}975: 统计利用先序遍历创建的二叉树的度为2的结点个数
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
char data;
struct node *lchild,*rchild;
}*bitree,binode;
void createbitree(bitree &t){
char ch;
cin>>ch;
if(ch=='#')t=NULL;
else{
t=new binode;
t->data=ch;
createbitree(t->lchild);
createbitree(t->rchild);
}
}
int num=0;
void tj(bitree t){
if(t){
tj(t->lchild);
tj(t->lchild);
if(t->lchild&&t->rchild)num++;
}
}
int main(){
bitree t;
createbitree(t);
tj(t);
cout<<num;
}1027: 舞伴问题
题目描述
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。要求编写程序实现舞伴问题。
输入
输入一共5行，第一行是男生人数m；第二行依次是男生的姓名；第三行是女士的人数n；第四行依次是女士的姓名；第五行是跳舞的轮数。
输出
配对的男士和女士的姓名。
样例输入
5 A B C D E 3 F G H 2
样例输出
B G
#include <bits/stdc++.h>
using namespace std;
int main() {
int m, n, rounds;
cin >> m;
vector<string> boys(m);
for (int i = 0; i < m; ++i) {
cin >> boys[i];
}
cin >> n;
vector<string> girls(n);
for (int i = 0; i < n; ++i) {
cin >> girls[i];
}
cin >> rounds;
int i = 0, j = 0;
for (int currentRound = 0; currentRound < rounds; ++currentRound) {
if (currentRound == rounds - 1) {
cout << boys[i] << " ";
cout << girls[j] ;
}
i = (i + 1) % m;
j = (j + 1) % n;
}
return 0;
}1028: 特定字符序列的判断
题目描述
编写一程序，识别依次读入的一个以“#”为结束符的字符序列是否为形如“序列1@序列2”模式的字符序列。期中序列1和序列2中都不含字符“@”，且序列2是序列1的逆序列。例如“a+b@b+a”是满足条件的序列字符，而“1+3@3-1”则不是。
输入
一个以“#”结束的字符序列。
输出
是满足条件的字符序列输出“yes!”；否则输出“no!”。
样例输入
a+b@b+a#
样例输出
yes!
#include<stdio.h>
#include<string.h>
int main() {
char a[1001];
char b[1001];
for (int i = 0; i < 1001; i++) {
scanf("%c", &a[i]);
if (a[i] == '@') {
a[i] = '\0';
break;
}
}
for (int i = 0; i < 1001; i++) {
scanf("%c", &b[i]);
if (b[i] == '#') {
b[i] = '\0';
break;
}
}
int lena = strlen(a);
int lenb = strlen(b);
if (lena != lenb) {
printf("no!");
return 0;
}
for (int i = 0; i < lena; i++) {
if (a[i] != b[lena - i - 1]) {
printf("no!");
return 0;
}
}
printf("yes!");
return 0;
}1036: 寻找整数序列的主元素
题目描述
已知一个整数序列A=（a0，a1，…an），如果其中有一个元素的出现次数超过n/2，就称该元素为A的主元素，否则就称整数序列没有主元素。例如A=（0，5，5，3，5，7，5，5），则5为主元素。A=（0，5，5，3，5，1，5，7），则A中没有主元素。要求编写程序实现寻找给定整数序列的主元素，如果找到，则输出主元素。如果没有找到，则输出-1。
输入
第一行为整数序列的个数n 第二行为一个整数序列。
输出
如果找到主元素，输出主元素的值，否则输出-1。
样例输入
8 0 5 5 3 5 7 5 5
样例输出
5
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int>a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
unordered_map<int, int> freq;
for (int i = 0; i < n; i++) {
freq[a[i]]++;
}
for (auto it = freq.begin(); it != freq.end(); it++) {
if (it->second > n / 2) {
cout << it->first;
return 0;
}
}
cout << -1;
return 0;
}1038: 顺序表中重复数据的删除
题目描述
将存储在顺序表中的长度为n的线性表中指定的数据全部删除。
输入
第一行为顺序表的长度n； 第二行为顺序表中的数据元素； 第三行为指定要删除的元素值。
输出
如果表不空，输出删除指定值后的线性表；如果删除后表空，则输出-1。
样例输入
8 11 22 33 44 44 55 44 66 44
样例输出
11 22 33 55 66
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++)cin>>a[i];
int b;
cin>>b;
a.erase(remove(a.begin(), a.end(), b), a.end());
if(a.empty())cout<<-1;
else {
for(int i=0;i<a.size();i++)cout<<a[i]<<" ";
}
}1042: 中缀表达式转换为后缀表达式
题目描述
中缀表达式是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) * 3 ， 即2 1 + 3 *。利用栈结构，将中缀表达式转换为后缀表达式。(测试数据元素为单个字符)
输入
中缀表达式
输出
后缀表达式
样例输入
A+(B-C/D)*E
样例输出
ABCD/-E*+
#include<bits/stdc++.h>
using namespace std;
int main(){
string a,b;
cin>>a;
stack<char>s;
for(int i=0;i<a.size();i++){
if(a[i]!='+'&&a[i]!='-'&&a[i]!='/'&&a[i]!='*'&&a[i]!='('&&a[i]!=')'){
b+=a[i];
}
else if(a[i]=='(')s.push(a[i]);
else if(a[i]==')'){
while(s.top()!='('){
char ch=s.top();
s.pop();
b+=ch;
}
s.pop();
}
else{
if(s.empty()||((s.top()=='+'||s.top()=='-')&&(a[i]=='*'||a[i]=='/'))){
s.push(a[i]);
}
else{
while(!s.empty()&&(s.top()=='*'||s.top()=='/')){
char ch=s.top();
s.pop();
b+=ch;
}
s.push(a[i]);
}
}
}
while(!s.empty()){
char ch=s.top();
s.pop();
b+=ch;
}
cout<<b;
return 0;
}1043: 利用栈完成后缀表达式的计算
题目描述
后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) * 3 ， 即2 1 + 3 *。利用栈结构，将后缀表达式的结果计算出来。
输入
后缀表达式。以#号作为表达式结束标志。为了简单，处理的数据为0-9的整数。
输出
计算结果。
样例输入
3 6 6 2 / - 3 * +#
样例输出
12
#include<bits/stdc++.h>
using namespace std;
int main(){
stack<int>stk;
char ch;
while(cin>>ch){
if(ch=='#')break;
if(ch>='0'&&ch<='9')stk.push(ch-'0');
else{
int a=stk.top();
stk.pop();
int b=stk.top();
stk.pop();
if(ch=='+')stk.push(b+a);
if(ch=='-')stk.push(b-a);
if(ch=='*')stk.push(b*a);
if(ch=='/')stk.push(b/a);
}
}
cout<<stk.top();
}1046: 链栈基本操作的实现
题目描述
编程实现链栈的初始化、入栈、出栈和计算栈中元素个数等基本操作。（测试数据为整数。）
输入
第一行为入栈元素的个数; 第二行为入栈元素； 出栈操作的次数n.
输出
n次出栈后的栈顶元素。如果是空栈，输出-1.
样例输入
4 1 2 3 4 2
样例输出
2
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
stack<int>a;
for(int i=0;i<n;i++){
int x;
cin>>x;
a.push(x);
}
int num;
cin>>num;
for(int i=0;i<num&&!a.empty();i++)a.pop();
//a.empty()非常重要！！
if(!a.empty())cout<<a.top();
else cout<<"-1";
} 1231: 寻找出现次数最多的数
题目描述
给定n个正整数，找出它们中出现次数最多的数。如果这样的数有多个，请输出其中最小的一个。
输入
输入的第一行只有一个正整数n(1 ≤ n ≤ 1000)，表示数字的个数。输入的第二行有n个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。相邻的数用空格分隔。
输出
输出这n个次数中出现次数最多的数。如果这样的数有多个，输出其中最小的一个。
样例输入
6 10 1 10 20 30 20
样例输出
10
#include<bits/stdc++.h>
using namespace std;
int a[1000001],b[1000001];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=1;i<=1000001;i++){
int sum=0;
for(int j=0;j<n;j++){
if(a[j]==i)sum++;
}
b[i]=sum;
}
int max=0;
for(int i=0;i<=1000001;i++){
if(b[i]>=max)max=b[i];
}
for(int i=0;i<=1000001;i++){
if(b[i]==max){
cout<<i;
return 0;
}
}
}1102: 顺序表上数据的划分问题的实现
题目描述
建立一个顺序表L，然后以第一个为分界，将所有小于等于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。
输入
顺序表长度n； 顺序表中的数据元素。
输出
移动后的数据元素。
样例输入
10 32 5 22 43 23 56 54 57 11 25
样例输出
25 11 23 22 5 32 43 56 54 57
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++)cin>>a[i];
stack<int>b;
vector<int>c;
for(int i=1;i<n;i++){
if(a[i]>a[0])c.push_back(a[i]);
else if(a[i]<=a[0])b.push(a[i]);
}
while(!b.empty()){
cout<<b.top()<<" ";
b.pop();
}
cout<<a[0]<<" ";
for(int i=0;i<c.size();i++)cout<<c[i]<<" ";
}
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
10
0- 0
已为社区贡献1条内容
所有评论(0)