数据结构测试模拟题（3）

1、两个有序链表序列的合并

#include<bits/stdc++.h>
using namespace std;struct node{int num;node* next;
};// 创建链表
node* CreatList(){int x;node *head = new node();  // 创建头节点head->next = NULL;node *tail = head;        // 尾指针初始指向头节点while(cin >> x && x != -1){node *p = new node();p->num = x;p->next = NULL;tail->next = p;       // 新节点插入到尾部tail = p;             // 尾指针移动到新节点}return head;
}// 合并两个有序链表
node* ListUnion(node* heada, node* headb){node *pa = heada->next;   // 跳过头节点，指向第一个数据节点node *pb = headb->next;node *dummy = new node(); // 合并后的虚拟头节点node *pc = dummy;while(pa && pb){if(pa->num <= pb->num){pc->next = pa;pa = pa->next;} else {pc->next = pb;pb = pb->next;}pc = pc->next;        // 移动pc指针}// 连接剩余节点pc->next = pa ? pa : pb;// 释放原链表头节点delete heada;delete headb;return dummy;
}// 输出链表
void print(node *head){node *p = head->next;     // 跳过头节点if(!p){                   // 处理空链表cout << "NULL";return;}cout << p->num;           // 输出第一个节点p = p->next;while(p){cout << " " << p->num; // 控制空格输出p = p->next;}cout << endl;
}int main(){node *heada = CreatList();node *headb = CreatList();node *head = ListUnion(heada, headb);print(head);// 释放合并后的链表while(head){node *temp = head;head = head->next;delete temp;}return 0;
}

2、一元多项式的加法运算

#include<bits/stdc++.h>
using namespace std;
struct node{double xishu;int zhishu;
};
int main(){vector<node>p1,p2,result;int n;cin>>n;for(int i=0;i<n;i++){node t;cin>>t.xishu>>t.zhishu;p1.push_back(t);}int m;cin>>m;for(int j=0;j<m;j++){node t;cin>>t.xishu>>t.zhishu;p2.push_back(t);}int i=0,j=0;while(i<n&&j<m){if(p1[i].zhishu>p2[j].zhishu){result.push_back(p1[i]);i++;}else if(p1[i].zhishu<p2[j].zhishu){result.push_back(p2[j]);j++;}else{double sum=p1[i].xishu+p2[j].xishu;if(sum!=0){result.push_back({sum,p1[i].zhishu});}i++;j++;}}while(i<n)result.push_back(p1[i++]);while(j<m)result.push_back(p2[j++]);for(const auto& term: result){cout<<fixed<<setprecision(2)<<term.xishu<<" "<<term.zhishu<<"\n";}return 0;
}

3、栈操作的合法性

#include<bits/stdc++.h>
using namespace std;bool isValid(string s, int m) {int cnt = 0;for(int i = 0; i < s.length(); i++) {char c = s[i];if(c == 'S') {cnt++;if(cnt > m) {return false;  // 超过最大容量}} else {cnt--;if(cnt < 0) {return false;  // 栈空时出栈}}}return cnt == 0;  // 最终栈必须为空
}int main() {int n, m;cin >> n >> m;for(int i = 0; i < n; i++) {string s;cin >> s;if(isValid(s, m)) {cout << "YES" << endl; } else {cout << "NO" << endl;  }}return 0;
}

4、括弧匹配检验

#include<bits/stdc++.h>
using namespace std;bool isValid(string s) {stack<char> st;for(int i = 0; i < s.length(); i++) {char c = s[i];if(c == '(' || c == '[') {st.push(c);} else if(c == ')' || c == ']') {if(st.empty()) {return false;}char top = st.top();st.pop();if((c == ')' && top != '(') || (c == ']' && top != '[')) {return false;}}}return st.empty();
}int main() {string s;cin >> s;if(isValid(s)) {cout << "OK" << endl;} else {cout << "Wrong" << endl;}return 0;
}

5、还原二叉树

#include<bits/stdc++.h>
using namespace std;struct node{char value;node* left;node* right;// 添加构造函数node(char val) : value(val), left(NULL), right(NULL) {}
};int n;node* buildtree(string pre, string idx){if(pre.empty() || idx.empty()){return NULL;}char vroot = pre[0];node* root = new node(vroot);int idxroot = idx.find(vroot);string leftidx = idx.substr(0, idxroot);string rightidx = idx.substr(idxroot+1);string leftpre = pre.substr(1, leftidx.length());string rightpre = pre.substr(1 + leftidx.length());root->left = buildtree(leftpre, leftidx);root->right = buildtree(rightpre, rightidx);return root;
}// 修正函数名和返回值类型
int treeHeight(node* root){if(root == NULL) return 0;int leftheight = treeHeight(root->left);int rightheight = treeHeight(root->right);return max(leftheight, rightheight) + 1;
}int main(){cin >> n;string pre, idx;cin >> pre >> idx;node* root = buildtree(pre, idx); // 构建二叉树int h = treeHeight(root); // 调用修正后的函数名cout << h << endl; return 0;
}

6、求先序排列（后中求先）

#include<bits/stdc++.h>
using namespace std;struct node{char value;node* left;node* right;node(char x):value(x),left(NULL),right(NULL){}
};//post表示后序，idx表示中序
node* buildtree(string post, string idx){if(post.empty() || idx.empty()) return NULL;// 后序遍历的最后一个字符是根节点char rootv = post.back();node* root = new node(rootv);// 在中序遍历中找到根节点的位置int rootidx = idx.find(rootv);// 分割中序遍历为左子树和右子树string leftidx = idx.substr(0, rootidx);string rightidx = idx.substr(rootidx + 1);// 分割后序遍历为左子树和右子树string leftpost = post.substr(0, leftidx.length());string rightpost = post.substr(leftidx.length(), rightidx.length());// 修正递归调用的参数顺序：(后序, 中序)root->left = buildtree(leftpost, leftidx);root->right = buildtree(rightpost, rightidx);return root;
}void xianxu(node* root){if(root == NULL) return;  //直接返回，不返回值cout << root->value;xianxu(root->left);xianxu(root->right);
}int main(){string post, idx;  // 修正变量名以反映实际用途cin >> idx >> post;  //先输入中序，再输入后序node* root = buildtree(post, idx);xianxu(root);cout << endl;return 0;
}

7、迷宫最短路径问题

#include <iostream>
#include <queue>
using namespace std;struct node {int r, c, s; // row column step
};int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int b[15][15];
int a[15][15];
int n;int bfs(int x, int y) {queue<node> mg;node q;q.r = x;q.c = y;q.s = 0;b[q.r][q.c] = 1;mg.push(q);while (!mg.empty()) {q = mg.front();mg.pop();if (q.r == n - 2 && q.c == n - 2) {return q.s;}node t;for (int i = 0; i < 4; i++) {t.r = q.r + dir[i][0];t.c = q.c + dir[i][1];if (!b[t.r][t.c] && a[t.r][t.c] == 0 && t.r >= 0 && t.r < n && t.c >= 0 && t.c < n) {b[t.r][t.c] = 1;t.s = q.s + 1;mg.push(t);}}}return -1;
}int main() {cin >> n;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> a[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {b[i][j] = 0;}}int result = bfs(1, 1);if (result == -1) {cout << "No solution\n";} else {cout << result << "\n";}return 0;
}    

8、图着色问题

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=N*N;
int color[N];
vector<int> g[M];
int v,m,k,n;void add(int a,int b){g[a].push_back(b);g[b].push_back(a);
}
int judge(int cnt){if(cnt!=k)return 0;for(int i=1;i<=v;i++){for(int j=0;j<g[i].size();j++){int t=g[i][j];if(color[i]==color[t])return 0;}}return 1;
}
int main(){cin>>v>>m>>k;while(m--){int a,b;cin>>a>>b;add(a,b),add(b,a);}cin>>n;for(int i=0;i<n;i++){set<int> se;//set具有去重功能for(int j=1;j<=v;j++){cin>>color[j];se.insert(color[j]);} if(judge(se.size()))cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

9、地下迷宫探索

#include <bits/stdc++.h>
using namespace std;const int N = 1005;
int vis[N];
int g[N][N];
stack<int> stk;
int n, m, src;// 深度优先搜索函数
void dfs(int k) {vis[k] = 1;if (vis[src]) cout << k;else cout << " " << k;stk.push(k);for (int i = 1; i <= n; i++) {if (!vis[i] && g[k][i] == 1) {cout << " ";dfs(i);}}stk.pop();if(!stk.empty()){cout<<" "<<stk.top();}
}int main() {memset(vis, 0, sizeof(vis));cin >> n >> m >> src; // n代表节点数，m代表边数，src代表初末位置 int s, d;for (int i = 1; i <= m; i++) {cin >> s >> d;g[s][d] = g[d][s] = 1;}dfs(src);bool connected = true;for (int i = 1; i <= n; i++) {if (!vis[i]) {connected = false;break;}}if (!connected) cout << " " << 0;return 0;
}