复旦大学计算机科学技术学院专业硕士复试上机考试题(2013-03-27).pdfVIP

复旦大学计算机科学技术学院专业硕士复试上机考试题

（2013-03-27）

第一篇：复旦大学计算机科学技术学院专业硕士复试上机考试题

(2013-03-27)

复旦大学计算机科学技术学院专业硕士复试上机考试题（2013-

03-27）

建议时间：120分钟。

评分方法和注意事项：

1.按考场老师指示的方法和要求提交源代码文件。按题目编号命

名和上传源代码文件problem1.cpp、problem2.cpp、

problem3.cpp。提交不必要的文件、建不必要的文件夹、不必要的压

缩、不按要求命名文件，而导致评测程序找不到对应文件的，将得0

分。

2.第一、二题我们拟只采用黑盒测试，因此：可以不书写注释；

更不必美化程序。3.第三题我们对未通过黑盒测试的程序，将检查其

程序，因此推荐写解题思路、注释，保持良好的编程风格。解题思路

以注释的形式，放在源代码文件的开始，建议采用伪代码风格。如果

您不能完成全部代码，书写正确的解题思路可能得部分分数。4.仔细

阅读题目要求，一定要确保您的输入输出严格符合要求。如输入输出

格式不严格遵循题目的要求，会导致被判断为结果错误而不得分。没

有特别说明的，输入为标准输入（键盘），输出为标准输出（屏幕）。

5.提交的源代码必须保持无编译错误，提交有编译错误的程序该

题直接得-10分。6.除题目另有要求外，程序执行时间应在1秒之内，

程序中的死循环恕不等待。7.不要编写破坏性程序，否则产生的结果

对您也是破坏性的，即取消评分资格。

Problem1:字符串匹配

对于主串M和模式串P，找到P在M中出现的所有子串的第一个

字符在P中的位置。P中第一个字符所在的位置为0。首行的数字表示

有多少组字符串。[输入及示例]2ababababaababaaaaaa[输出及

示例]02401(相邻位置之间用一个空格隔开)Problem2:AFamous

ICPCTeam

Mr.B,Mr.G,Mr.MandtheircoachProfessorSareplanning

theirwayfortheACM-ICPCWorldFinals.Eachofthefourhasa

square-shapedsuitcasewithsidelength

Ai(1=i=4)respectively.Theywanttopacktheirsuitcasesintoa

largesquarebox.Theheightsofthelargeboxaswellasthefour

suitcasesareexactlythesame.Sotheyonlyneedtoconsiderthe

largebox’ssidelength.Ofcourse,youshouldwriteaprogram

tooutputtheminimumsidelengthofthelargebox,sothatthe

foursuitcasescanbeputintotheboxwithoutoverlapping.[Input]

ThereareNtestcases.ThefirstlineisN.Eachtestcase

containsonlyonelinecontaining4integersAi(1=i=4,

1=Ai=1,000,000,000)indicatingthesidelengthofeach

suitcase.[Output]

Foreachtestcase,displayasinglelinecontainingthecase

numberandtheminimumsidelengthofthelargebox

required.[SampleInput]222222221[OutputforSample