复旦大学计算机科学技术学院专业硕士复试上机考试题(0327)_复旦金融专硕复试题库

复旦大学计算机科学技术学院专业硕士复试上机考试题(0327)由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“复旦金融专硕复试题库”。

复旦大学计算机科学技术学院 专业硕士复试上机考试题（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。首行的数字表示有多少组字符串。[输入及示例] 2 ababababa ababa aaa aa [输出及示例] 0 2 4 0 1(相邻位置之间用一个空格隔开)Problem2:A Famous ICPC Team

Mr.B, Mr.G, Mr.M and their coach Profeor S are planning their way for the ACM-ICPC World Finals.Each of the four has a square-shaped suitcase with side length Ai(1

There are N test cases.The first line is N.Each test case contains only one line containing 4 integers Ai(1

For each test case, display a single line containing the case number and the minimum side length of the large box required.[Sample Input] 2 2 2 2 2 2 2 2 1 [Output for Sample Input]

Case 1: 4 Case 2: 4 [Explanation]

For the first case, all suitcases have size 2x2.So they can perfectly be packed in a 4x4 large box without wasting any space.For the second case, three suitcases have size 2x2 and the last one is 1x1.No matter how you rotate or move the suitcases, the side length of the large box must be at least 4.Problem3：A Famous Grid Mr.B has recently discovered the grid named “spiral grid”.Construct the grid like the following figure.(The grid is actually infinite.The figure is only a small part of it.)

Considering traveling in it, you are free to any cell containing a composite number or 1, but traveling to any cell containing a prime number is disallowed.You can travel up, down, left or right, but not diagonally.Write a program to find the length of the shortest path between pairs of nonprime numbers, or report it's impoible.[Input]

There are N test cases.The first line is N.Each test case is described by a line of input containing two nonprime integer 1

For each test case, display its case number followed by the length of the shortest path or “impoible”(without quotes)in one line.[Sample Input] 3 1 4 9 32 10 12

[Output for Sample Input] Case 1: 1 Case 2: 7

Case 3: impoible