历年中山大学计算机考研复试机试真题
本文整理中山大学计算机考研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
前缀字符串
题目描述
如果一个字符串 $ s1 $ 是由另一个字符串 $ s2 $ 的前面部分连续字符组成的，那么我们就说 $ s1 $ 就是 $ s2 $ 的前缀。
比如 $ ac $ 是 $ acm $ 的前缀，$ abcd $ 是 $ abcddfasf $ 的前缀，特别的 $ kdfa $ 是 $ kdfa $ 的前缀。
现在给你一些字符串，你的任务就是从这些字符串中找出一些字符串放到一个集合中，使得这个集合中任意一个字符串不是其他字符串的前缀，并且要使集合里的字符串尽可能的多。
输出这个集合中字符串的个数。
输入格式
有多组测试数据。
每组测试数据以一个整数 $ n $ 开头，随后有 $ n $ 个字符串。
当 $ n=0 $ 时表示输入结束。
$ 0 < n < 100 $，字符串长度不大于 $ 20 $。
输出格式
每组测试数据输出一个整数，即所求的最大值。
每组数据占一行。
输入样例
6
acm
yuou
yuoufsdaf
acmmmdf
acmm
fdsf
0
输出样例
3
统计二进制数中的 1 的个数
题目描述
整数在计算机中使用二进制的形式表示，如整数 $7$ 用二进制表示为：$111$，其中 $1$ 的个数为 $3$。
输入格式
输入一个整数
输出格式
输出该整数用二进制表示时，其中 $1$ 的个数
输入样例
7
输出样例
3
最长连号
题目描述
输入 $n$ 个正整数，（$1 \leq n \leq 10000$），要求输出最长的连号的长度。
（连号指从小到大连续自然数）
输入格式
第一行，一个数 $n$；
第二行，$n$ 个正整数，之间用空格隔开。
输出格式
一个数，最长连号的个数。
输入样例
10
3 5 6 2 3 4 5 6 8 9
输出样例
5
最小生成树
题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 $ orz $。
输入格式
第一行包含两个整数 $ N $, $ M $，表示该图共有 $ N $ 个结点和 $ M $ 条无向边。
接下来 $ M $ 行每行包含三个整数 $ X_i $, $ Y_i $, $ Z_i $，表示有一条长度为 $ Z_i $ 的无向边连接结点 $ X_i $, $ Y_i $。
$ 1 \leq N \leq 5000 $，$ 1 \leq M \leq 2 \times 10^5 $。
输出格式
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。
如果该图不连通则输出 $ orz $。
输入样例
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出样例
7
排队
题目描述
N个小朋友，编号 $1 \sim N$，要排成一队。
在安排每个人的顺序时，有 M个要求，每个要求包含两个整数 $a,b$，表示小朋友 $a$ 要排在小朋友 $b$ 的前面。
请你找出符合所有要求的排队顺序。
保证至少存在一个符合条件的顺序。
当符合条件的排队顺序不唯一时，编号更小的小朋友尽量更靠前。
输入格式
第一行包含整数 $N,M$。
接下来 $M$ 行，每行包含两个整数 $a,b$。
输出格式
按排好队列从前到后的顺序在一行内输出每个小朋友的编号。
输入样例1
4 3
1 2
2 3
4 3
输出样例1
1 2 4 3