摘要:第五题为压轴题考了三叉霍夫曼树数据结构期末机考大致有道题,难度由浅入深,根据去年实际体验,大致人均题。最后一题会比较难,可能会遇到比较复杂的数据结构,机考过程中前四题全部后可以试一下。输入第一行为测试数据数。每组测试数据的输出占一行。
笔者按去年实际考试内容,回忆并编写本博客。建议大家收藏,如对考试有帮助,记得回来丢个赞。如果对部分内容有疑问可以直接留言。
去年第一题、第二题为顺序表,第三题为排序,第四题主要考dfs。第五题为压轴题考了三叉霍夫曼树
数据结构期末机考大致有5道题,难度由浅入深,根据去年实际体验,大致人均AC2~3题。前三题的难度会相对比较简单,主要需要重点复习下顺序表,链表等线性结构,排序算法(选择,插入,冒泡…),哈希查找。第四题一般会相对难一些,需要重点复习一下图的dfs,bfs。最短路径的Dijkstra算法以及最小生成树Prim和Kruskal算法。最后一题会比较难,可能会遇到比较复杂的数据结构,机考过程中前四题全部AC后可以试一下。
这部分的两道题大概是去年机考的第四第五题(前面题记不清了),凭着回忆把题目重新写了下,又做了一遍,自己敲了标程。
按输入顺序输出无向图的所有割点。(割点:在一个无向图中,如果删除某个顶点以及与该顶点相关联的所有边后,图的连通分量增多,就称这个点为割点。)
输入
第一行为测试数据数。对于每组测试数据,第一个整数 n n n表示该无向图的大小。接下来 n n n个字符串为每个顶点的名称。接下来输入一个 n ∗ n n*n n∗n的方阵作为无向图,0表示两个顶点之间不存在边,1表示两个顶点之间存在边。
输出
输出各个割点的名称。每组测试数据的输出占一行。如果没有割点,则输出No!
样例输入
4
8
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 1 1 0
0 1 1 0 0 0 0 0
0 1 1 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 1
0 0 0 0 0 0 1 0
3
A B C
0 1 0
1 0 1
0 1 0
5
a b c d e
0 1 0 0 1
1 0 1 1 0
0 1 0 0 0
0 1 0 0 0
1 0 0 0 0
6
v1 v2 v3 v4 v5 v6
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
样例输出
2 6
B
a b
No!
参考代码
#include #include using namespace std;bool *isVisited;int **matrix;int n = 0;//node:当前深搜点 cur:当前判断的割点void dfs(int node, int cur) { isVisited[node] = true; for (int i = 0; i < n; i++) { if ((!isVisited[i]) && i != cur && node != cur && (matrix[node][i] || matrix[i][node])) { dfs(i, cur); } }}int main() { int t; cin >> t; while (t--) { cin >> n; vector<string> vertex; vector<string> res; isVisited = new bool[n]; matrix = new int *[n]; for (int i = 0; i < n; i++) { string temp; cin >> temp; vertex.push_back(temp); matrix[i] = new int[n]; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> matrix[i][j]; } } int cc = 0; for (int i = 0; i < n; i++) { if (!isVisited[i]) { cc++; dfs(i, -1); } } for (int i = 0; i < n; i++) { int temp = 0; for (int ii = 0; ii < n; ii++) { isVisited[ii] = false; } for (int j = 0; j < n; j++) { if (!isVisited[j]) { temp++; dfs(j, i); } } if (temp > cc + 1) { res.push_back(vertex[i]); } } if (res.empty()) { cout << "No!" << endl; } else { for (int i = 0; i < res.size(); i++) { cout << res[i] << " "; } cout << endl; } } return 0;}
给定n个权值,根据这些权值构造三叉霍夫曼树,并进行三叉霍夫曼编码。
输入
第一行输入 t t t,表示有 t 个 t个 t个测试实例
第二行先输入 n n n,表示第1个实例有 n n n个权值,接着输入 n n n个权值,权值全是小于1万的正整数
依此类推
输出:
逐行输出每个权值对应的编码,格式如下:权值-编码
即每行先输出1个权值,再输出一个短划线,再输出对应编码,接着下一行输出下一个权值和编码。
以此类推
样例输入
2
8
1 5 3 4 9 2 6 10
10
1 5 9 6 3 4 7 8 11 12
样例输出
1-100
5-01
3-102
4-00
9-11
2-101
6-02
10-12
1-010
5-120
9-02
6-121
3-011
4-012
7-122
8-00
11-10
12-11
样例代码
#include #include #include #include using namespace std;struct Node { int value; int father = -1; int son[3]; string code; Node(int value, int father) { this->value = value; this->father = father; for (int i = 0; i < 3; i++) { this->son[i] = -1; } }};bool cmp(const Node &a, const Node &b) { return (a.father == -1 ? a.value : (9999 + a.value)) < (b.father == -1 ? b.value : (9999 + b.value));}int getNode(int num, vector<Node> nodeList) { for (int i = 0; i < nodeList.size(); i++) { if (nodeList[i].value == num && nodeList[i].father == -1) { return i; } } return -1;}void dfs(int index, vector<Node> &nodeList) { if (index == -1) { return; } for (int i = 0; i < 3; i++) { if (nodeList[index].son[i] == -1) { continue; } nodeList[nodeList[index].son[i]].code += (nodeList[index].code + to_string(i)); dfs(nodeList[index].son[i], nodeList); }}int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<Node> nodeList; for (int i = 0; i < n; i++) { int temp; cin >> temp; nodeList.push_back(Node(temp, -1)); } while (true) { vector<Node> temp(nodeList); sort(temp.begin(), temp.end(), cmp); if (temp[2].father == -1) { nodeList.push_back(Node(0, -1)); for (int i = 0; i < 3; i++) { nodeList[nodeList.size() - 1].value += temp[i].value; nodeList[nodeList.size() - 1].son[i] = getNode(temp[i].value, nodeList); nodeList[getNode(temp[i].value, nodeList)].father = nodeList.size() - 1; } continue; } else if (temp[1].father == -1) { nodeList.push_back(Node(0, -1)); for (int i = 0; i < 2; i++) { nodeList[nodeList.size() - 1].value += temp[i].value; nodeList[nodeList.size() - 1].son[i] = getNode(temp[i].value, nodeList); nodeList[getNode(temp[i].value, nodeList)].father = nodeList.size() - 1; } break; } else { break; } } dfs(nodeList.size() - 1, nodeList); for (int i = 0; i < n; i++) { cout << nodeList[i].value << "-" << nodeList[i].code << endl; } } return 0;}
笔试篇按上课讲课顺序,以章节为单位进行组织
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/125035.html
摘要:需要注意的是用矩阵形式如行列表示二维数组,是逻辑上的概念,能形象地表示出行列关系。再次强调二维数组名如是指向行的。一维数组名如是指向列元素的。 哈喽!这里是一只派大鑫,不是派大星。本着基础不牢,地动山摇的学习态度,从基础的C语言语法讲到算法再到更高级的语法及框架的学习。更好地让同样热爱编...
摘要:后来知道有了院赛,学长说刷院和杭电就可,我就一直刷院,到最后比赛前院的前五十道基本做完,杭电也弄了十来道,就这样草草参加比赛了。 博客主页: https://b...
摘要:泛型类型对象之间没有关系,就算之间互为父子关系,也没有任何关系。泛型类的静态上下文中类型变量无效。不能捕获或抛出泛型类的实例。 前言 作为一块后端没有太多经验的年糕,下周要考试了,所以我必须得来好好复习一下我的JAVA进阶课/(ㄒoㄒ)/~~。这个学期主要是学了: 泛型 反射 线程 JDBC JAVA WEB基础 Servlet session&cookie 过滤器&监听器 泛型 ...
摘要:一文带你快速学完数据库期末复习一数据库系统概述数据库系统的组成数据库的特点数据库的模式结构数据库建立的流程图关系数据库的一些术语关系数据库的数据完整性二数据库设计思路以及规范图数据库设计三范式三数据库语句的基础关系代数基 ...
摘要:正如我标题所说,简历被拒。看了我简历之后说头条竞争激烈,我背景不够,点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收,也不过个月的时间,但这都是建立在我过去一年的积累啊。 本文是 无精疯 同学投稿的面试经历 关注微信公众号:进击的java程序员K,即可获取最新BAT面试资料一份 在此感谢 无精疯 同学的分享 目录: 印象中的头条 面试背景 准备面试 ...
阅读 2029·2021-11-25 09:43
阅读 1061·2021-11-23 09:51
阅读 2270·2021-10-08 10:04
阅读 3157·2021-09-06 15:00
阅读 2625·2021-09-02 15:34
阅读 851·2021-08-16 10:57
阅读 1208·2019-08-30 12:46
阅读 825·2019-08-29 12:22