往年机考题

数据结构机考 9 题题目与答案代码说明输入均从 Test*.txt 读取第4~6题为函数实现可在 main 中调用测试。代码已精简并含关键注释。第1题机考20 · 40分单向链表操作【题目】从 Test1.txt 读入 n 和 n 个正整数。(1)按输入顺序建表并输出 (2)升序排序并输出 (3)去重并输出 (4)逆置并输出。【参考代码】#include iostream#include fstream#include algorithmusing namespace std;struct Node { int d; Node *n; };Node *head nullptr;Node* add(Node *h, int x) { //尾插建表Node *p new Node{x, nullptr};if (!h) return p;Node *t h; while (t-n) t t-n; t-n p; return h;}void print(Node *h) { for (Node *p h; p; p p-n) cout p-d (p-n ? : \n); }void sortList(Node *h) { //冒泡升序for (Node *i h; i; i i-n)for (Node *j i-n; j; j j-n)if (i-d j-d) swap(i-d, j-d);}void uniqueList(Node *h) { //有序去重if (!h) return;Node *p h;while (p-n) {if (p-d p-n-d) { Node *t p-n; p-n t-n; delete t; }else p p-n;}}void reverseList(Node *h) { //头插逆置Node *r nullptr;while (h) { Node *t h; h h-n; t-n r; r t; }h r;}int main() {ifstream fin(Test1.txt);int n, x; fin n;while (n--) { fin x; head add(head, x); }print(head); sortList(head); print(head);uniqueList(head); print(head); reverseList(head); print(head);return 0;}第2题机考20 · 30分无向图邻接矩阵与最小生成树【题目】从 Test2.txt 读顶点数、顶点编号、边数及边(u,v,w)。建立邻接矩阵输出最小生成树的边及权值。【参考代码】#include iostream#include fstream#include vectorusing namespace std;const int INF 1e9;int prim(vectorvectorint g, int n, vectorpairint,int edges) {vectorint low(n, INF), vis(n, 0), pre(n, -1);low[0] 0;for (int i 0; i n; i) {int u -1;for (int j 0; j n; j)if (!vis[j] (u -1 || low[j] low[u])) u j;vis[u] 1;if (pre[u] ! -1) edges.push_back({pre[u], u});for (int v 0; v n; v)if (!vis[v] g[u][v] low[v]) { low[v] g[u][v]; pre[v] u; }}return 0;}int main() {ifstream fin(Test2.txt);int n, m, id, u, v, w;fin n; vectorint vid(n);for (int i 0; i n; i) fin vid[i];fin m;vectorvectorint g(n, vectorint(n, INF));for (int i 0; i n; i) g[i][i] 0;while (m--) {fin u v w;u--; v--; g[u][v] g[v][u] min(g[u][v], w);}vectorpairint,int es;prim(g, n, es);for (auto e : es)cout vid[e.first] vid[e.second] g[e.first][e.second] endl;return 0;}第3题机考20 · 30分二叉排序树【题目】读 n 和 n 个正整数建 BST。(1)先序遍历 (2)输入 e若存在则删除以 e 为根的子树并再先序遍历否则输出“e 不存在”。【参考代码】#include iostream#include fstreamusing namespace std;struct TNode { int d; TNode *l, *r; };TNode* insert(TNode *t, int x) { //插入if (!t) return new TNode{x, nullptr, nullptr};if (x t-d) t-l insert(t-l, x);else if (x t-d) t-r insert(t-r, x);return t;}void pre(TNode *t) { //先序if (!t) return;cout t-d ;pre(t-l); pre(t-r);}void freeTree(TNode *t) { if (!t) return; freeTree(t-l); freeTree(t-r); delete t; }TNode* delSub(TNode *t, int e) { //删除以e为根的子树if (!t) return nullptr;if (t-d e) { freeTree(t); return nullptr; }t-l delSub(t-l, e); t-r delSub(t-r, e);return t;}bool find(TNode *t, int e) { //查找if (!t) return false;if (t-d e) return true;return find(t-l, e) || find(t-r, e);}int main() {ifstream fin(Test3.txt);int n, x, e; fin n; TNode *root nullptr;while (n--) { fin x; root insert(root, x); }pre(root); cout endl;cin e;if (!find(root, e)) cout e 不存在 endl;else { root delSub(root, e); pre(root); cout endl; }return 0;}第4题机考21 · 40分递增链表求交集【题目】L1、L2 均为递增有序单链表。求交集存入 L1 并删冗余节点另实现销毁链表。【参考代码】#include iostreamusing namespace std;typedef int Status; const int OK 1;struct LNode { int data; LNode *next; };typedef LNode *LinkList;Status Intersection(LinkList L1, LinkList L2) { //求交集LNode *p1 L1-next, *p2 L2-next, *pre L1;while (p1 p2) {if (p1-data p2-data) {pre-next p1-next; delete p1; p1 pre-next;} else if (p1-data p2-data) p2 p2-next;else { pre p1; p1 p1-next; p2 p2-next; }}while (p1) { pre-next p1-next; delete p1; p1 pre-next; }return OK;}Status DestroyList(LinkList L) { //销毁while (L) { LinkList t L; L L-next; delete t; }return OK;}第5题机考21 · 30分二叉树高度与销毁【题目】二叉链表存储的二叉树 T求高度并销毁。【参考代码】#include iostreamusing namespace std;typedef int Status; const int OK 1;struct BiTNode { int data; BiTNode *lchild, *rchild; };typedef BiTNode *BiTree;int HeightBiTree(BiTree T) { //高度if (!T) return 0;int hl HeightBiTree(T-lchild), hr HeightBiTree(T-rchild);return (hl hr ? hl : hr) 1;}Status DestroyBiTree(BiTree T) { //后序销毁if (!T) return OK;DestroyBiTree(T-lchild); DestroyBiTree(T-rchild);delete T; T nullptr; return OK;}第6题机考21 · 30分堆排序与折半查找【题目】顺序表 H 存整数堆排序升序、折半查找 key、销毁存储空间。【参考代码】#include iostreamusing namespace std;typedef int Status; const int OK 1, ERROR 0;struct SqList { int *elem; int length; };void sift(SqList H, int low, int high) { //筛选int x H.elem[low], i low, j 2 * i 1;while (j high) {if (j 1 high H.elem[j 1] H.elem[j]) j;if (H.elem[j] x) break;H.elem[i] H.elem[j]; i j; j 2 * i 1;}H.elem[i] x;}Status HeapSort(SqList H) { //堆排序for (int i H.length / 2 - 1; i 0; i--) sift(H, i, H.length - 1);for (int i H.length - 1; i 0; i--) {swap(H.elem[0], H.elem[i]); sift(H, 0, i - 1);}return OK;}int BinSearch(SqList H, int key) { //折半查找int l 0, r H.length - 1;while (l r) {int m (l r) / 2;if (H.elem[m] key) return m;if (H.elem[m] key) l m 1; else r m - 1;}return -1;}Status DestroyData(SqList H) { delete[] H.elem; H.elem nullptr; H.length 0; return OK; }第7题机考23秋 · 40分单向链表操作【题目】从 Test1.txt 读入。(1)建表输出 (2)升序排序 (3)逆置 (4)O(n)去重后输出。【参考代码】#include iostream#include fstream#include unordered_setusing namespace std;struct Node { int d; Node *n; };Node* add(Node *h, int x) {Node *p new Node{x, nullptr};if (!h) return p; Node *t h; while (t-n) t t-n; t-n p; return h;}void print(Node *h) { for (Node *p h; p; p p-n) cout p-d (p-n ? : \n); }void sortList(Node *h) {for (Node *i h; i; i i-n)for (Node *j i-n; j; j j-n)if (i-d j-d) swap(i-d, j-d);}void reverseList(Node *h) {Node *r nullptr;while (h) { Node *t h; h h-n; t-n r; r t; }h r;}void uniqueOn(Node *h) { // O(n)哈希去重unordered_setint seen; Node *p h, *pre nullptr;while (p) {if (seen.count(p-d)) {Node *t p; p p-n;(pre ? pre-n : h) p; delete t;} else { seen.insert(p-d); pre p; p p-n; }}}int main() {ifstream fin(Test1.txt);int n, x; fin n; Node *head nullptr;while (n--) { fin x; head add(head, x); }print(head); sortList(head); print(head);reverseList(head); print(head); uniqueOn(head); print(head);return 0;}第8题机考23秋 · 30分二叉树建立与层次输出【题目】Test2.txt 为先序序列# 表示空。建二叉链表输出高度再按层输出每层一行。【参考代码】#include iostream#include fstream#include queue#include stringusing namespace std;struct BiTNode { char data; BiTNode *l, *r; };BiTNode* build(string s, int i) { //先序建树if (i (int)s.size() || s[i] #) { i; return nullptr; }BiTNode *t new BiTNode{s[i], nullptr, nullptr};t-l build(s, i); t-r build(s, i);return t;}int height(BiTNode *t) {if (!t) return 0;return max(height(t-l), height(t-r)) 1;}void levelPrint(BiTNode *t) { //按层输出queueBiTNode* q; q.push(t);while (!q.empty()) {int sz q.size(); string line;while (sz--) {BiTNode *p q.front(); q.pop();line p-data;if (p-l) q.push(p-l);if (p-r) q.push(p-r);}cout line endl;}}int main() {ifstream fin(Test2.txt); string s; fin s;int idx 0; BiTNode *root build(s, idx);cout height(root) endl;levelPrint(root);return 0;}第9题机考23秋 · 30分图的最小生成树【题目】从 Test3.txt 读图信息。建立存储结构输出 MST 权值之和及各边。【参考代码】#include iostream#include fstream#include vectorusing namespace std;const int INF 1e9;int prim(vectorvectorint g, int n, vectorpairint,int edges) {vectorint low(n, INF), vis(n, 0), pre(n, -1);low[0] 0; int sum 0;for (int i 0; i n; i) {int u -1;for (int j 0; j n; j)if (!vis[j] (u -1 || low[j] low[u])) u j;vis[u] 1; sum low[u];if (pre[u] ! -1) edges.push_back({pre[u], u});for (int v 0; v n; v)if (!vis[v] g[u][v] low[v]) { low[v] g[u][v]; pre[v] u; }}return sum;}int main() {ifstream fin(Test3.txt);int n, m, id, u, v, w;fin n; vectorint vid(n);for (int i 0; i n; i) fin vid[i];fin m;vectorvectorint g(n, vectorint(n, INF));for (int i 0; i n; i) g[i][i] 0;while (m--) { fin u v w; u--; v--; g[u][v] g[v][u] w; }vectorpairint,int es; int sum prim(g, n, es);cout 最小权值之和 sum endl;for (auto e : es)cout 边( vid[e.first] vid[e.second] g[e.first][e.second] ) endl;return 0;}