17级数据结构实验考试题（疑似）

• 看数据，做出2道及2道以下的占3/67

• 从作答成功率上看难度，由简单到难应该是：B≈A≈C>E>>D，如果机试不是自己很擅长的考试方式，可以先考虑自己熟悉哪道题，拿分概率更高，然后再考虑看看排名榜单，哪个简单去做哪个

problem A：cocoa在矿大

• 时间限制: 1 Sec
• 内存限制: 128 MB

题目描述

cocoa和chino是矿大的学生，她们非常爱矿大。

这次chino扔给了cocoa一个字符串，想问问她字符串中出现了几次"CUMT"，cocoa不太擅长数数，你能来帮帮他吗？

输入

第一行一个正整数n(4<=n<=100)，表示字符串的长度；
第二行是一个由大写字母组成的长度为n的字符串。

输出

一个整数表示CUMT出现的次数

样例输入

9
CUMTXCUMT

样例输出

2

problem B：cocoa坐火车

• 时间限制: 1 Sec
• 内存限制: 128 MB

题目描述

又到了寒假，cocoa打算坐火车回家了。火车都有两个车头，进站与出站是不同的车头在最前面，我们把最前面的车厢计为第一节车厢(车头也算一节车厢)。

好奇的cocoa数出了火车的节数k，她发现自己应该坐在第b节车厢，她现在想知道自己坐的车厢在火车进站时算作第几节，你能帮帮她吗？

输入

用空格分开的两个正整数b,k(1<=b<=k<=100)

输出

一个正整数表示cocoa坐的那节车厢在火车进站时是第几节

样例输入

1 8

样例输出

8

problem C：cocoa吃面包

• 时间限制: 1 Sec
• 内存限制: 128 MB

题目描述

cocoa回到了老家，他们家是做面包的，她久违地做了一次面包，这次她想把最好吃的留给自己的好朋友chino，自己吃第二好吃的。

每个面包用一个正整数表示好吃程度，越大表示越好吃，cocoa想知道自己吃到的面包的好吃程度是多少，你帮忙能回答她吗？

输入

第一行一个正整数n(2<=n<=100)表示cocoa做的面包的数量
第二行n个正整数表示每个面包的好吃程度，保证没有两个面包是一样好吃的

输出

一个正整数表示cocoa吃到的面包的好吃程度

样例输入

5
1 2 3 5 4

样例输出

4

problem D：: cocoa看烟花

• 时间限制: 1 Sec
• 内存限制: 128 MB

题目描述

又到了一年一度的元宵节，这一天cocoa想离开自己家所在的小镇去临近的小镇看烟花大会，但是附近有许多小镇，小镇之间又有许多条路相连，她不知道到怎样走才能使路程最短，你能帮帮她吗？

总共有n个小镇，每个小镇都有一个编号(0~n-1)，cocoa的家在0号小镇，烟花大会将在n-1号小镇举行。

输入

第一行一个正整数n(2<=n<=10)表示小镇的数量
接下来给出一个n*n的矩阵a，a[i][j]表示i号小镇与j号小镇之间的路的长度l(1<=l<=100)，99999表示两个小镇之间没有路相连。

输出

一个正整数表示cocoa所要走的最短路程
如果cocoa看不到烟花大会，请输出-1

样例输入

4
0 2 9999 10
2 0 9999 5
9999 9999 0 1
10 5 1 0

样例输出

7

problem E：cocoa学二叉树

• 时间限制: 1 Sec
• 内存限制: 128 MB

题目描述

元宵节过后，cocoa又回到了学校开始了新学期的课程，这学期有一门课程cocoa特别喜欢，叫做《数据结构》。这一天，cocoa正在学习二叉树，但是她不知道如何判断一颗二叉树是不是满二叉树，你能来帮帮她吗？

输入

第一行一个正整数n(1<=n<=100)表示结点的数量
接下来n-1行每行两个用空格分开的正整数a,k，表示a结点的父亲结点是k结点
输入保证一个父节点最多有两个子节点，根节点是0号结点

输出

输出"YES"或“NO”表示这棵树是不是满二叉树

样例输入

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

样例输出

YES