中科大USTC计算机复试上机题，基于C语言实现，个人练习用.zip

# ustc-retest 基于C语言实现的部分中科大计算机复试上机题，个人练习用。本人不是专业算法，也不常用C语言，可能代码不太规范。 ## 详细 2015： 4. 求图中结点1经过结点k到结点n的最短路径，用dijkstra算法实现 2016： 1. 10进制转16进制 2. 设计一种类似微信的红包分配算法，需要注意浮点数运算不精确和如何使每个红包公平分配的问题 3. 使用二分法求多项式的一个解，可根据零点定理求近似解 4. 已知二叉树的前序和后序遍历，求一种中序遍历 2017： 1. 将一个句子中每个单词的首字母大写，并将单词间的多个空格转为一个空格输出 2. 求1~1000内的完数和盈数 3. 求最长等差子序列，这里用矩阵记录两数的差，之后用动态规划求解 4. 判断一个图中是否存在一个顶点，当顶点删除后图就不再连通，这里用dfs实现判断图是否连通的方法，之后逐一删除节点来判断 2018： 1. 已知2000.1.1是星期六，判断n天后的年月日和星期 2. 根据每个学生的签到和签退记录，计算逗留时间最长的学生 3. 给定任意几种面值的钞票，给出凑出某个面值的所需钞票数量最少的方法，只需优先考虑面值最大的钞票即可 4. 求两字符串最长的公共子序列长度，这里用矩阵法求解 2019： 1. 验证身份证是否有效，注意身份证号不一定全为数字 2. 求一个数是否能构成2^m+2^n的形式，只需判断该数的二进制中1的数量是否为2即可 3. 计算前缀表达式 4. 给出一个集合的所有划分方式，用动态规划求解：每个元素可被分为之前的一个子集或一个新子集 5. 根据二叉树的层次遍历求树的直径，详细可看[anyin233的解答](https://anyin233.github.io/2022/03/02/%E4%B8%AD%E7%A7%91%E5%A4%A72019-5/)先记录每个节点的高度和次高度以及对应得子节点，之后计算每个节点来说，如果父节点的高度对应的路径经过该节点，就将父节点的次高度与该节点的高度比较，如果更大，就将节点的高度的对应的节点更换为父节点的高度和节点；如果更小，就将父节点的次高度与该节点的次高度比较，如法炮制。如果父节点的高度对应的路径不经过该节点，就将父节点的高度与该节点的高度和次高度相比较，如法炮制。经过上述步骤，每个节点就保留了树的叶子节点经过该节点到另一叶子节点的最大距离，之后遍历每个节点找到最大距离中的最大值即直径。 2020： 1. 求两个正整数的最大公约数 2. 求无序数组中第k大的数 3. 求若干个数的最大组合数，这里要注意排序方法，对于两数如78和728，可将其转化为字符串后按两种次序拼接，得到78728和72878，之后比较哪个大，大的排前面 2021: 1. 计算$sum_{k=1}^n\frac{1}{k}$，注意阶乘溢出，不要直接计算k! 2. 计算海明距离，使用位运算更加高效 3. 计算4个数是否能组成+和*组成24，这里使用动态规划，每次选择两个数相加或相乘，直到只剩下1个数为止 4. 求10进制数的7进制