清华大学计算机科学与技术系

2007年硕士研究生招生复试

2007年3月24日

注意事项：

1. 试题共三题，总计100分，考试时间为一个半小时。

2. 不得使用自带的电子设备，包括笔记本、U盘、手机等；不得使用参考书籍和资料。 3. 编程环境为Windows 2000 Professional + Visual Studio 6.0，只能使用C/C++语言。

4. 每一题的输入数据都从文件input.txt中读取，将结果输出至文件output.txt，请严格按照

每一题的输入输出格式。在考试过程中，我们恕不提供除试题中样例以外的测试数据，请自行生成输入数据以对程序进行自测。

5. 请在考试结束之前自行设置编译环境和配置编译参数，将所写的程序编译成可执行文

件，文件名在每一题中都有规定。生成的可执行文件将作为最终测试的唯一依据，若无法运行您的可执行文件，最终成绩将记为零分。

6. 程序对每个测试数据的可用运行时间上限1秒，若超时或结果错误，则该测试用例不能

得分。

7. 在考试过程中，若计算机出现故障，请及时通知工作人员，以免耽误您的考试时间。 8. 上机考试结束后，请勿马上离开，工作人员将会直接进行现场测试，需要您的合作。

第一题（可执行文件名program1.exe）

求正整数N(N>1)的质因数的个数。注意：1不是N的质因数：若N为质数，N是N的质因数。相同的质因数需要重复计算。

如120=2*2*2*3*5，共有5个质因数。

输入：

9

正整数N，1N的质因数的个数

样例输入： 120 样例输出 5

第二题（可执行文件名：program2.exe）

对于一个十进制数A，将A转换为二进制数，然后按位逆序排列，再转换为十进制数B，我们乘B为A的二进制逆序数。

例如对于十进制数173，它的二进制形式为101011101，逆序排列得到10110101，其十进制数为181，181即为173的二进制逆序数

输入：

999

一个1000位(即10)以内的十进制数。 输出：

输入的十进制数的二进制逆序数。

样例输入： 173 样例输出： 181

第三题（可执行文件名program3.exe）

有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。

如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。 输入：

首先是要求凑成的邮票总值M，M<100

然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。 输出：

能够凑成总值M的最少邮票张数。若无解，输出0。

样例输入： 10 5 1 3 3 3 4 样例输出： 3