基本数据结构和算法

《基本数据结构和算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、公共基础知识（二级）基本数据结构和算法主讲人：张炎欣笔试考试题型一、选择题（每小题2分，共70分）二、填空题（每小题2分，共30分）公共基础知识占10道选择题，5道填空题，共占30分.数据结构概论考核知识点数据结构的基本概念算法的基本概念线性表的定义栈和队列线性链表循环链表树的基本概念查找技术排序技术数据结构概论重要考点提示数据结构的基本概念；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构算法的基本概念；算法复杂度的概念和意义（时间复杂度和空间复杂度）线性表的定义；线性表的顺序存储结构及其插入与删除运算栈和

2、队列的定义；栈和队列的顺序存储结构及其基本运算线性链表、双向链表与循环链表的结构及其基本运算树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序、后序遍历顺序查找与二分法查找算法基本排序算法(交换类排序、选择类排序、插入类排序)一、数据结构概论数据、数据元素和数据项的概念数据结构的概念定义：由逻辑结构S、基本运算集Δ和存储实现D所构成的整体（S，Δ，D）。构成：包括逻辑结构和基本运算两部分。数据的逻辑结构定义：是指数据元素之间逻辑关系的整体。是数据的组织形式。四类基本逻辑结构:集合、线性结构、树型结构、图状结构（逻辑结构

3、的图形表示）非线性结构一、数据结构概论数据的存储结构定义：数据按逻辑结构规定的关系在计算机存储器中的存放方式（也称物理结构）。存储结构的三个主要部分：存储结点：每个结点存储一个数据元素数据元素间关联方式的表示，即逻辑结构的计算机内部表示。附加设施，如为便于运算实现而设置的“哑结点”等。存储结点之间可以有四种关联方式（称为基本存储方式）顺序存储/链式存储/索引存储/散列存储二、算法及其描述重点提示算法的基本概念算法设计的要求算法复杂度的概念和意义（时间复杂度和空间复杂度）二、算法及其描述算法的基本概念定义：求解给定类型问题所需的

4、所有“处理步骤”及其执行顺序，使得给定类型的任何问题能通过有限的指令序列、在有限的时间内被求解。算法的5个特性：有穷性确定性可行性输入输出二、算法及其描述算法设计的要求正确性可读性健壮性效率与低存储量需求算法的描述可以用自然语言，也可用计算机程序设计语言二、算法及其描述算法的时间复杂度和空间复杂度时间复杂度：是指执行算法所需要的计算工作量。但有时使用这种绝对时间单位来衡量算法的效率是不合适的，所以又采用最坏情况复杂度和平均时间复杂度。最坏情况时间复杂度：是指在规模为n时，算法所执行的基本运算次数。平均时间复杂度：各种特定输入下

5、的基本运算次数的加权平均值空间复杂度：指执行这个算法所需要占用存储空间的大小。算法好坏比较：当问题规模n趋于无穷大时所需时间小的算法好（P5例）。三、线性表重点提示线性结构的定义与特征线性表的定义线性表的顺序存储实现—顺序表顺序表上插入与删除元素的运算三、线性表线性结构与线性表的概念线性结构：定义：是n(n>=0)个数据元素（结点）的有穷序列。说明：同一线性结构中的元素必定具有相同特性，相邻数据元素之间存在着序偶关系。描述：将含n(n>0)个结点的线性结构表示成(a1,…,ai-1,ai,ai+1,…,an）。其中ai(0

6、<=n)代表一个结点，a1称为起始结点,an称为终端结点。“i”称为ai在线性表中的序号或位置。对任意一对相邻结点，ai称为ai+1的直接前趋元素，ai+1称为ai的直接后断元素。三、线性表线性结构与线性表的概念线性结构的基本特征存在惟一的一个被称为“第一个”的数据元素存在惟一的一个被称为“最后一个”的数据元素除起始结点外，其他结点有且仅有一个直接前趋；除终端结点外，其他结点有且仅有一个直接后继；线性表的概念定义：线性表的逻辑结构是线性结构线性表的长度：指所含结点的个数。表长为0的表称为空表。三、线性表线性表

7、的顺序存储结构—顺序表顺序表：即用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的特点：逻辑结构中相邻的结点在存储结构中仍相邻。顺序表的容量：指线性表实际达到的最大长度；表长指当前表的长度，表长小于或等于表的容量。插入、删除运算在顺序表上的实现插入删除四、线性单链表、双向链表与循环链表的结构及其基本运算重点提示线性表的链式存储结构—单链表，在单链表上插入与删除结点的操作双向链表与循环链表的结构在双向链表中插入与删除结点的基本操作线性表的链式存储结构—单链表单链表表示法的基本思想是用指针表示结点间的逻辑关系。结点形式为：

8、所有结点通过指针的链接而组织成单链表。插入、册除运算在单链表上的实现插入:INSERT(L,x,i)在单链表上找到插入位置生成一个值为X的新结点将新结点链入C语言描述：s->next=p->next;p->next=s;四、线性单链表、双向链表与循环链表next(指针域)da