2014年网研上机题目

1、Problem A.分数加法题目描述 求2-a+2-b,其中a和b均为正整数，结果请用最简分数表示。输入格式第一行为测试数据的组数 T (1二T=4O0。请注意，任意两组测试数据之 间是相互独立的。每组测试数据一行，包含两个整数 a 和 b( 2=a,b=20)。输出格式对于每组测试数据，在一行内输出结果，分子和分母用“/隔”开。输入样例22 43 2输出样例5/163/8Problem B最小堆题目描述给定一棵带权二叉树，请判断它是不是一个最小堆。一棵二叉树是一个最小堆，当且仅当对于树上任意一个节点，它的权值都 小于或等于以它为根的子树中的所有权值。输入格式输入数据第一行是一个整数 T (1

2、=Tv=1O0，表示测试数据的组数。对于每组测试数据：第一行是一个整数N (1=Nv=1O0,表示树的节点个数。接下来一行包含 N个正整数，第i个整数valuei(1二valuei=1000表示编号i 的点的权值。接下来N-1行，每行两个整数u和v (1二u, v=N, u!=V，表示节点u是 节点 v 的父节点。测试数据保证给定的一定是一棵二叉树,并且节点 1 是树的根结点。输出格式对于每组测试数据，如果给定的树是一个最小堆则输出Yes否则输出No。输入样例3110310 5 31 21 351 2 3 4 51 31 22 42 5输出样例YesNoYesProblem C进程管理题目描述

3、在操作系统中，进程管理是非常重要的工作，每个进程都有唯一的进程标识（PID）。每个进程都可以启动子进程，此时我们称它为其子进程的父进程， 除了 PID为0的进程之外，每个进程有且只有一个父进程，在这个任务中，你 需要实时维护操作系统运行中的三个基本操作：1. FORK PID1 PID2标识为PID1的进程启动了一个标识为 PID2的子进程。2. KILL PID结束标识为PID的进程。请注意，与此同时所有 PID的子进程也 将同时结束。如果PID是不存在或已经结束的进程，则不做任何操作。3. QUERY PID查询标识为PID的进程是否仍然存在。在初始状态下，系统只开启了 PID为0的进程，

4、并且在任何情况下该进程 不会结束。输入格式输入的第一行是一个整数 T （T=50） ，表示输入的数据组数。每组测试数据的第一行是一个整数 N （1=Nv=1O0）,表示操作的数量。没下来 N 行，每行按照上面的描述给出每个操作，输入保证所有的进程的PID都不相同，且一个进程结束后不会被重新启动，所有PID都是1,10 0之间的整数。输出格式5FORK 0 1QUERY 1KILL 1QUERY 1QUERY 2输出样例YesNoNoYesProblem D.网络传输题目描述网络的高效互联与智能传输是提升海量用户服务请求映射效率的重要措 施。在这个任务中，你要用最少的传输时间，将特定的数据源发送

5、到指定的网 络节点中。我么给定的网络一共包含 N个节点（从1到N编号），其中节点1为数据 源。网络中有M条无向边（u,v,w），表示一条传输线连接节点u和节点V，且 数据通过这条传输线的平均时间为 w。由于传送机制的限制，当一个节点接收 到数据之后，它只能选择与它互连的一个节点，并将数据转发到该节点。节点 1 在初始化时只会发送一次数据，但在传输过程中它可以作为转发节点。网络中有k个目标节点，你需要计算出该数据从节点 1传送到所有K歌节 点所需要的最短时间。注意目标节点可以按任意顺序进行传送，数据也可以多 次经过同一节点。输入格式输入数据第一行是一个整数 T(T=5) ，表示测试数据的组数。对于每组测 试数据：第一行是三个正整数 N,M,K (2=Nv=100Q 1二M二N(N-1)/2, K=10,分 别表示节点数，边数和目标节点数。接下来