2021级研究生考试真题

清华美院交叉学科-技术编程方向

 

专业一: 680理论基础

 

题目:

论艺术和科技的融合对未来生活方式的影响(论文)

 

要求:

1、结合实例进行证明;

2、论点论据有说服力;

3、2000字以上;

 

专业二: 981专业基础「六选三、笔答」

 

一、数字黑洞

假设你有-个各位数字互不相同的四位数，把所有的数字从大到小排序后得到a,从小到大后得到b,然后用a-b替换原来这个数，并且继续操作。例如，从1234出发，依次 可以得到4321-1234=3087、8730-378=8352、 8532- 2358=6174,又回到了它自己!请写一个程序来判断一个四位数经过多少次这样的操作能出现循环，并且求出操作的次数。

 

比如输入1234执行顺序是1234->3087->8352->6174->6174,输出是4

 

输入1  2  3  4

输出4

 

 

 

三、顺时针打印矩阵

输入-个矩阵，先输入行数，再输入列数，按照从外向里以顺时针的顺序依次打印出每一-个数字。

 

输入

4  3

1  2  3  4

5  6  7  8  

9  10  11  12

 

输出

1  2  3  4  8  12  11  10  9  5  6  7

 

四、计算

1、n^logn=0 (logn^n)是否成立;

2、将中缀表达式: (0!+1)*2^(3!+4)-5./6-(7-8+9)，转换为逆波兰表达式，并写入44455的格子中;

3、模式串对应的next[]表和改进后的next[]表;

j	0	1	2	3	4	5	6	7	8	9	10	11	12
p[j]	x
Nest[j]	-1
improvednext[j]	-1

 

五、简答

1、如何基于向量结构，派生出栈结构，原理与关键点;

2、Floyd建堆算法的过程原理，为何能保证0(n)的时间复杂度;

3、归并排序:快速排序递归算法都不会递归到最底层，当子序列长度小于某个阙值m时提前停止递归用朴素的算法直接对子序列排序，这样处理处于什么考虑，阙值m的主要因素有哪些;

 

六、算法与数据结构设计

二部图:用广度优先搜索的框架设计一个算法，判断-个图是否为二部图，伪代码描述算法，说明原理，估计时间复杂度。

 

C++：

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

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

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

 

2. 回形顺时针实现矩阵

a) 输入，8 行 3 列

b) 输出：

0 0 0 0 0 0 0 0

3 4 4 4 4 4 4 1

2 2 2 2 2 2 2 1

 

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

 

算法与数据结构：

一、

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

2. 逆波兰表达式

3. Kmp next数组求解

 

二、

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

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

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

 

三、

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