《程序设计基础 期末考试题目 2009》由会员分享，可在线阅读，更多相关《程序设计基础 期末考试题目 2009（4页珍藏版）》请在金锄头文库上搜索。
1、 第1页 共 4 页清华大学试卷清华大学试卷（本科生专用）（本科生专用） 考场纪律 一、学生应试时必须携带学生证，以备查对，学生必须按照监考老师指定的座位就坐。 二、除答卷必须用的笔、橡皮及老师指定的考试用具外，不得携带任何书籍、笔记、草稿纸等。 三、答卷时不准互借文具（包括计算器） 。题纸上如有字迹不清等问题，学生应举手请监考教师解决。 四、学生应独立答卷，严禁左顾右盼、交头接耳、抄袭或看别人答卷等各种形式的作弊行为，如有违反， 当场取消其考试资格，答卷作废。 五、在规定的时间内答卷，不得拖延。交卷时间到，学生须在原座位安静地等候监考教师收卷后，方可离 开考场。 系别 班号 200 级 班
2、学号 姓名 成绩 考试课程 日期 200 年 月 日 阅卷老师 题号 一 二 三 四 五 六 七 八 九 十 十一 十二 总分 成绩 说明：请务必在每个源程序的最开头以注释的形式写上你的姓名和学号。说明：请务必在每个源程序的最开头以注释的形式写上你的姓名和学号。 一、 （10 分）编写一个程序，计算以下的数列： 1)2() 1(*31301)( nnFnFnnnF 要求：用户输入 n（10 n = 0） ，然后程序输出第 n 个元素的值。以下是一次运行的结果。样例输入样例输入 样例输出样例输出 5 144 二、 （20 分）考虑如下的 88 数据网格： 2 4 6 8 9 7 5 3 3 4
3、6 7 8 4 3 2 5 8 4 9 0 4 3 2 4 3 2 1 6 7 8 9 4 5 6 7 8 9 0 7 2 3 4 6 7 8 9 6 1 2 3 4 5 6 7 8 0 9 8 7 6 5 4 3 假设网格左下角的坐标为（1，1） ，右下角的坐标为（1，8） ，左上角的坐标为（8，1） ，右上角的坐标 为（8，8） 。输入一个长方形的两个不相邻的顶点坐标，然后计算该长方形所包含的所有整数之和。例 如，对于顶点（1，2）和（3，5） ，相应的长方形包含了三行数据，即（9，8，7，6） （最底行） 、 （2， 3，4，5） （中间行）和（3，4，6，7） （最顶行） ，这 12
4、个整数之和为 64。 第2页 共 4 页输入格式：输入只有一行，即四个正整数，表示两个不相邻的顶点的坐标。 输出格式：输出只有一行，即相应的长方形所包含的所有整数之和。 说明：对于输入的这两个顶点，它们的相对位置是未知的，不能假定第个顶点一定是位于第个 顶点的左下方。样例输入样例输入 样例输出样例输出 1 2 3 5 64 三、 （20 分）编写一个程序，输入一个句子，然后去掉其中所有重复出现的单词（只保留 1 个） ，并将 剩余的单词按照“长度字母”顺序进行排列，然后打印出来。所谓“长度字母”顺序，就是把较短 的单词放在前面，较长的单词放在后面，如果两个单词的长度相同，那么再按照字母顺序进行
5、排序。 说明： （1）由于句子当中包含有空格，所以应该用 gets 函数来输入这个句子； （2）输入的句子当 中只包含英文字符和空格，单词之间用一个空格隔开； （3）不用考虑单词的大小写，假设输入的都是 小写字符； （4）句子长度不超过 100 个字符； （）允许使用如下的字符串操作函数： unsigned int strlen(char *str); char *strcpy(char *dest, char *src); int strcmp(char *s1, char *s2); char *strcat(char *dest, char *src); 输入格式：输入只有一行，即一个英
6、文句子。 输出格式：输出只有一行，即经过去重、排序之后得到的句子。 样例：样例输入：样例输入： jingle bells jingle bells jingle all the way 样例输出：样例输出： all the way bells jingle 四、 （20 分）编写一个程序，首先根据用户的输入信息创建一条链表 LA，每个链表结点的内容为学生 的学号（正整数） ，各结点之间按学号升序排列。然后再根据用户的输入信息创建另一条链表 LB，每 个链表结点包括学生的学号 S 和一个运算符 O，O 的值为“增加”或“删除” 。接下来，程序将对 LB 的每个结点进行分析，如果 O 的值为“增加
7、” ，则在链表 LA 中新增一个结点，其学号即为 S（若 LA 中已有一个学号为 S 的结点，则不进行此操作） ；如果 O 的值为“删除” ，则在链表 LA 中，找到学号 为 S 的结点并将其删除（若 LA 中没有学号为 S 的结点，则不进行此操作） 。在经过上述处理后，要求 LA 中的结点依然按学号升序排列。 说明： （1）在创建链表时，为了减少内存空间的浪费，必须采用动态链表动态链表的方法，即每一个链表 结点都是根据需要动态创建的； （2）为了增强程序的可读性，应采用多函数的形式来实现，至少应包 含如下的函数：创建链表、打印链表等。 输入格式：第一行是一个整数 M，表示链表 LA 的结点个
8、数，接下来有 M 行，每一行是一个整数 si，表示第 i 个结点的学号（在输入时肯定是按照从小到大的顺序） 。接下来的一行是一个整数 N，表 示链表 LB 的结点个数，再接下来有 N行，每一行是两个整数 si和 oi，其中，si表示第 i 个结点的学号 （在输入时也是按从小到大的顺序） ，oi表示运算符，oi 表示“增加”结点，oi 表示“删除”结点。 输出格式：输出经过处理以后的链表 LA 的内容。假设该链表共有 K 个结点，则输出有 K 行，每第3页 共 4 页一行是一个整数，即相应的学号。 样例：样例输入样例输入 样例输出样例输出 4 1001 1003 1005 1007 2 1002
9、 1 1007 0 1001 1002 1003 1005 五、 （20 分）贴邮票问题。小明去邮局寄包裹，寄包裹的流程是这样的：先把包裹放在一台自动秤上称 一下，该秤将会显示所需要的邮费。然后再购买相应数量的邮票贴上去，并交给邮局工作人员即可。 邮局最多有十种不同面值的邮票，而在一个包裹上，最多只能贴 10 张邮票。请编写一个程序，根据所 需要的邮费（不超过 30 元） ，为小明选择相应数量和面值的邮票。 输入格式：第一行是一个整数 M，表示有多少种不同面值的邮票。接下来有 M 行，每一行是一个 整数 si，表示第 i 种邮票的面值（面值以“分”为单位，并按照从小到大的顺序排列） 。再接下来
10、的一 行是一个整数 N，表示包裹的邮费（不超过 3000） 。 输出格式：第一行是一个整数 K，表示所需的邮票数量，接下来有 K 行，每一行是一个整数，表 示邮票的面值。 说明：在挑选邮票时，邮票的总面值必须大于或等于邮费，如果无法做到正好相等，那么要尽可 能接近，以免浪费。如果存在多种可行方案，则优先选择邮票面值最接近的；如果邮票面值相同，则 优先选择邮票数量最少的；如果邮票面值相同且邮票数量也相同，则任选一个。如果找不到可行方案， 则显示“No Solution“。 例如，假设邮局有种邮票，面值分别为、，如果邮费为，则最佳方案 为；如果邮费为，则最佳方案为；如果邮费为，则最佳方案为。 样例
11、： 样例输入样例输入 样例输出样例输出 7 2 7 14 17 22 63 98 143 3 63 63 17 六、 （10 分） 在美国加州硅谷， 曾经出现过一个神秘的大广告牌， 上面只写了一句话： First 10 digit prime in consecutive digits of e .com。原来，这是 google 公司的一个招聘线索，它的意思是说，在 e（自然对 数的底）当中，寻找第一个由连续数位所构成的长度为 10 的质数，然后去访问以该数为名称的网站。 e 是一个无限不循环小数，它的前几位为：e = 2.71828182845904523536。它的计算公式是： 第4页 共 4 页.! 31 ! 21 ! 111e 请编写一个程序，先计算出e的近似值，然后在其中寻找第一个由连续数位所构成的长度为10的 质数。程序没有输入，输出即为该质数。 提示： （）该质数出现在小数点后位以内，因此e的精度必须足够高，而通常的实数类型无法 提供这么高的精度； （）阶乘的增长速度非常快，例如，就已经比较大了，已经无法存放在一个整 型变量中；而就更大了，它已经无法存放在一个浮点型变量中。
