数据结构与算法设计知识点

试题类型：

本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。

第一章 绪论

重点内容及要求：

1、 了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元素之间的关系等）。

数据： 所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。

数据元素：是数据（集合）中的一个“个体”，数据结构中的基本单位，在计算机程序中通常作为一个整体来考虑和处理。

数据项：是数据结构中讨论的最小单位，数据元素可以是一个或多个数据项的组合

关键码：也叫关键字（Key），是数据元素中能起标识作用的数据项。

其中能起到唯一标识作用的关键码称为主关键码（简称主码）；否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多个次码。

关系：指一个数据集合中数据元素之间的某种相关性。

数据结构：带“结构”的数据元素的集合。这里的结构指元素之间存在的关系。

数据类型：是一个值的集合和定义在此集合上的一组操作的总称。

2、 掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。

数据结构包括逻辑结构和物理结构两个层次。

数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示

逻辑结构有四种：线性结构、树形结构、图状结构、集合结构 数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。

存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种

1

特定的关系来表示数据元素之间的逻辑关系；

链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。

3、 了解算法分析的基本方法，掌握算法时间复杂度相关的概念。

算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略

一个算法必须满足以下五个重要特性：1．有穷性 2．确定性 3．可行性4．有输入 5．有输出

设计算法时，通常还应考虑满足以下目标： 1.正确性，2.可读性， 3.健壮性 4.高效率与低存储量需求 如何估算 算法的时间复杂度？ 算法 = 控制结构 + 原操作

（固有数据类型的操作）

算法的执行时间 = 原操作(i)的执行次数×原操作(i)的执

∑ 行时间

算法的执行时间与 原操作执行次数之和成正比 算法的空间复杂度定义为: S(n) = O(g(n))

表示随着问题规模 n 的增大,算法运行所需存储量的增长率与 g(n) 的增长率相同。

算法的存储量包括: 1. 输入数据所占空间 2. 程序本身所占空间 3. 辅助变量所占空间

第二章 线性表

重点内容及要求：

1、 掌握线性表的顺序存储结构，了解顺序表的存储特点（数据元素在内存中依次顺序存储），优点：可随机存取访问；缺点：结点的插入/删除操作不方便。

线性表：是一种最简单的数据结构，也是构造其它各类复杂数据结构的基础。一个数据元素的有序（次序）集。它有顺序和链式两种存储表示方法。

线性表必有：

1．集合中必存在唯一的一个“第一元素” 2．集合中必存在唯一的一个 “最后元素” 3．除最后元素在外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱 定义如下：

2

typedef int ElemType; typedef struct{

ElemType*elem; //存储数据元素的一维数组； int length; //线性表当前长度； int listsize; //当前分配数组容量； }SqList;

Void InitSqList(SqList A,int maxsize)//初始化线性表 {

A.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!A.elem) {

exit(0);

}

A.length = 0;

A.listsize = LIST_INIT_SIZE; return ; }

2、 了解线性表的链式存储结构，重点掌握带头结点的单链表的基本操作（结点的插入与删除运算），了解单向循环链表和双向链表存储表示方法。

单链表：用一组地址任意的存储单元存放线性表中的数据元素。 以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点

(表示数据元素 或 数据元素的映象)

单链表是一种顺序存取的结构，求以此为存储表示的线性表长度，可设置一个计数器

3、了解有序线性表的特点（顺序有序表、有序链表）。

有序线性表：线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 ai≥ai-1 或 ai≤ai-1(i = 2,3,…, n)，则称该线性表为有序表(Ordered List)

4、学会对线性表设计相关的算法进行相应的处理。

第三章 排序

重点内容及要求：

1、掌握对顺序表数据记录进行排序的基本思路和常规操作（比较、移动），了解排序算法的稳定性问题。

2、掌握简单选择排序、直接插入排序、冒泡排序算法，了解各种排序算法的特点及时间复杂度。

排序：将一组“无序”的记录序列按某一关键字调整为“有序”的记录序列。

若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之则为外部排序。

选择排序：从记录的无序子序列中“选择”关键字最小或最大的

3