数据结构考研总结

《数据结构考研总结》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构考研总结总结数据结构考研真题及知识点解析考察目标1.掌握数据结构的基本概念、基本原理和基本方法。2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3.能够运用数据结构的基本原理和方法进行问题的分析与求解；具备采用C、C++或Java语言设计与实现算法的能力。第2章线性表一、考研知识点（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储2.链式存储3.线性表的应用二、考查重点1．线性结构的特点；2．线性表在顺序存储及链式存储方式下的基本操作及其应用；3．线性表的顺序存储及链式

2、存储情况下，其不同和优缺点比较，及其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针的各自好处；4．能分析所写算法的时间和空间复杂度。分析：线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。线性表一章小的知识点比较少，一般会出一个综合题，并且容易和第三章、第

3、九章和第十章的内容结合来考，注意对基本知识的理解，能够利用书上的理论解决具体问题。学习过程中要注意多积累，多看、多写一些相关算法。三、考研真题（一）选择题近几年第2章没有考选择题，只有两个计算时间复杂度的题目，因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，可以和第3章、第9章和第10章的内容结合来出题。1．（11年）设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（A）。x=2;p;for(i=0;i<=(high-lop=R[lop;}}voidconverse(intR[],intn,i

4、ntp){reverse(R,0,p-1);reverse(R,p,n-1);reverse(R,0,n-1);}（3）上述算法中三个reverse函数的时间复杂度分别是O(p/2)、O((n-p)/2)、O(n/2)，故所设计算法的时间复杂度为O(n)，空间复杂度为O(1)。解法二：算法思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。时间复杂度为O(n)，空间复杂度为O(p)。3.（11年）一个长度为L（L>=1）的生序列S，处在第┌L

5、/2┐个位置的数称为S的中位数，例如，若序列S1=（11,13,15,17,19），则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2,4,6,8,20），则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出