北邮2011计算机上机复试编程题目

北邮2011计算机上机复试编程题目（共2篇）

篇1：北邮2011计算机上机复试编程题目

Your account is taobao_68.And your passwd: 1138899884

A 句子逆转

输入一个句子，占用一行。句子由单词和单词间的空格组成。单词只有小写字母。单词之间由空格隔开。单词之间不会有多个空格。每个句子至多有1000个字母。多组数据输入。将句子单词的排列顺序倒过来输出。

多组数据输入，以EOF为结束。

SAMPLE

INPUT:

It is a apple

OUTPUT:

apple a is it

B 成绩管理

实现查询成绩的功能。首先输入T表示有T组数据。每组数据首先输入n，接下来有n行输入.每行输入是插入或者查找。插入为Insert id score。id是自然数，不大于1000。每次插入的id都不同。score是自然数，不大于100。查找为Find id。找到输出该id与score。查找不到输出No result!

SAMPLE

INPUT:

Insert 0 10

Find 0

Insert 1 15

Find 1

Find 2

Insert 2 35

Find 2

Output:

name:0 score:10

name:1 score:15

No result!

name:2 score:35

C 寻找宝藏

一棵多叉树T，根结点为0，某个结点上有宝藏。从根结点沿着树枝向下寻找，如果有分支，沿各分支继续寻找是等概率的。计算找到宝藏的概率。首先输入M，N，L。M多叉树T的结点数，结点分别为0~M-1。N和L分别是树枝数和宝藏所在结点。接下来有N行输入，每行两个数，表示这两个结点之间有树枝连接。而且前一个结点比后一个更靠近根结点。输出找到结点的概率，保留六位小数。

SAMPLE

INPUT:6 5 50 10 21 32 42 5

OUTPUT:0.250000HINT:

输出可用printf(“%.6f”,a)

篇2：北邮2011计算机上机复试编程题目

A、字符串操作

Accept:93 Submit:1212 Time Limit:1000MS Memory Limit:65536KB 请仔细阅读“考前必读”

Description

大家平时都会用到字符串，现在有几种字符串操作，需要你用这几种操作处理下字符串。

Input

多组数据，以EOF结束。

第一行一个字符串，字符串长度大于0，并且小于等于200。第二行一个数字t，（0

共有两种操作，每行数据的第一个数表示操作的种类：

翻转操作：第一个是一个数字0，然后两个数字i和len，翻转从下标i长度为len的子串。

替换操作：第一个是一个数字1，然后两个数字i和len，接着一个长度为len的字符串str，用str替换从下标i长度为len的子串。字符串操作后会更新，旧的字符串被舍弃。(详见sample)Output

每个操作之后输出生成的新的字符串

Sample Input

bac 2 0 0 3 1 1 2 as

Sample Output

cab cas

Hint

字符串下标从0开始，所有操作的数据范围都合乎规范。

B、虚数

Accept:36 Submit:448 Time Limit:1000MS Memory Limit:65536KB 请仔细阅读“考前必读”

Description

给你一个复数集合{Aj+i*Bj},保证Aj和Bj都是整数，初始为空集。

每次会给你如下两种操作中的一种：

1.“Insert x+iy”,其中x，y都是整数。表示在集合中加入一个复数 x+iy，同时输出此时集合的大小；

2.“Pop”。如果集合为空集直接返回“Empty!”，如果有元素则以“x+iy”的形式显示集合中模值最大的复数,然后将该元素从集合中删除，之后在第二行显示操作之后的集合大小，如果为空集则显示“Empty!”。

Input

第一行只有一个数T，代表case数。0<=T<=10 每一组case：

第一行有一个整数n，表示这组case中一共有n条命令 0

保证不会输入两个模值同样的元素,并保证实部虚部都大于0,小于1000。

Output

依照上述原则输出每一个命令对应的输出

如果输入命令是Insert命令，则对应的输出占一行为集合大小； 如果输入命令是Pop命令，则对应的输出占一行或者两行，为模值最大的复数和集合大小。

请注意，输出集合大小的格式为“Size:空格x回车”,x为集合大小

Sample Input 5 Pop Insert 1+i2 Insert 2+i3 Pop Pop Sample Output

Empty!Size: 1 Size: 2 2+i3 Size: 1 1+i2 Empty!

C、中序遍历树

Accept:0 Submit:18 Time Limit:1000MS Memory Limit:65536KB 请仔细阅读“考前必读”

Description 给一棵树，你可以把其中任意一个节点作为根节点。每个节点都有一个小写字母，中序遍历，得到一个字符串，求所有能得到的字符串的字典序最小串。因为这棵树不一定是二叉树，所以中序遍历时，先中序遍历以节点序号最小的节点为根的子树，然后再遍历根节点，最后根据节点序号从小到大依次中序遍历剩下的子树。

Input

多组数据，以EOF结束。

第一行一个数n（0

接下来n-1行，每行两个数a，b,(0<=a,b

Output

题中要求的最小的字符串

Sample Input 3 bac 0 1 1 2 4 abcd 0 1 0 2 0 3

Sample Output

bac

bacd

Hint

意思就是请枚举所有的点为根，然后中序遍历 最后输出所有结果中字典序最小的

比如说第二组数据

以0为根时结果为 bacd 以1为根时结果为 cadb 以2为根时结果为 badc 以3为根时结果为 bacd 所以字典序最小的是bacd

D、first集

Accept:0 Submit:17 Time Limit:1000MS Memory Limit:65536KB 请仔细阅读“考前必读”

Description

对于文法，给出求first集的算法，让大家求first集。输入中大写字母表示非终结符，小写字母表示终结符，#表示空也是终结符。First集求解算法如下： 为了求每个符号的first集，连续使用以下规则，直到每个符号的first集不再增大为止。

1.对于终结符，它的first集就是它自己。

2.对于非终结符，如果有产生式 X-> a...，把a加入first（X）中，如果X-># ,即X可以推出空，那么把空加入first（X）中。3.对于X->Y...这样的产生式，且X,Y都是非终结符，把first（Y）中的所有非空的元素加入到first（X）中。

对于X->Y1Y2...Yk产生式,X,Y1,Y2...Yk都是非终结符，对于某个i（i<=k），如果first（Y1），first（Y2），...first（Yi-1）都含有空，那么将first（Yi）中的所有非空元素加入到first（X）中。若所有的first（Yi）（i=1，2，...k）中都有空，那么将空加入first（X）中。

Input

多组数据，以EOF结束。

第一行一个数字n，表示有n个文法式，（0

下面n行，每行第一个是一个大写字母，表示产生式的左边，然后一个字符串，由大写字母（非终结符），小写字母（终结符）和#（空）组成。

Output

按照字典序输出每个非终结符的first（集）。每行表示一个first集。第一个字母输出表示非终结符(按字母序排列)，然后按字母顺序输出first集，如果包含空的话，最后输出#。一行中每两个字符间有一个空格。

Sample Input B A A ab A c A # Sample Output

A a c # B a c #

Hint

2011北邮计算机学院复试上机题目(回忆版)

A 句子逆转 输入一个句子，占用一行。句子由单词和单词间的空格组成。单词只有小写字母。单词之间由空格隔开。单词之间不会有多个空格。每个句子至多有1000个字母。多组数据输入。将句子单词的排列顺序倒过来输出。多组数据输入，以EOF为结束。SAMPLE: INPUT: It is a apple OUTPUT: apple a is it

B 成绩管理

实现查询成绩的功能。首先输入T表示有T组数据。每组数据首先输入n，接下来有n行输入.每行输入是插入或者查找。插入为Insert id score。id是自然数，不大于1000。每次插入的id都不同。score是自然数，不大于100。查找为Find id。找到输出该id与score。查找不到输出No result!

SAMPLE: INPUT: 2 2 Insert 0 10 Find 0 5 Insert 1 15 Find 1 Find 2 Insert 2 35 Find 2 Output: name:0 score:10 name:1 score:15 No result!name:2 score:35

C 寻找宝藏

一棵多叉树T，根结点为0，某个结点上有宝藏。从根结点沿着树枝向下寻找，如果有分支，沿各分支继续寻找是等概率的。计算找到宝藏的概率。首先输入M，N，L。M多叉树T的结点数，结点分别为0~M-1。N和L分别是树枝数和宝藏所在结点。接下来有N行输入，每行两个数，表示这两个结点之间有树枝连接。而且前一个结点比后一个更靠近根结点。输出找到结点的概率，保留六位小数。SAMPLE: INPUT: 6 5 5 0 1 0 2 1 3 2 4 2 5 OUTPUT: 0.250000 HINT: 输出可用printf(“%.6f”,a)