01
2023真题还原
02
真题解析
_1. 代码填空（35分）_
程序实现中缀转后缀
重载<运算符用来比较运算符优先级
输入：1-2*（3+4）
输出：1234+*-
答案
点击下方空白处获得答案
以下步骤将中缀表达式转换成后缀表达式。
代码思路如下：
- 创建一个空栈opstack，用于保持运算符。为输出创建一个空字符串。
- 从左到右扫描字符串。
- 如果字符是操作数，则将其附加到输出列表的末尾。
- 如果字符是左括号，请将其压栈入opstack。
- 如果字符是右括号，则弹出opstack直到遇到相应的左括号。并将每个弹出的运算符附加到输出字符串的末尾。
- 如果字符是操作符， \* ， / ， + 或 - ，请将其入栈到 opstack。但是，首先弹出opstack上具有更高或相同优先级的任何运算符 ，并将这些运算符加到输出字符串。
- 扫描字符串完字符串后，检查 opstack。任何仍在堆栈上的运算符都可以删除并附加到输出字符串的末尾。
_2.编写程序设计银行储蓄账户（40分）_
1）先实现一个基类即账户类 实现存款 取款 账户信息等功能
2）根据账户类派生出 信用账户 储蓄账户。信用账户不用详细实现，储蓄账户需要详细实现，实现以月或年为单位的储蓄过程，计算利率
3）自行设计更多功能并实现
4）画出uml类图 表示类与类之间的关系 测试此程序
【参考书上7.7.3 个人银行账户管理程序】
答案
点击下方空白处获得答案
一家银行有很多分行。在每个区域中，一个分支被指定为区域总部，负责监督该区域中的其他分支。每个分行可以有多个账户和贷款。帐户可能是储蓄账户或信用账户。客户可以打开储蓄账户和信用账户。但是，客户不得拥有多个储蓄账户或信用账户。客户还可以从银行采购贷款。
系统中的类：
银行，分行，账户，储蓄账户，经常账户，贷款和客户。
关系：
银行“拥有”分支数：组合，一对多
一个有角色区域总部的分公司监督其他分支机构：一元关联，一对多
一个分支机构拥有一个“多个帐户：聚合，一对多”
从账户基类中，继承了两个类，即储蓄账户和信用账户。
客户可以有一个信用账户：关联，一对一
客户可以有一个储蓄账户：关联，一对一
一个分支机构拥有“多少贷款：聚合”，一对多
客户可以多次贷款：关联，一对多
_3.判断对错 给出解释或证明 （6分一题， 共30分）_
(1) 在渐进复杂度中，对数复杂度的常数底会影响复杂度。
答案
点击下方空白处获得答案
False，算法时间复杂度为log（n）时，不同底数对应的时间复杂度的倍数关系为常数，不会随着底数的不同而不同，因此可以将不同底数的对数函数所代表的时间复杂度，当作是同一类复杂度处理，即抽象成一类问题。
(2) 所有叶子结点深度一致的二叉树为满树。
答案
点击下方空白处获得答案
False，所有叶子结点深度一致代表所有叶子结点深度在同一层上。但是不能代表非叶结点的度一定为2，也可能存在度为1的非叶结点，此时不符合满树的特征。
比如 A ,此时只有一个叶节点B，但是该树不是满树。
/
B
(3) 深度优先搜索能用于判断有向图的回路。
答案
点击下方空白处获得答案
True，深度优先搜索（DFS：Depth-First Search）和拓扑排序可以用于检测图中是否存在环。
(4) 某个队列允许一端入队两端出队，入队过程中可以出队，则当入队顺序为ABCDE时不可能得到EBCAD的出队顺序。
答案
点击下方空白处获得答案
True，注意到出队顺序的第一个字母为E，而E是入队顺序的最后一个字母，也就是说在E出队前没有任何元素出队。即入队过程中没有元素出队。全部元素入队后开始出队，注意到出队顺序第二个元素是B，而B在入队顺序中位于A和C的中间，因此B元素不可能同时先于AC出队。
(5) 中序遍历二叉搜索树得到的序列是单调非降的。
答案
点击下方空白处获得答案
True， 二叉搜索树一个很重要的特性就是：树中任何结点的左子树中所有结点的值均比该结点小，右子树中所有结点的值均比该结点大。对二叉搜索树进行中序遍历即得到一个单调非降的序列。同理，检查一个树是否是二叉搜索树可以使用中序遍历。
4.查找算法 （20分)
(1) 计算序列{2,3,4,6,7,8,9}二分查找的平均查找长度。
答案
点击下方空白处获得答案
首先根据二分查找的算法，将有序数组转换成二叉树搜索树的形式，然后每一层的数据的个数乘以所在层数后累加，最后除以数据数即可。
对于查找失败的平均查找长度来说，需要为所有的结点补充左右子结点。然后计算各层子结点数与层数乘积后的累加和，最后除以补充的子结点数即可。
(2) 改用散列表法，散列表 A[0,….10]，哈希函数为 H(key)=(key^2+2) mod 11，采用链表法处理冲突，当查找顺序为{4,7,3,6,8,9,2}时，画出哈希表并计算平均查找长度。
答案
点击下方空白处获得答案
_5.二叉树算法 25分_
（1）已知前序序列和中序序列，画出二叉树，写出后序序列。
答案
点击下方空白处获得答案
做题思路：
最好的办法是，根据已经知道的前序和中序序列，画出二叉树即可根据后序遍历的口诀：左右根，求出后序遍历
那么问题来了，怎么画出二叉树的图呢？？
其实简单，因为左右子树的中间被访问叫做中序，其顺序为左根右
我们将中序序列作为切入点，化为左右子节点，具体怎么做呢？
我们知道前序遍历时，都是先遍历根子节点，而中序遍历时先遍历左子节点的，所以左子节点一定是在根节点的左边，右子节点在根节点的右边，如下图
第一步： 根据前序遍历的根节点1(即根节点A)划分中序遍历的左右子节点
第二步： 根据前序遍历的根节点2(即根节点B)划分中序遍历的左右子节点
第三步： 根据前序遍历的根节点3(即根节点C)划分中序遍历的左右子节点,此时中序序列的C无左右子节点，B是它的父节点，如上图所示
第四步： 根据前序遍历的根节点4(即根节点D)划分中序遍历的左右子节点, 操作同上，如下图所示
第五步： 根据前序遍历的根节点5(即根节点E)划分中序遍历的左右子节点, 操作同上，如下图所示
第六步： 根据前序遍历的根节点6(即根节点F)划分中序遍历的左右子节点, 操作同上，如上图所示
第七步： 根据前序遍历的根节点7(即根节点G)划分中序遍历的左右子节点, 操作同上，如下图所示
…
重复以上步奏，得到最终的二叉树图如下
然后根据后序遍历：左右根
遍历得到：CBFEIJHGDA
（2）二叉树用二叉链表实现 查找前序遍历的第一个节点 设计算法 不用栈和递归实现 写出伪代码。
答案
点击下方空白处获得答案
前序遍历的第一个节点即根节点直接返回即可：
BiTreeNode *getFirstNodeUsingPreOrderTraverse(BiTree T)
{
if(NULL == T)
return NULL;
return T;
}
中序遍历的第一个节点即最左边的结点，因此一直向左孩子找，直到不能向左为止。此时的最左节点即中序遍历的第一个节点
BiTreeNode *getFirstNodeUsingInOrderTraverse(BiTree T)
{
if(NULL == T)
return NULL;
while(NULL != T->leftChild)
T = T->leftChild; //向左一路狂奔，直到不能向左为止
return T;
}