[专业课]数据结构考研知识点总结
数据结构考研真题及知识点解析
考察目标
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<n/2) x=2*x;
2A.O(logn) B.O(n) C.O(nlogn) D.O(n)
2.(12年)求整数n(n>=0)的阶乘的算法如下，其时间复杂度是( B )。
int fact(int n)
{
if(n<=1) return 1;
return n*fact(n-1);
}
2A. o(logn) B. O(n) C. O(nlogn) D. O(n) 22
分析:考查的是算法时间复杂度的计算。可以放在第二章，实际这内容贯穿每一章内容中算法的度量。
(二)综合题
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)算法描述:
nt locate(Linklist list, int k) i
{
p1=list->link;
p=list;
i=1;
while(p1)
{
p1=p1->link;
i++;
if(i>k)p=p->next; //如果i>k，则p也后移
}
if(p==list)return 0; //链表没有k个结点
else
{
printf(“%\n”,p->data);
return 1;
}
}
2.(10年)设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0，P，n)个位置，即将R中的数据由(X0 X1 „„Xn-1)变换为(Xp Xp+1 „„Xn-1 X0 X1 „„Xp-1)要求:
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度
分析:此题考查的是数组的操作，线性表的顺序存储的核心就是数组，因此此题实质上是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时间和空间复杂度。
解法一:
(1)算法的基本设计思想:可以将这个问题看做是把数组ab转化成数组ba(a代表数
-1组的前p个元素，b代表数组中余下的n-p个元素)，先将a逆置得到ab，再将b逆置得
-1-1-1-1-1-1-1到ab，最后将整个ab逆置得到(ab)=ba。设reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3(p=3)个位置的过程如下:
reverse(0,p-1)得到cbadefgh;
reverse(p,n-1)得到cbahgfde;
reverse(0,n-1)得到defghabc。
注:reverse中，两个参数分别表示数组中待转换元素的始末位置。
(2)算法描述:
void reverse(int R[], int low, int high)
{//将数组中从low到high的元素逆置

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。