2022年清华大学981信息艺术基础—信息技术基础考研试题 - 中外艺术研究生招生信息网

一、程序填空：逆序输出

只识别字母和空格，逆序输出各个单词

输入：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]