清华大学美术学院2021考研

交叉学科编程方向

981专业基础—信息技术基础

考题解析

 

伴随着专业一的统考改革，交叉编程方向的专业二进行了一些变动。C++和数据结构两大核心考点没变，在命题的侧重点上更加“务实”，更加“直接”。题目的难度分布上也与往年类似，最难的题出自数据结构最后一题。

C++在题型上，取消了代码填空和类的实现，取代为三道代码实现。考察的侧重点在考生解决问题的逻辑能力，审题的细心和考虑问题的全面性，难度偏简单。

 

数据结构的考核上，取消了名词解释和判断题，取代改三道简答题，知识点的考察更加的细致和综合，强调对数据结构和算法的理解。难度中等。

 

1C++：

●●● 考题 ●●●

1. 任何一个四位正整数，在它的四位数字排列中，最大值和最小值相减得到一个数值，这个数值的最大值和最小值相减，也可以得到一个数字。反复这个过程，最终总会得到4176这个数字

a) 输入：任意一个四位正整数（保证四位数值不完全一致）

b) 输出：反复运算几次才能得到这个数字，输出次数

2. 回形顺时针实现矩阵

a) 输入，8 行 3 列

b) 输出：

00000000

34444441

22222221

3. 回形顺时针输出矩阵

a) 输入 4 4（四行四列）

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

输出

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

C++这一部分的改动，对同学们的复习实则影响不大。第1题的命题思路很像2018年真题“相亲数”。披着“数论”的外衣，提出一个概念或规律，仔细读下来底层逻辑很简单。

2，3题目命题思路类似2010的区域填充，和“矩阵”本身关系不大，考察的是处理输入和输出的格式。相信大多数同学们也都选择了C++三道题为主要的拿分题。

和以往的命题风格不同的是，本次特别增加了输入格式和输出格式，其中也蕴含了一些细节，

如输入条件的判断：第1题：保证四位数值不完全一致；第2题：输入内容包含了数值和字符串等。

 

复习建议：

C++考查弱化了C++语言技术细节，强化了解题逻辑。对同学们来说C++的备考也变得更加轻松和有针对性，对教材的依赖减轻，对技术细节的比如指针和模版类等的记忆负担也减轻了。同学们应在日后的复习中，多刷题，多多积累题目逻辑，培养题目的敏感性；

另外一定要提前练习手写代码，去规避一些容易出现的笔误陷阱。 

  

2算法与数据结构：

题型以简答为主，难度中等。综合分析看来，数据结构以往题型：名词解释过于简单，判断题的随机性和不确定性较大，单从T/F去判断学生对数据结构的完整理解其实过于武断，相比而言，简单题是考查知识点的最客观的途径。

第一题侧重于对算法基本思想和概念的理解，难度简单。

●●● 题目 ●●●

1. nlogn=O(lognn)是否正确，为什么？

2. 逆波兰表达式

3. Kmp next数组求解

第一小题，考查了算法复杂度分析，对大O记号的理解，教材位于第一章。

第二小题逆波兰表达式已经出现在三年的真题中（2017，2018，2020），属于基础概念考察。教材位于栈章节。

第三小题考查了串匹配算法中的经典实现KMP算法，next数组是其算法思想的核心，位于教材较后的位置，串章节。

 

第二大题整体侧重于对数据结构的理解和不同数据结构之间的联系。涉及向量，栈，堆和排序算法。

●●● 题目 ●●●

1. 向量如何构造栈，有什么注意点

2. 二叉堆的构造，如何保证o(n)

3. 归并排序和快速排序为什么在递归到一定深度时要换成朴素的排序算法，影响因素有哪些？

第一小题：栈的特点

第二小题：堆，Floyd建堆法

第三小题：排序算法的优化，归并和快排本质都是基于分治思想实现的，从分治复杂度角度分析即可。

 

第三题侧重算法应用

●●● 题目 ●●●

用BFS判断是否为二部图，写出算法和时间复杂度

算法设计考查了图算法。因为其中涉及的二部图属于拓展的数据结构，需要同学们在教材以外自行拓展，相应增加了难度。在了解二部图定义后，题目就转化为了BFS求解联通域的基本问题，在教材射程以内。

和往年的数据结构优化思路有所不同，今年侧重于算法应用以及与数据结构的结合。 

 

复习建议：

数据结构的知识点贯穿全书，算法复杂度分析，向量，栈，堆向来是往年的高频考点。算法思想和基本概念的考查都仍以教材为重，对于教材中涉及的和数据结构密切相关的算法，应着重复习。在数据结构的实现上由于教材的描述过于细致和繁琐，不适合命题，因此同学们应掌握提炼思想的能力，并适当的进行一些拓展。

 

3总结

总体来说专业二的难度不大，同学们得高分还是很容易的，此时的比拼就在于选题策略和细心上。尽管题型有所改变，但就复习路径来说，变化不大，同学们按照基本的知识体系框架，按部就班地进行即可。

最后祝愿大家取得理想的成绩，马到功成～