数据结构考研真题及知识点解析
考察目标
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(x
A.O(logn) B.O(n) C.O(nlogn) hmddy(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表示当前遍历了多少结点,当i>k时,指针p
随着每次遍历,也向前移动一个结点。当遍历完成时,p或者指向表头结点,或者指向链表
中倒数第k个位置上的结点。
(3)算法描述:
int locate(Linklist list, int k)