2020级数据结构荣誉课第三次上机考试题解（树）
目录
题目一：7-1 二叉树最长路径 (100 分)
题目描述：
给定一棵二叉树T，求T中的最长路径的长度，并输出此路径上各结点的值。若有多条最长路径，输出最右侧的那条。
输入格式:
第1行，1个整数n，表示二叉树有n个结点， 1≤n≤100000.
第2行，2n+1个整数，用空格分隔，表示T的扩展先根序列， -1表示空指针，结点用编号1到n表示。
输出格式:
第1行，1个整数length，length表示T中的最长路径的长度。
第2行，length+1个整数，用空格分隔，表示最右侧的最长路径。
输入样例:
在这里给出一组输入。例如：
5
1 2 -1 -1 3 4 -1 -1 5 -1 -1输出样例:
在这里给出相应的输出。例如：
2
1 3 5题目分析：
此题考查二叉树的建立与遍历，建立操作可通过递归实现，在求最长路径方面用了两个 vector 一个用于存当前的临时路径，一个存最长路径，两者有更新关系。求最长路径可理解为一种深度优先搜寻。
代码：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class T
{
public:
T* l;
T* r;
int n;
};
void CBT(T*& p0)
{
int n;
cin>>n;
if (n == -1)
{
p0 = NULL;
return;
}
p0 = new T;
p0->n = n;
CBT(p0->l);
CBT(p0->r);
}
void FIO(T* p)
{
if (!p)
return;
cout<<p->n;
FIO(p->l);
FIO(p->r);
}
vector<int>temp;
vector<int>path;
void dfs(T* t,vector<int>& temp)
{
if (!t) return;
temp.push_back(t->n);
if (t->r)
{
dfs(t->r,temp);
}
if (t->l)
{
dfs(t->l,temp);
}
if (temp.size()>path.size())
{
path = temp;
}
temp.pop_back();
}
int main()
{
T* t;
int n;
cin>>n;
CBT(t);
//FIO(t);
dfs(t,temp);
cout<<int(path.size())-1<<'\n';
for (int i = 0;i<int(path.size())-1;i++)
cout<<path[i]<<' ';
cout<<path[path.size()-1]<<'\n';
return 0;
}
题目二：7-2 森林的层次遍历 (100 分)
题目描述：
给定一个森林F，求F的层次遍历序列。森林由其先根序列及序列中每个结点的度给出。
输入格式:
第1行，1个整数n，表示森林的结点个数， 1≤n≤100000.
第2行，n个字符，用空格分隔，表示森林F的先根序列。字符为大小写字母及数字。
第3行，n个整数，用空格分隔，表示森林F的先根序列中每个结点对应的度。
输出格式:
1行，n个字符，用空格分隔，表示森林F的层次遍历序列。
输入样例:
在这里给出一组输入。例如：
14
A B C D E F G H I J K L M N
4 0 3 0 0 0 0 2 2 0 0 0 1 0输出样例:
在这里给出相应的输出。例如：
A M B C G H N D E F I L J K题目分析：
题目是让对一个森林以层次遍历的方式输出。所以可考虑真的构造此森林。
树的节点的数据类型定义为：
typedef struct node
{
vector<int>nxt;
}T;还需要用一个辅助栈来操作。需要分几种情况：
1.栈空，将该节点添加到 t[0] 的 nxt中，若该节点度为0，则该节点不能入栈；
2.栈不空，该节点入栈顶元素的 nxt 中，并进行一次度是否满的判断；
3.若度不为零，该节点直接入栈。
d[0] = 0;
for (int i = 1;i<=n;i++)
{
if (st.empty())
{
t[0].nxt.push_back(i);
st.push(i);
d[0]++;
if (!d[i])
st.pop();
continue;
}
t[st.top()].nxt.push_back(i);
if (int(t[st.top()].nxt.size()) == d[st.top()])
st.pop();
if (d[i])
{
st.push(i);
}
}层次遍历方面用队列来辅助即可。
完整代码：
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
stack<int>st;
queue<int>ss;
typedef struct node
{
vector<int>nxt;
}T;
char s[100001];
int d[100001];
int main()
{
T t[100001];
int n;
char ch;
scanf("%d\n",&n);
for (int i = 1;i<=n;i++)
{
s[i] = getchar();
ch = getchar();
}
for (int i = 1;i<=n;i++)
{
scanf("%d",&d[i]);
}
d[0] = 0;
for (int i = 1;i<=n;i++)
{
if (st.empty())
{
t[0].nxt.push_back(i);
st.push(i);
d[0]++;
if (!d[i])
st.pop();
continue;
}
t[st.top()].nxt.push_back(i);
if (int(t[st.top()].nxt.size()) == d[st.top()])
st.pop();
if (d[i])
{
st.push(i);
}
}
ss.push(0);
int k;
int f = 1;
while (!ss.empty())
{
k = ss.front();
ss.pop();
// printf("%d",k);
if (k)
{
if (f)
{
printf("%c",s[k]);
f = 0;
}
else
printf(" %c",s[k]);
}
for (int i = 0;i<d[k];i++)
{
ss.push(t[k].nxt[i]);
}
}
return 0;
}
题目三：7-3 纸带切割 (100 分)
题目描述：
有一条细长的纸带,长度为 L 个单位，宽度为一个单位。现在要将纸带切割成 n 段。每次切割把当前纸带分成两段，切割位置都在整数单位上，切割代价是当前切割纸带的总长度。每次切割都选择未达最终要求的最长纸带切割，若这样的纸带有多条，则任选一条切割。如何切割，才能完成任务，并且总代价最小。
输入格式:
第1行，1个整数n，表示切割成的段数， 1≤n≤100000.
第2行，n个整数Li，用空格分隔，表示要切割成的各段的长度，1≤Li≤200000000，1≤i≤n.
输出格式:
第1行，1个整数，表示最小的总代价。
第2行，若干个整数，用空格分隔，表示总代价最小时每次切割的代价。
输入样例:
在这里给出一组输入。例如：
5
5 6 7 2 4输出样例:
在这里给出相应的输出。例如：
54
24 13 11 6题目分析：
题目要求输出每次切割的最小代价以及总的最小代价。可以想到，总的最小代价，就是每次最小代价之和。不难发现每次的最小代价是当前的两个最小值之和。如此可以逆推出来。
且此题即构建一颗哈夫曼树。在选取最小值方面，可以使用优先队列，也可以构造一个小根堆。我用的是构造小跟堆，操作如下：
ll int heap[100001];
ll int hlen = 0;
void heap_down(int x)
{
ll int t;
ll int i = x,y;
while (2*i<=hlen)
{
y = 2*i;
if (2*i+1<=hlen&&heap[2*i+1]<heap[2*i])
y++;
if (heap[y]<heap[i])
{
t = heap[i];
heap[i] = heap[y];
heap[y] = t;
i = y;
}
else break;
}
}
void build()
{
hlen = n;
for (int i = n/2;i>=1;i--) heap_down(i);
}
接下来是每次选两个最小值并求出和再插入回去：
for (int i = n;i>=2;i--)
{
t1 = heap[1];
heap[1] = heap[hlen];
heap[hlen] = t1;
hlen--;
heap_down(1);
heap[1]+=t1;
ans[cnt++] = heap[1];
sum+=heap[1];
heap_down(1);
} 此外，还需特判当 n = 1时，直接输出一个 0；题目也没说要这样啊？？
完整代码：
#include <cstdio>
#define ll long long
char ch;
int n;
ll int heap[100001];
ll int hlen = 0;
void heap_down(int x)
{
ll int t;
ll int i = x,y;
while (2*i<=hlen)
{
y = 2*i;
if (2*i+1<=hlen&&heap[2*i+1]<heap[2*i])
y++;
if (heap[y]<heap[i])
{
t = heap[i];
heap[i] = heap[y];
heap[y] = t;
i = y;
}
else break;
}
}
void build()
{
hlen = n;
for (int i = n/2;i>=1;i--) heap_down(i);
}
int main()
{
ll int t1,sum = 0;
ll int cnt = 0;
ll int ans[100000];
scanf("%d",&n);
for (int i = 1;i<=n;i++)
scanf("%lld",&heap[i]); //输入的数
if (n == 1)
{
printf("0");
return 0;
}
build();
for (int i = n;i>=2;i--)
{
t1 = heap[1];
heap[1] = heap[hlen];
heap[hlen] = t1;
hlen--;
heap_down(1);
heap[1]+=t1;
ans[cnt++] = heap[1];
sum+=heap[1];
heap_down(1);
}
printf("%lld\n",sum);
for (int i = cnt-1;i>0;i--)
printf("%lld ",ans[i]);
printf("%lld\n",ans[0]);
return 0;
}
题目四：序列乘积 (100 分)
输入格式:
第1行，1个整数n，表示序列的长度， 1≤n≤100000.
第2行，n个整数Ai，用空格分隔，表示序列A，1≤Ai≤40000，1≤i≤n.
第3行，n个整数Bi，用空格分隔，表示序列B，1≤Bi≤40000，1≤i≤n.
输出格式:
1行，n个整数，用空格分隔，表示序列乘积中的从小到大前n个。
输入样例:
在这里给出一组输入。例如：
5
1 3 5 7 9
2 4 6 8 10
输出样例:
在这里给出相应的输出。例如：
2 4 6 6 8题目分析：
看到此题首先会想开一个长度为的二维数组，计算出全部的大小然后进行排序。但是这样空间复杂度过高，堆区会爆掉。我们可以建立一个大根堆的优先队列p，先将A1*Bn的所有元素插入,对其余数插入的时候与队顶比较，若比队顶元素小则可插入，并把队顶元素弹出，以此来维护长度不超过n的队列。
for (int i = 1;i<=n;i++)
q.push(A[1]*B[i]);
for(int i = 2;i<=n;i++)
{
for (int j = 1;j<=n;j++)
{
if (A[i]*B[j]<=q.top())
{
q.pop();
q.push(A[i]*B[j]);
}
else
break;
}
}并且可利用A[n],B[n]单调递增这一点，及时剪枝，可以节省大量时间。
完整代码：
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int A[100002],B[100002];
priority_queue<long long,vector<long long >,less<long long >>q;
long long int ans[100002];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
for (int i = 1;i<=n;i++)
{
cin>>A[i];
}
for (int i = 1;i<=n;i++)
{
cin>>B[i];
}
for (int i = 1;i<=n;i++)
q.push(A[1]*B[i]);
for(int i = 2;i<=n;i++)
{
for (int j = 1;j<=n;j++)
{
if (A[i]*B[j]<=q.top())
{
q.pop();
q.push(A[i]*B[j]);
}
else
break;
}
}
for (int i = 1;i<=n;i++)
{
ans[n-i+1] = q.top();
q.pop();
}
cout<<ans[1];
for (int i = 2;i<=n;i++)
cout<<' '<<ans[i];
return 0;
}