清华大学计算机考研复试题

试题一（5个测试数据，每个5分，共25分）

求N的阶乘

变量条件：N为正整数，且N≤1000。

运行时限：1秒/测试数据。

输入格式：仅一个数，N。

输出格式：仅一个数，N！的结果。

可执行文件：program1.exe

样例一：

Input.txt

4

Output.txt

24

样例二：

Input.txt

15

Output.txt

1307674368000

试题二（7个测试数据，每个5分，共35分）

给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。对于S的所有非空连续子序列T，求最大的序列和。

变量条件：N为正整数，N≤1000000，结果序列和在范围（-2e63,2e63-1）以内。

运行时限：2秒/测试数据

输入格式：第一行为一个正整数N，第二行为N个整数，表示序列中的数。

输出格式：仅一个整数，表示最大序列和。

可执行文件：program2.exe

样例一：

Input.txt

5

15-324

Output.txt

9

解释：子序列“1，5，-3，2，4”具有最大的序列和，9=1+5+(-3)+2+4

样例二：

Input.txt

6

1-234-106

Output.txt

7

解释：子序列“3，4”具有最大的序列和，7=3+4

样例三：

Input.txt

4

-3-1-2-5

Output.txt

-1

解释：子序列“-1”具有最大的序列和，-1=-1

试题三（8个测试数据，每个5分，共40分）

二叉树的前序、中序、后序遍历的定义：

前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；

中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；

后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

变量条件：二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

运行时限：1秒/测试数据。

输入格式：两行，第一行为前序遍历，第二行为中序遍历。

输出格式：若不能根据前序和中序遍历求出后序遍历，输出NOANSWER；否则输出一行，为后序遍历。

可执行文件：program3.exe

样例一：

Input.txt

ABC

BAC

Output.txt

BCA

样例二：

Input.txt

FDXEAG

XDEFAG

Output.txt

XEDGAF

样例三：

Input.txt

ABCD

BDAC

Output.txt

NOANSWER

测试用例说明

试题一

1.N=12，使用32位整数可以出结果，验证基本正确性

2.N=20，直接使用64位数可以出结果

3.N=100，验证较大的数

4.N=666，验证较大的数

5.N=1000，最大范围

试题二

1.N=100，全正整数

2.N=100，全负整数

3.N=20000，直接使用二重循环，如果效率高可以出解

4.N=50000

5.N=100000

6.N=500000，序列和超过2^32，必须使用64位整数类型

7.N=1000000

试题三

1.完全二叉树

2.全左子树直线型

3.全右子树直线型

4.根结点在中间的直线型

5.无解

6.随机26字母

7.随机26字母

8.随机26字母