鉴于2021级上机实验似乎有原题，故将代码均暂时注释，避免自制力不强的学弟学妹投机取巧，但保留思路解释，可供参考
1.前言
寒假闲来无事，遂整理上机题，以供参考交流。
上机时间为三小时，尽量多思考、多动手，切勿抄袭。
吉林大学软件学院2020级上机实验题及代码，能力所限，请多包涵。欢迎交流。
2.上机题
（1）老师将对答完题的同学进行抽查，让其讲解代码，检查不通过者，视情节严重情况扣分，若被发现抄袭，则按抄袭处理。
（2）每次题目开放一周，课下得分不打折。但会设置平时分，课上表现积极、课上完成题目多、出勤率高的同学，平时分高。 每次3道题，判题采用OI规则。
（3）查重将以首次提交的最高分代码为准，所以自己通过前请不要提交别人的通过代码。抄袭者与被抄袭者同等处理，不做区分。往届均有因上机抄袭导致数据结构课程不及格的同学，希望同学们不要铤而走险，不要坑自己，更不要坑自己的朋友！抄袭1次：整个上机成绩减半。抄袭2次：整个上机成绩记0分。
（4）不允许include以下头文件：algorithm、vector、stack、queue、deque、list、map、set。若include <bits/stdc++.h>也不允许使用上述STL头文件内的东西。允许使用STL string，但不允许使用其中的find、insert、erase、substr、assign函数。不允许使用C语言qsort、strstr库函数。除此之外，其余头文件和库函数均可自由使用。
A 单链表基本操作 (10 分)
请编写程序实现单链表插入、删除结点等基本算法。给定一个单链表和一系列插入、删除结点的操作序列，输出实施上述操作后的链表。单链表数据域值为整数。
输入格式:
输入第1行为1个正整数n，表示当前单链表长度；第2行为n个空格间隔的整数，为该链表n个元素的数据域值。第3行为1个正整数m，表示对该链表施加的操作数量；接下来m行，每行表示一个操作，为2个或3个整数，格式为0 k d或1 k。0 k d表示在链表第k个结点后插入一个数据域值为d的结点，若k=0则表示表头插入。1 k表示删除链表中第k个结点，此时k不能为0。注：操作序列中若含有不合法的操作（如在长度为5的链表中删除第8个结点、删除第0个结点等），则忽略该操作。n和m不超过100000。
输出格式:
输出为一行整数，表示实施上述m个操作后的链表，每个整数后一个空格。输入数据保证结果链表不空。
输入样例:
5
1 2 3 4 5
5
0 2 8
0 9 6
0 0 7
1 0
1 6
输出样例:
7 1 2 8 3 5 作者
朱允刚
单位
吉林大学
代码长度限制
16 KB
Python (python3)
时间限制
1000 ms
内存限制
256 MB
其他编译器
时间限制
100 ms
内存限制
10 MB这题比较简单，没啥可说的，就是根据输入格式构造链表，并对链表进行一系列操作，正常进行操作就行，一般不会超时。代码如下：
#include<iostream>
using namespace std;
struct node {
int num;
node* next;
node(int n) {
num = n;
next = NULL;
}
};//结点
int main() {
int n = 0, m = 0, order = 0, k = 0, d = 0, a = 0,length=0;
node* head = NULL, * last = NULL, * p1 = NULL,*p2=NULL;
cin >> n;
length = n;
for (int i = 0; i < n; i++) {
cin >> a;
if (i ==0) {
last=head = new node(a);//头结点，但是建议不要像我这么干，最好放在循环外
}
else {
last = last->next = new node(a);//尾插
}
}//构造链表
cin >> m;
for (int i = 0; i < m; i++) {
cin >> order;
p1 = head;
if (order == 0) {
cin >> k >> d;
if (k>length) { continue; }
if (k == 0) {
p1 = new node(d);
p1->next = head;
head = p1;
}
else {
while (k != 1) {
p1 = p1->next;
k--;
}
p2 = new node(d);
p2->next = p1->next;
p1->next = p2;
}
length++;
}//order==0时对链表进行相应操作
else {
cin >> k;
if (k > length||k==0) { continue; }
if (k == 1) {
head = head->next;
}
else {
while (k != 2) {
p1 = p1->next;
k--;
}
p2 = p1->next;
p1->next = p2->next;
}
length--;
}
}
p1 = head;
while (p1 != NULL) {
cout << p1->num<<" ";
p1 = p1->next;
}
return 0;
}B 重建二叉树 (10 分)
给定非空二叉树的中根序列和后根序列，请编写程序创建该二叉树，计算其高度和先根序列，最后删除该二叉树；如给定的中根和后根序列不合法，则亦能识别。
输入格式:
输入包含多组数据（不超过10组），每组为两行字符串，第一行表示某二叉树的后根序列，第二行表示其中根序列。结点的值均为A-Z的大写字母，故二叉树结点个数不超过26，且保证输入的两个序列都是结点的全排列，但不一定是合法的中根和后根序列。输入保证不是空二叉树。
输出格式:
对于每组数据，如果输入的序列不合法（不是同一棵树的中根序列和后根序列），则输出INVALID；若输入序列合法，输出为两行，第一行为一个整数，表示该二叉树的高度，第二行为一个字符串，表示该二叉树的先根序列。
输入样例1:
CEFDBHGA
CBEDFAGH
CBEDFAGH
CEFDBHGA
BCA
CAB
输出样例1:
3
ABCDEFGH
INVALID
INVALID作者
朱允刚
单位
吉林大学
代码长度限制
16 KB
时间限制
50 ms
内存限制
64 MB这题略微有些意思，但最后要删除二叉树的操作有点迷（不知道删不删除系统能否检测，反正加了删除也不会超时），总之先递归构造二叉树，在构造的时候依次根据条件判断合法，不断分割二叉树的先序和后序遍历。同时构造两个全局数组分别记录树高和其先根遍历序列即可。
#include<iostream>
using namespace std;
#include<string>
string re[10];//记录先序遍历
int hight[10];//记录高度
int n=0;//树的数目
struct treenode {
char c;
treenode* left, * right;
treenode() {
c = '*';
left = NULL;
right = NULL;
}
};//树节点
//树的构造
void gettree(string last,string mid,treenode*head) {//后序、中序遍历序列，以及当前需要构造结点的地址
int len1 = last.length(), len2 = mid.length(), position = len2;//position指示当前构造结点
if (len1<1) { return; }//长度为0
char h = last[len1 - 1];
if (len1 != len2||hight[n]==-1||(len1==1&&last!=mid)) { hight[n] = -1; return; }//判断先序和后序不为一棵树
head->c = last[len2 - 1];
if (len1 == 1) { return; }//无子结点
string left_last, left_mid, right_last, right_mid;//接下来进行左右字数先序后序遍历的构造
for (int i = 0; i < len1; i++) {
if (mid[i] == h) { position = i; }
if (i < position) {
left_last.push_back(last[i]);
left_mid.push_back(mid[i]);
}
else if (i == position&&i!=len1-1) {
right_last.push_back(last[i]);
}
else {
if (i == len1 - 1) {
right_mid.push_back(mid[i]);
}
else {
right_mid.push_back(mid[i]);
right_last.push_back(last[i]);
}
}
}
if (position == len2) { hight[n] =-1; return; }
head->left = new treenode(); head->right = new treenode();//递归构造
gettree(left_last, left_mid, head->left);
gettree(right_last, right_mid, head->right);
}
void front(treenode* head, int depth) {
if (head == NULL||head->c == '*') { return; }
hight[n] = max(hight[n], depth);//高度的获取
re[n].push_back(head->c);//先序遍历保存
front(head->left, depth + 1);
front(head->right, depth + 1);
}
void deletetree(treenode*head) {
if (head == NULL) { return; }
if (head->c == '*') { delete head; return; }
deletetree(head->left);
deletetree(head->right);
delete head;
}//删除树
int main() {
string s1, s2; treenode* head;
while (cin >> s1) {
cin >> s2;
head = new treenode();
gettree(s1, s2, head);
if (hight[n] != -1) {
front(head, 0);
deletetree(head);
}
n++;
}
for (int i = 0; i < n;i++) {
if (hight[i] == -1) {
cout << "INVALID" << endl;
}
else {
cout << hight[i] << endl;
cout << re[i] << endl;
}
}//输出
return 0;
}C 最少点字典序最短路径 (10 分)
给定一个正权有向图，图中包含n个顶点，编号为0至n-1。以顶点0作为源点，请编写程序求顶点0到各顶点的最短路径。若顶点0到某顶点存在多条最短路径，则输出经过顶点最少的那条路径，例如图1(a)中0到4的经过顶点最少的最短路径为0 - 3 - 4。若存在多条最短路径且其经过顶点个数相等，则输出字典序最小者。例如图1(b)中0到5的满足条件的最短路径为0 - 2 - 5。
注：字典序，即对象在字典中的顺序。对于两个数字序列，从第一个数字开始比较，当某一个位置的数字不同时，该位置数字较小的序列，字典序较小，例如1 2 3 9比1 2 4 5小，1 2 8 9比1 2 10 3小。
输入格式:
输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过20000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。
输出格式:
输出为若干行由“->”间隔的数字序列，每行为源点0到某顶点的满足条件的最短路径，如源点到某顶点无最短路径，则不输出该条路径。各条路径按终点的递增顺序输出，源点到源点的最短路径无需输出。
输入样例:
6 7
0 1 1
1 4 2
4 5 3
0 3 4
3 5 2
0 2 5
2 5 1
输出样例:
0->1
0->2
0->3
0->1->4
0->2->5作者
朱允刚
单位
吉林大学
代码长度限制
16 KB
时间限制
500 ms
内存限制
20 MB这题看起来似乎不难，但是数据测试点数据似乎有些诡异。首先是用边链表存储有向图（最好用头插法）。每次寻找当前未被直接访问结点中，length最小的结点进行访问。用load数组（当时不太注意命名规范，命名为path数组更合适）记录某个点从0到它这条路上的前驱结点，用depth数组记录这条路上经过的结点数。当访问至该节点，则根据这两个数组判断是否要更新结点路径信息。特别是当更新前后load、depth值都相同时，要进行回溯，找到二者最近的共同祖先结点即停止回溯，比较字典序（也是一种局部优化）。最后按格式输出即可。