当前位置：搜档网 › 上海交通大学05-07年计算机上机真题附答案

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

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输出就可以了。

给你一串路径，譬如

a\b\c

a\d\e

b\cst

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

cst

同一级的需要按字母顺序排列，不能乱。

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 o

f 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)

{

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<

}

//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

{

for (int j=0;j

{

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

}

cout<

}

//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<

}

//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

else

{

l=l*2;

k++;

}

return k-1;

}

int getremain(int n)

{

int t=getminex(n);

int s=1;

for (int i=0;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<

}

参考试题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.

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..

....

.X.

X.X

.X.

...

.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.

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

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.

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.

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

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

最全的历年上海交通大学汽车理论考研真题含部分答案

上海交通大学一九九九年硕士生入学考试试题一、填空题（×28） 1、国际上常用油耗计算方法有两种，即以欧洲为代表的ECE和以美国为代表的EPA. 2、良好路面上行驶汽车所受的行驶阻力主要由、、和四部分组成。 3、制动时汽车减速度行驶，避免车轮抱死的最小称为汽车在该制动强度时的。 4、操纵稳定性是指弯道行驶汽车转向特性抗干扰能力，与其有关的主要运动参数包括、和。 5、汽车动力性主要由三项指标来评定，它们是、和。 6、因可在负实数、零或正实数上取值，弯道行驶汽车的横摆角速度增益对应三种不同的转向特性，即、以及。 7、制动全过程大致分为四个不同阶段，即、、以及。 8、汽车加速时产生相应的惯性阻力，即由和两部分惯性力组成。 9、汽车拖带挂车的目的是提高燃油经济性，其原因有二：一是汽车发动机的上升，二是汽车列车增加。 10、对汽车动力性和燃油经济性有重要影响的动力装置参数有两个，即和。二、论述题（3×5） 1、高速行驶汽车的轮胎会发生爆裂，试简述轮胎发生什么现象并说明原因？ 2、装有防抱死制动系统（ABS）的汽车可避免制动时跑偏和侧滑，试说明其理论依据？ 3、某汽车传动系统采用齿轮变速器，试说明各档位传动比的确定原则是什么？ 4、某汽车装有非ABS的普通制动系统，试简述制动时制动距离与哪些因素有关？ 5、加装液力变速器的汽车具有较理想的动力特性，试说明主要目的是什么？

三、是非题（错误×正确√，2×10） 1、汽车轮胎的侧滑刚度与车轮坐标系的选择有关。（×） 2、超速挡的应用可以降低汽车的负荷率。（×） 3、地面的制动力大小取决于汽车具有足够的制动器制动力。（×） 4、汽车稳态横摆角速度响应与行驶车速有关。（√） 5、不出现前轮或后轮抱死的制动强度必小于地面附着系数。（√） 6、同步附着系数ψ0与地面附着特性有关。（×） 7、未装有ABS的汽车在制动时发生侧滑是技术状况不良造成的。（×） 8、特征车速u ch是表征汽车过多转向量的一个参数。（×） 9、汽车的最高行驶车速对应发动机最高转速。（×） 10、汽车齿轮变速器的相邻两变速档速比之比基本上取为常数。（√）四、某轿车按给定的速度变化曲线作加速度行驶，欲根据汽油发动机万有特性（见图）计算过程中的燃油消耗量.已知：发动机功率P=30KW,初始车速u0=10km，经过△t1=2秒（s）车速达到40km/h,又经过△t24秒（s）车速达到60km/h,再经过△t3=4秒（s）车速已到达到90km/h,等速单位时间油耗计算公式为Q t=Pb/γ),其中b 为燃油消耗率（g/kw·h）(由图中曲线给出)，汽油重度γ=7（N/L）.(15分) a 五、某轿车沿水平硬路面公路高速行驶， A B C D 遇事后采取紧急制动。图示为该轿车制动 t 时的加速度，速度和距离的对应变化关系。 j max 试求：（1）制动反应阶段经过时刻t1,在AB

上海交通大学试卷( A 卷)

上海交通大学试卷（ A 卷）课程线性代数（B 类）学期 2011－2012第1学期班级号学号姓名一．单项选择题（每题3分，共18分） 1．设A ，B 为n 阶方阵，且A A =2 ，B B =2 。则（）（A ）)()(B r A r =时，A ，B 不相似；（B ）)()(B r A r ≠时，A ，B 相似；（C ）)()(B r A r =时，A ，B 相似；（D ）以上都有可能。 2．设A 为n 阶反对称矩阵，则（）（A ）0)(=+E A r ；（B ）n E A r =+)(；（C ）n E A r <+<)(0；（D ）以上都有可能。 3．设B A ,为n 阶方阵，??? ? ??=B A C 00。则伴随矩阵* C 为（）（A ）???? ??** B A A B ||0 0||；（B ）??? ? ??**B B A A ||00||；（C ）???? ? ?** A A B B ||0 0||；（D ）??? ? ? ?**A B B A ||00||。 4．设A 为n m ?的实矩阵，矩阵)(A A T 正定的充分必要条件为（）（A ）m A r =)(；（B ）m A r <)(；（C ）m A r <)(；（D ）n A r =)(。 5．设α是单位向量，矩阵ααT k E A +=，其中1-≠k 。则（）我承诺，我将严格遵守考试纪律。

（A ）A 为正交矩阵；（B ）A 为正定矩阵；（C ）A 为可逆矩阵；（D ）A 为反对称矩阵。 6．设向量组321,,ααα线性无关，向量321,,βββ线性相关但相互不成比例，且， 321332123211,,αααβαααβαααβk k k ++=++=++=。则（）（A ）2-=k 或 1=k ；（B ）1=k ；（C ）2-≠k 且 1≠k ；（D ）2-=k 。二．填空题（每题3分，共18分） 7．设行列式 4 111311 12=D ，j i A 是D 中元素j i a 的代数余子式，则 ∑∑==313 1 i j j i A ＝。 8．已知4阶行列式4||j i a 的展开式中某项为42143123)1(a a a a k -。则=k 。 9. 设33)(?=ij a A ,j i A 是||A 中j i a 的代数余子式，j i j i A a =，13 121132a a a ==。已知011