清华大学高性能计算研究所硕士生招生复试
程序设计考试试题
注意事项：
1.试题共三题，总计100分，考试时间为2小时整。
2.不得使用自带的电子设备，包括笔记本、U盘、手机等；不得使用参考书籍和资料。
3.编程环境为Windows2000Professional+VisualStudio6.0，只能使用C/C++语言。
4.每一题的输入数据都从文件Input.txt中读取，将结果输出至文件Output.txt，请严格按照每一题的输入输出格式。在考试过程中，我们恕不提供除试题中样例以外的测试数据，请自行生成输入数据以对程序进行自测。
5.请在考试结束之前自行设置编译环境和配置编译参数，将所写的程序编译成可执行文件，文件名在每一题中都有规定。生成的可执行文件将作为最终测试的唯一依据，若无法运行您的可执行文件，最终成绩将记为零分。
6.程序对每个测试数据的可用运行时间上限为每一题中规定的“运行时限”，若超时或结果错误，则该测试用例不得分。
7.在考试过程中，若计算机出现故障，请及时通知工作人员，以免耽误您的考试时间。
8.上机考试结束后，请勿马上离开，工作人员将会直接进行现场测试，需要您的合作。
————————————————————————————————————————————————————————
试题一（5个测试数据，每个5分，共25分）
求N的阶乘
变量条件：N为正整数，且N≤1000。
运行时限：1秒/测试数据。
输入格式：仅一个数，N。
输出格式：仅一个数，N！的结果。
可执行文件：program1.exe
样例一：
Input.txt
4
Output.txt
24
样例二：
Input.txt
15
Output.txt
1307674368000
题解链接：点击链接
AC代码：
import java.util.*;import java.math.BigInteger;public class Test {public static void main(String[] args) {Scanner in=new Scanner(System.in);while (in.hasNext()){int n=in.nextInt();BigInteger sum=BigInteger.valueOf(1);for(int i=1;i<=n;i++){sum=sum.multiply(BigInteger.valueOf(i));}System.out.println(sum);}}}
————————————————————————————————————————————————————
试题二（7个测试数据，每个5分，共35分）
给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。对于S的所有非空连续子序列T，求最大的序列和。
变量条件：N为正整数，N≤1000000，结果序列和在范围（-2e63,2e63-1）以内。
运行时限：2秒/测试数据
输入格式：第一行为一个正整数N，第二行为N个整数，表示序列中的数。
输出格式：仅一个整数，表示最大序列和。
可执行文件：program2.exe
样例一：
Input.txt
515-324
Output.txt
9
解释：子序列“1，5，-3，2，4”具有最大的序列和，9=1+5+(-3)+2+4
样例二：
Input.txt
61-234-106
Output.txt
7
解释：子序列“3，4”具有最大的序列和，7=3+4
样例三：
Input.txt
4-3-1-2-5
Output.txt
-1
解释：子序列“-1”具有最大的序列和，-1=-1
题解链接：点击链接
#include <iostream>using namespace std;const int nmax=1000000;const int mmin=-999999999;int main(int argc, char** argv) {int n;while(cin>>n){long tmp;long sum=0;long mmax=mmin;for(int i=0;i<n;i++){cin>>tmp;sum=max(sum+tmp,tmp);mmax=max(mmax,sum);}cout<<mmax<<endl;} return 0;}
————————————————————————————————————————————————————————
试题三（8个测试数据，每个5分，共40分）
二叉树的前序、中序、后序遍历的定义：
前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。
变量条件：二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
运行时限：1秒/测试数据。
输入格式：两行，第一行为前序遍历，第二行为中序遍历。
输出格式：若不能根据前序和中序遍历求出后序遍历，输出NOANSWER；否则输出一行，为后序遍历。
可执行文件：program3.exe
样例一：
Input.txt
ABCBAC
Output.txt
BCA
样例二：
Input.txt
FDXEAGXDEFAG
Output.txt
XEDGAF
样例三：
Input.txt
ABCDBDAC
Output.txt
NOANSWER
代码：样例三最后多打印了一行NO ANSWER。
题解链接：点击链接
#include <iostream>#include <cstdio>using namespace std;struct node{char data;//data是char类型 node* lchild;node* rchild;};void PostOrder(node* root){//后根遍历,传入参数为根节点 if(root==NULL){return;}PostOrder(root->lchild);PostOrder(root->rchild);printf("%c",root->data);}node* Create(string preorder,string inorder){node* root=NULL;if(preorder.size()>0){root=new node;root->data=preorder[0];//根节点root->lchild=NULL;root->rchild=NULL;string pre1,pre2;string in1,in2;int index=inorder.find(preorder[0]);//中序中找到根if(index==-1){cout<<"NO ANSWER"<<endl;return 0;}pre1=preorder.substr(1,index);pre2=preorder.substr(index+1,preorder.size()-index-1); in1=inorder.substr(0,index);in2=inorder.substr(index+1,inorder.size()-index-1);root->lchild=Create(pre1,in1);root->rchild=Create(pre2,in2);}return root;} int main(int argc, char** argv) {string s1,s2;while(cin>>s1>>s2){node* t=Create(s1,s2);PostOrder(t);cout<<endl; }return 0;}/*ABCBACBCAFDXEAGXDEFAGXEDGAFABCDBDACNO ANSWER*/
————————————————————————————————————————————————————
测试用例说明
试题一
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字母
