[转帖]清华计算机06复试上机考试说明及真题

灰飞烟未灭

[转帖]清华计算机06复试上机考试说明及真题
2006清华计算机复试中网络所和高性能所进行的编程题上机考试，分数在复试中占 +#c U_6
f&|}uc
1/3,现在清华研究生改成两年，很多老师很看重动手能力特别强的学生。如果想找 a4>_xl
^^spTh@Zl
好方向的考生，建议对此早有准备，先贴出2006清华计算机考研复试上机题供大家 VkQGp)P
p( ]r*$r
参考。 %qtv*.
7cd-:byyL
原版为word版 需要原版同学留下邮箱或给我发邮件。 NB9W<z0Z
}@DQ7oklw
清华大学高性能计算研究所硕士生招生复试 5Y!/IX(
程序设计考试试题 L0&};:^j
注意事项： D%5V`P.YS
1.    试题共三题，总计100分，考试时间为2小时整。 ']V2zQS
2.    不得使用自带的电子设备，包括笔记本、U盘、手机等；不得使用参考书 e?h{h8pF
f FhFp@
籍和资料。 ~~5R 1=m)
3.    编程环境为Windows 2000 Professional + Visual Studio 6.0，只能使 a:A[Fek
7Aq@,/
用C/C++语言。 =+ #{"O
4.    每一题的输入数据都从文件Input.txt中读取，将结果输出至文件 #:a xN+(
[H@x\
0RK
Output.txt，请严格按照每一题的输入输出格式。在考试过程中，我们恕不提供除 6n8Di<wXD
VGaW o~c8J
试题中样例以外的测试数据，请自行生成输入数据以对程序进行自测。 _eInC
5.    请在考试结束之前自行设置编译环境和配置编译参数，将所写的程序编译 3-0 $wNH>
IXkO{M b
成可执行文件，文件名在每一题中都有规定。生成的可执行文件将作为最终测试的 Jq8xDhB`X
u\h]mWd
唯一依据，若无法运行您的可执行文件，最终成绩将记为零分。 9!Ko .j^
6.    程序对每个测试数据的可用运行时间上限为每一题中规定的“运行时限” L3 bs ]
7r1c
，若超时或结果错误，则该测试用例不得分。 ]f}wi; U:
7.    在考试过程中，若计算机出现故障，请及时通知工作人员，以免耽误您的 k9 o?q]}
UstyT,IW7
考试时间。 tI9 ?sug
8.    上机考试结束后，请勿马上离开，工作人员将会直接进行现场测试，需要 A=4yc^Soa&
n=& v")
您的合作。 $s! {wt
stplxGy$S
试题一（5个测试数据，每个5分，共25分） y }60QJ
求N的阶乘 _@$Zrp;%
变量条件：N为正整数，且N≤1000。 dr@KY6@
运行时限：1秒/测试数据。 ui;]pH
输入格式：仅一个数，N。 m\643s'
输出格式：仅一个数，N！的结果。 Q_'\3NH~Q
可执行文件：program1.exe ucF~zH'
OXTxBR
样例一： d[ajnGq4r
Input.txt p3G1>Zr
4 wMc wQ'm
/!e@neI
Output.txt i[@l 'g
24 )1 =mMnsu
样例二： .GL P/@hs
Input.txt 9[
9nkjN
15 mO?4ju&]4
18:T(<rM
Output.txt +eak7kp
1307674368000 |L nlO8
3  B/7 I
试题二（7个测试数据，每个5分，共35分） a?bdJ"U
B0
   给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所 v QI/*g4-g
U8#oI%}<
有数的和为T的“序列和”。对于S的所有非空连续子序列T，求最大的序列和。 _lQX,, Z
变量条件：N为正整数，N≤1000000，结果序列和在范围（-2e63,2e63-1）以内。 9[Qml0Ym
运行时限：2秒/测试数据 /M4s^Zt
输入格式：第一行为一个正整数N，第二行为N个整数，表示序列中的数。 m;TFg 7J
输出格式：仅一个整数，表示最大序列和。 =,NfXqy
可执行文件：program2.exe &]Z~/Oa
aO9N-zU
样例一： {LEkBM9J
Input.txt g[A1ev;`?
5 ,x102$MC
1 5 -3 2 4 Z 0A,e
#-kIK!+
Output.txt F$
LN$D<
9 Wi/|W9]w7
g~'XCV.G9M
解释：子序列“1，5，-3，2，4”具有最大的序列和，9=1+5+(-3)+2+4 v9c /tOv|
样例二： lXlKgP^
Input.txt +SBsaXRE
6 BN'p$%hc
1 -2 3 4 -10 6 
I9-r-*M
QS:V?Q+8]
Output.txt I`H[n#'1
7 d_{O o=
C ?[&Q?Fd
解释：子序列“3，4”具有最大的序列和，7=3+4 FFeWq>T3'
样例三： ->X 2p)KR
Input.txt F]AZ/00M
4 Uv(M68;
-3 -1 -2 -5 VYLLd0/`
R. Wc8
Output.txt
l>@6-{NkY
-1 ~ fl*
4~_6^8[
解释：子序列“-1”具有最大的序列和，-1=-1 ?@7o)0^
2uAGf.M"
试题三（8个测试数据，每个5分，共40分） }}U.toaUF
   二叉树的前序、中序、后序遍历的定义： )[j,$ojHI
前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树； _N ]<d=k
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； P &mi [ Y
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 ]f_Nu:tk
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中 _ar;{+HP
. (:_L
序遍历能够唯一确定后序遍历）。 Hm3A(k
变量条件：二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。 M3g#J;uO
运行时限：1秒/测试数据。 2T6N"uuO~
输入格式：两行，第一行为前序遍历，第二行为中序遍历。 :2u]Ff"/
输出格式：若不能根据前序和中序遍历求出后序遍历，输出NO ANSWER；否则输出 QjZ)WN0i
?qQ+7rB
一行，为后序遍历。 b&@gt3"
可执行文件：program3.exe (rBzkGbJl
&7eo[QqF
样例一： 3v ~t
Input.txt nnWZObD

ABC 68DWpq.
BAC ' I
{+)B[J/at
Output.txt N-37G%%E
BCA FwA{* 3<
样例二： wrho p
K
Input.txt ~;9{Nk0?
FDXEAG |9xW}?}17
XDEFAG RGY <ft5
=;%+`^C
Output.txt 7LlP4~\
XEDGAF .Z;9 @,":R
样例三： ] JEftX
Input.txt n*dVk'\O
ABCD 3,+ Z7uxR
BDAC GT^Nqi~V
k!hLz#
Output.txt :_B~Os
NO ANSWER 2nWi!nXU
OQQF>gyTA
94Nl
s`/FL')tS
z/:}yk
tl'_a?3
}M;awH.
 ~$N8
U[9_S4 +p
v|\ dVQ
k[@8(J;nB
U5T6 !=
LROgno0
` nb'tfK
0_>!m* QG
>_M+j2`
 5
KpS\G=7DO
5TY{& Hd6
UvHwG W$
H_|[x -/
d^4M| K
测试用例说明 &XWp!\ h
试题一 wzLe>H/DJ
1.    N=12，使用32位整数可以出结果，验证基本正确性 47PN!\`bO
2.    N=20，直接使用64位数可以出结果 &yz > vs
3.    N=100，验证较大的数 8l6x`E D
4.    N=666，验证较大的数 I-^y86kw
5.    N=1000，最大范围 =Q)1=26#
c`>a_~
试题二 qv6A I
1.    N=100，全正整数 o2'$)(IEi
2.    N=100，全负整数 ? 6*[6WfO_
3.    N=20000，直接使用二重循环，如果效率高可以出解 T]v-P$+y
4.    N=50000 ]BGN<2Q
5.    N=100000 mJ-1
"Th#,
6.    N=500000，序列和超过2^32，必须使用64位整数类型 /eG ,E ]~
7.    N=1000000 a[g@$H
d L+^c`R
试题三 0/92|3V
1.    完全二叉树 =^D\=Q
B
2.    全左子树直线型 (]Vw&)oP
3.    全右子树直线型 8J{I1+&k
4.    根结点在中间的直线型 Lpx3h4i
5.    无解 v 1S*$cp
6.    随机26字母 W> n!KQ!Qq
7.    随机26字母 BG6[
2
8.    随机26字母 LIN/&97kf\
I[?S`_D
a+Z9RO> A
!RC)T5A$)
B'F9GK^<-
2007考研临近，我在清华本校，如果有清华计算机考研资料不全的同学欢迎联系 Jp'E8i6%n
r;>T}88
我chicago1113@163.com or 13466338386. 我这儿有一套纸版很全的清华计算机考 /LU.tt\b
9?VbAYlX
研内部资料。