2025年上海交通大学计算机复试上机考试题目解析

以下为2025年上海交通大学计算机专业硕士研究生复试中的上机真题内容整理与格式优化，包含两道典型算法题目的描述与样例说明。

最短路径问题

时间限制：1000 ms
内存限制：256 mb

设有N座城市，编号从0到N-1，共有M条双向道路连接这些城市。第K条道路（K从0开始计数）的长度为2^K。现需计算从编号为0的城市出发，到达其余各城市的最短距离。

若某城市无法从0号城市到达，则输出-1；若最短路径值过大，则结果对100000取模后输出。

输入格式说明

• 第一行包含两个正整数N和M（2 ≤ N ≤ 100，M ≤ 500），分别表示城市数量和道路条数。
• 接下来M行，每行给出两个整数，表示一条道路连接的两个城市编号。

输出格式说明

• 输出共N-1行，依次表示0号城市到编号为1、2、...、N-1城市的最短距离。
• 若不可达，对应行输出-1。
• 若距离过大，输出其对100000取模的结果。

样例输入与输出

样例输入：

4 4
1 2
2 3
1 3
0 1

样例输出：

8
9
11

棋盘遍历判定问题

时间限制：1000 ms
内存限制：256 mb

给定一个N×M的棋盘，一个棋子从左上角（即(0,0)位置）出发，要求判断是否存在一条路径，使得棋子恰好经过每一个格子一次，并最终回到起点。移动过程中不允许重复访问任何格子。

若存在这样的回路，输出字符'Y'；否则输出'N'。

输入格式说明

• 多组测试数据输入。
• 每组输入包含两个整数N和M（均不超过10），表示棋盘的行数和列数。

输出格式说明

• 对每组输入，输出一行结果：能完成遍历则输出Y，否则输出N。

样例输入与输出

样例输入：

1 2

样例输出：

N