7-29 修理牧场 (25 分)

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要$N$块木头，每块木头长度为整数$L_i$个长度单位，于是他购买了一条很长的、能锯成$N$块的木头，即该木头的长度是$L_i$的总和。

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

请编写程序帮助农夫计算将木头锯成$N$块的最少花费。

输入格式:

输入首先给出正整数$N$（≤104），表示要将木头锯成$N$块。第二行给出$N$个正整数（≤50），表示每段木块的长度。

输出格式:

输出一个整数，即将木头锯成$N$块的最少花费。

输入样例:

1
2

8
4 5 1 2 1 3 1 1

输出样例:

1

49

7-28 搜索树判断 (25 分)

对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。

输入格式:

输入的第一行包含一个正整数$N$（≤1000），第二行包含$N$个整数，为给出的整数键值序列，数字间以空格分隔。

输出格式:

输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。

输入样例1:

1
2

7
8 6 5 7 10 8 11

输出样例1:

1
2

YES
5 7 6 8 11 10 8

输入样例2:

1
2

7
8 6 8 5 10 9 11

输出样例2:

1

NO

7-27 家谱处理 (30 分)

人类学研究对于家族很感兴趣，于是研究人员搜集了一些家族的家谱进行研究。实验中，使用计算机处理家谱。为了实现这个目的，研究人员将家谱转换为文本文件。下面为家谱文本文件的实例：

1
2
3
4
5
6

John
  Robert
    Frank
    Andrew
  Nancy
    David

家谱文本文件中，每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代，而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例，John这个家族最早的祖先，他有两个子女Robert和Nancy，Robert有两个子女Frank和Andrew，Nancy只有一个子女David。

在实验中，研究人员还收集了家庭文件，并提取了家谱中有关两个人关系的陈述语句。下面为家谱中关系的陈述语句实例：

1
2
3

John is the parent of Robert
Robert is a sibling of Nancy
David is a descendant of Robert

研究人员需要判断每个陈述语句是真还是假，请编写程序帮助研究人员判断。

输入格式:

输入首先给出2个正整数N（2≤N≤100）和M（≤100），其中N为家谱中名字的数量，M为家谱中陈述语句的数量，输入的每行不超过70个字符。

名字的字符串由不超过10个英文字母组成。在家谱中的第一行给出的名字前没有缩进空格。家谱中的其他名字至少缩进2个空格，即他们是家谱中最早祖先（第一行给出的名字）的后代，且如果家谱中一个名字前缩进k个空格，则下一行中名字至多缩进k+2个空格。

在一个家谱中同样的名字不会出现两次，且家谱中没有出现的名字不会出现在陈述语句中。每句陈述语句格式如下，其中X和Y为家谱中的不同名字：

1
2
3
4
5

X is a child of Y
X is the parent of Y
X is a sibling of Y
X is a descendant of Y
X is an ancestor of Y

输出格式:

对于测试用例中的每句陈述语句，在一行中输出True，如果陈述为真，或False，如果陈述为假。

输入样例:

1
2
3
4
5
6
7
8
9
10
11
12

6 5
John
  Robert
    Frank
    Andrew
  Nancy
    David
Robert is a child of John
Robert is an ancestor of Andrew
Robert is a sibling of Nancy
Nancy is the parent of Frank
John is a descendant of Andrew

输出样例:

1
2
3
4
5

True
True
True
False
False

7-26 Windows消息队列 (25 分)

消息队列是Windows系统的基础。对于每个进程，系统维护一个消息队列。如果在进程中有特定事件发生，如点击鼠标、文字改变等，系统将把这个消息加到队列当中。同时，如果队列不是空的，这一进程循环地从队列中按照优先级获取消息。请注意优先级值低意味着优先级高。请编辑程序模拟消息队列，将消息加到队列中以及从队列中获取消息。

输入格式:

输入首先给出正整数$N$（≤105），随后$N$行，每行给出一个指令——GET或PUT，分别表示从队列中取出消息或将消息添加到队列中。如果指令是PUT，后面就有一个消息名称、以及一个正整数表示消息的优先级，此数越小表示优先级越高。消息名称是长度不超过10个字符且不含空格的字符串；题目保证队列中消息的优先级无重复，且输入至少有一个GET。

输出格式:

对于每个GET指令，在一行中输出消息队列中优先级最高的消息的名称和参数。如果消息队列中没有消息，输出EMPTY QUEUE!。对于PUT指令则没有输出。

输入样例:

1
2
3
4
5
6
7
8
9
10

9
PUT msg1 5
PUT msg2 4
GET
PUT msg3 2
PUT msg4 4
GET
GET
GET
GET

输出样例:

1
2
3
4
5

msg2
msg3
msg4
msg1
EMPTY QUEUE!

7-25 朋友圈 (25 分)

某学校有$N$个学生，形成$M$个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。

输入格式:

输入的第一行包含两个正整数$N$（≤30000）和$M$（≤1000），分别代表学校的学生总数和俱乐部的个数。后面的$M$行每行按以下格式给出1个俱乐部的信息，其中学生从1~$N$编号：

1

第i个俱乐部的人数Mi（空格）学生1（空格）学生2 … 学生Mi

输出格式:

输出给出一个整数，表示在最大朋友圈中有多少人。

输入样例:

1
2
3
4
5

7 4
3 1 2 3
2 1 4
3 5 6 7
1 6

输出样例:

1

4

7-24 树种统计 (25 分)

随着卫星成像技术的应用，自然资源研究机构可以识别每一棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。

输入格式:

输入首先给出正整数N（≤105），随后N行，每行给出卫星观测到的一棵树的种类名称。种类名称由不超过30个英文字母和空格组成（大小写不区分）。

输出格式:

按字典序递增输出各种树的种类名称及其所占总数的百分比，其间以空格分隔，保留小数点后4位。

输入样例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

29
Red Alder
Ash
Aspen
Basswood
Ash
Beech
Yellow Birch
Ash
Cherry
Cottonwood
Ash
Cypress
Red Elm
Gum
Hackberry
White Oak
Hickory
Pecan
Hard Maple
White Oak
Soft Maple
Red Oak
Red Oak
White Oak
Poplan
Sassafras
Sycamore
Black Walnut
Willow

输出样例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Ash 13.7931%
Aspen 3.4483%
Basswood 3.4483%
Beech 3.4483%
Black Walnut 3.4483%
Cherry 3.4483%
Cottonwood 3.4483%
Cypress 3.4483%
Gum 3.4483%
Hackberry 3.4483%
Hard Maple 3.4483%
Hickory 3.4483%
Pecan 3.4483%
Poplan 3.4483%
Red Alder 3.4483%
Red Elm 3.4483%
Red Oak 6.8966%
Sassafras 3.4483%
Soft Maple 3.4483%
Sycamore 3.4483%
White Oak 10.3448%
Willow 3.4483%
Yellow Birch 3.4483%

7-23 还原二叉树 (25 分)

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入格式:

输入首先给出正整数$N$（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为$N$的不包含重复英文字母（区别大小写）的字符串。

输出格式:

输出为一个整数，即该二叉树的高度。

输入样例:

1
2
3

9
ABDFGHIEC
FDHGIBEAC

输出样例:

1

5

7-22 堆栈模拟队列 (25 分)

设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。

所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数:

• int IsFull(Stack S)：判断堆栈S是否已满，返回1或0；
• int IsEmpty (Stack S )：判断堆栈S是否为空，返回1或0；
• void Push(Stack S, ElementType item )：将元素item压入堆栈S；
• ElementType Pop(Stack S )：删除并返回S的栈顶元素。

实现队列的操作，即入队void AddQ(ElementType item)和出队ElementType DeleteQ()。

输入格式:

输入首先给出两个正整数N1和N2，表示堆栈S1和S2的最大容量。随后给出一系列的队列操作：A item表示将item入列（这里假设item为整型数字）；D表示出队操作；T表示输入结束。

输出格式:

对输入中的每个D操作，输出相应出队的数字，或者错误信息ERROR:Empty。如果入队操作无法执行，也需要输出ERROR:Full。每个输出占1行。

输入样例:

1
2

3 2
A 1 A 2 A 3 A 4 A 5 D A 6 D A 7 D A 8 D D D D T

输出样例:

1
2
3
4
5
6
7
8
9

ERROR:Full
1
ERROR:Full
2
3
4
7
8
ERROR:Empty

7-21 求前缀表达式的值 (25 分)

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3*(7-4)+8/4的前缀表达式是：+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。

输入格式:

输入在一行内给出不超过30个字符的前缀表达式，只包含+、-、*、/以及运算数，不同对象（运算数、运算符号）之间以空格分隔。

输出格式:

输出前缀表达式的运算结果，保留小数点后1位，或错误信息ERROR。

输入样例:

1

+ + 2 * 3 - 7 4 / 8 4

输出样例:

1

13.0

7-20 表达式转换 (25 分)

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:

输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。

输出格式:

在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

输入样例:

1

2+3*(7-4)+8/4

输出样例:

1

2 3 7 4 - * + 8 4 / +