上海交通大学05-07年上机真题附答案
- 格式：doc
- 大小：93.50 KB
- 文档页数：24
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. 给你一串路径，譬如 a\b\c a\d\e b\cst d 你把这些路径中蕴涵的目录结构给画出来，子目录直接列在父目录下面，并比父目录向右 缩一格，就象这样 a b c d e b cst d 同一级的需要按字母顺序排列，不能乱。 3. 这题听说.....有点问题。反正大概意思是这样的(除非我理解错了.....)： 有一个x[6][6] 任意的 0<=i,j<=5 1<=x[i][j]<=10; 现在有一个起始位置i1,j1与一个结束位置i2,j2。 请找出一条从i1,j1到i2,j2的总代价最小的路径。 1. 只能沿上下左右四个方向移动 2. 总代价是每走一步的代价之和 3. 每步（从a,b到c,d)的代价是x[c][d]与其在a,b处状态的乘积 4. 初始状态(在i1,j1时的状态）是1，每走一步，状态按如下公式变化 (走这步的代价 % 4)+1 也就是状态只有4种:1,2,3 or 4.
2006年上机试题: Problem A.Fibonacci Input: fib.in Output: Standard Output Time limit: 5 second Memory limit: 64 megabytes The Fibonacci Numbers{0,1,1,2,3,5,8,13,21,34,55...} are defined by the recurre nce: F0=0 F1=1 Fn=Fn-1+Fn-2,n>=2 Write a program to calculate the Fibonacci Numbers.
Input The input file contains a number n and you are expected to calculate Fn.(0<=n< =30) Output Print a number Fn on a separate line,which means the nth Fibonacci Number. Example fib.in Standard Output 1 1 2 1 3 2 4 3 5 5 6 8
Problem B.WERTYU Input: wertyu.in Output: Standard Output Time limit: 5 second Memory limit: 64 megabytes 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" and so on.You are to decode a message typed in this manner.
` 1 2 3 4 5 6 7 8 9 0 - = BackSp Tab Q W E R T Y U I O P [ ] \ A S D F G H J K L ; ' Enter Z X C V B N M , . / Control Alt Space Alt Control
Input The 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. Output 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 ech oed in the output.
Example wertyu.in Standard Output O S, GOMR YPFSU/ I AM FINE TODAY.
Problem C.String Matching Input: matching.in Output: Standard Output Time limit: 5 second Memory limit: 64 megabytes Finding all occurrences of a pattern in a text is a problem that arises freque ntly 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 T[1..n] of length n and that the pattern i s 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 cal led 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 s a invalid shift. Your task is to calculate the number of vald shifts for the given text T and p attern P.
Input In the input file,there are two strings T and P on a line,separated by a singl e space.You may assume both the length of T and P will not exceed 10^6.
Output You should output a number on a separate line,which indicates the number of va lid shifts for the given text T and pattern P.
Example matching.in Standard Output aaaaaa a 6 abababab abab 3 abcdabc abdc 0
Problem D.Exponential Form Input: form.in Output: Standard Output Time limit: 5 second Memory limit: 64 megabytes Every positive number can be presented by the exponential form.For example, 137 = 2^7 + 2^3 + 2^0
Let'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.
Input The input file contains a positive integer n (n<=20000).
Output You 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.
Example form.in 137 Stardard Output 2(2(2)+2+2(0))+2(2+2(0))+2(0) form.in 1315 Stardard Output 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
2006年上机试题参考答案: //A.cpp //18 lines #include "iostream" #include "fstream" using namespace std;
int fib(int n) {
