发帖
雷达卡
2025年复旦大学计算机复试上机真题解析
中位数问题
题目说明：
时间限制：1000 毫秒
内存限制：32768 KB
定义：将一组数据按照升序排列后，位于正中间位置的数值即为中位数。若数据个数为奇数，则取中间那个数；若为偶数，则取最中间两个数的平均值，并对结果进行向下取整（无需使用浮点运算）。
输入格式：
程序需处理多组测试用例。每组数据首行为整数 N，表示该组数据包含的整数个数（1 ≤ N ≤ 10000）。随后 N 行每行一个整数，代表数据元素。当 N = 0 时，输入结束。
输出格式：
对于每一组数据，输出其对应的中位数（向下取整后的整数结果），每组一行。
样例输入：
复制：
4
10
30
20
40
3
40
30
50
4
1
2
3
4
样例输出：
复制：
25
40
2
二叉搜索树构造与父节点查询
题目说明：
时间限制：1000 毫秒
内存限制：256 MB
给定一个长度为 n 的排列 P，其中包含从 1 到 n 的所有整数各一次。按顺序将这些元素逐个插入一个初始为空的二叉搜索树（左子树小于根，右子树大于根）。要求输出每个节点对应元素在最终树结构中的父节点值。特别规定：根节点的父节点视为 0。
例如，在样例中形成的二叉搜索树如下：
- 元素 1 的父节点是 2
- 元素 2 是根节点，故其父节点为 0
- 元素 3 的父节点是 2
- 元素 4 的父节点是 5
- 元素 5 的父节点是 3
输入格式：
第一行是一个整数 n（1 ≤ n ≤ 10^5），表示排列的长度。
第二行是 n 个整数 p, p, ..., p，表示依次插入的排列元素。
输出格式：
输出 n 个整数 a, a, ..., a，其中 a 表示数字 i 所在节点的父节点元素。根节点对应的父节点输出为 0。
样例输入：
复制：
5
2 3 5 1 4
样例输出：
复制：
2 0 2 5 3
京公网安备 11010802022788号
