企业官网建设流程全解析

数据结构机考 9 题题目与答案代码

说明：输入均从 Test*.txt 读取（第4~6题为函数实现，可在 main 中调用测试）。代码已精简并含关键注释。

第1题（机考20 · 40分）单向链表操作

【题目】从 Test1.txt 读入 n 和 n 个正整数。(1)按输入顺序建表并输出 (2)升序排序并输出 (3)去重并输出 (4)逆置并输出。

【参考代码】

#include <iostream>
#include <fstream>
#include <algorithm>
using 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 <vector>
using namespace std;
const int INF = 1e9;

int prim(vector<vector<int>> &g, int n, vector<pair<int,int>> &edges) {
vector<int> 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; vector<int> vid(n);
for (int i = 0; i < n; i++) fin >> vid[i];
fin >> m;
vector<vector<int>> g(n, vector<int>(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);
}
vector<pair<int,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 <fstream>
using 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 <iostream>
using 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 <iostream>
using 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 <iostream>
using 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_set>
using 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_set<int> 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 <string>
using 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) { //按层输出
queue<BiTNode*> 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 <vector>
using namespace std;
const int INF = 1e9;

int prim(vector<vector<int>> &g, int n, vector<pair<int,int>> &edges) {
vector<int> 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; vector<int> vid(n);
for (int i = 0; i < n; i++) fin >> vid[i];
fin >> m;
vector<vector<int>> g(n, vector<int>(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; }
vector<pair<int,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;
}