北京分校

考试资讯

      408计算机综合中的数据结构，占试卷分值为45分。因此，备考2020考研408计算机综合考研者，需要认真对待数据结构中的重难点知识。接下来，北京文都考研网小编分享出“408数据结构考点知识:线性表”，供考生参考。

2020考研408数据结构考点知识:线性表

点睛点:顺序表、链表应用的综合应用题,主要是以算法设计题的形式出现。

答题要点:算法设计题是数据结构拉开分数的一个关键地方,解题思路如何获取，较优的算法要从最基本的算法以及题目的要求入手全面考虑，采用归纳法找规律，实例法找特点，同时注意基本功的联系。

第一,需要熟练掌握顺序表、链表的基本操作的实现;

第二,牢记“复杂的操作都是由一种或几种基本操作的组合来实现的”,因此对于这些复杂的操作首先要分析它是由哪些基本操作实现的;

第三,考试时,如果不能找到更好的方法，来拿全部分值的能力,就要考虑如何尽可能拿到较多的部分分值,也就是说,题目中“时间和空间上尽可能高效的算法”这一点要求,考生若不能写出优的算法或是花费时间过长而影响后面题目的作答时间,那么次优的或者较笨的算法能写出来也会拿到部分分值;

第四,平时积累算法设计的经验。

本章对于整个数据结构课程的学习都非常重要,是进行算法设计的基础。

 

【例】设有一个长度为 n 的整数序列，所有整数的值有负数、正数和零。编写一个尽可能高效的算法，把所有的负数移动到零和正数之前。要求：

(1)给出算法的设计思路

(2)给出 C 语言算法程序设计

(3)算法的时间和空间复杂度

(1)设计思路：参考快速排序一趟划分的原理，以零作为划分的轴点。算法首先遍历一遍整数序列，找到第一个值为零的元素则停止遍历，然后把表中第一个元素与该元素对换。最后采用任何一种一趟划分的算法把所有负数移到零和正数之前。

另：从两头开始，与 0 进行比较并进行交换。

(2)void partition (int A[], int n){//算法假定 0 元素存在

int i,j

int temp;

for(i=0;i

if(i!=0)

{temp=A[0];A[0]=A[i];A[i]=temp;}

for(i=1,j=0;i

if(A[i]

j++;

if(j!=i)

{ temp=A[j];A[j]=A[i];A[i]=temp;}

}

temp=A[j];A[j]=A[0];A[0]=temp;

}

(3)算法的事件复杂度为 O(n)，空间复杂度 O(1)。

 

【例】设有一个长度为 n 的正整数序列，它的中位数是把他们排好序后位于 n/2 的整数。若序列用无序单链表存储，其所有整数的值互不相等，编写一个时间上尽可能高效的算法，求该序列的中位数。要求：

(1)给出算法的设计思路

(2)给出 C 语言算法程序设计

(3)算法的时间

直接方法：单链表的排序，简单选择，冒泡，插入

推荐方法：题目没有要求空间复杂度，参考计数排序的思想，设置一个辅助数组 Temp[n]，在 Temp[i]中按值的大小记录链表第 i 个结点的元素值在序列中的顺序。算法采用二重循环的方式构造 Temp[i]，在查找值为 n/2 的 Temp[i]。

      以上是北京文都考研网给出的“2020考研408数据结构考点知识:线性表”，希望对参加408计算机考研考生，在复习该部分上面有很大的帮助!祝考研路上顺利!

推荐阅读：

2020考研408数据结构考点知识总结

2020考研计算机408考点知识总结