东华大学2015年计算机学院研究生复试上机考真题

1、2015年硕士学位研究生招生复试笔试一试题考试科目：C语言与数据构造算法上机测试考试时间120分钟注意事项：1、源程序都在D:TEST文件夹下，请先将该“TEST文件夹更名为准考据号_姓名”此中准考据号是初试时的15位准考据号；2、考试结束后，第一删除VC+6.0自动生成的debug文件夹，而后使用压缩软件将上述考生文件夹中全部内容打包（包含里面全部文件，比方工程文件等。除上述debug文件夹外，不得删除任何考试过程中产生的文件，文件名为准考据号J生名.rar而后将该文件经过教课系统的学生端的传文件给教师”功能上传到服务器。1文件上传后,需到监考老师处确认方可走开考场。假如未经监考老师确认而且

2、文件因为某种原由上传未成功，考试成绩以0分计。2上传的压缩包解压后将立刻看到全部文件，压缩包中不得包含任何子文件夹。压缩包被翻开后的图示见附录，此中附图a和附图b错误，附图c正确。3、假如已经上传，需要改正而后再上传的，在压缩包的文件名后加编号2、3、4等，形如：考号J生名2.rar、”考号姓名3.rar。在监考老师处确认时，恳求监考老师将老文件删除。4、全部供给的文件(包含C源文件，不得改正文件名，也不得改正其内部构造(详见题目中的红字。5、全部程序需要在VC环境中运转，结果正确方可。比方，程序填空，不可以仅将空填好，而是需要运转程序，进行测试，保证正确。6本考试共包含1道程序改错、1道程序

3、填空、3道程序编写题，分数分别为:30、15、15、20、20。7、考试题文字描绘见下页,C程序见考生文件夹下相应文件。(1(30分给定程序modi.c中,程序的功能是：输出100到999之间的全部水仙花数。水仙花数的特色是：它的每个位上的数字的3次幕之和等于它自己。(例如:371=3A3+7A3+1A3,所以371是水仙花数。请改正程序中的五行标志有错的代码，并注意在原程序上做尽量少的改正，使得程序能运转出正确的结果。注意:不得改正其余程序行，不得增行或删行,也不得改正程序的构造！(2(15分给定程序blank.c中已成立一个带有头结点的单向链表，链表中的各结点数据域中的数据各不同样，而且按

4、结点数据域中的数据从小到大次序链接。函数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,它的功能是：依

5、据以下公式求n的值(要求知足精度0.0005，即某项小于0.0005时停止迭代：兀11X21X2X31X2X3X4lX2X-Xn=1+-1-1-+-+4-巧QrQVrV-.iX/丄斗程序运转后，假如输入精度0.005则程序输出为3.132157,假如输入精度0.0005则程序输出为3.14057&注意:部分源程序存在文件prog1.c中。请勿变动主函数main和其余函数中的任何内容，仅在函数fun的花括号中填入你编写的若干语句。(4(20分在一个递加有序的数组中，有数值同样的元素存在，程序的功能是去掉数值相同的元素，使数组中不再有重复的元素。比如：(7,10,10,21,30,42,42,42

6、,51将变为(7,10,21,30,42,51。主函数main中，第一输入有序数组的元素数量及各元素的值，而后将数组及元素数量传入函数fun中，函数fun达成删除重复元素的操作。部分源程序存贮在文件prog1.c中,请达成fun函数。要求:尽量优化算法的时间复杂度与空间复杂度，并在prog2.c的最前面增添说明,简要介绍自己的算法，并指出该算法拥有什么样的时间复杂度与空间复杂度。请勿变动主函数main和其余函数中的任何内容，仅在最前面增添说明，并在函数fun的花括号中填入你编写的若干语句。(5(20分从数据构造中树的定义可知，除根结点外,树中的每个结点都有独一的一个双亲结点。依据这一特征，可用

7、一组连续的储存空间(一维数组储存树中的各结点。树中的结点除保留结点自己的信息以外，还要保留其双亲结点在数组中的地点(即在数组中的下标。双亲的信息为-1则表示该结点为根结点，树的这类表示法称为双亲表示法。树的每个结点的数据种类定义以下：structPTNodechardata;/结点数据域intparent;结点双亲在数组中的地点;树的数据种类定义以下：#defineMAX_TREE_SIZE100structPTreestructPTNodenodesMAX_TREE_SIZE;/储存树中全部结点intn;/树中共有n个结点,n不超出100;则下列图a所示的树，依据双亲表示法储存构造，储存为图

8、b所示形式（n为10序号dataparent图a树的表示图图b双亲表示法储存已知一棵树已储存为以上形式，请编写函数GetLeavesCount计算叶子结点数量。GetLeavesCount的函数原型为：intGetLeavesCount(structPTreeT此中，形参T中保留了树中结点数量及图b所示的结点数组。函数返回叶子结点的数量。比方对图b的树调用函数GetLeavesCount(T返回结果为6(因为有6个叶子结点。部分代码在prog3.c中,请仅在GetLeavesCount函数中填入内容，达成程序。要求:尽量优化算法的时间复杂度与空间复杂度，并在GetLeavesCount函数前的

9、说明部分简要介绍自己的算法，同时指出该算法拥有什么样的时间复杂度与空间复杂度。请勿变动主函数main和其余已有函数中的任何内容，能够在函数GetLeavesCount的花括号中填入你编写的若干语句，同意增添自定义函数。prog3.c中,structPTreeCreateTree函数用于从键盘输入树的双亲表示法的信息创立一棵树。输入的第一个数n表示树中结点数，今后有n行输入，每行表示一个结点的信息，第一个信息为结点的数据，第二个信息为结点的双亲结点在数组中的地点。如输入：10-1c00111233则将创立图b所对应的树。对此树调用函数GetLeavesCount(T返回结果为6如输入：8-101

10、20g5对此树调用函数GetLeavesCount(T返回结果为4附录:压缩方式图示附图a翻开压缩包后，看到的是文件夹，错误!File(QmrrTndt7adjOptionsHelpAddExtractTaTtstVipwDeleteFtl14L011001M?Nimc鼻”Jt?bLjgIWbl*nk-cIbidnk冷甲blank.d3w曲blank.neb(JtrtanlLoptblankrplg孙nl,d矶gin2d?t3modi.dlspSmdi-dsw卜inFar-RARarchivt.unpackSKZKPack.TypeFolderFolderB69CSourceJU972VC*+6_.血232VC*6lP06lVC*Int-1,194Fileopt?3421