关于哈夫曼树，下面说法正确的是（ ）。

给定一组权值{3, 4, 7, 14, 15, 20}，计算其带权路径长度（WPL）为（ ）。

二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）。

一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（ ）。

完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的 1 号位置，则第 k 号结点的父结点如果存在的话，应当存放在数组的（ ）号位置。

如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（ ）。

广度优先搜索时，需要用到的数据结构是（ ）。

如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c，另有元素d已经出栈，则可能的入栈顺序是（ ）。

在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

一棵具有5层的满二叉树中结点数为（ ）。

今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S的栈顶元素为（ ）。

如果根的高度为1，具有61个结点的完全二叉树的高度为（ ）。

面向对象程序设计将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中，不正确的是（ ）

前序遍历序列与中序遍历序列相同的二叉树为（ ）。

下面程序是一个二叉排序树的插入操作，横线处应该填入的是（ ）。

class BinarySortTree:
def __init__(self):
self.root = None
def insert(self, key, value):
node = TreeNode(key, value)
if self.root is None:
self.root = node
return
current = self.root
while True:
if key < current.key:
___________________________
current = current.left
else:
if current.right is None:
current.right = node
return
current = current.right
if current.left is None:
current.right = node
return
if current.right is None:
current.right = node
return
if current.right is None:
current.left = node
return
if current.left is None:
current.left = node
return

在哈夫曼树中，从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。（ ）

满二叉树每一层的结点个数都达到了最大值。（ ）

如果一棵二叉树是满二叉树，但是它不一定是完全二叉树。（ ）

栈中元素的插入和删除操作都在栈的顶端进行，所以方便用双向链表比单向链表更合适表实现。（ ）

格雷码是一种变权码，每一位码没有固定的大小。（ ）

格雷码的基本特点就是任意两个相邻的代码只有一位二进制数不同。（ ）

栈是一种只能在一端进行插入和删除操作的特殊线性表。（ ）

最后进入队列的元素才能最先从队列中删除。（ ）

当队列为满时，做出队运算产生的溢出现象，常用作程序控制转移的条件。（ ）

在循环队列的上下文中，rear指针通常用于指示队列尾部元素的下一个位置，而不是直接指示队列尾部的元素。因此，rear的计算通常与入队操作相关。（ ）

树上游走

时间限制：1.0 s 内存限制：512.0 MB
题面描述：小杨有一棵包含无穷节点的二叉树（即每个节点都有左儿子节点和右儿子节点；除根节点外，每个节点都有父节点），其中根节点的编号为1，对于节点i，其左儿子的编号为2i，右儿子的编号为2i+1。
小杨会从节点s开始在二叉树上移动，每次移动为以下三种移动方式的任意一种：
第1种移动方式：如果当前节点存在父亲节点，向上移动到当前节点的父亲节点，否则不移动；
第2种移动方式：移动到当前节点的左儿子；
第3种移动方式：移动到当前节点的右儿子。
小杨想知道移动n次后自己所处的节点编号。数据保证最后的所处的节点编号不超过10^12。

第一行包含一个正整数n和s，代表移动次数和初始节点编号。第二行包含一个长度为n且仅包含大写字母U、L、R的字符串，代表每次移动的方式，其中U代表第1种移动方式，L代表第2种移动方式，R代表第3种移动方式。

输出一个正整数，代表最后所处的节点编号。

样例输入：
3 2
URR
样例输出：
7
样例解释：小杨的移动路线为2-1-3-7。

运送物资

时间限制：2.0 s 内存限制：512.0 MB
题面描述：小杨管理着m辆货车，每辆货车每天需要向A市和B市运送若干次物资。小杨同时拥有n个运输站点，这些站点位于A市和B市之间。
每次运送物资时，货车从初始运输站点出发，前往A市或B市，之后返回初始运输站点。A市、B市和运输站点的位置可以视作数轴上的三个点，其中A市的坐标为0，B市的坐标为x，运输站点的坐标为p且有0对于第i个运输站点，其位置为p_i且至多作为c_i辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运输站点的情况下，所有货车每天的最短总行驶路程是多少。

第一行包含三个正整数n, m, x，代表运输站点数量，货车数量和两市距离。之后n行，每行包含两个正整数p_i, c_i，代表第i个运输站点的位置和最多容纳车辆数。之后m行，每行包含两个正整数a_i, b_i，代表第i辆货车每天需要向A市运送a_i次物资，向B市运送b_i次物资。

输出一个正整数，代表所有货车每天的最短总行驶路程。

样例输入：
3 4 10
1 1
2 1
8 3
5 3
7 2
9 0
1 10000
样例输出：
40186