考研清华，更要脚踏实地，不要妄图走所谓的“捷径”。在这里，盛世清北提醒大家：想要备考清华深研院840数学-数据方向基础综合硕士，重要的是基础知识掌握是否扎实、能否将所学灵活运用，而不是投机取巧，不能轻信押题，压中或者压不中，这个结果只能自己承担。

为帮助考生少走弯路，盛世清北整理了清华深研院840数学-数据方向基础综合考研真题，供报考清华的考生参考。

科目介绍

清华840数学-数据方向基础综合科目的考试内容涵盖了数据结构、算法分析、线性表、栈和队列、串、数组和广义表、树和二叉树、图、动态存储管理、查找、排序等多个方面。具体考试内容可能包括：

数据结构：介绍数据结构的基本概念、术语以及抽象数据类型的表示与实现。

算法和算法分析：包括算法的定义、设计的要求、效率的度量和存储空间需求等方面的内容。

线性表：线性表的类型定义、顺序表示和实现、链式表示和实现（包括线性链表、循环链表和双向链表）等。

栈和队列：栈和队列的定义、表示和实现，以及栈的应用举例（如数制转换、括号匹配的检验、行编辑程序等）和队列的应用（如离散事件模拟）。

串：串类型的定义、表示和实现（包括定长顺序存储表示、堆分配存储表示和串的块链存储表示）以及串的模式匹配算法。

数组和广义表：数组的定义、顺序表示和实现，矩阵的压缩存储（特殊矩阵和稀疏矩阵），广义表的定义、存储结构和递归算法等。

树和二叉树：树的定义和基本术语，二叉树的定义、性质、存储结构和遍历方法，以及树和森林的存储结构、遍历方法和赫夫曼树及其应用等。

图：图的定义和术语，图的存储结构（数组表示法、邻接表、十字链表和邻接多重表），图的遍历（深度优先搜索和广度优先搜索），图的连通性问题（无向图的连通分量和生成树、有向图的强连通分量、最小生成树和关节点等），有向无环图及其应用（拓扑排序和关键路径），以及最短路径算法等。

动态存储管理：包括概述、可利用空间表及分配方法、边界标识法、伙伴系统、无用单元收集和存储紧缩等方面的内容。

查找：包括静态查找表和动态查找表（如二叉排序树和平衡二叉树、B树和B+树、键树等）以及哈希表的构造方法、处理冲突的方法和查找及其分析等方面的内容。

排序：包括插入排序、快速排序、选择排序（简单选择排序、树形选择排序和堆排序）、归并排序和基数排序等多种排序算法及其比较讨论。

外部排序和文件：包括外存信息的存取、外部排序的方法、多路平衡归并的实现、置换-选择排序、最佳归并树以及有关文件的基本概念、顺序文件、索引文件、ISAM文件和VSAM文件、直接存取文件（散列文件）和多关键字文件等方面的内容。

考研真题

一、选择题，16*3分

1. 复杂度的概念

3. 单链表头尾节点的特性

4. 汉诺塔次数递推

14. 简单选择排序的比较次数和移动次数

15. 稳定性判定

16. 什么文件适合磁带储存

二、填空题，2分一空，共38分

1. 评价算法的两个重要概念

3. 队列的几个复杂度

4. KMP算法复杂度

9. 伙伴系统求地址

三、简答题，39分

1. 算术表达式转化二叉树 *12

2. 哈希表除余取留法、线性再探测、成功查找长度*12

3. demonstrate()函数，字符串常见assign/concat/substring/replace，求输出 *15

四、证明题：25分

1. （1）证2n-1个节点，只有0和2度的二叉树 *5

（2）证明叶子结点的层数li，满足求和：2的li -1 次方的倒数之和为1 *5

2. （1）证明AVL树最少节点的递推公式*5

（2）证明通项公式，斐波那契数列，爱咋求咋求，查分方程，构造特征方程、数归暴力也行*5

（3）证明AVL树查找复杂度为O(logn) *5

更多清华深研院840数学-数据方向基础综合考研相关内容，请持续关注。