下载文档原格式
清华考研辅导班-2020清华大学962数学-数据方向基础综合考研经验真题参考书目清华大学962数学-数据方向基础综合考试科目，2020年初试时间安排为12月22日下午14:00-17:00业务课二进行笔试，清华大学自主命题，考试时间3小时。
一、适用院系及专业清华大学伯克利深圳学院0812J3数据科学与信息技术清华大学伯克利深圳学院0830J2环境科学与新能源技术二、考研参考书目清华大学962数学-数据方向基础综合有官方指定的考研参考书目，盛世清北整理如下：《数据结构》(C语言版) 清华大学出版社严蔚敏、吴伟民盛世清北建议：（1）参考书的阅读方法目录法：先通读各本参考书的目录，对于知识体系有着初步了解，了解书的内在逻辑结构，然后再去深入研读书的内容。
体系法：为自己所学的知识建立起框架，否则知识内容浩繁，容易遗忘，最好能够闭上眼睛的时候，眼前出现完整的知识体系。
问题法：将自己所学的知识总结成问题写出来，每章的主标题和副标题都是很好的出题素材。
尽可能把所有的知识要点都能够整理成问题。
（2）学习笔记的整理方法A:通过目录法、体系法的学习形成框架后，在仔细看书的同时应开始做笔记，笔记在刚开始的时候可能会影响看书的速度，但是随着时间的发展，会发现笔记对于整理思路和理解课本的内容都很有好处。
B:做笔记的方法不是简单地把书上的内容抄到笔记本上，而是把书上的关键点、核心部分记到笔记上，关上书本，要做到仅看笔记就能将书上的内容复述下来，最后能够通过对笔记的记忆就能够再现书本。
三、重难点知识梳理2020年清华大学深圳国际研究生院962 《数学-数据方向基础综合》考研考试大纲：考试内容：1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间需求2 线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加3栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.2栈的应用举例3.2.1数制转换3.2.2括号匹配的检验3.2.3行编辑程序3.2.4迷宫求解3.2.5表达式求值3.3栈与递归的实现3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列——队列的链式表示和实现3.4.3循环队列——队列的顺序表示和实现3.5离散事件模拟4 串4.1串类型的定义4.2串的表示和实现4.2.1定长顺序存储表示4.2.2堆分配存储表示4.2.3串的块链存储表示4.3串的模式匹配算法4.3.1求子串位置的定位函数Index（S，T，pos）4.3.2模式匹配的一种改进算法4.4串操作应用举例4.4.1文本编辑4.4.2建立词索引表5 数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义5.5广义表的存储结构5.6m元多项式的表示5.7广义表的递归算法5.7.1求广义表的深度5.7.2复制广义表5.7.3建立广义表的存储结构6 树和二叉树6.1树的定义和基本术语6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树和线索二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换6.4.3树和森林的遍历6.5树与等价问题6.6赫夫曼树及其应用6.6.1最优二叉树（赫夫曼树）6.6.2赫夫曼编码6.7回溯法与树的遍历6.8树的计数7 图7.1图的定义和术语7.2图的存储结构7.2.1数组表示法7.2.2邻接表7.2.3十字链表7.2.4邻接多重表7.3图的遍历7.3.1深度优先搜索7.3.2广度优先搜索7.4图的连通性问题7.4.1无向图的连通分量和生成树7.4.2有向图的强连通分量7.4.3最小生成树7.4.4关节点和重连通分量7.5有向无环图及其应用7.5.1拓扑排序7.5.2关键路径7.6最短路径7.6.1从某个源点到其余各顶点的最短路径7.6.2每一对顶点之间的最短路径8 动态存储管理8.1概述8.2可利用空间表及分配方法8.3边界标识法8.3.1可利用空间表的结构8.3.2分配算法8.3.3回收算法8.4伙伴系统8.4.1可利用空间表的结构8.4.2分配算法8.4.3回收算法8.5无用单元收集8.6存储紧缩9 查找9.1静态查找表9.1.1顺序表的查找9.1.2有序表的查找9.1.3静态树表的查找9.1.4索引顺序表的查找9.2动态查找表9.2.1二叉排序树和平衡二叉树9.2.2B树和B+树9.2.3键树9.3哈希表9.3.1什么是哈希表9.3.2哈希函数的构造方法9.3.3处理冲突的方法9.3.4哈希表的查找及其分析10 内部排序10.1概述10.2插入排序10.2.1直接插入排序10.2.2其他插入排序10.2.3希尔排序10.3快速排序10.4选择排序10.4.1简单选择排序10.4.2树形选择排序10.4.3堆排序10.5归并排序10.6基数排序10.6.1多关键字的排序10.6.2链式基数排序10.7各种内部排序方法的比较讨论11 外部排序11.1外存信息的存取11.2外部排序的方法11.3多路平衡归并的实现11.4置换一选择排序11.5最佳归并树12 文件12.1有关文件的基本概念12.2顺序文件12.3索引文件12.4ISAM文件和VSAM文件12.4.1ISAM文件12.4.2VSAM文件12.5直接存取文件（散列文件）12.6多关键字文件12.6.1多重表文件12.6.2倒排文件四、考研真题2009年，教育部出台了严格管理院校自主命题专业考试科目相关资料、限制专业课辅导的规定，很多学校从那时起不再公布和出售真题，并不再提供专业课参考书目。
数据结构--栈和队列基础知识⼀概述栈和队列，严格意义上来说，也属于线性表，因为它们也都⽤于存储逻辑关系为 "⼀对⼀" 的数据，但由于它们⽐较特殊，因此将其单独作为⼀篇⽂章，做重点讲解。
既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列，这些内容都会在本章做详细讲解。
使⽤栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使⽤队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队列。
⼆栈2.1 栈的基本概念同顺序表和链表⼀样，栈也是⽤来存储逻辑关系为 "⼀对⼀" 数据的线性存储结构，如下图所⽰。
从上图我们看到，栈存储结构与之前所了解的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：1. 栈只能从表的⼀端存取数据，另⼀端是封闭的；2. 在栈中，⽆论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。
拿图 1 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。
因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。
因此，我们可以给栈下⼀个定义，即栈是⼀种只能从表的⼀端存取数据且遵循 "先进后出" 原则的线性存储结构。
通常，栈的开⼝端被称为栈顶；相应地，封⼝端被称为栈底。
因此，栈顶元素指的就是距离栈顶最近的元素，拿下图中的栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，下中的栈底元素为元素 1。
2.2 进栈和出栈基于栈结构的特点，在实际应⽤中，通常只会对栈执⾏以下两种操作：向栈中添加元素，此过程被称为"进栈"（⼊栈或压栈）；从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；2.3 栈的具体实现栈是⼀种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种⽅式：1. 顺序栈：采⽤顺序存储结构可以模拟栈存储数据的特点，从⽽实现栈存储结构。
一、课程设计的原始资料及依据在现代社会，火车以其安全，舒适以及其服务的周到使愈来愈多的人选择了火车为长距离出行的交通工具，这就使火车公司以及车站的工作量愈来愈大，若仍然使用文件或者人工来管理公司、车站、火车、列班、路线、客户以及售票的信息，那无疑在效率上会大打折扣。
21世纪的今天，信息社会占着主流地位，计算机在各行各业中的运用已经得到普及，自动化、信息化的管理越来越广泛应用于各个领域。
利用计算机来储存和管理公司、车站、火车、列班、车线、客户以及售票的信息成为了首选，在这种情况下，火车订票系统就显得非常重要了。
两个客户名单可分别由线性表和队列实现。
为查找方便，已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。
由于预约人数无法预计，队列也应以链表作存储结构。
整个系统需汇总各条路线的情况登录在一张线性表上，由于路线基本不变，可采用顺序存储结构，并按车次有序或按终点站名有序。
每条路线是这张表上的一个记录，包含上述8个域，其中乘员名单域为指向乘员名单链表的头指针，等候替补的客户名单域为分别指向队头和队尾的指针。
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
用队列来进行客户信息的存储。
编辑用户使用菜单，内容包括：输入列班信息，保存列班信息，读取列班信息，查找列班信息，删除列班信息，订票信息，退票信息以及修改信息。
二、课程设计主要内容及要求1. 列车基本信息管理：输入所有列班信息。
每条路线所涉及的信息有：终点站名、车次号、车厢号、开车周日（星期几）、乘员定额、余票量、已订票的客户名单（包括姓名、订票量、座位等级1，2或3）以及等候替补的客户名单（包括姓名、所需的票量）。
2．列车基本信息查询：按车次号查找，按抵达站查找，按路线查找三种查找方式进行查找。
3. 订票管理：客户对想要购买的票进行订票。
3. 退票管理：将不想要的票进行退票。
三、对课程设计说明书撰写内容、格式、字数的要求1．课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。
数据结构之队列队列的概念实现方式和应用场景队列是一种常见的数据结构，它按照先进先出（First-In-First-Out，FIFO）的原则，对数据进行存储和访问。
在本文中，我们将讨论队列的概念、实现方式以及常见的应用场景。
一、队列的概念队列是一种线性数据结构，它由一系列元素组成，其中每个元素都包含自身的数据以及指向下一个元素的指针。
队列有两个基本操作：入队和出队。
入队操作将元素插入到队列的末尾，而出队操作则从队列的头部移除元素。
队列的特点是先进先出，在队列中，新元素总是被添加到队列的末尾，而最早添加的元素总是在队列的头部。
这一特点使队列非常适合于模拟实际生活中的排队场景。
二、队列的实现方式1. 顺序队列：顺序队列是使用数组来实现的队列，它具有固定的大小。
数组的索引表示队列中元素的位置，使用两个指针front和rear分别指向队列的头部和尾部。
入队操作：将元素添加到rear指针所指向的位置，并将rear指针后移一位。
出队操作：将front指针所指向的元素移除，并将front指针后移一位。
顺序队列的主要优势是访问元素的速度较快，但其缺点是在入队和出队操作频繁时，会造成大量元素的移动。
2. 链式队列：链式队列使用链表来实现，这样可以解决顺序队列中需要移动大量元素的问题。
链式队列由一系列结点组成，每个结点包含一个数据元素和指向下一个结点的指针。
入队操作：创建一个新的结点，并将其添加到链表的尾部，更新rear指针。
出队操作：将链表的头部结点移除，并更新front指针。
链式队列的优势是没有固定的大小限制，可以根据需要动态地分配内存空间。
但其缺点是访问元素的速度较慢，需要通过指针进行遍历。
三、队列的应用场景队列在计算机科学中有广泛的应用。
下面列举一些常见的应用场景：1. 线程池：线程池中的任务通常以队列的形式进行排队，工作线程从队列中获取任务并执行。
2. 消息队列：在分布式系统中，消息队列用于异步通信，生产者将消息发送到队列中，而消费者从队列中获取消息进行处理。
A—熟练掌握B—理解C—了解第一章：绪论1. 基本概念：包括数据的逻辑结构、数据的存储结构和数据的相关运算。
C四类数据组织结构：集合、线性表、树形、图状结构C数据的存储方式：顺序存储和链式存储。
B2.算法和分析算法的特征、时间复杂度的分析和常见的时间复杂度增长率排序、空间复杂度B本章重点：分析算法时间复杂度例1. 下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的D例2. 以下那一个术语与数据的存储结构无关？（）A．栈 B. 哈希表 C. 线索树 D. 双向链表A．例3.．求下段程序的时间复杂度：void mergesort(int i, int j){int m;if(i!=j){m=(i+j)/2;mergesort(i,m);mergesort(m+1,j);merge(i,j,m);}}其中mergesort()用于对数组a[n]归并排序，调用方式为mergesort(0,n-1);，merge()用于两个有序子序列的合并，是非递归函数，时间复杂度为。
解：分析得到的时间复杂度的递归关系：为merge（）所需的时间，设为cn（c为常量）。
因此令，有有第二章：线性表1.线性表的基本运算：….. C2.线性表的顺序存储（利用静态数组或动态内存分配）。
相应的表示与操作 A3.线性表的链式存储。
相应的表示与操作。
包括循环链表、双向链表。
A4.顺序存储与链式存储的比较：基于时间的考虑--分别适用于静态的和动态的操作：比如静态查找和插入删除）；基于空间的考虑-- ……. B这也适用于后面用两种方式存储的其他数据结构。
★本章重点：很熟悉顺序表，单链表、双链表，循环链表的基本操作；并学会在各种链表上进行一些算法设计（与基本操作类似的操作或组合），请仔细复习。
例4．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。
栈的操作(实验报告范文)栈的基本操作,附带源程序实验三栈和队列3.1实验目的：（1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；（2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。
3.2实验要求：（1）复习课本中有关栈和队列的知识；（2）用C语言完成算法和程序设计并上机调试通过；（3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。
3.3基础实验[实验1]栈的顺序表示和实现实验内容与要求:编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序栈（2）插入元素（3）删除栈顶元素（4）取栈顶元素（5）遍历顺序栈（6）置空顺序栈分析:栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top==MA某NUM-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。
出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。
通常栈空作为一种控制转移的条件。
注意：（1）顺序栈中元素用向量存放（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top （通常称top为栈顶指针）来指示当前栈顶位置参考程序:#include<tdio.h>#include<tdlib.h>#defineMA某NUM20栈的基本操作,附带源程序#defineElemTypeint/某定义顺序栈的存储结构某/ typedeftruct{ElemTypetack[MA某NUM]; inttop;}SqStack;/某初始化顺序栈某/voidInitStack(SqStack某p){if(!p)printf("Eorror");p->top=-1;}/某入栈某/voidPuh(SqStack某p,ElemType某){if(p->top<MA某NUM-1){p->top=p->top+1;p->tack[p->top]=某;}eleprintf("Overflow!\n");}/某出栈某/ElemTypePop(SqStack某p){ElemType某;if(p->top!=0){某=p->tack[p->top];printf("以前的栈顶数据元素%d已经被删除！\n",p->tack[p->top]);p->top=p->top-1;return(某);}ele{printf("Underflow!\n");return(0);}}/某获取栈顶元素某/ ElemTypeGetTop(SqStack某p) {ElemType某;if(p->top!=0){某=p->tack[p->top];return(某);}ele{printf("Underflow!\n");栈的基本操作,附带源程序return(0);}}/某遍历顺序栈某/ voidOutStack(SqStack某p) {inti;if(p->top<0)printf("这是一个空栈！");printf("\n");for(i=p->top;i>=0;i--)printf("第%d个数据元素是：%6d\n",i,p->tack[i]); }/某置空顺序栈某/voidetEmpty(SqStack某p){p->top=-1;}/某主函数某/main(){SqStack某q;inty,cord;ElemTypea;do{printf("\n");printf("第一次使用必须初始化！\n");printf("\n主菜单\n");printf("\n1初始化顺序栈\n");printf("\n2插入一个元素\n");printf("\n3删除栈顶元素\n");printf("\n4取栈顶元素\n");printf("\n5置空顺序栈\n");printf("\n6结束程序运行\n");printf("\n--------------------------------\n"); printf("请输入您的选择(1,2,3,4,5,6)");canf("%d",&cord);printf("\n");witch(cord){cae1:{q=(SqStack某)malloc(izeof(SqStack));InitStack(q);OutStack(q);}break;cae2:栈的基本操作,附带源程序{printf("请输入要插入的数据元素：a="); canf("%d",&a);Puh(q,a);OutStack(q);}break;cae3:{Pop(q);OutStack(q);}break;cae4:{y=GetTop(q);printf("\n栈顶元素为：%d\n",y); OutStack(q);}break;cae5:{etEmpty(q);printf("\n顺序栈被置空！\n"); OutStack(q);}break;cae6:e某it(0);}}while(cord<=6);}[实验2]栈的链式表示和实现实验内容与要求:编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化链栈（2）链栈置空（3）入栈（4）出栈（5）取栈顶元素（6）遍历链栈分析:链栈是没有附加头结点的运算受限的单链表。
《数据结构》学习指导说明：本指导以《数据结构》(C语言版)(严蔚敏等编著,清华大学出版社1997年出版，国家级优秀教材特等奖)和《数据结构题集》(严蔚敏等编著,清华大学出版社1999年出版)为教学主要参考书。
一、绪论1、学习目的：明确数据结构课程在本专业知识结构中的地位，作用。
课程的特点，教学的要求，方法。
明确数据结构所研究的问题以及有关基本概念。
初步掌握抽象数据类型的表示与实现，初步明确算法分析的作用与分析的重点，初步掌握算法分析的方法。
2、学习重点：数据的逻辑结构、存储结构及其算法，数据结构的有关概念，抽象数据类型及其表示与实现，算法，算法设计的要求，算法的时间复杂度和算法的空间复杂度。
3、学习难点：数据结构的有关概念，抽象数据类型的表示与实现；算法的时间复杂度分析。
4、课程内容与基本要求(一) 数据结构的引入(1) 三个世界：现实世界，信息世界，机器世界。
数据结构要解决的就是实现从现实世界到信息世界，再由信息世界到机器世界的转换，从而实现用计算机来解决问题的目的。
(2) 非数值问题(结合三个世界讲)：控制，管理，数据处理(3) 数值问题：数值计算(4)数据结构：从学科角度讲，数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及他们之间的关系和操作等等的学科。
(二) 课程的地位，性质，作用。
(1) 地位: 计算机专业的核心课程之一。
(2) 性质: 算法理论基础和软件设计的技术基础课。
(3) 作用: 程序设计的基础，编译程序，操作系统，数据库系统及软件系统和应用程序的基础(三) 数据结构的产生和发展(四) 课程的特点，学习的要求教材：《数据结构》(C语言版)严蔚敏等编著北京清华大学出版社1997年参考书：《数据结构》许卓群等编著北京高等教育出版社1987年数据结构实用教程》（C/C++描述）徐孝凯北京清华大学出版社1999年《数据结构题集》严蔚敏等编著北京清华大学出版社1999年《数据结构导学》苏光奎等编著北京清华大学出版社20XX年《数据结构》(C语言篇)－习题与解析李春葆编著北京清华大学出版社20XX年《数据结构》实验指导书唐开山自编讲义20XX年(五) 基本概念和术语数据数据元素数据对象(4)数据结构:按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它存储到计算机的存储器中，并在这些数据上定义了一个运算的集合，叫做一个数据结构。
.
数学与计算科学学院实验报告
实验项目名称队列的链式表示和实现
所属课程名称数据结构
实验类型验证型
实验日期2013年11月14日
班级
学号
姓名
成绩
错误分析：表示未对P进行定义，错误分析：表示DestroyQueue未定义，
观察上面的输出窗口，发现此三组数据测试无误。
附录1：源程序
附录2：实验报告填写说明
1．实验项目名称：要求与实验教学大纲一致。
2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。
3．实验原理：简要说明本实验项目所涉及的理论知识。
4．实验环境：实验用的软、硬件环境。
5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。
概括整个实验过程。
对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。
对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。
对于创新性实验，还应注明其创新点、特色。
6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。
7．实验结论（结果）：根据实验过程中得到的结果，做出结论。
8．实验小结：本次实验心得体会、思考和建议。
9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。
