2005-2007年上海交通大学计算机上机真题附答案

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 

你把这些路径中蕴涵的目录结构给画出来,子目录直接列在父目录下面,并比父目录向右 
缩一格,就象这样 






cst 


1

同一级的需要按字母顺序排列,不能乱。 
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. 

2

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 ERT Y U I O P [] \ 
A SD F G HJ KL ; ' Enter 
ZXCVBNM, . / 
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) 


6

if (n==0) return 0; 
else if (n==1) return 1; 
else return fib(n-1)+fib(n-2); 




void main() 


fstream f("fib.in"); 
int n; 
f>>n; 
cout<<fib(n)<<endl; 




//B.cpp 
//28 lines 
#include "iostream" 
#include "fstream" 
#include "string" 
#include "stdio.h" 
using namespace std; 


char table[100]="`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"; 


void main() 



fstream f("wertyu.in"); 
char c[1000]; 
string s; 
int tablelen = strlen(table); 


while (!f.getline(c,1000).eof()) 


s = c; 
int n = s.length(); 
for (int i=0;i<n;i++) 



for (int j=0;j<tablelen;j++) 

if (s[i]==table[j]) s[i]=table[j-1]; 



cout<<s<<endl; 




//C.cpp 
//24 lines 
#include "iostream" 
#include "fstream" 
#include "string" 
using namespace std; 


int match(string s,string t) 



int count=0; 
string::size_type index = -1; 
while ((index = s.find(t,index+1))!=string::npos) count++; 
return count; 




void main() 


fstream f("matching.in"); 
string s,t; 
while (!f.eof()) 


f>>s; 
f>>t; 
cout<<match(s,t)<<endl; 





//D.cpp 
//60 lines 
#include "iostream" 
#include "fstream" 
#include "string" 
using namespace std; 


int getminex(int n) 



int k=0; 
int l=1; 
while (1) 


if (n<l) break; 
else 



l=l*2; 
k++; 



return k-1; 



int getremain(int n) 


int t=getminex(n); 
int s=1; 
for (int i=0;i<t;i++) 


s=s*2; 

return n-s; 



string getform(int n) 


if (n==0) return ""; 
else if (n==1) return "2(0)"; 
else if (n==2) return "2"; 
else if (n==4) return "2(2)"; 
else 


string t,s; 

int e = getminex(n); 
if (e == 1) t= ""; 


else t = "("+getform(e)+")"; 
s = "2"+t; 
int r = getremain(n); 
if (r != 0) s = s+"+"+getform(r); 
return s; 


void main() 

fstream f("form.in"); 
int n; 
f>>n; 
cout<<getform(n)<<endl; 

参考试题1: 
Fire Net 
Suppose 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. 

11

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: 


.X.. 
.... 
XX.. 
.... 


XX 
.X 


.X. 

X.X 
.X. 


... 
.XX 
.XX 


.... 
.... 
.... 


.... 



Sample output: 







Trees are fundamental in many branches of computer science. Current state-of-t 
he art parallel computers such as Thinking Machines' CM-5 are based on fat tre 
es. Quad- and octal-trees are fundamental to many algorithms in computer graph 
ics. 

This problem involves building and traversing binary trees. 

Given a sequence of binary trees, you are to write a program that prints a lev 
el-order traversal of each tree. In this problem each node of a binary tree co 
ntains 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 a 
re 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 L's and R's where L indicates a left branch a 
nd R indicates a right branch. In the tree diagrammed above, the node containi 
ng 13 is specified by (13,RL), and the node containing 2 is specified by (2,LL 
R). The root node is specified by (5,) where the empty string indicates the pa 
th from the root to itself. A binary tree is considered to be completely speci 
fied if every node on all root-to-node paths in the tree is given a value exac 
tly once. 
Input 
The input is a sequence of binary trees specified as described above. Each tre 
e in a sequence consists of several pairs (n,s) as described above separated b 
y 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-fi
le. 

15

Output 
For each completely specified binary tree in the input file, the level order t 
raversal 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 Output 
5 4 8 11 13 4 7 2 1 
not complete 
参考试题3: 
写一个求任意边平面多边形面积的程序 
要求是:输入边数,然后依次输入每个顶点的坐标 
有可能输入的数值不能构成正则多边形,也即,边与边之间发生了交叉,比如,四个顶 
点分别为(0,0),(1,1),(0,1),(1,0)这种情况,这时候,请打印出“imp 
ossible"字样;如果多边形合法,则请输出该多边形的面积 
要注意的情况是:凹多边形的正确处理 
Sample Input 


16

0 0 
0 1 
0.5 0.5 
1 1 
1 0 
Sample Output 
0.75 
Sample Input 

0 0 
0 1 
1 0 
1 1 
Sample Output 
Impossible 
保送生试题: 
Problem D . Code the Tree 
Source File: tree.cpp Time limited: 1 second 
Input File: tree.in Output File:tree.out 
A 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 i 
s 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. 

17

In the obtained graph, this procedure is repeated, until there is only one ve 
rtex 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. 

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 | empty 
N::= integer 


That 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 t 
he 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 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 
. You 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 output 
tree.in 
(2,(6,(7)),(3),(5,(1),(4)),(8)) 
tree.out 
5 2 5 2 6 2 8 
2007 年复试上机真题: 
Problem A. Old Bill 
Input file: standard input 
Output file: standard output 
Among grandfather's 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. 

19

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. 

Input 
The first line of the input file contains an integer N (0<N<100), 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_. 

Output 
For 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 output 
Standard input standard output 
72 3 2 511 
6 7 9 

5 9 5 18475 
2 3 7 

78 0 
0 0 5 


Problem B. Powerful Calculator 
Input file: standard input 
Output file: standard output 

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.4×10^16. 
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. 


Input 
The input file consist of two separate lines where the first line gives the 
integer a and the second gives b (|a| <10^200 and |b| < 10^200). 

Output 
For 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 output 
Standard input standard output 
20000000000000000 24000000000000000 
4000000000000000 16000000000000000 
80000000000000000000000000000000 

Problem C. Sum of Factorials 
Input file: standard input 
Output file: standard output 

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! (t≥1, xi≥0, xi = xj <==> i = j) 

即 Σ xi! (t≥1, xi≥0, xi = xj <==> i = j)
i=1 
If the answer is yes, say "YES"; otherwise, print out 
"NO". 
Input 
You will get a non-negative integer n (n≤1,000,000) from input file. 
Output 
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. 
Sample input and output 
Standard input standard output 
9 YES 
2 YES 

23

Problem D. Zero-complexity Transposition 
Input file: standard input 
Output file: standard output 
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. 
Input 
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). 
Output 
On the first line of the output file print the sequence in the reverse 
order. 
Sample input and output 
Standard input standard output 
3 3 2 1 
1 2 3 
5 9 -8 6 4 -3 
-3 4 6 -8 9 

24

 

免责声明:本站所有的内容均来源于互联网采集或网友投稿提供,不能保证内容的真实性、完整性,仅供个人研究、交流学习使用,不涉及任何商业盈利目的。如果资料有误与官方发布不一致,请与官方最新发布为准,请联系本站管理员予以更改,如果涉及版权等问题,请联系本站管理员予以删除。
维权指引 | 权限说明 | 下载说明 | 内容投诉
考研云分享 » 2005-2007年上海交通大学计算机上机真题附答案
您需要 登录账户 后才能发表评论

发表评论

欢迎 访客 发表评论

加入会员,每天进步一点点
·会员权限 ·加网盘群 ·加微信群