计算机学院研究生复试上机考试真题.pdf
- 文档编号:14651482
- 上传时间:2023-06-25
- 格式:PDF
- 页数:5
- 大小:228.18KB
计算机学院研究生复试上机考试真题.pdf
《计算机学院研究生复试上机考试真题.pdf》由会员分享,可在线阅读,更多相关《计算机学院研究生复试上机考试真题.pdf(5页珍藏版)》请在冰点文库上搜索。
-1-20172017年年硕士硕士学位研究生招生学位研究生招生复试复试上机上机试题试题考试科目:
考试科目:
C语言与数据结构算法上机测试考试时间112200分钟注意事项:
注意事项:
11、源程序都在源程序都在D:
D:
TESTTEST文件夹下,请先将该“文件夹下,请先将该“TESTTEST”文件夹改名为“准考证号”文件夹改名为“准考证号__姓名”,其中准考证号是初试时的姓名”,其中准考证号是初试时的1515位准考证号;位准考证号;22、考试、考试结束结束后,首先删除后,首先删除VC+6.0VC+6.0自动生成的自动生成的debugdebug文件夹,然后使用文件夹,然后使用压缩软压缩软件件将上述考生文件夹中所有内容打包(包括里面所有文件,比如工程文件将上述考生文件夹中所有内容打包(包括里面所有文件,比如工程文件等等。
除除上述上述debugdebug文件夹外,文件夹外,不得删除任何考试过程中产生不得删除任何考试过程中产生的文件的文件),文件),文件名为“名为“准考证号准考证号__姓名姓名.rar.rar”,然后将该文件”,然后将该文件通过教学系统的学生端的“传通过教学系统的学生端的“传文件给教师”功能上传到服务器。
文件给教师”功能上传到服务器。
注意:
注意:
文件上传后,需到监考老师处确认方可离开考场。
如果未经监考老师确认,文件上传后,需到监考老师处确认方可离开考场。
如果未经监考老师确认,并且文件由于某种原因上传未成功,考试成绩以并且文件由于某种原因上传未成功,考试成绩以00分计。
分计。
33、如果已经上传,需要修改然后再上传的,在压缩包的文件名后加编号、如果已经上传,需要修改然后再上传的,在压缩包的文件名后加编号22、33、44等,形如:
“考号等,形如:
“考号__姓名姓名2.rar2.rar”、“考号”、“考号__姓名姓名3.rar3.rar”。
”。
在监考老师处确在监考老师处确认时,请求监考老师将老文件删除。
认时,请求监考老师将老文件删除。
44、所有提供的文件(包括、所有提供的文件(包括CC源文件),不得源文件),不得更更改改文件文件名,也不得更改其名,也不得更改其内部内部结结构(详见题目中的构(详见题目中的红字)。
红字)。
55、所有程序需要在、所有程序需要在VCVC+6.0+6.0环境中运行,结果正确方可。
比如,程序填空,不环境中运行,结果正确方可。
比如,程序填空,不能仅将空填好,而是需要运行程序,进行测试,确保正确。
能仅将空填好,而是需要运行程序,进行测试,确保正确。
66、本考试共包括、本考试共包括11道程序改错、道程序改错、22道程序填空、道程序填空、33道程序编写题,分数道程序编写题,分数分别分别为:
为:
2020、1155、1515、1515、1515、2020。
77、考试题文字描述见下、考试题文字描述见下,CC程序见考生文件夹下相应文件。
程序见考生文件夹下相应文件。
-2-
(1)
(1)给定程序给定程序modi.cmodi.c中,函数中,函数funfun的功能是:
用下面的公式求的功能是:
用下面的公式求的近似值,直到最后一项的的近似值,直到最后一项的绝对值小于指定的数(参数绝对值小于指定的数(参数numnum)为止)为止(该项不包括在结果中该项不包括在结果中):
例如,程序运行后,输入例如,程序运行后,输入0.00010.0001,则程序输出,则程序输出3.14143.1414。
请改正程序中的错误,使它能得出正确结果。
请改正程序中的错误,使它能得出正确结果。
注意:
不要改动注意:
不要改动mainmain函数,不得增行或删行,也不得更改程序的结构!
函数,不得增行或删行,也不得更改程序的结构!
(2)
(2)给定程序给定程序blankblank1.1.cc中,函数中,函数funfun的功能是:
找出的功能是:
找出100100至至xx(xx999999)之间各位上的数字之)之间各位上的数字之和为和为1515的所有整数,然后输出;符合条件的整数个数作为函数值返回。
的所有整数,然后输出;符合条件的整数个数作为函数值返回。
例如,当例如,当xx值为值为500500时,各位数字之和为时,各位数字之和为1515的整数有:
的整数有:
159159、168168、177177、186186、195195、249249、258258、267267、276276、285285、294294、339339、348348、357357、366366、375375、384384、393393、429429、438438、447447、456456、465465、474474、483483、492492。
共有。
共有2626个。
个。
所以所以,程序程序运行运行后后,输入输入550000,则则输出输出Theresultis:
Theresultis:
2626。
请在程序的下划线处填入正确的内容并把下划线删除请在程序的下划线处填入正确的内容并把下划线删除,使程序得出正确的结果。
,使程序得出正确的结果。
注意:
注意:
不得增行或删行,也不得更改程序的结构!
不得增行或删行,也不得更改程序的结构!
(3)(3)给定程序给定程序blank2blank2.cc中,函数中,函数funfun的功能是将的功能是将aa和和bb所指的两个字符串转换成面值相同的整所指的两个字符串转换成面值相同的整数,并进行相加作为函数值返回,规定字符串中只数,并进行相加作为函数值返回,规定字符串中只包含包含数字字符。
数字字符。
例如,主函数例如,主函数mainmain中输入字符串:
中输入字符串:
3248632486和和1123452345,在主函数中输出的函数值为:
,在主函数中输出的函数值为:
4483144831。
请在程序的下划线处填入正确的内容并把下划线删除请在程序的下划线处填入正确的内容并把下划线删除,使程序得出正确的结果。
,使程序得出正确的结果。
注意:
注意:
不得增行或删行,也不得更改程序的结构!
不得增行或删行,也不得更改程序的结构!
(4)(4)有有nn(nn很大)个范围为很大)个范围为032767032767数字,其中有大量重复的数数字,其中有大量重复的数,在,在mainmain函数中已读入到函数中已读入到datadata数组中数组中,请编写,请编写函数函数funfun,计算剔除重复数字之后,还剩下几个数。
,计算剔除重复数字之后,还剩下几个数。
funfun函数的功能是:
函数的功能是:
传入传入两个形参,一个是数组两个形参,一个是数组datadata,一个是,一个是nn的值,的值,经过计算,经过计算,返回剔除返回剔除重复数字后剩下的数字的个数。
重复数字后剩下的数字的个数。
比如比如,程序程序运行运行时时输入输入:
551111331133则则程序程序输出输出:
22要求:
请衡量时间复杂度和空间复杂度,尽量设计高要求:
请衡量时间复杂度和空间复杂度,尽量设计高效算法。
效算法。
请在请在prog1.cprog1.c最前面的注释部最前面的注释部分介绍自己的算法分介绍自己的算法。
注意:
部分源程序存在文件注意:
部分源程序存在文件progprog11.c.c中。
中。
请勿改动主函数请勿改动主函数mainmain和其他函数中的任何内容,仅在函数和其他函数中的任何内容,仅在函数funfun的花括号中填入你编写的的花括号中填入你编写的若干语句。
若干语句。
-3-(5)(5)计算所需要计算所需要最少拦截系统最少拦截系统的数目:
的数目:
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷:
虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都缺陷:
虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能达到不能达到前一发前一发的高度。
的高度。
某天,雷达捕捉到敌国的导弹来袭,如果系统数量太少,将导致有可能不能拦截所有的导某天,雷达捕捉到敌国的导弹来袭,如果系统数量太少,将导致有可能不能拦截所有的导弹。
所以,根据雷达捕捉弹。
所以,根据雷达捕捉到的导弹高度到的导弹高度(导弹总数目不超过(导弹总数目不超过1000),需要预先准备相应数,需要预先准备相应数量的拦截系统。
量的拦截系统。
比如导弹的高度依次为:
比如导弹的高度依次为:
534241则一个拦截系统的第一发炮弹必须打到高度则一个拦截系统的第一发炮弹必须打到高度5的地方,第二发炮弹打到高度的地方,第二发炮弹打到高度3的地方。
的地方。
但第三发炮弹打不到高度但第三发炮弹打不到高度4的地方(因为每一发炮弹不能达到前一发的高度),所以要使的地方(因为每一发炮弹不能达到前一发的高度),所以要使用第二套拦截系统。
用第二套拦截系统。
第二套拦截系统发射的炮弹高度打到第二套拦截系统发射的炮弹高度打到4和和2的高度的高度(实际上实际上,要拦截高度为要拦截高度为2的炮弹的炮弹,使用第使用第一套拦截系统或者第二套都可以一套拦截系统或者第二套都可以)。
第三套拦截系统发射的炮弹高度打到第三套拦截系统发射的炮弹高度打到4和和1的高度的高度(实际上实际上,要拦截高度为要拦截高度为1的炮弹的炮弹,三套拦三套拦截系统都可以截系统都可以)。
因此,总共需要三套拦截系统。
因此,总共需要三套拦截系统。
再比如导弹的高度依次为:
再比如导弹的高度依次为:
534231则一个拦截系统的第一发炮弹必须打到高度则一个拦截系统的第一发炮弹必须打到高度5的地方,第二发炮弹打到高度的地方,第二发炮弹打到高度3的地方。
的地方。
但第三发炮弹打不到高度但第三发炮弹打不到高度4的地方(因为每一发炮弹不能达到前一发的高度),所以要使的地方(因为每一发炮弹不能达到前一发的高度),所以要使用第二套拦截系统。
用第二套拦截系统。
第二套拦截系统发射的炮弹高度打到第二套拦截系统发射的炮弹高度打到4的高度。
的高度。
再要拦截高度为再要拦截高度为2的炮弹的炮弹,使用第一套拦截系统或者第二套都可以,但考虑到后面还需要拦使用第一套拦截系统或者第二套都可以,但考虑到后面还需要拦截炮弹,我们这里使用第一套拦截截炮弹,我们这里使用第一套拦截系统(为什么不能用第二套,自己想啦)。
系统(为什么不能用第二套,自己想啦)。
再要拦截高度为再要拦截高度为3的炮弹的炮弹,我们使用第二套拦截系统。
我们使用第二套拦截系统。
再拦截高度为再拦截高度为1的炮弹,第一套和第二套系统都可以,我们使用第的炮弹,第一套和第二套系统都可以,我们使用第一一套。
套。
因此,总共仅需要两套拦截系统,第一套拦截的是因此,总共仅需要两套拦截系统,第一套拦截的是5321,第二套拦截的是,第二套拦截的是43。
请根据给定的高度数据,帮助计算一下最少需要多少套拦截系统。
请根据给定的高度数据,帮助计算一下最少需要多少套拦截系统。
在在mainmain函数中,首先输入函数中,首先输入nn,表示共有,表示共有nn个导弹,然后读入导弹的高度到数组个导弹,然后读入导弹的高度到数组aa中。
中。
funfun函数接受函数接受aa数组和数组和nn两个参数,计算需要的拦截系统的数目,并返回该结果。
请完成两个参数,计算需要的拦截系统的数目,并返回该结果。
请完成funfun函数。
函数。
比如比如,程序程序运行运行时时输入输入:
66534231534231则则程序程序输出输出:
“Thenumberis:
2Thenumberis:
2”-4-注意:
部分源程序存贮在文件注意:
部分源程序存贮在文件progprog22.c.c中。
中。
请勿改动主函数请勿改动主函数mainmain和其它函数中的任何内容,仅在函数和其它函数中的任何内容,仅在函数funfun的花括号中填入你编写的的花括号中填入你编写的若干语句。
若干语句。
(66)从从数据结构中数据结构中树的定义可知,除根结点外,树中的每个结点都有唯一的一个双亲结点。
树的定义可知,除根结点外,树中的每个结点都有唯一的一个双亲结点。
根据这一特性,可用一组连续的存储空间(一维数组)存储树中的各结点。
树中的结点根据这一特性,可用一组连续的存储空间(一维数组)存储树中的各结点。
树中的结点除保存结点本身的信息之外,还要保存其双亲结点在数组中的位置(除保存结点本身的信息之外,还要保存其双亲结点在数组中的位置(即在即在数组数组中中的的下标。
下标。
双亲的信息为双亲的信息为-11则表示该结点为根结点则表示该结点为根结点),树的这种表示法称为双亲表示法。
),树的这种表示法称为双亲表示法。
树的每个结点的数据类型定义如下:
树的每个结点的数据类型定义如下:
structPTNodestructPTNodechardata;chardata;/结点数据域结点数据域intparent;intparent;/结点双亲在数组中的位置结点双亲在数组中的位置;树的数据类型定义如下:
树的数据类型定义如下:
#defineMAX_TREE_SIZE100#defineMAX_TREE_SIZE100structPTreestructPTreestructPTNodenodesMAX_TREE_SIZE;structPTNodenodesMAX_TREE_SIZE;/存储树中所有结点存储树中所有结点intn;intn;/树中共有树中共有nn个结点,个结点,nn不超过不超过100100;则下图则下图11所示的树,按照双亲表示法存储结构,存储为图所示的树,按照双亲表示法存储结构,存储为图22所示形式(所示形式(nn为为1010)。
)。
序号序号dataparentdataparent图图11树的示意图树的示意图图图22双亲表示法存储双亲表示法存储已知一棵树已存储为以上形式,请编写函数已知一棵树已存储为以上形式,请编写函数GetNearestCommonGrandGetNearestCommonGrand,查找给定的两个查找给定的两个(不相同的)(不相同的)结点最近的共同祖先结点最近的共同祖先。
GetNearestCommonGrandGetNearestCommonGrand的函数原型为:
的函数原型为:
charcharGetNearestCommonGrandGetNearestCommonGrand(stru(structPTreeT,charnodeDatactPTreeT,charnodeData1,charnodeData21,charnodeData2)函数形参函数形参:
TT:
保存了树中结点数目及图:
保存了树中结点数目及图22所示的结点数组所示的结点数组nodeData1,nodeData2nodeData1,nodeData2:
给定的两个结点的数据:
给定的两个结点的数据(输入时保证这两个结点存在)(输入时保证这两个结点存在)。
-5-函数返回值:
函数返回值:
两个结点最近的共同祖先。
两个结点最近的共同祖先。
比如,比如,nodeData1nodeData1为为GG,nodeData2,nodeData2为为HH,则函数返回则函数返回AA。
说明:
输入保证说明:
输入保证nodeData1nodeData1和和nodeData2nodeData2在树中能找到。
在树中能找到。
部分代码在部分代码在prog3.cprog3.c中中,请仅在请仅在GetNearestCommonGrandGetNearestCommonGrand函数中填入函数中填入内容内容,完成完成程序程序。
要求要求:
尽量优化算法的时间复杂度与空间复杂度尽量优化算法的时间复杂度与空间复杂度,并在并在GetNearestCommonGrandGetNearestCommonGrand函数函数前的注释部分简要介绍自己的算法前的注释部分简要介绍自己的算法,同时指出该算法具有什么样的时间复杂度与空间复同时指出该算法具有什么样的时间复杂度与空间复杂度。
杂度。
请勿改动主函数请勿改动主函数mainmain和其它和其它已有函数中的任何内容已有函数中的任何内容,可以可以在函数在函数GetNearestCommonGrandGetNearestCommonGrand的花括号中填入你编写的若干语句的花括号中填入你编写的若干语句,允许增加自定义函数。
允许增加自定义函数。
prog3.cprog3.c中,中,structPTreeCreateTree()structPTreeCreateTree()函数用于从键盘输入树的双亲表示法的信息,创函数用于从键盘输入树的双亲表示法的信息,创建一棵树。
输入的第一个数建一棵树。
输入的第一个数nn表示树中结点数,此后有表示树中结点数,此后有nn行输入,每行表示一个结点的信行输入,每行表示一个结点的信息,其中第一个信息为结点的数据,第二个信息为结点的双亲结点在数组中的位置。
息,其中第一个信息为结点的数据,第二个信息为结点的双亲结点在数组中的位置。
在在mainmain函数函数中中还还需要需要输入输入两两个个结点结点的的字符字符数据数据,查询查询这这两两个个结点结点的的最近最近共同共同祖先祖先。
如输入如输入(第第一一行行为为nn,表示表示共共有有1100个个结点结点,后面后面1100行行,为为1100个个结点结点的的信息信息,最后最后一一行行为为gg和和hh,表示表示查询查询结点结点gg和和结点结点hh的的最近最近共同共同祖先祖先):
1010aa-11b0b0c0c0d0d0e1e1f1f1g1g1h2h2i3i3j3j3ghgh则将创建图则将创建图bb所对应的树。
所对应的树。
输出输出结果为结果为aa如输入如输入:
88aa-11b0b0e1e1hh66c0c0d0d0f5f5g5g5ghgh输出结果为输出结果为dd
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 学院 研究生 复试 上机 考试