《数据结构与算法设计知识点(精心整理)》由会员分享，可在线阅读，更多相关《数据结构与算法设计知识点(精心整理)（22页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法设计知识点试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %）， 单项选择题（40 %），算法填空题（10%），算法应用题（20 %），算法设计题（10 %）。第一章 绪论重点内容及要求：1、 了解与数据结构相关的概念（ 集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。数据： 所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。数据元素：是数据（集合）中的一个“个体”，数据结构中的基 本单位，在计算机程序中通常作为一个整体来考虑和处理。数据项：
2、是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合关键码：也叫关键字（Key）,是数据元素中能起标识作用的数据 项。其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。数据类型： 是一个值的集合和定义在此集合上的 一组操作的总 称。2、 掌握数据结构的基本概念、 数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。数据结构包括逻
3、辑结构和物理结构两个层次。数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种 抽象的描述，可以用一个数据元素的集合和定义在此集合上的若 干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现， 因此又称其为存储结构。存储结构：顺序存储结构和链式存储结构顺序存储结构：利用数据元素在存储器中相对位置之间的某种 特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示 数据元素之间的逻辑关系。3、 了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长
4、的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性： 1有穷性 2确定性 3可行性 4有输入 5有输出 设计算法时，通常还应考虑满足以下目标：1. 正确性，2.可读性， 3.健壮性 4.高效率与低存储量需求 如何估算 算法的时间复杂度？ 算法 = 控制结构 + 原操作（固有数据类型的操作）算法的执行时吩=原操作（i）的执行次数X原操作（i）的执行时间算法的执行时间与 原操作执行次数之和成正比 算法的空间复杂度定义为:S（n） = O（g（n） 表示随着问题规模 n 的增大,算法运行所需存储量的增长率与 g（n） 的增长率相同。算法的存储量包括:1. 输入数据所占空间2. 程序本身所
5、占空间3. 辅助变量所占空间第二章 线性表重点内容及要求：1、掌握线性表的顺序存储结构，了解顺序表的存储特点（数据元素在内存中依次 顺序存储），优点：可随机存取访问；缺点：结点的插入/删除操作不方便。线性表：是一种最简单的数据结构，也是构造其它各类复杂 数据结构的基础。一个数据元素的有序（次序）集。它有顺序和 链式两种存储表示方法。线性表必有： 1集合中必存在唯一的一个“第一元素” 2集合中必存在唯一的一个 “最后元素” 3除最后元素在外，均有 唯一的后继； 4除第一元素之外，均有 唯一的前驱 定义如下：typedef int ElemType; typedef struct ElemType
6、*elem; int length; int listsize;SqList;Void/存储数据元素的一维数组/线性表当前长度；/当前分配数组容量；Ini tSqLis t(SqLis t 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、 了解线性表的链式存储结构，重点掌握带头结点的单链表的基本操作（结点 的插入与删除运算），了解单向循环链表和
7、双向链表存储表示方法。单链表：用一组地址任意的存储单元存放线性表中的数据元素。 以元素（数据元素的映象）+ 指针（指示后继元素存储位置 ） =结点（表示数据元素 或 数据元素的映象） 单链表是一种顺序存取的结构，求以此为存储表示的线性表长 度，可设置一个计数器3、了解有序线性表的特点（顺序有序表、有序链表）。有序线性表：线性表中的数据元素相互之间可以比较，并且数据 元素在线性表中依值非递减或非递增有序排列，即a $a 或a Wi i-1ia （i = 2,3,，n）,则称该线性表为有序表（Ordered List）i-14、学会对线性表设计相关的算法进行相应的处理。第三章 排序重点内容及要求：
8、1、掌握对顺序表数据记录进行排序的基本思路和常规操作（比较、移动），了解排序算 法的稳定性问题。2、掌握简单选择排序、直接插入排序、冒泡排序算法，了解各种排序算法的特点及时 间复杂度。排序：将一组“无序”的记录序列按某一关键字调整为“有序” 的记录序列。若整个排序过程不需要访问外存便能完成，则称此类排序问题为 内部排序；反之则为外部排序。选择排序：从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列 的长度基本代码如下for(i=0;in-1;i+)/*外循环控制趟数，n个数选n-1趟*/k=i；/*假设当前趟的第一个数为最值，记在k中*/
9、for(j=i+1;jn;j+)/*从下一个数到最后一个数之间找最值*/if(akaj)/*若其后有比最值更大的*/k=j;/*则将其下标记在k中*/if(k! = i)/*若k不为最初的i值，说明在其后找到比其更大的数*/t二ak;ak二ai;a i二t ;/*则交换最值和当前序列的第一个数*/插入排序：插入排序是将一个数据插入到已经排好序的有序数据 中，从而得到一个新的、个数加一的有序数据。代码如下：void InsertSort ( SqList &L) /对顺序表L作插入排序for ( i=2; i=L.length; +i )if ( L.ri.key L.ri-1.key )L.r
10、0 = L.ri;/复制为哨兵for ( j=i-1; L.r0.key 1) / i1 表明上一趟曾进行过记录的交换lastExchangeIndex = 1;for (j = 1; j i; j+)if (L.rj+1.key L.rj.key) W=L.rj；L.rj =L.rj+1；L.rj+1 = W；/ 互换记录lastExchangeIndex = j;i = lastExchangeIndex; / 一趟排序中无序序列中最后一个记录的位置3、 了解什么是堆？堆是满足下列性质的数列r , r ,，r :1 2 nr （小顶堆rr （大顶堆） i2ii2ir rJ i2i +1J
11、i2i +1第四章 栈和队列重点内容及要求：1、掌握栈和队列的结构特点及基本操作(入栈、出栈/入队、出队)。栈(后进先出)，队列(先进先出)构造空栈：void InitStack_Sq (SqStack &S) / 构造一个空栈 SS.elem = new SElemTypemaxsize;S.top =-1;S.stacksize = maxsize;S.incrementsize=incresize;栈：(入栈)void Push_Sq(SqStack &S, SElemType e)if (S.top = S.stacksize-1) incrementStacksize (S);/ 如
12、果顺序栈的空间已满，应为栈扩容 S.elem+S. top = e;/ 在栈顶插入数据元素栈：(入栈)bool Pop_Sq (SqStack &S, SElemType &e)/ 若栈不空，则删除 S 的栈顶元素，/ 用 e 返回其值，并返回 TRUE ；/ 否则返回 FALSE 。if (S.top = -1) return FALSE;e = S.elemS.top- -; return TRUE;2、对于顺序栈，熟悉栈空和栈满的条件；对于链栈，掌握其栈空的条件。 #include using namespace std;#define INITSIZE 100#define RESIZ
13、E 20 typedef struct int *base;int *top;int stacksize;Sqstack;int Initstack(Sqstack S)S.base=(int *)malloc(INITSIZE*sizeof(int); if(!S.base) return false;S.top=S.base; S.stacksize=INITSIZE;return true;int Clearstack(Sqstack &S)free(S.base);S.base=(int *)malloc(INITSIZE*sizeof(int);S.top=S.base; retur
14、n true;int Stackempty(Sqstack S) if(S.base=S.top) return true; else return false;int Push(Sqstack &S,int e) if(S.top-S.base=S.stacksize)S.base=(int *)realloc(S.base,(RESIZE+INITSIZE)*sizeof(int); if(!S.base) return false;S.top=S.base+S.stacksize; S.stacksize+=RESIZE;*S.top+=e; return true;int Pop(Sqstack &S
