上海交大计算机研究生考试复试上机题目
- 格式：doc
- 大小：41.50 KB
- 文档页数：5
2006年上海交大计算机研究生考试复试上机题目编程环境：VC+6考试时间：3小时本题目是我一字一字敲上电脑的后给出自己做的参考解答，希望能和大家多多交流。
上机题目均为英文，一共四道，偏ACM，我只是尽量还原原文。
Problem A.FibonacciInput: fib.inOutput: Standard OutputTime limit: 5 secondMemory limit: 64 megabytesOfferd by ：/davidblogs/The Fibonacci Numbers{0,1,1,2,3,5,8,13,21,34,55...} are defined by the recurrence:F0=0 F1=1 Fn=Fn-1+Fn-2,n>=2Write a program to calculate the Fibonacci Numbers.InputThe input file contains a number n and you are expected to calculate Fn.(0<=n<=30)OutputPrint a number Fn on a separate line,which means the nth Fibonacci Number.Examplefib.in Standard Output1 12 13 24 35 56 8Problem B.WERTYUInput: wertyu.inOutput: Standard OutputTime limit: 5 secondMemory limit: 64 megabytesOfferd by ：/davidblogs/A common typing error is to place the hands on the keyboard one row to the rig ht of the correct position.So "Q" is typed as "W" and "J" is typed as "K" andso on.Y ou are to decode a message typed in this manner.` 1 2 3 4 5 6 7 8 9 0 - = BackSpTab Q W E R T Y U I O P [ ] \A S D F G H J K L ; ' EnterZ X C V B N M , . /Control Alt Space Alt ControlInputThe input file consist of several lines of text.Each line may contain digits,s paces,upper case letters(except Q,A,Z),or punctuation shown above(except back- quote(') which is left to the key "1").Keys labelled with words [Tab,BackSp,Co ntrol,etc.] are not represented in the input.OutputY ou 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 ech oed in the output.Examplewertyu.in Standard OutputO S, GOMR YPFSU/ I AM FINE TODA Y.Problem C.String MatchingInput: matching.inOutput: Standard OutputTime limit: 5 secondMemory limit: 64 megabytesOfferd by ：/davidblogs/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 T[1..n] of length n and that the pattern is an array P[1..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 T[s+1..s+m] = P[1..m](that is if T[s+j]=P[j],for 1<=j<=m).If P occurs with shift s in T,then we call s a valid shift;otherwise,we call sa invalid shift.Y our task is to calculate the number of vald shifts for the given text T and p attern P.InputIn the input file,there are two strings T and P on a line,separated by a single space.Y ou may assume both the length of T and P will not exceed 10^6.OutputY ou should output a number on a separate line,which indicates the number of va lid shifts for the given text T and pattern P.Examplematching.in Standard Outputaaaaaa a 6abababab abab 3abcdabc abdc 0Problem D.Exponential FormInput: form.inOutput: Standard OutputTime limit: 5 secondMemory limit: 64 megabytesOfferd by ：/davidblogs/Every positive number can be presented by the exponential form.For example, 137 = 2^7 + 2^3 + 2^0Let's present a^b by the form a(b).Then 137 is presented by 2(7)+2(3)+2(0). Since 7 = 2^2 + 2 + 2^0 and 3 = 2 + 2^0 , 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 form which only contains the digits 0 and 2.InputThe input file contains a positive integer n (n<=20000).OutputY ou should output the exponential form of n an a single line.Note that,there s hould not be any additional white spaces in the line.Exampleform.in137Stardard Output2(2(2)+2+2(0))+2(2+2(0))+2(0)form.in1315Stardard Output2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)搭车附赠一道这届保送生的上机题目Problem D . Code the TreeSource File: tree.cpp Time limited: 1 secondInput File: tree.in Output File:tree.outA tree(ie:a connected graph without cycles) with vertices numbered by the inte gers 1,2....,n is given. The "Prufer" code of such a tree is built as follows:the leaf(a vertex that is incident to only one edge) with the minimal number is taken. This leaf, together with its incident edge is removed from the graph, while the number of the vertex that was adjacent to the leaf is written down.In the obtained graph, this procedure is repeated, until there is only one vertex left(which, by the way, always has number n). The written down sequence o f n - 1 numbers is called the Prufer code of the tree.Y our task is, given a tree, to compute its Prufer code. The tree is denoted bya word of the language specified by the following grammar:T::= (N S)S::= ,T S | emptyN::= integerThat is, trees have parentheses around them, and a number denoting the identif ier of the root vertex, followed by arbitrarily many(maybe none) subtrees sepa rated by a single comma character. As an example, take a look at the tree in the figure below which is denoted in the first example./file/PIC/1143645530160541.bmpNote that, according to the definition given above, the root of a tree may bea leaf as well. It is only for the ease of denotation that we designate some v ertex to be the root. Usually, what we are dealing here with is called an "unr ooted tree".Input:There is only one line in the input, which specifies a tree as described above . Y ou may assume that 1 <= n <= 50.Output:Generate a single line containing the Prufer code of the tree. Separate number s by a single space. Do not print any spaces at the end of the line.Sample input and outputtree.in(2,(6,(7)),(3),(5,(1),(4)),(8))tree.out5 2 5 26 2 8。
