2020北航计算机夏令营机试题目个人理解
发布时间
阅读量：
阅读量
摘要：
二叉树问题：
- 输入一个整数序列，构建完全二叉排序树。
- 通过排序输入数组并构建索引树，利用中序遍历得到排序后的数组。
- 根据层数输出层序遍历序列。
栈问题：- 模拟栈操作，记录函数调用的最大嵌套深度。
- 输出调用路径、父函数个数和被调用次数。
- 使用栈记录调用过程，维护父函数和调用次数的记录。
一、二叉树(60分)
给定一个整数序列，以这些数为基础构建一个完全二叉排序树，生成该二叉树的层次遍历序列。输入部分包括一个整数n，表示序列的长度，以及第二行的n个整数，每个整数代表二叉排序树中的一个节点。你的任务是根据这些输入生成相应的层次遍历序列。
输入样例：
18
56 987 -25 0 1021 -238 399 12 77 -1 72190 -25 -168 -41367 3218 12 0 -25输出样例：
12 -1 987 -25 0 77 3218 -238 -25 0 12 56 399 1021 72190 -41367 -168 -25首先对输入数组进行排序，生成该完全二叉树的中序遍历序列。随后构建一个完全二叉索引树，其中每个节点存储的值代表其所在层次。对这个索引树进行中序遍历，得到的序列即为排序后数组中每个元素对应的层次信息。最后根据各元素所在的层次进行输出，这样就完成了整个过程。
#include <bits/stdc++.h>
using namespace std;
vector<int>data;
vector<int>ind;
vector<int>order_data;//存放index完全二叉树的中序遍历
int n;
//中序遍历
void visits(int root){
if(root>=n)
return;//超过节点范围了
else{
visits(2*root+1);//左子树
order_data.push_back(ind[root]);
visits(2*root+2);//右子树
}
}
int main() {
cin>>n;
int cnt=n;int tp;
while(cnt--){
cin>>tp;data.push_back(tp);
}
cnt=n;
//构建索引树
int level=0;//计算层数
int count=1;
for(int i=1;cnt>0;i++){
level++;
for(int k=0;k<count&&cnt>0;k++){
ind.push_back(i);cnt--;//完全二叉树索引节点存放的是这个节点的层数
}
count*=2;
}
//排序，则得到了原来数据建立的排序完全二叉树的中序遍历
sort(data.begin(),data.end());
//得到数据
visits(0);
//输出数据
vector<vector<int>>mymap(level);
for(int i=0;i<n;i++){
mymap[order_data[i]-1].push_back(data[i]);
}
for(int i=0;i<level;i++){
for(int m=0;m<mymap[i].size();m++)
cout<<mymap[i][m]<<" ";
}
}在50行代码内实现了hhh功能，同时，还可以自行分析其中的其他关联。相比之下，构建索引树的思路相对较为直观且易于想到。
二、栈(40分）
请分析一个函数调用链，找出嵌套最深的调用所对应的函数名称，并记录调用路径。同时，统计该函数的调用者数量及其被调用次数。若有多个调用路径可达到相同的最大嵌套深度，仅需输出第一条路径。输入数据中，若为1 funcName格式，则表示调用funcName函数；若输入为0，则表示终止对嵌套最深函数的调用。
输入样例：
1 main
1 input
0
1 mysqrt
0
1 findA
0
1 findB
1 area
1 mysin
0
1 mycos
0
1 mysqrt
0
0
0
1 findC
1 area
1 mysin
0
0
1 mysqrt
1 max
0
0
0
1 output
0
0输出样例：
mysin main-findB-area 1 2
mycos main-findB-area 1 1
mysqrt main-findB-area 3 3
max main-findC-mysqrt 1 1个人思路：这可能是一种较为简单的栈模拟方案，通过实时进行数据的输入与处理，只要细心做好记录，实现起来还是比较容易的。
#include <bits/stdc++.h>
using namespace std;
map<string,int>mp;//记录每个函数调用次数
map<string,set<string>>fu;//记录每个函数父函数个数
vector<string>sta;//模拟栈
vector<vector<string>>data(100);//记录所有最长完整调用
int maxlen=0;int num=0;//num记录有多少个最长的调用
int main(){
int op;string func;int nowlen=0;
while(cin>>op){
if(op==1){
nowlen++;
cin>>func;
sta.push_back(func);
//父函数
if(nowlen>1){
fu[func].insert(sta[nowlen-2]);
}
if(mp.find(func)!=mp.end())
mp[func]++;
else
mp[func]=1;
}else{
if(nowlen>maxlen){
//找到一条当前最长
if(num!=0){
//清空之前的
for(int i=0;i<num;i++)
data[i].clear();
num=0;
}
//装入新的
data[num++]=sta;
maxlen=nowlen;
}else if(nowlen==maxlen){
//看下是不是以前出现过的
int flag=0;
for(int i=0;i<num;i++){
if(data[i][maxlen-1]==sta[nowlen-1]){
flag=1;break;}
}
if(!flag){
data[num++]=sta;
}
}
//出栈
nowlen--;
sta.erase(sta.end());
}
}
//输出
for(int i=0;i<num;i++){
cout<<data[i][maxlen-1]<<" ";
for(int j=0;j<data[i].size()-2;j++)
cout<<data[i][j]<<"-";
cout<<data[i][maxlen-2]<<" ";
cout<<fu[data[i][maxlen-1]].size()<<" ";
cout<<mp[data[i][maxlen-1]];
cout<<endl;
}
}这个网站是一个非常棒的在线编程工具，您可以访问 Ideone.com 以体验更多功能。
全部评论 (0)
还没有任何评论哟~