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
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:
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0
Sample output:
5
1
5
2
4
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
5
16
0 0
0 1
0.5 0.5
1 1
1 0
Sample Output
0.75
Sample Input
4
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)
t
即 Σ 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
您需要 登录账户 后才能发表评论
