二级公共基础知识第一章数据结构与算法

一、算法的基本概念
计算机解题的过程其实就是实现某种算法，这种算法叫做计算机算法。
1。算法的基本特征:可行性、确定性、有限性和充分信息。
2。算法的基本要素:算法中数据的运算和操作，算法的控制结构。
3。算法设计的基本方法:枚举、归纳、递归、递归、对半递归技术和回溯。
4。算法设计的要求:正确性、可读性、健壮性、效率和低存储要求
2。算法的复杂性
1。算法的时间复杂度:指执行算法所需的计算工作量
2。算法的空之间的复杂度:执行这个。数据的逻辑结构包括集合、线性结构、树形结构和图形结构。
2。数据的存储结构:数据的逻辑结构存储在计算机空中，存储形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等。
四。数据结构的图形化表示:
在数据结构中，没有前件的节点称为根节点；没有后继者的节点成为终端节点。插入和删除是对数据结构的两种基本操作。还有搜索、分类、合并、分解、复制和修改等。
五、线性结构和非线性结构
根据一个数据结构中数据元素之间上下文关系的复杂程度，数据结构一般分为线性结构和非线性结构两种。
线性结构:not 空数据结构:只有一个根节点；每个节点最多有一个前部和一个后部。非线性结构:如果一个数据结构不是线性的，就称为非线性结构。
常见的线性结构:线性表、栈、队列
VI。线性表的定义
线性表是n个元素(A1，A2，A3……)的有限序列。除了第一个数据元素，表中的每个数据元素都只有一个前提。除了最后一个只有一个后半部分。即线性表是空表，也可以表示为(a1，a2，…an)，其中ai(I=1，2，…n)是属于数据对象的元素，通常也称为线性表中的节点。
非空线性表具有以下特征:
(1)只有一个根节点a1，没有前件；
(2)终端节点an只有一个，没有后继；
(3)除了根节点和终端节点，其他所有节点都只有一个前件，也只有一个前件。线性表中节点的个数n称为线性表的长度。当n=0时，称为空表。
七。线性表的顺序存储结构
线性表的顺序表是指一组地址连续的存储单元对线性表的数据元素进行顺序存储。
线性表的顺序存储结构有以下两个基本特征:
1。线性表中所有元素的存储空是连续的；
2。线性表中的数据元素按照逻辑顺序存储在存储室空中。
也就是线性表逻辑相邻，物理相邻，所以知道第一个元素头地址和每个元素占用的字节数，就可以找到任意一个元素头地址。
假设线性表的每个元素需要占用K个存储单元，所占用的第一个单元的存储地址作为数据元素的存储位置。那么线性表中第I个数据元素的存储位置LOC(ai+1)与第I个数据元素的存储位置LOC(ai)之间满足以下关系:
LOC(AI+1)= LOC(AI)+K
LOC(AI)= LOC(a1)+(
在顺序存储结构中，每个数据元素的地址可以通过公式①计算，所以线性表的顺序存储结构是一种随机存取存储结构。
在线性表的顺序存储结构下，可以对线性表进行以下操作:
插入、删除、查找、排序、拆分、合并、复制、反转。资料来源:www.examda.com。顺序表的插入操作
线性表的插入操作是指表中的第I个位置。A2 …ai…an)变成长度为n+1的线性表(a1，a2 … x，ai…an)。
该算法的时间主要花在循环节点后移语句上，执行次数为n-I+1。
当I=n+1，case，时间复杂度o(1)当I=1，最坏情况，时间复杂度o(n)
算法的平均时间复杂度为o(n)
IX。顺序表的删除操作
线性表的删除操作是指A2 …ai…an)变成长度为n-1 (a1，a2…ai-1，ai+1…an)的线性表。
当I=n时，时间复杂度o(1)，当I=1时，时间复杂度o(n)，平均时间复杂度o (n) [/br Stack其实是一个线性表，只是一个特殊的线性表。栈是一个线性表，只能在表的一端插入和删除，通常称为栈顶()和栈底()。当表中没有元素时，称为空 stack。堆栈的顶部元素总是最后插入的元素，因此是第一个删除的元素；堆栈底部的元素总是第一个插入的元素，因此也是最后一个删除的元素。
假设堆栈S = (a1，A2，A3，...an)，那么A1称为堆栈的底部元素，An称为堆栈的顶部元素。堆栈中的元素按照A1、A2、A3的顺序被推入堆栈...一个，被推出堆栈的第一个元素应该是顶部元素。后进先出。
2。栈及其操作的顺序存储
S (1: m)作为栈的顺序存储空间空。m是电池组的容量。
有三种基本的堆栈操作:推入、推出和读出。
栈操作:在栈顶插入一个新元素。
首先将顶部指针放入一个(+1)，然后将新元素插入顶部指针所指的位置。
栈顶操作:取出栈顶元素，赋给指定变量。
首先将top元素赋给指定的变量，然后将top指针回退一(-1)
读取top元素:将top元素赋给指定的变量。顶部指针不会改变。