2023.03全国青少年软件编程（C语言）等级考试试卷（八级）.docx
青少年软件编程（C语言）等级考试试卷（八级）分数：100题数：4一、编程题（共4题，共100分）1 .最短路径问题平面上有n个点（n<=100）,每个点的坐标均在1000010000之间。其中的一些点之 间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点 间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。时间限制：1000内存限制：131072输入共n+m+3行，其中：第一行为整数n。第2行到第n+1行（共n行），每行两个整 数x和y,描述了一个点的坐标。第n+2行为一个整数m,表示图中连线的个数。此 后的m行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间 有连线。最后一行：两个整数s和t,分别表示源点和目标点。输出仅一行，一个实数（保留两位小数），表示从S至lt的最短路径长度。样例输入50 02 03 20 24 151 22 33 44 55 51 5样例输出3.41 试题编号：20230318-8-01试题类型：编程题标准答案：试题难度：一般试题解析：展示地址：点击浏览考生答案：（此题已作答）考生得分：0是否评分：已评分评价描述：2 . Freda的越野跑Freda报名参加了学校的越野跑。越野跑共有N人参加，在一条笔直的道路上进行。这 N个人在起点处站成一列，相邻两个人之间保持一定的间距。比赛开始后，这N个人同 时沿着道路向相同的方向跑去。换句话说，这N个人可以看作x轴上的N个点，在比 赛开始后，它们同时向x轴正方向移动。假设越野跑的距离足够远，这N个人的速度各不相同且保持匀速运动，那么会有多少对 参赛者之间发生“赶超”的事件呢？ 时间限制:1000 内存限制：262144输入第一行1个整数No第二行为N个非负整数，按从前到后的顺序给出每个人的跑步速度。对于 50%的数据，2v=Nv=1000。对于 100%的数据，2<=N<=1 OOOOOo输出一个整数，表示有多少对参赛者之间发生赶超事件。样例输入51 3 10 8 5样例输出提示我们把这5个人依次编号为A,B,C,D,E,速度分别为1,3,10,8,5。在跑步过程中： B,C,D,E均会超过A,因为他们的速度都比A快；C,D,E都会超过B,因为他们的速度 都比B快；C,D,E之间不会发生赶超，因为速度快的起跑时就在前边。试题编号：20230318-8-02试题类型：编程题标准答案：试题难度：一般试题解析：展示地址：点击浏览考生答案：(此题已作答)考生得分：0是否评分：已评分评价描述：3 .社交网络随着社交平台的兴起，人们之间的沟通变得越来越密切。通过Facebook的分享功能, 只要你是对方的好友，你就可以转发对方的状态，并且你的名字将出现在“转发链”上。 经过若干次转发以后，很可能A分享了一条好友C的状态，而C的这条状态实际上是 分享B的，但A与B可能并不是好友，即A通过C间接分享了 B的状态。给定你N个人之间的好友关系，好友关系一定是双向的。只要两个人是好友，他们就可 以互相转发对方的状态，无论这条状态是他自己的，还是他转发了其他人的。现在请你 统计，对于每两个人，他们是否有可能间接转发对方的状态。时间限制：1000内存限制：262144输入第一行1个整数N (1<=N<=300) o接下来N行每行N个整数，表示一个N*N的01 矩阵，若矩阵的第i行第j列是1,表示这两个人是好友，o则表示不是好友。保证矩 阵的主对角线上都是1,并且矩阵关于主对角线对称。输出一个N*N的01矩阵，若矩阵的第i行第j列是1,表示这两个人可能间接转发对方的状 态，0则表示不可能。样例输入51100011100011000001100011样例输出111001110011100 00011 00011提示在输入数据中，1与2是好友，2与3是好友，4与5是好友。因此1、2、3有可能互 相转发状态；4、5有可能互相转发状态。这两组人之间则不可能。试题编号：20230318-8-03试题类型：编程题标准答案：试题难度：一般试题解析：展示地址：点击浏览考生答案：(此题已作答) 考生得分：25 是否评分：已评分 评价描述： 考生答案：#include<bits/stdc+.h> using namespace std; int n,fa310;chara310310;int find(int x)(if(x = fax)( return x; return find(fax);)void merge(int x,int y)( if(find(x) = find(y)( return ;fafind(x) = find(y);)int main()cin » n;for(int i = l;i <= n;i+)fai = i;for(int i = l;i <= n;i+)(for(int j = l;j <= n;j+)(cin»aij;if(aij = 49 && i !=j)(merge(ij);)for(int i = l;i <= n;i+)(for(int j = l;j <= n;j+)(if(find(i) = find(j)(cout« 1;)else(cout« 0;)cout«'n')4.旅行转眼毕业了，曾经朝夕相处的同学们不得不都各奔东西，大家都去了 不同的城市开始新的生活。在各自城市居住了一段时间后，他们都感 到了一些厌倦，想去看看其他人的生活究竟如何，于是他们都选择到 另一个同学所在城市去旅游，并且希望旅游的城市各不相同，他们想 知道有多少种不同的方案，可是数量实在太多了，他们无法计算出来, 你能帮助他们吗。时间限制：10000内存限制：131072输入一个正整数n(nv200),表示人数。输出一个数，表示有多少不同的方案。样例输入样例输出提示有如下两种方案：同学1去同学2的城市，同学2去同学3的城市，同学3去同学1 的城市；同学1去同学3的城市，同学3去同学2的城市，同学2去同学1的城市。试题编号：20230318-8-04试题类型：编程题标准答案：试题难度：一般试题解析：展示地址：点击浏览考生答案：考生得分：0是否评分：已评分评价描述：
