上海交通大学05-07年上机真题附答案.doc

2005年上机试题发信人: tiancai (tiancai), 信区: KaoyanExam标 题: Re: 问：今年cs上机题是什么？发信站: 饮水思源 (2005年04月01日16:10:39 星期五)可能晚些时候会有人发出完整版本，我写一下我记到的东西：1. 太恐怖了，12翻一下是21对吗？34翻一下是43对吗？12+34是46对吗？46翻一下是64对吗？现在给你21与43，把64输出就可以了。2. 给你一串路径，譬如abcadebcstd你把这些路径中蕴涵的目录结构给画出来，子目录直接列在父目录下面，并比父目录向右缩一格，就象这样a b c d eb cstd同一级的需要按字母顺序排列，不能乱。3. 这题听说.有点问题。反正大概意思是这样的(除非我理解错了.)：有一个x66 任意的 0=i,j=5 1=xij=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 megabytesA 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. 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,spaces,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,Control,etc. are not represented in the input.OutputYou 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.Examplewertyu.in Standard OutputO S, GOMR YPFSU/ I AM FINE TODAY.Problem C.String MatchingInput: matching.inOutput: Standard OutputTime limit: 5 secondMemory limit: 64 megabytesFinding 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 is a 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 call s a invalid shift.Your task is to calculate the number of vald shifts for the given text T and pattern P.InputIn the input file,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.OutputYou should output a number on a separate line,which indicates the number of valid 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 megabytesEvery positive number can be presented by the exponential form.For example,137 = 27 + 23 + 20Lets 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 form which only contains the digits 0 and 2.InputThe input file contains a positive integer n (nn;coutfib(n)endl;/B.cpp /28 lines#include iostream#include fstream#include string#include stdio.husing namespace std;char table100=1234567890-=QWERTYUIOPASDFGHJKL;ZXCVBNM,./;void main()fstream f(wertyu.in);char c1000;string s;int tablelen = strlen(table);while (!f.getline(c,1000).eof()s = c;int n = s.length();for (int i=0;in;i+)for (int j=0;jtablelen;j+)if (si=tablej) si=tablej-1;coutss;ft;coutmatch(s,t)endl;/D.cpp /60 lines#include iostream#include fstream#include stringusing namespace std;int getminex(int n)int k=0;int l=1;while (1)if (nl) break;else l=l*2;k+;return k-1;int getremain(int n)int t=getminex(n);int s=1;for (int i=0;in;coutgetform(n)endl;参考试题1:Fire NetSuppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall. A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening. Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets. The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through. The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways. Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration. The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a . indicating an open space and an uppercase X indicating a wall. There are no spaces in the input file. For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration. Sample input: 4.X.XX.2XX.X3.X.X.X.X.3.XX.XX4.0Sample output: 51524Trees are fundamental in many branches of computer science. Current state-of-the art parallel computers such as Thinking Machines CM-5 are based on fat trees. Quad- and octal-trees are fundamental to many algorithms in computer graphics.This problem involves building and traversing binary trees.Given a sequence of binary trees, you are to write a program that prints a level-order traversal of each tree. In this problem each node of a binary tree contains a positive integer and all binary trees have fewer than 256 nodes.In a level-order traversal of a tree, the data in all nodes at a given level are printed in left-to-right order and all nodes at level k are printed before all nodes at level k+1.For example, a level order traversal of the tree is: 5, 4, 8, 11, 13, 4, 7, 2, 1. 参考试题2:In this problem a binary tree is specified by a sequence of pairs (n,s) where n is the value at the node whose path from the root is given by the string s. A path is given be a sequence of Ls and Rs where L indicates a left branch and R indicates a right branch. In the tree diagrammed above, the node containing 13 is specified by (13,RL), and the node containing 2 is specified by (2,LLR). The root node is specified by (5,) where the empty string indicates the path from the root to itself. A binary tree is considered to be completely specified if every node on all root-to-node paths in the tree is given a value exactly once.InputThe input is a sequence of binary trees specified as described above. Each tree in a sequence consists of several pairs (n,s) as described above separated by whitespace. The last entry in each tree is (). No whitespace appears between left and right parentheses.All nodes contain a positive integer. Every tree in the input will consist of at least one node and no more than 256 nodes. Input is terminated by end-of-file.OutputFor each completely specified binary tree in the input file, the level order traversal of that tree should be printed. If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string not complete should be printed.Sample Input(11,LL) (7,LLL) (8,R)(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()(3,L) (4,R) ()Sample Output5 4 8 11 13 4 7 2 1not complete参考试题3:写一个求任意边平面多边形面积的程序要求是：输入边数，然后依次输入每个顶点的坐标有可能输入的数值不能构成正则多边形，也即，边与边之间发生了交叉，比如，四个顶点分别为（0，0），（1，1），（0，1），（1，0）这种情况，这时候，请打印出“impossible字样；如果多边形合法，则请输出该多边形的面积要注意的情况是：凹多边形的正确处理Sample Input50 00 10.5 0.51 11 0Sample Output0.75Sample Input40 00 11 01 1Sample OutputImpossible保送生试题: Problem D . Code the Tree Source File: tree.cpp Time limited: 1 secondInput File: tree.in Output File:tree.out A tree(ie:a connected graph without cycles) with vertices numbered by the integers 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 of n - 1 numbers is called the Prufer code of the tree. Your task is, given a tree, to compute its Prufer code. The tree is denoted by a word of the language specified by the following grammar: T:= (N S)S:= ,T S | emptyN:= integer That is, trees have parentheses around them, and a number denoting the identifier of the root vertex, followed by arbitrarily many(maybe none) subtrees separated 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.Note that, according to the definition given above, the root of a tree may be a leaf as well. It is only for the ease of denotation that we designate some vertex to be the root. Usually, what we are dealing here with is called an unrooted tree. Input:There is only one line in the input, which specifies a tree as described above. You may assume that 1 = n = 50.Output:Generate a single line containing the Prufer code of the tree. Separate numbers by a single space. Do not print any spaces at the end of the line. Sample input and output tree.in(2,(6,(7),(3),(5,(1),(4),(8) tree.out5 2 5 2 6 2 8 2007年复试上机真题： Problem A. Old BillInput file: standard inputOutput file: standard outputAmong 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.InputThe 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_.OutputFor the input case, there may be more than one candidate for the original price or there is none. In the latter case your program is to report 0. Otherwise, if there is more than one candidate for the original price, the program is to report the two faded digits and the maximum price per turkey for the turkeys.Sample input and outputStandard input standard output72 3 2 5116 7 95 9 5 184752 3 778 00 0 5Problem B. Powerful CalculatorInput file: standard inputOutput file: standard outputToday, 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 00020000000000000000 - 4000000000000000 = 16 000 000 000 000 00020000000000000000 4000000000000000 = 80 000 000 000 000 000 000 000 000 000 000Note: 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.InputThe input file consist of two separate lines where the first line gives the integer a and the second gives b (|a| 10200 and |b| 10200).OutputFor the input file, 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.Sample input and outputStandard input standard output 20000000000000000 240000000000000004000000000000000 16000000000000000 80000000000000000000000000000000 Problem C. Sum of FactorialsInput file: standard inputOutput file: standard outputJohn 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