网上找的一些试题备用题目训练test

1、最小值(A)源程序名 A.? (pas,c,cpp)可执行文件名 A.exe输入文件名 A.in 输出文件名 A.out已知整数X和由0.9组成的字符串S，其中，字符串S可以分割成若干个非空子集S0、S1、S2、使S0+S1+S2+=S。我们再定义字符串S分割成M个部分形成的P(x)=a0+a1*x+a2*x2+aM*xM。这里ai对应着的就是si。例如字符串S=1204时，S可以分割成S=1+204（P(x)=1+204*x），或S=1+2+04（P(x)=1+2*x+4*x2）等。你的任务是写一个程序，在所有的分割方法中找出最小的一种。已知结果不会超过12*1014。输入第一行一个数字，表

2、示该输入文件中测试数据的个数。如果有几个最小值，你必须输出分割最少的。输出时，指数小的写在前。输出每一个测试数据，你都要输出一行P(K)的最小值。输出时，指数小的写在前。例如X=3，S=123时，有以下几种分割方法：S = 123P(X) = 123P(3) = 123S = 1 + 23P(X) = 1 + 23 * XP(3) = 70S = 12 + 3P(X) = 12 + 3 * XP(3) = 21S = 1 + 2 + 3P(X) = 1 + 2 * X + 3 * X2P(3) = 34最小值是21，所以答案便是12 + 3 * X。样例a.in31 12343 1231 10

3、01a.out1 + 2 * X1 + 3 * X2 + 4 * X312 + 3 * X11 + 1 * X1注意：输出时指数符号和数字（字母）间没有空格，其他符号和数字（字母）间有空格。关键顶点问题源程序名 e.? (pas,c,cpp)可执行文件名 e.exe输入文件名 pe.dat输出文件名 pe.out在十年里，人们意识到了数据通信的意义，大多数网络通信的设计和分析，经常用图示法模仿他们的布局，因为许多有关网络问题可以使用图论解决。像往常一样，一个信息网被图中的结点和边，相应模拟通信站和连接。一个网络G = (N,E)由顶点集合N以及边的集合E（一对结点表示）组成。如果考虑这些对无序

4、，那么我们就有了一个无向图，边连接两个顶点u和v表示成(u,v)。比如说，图3描述了一个网络G，它包含10个顶点和16条边。图3：一个网络G在一个网络G里，两个顶点的距离表示为，是从u到v的最短路经上的边数和。一个定点顺序，是一条从到的长k-1的路径，仅当这里所有从到都有边，。如果在点u到v中间不存在路径，那么。一条路径是顶点u到v的最短路径，仅当这条路径是所有从u到v的路径中的最短一条。一个网络，是如果这里对任意两个顶点都存在路径时的连接。结点w的退出，指的是w和所有它所连接的边从G图中删除。而且剩余的子图表示为G-w。一个结点w被叫做关键顶点，仅当G中存在两个顶点u和v，满足。这表示u到v

5、的距离，在将w从G中移除后增加了。因此，一个关键顶点就像通讯网络上的必须顶点，这样的结点的退出，会使剩下子网的通讯费用上升。例如，我们考虑图3的网络G。顶点v2是一个关键顶点，因为。当然，G包含的关键顶点集合是。假如我们有几个网络，每个网络连接包含最多n个顶点，这里。假如现在你被雇佣当一名网络管理员，你要分析通信费用。因此之故，你将感兴趣与找到网络中所有的关键顶点。特别的，你应该设计一个程序，对给出的每个网络，可以有效的计算出关键结点的总数。输入输入文件包含至少一个，最多六个网络（测试点）。每个测试点以一个正整数n开始，这里。接下来n行表示网络G的邻接矩阵。最后一个数据紧接着一个“0”，表示“输入的结束”。一个n个结点的邻接矩阵，表示形式为，是一个的01矩阵，当，则，否则。注意这里在01矩阵a的每行任意两个元素之间没有分隔符。例如，图3那幅图的邻接矩阵，在样例输入的测试点3中给出。输出对每个测试点，在一行里输出关键结点的总数。样例pe.dat301010101030111011101001100010001001000111100