西山居3.20笔试，技术开发B卷讨论

三道算法AK。强制要求C＋＋

一、一个节点数据为整数的二叉搜索树，他的遍历结果可以在内存中用一个整数数组来表示。请实现一个函数，该函数的功能为：输入一个整数数组，判断该数组是不是某个二叉搜索树的后序遍历结果。如果是则输出true，否则输出false。假设输入数组中，任意元素都互不相同。例子1:输入[3,6,5,9,8,11,13,12,10]输出true 例子2:输入[3,6,5,9,11,8,13,12,10]输出false。

按照后续遍历的特点，递归检查就完事了。

二、给定一个单词列表words和一个整数k,输入用逗号隔开，返回前k个出现次数最多的单词。返回的答案应该按照出现频率由高到低排序。如果不同的单词有相同的出现频率，则按照字典顺序排序。c++完成代码，输入一个列表和一个整数k，使用逗号隔开。具体实现代码内部要求使用vector<string> &words, int k两个形参。例子1:输入[“today”,”is”,”sunday”,”today”,”is”,”raining”],2输出[“is”,”today”] 例子2:[“love”,”peace”,”peace”,”and”,”peace”,”love”,”and”,”and”,”hope”],3输出[“and”,”peace”,”love”]

词频统计题，没啥好说的。队列输出前k位完事

三、把玻璃杯摆成金字塔形状，其中第一层有1个玻璃杯，第二层有2个，依此类推到第100层，每个玻璃杯容量为250ml。从顶层第一个玻璃杯开始倒香槟，当当前层的杯子满了，任何溢出的香槟会立刻等量的流向左右两侧下一层的玻璃杯。当下层左侧玻璃杯满了，同理也会流向相对它的下一层左右两个杯子，依次类推。但是当最底层的杯子满了，香槟则会流到地上。例如当在倾倒一杯香槟250ml后，最顶层的玻璃杯满了。倾倒两杯香槟500ml后，顶层玻璃杯满了，第二层的玻璃杯将会各自装一半杯125ml。倒三杯750ml后，第二层杯子全满了，此时一共有3个满的玻璃杯。倒第四杯1000ml，则第三层中间的玻璃杯会装有一半125ml，他同层两侧的另外两个玻璃杯则只装了四分之一。现在输入三个整数，poured，query_row和query_glass，用逗号隔开，分别代表poured一共到了多少杯，query_row第几行，以及query_glass当前行第几个杯子。输出，第query_row行，第query_glass个杯子所装香槟占整个杯子全部容积的比例。其中query_row和query_glass都从0开始计数。返回的结果保留五位小数。0<=poured<=10^9,0<=query_glass<=query_row<100.

DP题。注意处理整数的精度问题

选择题不难，就是C++和几门计算机专业课

填空题还有两个C++题目