2019年中山大学数据科学与计算机学院研究生统考机试

2019年中山大学数据科学与计算机学院研究生机试考试回忆录中提到共有十道题目：
1. 继承 题目涉及三个类的关系（animal、cat、dog），cat和dog继承animal，并要求完成相关函数定义；
2. 多态 题目涉及构造函数和析构函数调用时打印提示信息；
3. 不连续1的子串 计算长度为n且不含连续两个1的0-1串的数量；
4. 拓扑排序 给定点与边关系并输出拓扑排序结果；
5. 循环移位 判断一个字符串是否是另一个字符串循环移位后的子串；
6. 碰撞 实现哈希冲突处理（链接法）；
7. 嵌套 判断一个字符串能否形成不相交且不重复的配对；
8. A=BB 判断是否存在子串由两个相同字符组成；
9. 机器人 计算机器人从当前位置到出口经过多少个岔路口（保证唯一路径）；
10. 括号匹配 问题较难且较长，在当时考试中未细致回忆。
本文仅作为学习参考用途。

2019年中山大学数据科学与计算机学院研究生统考机试题目回忆

本文梳理了2019年中山大学数据科学与计算机学院研究生应试机试题目，并旨在为即将参加此类考试的学生提供参考价值。具体来说，这些题目涵盖了数据结构、算法设计、编程语言原理以及软件工程的基础知识。机试共十道题。

1. 继承

包含三个类：animal、cat和dog。其中cat和dog继承自animal。在构造实例对象时使用d = new Dog()或c = new Cat()。并要求完成相关函数定义。

2. 多态

给定多个类A、B、C以及derivedA、derivedB1、derivedB2等，在每个类的构造函数和析构函数调用时会输出一些相关信息。通过这些输出的信息推断各类之间的继承关系，并完成类的声明。这并不是很难的任务，但如果未系统复习过这部分知识的话，则会感到有一定的难度。

这段文字的主要目的是要求编写一段代码或逻辑流程图，在特定条件下执行特定操作并分析结果以确定程序结构与依赖关系。

3. 不连续1的子串

例如当n=3时，请计算并列举出所有符合条件的一组二进制字符串数目如下：包括{[}""""""""" """""{}等五种情况。”

4. 拓扑排序

经典的拓扑排序问题中，请给定顶点集合及其连接关系，并求解相应的拓扑顺序；若有多个可能的topological order，请按照字典 order进行排列

5. 循环移位

给定字符串A和B，请判定字符串A是否为由字符串B进行循环移位操作所得的结果。例如，在以下情况中：当A等于"ABC"且B等于"BCDEFA"时，则上述判定结果成立。

6. 碰撞

给定Hash函数，要求用链接法处理冲突，实现插入和查询等功能。

7. 嵌套

给定一个字符串S，请判断是否可以构造出一组互不重叠且互不交叉的配对结构。对于该问题的一个可能解法是通过动态规划的方式进行求解。具体来说，在每一步操作中我们需要考虑以下几种情况：第一种情况是选择当前字符与下一个字符进行配对；第二种情况是跳过当前字符继续寻找下一个可能的位置进行配对；第三种情况则是选择当前字符与后续某个位置上的字符进行跨步配
【对于上述问题的一个典型实例是当输入序列长度为偶数时可以通过回溯算法找到所有可能的有效解；但对于长度较大的序列回溯算法可能会导致较高的计算复杂度因此需要寻找一种更为高效的解决方案

8. A=BB

给定输入字符串 A ,请判断是否存在其子串是由两个相同子串 B+B 组成的结构（其中 B 未给出）。例如，在输入字符串中取值为 A 的情况下（即 A="ababc"），我们可以发现其包含一个特定的子串 A'=“abab”这一结构是由两个连续的 ab 组成的（即 B="ab"）。同样地，在输入中取值为 A 的情况（即" A=zaat "），我们发现其中包含一个长度较短的子串" A'=‘aa’"这一结构也是由两个连续的"a"组成的（即 B="a"）。

9.机器人

假设有一个二维数组用于表示地图，在这个数组中不同的符号分别代表障碍物、通路、唯一的一个机器人起始位置以及唯一的一个目标点出口。我们的任务是计算机器人从当前位置到目标点的道路路径上经过的分岔点数量。该地图确保机器人从起始位置到目标点的道路是唯一的。

10. 括号匹配

这道题目难度较大也很长 不算特别厉害的人因此在考试时我对这道题并没有深入研究 记得不是很清楚了实际在场能够解答的人并不多 不回忆了哈哈哈哈哈哈= =|||

这篇文章旨在帮助以后考研的同学复习备考。每年的真题不可能完全相同, 但可以通过本篇文章获得一个大致的方向指引。
本文仅作为参考资料使用, 不具备其他用途。