西大软件工程｜20届考研打好专业课基础，第一章详细解读！

导师简介

妍梓学姐，2015年以专业排名第一的成绩考入西北大学软件工程专业，总分389，专业课128分，读研期间一直在从事数据结构专业课的考研辅导，对西北大学历年考研真题侧重点有深入了解，真正做到了知识点与考点相结合，钻研出一套独有的解题思路和冲刺阶段快速提分的技巧方法。（以下内容由妍梓学姐分享，小彦整理）

上一次针对2020届的同学如何进行基础知识的复习和复习重点做了简单的介绍。俗话说的好，经济基础决定上层建筑，打好基础才能全面理解本知识点的延伸。

那么从第一章开始，对重点的知识点进行讲解。

PART 1 数据类型划分

数据元素之间的逻辑结构有四种基本类型，如下所示。

1集合：结构中的数据元素除了”同属于一个集合”外，没有其它关系。

2线性结构：结构中的数据元素之间存在一对一的关系。

3树型结构：结构中的数据元素之间存在一对多的关系。

4图状结构或 状结构：结构中的数据元素之间存在多对多的关系。

数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的物理结构存储方式：顺序存储结构和链式存储结构。

数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。

在后面的章节中，主要采用的结构分为以下几种：

PART 2 算法以及特性

算法(Algorithm)：是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。

1有穷性

一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

2确定性

算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。

3可行性

一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。

4输入

一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。

5输出

一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

PART 3算法的时间复杂度

算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作 T(n)=O(f(n))，称作算法的渐近时间复杂度(Asymptotic Time complexity)，简称时间复杂度。

一般地，常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。

例１ 两个n阶方阵的乘法

for(i=1，i<=n; ++i)

for(j=1; j<=n; ++j)

{ c[i][j]=0 ;

for(k=1; k<=n; ++k)

c[i][j]+=a[i][k]*b[k][j] ; }

由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=n3　时间复杂度为T(n)=O(n3)

例２ {++x; s=0 ;}

将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1) 。如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。

例３ for(i=1; i<=n; ++i)

{ ++x; s+=x ; }

语句频度为：2n，其时间复杂度为：O(n) ，即为线性阶。

例４ for(i=1; i<=n; ++i)

for(j=1; j<=n; ++j)

{ ++x; s+=x ; }

语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为平方阶。

以下六种计算算法时间的多项式是最常用的。其关系为：

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)

数时间的关系为：O(2n)<O(n!)<O(nn)

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。

有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。

今天的这节主要对第一章的重点内容进行了讲解。到此为止啦，咱们下回见呀～

别怕，勇敢往前走吧！文彦一直都在！

如何get所有这些？来文彦考研专业课与妍梓学姐进一步交流吧！更可找群管理直接 名冲刺班哦！群 ：851630618

LY18980051143也可加小彦微信直接咨询 名哟~