上海交通大学机试真题.doc

2007年上海交通大学计算机研究生机试真题1036: Old Bill题目描述 Among grandfathers papers a bill was found. 72 turkeys $_679_ The first and the last digits of the number that obviously represented the total price of those turkeys are replaced here by blanks (denoted _), for they are faded and are illegible. What are the two faded digits and what was the price of one turkey? We want to write a program that solves a general version of the above problem. N turkeys $_XYZ_ The total number of turkeys, N, is between 1 and 99, including both. The total price originally consisted of five digits, but we can see only the three digits in the middle. We assume that the first digit is nonzero, that the price of one turkeys is an integer number of dollars, and that all the turkeys cost the same price. Given N, X, Y, and Z, write a program that guesses the two faded digits and the original price. In case that there is more than one candidate for the original price, the output should be the most expensive one. That is, the program is to report the two faded digits and the maximum price per turkey for the turkeys.输入 The first line of the input file contains an integer N (0N100), which represents the number of turkeys. In the following line, there are the three decimal digits X, Y, and Z., separated by a space, of the original price $_XYZ_.输出 For each case, output the two faded digits and the maximum price per turkey for the turkeys.样例输入726 7 952 3 7780 0 5样例输出3 2 5119 5 1847502007年上海交通大学计算机研究生机试真题1037: Powerful Calculator题目描述 Today, facing the rapid development of business, SJTU recognizes that more powerful calculator should be studied, developed and appeared in future market shortly. SJTU now invites you attending such amazing research and development work. In most business applications, the top three useful calculation operators are Addition (+), Subtraction (-) and Multiplication () between two given integers. Normally, you may think it is just a piece of cake. However, since some integers for calculation in business application may be very big, such as the GDP of the whole world, the calculator becomes harder to develop. For example, if we have two integers 20 000 000 000 000 000 and 4 000 000 000 000 000, the exact results of addition, subtraction and multiplication are: 20000000000000000 + 4000000000000000 = 24 000 000 000 000 000 20000000000000000 - 4000000000000000 = 16 000 000 000 000 000 20000000000000000 4000000000000000 = 80 000 000 000 000 000 000 000 000 000 000 Note: SJTU prefers the exact format of the results rather than the float format or scientific remark format. For instance, we need 24000000000000000 rather than 2.41016. As a programmer in SJTU, your current task is to develop a program to obtain the exact results of the addition (a + b), subtraction (a - b) and multiplication (a b) between two given integers a and b.输入Each case consists of two separate lines where the first line gives the integer a and the second gives b (|a| 10400 and |b| 10400).输出 For each case, output three separate lines showing the exact results of addition (a + b), subtraction (a - b) and multiplication (a b) of that case, one result per lines. 样例输入200000000000000004000000000000000样例输出2400000000000000016000000000000000800000000000000000000000000000002007年上海交通大学计算机研究生机试真题1038: Sum of Factorials题目描述 John von Neumann, b. Dec. 28, 1903, d. Feb. 8, 1957, was a Hungarian-American mathematician who made important contributions to the foundations of mathematics, logic, quantum physics, meteorology, science, computers, and game theory. He was noted for a phenomenal memory and the speed with which he absorbed ideas and solved problems. In 1925 he received a B.S. diploma in chemical engineering from Zurich Institute and in 1926 a Ph.D. in mathematics from the University of Budapest, His Ph.D. dissertation on set theory was an important contributions to the subject. At the age of 20, von Neumann proposed a new definition of ordinal numbers that was universally adopted. While still in his twenties, he made many contributions in both pure and applied mathematics that established him as a mathematician of unusual depth. His Mathematical Foundation of Quantum Mechanics (1932) built a solid framework for the new scientific discipline. During this time he also proved the mini-max theorem of GAME THEORY. He gradually expanded his work in game theory, and with coauthor Oskar Morgenstern he wrote Theory of Games and Economic Behavior (1944). There are some numbers which can be expressed by the sum of factorials. For example 9, 9 = 1! + 2! + 3! . Dr. von Neumann was very interested in such numbers. So, he gives you a number n, and wants you to tell whether or not the number can be expressed by the sum of some factorials.Well, it is just a piece of case. For a given n, you will check if there are some xi, and let n equal to t (上标) i=1（下标） xi! (t1, xi0, xi = xj i = j) t 即 xi! (t1, xi0, xi = xj i = j) i=1 If the answer is yes, say YES; otherwise, print out NO.输入 You will get a non-negative integer n (n1,000,000) from input file.输出 For the n in the input file, you should print exactly one word (YES or NO) in a single line. No extra spaces are allowed.样例输入92样例输出YESYES2007年上海交通大学计算机研究生机试真题1039: Zero-complexity Transposition题目描述You are given a sequence of integer numbers. Zero-complexity transposition of the sequence is the reverse of this sequence. Your task is to write a program that prints zero-complexity transposition of the given sequence.输入For each case, the first line of the input file contains one integer n-length of the sequence (0 n 10 000). The second line contains n integers numbers-a1, a2, , an (-1 000 000 000 000 000 ai 1 000 000 000 000 000).输出For each case, on the first line of the output file print the sequence in the reverse order.样例输入5-3 4 6 -8 9样例输出9 -8 6 4 -32008年上海交通大学计算机研究生机试真题1040: Prime Number时间限制: 1 Sec内存限制: 32 MB提交: 136解决: 57题目描述Output the k-th prime number.输入k10000输出The k-th prime number.样例输入37样例输出5172008年上海交通大学计算机研究生机试真题1041: Simple Sorting时间限制: 1 Sec内存限制: 32 MB提交: 380解决: 140题目描述You are given an unsorted array of integer numbers. Your task is to sort this array and kill possible duplicated elements occurring in it.输入For each case, the first line of the input contains an integer number N representing the quantity of numbers in this array(1N1000). Next N lines contain N integer numbers(one number per each line) of the original array.输出For each case ,outtput file should contain at most N numbers sorted in ascending order. Every number in the output file should occur only once.样例输入68 8 7 3 7 7样例输出3 7 82008年上海交通大学计算机研究生机试真题1042: Coincidence时间限制: 1 Sec内存限制: 32 MB提交: 57解决: 25题目描述Find a longest common subsequence of two strings.输入First and second line of an input contain two strings of lowercase character az. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.输出In the first line of output file k the length of a longest common subsequence.样例输入abcdcxbydz样例输出22008年上海交通大学计算机研究生机试真题1043: Day of Week题目描述We now use the Gregorian style of dating in Russia. The leap years are years with number divisible by 4 but not divisible by 100, or divisible by 400.For example, years 2004, 2180 and 2400 are leap. Years 2004, 2181 and 2300 are not leap.Your task is to write a program which will compute the day of week corresponding to a given date in the nearest past or in the future using todays agreement about dating.输入There is one single line contains the day number d, month name M and year number y(1000y3000). The month name is the corresponding English name starting from the capital letter.输出Output a single line with the English name of the day of week corresponding to the date, starting from the capital letter. All other letters must be in lower case.样例输入9 October 200114 October 2001样例输出TuesdaySunday提示Month and Week name in Input/Output: January, February, March, April, May, June, July, August, September, October, November, DecemberSunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday2008年上海交通大学计算机研究生机试真题1044: Pre-Post题目描述We are all familiar with pre-order, in-order and post-order traversals of binary trees. A common problem in data structure classes is to find the pre-order traversal of a binary tree when given the in-order and post-order traversals. Alternatively, you can find the post-order traversal when given the in-order and pre-order. However, in general you cannot determine the in-order traversal of a tree when given its pre-order and post-order traversals. Consider the four binary three below: All of these trees have the same pre-order and post-order traversals. This phenomenon is not restricted to binary tree, but holds for general m-ary trees as well.输入 For each case, there is only one line of the form m indicating that the trees are m-ary trees, is the pre-order traversal and is the post-order traversal. All traversal strings will consist of lowercase alphabetic characters. For all input instances, 1m20 and the length of and will be between 1 and 26 inclusive. If the length of is k(which is the same as the length of , of course), the first k letters of the alphabet will be used as pre-order traversal string, the other k letters as post-order traversal string.输出 For each case, you should output one line containing the number of possible trees which would result in the pre-order and post-order traversals for the instances. Output value will be within the range of a 32-bit unsigned integer. You are guaranteed that there is at least one tree with the given pre-order and post-order traversals.样例输入2 abc cba2 abc bca10 abc bca13 abejkcfghid jkebfghicda样例输出41452073528602005年上海交通大学计算机研究生机试真题1089: 数字反转题目描述 12翻一下是21,34翻一下是43,12+34是46,46翻一下是64，现在又任意两个正整数，问他们两个数反转的和是否等于两个数的和的反转。输入 第一行一个正整数表示测试数据的个数n。 只有n行，每行两个正整数a和b（0a,b=10000）。输出 如果满足题目的要求输出a+b的值，否则输出NO。样例输入212 3499 1样例输出46NO2005年上海交通大学计算机研究生机试真题1090: 路径打印目标描述给你一串路径，譬如：abcadebcstd你把这些路径中蕴含的目录结构给画出来，子目录直接列在父目录下面，并比父目录向右缩一格，就像这样：a b c d eb cstd同一级的需要按字母顺序排列，不能乱。输入 每个测试案例第一行为一个正整数n（n=2 Write a program to calculate the Fibonacci Numbers.输入Each casecontains a number n and you are expected to calculate Fn.(0=n=30) 。输出 For each case, print a number Fn on a separate line,which means the nth Fibonacci Number.样例输入1样例输出12006年上海交通大学计算机研究生机试真题1093: WERTYU题目描述 A common typing error is to place the hands on the keyboard one row to the right of the correct position. So Q is typed as W and J is typed as K and so on. You are to decode a message typed in this manner.输入 Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except Q, A, Z), or punctuation shown above except back-quote (). Keys labelled with words Tab, BackSp, Control, etc. are not represented in the input.输出 You are to replace each letter or punctuation symbol by the one immediately to its left on the QWERTY keyboard shown above. Spaces in the input should be echoed in the output.样例输入O S, GOMR YPFSU/样例输出I AM FINE TODAY.2006年上海交通大学计算机研究生机试真题1094: String Matching 题目描述 Finding all occurrences of a pattern in a text is a problem that arises frequently in text-editing programs. Typically,the text is a document being edited,and the pattern searched for isa particular word supplied by the user. We assume that the text is an array T1.n of length n and that the pattern is an array P1.m of length m=n.We further assume that the elements of P and T are all alphabets(=a,b.,z).The character arrays P and T are often called strings of characters. We say that pattern P occurs with shift s in the text T if 0=s=n and Ts+1.s+m = P1.m(that is if Ts+j=Pj,for 1=j=m). If P occurs with shift s in T,then we call s a valid shift;otherwise,we calls a invalid shift. Your task is to calculate the number of vald shifts for the given text T and p attern P.输入For each case, there are two strings T and P on a line,separated by a single space.You may assume both the length of T and P will not exceed 106. 输出 You should output a number on a separate line,which indicates the number of valid shifts for the given text T and pattern P.样例输入abababab abab样例输出32006年上海交通大学计算机研究生机试真题1095: 2的幂次方题目描述 Every positive number can be presented by the exponential form.For example, 137 = 27 + 23 + 20。 Lets present ab by the form a(b).Then 137 is presented by 2(7)+2(3)+2(0). Since 7 = 22 + 2 + 20 and 3 = 2 + 20 , 137 is finally presented by 2(2(2)+2 +2(0)+2(2+2(0)+2(0). Given a positive number n,your task is to present n with the exponential formwhich only contains the digits 0 and 2.输入 For each case, the input file contains a positive integer n (n=20000).输出 For each case, you should output the exponential form of n an a single line.Note that,there should not be any additional white spaces in the line.样例输入1315样例输出2(2(2+2(0)+2)+2(2(2+2(0)+2(2(2)+2(0)+2+2(0)2009年上海交通大学计算机研究生机试真题1096: 日期差值题目描述有两个日期，求两个日期之间的天数，如果两个日期是连续的我们规定他们之间的天数为两天输入有多组数据，每组数据有两行，分别表示两个日期，形式为YYYYMMDD输出每组数据输出一行，即日期差值样例输入2011041220110422样例输出112009年上海交通大学计算机研究生机试真题1097: 取中值题目描述 存在两组数组，和4个数字a,b,c,d,要求做如下操作，将第一个数组第a个数到第b个数，第二个数组的第c个数到第d个数放到一个数组中，求出合并后数组的中间值，如果有两个中间值，取下标较小的那个。输入 第一行一个整数t表示有t个测试数据 第二行两个整数，表示两个数组的长