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

《数据结构与算法设计知识点.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.数据结构与算法设计知识点试题类型：本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10%），是非判断题（10%），单项选择题（40%），算法填空题（10%），算法应用题（20%)，算法设计题（10%）。第一章绪论重点内容及要求：1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元素之间的关系等）。数据：所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据（集合）中的一个“个体”，数据结构中的基本单位，在计算机程序中通常作为一个

2、整体来考虑和处理。数据项：是数据结构中讨论的最小单位，数据元素可以是一个或多个数据项的组合关键码：也叫关键字（Key），是数据元素中能起标识作用的数据项。其中能起到唯一标识作用的关键码称为主关键码（简称主码）；否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多个次码。关系：指一个数据集合中数据元素之间的某种相关性。数据结构：带“结构”的数据元素的集合。这里的结构指元素之间存在的关系。word范文.数据类型：是一个值的集合和定义在此集合上的一组操作的总称。1、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素的表示与

3、关系的表示、两类存储结构：顺序存储结构和链式存储结构）。数据结构包括逻辑结构和物理结构两个层次。数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。存储结构：顺序存储结构和链式存储结构顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系；链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑

4、关系。2、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。算法：是为了解决某类问题而规定的一个有限长的操作序列或处理问题的策略一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出设计算法时，通常还应考虑满足以下目标：1.正确性，2.可读性，3.健壮性4.高效率与低存储量需求word范文.如何估算算法的时间复杂度？算法=控制结构+原操作（固有数据类型的操作）算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间算法的执行时间与原操作执行次数之和成正比算法的空间复杂度定义为:S(n)=O(g(n))

5、表示随着问题规模n的增大,算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括:1.输入数据所占空间2.程序本身所占空间3.辅助变量所占空间第二章线性表重点内容及要求：1、掌握线性表的顺序存储结构，了解顺序表的存储特点（数据元素在内存中依次顺序存储），优点：可随机存取访问；缺点：结点的插入/删除操作不方便。线性表：是一种最简单的数据结构，也是构造其它各类复杂数据结构的基础。一个数据元素的有序（次序）集。它有顺序和链式两种存储表示方法。线性表必有：1．集合中必存在唯一的一个“第一元素”word范文.2．集合中必存在唯一的一个“最

6、后元素”3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱定义如下：typedefintElemType;typedefstruct{ElemType*elem;//存储数据元素的一维数组；intlength;//线性表当前长度；intlistsize;//当前分配数组容量；}SqList;VoidInitSqList(SqListA,intmaxsize)//初始化线性表{A.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!A.elem){exit

7、(0);}A.length=0;A.listsize=LIST_INIT_SIZE;return;}1、了解线性表的链式存储结构，重点掌握带头结点的单链表的基本操作（结点的插入与删除运算），了解单向循环链表和双向链表存储表示方法。单链表：用一组地址任意的存储单元存放线性表中的数据元素。以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素或数据元素的映象)单链表是一种顺序存取的结构，求以此为存储表示的线性表长度，可设置一个计数器3、了解有序线性表的特点（顺序有序表、有序链表）。有序线性表：线性表中的数据元素相互之间可以比

8、较word范文.，并且数据元素在线性表中依值非递减或非递增有序排列，即ai≥ai-1或ai≤ai-1(i=2,3,…,n)，则称该线性表为有序表(OrderedList)4、学会