数据结构考研知识点总结.pdf

数据结构考研真题及知识点解析 考察目标 1. 掌握数据结构的基本概念、基本原理和基本方法。 2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复 杂度与空间复杂度的分析。 3. 能够运用数据结构的基本原理和方法进行问题的分析与求解；具备采用C、C++或 Java语言设计与实现算法的能力。 第2章 线性表 一、考研知识点 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储 2.链式存储 3.线性表的应用 二、考查重点 1．线性结构的特点； 2．线性表在顺序存储及链式存储方式下的基本操作及其应用； 3．线性表的顺序存储及链式存储情况下，其不同和优缺点比较，及其各自适用的场合。 单链表中设置头指针、循环链表中设置尾指针而不设置头指针的各自好处； 4．能分析所写算法的时间和空间复杂度。 分析： 线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、 线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链 式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。 线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估 的。线性表一章小的知识点比较少，一般会出一个综合题，并且容易和第三章、第九章和第 十章的内容结合来考，注意对基本知识的理解，能够利用书上的理论解决具体问题。学习过 程中要注意多积累，多看、多写一些相关算法。 三、考研真题 （一）选择题 近几年第2章没有考选择题，只有两个计算时间复杂度的题目，因为此章主要是线性表 的操作，而且又是这门课的一个基础，考综合题的可能性比较大，可以和第3章、第9章和 第10章的内容结合来出题。 1．（11年）设n是描述问题规模的非负整数，下面程序片段的时间复杂度是 （ A ）。 x 2; while(xn/2) x 2*x; A.O(logn) B.O(n) C.O(nlogn) D.O(n)2 2. （12年）求整数n （n 0）的阶乘的算法如下，其时间复杂度是 （ B ）。 int fact(int n) { if(n 1) return 1; return n*fact(n-1); } A. o(logn) B. O(n)2 C. O(nlogn)2 D. O(n)2 分析：考查的是算法时间复杂度的计算。可以放在第二章，实际这内容贯穿每一章内容 中算法的度量。 （二）综合题 1. （09年）已知一个带有表头结点的单链表结点结构为(data,link)，假设该链表只给 出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒 数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1； 否则，只返回0。要求： （1）描述算法的基本设计思想； （2）描述算法的详细实现步骤； （3）根据设计思想和实现步骤，采用程序设计语言描述算法 （使用C或C++或JAVA语 言实现），关键之处给出简要注释。 分析：此题考查线性表的链式存储，主要是线性表的基本操作的应用。做此题时要把握 算法的效率。 （1）算法基本思想如下：从头到尾遍历单链表，并用指针p指向当前结点的前k个结 点。当遍历到链表的最后一个结点时，指针p所指向的结点即为所查找的结点。 （2）详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指 针p1指向当前遍历的结点，指针p指向p1所指向结点的前k个结点，如果p1之前没有k 个结点，那么p指向表头结点。用整型变量i表示当前遍历了多少结点，当ik时，指针p 随着每次遍历，也向前移动一个结点。当遍历完成时，p或者指向表头结点，或者指向链表 中倒数第k个位置上的结点。 （3）算法描述： int locate(Linklist list, int k) {