数据结构复习部分机考题-自用
?A.二叉树孩子链表法之找家人
题目描述
给出二叉树的孩子链表表示法，根据输入要求，找指定结点的双亲或孩子
输入
第一行输入两个参数，第一个参数n表示树有n个结点，第二个参数r表示根结点的数组下标
接着n行，每行先输入一个结点的数值（用单个字母表示），再输入结点的孩子下标（先左后右），如果只有一个孩子默认是左孩子，最后以-1结尾
如果该结点没有孩子，则一行只输入结点的数值和-1
接着输入t表示有t个结点要找家人
接着t行，每行输入两个参数，第1个参数是结点的数值，第2个参数是一个数字，其中0表示找双亲，1表示找左孩子，2表示找右孩子；
输出
输出t行，每行输出指定结点的双亲数值或孩子数值
每行输出一个数值，如果指定结点没有双亲或者没有孩子，则输出@
样例查看模式?
正常显示查看格式
输入样例1?
10?4\n
A?3?5?-1\n
B?2?9?-1\n
C?6?-1\n
D?-1\n
R?0?1?-1\n
E?-1\n
F?7?8?-1\n
G?-1\n
H?-1\n
K?-1\n
4\n
G?0\n
R?1\n
C?2\n
R?0\n
输出样例1
F\n
A\n
@\n
@\n
AC代码
#include<iostream>
#include<queue>
#include<map>
using namespace std;
struct node
{
char data;
vector<char>child;
};
class tree
{
int n;
int root;
vector<node>v;
map<char, int>mp;
map<int, char>mm;
public:
tree()
{
cin >> n >> root;
v.resize(n);
for (int i = 0; i < n; i++)
{
char ch;
cin >> ch;
v[i].data = ch;
mp[ch] = i;
mm[i] = ch;
int x;
cin >> x;
while (x != -1)
{
v[i].child.push_back(x);
cin >> x;
}
}
}
void check()
{
int m;
cin >> m;
while (m--)
{
char ch;
int op;
cin >> ch >> op;
if (op == 1)
{
if (v[mp[ch]].child.size() == 0)
{
cout << "@" << endl;
}
else
{
cout << mm[v[mp[ch]].child[0]] << endl;
}
}
else if (op == 2)
{
if (v[mp[ch]].child.size() < 2)
{
cout << "@" << endl;
}
else
{
cout << mm[v[mp[ch]].child[1]] << endl;
}
}
else
{
int id = mp[ch];
bool ok = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < v[i].child.size(); j++)
{
if (v[i].child[j] == id)
{
ok = 1;
cout << v[i].data << endl;
break;
}
}
if (ok)break;
}
if (!ok)cout << "@" << endl;
}
}
}
};
int main()
{
tree t;
t.check();
return 0;
}B.DS二叉树双亲表示法之找左叶子
题目描述
给出一棵二叉树的双亲表示法结果，用一个二维数组表示，位置下标从0开始，如果双亲位置为-1则表示该结点为根结点
如果结点有孩子，那么孩子的数组下标为奇数，则表示该孩子是左孩子，如果孩子的数组下标为偶数，则表示该孩子是右孩子（0算偶数）
编写程序，找出这棵树的所有左叶子。按照数组下标的顺序输出
输入
第一个输入t，表示有t棵树
接着每棵树输入3行：
第1行输入n，表示树有n个结点
第2行输入n个英文字母，表示每个树结点的数值
第3行输入n个整数，表示每个结点的双亲在数组的下标
以此类推输入下一棵树
输出
共输出t行，每行输出一棵二叉树的所有左叶子，按数组下标顺序输出
每行输出的每个叶子后面都带一个空格，最后一个也带空格
样例查看模式?
正常显示查看格式
输入样例1
2\n
7\n
A?B?C?D?E?F?G\n
-1?0?0?1?1?3?3\n
10\n
A?B?C?D?R?E?F?G?H?K\n
4?4?0?0?-1?1?2?2?6?7\n
输出样例1
F?\n
D?E?K?\n
AC代码
#include<iostream>
#include<queue>
#include<map>
#include<list>
using namespace std;
struct node
{
char data;
list<int>child;
int fa;
node()
{
data = '0';
fa = -1;
}
};
class tree
{
int n;
int root;
vector<node>v;
map<char, int>mp;
map<int, char>mm;
public:
tree()
{
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++)
{
cin >> v[i].data;
mp[v[i].data] = i;
mm[i] = v[i].data;
}
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
if (x == -1)
{
root = i;
}
else
{
v[i].fa = x;
v[x].child.push_back(i);
}
}
}
void show()
{
for (int i = 0; i < n; i++)
{
cout << v[i].data << ":";
for (auto tt:v[i].child)
{
cout << mm[tt] << " ";
}
cout << endl;
}
}
void check()
{
for (int i = 0; i < n; i++)
{
int ss = v[i].child.size();
if (ss == 0)
{
continue;
}
else
{
int tt = v[i].child.front();
if (v[tt].child.size() == 0)
{
cout << mm[tt] << " ";
}
}
}
cout << endl;
}
};
int main()
{
int tt;
cin >> tt;
while (tt--)
{
tree t;
t.show();
t.check();
}
return 0;
}C.DS二叉树--基于数组存储的构建
题目描述
任意二叉树可以根据完全二叉树性质保存在一个数组中。已知二叉树的数组存储，用程序构建该二叉树。
提示：用递归方法或非递归都可以
输入
第一行输入一个整数t，表示有t个测试数据
第二行起输入二叉树的数组存储结果，空树用字符‘0’表示，输入t行
数组的数据由大写字母和0表示
输出
逐行输出每个二叉树的先序遍历结果
样例查看模式?
正常显示查看格式
输入样例1?
3\n
ABC0D\n
ABCDEF000G\n
ABEC0F0D0\n
输出样例1
ABDC\n
ABDEGCF\n
ABCDEF\n
AC代码
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<list>
using namespace std;
class tree
{
string s;
public:
tree()
{
cin >> s;
}
void pre(int x=0)
{
if (x >= s.size() || s[x] == '0')return;
cout << s[x];
pre(2 * x + 1);
pre(2 * x + 2);
}
};
int main()
{
int tt;
cin >> tt;
while (tt--)
{
tree t;
t.pre(0);
cout << endl;
}
return 0;
}D. DS二叉树--赫夫曼树的构建与编码
题目描述
给定n个权值，根据这些权值构造huffman树，并进行huffman编码
大家参考课本算法6.12为主，注意数组访问是从位置1开始
要求：赫夫曼的构建中，默认左孩子权值不大于右孩子权值
输入
第一行先输入n，表示有n个权值，即有n个叶子
第二行输入n个权值，权值全是小于1万的正整数
输出
逐行出每个权值对应的编码，格式如下：权值-编码
即每行先输出1个权值，再输出一个短划线，再输出对应编码
接着下一行输出下一个权值和编码，以此类推
样例查看模式?
正常显示查看格式
输入样例1?
5\n
15?4?4?3?2\n
输出样例1
15-1\n
4-010\n
4-011\n
3-001\n
2-000\n
AC代码
#include<iostream>
using namespace std;
struct node
{
int weight;
int l, r, p;
string code;
node()
{
weight = 0;
l = r = p = 0;
}
};
class tree
{
node* root;
int n;
public:
tree()
{
cin >> n;
root = new node[2*n+2];
//从1开始，下标不会为0，与双亲冲突
for (int i = 1; i <= n; i++)
{
cin >> root[i].weight;
}
}
void findmin(int len, int& p1, int& p2)
{
int min1 = 0x3f;
int min2 = 0x3f;
for (int i = 1; i < len; i++)
{
//注意是独立的树！
if (root[i].p == 0)
{
if (root[i].weight < min1)
{
min2 = min1;
p2 = p1;
min1 = root[i].weight;
p1 = i;
}
else if (root[i].weight < min2)
{
min2 = root[i].weight;
p2 = i;
}
}
}
}
void hatree()
{
int p1 = 0, p2 = 0;
for (int i = n+1; i < 2 * n; i++)
{
findmin(i, p1, p2);
root[i].l = p1;
root[i].r = p2;
root[p1].p = i;
root[p2].p = i;
root[i].weight = root[p1].weight + root[p2].weight;
}
}
void hacode()
{
for (int i = 1; i <= n; i++)
{
for (int c = i, f = root[i].p; f != 0; c = f, f = root[f].p)
{
if (root[f].l == c)
{
(root + i)->code = '0' + (root + i)->code;
}
else
{
(root + i)->code = '1' + (root + i)->code;
}
}
}
}
void show()
{
for (int i = 1; i <= n; i++)
{
cout << root[i].weight <<"-" << root[i].code << endl;
}
}
};
int main()
{
tree t;
t.hatree();
t.hacode();
t.show();
return 0;
}E. DS图—最小生成树
题目描述
根据输入创建无向网。分别用Prim算法和Kruskal算法构建最小生成树。（假设：输入数据的最小生成树唯一。）
输入
顶点数n
n个顶点
边数m
m条边信息,格式为：顶点1顶点2权值
Prim算法的起点v
输出
输出最小生成树的权值之和
对两种算法，按树的生长顺序，输出边信息(Kruskal中边顶点按数组序号升序输出)
样例查看模式?
正常显示查看格式
输入样例1
6\n
v1?v2?v3?v4?v5?v6?\n
10\n
v1?v2?6\n
v1?v3?1\n
v1?v4?5\n
v2?v3?5\n
v2?v5?3\n
v3?v4?5\n
v3?v5?6\n
v3?v6?4\n
v4?v6?2\n
v5?v6?6\n
v1\n
输出样例1
15\n
prim:\n
v1?v3?1\n
v3?v6?4\n
v6?v4?2\n
v3?v2?5\n
v2?v5?3\n
kruskal:\n
v1?v3?1\n
v4?v6?2\n
v2?v5?3\n
v3?v6?4\n
v2?v3?5\n
AC代码
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1000, inf = 0x3f3f3f;
int g[N][N];
int n, m;
map<string, int>mp;
map<int, string>mm;
struct node
{
int u, v, w;
};
vector<node>edge;
vector<node>edges;
int fa[N];
bool cmp(const node& a, const node& b)
{
return a.w < b.w;
}
void Prim(int x)
{
int len = inf;
int end = 0;
int sum = 0;
int k = 0;
vector<node>temp(n + 1);
//temp[i].u表:i点连接u点
//temp[i].w表:i到u的距离
for (int i = 1; i <= n; i++)
{
temp[i].u = x;
temp[i].w = g[x][i];
}
temp[x].w = 0;
for (int i = 1; i < n; i++)
{
len = inf;
//找到x到某点j的最小距离
for (int j = 1; j <= n; j++)
{
if (temp[j].w && temp[j].w < len)
{
len = temp[j].w;
end = j;
}
}
sum += len;
//更新添加记录边
edge[k].u = temp[end].u;
edge[k].v = end;
edge[k].w = len;
k++;
//加入后更新
for (int j = 1; j <= n; j++)
{
if (temp[j].w && temp[j].w > g[end][j])
{
temp[j].w = g[end][j];
temp[j].u = end;
}
}
temp[end].w = 0;
}
cout << sum << endl;
for (int i = 0; i < n - 1; i++)
{
cout << mm[edge[i].u] << " " << mm[edge[i].v] << " " << edge[i].w << endl;
}
}
int find(int x)
{
if (x != fa[x])fa[x] = find(fa[x]);
return fa[x];
}
void kuskal()
{
cout << "kruskal:" << endl;
for (int i = 0; i < m; i++)
{
int p1 = find(edges[i].u);
int p2 = find(edges[i].v);
if (p1 != p2)
{
fa[p1] = p2;
cout << mm[min(edges[i].u, edges[i].v)] << " "
<< mm[max(edges[i].u, edges[i].v)] << " "
<< edges[i].w << endl;
}
}
}
int main()
{
memset(g, inf, sizeof(g));
cin >> n;
for (int i = 1; i <= n; i++)
{
fa[i] = i;
string s;
cin >> s;
mp[s] = i;
mm[i] = s;
}
cin >> m;
edge.resize(m);
for (int i = 0; i < m; i++)
{
string s1, s2;
int c;
cin >> s1 >> s2 >> c;
g[mp[s1]][mp[s2]] =
g[mp[s2]][mp[s1]] = c;
edge[i].u = min(mp[s1], mp[s2]);
edge[i].v = max(mp[s1], mp[s2]);
edge[i].w = c;
}
sort(edge.begin(), edge.end(), cmp);
edges = edge;
string start;
cin >> start;
//Prim算法有起点
Prim(mp[start]);
kuskal();
return 0;
}F. 层次遍历叶子节点
题目描述
给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构，并层次遍历该二叉树的叶子节点
层次遍历是指从先从上往下，再从左到右的遍历二叉树节点
例如上图的遍历叶子的结果是D C
层次遍历二叉树算法如下，请改造成层次遍历叶子算法
初始设置：创建空队列Q，设T是根结点的指针，p是二叉树结点类型指针，初始操作时根结点T入队，执行以下循环：
(1)队首元素出队到p；
(2)访问p所指向的结点；（访问操作可以定义输出、比较、判断.......，根据题目要求来定义）?
(3)p所指向的结点的左、右子结点依次入队。
(4)跳转步骤1循环，直到队空为止
输入
第一行输入一个整数t，表示有t个二叉树
第二行起输入每个二叉树的包含空树的先序遍历结果，空树用字符‘0’表示，连续输入t行
输出
输出每个二叉树的叶子的层次遍历结果，
每行结果输出叶子的数值，并且用空格隔开，最后一个叶子输出后也带空格再换行
样例查看模式?
正常显示查看格式
输入样例1?<
2\n
AB0C00D00\n
ABD000C0E00\n
输出样例1
D?C?\n
D?E?
AC代码
#include<iostream>
#include<queue>
using namespace std;
struct node
{
char data;
node* l;
node* r;
node()
{
data = '0';
l = NULL;
r = NULL;
}
};
class tree
{
node* root;
int cnt;
void create(node*& root)
{
char x;
cin >> x;
if (x == '0')
{
root = NULL;
return;
}
root = new node;
root->data = x;
create(root->l);
create(root->r);
}
void post(node* root)
{
if (!root)
{
return;
}
post(root->l);
post(root->r);
cout << root->data;
}
void mid(node* root)
{
if (!root)
{
return;
}
mid(root->l);
cout << root->data;
mid(root->r);
}
void Delete(node* root)
{
if (!root)
{
delete root;
return;
}
Delete(root->l);
Delete(root->r);
delete root;
}
void child(node* root)
{
if (!root)
{
return;
}
if (!root->l && !root->r)
{
cout << root->data << " ";
}
child(root->l);
child(root->r);
}
void parent(node* root)
{
if (!root)
{
return;
}
parent(root->l);
parent(root->r);
if (root->l && !root->l->r && !root->l->l)
{
cout << root->data << " ";
}
if (root->r && !root->r->r && !root->r->l)
{
cout << root->data << " ";
}
}
public:
tree()
{
cnt = 0;
root = NULL;
}
void create_tree()
{
create(root);
}
~tree()
{
Delete(root);
}
void posorder()
{
post(root);
cout << endl;
}
void midorder()
{
mid(root);
cout << endl;
}
void find_child()
{
child(root);
cout << endl;
}
void find_parent()
{
parent(root);
cout << endl;
}
void lerver()
{
queue<node*>q;
q.push(root);
while (!q.empty())
{
auto t = q.front();
q.pop();
if (!t->l && !t->r)
{
cout << t->data << " ";
}
if (t->l)
{
q.push(t->l);
}
if (t->r)
{
q.push(t->r);
}
}
cout << endl;
}
};
int main()
{
int t;
cin >> t;
while (t--)
{
tree tt;
tt.create_tree();
tt.lerver();
}
return 0;
}G. DS线性表—多项式相加
时间限制1s
内存限制128MB
题目描述
对于一元多项式p(x)=p0+p1x+p2x2+…+pnxn，每个项都有系数和指数两部分，例如p2x2的系数为p2,指数为2。
编程实现两个多项式的相加。
例如5+x+2x2+3x3，-5-x+6x2+4x4，两者相加结果：8x2+3x3+4x4
其中系数5和-5都是x的0次方的系数，相加后为0，所以不显示。x的1次方同理不显示。
要求用单链表实现。
输入
第1行：输入t表示有t组测试数据
第2行：输入n表示有第1组的第1个多项式包含n个项
第3行：输入第一项的系数和指数，以此类推输入n行
接着输入m表示第1组的第2个多项式包含m项
同理输入第2个多项式的m个项的系数和指数
参考上面输入第2组数据，以此类推输入t组
假设所有数据都是整数
输出
对于每1组数据，先用两行输出两个原来的多项式，再用一行输出运算结果，不必考虑结果全为0的情况
输出格式参考样本数据，格式要求包括：
1.如果指数或系数是负数，用小括号括起来。
2.如果系数为0，则该项不用输出。
3.如果指数不为0，则用符号^表示，例如x的3次方，表示为x^3。
4.多项式的每个项之间用符号+连接，每个+两边加1个空格隔开。
样例查看模式?
正常显示查看格式
输入样例1?
2\n
4\n
5?0\n
1?1\n
2?2\n
3?3\n
4\n
-5?0\n
-1?1\n
6?2\n
4?4\n
3\n
-3?0\n
-5?1\n
2?2\n
4\n
9?-1\n
2?0\n
3?1\n
-2?2\n
输出样例1
5?+?1x^1?+?2x^2?+?3x^3\n
(-5)?+?(-1)x^1?+?6x^2?+?4x^4\n
8x^2?+?3x^3?+?4x^4\n
(-3)?+?(-5)x^1?+?2x^2\n
9x^(-1)?+?2?+?3x^1?+?(-2)x^2\n
9x^(-1)?+?(-1)?+?(-2)x^1\n
\n
AC代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void display(vector<pair<int, int>>v)
{
for (int i = 0; i < v.size(); i++)
{
if (v[i].second == 0)continue;
else if (v[i].second < 0)
{
cout << "(" << v[i].second << ")";
}
else cout << v[i].second;
if (v[i].first == 0)
{
if (i != v.size() - 1&&v[i+1].second!=0)cout << " + ";
continue;
}
else if (v[i].first < 0)
{
cout << "x^(" << v[i].first << ")";
if (i != v.size() - 1 && v[i+1].second != 0)cout << " + ";
}
else
{
cout << "x^" << v[i].first;
if (i != v.size() - 1 && v[i+1].second != 0)cout << " + ";
}
}
cout << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<pair<int, int>>v1;
vector<pair<int, int>>v2;
vector<pair<int, int>>ans;
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
v1.push_back({ y,x });
}
cin >> n;
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
v2.push_back({ y,x });
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
display(v1);
display(v2);
//n为v2的
for (int i = 0; i < n; i++)
{
bool flag = 0;
for (int j = 0; j < v1.size(); j++)
{
if (v1[j].first == v2[i].first)
{
ans.push_back({ v2[i].first,v1[j].second + v2[i].second });
flag = 1;
break;
}
}
if (!flag)
{
ans.push_back({ v2[i].first,v2[i].second });
}
}
for (int j = 0; j < v1.size(); j++)
{
bool flag = 0;
for (int i = 0; i < ans.size(); i++)
{
if (ans[i].first == v1[j].first)
{
flag = 1;
break;
}
}
if (!flag)
{
ans.push_back({ v1[j].first,v1[j].second });
}
}
sort(ans.begin(), ans.end());
display(ans);
}
cout << endl;
return 0;
}本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！