《清华大学06-12年上机试题-.docx》由会员分享，可在线阅读，更多相关《清华大学06-12年上机试题-.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2012年上机试题1.求最大最小数题目描述：输入N个(N=l0000)数字，求出这N个数字中的最大值和最小值。每个数字的 绝对值不大于1000000 o输入：输入包括多组测试用例，每组测试用例由一个整数N开头，接下去一行给出N个 整数。输出：输出包括两个整数，为给定N个数中的最大值与最小值。样例输入：51 2 3 4 533 7 8样例输出：5 18 3.玛雅人的密码题目描述：玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一 个长度为N的字符串，(2=N=13)该字符串中只含有0,1,2三种数字，问这个 字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如0
2、2120经过 一次移位，可以得到20120,01220,0221002102,其中20120符合要求，因此输出为 1.如果无论移位多少次都解不开密码，输出-1。输入：输入包含多组测试数据，每组测试数据由两行组成。第一行为一个整数N,代表字符串的长度(2=N=13) o第二行为一个仅由()、1、2组成的，长度为N的字符串。输出：对于每组测试数据，假设可以解出密码，输出最少的移位次数；否那么输出-1。样例输入：输入:一个1000位（即10人999）以内的十进制数。输出：输入的十进制数的二进制逆序数。样例输入：173样例输出：181.最小邮票数题目描述：有假设干张邮票，要求从中选取最少的邮票张数凑成
3、个给定的总值。如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，那么使用3张邮 票：3分、3分、4分即可。输入：有多组数据，对于每组数据，首先是要求凑成的邮票总值M, M100.然后是 一个数N, N 20,表示有N张邮票。接下来是N个正整数，分别表示这N张邮 票的面值，且以升序排列。输出：对于每组数据，能够凑成总值M的最少邮票张数。假设无解，输出0。样例输入：1051 3 3 3 4样例输出：32006年上机试题1 . N的阶乘题目描述：输入一个正整数N,输出N的阶乘。输入:正整数 N(0=N=1000)输出：输入可能包括多组数据，对于每一组输入数据，输出N的阶乘样例输入：4515
4、样例输出：24120.最大序列和题目描述：给出一个整数序列S,其中有N个数，定义其中一个非空连续子序列T中所有数 的和为T的“序列和”。对于S的所有非空连续子序列T,求最大的序列和。变量条件:N为正整数,N1 ()0000(),结果序列和在范围(2人63,2人63-1)以内。输入：第一行为一个正整数N,第二行为N个整数，表示序列中的数。输出：输入可能包括多组数据，对于每一组输入数据，仅输出一个数，表示最大序列和。样例输入：515-32461 -2 3 4 -10 64-3 1 -2 -5样例输出：97-13.二叉树遍历题目描述：二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟
5、，然后遍历其左子树，最后遍历其右子树： 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中 序遍历能够唯一确定后序遍历）。输入：两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示：A, B, C.最多26个结点。输出：输入样例可能有多组，对于每组测试样例，输出一行，为后序遍历的字符串。样例输入：ABCBACFDXEAGXDEFAG样例输出：BCAXEDGAF502120 样例输出：1
6、3.求1和2的个数题目描述：给定正整数N,函数F(N)表示小于等于N的自然数中1和2的个数之和，例如： 1,2,3,4,5,6,7,8,9,10序歹I中1和2的个数之和为3,因此F(10)=3。输入N,求F(N) 的值,I=N=10AI00(10 的 100 次方)假设 F(N)很大，那么求 F(N)mod20123 的值。 输入：输入包含多组测试数据，每组仅输入一个整数N。输出：对于每组测试数据，输出小于等于N的自然数中1和2的个数之和，且对20123 取模。样例输入：1011 样例输出：35 提示：建议用scanf (%s)输入,而不建议用gets()!2011年上机试题1.最小花费题目描
7、述：在某条线路上有N个火车站，有三种距离的路程，LL L2, L3,对应的价格为CLC2C3.其对应关系如下：距离s票价0S=L1ClLIS=L2C2L2S=L3C3输入保证(KLlL2L310A9,0C1C2C3 1 (”9。每两个站之间的距离不超过L3。当乘客要移动的两个站的距离大于L3的时候，可以选择从中间一个站下车，然后 买票再上车，所以乘客整个过程中至少会买两张票。现在给你一个LI, L2, L3, Cl, C2,C3o然后是A B的值，其分别为乘客旅程的 起始站和终点站。然后输入N, N为该线路上的总的火车站数目，然后输入N-1个整数，分别代表从 该线路上的第一个站，到第2个站，第
8、3个站，第N个站的距离。根据输入，输出乘客从A到B站的最小花费。输入：以如下格式输入数据：Li L2 L3 Cl C2 C3A BNaf2al3aN输出：可能有多组测试数据，对于每一组数据，根据输入，输出乘客从A到B站的最小花费。样例输入：12 3 12 31 223 样例输出：4 2.约数的个数题目描述：输入n个整数，依次输出每个数的约数的个数输入：输入的第一行为N,即数组的个数(N=1000)接下来的1行包括N个整数，其中每个数的范围为(lv=Numv=1000000000) 当N=0时输入结束。输出:可能有多组输入数据，对于每组输入数据，输出N行，其中每一行对应上面的一个数的约数的个数。
9、样例输入：51 3 4 6 12样例输出：123463.剩下的树题目描述：有一个长度为整数L(l=L=100()0)的马路，可以想象成数轴上长度为L的一个 线段，起点是坐标原点，在每个整数坐标点有一棵树，即在0,1,2,，L共L+1个 位置上有L+1棵树。现在要移走一些树，移走的树的区间用一对数字表示，如100 20()表示移走从 100到200之间(包括端点)所有的树。可能有M(l=M=100)个区间，区间之间可能有重叠。现在要求移走所有区间 的树之后剩下的树的个数。输入：两个整数 L(l=L=10000)和 M(l=M=100)o接下来有M组整数，每组有一对数字。输出：可能有多组输入数据，
10、对于每组输入数据，输出个数，表示移走所有区间的 树之后剩下的树的个数。样例输入：500 3100 200150 300470 471样例输出：2982010年上机试题1 .特殊乘法题目描述：写个算法，对2个小于1000000000的输入，求结果。特殊乘法举例：123 *45= 1 *4 +1 *5 +2*4 +2*5 +3*4+3*5输入：两个小于1000000000的数输出：输入可能有多组数据，对于每一组数据，输出Input中的两个数按照题目要求的方 法进行运算后得到的结果。样例输入：123 45样例输出：54.整数拆分题目描述：一个整数总可以拆分为2的品的和，例如：7=1+2+47=1+2
11、+2+27=1+1+1+47=1+1+1+2+27=1 + 14-1 + 1 + 1+27=1 + 1 + 1 + 14-1 + 1 + 1总共有六种不同的拆分方式。再比方：4 可以拆分成：4 = 4, 4=1+ 1 + 1 + 1, 4 = 2 + 2, 4=1 + 1+2。用f(n)表示n的不同拆分的种数，例如f(7)=6.要求编写程序，读入n(不超过1000000),输出f(n)%1000000000。输入：每组输入包括一个整数：N(K=N=1000000)o输出:对于每组数据,输出f(n)%l()()(X)(X)()()()0样例输入:样例输出：6.求 root(N, k)题目描述：N
12、k 时，root(N,k) = N,否那么，root(N,k) = root(N,k)o N为 N 的 k 进制表示的各 位数字之和。输入x,y,k,输出root(xAy,k)的值(这里人为乘方，不是异或)， 2=k=16, 0x,y=2000000(X)0) 输入：每组测试数据包括一行，x(0x2(X)0000000), y(0y20(X)000000), k(2=k= 2。求第 k 个数对 10000 的模。输入：输入包括5个整数：a。、al、p、q、k。输出：第k个数a(k)对10000的模。样例输入：20 1 1 14 5 样例输出：8359.代理服务器题目描述：使用代理服务器能够在一
13、定程度上隐臧客户端信息，从而保护用户在互联网上 的隐私。我们知道n个代理服务器的IP地址，现在要用它们去访问m个服务器。 这m个服务器的IP地址和访问顺序也已经给出。系统在同一时刻只能使用一个 代理服务器，并要求不能用代理服务器去访问和它IP地址相同的服务器（不然客 户端信息很有可能就会被泄露）。在这样的条件下，找到一种使用代理服务器的方 案，使得代理服务器切换的次数尽可能得少。输入：每个测试数据包括n + m + 2行。第1行只包含一个整数n,表示代理服务器的个数。第2行至第n+l行每行是一个字符串，表示代理服务器的IP地址。这n个IP 地址两两不相同。第n + 2行只包含一个整数m,表示要
14、访问的服务器的个数。第n + 3行至第n + m + 2行每行是一个字符串，表示要访问的服务器的IP地 址，按照访问的顺序给出。每个字符串都是合法的IP地址，形式为“xxx.yyy.zzz.www，其中任何一局部均 是0-255之间的整数。输入数据的任何行都不包含空格字符。其中，l=n=1000, l=m=5000a输出：可能有多组测试数据，对于每组输入数据，输出数据只有一行，包含一个整数 s,表示按照要求访问服务器的过程中切换代理服务器的最少次数。第一次使用的 代理服务器不计入切换次数中。假设没有符合要求的安排方式，那么输出-1。样例输入：2166. 111.4. 100162. 105.
15、131. 113202. 112. 128. 69672. 14. 235. 104166. 111.4. 100207.46. 19. 190202. 112. 128. 69162. 105. 131. 113118.214. 226. 52样例输出：1 2008年上机试题2 .手机键盘题目描述：按照手机键盘输入字母的方式，计算所花费的时间如：a,b,c都在“1”键上，输入a只需要按一次，输入c需要连续按三次。如果连续两个字符不在同一个按键上，那么可直接按，如：ad需要按两下，kz需要按6下如果连续两字符在同一个按键上，那么两个按键之间需要等一段时间，如ac,在按了 a之后，需要等一会儿才
16、能按c。现在假设每按一次需要花费一个时间段，等待时间需要花费两个时间段。现在给出一串字符，需要计算出它所需要花费的时间。输入：一个长度不大于100的字符串，其中只有手机按键上有的小写字母输出：输入可能包括多组数据，对于每组数据，输出按出I叩ut所给字符串所需要的时间样例输入：bobWWW样例输出：,7.进制转换题目描述：将M进制的数X转换为N进制的数输出。输入：输入的第一行包括两个整数：M和N(2=M,N1)的质因数的个数。相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。输入：可能有多组测试数据，每组测试数据的输入是一个正整数N, (lvNvl(F9)。输出：对于每组数据，输出N的质因数的个数。样例输入：120样例输出：5提示：注意：1不是N的质因数；假设N为质数，N是N的质因数。2. 10进制VS 2进制题目描述：对于一个十进制数A,将A转换为二进制数，然后按位逆序排列，再转换为十 进制数B,我们乘B为A的二进制逆序数。例如对F十进制数173,它的二进制形式为10101101,逆序排列得到10110101,其十进制数为。1, 181即为173的二进制逆序数。