数据结构考研复习纲要

《数据结构考研复习纲要》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构复习纲要数据结构复习纲要推荐教材数据结构（C语言版）.严蔚敏，吴伟民等.清华大学出版社全国硕士研究生入学统一考试计算机学科专业基础综合考试大纲解析(2013年版).高等教育出版社数据结构学习指导与典型题解.朱战立，张选平.西安交通大学出版社数据结构与算法—学习指导与习题解析.张铭，赵海燕等.高等教育出版社大连考研网（www.popedu.net）上有很多相关的信息和资料，同学们可以去查阅和下载复习计划1、C/C++预习的结果可以用C/C++语言执行数据结构中算法的执行；预习的内容是C/C++语法、基本语句、上机操作例题

2、1（线形表算法会用到）：下面的代码，a代表什么？typedefintINTVEC[10];INTVECa;例题2（二叉树的遍历用）如何把函数当参数传给另一个函数typedefvoid(*FUN)(int);voidf(int){cout<<"hello";}FUNPF=f;typedefstruct{inta;intb;}s1,*ps1;inta1=sizeof(char*);intb1=sizeof(double*);intc1=sizeof(ps1);例题3（华为公司的面试题，线性表要用到的知识点）ps1pp=news1(

3、);//pp+1的指向的地址是多少是PP中的地址加上SIZEOF(NEWS1())例题4（排序要用到的知识点）intve1[100];intk=sizeof(ve1);intf2(intve2[100]){数据结构复习纲要inta=sizeof(ve2);return1;}例题5（请写出下面的非递归程序）G(M,N)=G(M-1,2N)+NG(0,X)=0;M>=0;2、数据结构第一章绪论（第1天）绪论数据结构算法基本概念1数据2数据元素3数据对象4ADT5数据结构6存储结构(物理结构)1集合2线性结构3树形结构4图形结构或网

4、状结构线性结构非线性关系存储结构逻辑结构1顺序2链式3索引4散列注意：5个无关1与数据元素本身的形式2与数据元素本身的内容3与数据元素相对的位置4与所含数据元素的个数5与数据的存储基本概念算法分析1算法2特性3要求1问题规模2基本语句3时间复杂度4空间复杂度重点难点：1算法与程序的区别2算法与数据结构的关系数据结构复习纲要第二章线性表（第2-3天）线性表逻辑结构基本概念1何为线性表2逻辑特征ADT定义1ADT定义2基本操作应用1顺序表特点2类型定义3基本操作的实现与时间性能比较其他结构1循环链表2双向链表3静态链表1单链表特点

5、2类型定义3基本操作的实现与时间性能顺序结构链式结构存储结构多项式相加减链表的优缺点恰好与顺序表相反（1）基于存储的考虑：容量可知不可知（2）基于运算的考虑：插入、删除操作的快与慢（3）基于环境的考虑◆“较稳定”的线性表选择顺序存储◆频繁插入删除的选择链式存储重点难点：1、存取结构与存储结构异同点2、顺序表与链表各自优点、缺点以及在实际应用中任何选取存储结构2009真题42.已知一个带有表头结点的单链表，结点结构为DataLink假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数

6、第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求：1.描述算法的基本设计思想2.描述算法的详细实现步骤3.根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处请给出简要注释。数据结构复习纲要第三章栈、队列和数组（第4-5天）比较特殊线性表数组寻址的计算方法1对称矩阵2三角矩阵3对角矩阵特殊矩阵压缩存储广义线性表比较对列栈逻辑结构存储结构逻辑结构存储结构逻辑结构存储结构1栈定义2操作特性3ADT定义顺序栈链栈1基本操作的实现2时间性

7、能比较顺序队列链式队列1队列定义2操作特性3ADT定义1基本操作的实现2时间性能1数组定义2基本操作3ADT定义顺序存储按列优先按行优先重点难点提示：1、存储结构不同的栈的栈空、栈满条件是什么？2、存储结构不同的队列的队空、队满条件是什么？3、队列与循环链表的关系及其各自特点？4、能否用循环链表实现队列的操作？历年真题：2009真题1：为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是A、栈B、队列C、树D、图2

8、009真题2：设栈S和队列Q的初始状态均为空，原始abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，则7个元素出队的顺序是bdcfeag，则栈S的容量至少是A、1B、2C、3D、42010真题1：若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行。但不