2015年硕士学位研究生招生复试笔试试题
考试科目: C语言与数据结构算法上机测试
考试时间120分钟
注意事项:
1、源程序都在D:\TEST文件夹下,请先将该“TEST”文件夹改名为“准考证号_
姓名”,其中准考证号是初试时的15位准考证号;
2、考试结束后,首先删除VC++ 6.0自动生成的debug文件夹,然后使用压缩软件
将上述考生文件夹中所有内容打包(包括里面所有文件,比如工程文件等。
除上述debug文件夹外,不得删除任何考试过程中产生的文件,文件名为“准考证号_姓名.rar”,然后将该文件通过教学系统的学生端的“传文件给教师”
功能上传到服务器。
注意:
1文件上传后,需到监考老师处确认方可离开考场。
如果未经监考老师确认,
并且文件由于某种原因上传未成功,考试成绩以0分计。
2上传的压缩包解压后将立即看到所有文件,压缩包中不得包含任何子文件
夹。
压缩包被打开后的图示见附录,其中附图a和附图b错误,附图c正确。
3、如果已经上传,需要修改然后再上传的,在压缩包的文件名后加编号2、3、4
等,形如:“考号_姓名2.rar”、“考号_姓名3.rar”。
在监考老师处确认时,请求监考老师将老文件删除。
4、所有提供的文件(包括C源文件,不得更改文件名,也不得更改其内部结构
(详见题目中的红字。
5、所有程序需要在VC环境中运行,结果正确方可。
比如,程序填空,不能仅将
空填好,而是需要运行程序,进行测试,确保正确。
6、本考试共包括1道程序改错、1道程序填空、3道程序编写题,分数分别为:
30、 15、 15、 20、 20。
7、考试题文字描述见下页,C程序见考生文件夹下相应文件。
(1 (30分给定程序modi.c中,程序的功能是:输出100到999之间的所有水仙花数。
水
仙花数的特点是:它的每个位上的数字的 3次幂之和等于它本身。
(例
如:371=3^3 + 7^3 + 1^3,因此371是水仙花数。
请修改程序中的五行标记有错的代码,并注意在原程序上做尽量少的修改,使得程序能运行出正确的结果。
注意:不得更改其它程序行,不得增行或删行,也不得更改程序的结构!
(2 (15分给定程序blank.c中已建立一个带有头结点的单向链表,链表中的各结点数据域
中的数据各不相同,并且按结点数据域中的数据从小到大顺序链接。
函数fun 的功能是:把形参x的值放入一个新结点并插入到链表中,插入后各结点仍保持从小到大顺序排列。
如果x在链表中已经存在,则不插入。
链表已有元素为:11,12,15,18,19,22,25,29,则:
如果x为20,插入后链表为:11,12,15,18,19,20,22,25,29
如果x为30,插入后链表为:11,12,15,18,19,22,25,29,30
如果x为12,程序执行后链表保持不变
请在程序的下划线处填入正确的内容并把下划线删除,使程序得出正确的结果。
(15分注意:不得增行或删行,也不得更改程序的结构!
(3 (15分请编写一个函数fun,它的功能是:根据以下公式求π的值(要求满足精度0.0005,即某项小于0.0005时停止迭代:
程序运行后,如果输入精度0.005,则程序输出为3.132157,
如果输入精度0.0005,则程序输出为3.140578。
注意:部分源程序存在文件prog1.c中。
请勿改动主函数main和其他函数中的任何内容,仅在函数fun的花括号中填入你编写的若干语句。
(4 (20分在一个递增有序的数组中,有数值相同的元素存在,程序的功能是去掉数值相同
的元素,使数组中不再有重复的元素。
例如:(7,10,10,21,30,42,42,42,51将变成(7,10,21,30,42,51。
主函数main中,首先输入有序数组的元素数目及各元素的值,然后将数组及元素数目传入函数fun中,函数fun完成删除重复元素的操作。
部分源程序存贮在文件prog1.c中,请完成fun函数。
要求:尽量优化算法的时间复杂度与空间复杂度,并在prog2.c的最前面添加注释,简要介绍自己的算法,并指出该算法具有什么样的时间复杂度与空间复杂度。
请勿改动主函数main和其它函数中的任何内容,仅在最前面添加注释,并在函数fun的花括号中填入你编写的若干语句。
(5 (20分从数据结构中树的定义可知,除根结点外,树中的每个结点都有唯一的一个双亲
结点。
根据这一特性,可用一组连续的存储空间(一维数组存储树中的各结点。
树中的结点除保存结点本身的信息之外,还要保存其双亲结点在数组中的位置(即在数组中的下标。
双亲的信息为-1则表示该结点为根结点,树的这种表示法称为双亲表示法。
树的每个结点的数据类型定义如下:
struct PTNode
{
char data; //结点数据域
int parent; //结点双亲在数组中的位置
};
树的数据类型定义如下:
#define MAX_TREE_SIZE 100
struct PTree
{
struct PTNode nodes[MAX_TREE_SIZE]; //存储树中所有结点
int n; //树中共有n个结点,n不超过100
};
则下图a所示的树,按照双亲表示法存储结构,存储为图b所示形式(n为10。
序号 data parent
图a 树的示意图
图b 双亲表示法存储
已知一棵树已存储为以上形式,请编写函数GetLeavesCount,计算叶子结点数目。
GetLeavesCount的函数原型为:
int GetLeavesCount (struct PTree T
其中,
形参T中保存了树中结点数目及图b所示的结点数组。
函数返回叶子结点的数目。
比如,对图b的树调用函数GetLeavesCount (T,返回结果为6(因为有6个叶子结点。
部分代码在prog3.c中,请仅在GetLeavesCount函数中填入内容,完成程序。
要求:尽量优化算法的时间复杂度与空间复杂度,并在GetLeavesCount函数前的注释部分简要介绍自己的算法,同时指出该算法具有什么样的时间复杂度与空间复杂度。
请勿改动主函数main和其它已有函数中的任何内容,可以在函数GetLeavesCount的花括号中填入你编写的若干语句,允许增加自定义函数。
prog3.c中,struct PTree CreateTree(函数用于从键盘输入树的双亲表示法的信息,创建一棵树。
输入的第一个数n表示树中结点数,此后有n行输入,每行表示一个结点的信息,第一个信息为结点的数据,第二个信息为结点的双亲结点在数组中的位置。
如输入:
10
a -1
b 0
c 0
d 0
e 1
f 1
g 1
h 2
i 3
j 3
则将创建图b所对应的树。
对此树调用函数GetLeavesCount (T,返回结果为6 如输入:
8
a -1
b 0
e 1
h 2
c 0
d 0
f 5
g 5
对此树调用函数GetLeavesCount (T,返回结果为4 附录:压缩方式图示附图a 打开压缩包后,看到的是文件夹,错误!
附图b 附图c 压缩包中包含所有的文件,且无文件夹,正确!。