[hide=11111111111111111]
一、程序填空：逆序输出
只识别字母和空格，逆序输出各个单词
输入：I love TsingHua University
输出：University Tsinghua love i
输入：I lo*e Ts/ngHua Un￥vers&ty
输出：ty vers Un ngHua Ts e lo I
考察基础的字符串操作,字母和字符的辨别,以及逆序的实现.难度属于简单.
二、程序填空：可以填写一个或多个语句
停车场问题，一个类Park，一个基类Automobile，三个派生类Truck、Car、（剩下这个忘了），离开的时候需要交停车费，分别是3元，1元，2元
1）Park类析构函数
2）Park类有车进入的函数
3）Park类有车离开的函数
4）Truck类构造函数
5）Truck类有车离开的函数
用代码填空的形式考察了类实现相关的知识点.在类的考察上,选择了偏“实际应用”,而不是具体实现某一“数据结构”. 考核点除了构造函数,析构函数,成员函数的编写,还包括两个派生类Park和Truck的逻辑区别与联系.难度属于简单.
三、程序填空: 文件流的问题
1）打开文件
2）判断打开成功了吗
3）在文件中存入数字
4）打开文件
5）读取文件中的数字
考察文件流的基础操作.包括文件打开,关闭,读写.文件流细节相关的考察上一次在真题中出现还是2014年,这一点可能会让备考解题逻辑考生有一丝措手不及.但是考察的点是文件流的基础操作,也是c++教材中涵盖的内容,总体来说难度偏易.
数据结构与算法:
数据结构的题型从去年的计算,简答,优化,改为了前年的判断,简答,优化. 考察内容上仍是以基础的数据结构和算法分析的理解为主.本质不变,我们可以将数据结构的考核方式统一理解为简答题的变体.
四、判断对错并简要解释
1）2.021^n=Ω(n^2021)
2) 向量扩容增量操作分摊时间O(1)
3）Bitmap结构
4）B-树的insert(key)执行完成之后，关键码key总是位于叶节点中
与此前的判断相比,今年的判断题新增了解释环节.考核的内容包括算法分析基础知识: 大O记号理解,分摊分析,向量扩容策略… 其中,Bitmap和B树的考查是这里的拔高题.
五、简答题
1）向量和列表数据访问方式的差异，以及两种数据机构的优势、劣势
2）左式堆为什么能够保持O(logn)内执行insert()、delMax()、merge()
3）在数据集理想随机时，为什么平凡算法和优化算法的效果实质上可能差别不大。举两个例子，并解释。
简单题是数据结构的经典考法,今年涉及的知识点包括向量和列表,左式堆,和数据集特征对优化算法的理解.其中第三题属于拔高题.
六、中序遍历
1）伪代码
要求：可以使用栈或者队列，但不能使用其他数据结构。节点总是为n，二叉树高度为h，时间复杂度为O(n)，空间复杂度为O(h)
2）解释算法
3）解释正确性
4）解释时间复杂度、空间复杂度符合要求[/hide]
| 
发表于 2021-12-28 23:28:08
收藏